Phát hiện dữ liệu bất thường với rừng cô lập

Hầu hết các tiếp cận dựa trên những mô hình đang tồn tại vềphát hiện bất thường đi xây dựng các tiểu sửcủa các thểhiện bình thường, kế đến là nhận dạng ra những thể hiện nào không phù hợp với những tiểu sử bình thường thì cho là bất thường. Đề tài "Phát hiện dữ liệu bất thường với Rừng cô lập" đề cập đến một phương pháp tiếp cận khác biệt vềcơbản đó là cô lập trực tiếp các bất thường thay vì dựa trên mô tảcủa các thểhiện bình thường. Cách tiếp cận này được đềcập trong một bài báo của các tác giảFei Tony Liu, Kai Ming Ting and Zhi-Hua Zhou được đăng vào cuối năm 2008 [27].

NỘI DUNG:

CHƯƠNG 1: MỞ ĐẦU .......................................................................................1

1.1. Đặt vấn đề .....................................................................................................1

1.2. Lịch sửgiải quyết vấn đề ..............................................................................2

1.3. Phạm vi của đềtài.........................................................................................2

1.4. Phương pháp nghiên cứu...............................................................................2

1.5. Nội dung nghiên cứu .....................................................................................3

CHƯƠNG 2: TỔNG QUAN VỀPHÁT HIỆN DỮLIỆU BẤT THƯỜNG..........4

2.1. Tồn tại dữliệu bất thường trong tập dữliệu...................................................4

2.2. Một sốthửthách trong vấn đềphát hiện bất thường ......................................5

2.3. Những khía cạnh liên quan vấn đềphát hiện bất thường................................6

2.3.1. Bản chất của dữliệu ...............................................................................6

2.3.2. Các loại bất thường.................................................................................6

2.3.3. Nhãn dữliệu ...........................................................................................9

2.3.4. Đầu ra của phát hiện bất thường ...........................................................11

2.4. Những ứng dụng cho phát hiện bất thường..................................................11

2.4.1. Phát hiện tấn công ................................................................................11

2.4.2. Phát hiện gian lận .................................................................................12

2.4.3. Phát hiện bất thường vềsức khỏe y tếvà sức khỏe cộng đồng ..............12

2.4.4. Phát hiện sựhưhại của thiết bịcông nghệ ............................................12

2.4.5. Phát hiện bất thường trong quá trình xửlý ảnh .....................................12

2.4.6. Phát hiện bất thường trên dữliệu văn bản .............................................13

2.5. Những kỹthuật phát hiện bất thường đang được sửdụng............................13

2.5.1. Các kỹthuật phát hiện bất thường dựa trên phân lớp (Classification)....13

2.5.2. Phát hiện bất thường dựa trên lân cận gần nhất (Nearest Neighbor) ......14

2.5.3. Các kỹthuật phát hiện bất thường dựa trên gom cụm (Clustering)........15

2.5.4. Các kỹthuật phát hiện bất thường theo thống kê (Statistical)................16

2.5.5. Các kỹthuật phát hiện bất thường dựa vào lý thuyết thông tin

(Information Theoretic) ..................................................................................16

2.5.6. Các kỹthuật phát hiện bất thường theo phổ(Spectral) ..........................17

2.6. Đánh giá hiệu quảcủa giải thuật học ..........................................................17

2.6.1. Nghi thức kiểm tra ...................................................................................17

2.6.1.1. Phương pháp huấn luyện và kiểm tra (Training and Test sets):.......18

2.6.1.2. k-fold cross-validation....................................................................18

2.6.1.3. N-fold cross-validation (leave-one-out) .........................................19

2.6.2. Các độ đo cổ điển .................................................................................19

2.6.3. Đường cong ROC (Receiver Operating Characteristic) [10] .................20

2.6.4. Diện tích dưới đường ROC [10]- Area Under Curve (AUC) .................22

CHƯƠNG 3:......................................................................................................24

KỸTHUẬT RỪNG CÔ LẬP CHO PHÁT HIỆN BẤT THƯỜNG ...................24

3.1. Cây cô lập (iTree) và rừng cô lập (iForest) ..................................................24

3.1.1. Định nghĩa cây cô lập ...........................................................................24

3.1.2. Định nghĩa rừng cô lập .........................................................................24

3.1.3. Độdài đường dẫn h(x) .........................................................................25

