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

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC CẦN THƠ CHÂU XUÂN PHƯƠNG PHÁT HIỆN DỮ LIỆU BẤT THƯỜNG VỚI RỪNG CÔ LẬP LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN Cần Thơ - 2009 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC CẦN THƠ CHÂU XUÂN PHƯƠNG PHÁT HIỆN DỮ LIỆU BẤT THƯỜNG VỚI RỪNG CÔ LẬP Chuyên ngành: HỆ THỐNG THÔNG TIN Mã số: 60 44 31 LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN Người hướng dẫn: TS. HUỲNH XUÂN HIỆP Cần Thơ - 2009 LỜI CẢM ƠN Sau hai năm theo học tại lớp Cao Học Hệ Thống Thông Tin khoá 14, và gần sáu tháng thực hiện luận văn, ngoài sự nổ lực của bản thân, tôi đã nhận được rất nhiều sự động viên, chia sẻ, giúp đỡ của quý Thầy Cô, gia đình, bạn bè. Nay luận văn đã hoàn tất, tôi xin chân thành gởi lời tri ân đến: Thầy hướng dẫn, TS. Huỳnh Xuân Hiệp, đã nhiệt tình hướng dẫn và đóng góp nhiều ý kiến quý báu cho tôi trong suốt quá trình thực hiện luận văn. Tất cả các Thầy Cô bộ môn ở Khoa Công Nghệ Thông Tin và Truyền Thông, các Thầy ở học viện IFI-Hà Nội, đã nhiệt tình truyền thụ kiến thức, kinh nghiệm cho chúng em trong suốt thời gian gần hai năm học qua. Tất cả các Thầy Cô, các anh chị em đồng nghiệp bộ môn Toán - khoa Sư Phạm đã phối hợp, tạo điều kiện thuận lợi trong công tác để tôi yên tâm vừa hoàn thành tốt công tác chuyên môn và hoàn thành tốt việc học. Bên cạnh đó, tôi không quên gởi lời cảm ơn đến các bạn cùng lớp Cao học Hệ Thống Thông Tin đã chia sẻ động viên tôi rất nhiều trong quá trình học tập cũng như trong quá trình thực hiện luận văn. Con xin gởi lời tri ân chân thành đến cha mẹ kính yêu, kính chúc cha mẹ luôn khoẻ mạnh để dõi theo sự thành đạt của con cái. Cám ơn chồng con thân yêu của tôi, luôn là chổ dựa tinh thần vững chắc cho tôi có được thành công như ngày hôm nay. Lời cuối, kính chúc tất cả mọi người lời chúc sức khỏe, thành đạt. Châu Xuân Phương. LỜI CAM ĐOAN Tôi xin cam đoan rằng toàn bộ nội dung đề tài “Phát hiện dữ liệu bất thường với Rừng cô lập” là kết quả nghiên cứu của tôi, ngoại trừ các phần được trích dẫn. Người cam đoan Châu Xuân Phương MỤC LỤC LỜI CẢM ƠN LỜI CAM ĐOAN TÓM TẮT ABSTRACT KÍ HIỆU, THUẬT NGỮ VÀ VIẾT TẮT DANH MỤC BẢNG DANH MỤC BIỂU ĐỒ DANH MỤC HÌNH 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 PL-TLTK 4 TÓM TẮT 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]. Đề tài đã nghiên cứu tổng quan về dữ liệu bất thường và các kỹ thuật phát hiện bất thường hiện tại, triển khai thành công kỹ thuật rừng cô lập theo ý tưởng giải thuật được các tác giả đề xuất [27], lựa chọn những tập dữ liệu có những tính chất đặc trưng để tiến hành thực nghiệm trên mô hình và đánh giá hiệu quả phát hiện của mô hình. Các thực nghiệm đã chứng tỏ được việc sử dụng ít bộ nhớ là ưu điểm nổi bật của mô hình bởi vì bộ nhớ đòi hỏi cho mô hình chỉ tăng tuyến tính theo số lượng cây và kích thước mẫu (không bị ảnh hưởng bởi kích thước toàn tập dữ liệu). Ngoài ra, từ thực nghiệm đã khẳng định rằng mô hình sẽ đáp ứng tốt về hiệu quả phát hiện bất thường cho các tập dữ liệu thoả mãn được hai tính chất “ít và khác” ngay cả khi không có thể hiện bất thường nào trong tập kiểm tra. Bên cạnh đó, mô hình đã bộc lộ một số điểm yếu đó là: đối với những tập dữ liệu không thoả mãn tốt hai giả định “ít và khác” thì mô hình cho kết quả không tốt, thậm chí là rất tệ, điều này hạn chế khả năng ứng dụng của mô hình trên các tập dữ liệu được thu thập tự nhiên. ABSTRACT To detect anomaly, most existing approaches construct profiles of normal instances and then classify an instance that does not belong the normal profiles as anomaly. However, this project presents the different approach in which an abnormal object is isolated explicitly. This approach, named as IForest, was proposed by Fei Tony Liu, Kai Ming Ting and Zhi-Hua Zhou iForest [27]. The project has implemented the proposed iForest successfully based on the concept which was presented on [27]. Some experiences have been carried out on some different characteristic datasets in order to evaluate it. The outcome results show that the proposed iForest performs quite well in general. Using less memory is its first advantage because memory requirement is bounded and only grows linearly with the number of trees and sample size. Especially, it shows excellent performances when it is used in the dataset, satisfied ‘minority and difference’ requirement even though there is no anomaly in training set. However, the proposed iForest has weaknesses itself. Its performance is very poor if the dataset does not satisfy the ‘minority and difference’ requirement. This limitation prevents iForest from being applied on real-life domain. KÍ HIỆU, THUẬT NGỮ VÀ VIẾT TẮT Số thứ tự Ký hiệu và viết tắt Diễn giải 1. iTree Isolation tree – cây cô lập 2. iForest Isolation Forest – rừng cô lập 3. BST Binary Search Tree – cây nhị phân tìm kiếm 4. Test Tập kiểm tra 5. Instance Thể hiện 6. Attribute Thuộc tính 7. Anomaly instance Thể hiện bất thường 8. Normal instance Thể hiện bình thường 9. Training Tập huấn luyện 10. sub-sample Mẫu con TỪ KHOÁ Dữ liệu bất thường, phát hiện bất thường, kỹ thuật phát hiện bất thường, cây cô lập, rừng cô lập, anomaly data, anomaly detection, anomaly detection techniques, iForest, iTree, sub-sampling. DANH MỤC BẢNG Số TT Tên bảng Số trang Bảng 2.1 Ma trận hỗn độn cho 2 lớp Anomaly (AC) và Normal (NC) 19 Bảng 2.2 các cặp giá trị (FPR, TPR) 22 Bảng 3.1 Mẫu sub-sample cho cây thứ nhất – cây T1 (hình 3.4) 35 Bảng 3.2 Mẫu sub-sample cho cây thứ 2 – cây T2 (hình 3.5) 37 Bảng 3.3 Mẫu sub-sample cho cây thứ 3 – cây T3 (hình 3.6) 37 Bảng 3.4 Một số tương quan về cấu trúc và hoạt động trên cây iTree và BST 41 Bảng 5.1 Các tập dữ liệu chọn thực nghiệm 51 Bảng 5.2 Mô tả các thuộc tính trong tập Breastw 52 Bảng 5.3 8 thể hiện bất kỳ (ngẫu nhiên) trong tập Breastw 52 Bảng 5.4 Mô tả các thuộc tính của tập RayNau 54 Bảng 5.5 8 thể hiện bất kỳ (ngẫu nhiên) trong tập RayNau 54 Bảng 5.6 Mô tả các thuộc tính trong tập Spambase 55 Bảng 5.7 8 thể hiện bất kỳ (ngẫu nhiên) trong tập Spambase 55 Bảng 5.8 Bảng mô tả thuộc tính trên tập Pima 56 Bảng 5.9 8 thể hiện bất kỳ ( được lấy ngẫu nhiên) trong tập Pima 56 Bảng 5.10 Mô tả các thuộc tính của tập Mammographic 57 Bảng 5.11 8 thể hiện bất kỳ (chọn ngẫu nhiên) trong tập Mammographic 57 Bảng 5.12 Bảng giá trị cho các (FPR,TPR) – tập Breastw 59 Bảng 5.13 Kết quả theo AUC trên tập Breastw theo thực nghiệm 1 62 Bảng 5.14 Bảng giá trị cho các (FPR,TPR – tập RayNau 63 Bảng 5.15 Kết quả tính theo AUC trên tập RayNau theo thực nghiệm 1 66 Bảng 5.16 Bảng giá trị cho các (FPR,TPR) – tập Spambase 67 Bảng 5.17 Kết quả tính theo AUC trên tập Spambase theo thực nghiệm 1 69 Bảng 5.18 Bảng giá trị cho các (FPR,TPR) – tập Pima 70 Bảng 5.19 Kết quả tính theo AUC trên tập Pima theo thực nghiệm 1 73 Bảng 5.20 Bảng giá trị cho các (FPR,TPR) – tập Mammographic 74 Bảng 5.21 Kết quả tính theo AUC trên tập Mammographic theo thực nghiệm 77 Bảng 5.22 Tổng hợp kết quả chọn T, Ψ và giá trị AUC cho 3 thực nghiệm 81 DANH MỤC BIỂU ĐỒ Số TT Tên biểu đồ Số trang Biểu đổ 5.1 Đường cong ROC cho tập Breastw (Thực nghiệm 1) 60 Biểu đồ 5.2 Kết quả thực nghiệm trên tập Breastw 62 Biểu đồ 5.3 Đường ROC cho tập RayNau 63 Biểu đổ 5.4 Kết quả thực nghiệm trên tập RayNau 66 Biểu đồ 5.5 Đường ROC cho tập Spambase (PP1) 67 Biểu đồ 5.6 Kết quả thực nghiệm trên tập Spambase 69 Biểu đổ 5.7 Đường cong ROC (Pima) 70 Biểu đồ 5.8 Kết quả thực nghiệm trên tập Pima 73 Biểu đồ 5.9 Đường ROC cho tập Mammographic 74 Biểu đổ 5.10 Kết quả thực nghiệm trên tập Mammographic 77 Biểu đồ 5.11 Các đường ROC (thực nghiệm 1) 78 Biểu đồ 5.12 Các đường ROC (thực nghiệm 2) 79 Biểu đồ 5.13 Các đường ROC (thực nghiệm 3) 80 Biểu đồ 5.14 So sánh hiệu quả của mô hình trên 3 thực nghiệm 81 DANH MỤC HÌNH Số TT Tên hình Số trang Hình 2.1 Ví dụ đơn giản về các bất thường trong tập dữ liệu hai chiều 4 Hình 2.2 Bất thường theo ngữ cảnh trong một chuỗi nhiệt độ theo thời gian 8 Hình 2.3 Điện tâm đồ của một người 9 Hình 2.4 Phát hiện bất thường theo mô hình một lớp, nhiều lớp 14 Hình 2.5 Huấn luyện và kiểm tra 18 Hình 2.6 k-fold cross-validation 19 Hình 2.7 Đường cong ROC 21 Hình 2.8 So sánh các đường ROC 21 Hình 2.9 Đường ROC và AUC 22 Hình 3.1 Mối quan hệ giữa E(h(x)) và S(x,n) 26 Hình 3.2 (a) Cô lập xi và (b)Cô lập x0 27 Hình 3.3 (a) Tập mẫu gốc (4096 thể hiện),(b): sub-sample(128 thể hiện) 28 Hình 3.4 Cây T1 được xây dựng cho tập mẫu 16 phần tử 36 Hình 3.5 Cây T2 được xây dựng cho tập mẫu 16 phần tử 38 Hình 3.6 Cây T3 được xây dựng cho tập mẫu 16 phần tử 39 Hình 4.1 Mô hình rừng cô lập 50 Hình 5.1 Cây cô lập cho mẫu 8 thể hiện 53 Hình 5.2 Minh họa Top(4) và Bottom(4) với tập Breastw 60 Hình 5.3 So sánh giá trị trung bình giữa 2 nhóm Top(4) và Bottom(4) trên tập Breastw 61 Hình 5.4 Minh họa top(4) và bottom(4) với tập RayNau 64 Hình 5.5 So sánh giá trị trung bình của các thuộc tính trên 2 nhóm Top(4) và Bottom(4) trên tập RayNau 65 Hình 5.6 Top(4) và Bottom(4) trên tập Spambase 67 Hình 5.7 So sánh giá trị trung bình của các thuộc tính của 2 nhóm Top(4) và Bottom(4) trên tập Spambase 68 Hình 5.8 Top(4) và Bottom(4) trên tập Pima 70 Hình 5.9 So sánh giá trị trung bình của các thuộc tính của 2 nhóm Top(4) và Bottom(4) trên tập Pima 72 Hình 5.10 Top(4) và Bottom(4) trên tập Mammographic 68 Hình 5.11 So sánh giá trị trung bình của các thuộc tính của 2 nhóm Top(4) và Bottom(4) trên tập Mammographic 76 1 CHƯƠNG 1: MỞ ĐẦU 1.1. Đặt vấn đề Phát hiện bất thường liên quan tới vấn đề tìm những mẫu dữ liệu không phù hợp với những hành vi được mong đợi. Những mẫu không phù hợp này thường liên quan đến sự bất thường, sự tách rời, sự ngoại lệ, sự nhầm lẫn, hoặc sự lập dị trong nhiều lĩnh vực ứng dụng khác nhau. Bất thường (Anomaly) và tách rời (Outlier) là hai thuật ngữ được dùng phổ biến trong ngữ cảnh phát hiện bất thường, đôi khi thay thế nhau. Phát hi