3.1.4. Điểm sốbất thường s(x,n).....................................................................25

3.2. Các đặc điểm của cây cô lập........................................................................26

3.2.1. Sựxuất hiện ‘ít và khác biệt’ trong tập dữliệu......................................26

3.2.2. Loại bỏ ảnh hưởng của swamping và masking nhờmẫu kích thước nhỏ27

3.3. Chọn mẫu (sub-sample) ..............................................................................29

3.4. Ưu điểm của rừng cô lập .............................................................................29

3.5. Phát hiện dữliệu bất thường sửdụng rừng cô lập (iForest)..........................29

3.5.1. Giai đoạn huấn luyện (Training) ...........................................................29

3.5.1.1. Giải thuật xây dựng rừng cô lập .....................................................30

3.5.1.2. Giải thuật xây dựng cây cô lập (iTree)............................................31

3.5.2. Giai đoạn đánh giá (Evaluating)............................................................32

3.5.2.1. Hàm tính điểm sốbất thường (AnomalyScore) cho thểhiện x:.......32

3.5.2.2. Hàm tính độdài đường dẫn của mỗi thểhiện trên tập.....................33

3.6. Ví dụminh họa cho việc xây dựng rừng cô lập............................................34

3.6.1. Giai đoạn huấn luyện (xây dựng rừng cô lập) .......................................35

3.6.2. Giai đoạn đánh giá: tính điểm sốbất thường (AnomalyScore) cho các thể

hiện x trên tập kiểm tra...................................................................................40

3.7. Mối tương quan vềcấu trúc và hoạt động giữa cây cô lập (iTree) và cây nhị

phân tìm kiếm (Binary Search Tree -BST). ........................................................41

CHƯƠNG 4.......................................................................................................43

CÀI ĐẶT MÔ HÌNH RỪNG CÔ LẬP ..............................................................43

4.1. Xây dựng rừng cô lập..................................................................................43

4.1.1. Cấu trúc cây cô lập ...............................................................................43

4.1.1.1. Nút tổng quát .................................................................................43

4.1.1.2. Nút trong........................................................................................43

4.1.1.3. Nút ngoài .......................................................................................43

4.1.2. Cấu trúc rừng cô lập .............................................................................43

4.2. Triển khai một sốgiải thuật trên rừng cô lập ...............................................44

4.2.1. Lấy mẫu ngẫu nhiên .............................................................................44

4.2.2. Chọn giá trịcắt ngẫu nhiên ...................................................................45

4.2.3. Xây dựng cây cô lập ..........................................................................45

4.2.4. Xác định độdài đường dẫn của một thểhiện ........................................46

4.2.5. Tính điểm sốbất thường .......................................................................47

4.2.6. Sửdụng mô hình rừng cô lập đểkiểm tra dữliệu..................................47

4.2.6.1. Dữliệu đầu vào ..............................................................................47

4.2.6.2. Xây dựng rừng cô lập từdữliệu đầu vào........................................48

4.2.6.3. Kiểm thửdữliệu ............................................................................49

4.3. Giới thiệu giao diện của mô hình rừng cô lập:.............................................49

CHƯƠNG 5: NỘI DUNG VÀ KẾT QUẢTHỰC NGHIỆM .............................51

5.1. Chọn các tập dữliệu thực nghiệm ...............................................................51

5.2. Thực nghiệm mô hình rừng cô lập trên các tập dữliệu ................................58

5.2.1. Thực nghiệm 1: sửdụng nghi thức k fold cross-validation....................58

5.2.2. Thực nghiệm 2: tập Training và tập Test là một....................................78

5.2.3. Thực nghiệm 3: Loại bỏcác thểhiện bất thường ra khỏi tập Training...80

5.3. Đánh giá kết quảthực nghiệm.....................................................................80

5.3.1. Khẳng định lại một sốtính chất của mô hình dựa vào thực nghiệm:......80

5.3.2. Đánh giá hiệu quảphát hiện của mô hình..............................................81

5.3.3. Nhận xét vềthời gian chạy của chương trình ........................................82

CHƯƠNG 6: KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ....................................84

6.1. Kết luận ......................................................................................................84

6.2. Hướng phát triển .........................................................................................86

TÀI LIỆU THAM KHẢO PL-TLTK 1

PHỤLỤC

LINK DOWNLOAD