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

tả hàm AnomalyScore: 33 Hàm nhận giá trị đầu vào là một thể hiện x, đầu ra sẽ trả về giá trị điểm số bất thường của x trên tập Test. Bước 1: Nếu số cây t<0 hoặc rừng chưa được tạo thì không trả về giá trị. Bước 2: Tính công thức c_n là giá trị của độ cao trung bình trên cây iTree có n phần tử (3.1.4). Bước 3: Gọi hàm trả về độ cao trung bình của x trên iForest. Gán giá trị cho temp=- getAveragePathLength(x)/c_n Bước 4: Trả về giá trị điểm số s(x,n) 3.5.2.2. Hàm tính độ dài đường dẫn của mỗi thể hiện trên tập. AnomalyScore(x) Đầu vào: một thể hiện x Đầu ra: điểm số bất thường s(x,n) Giải thuật: 1. nếu (t<=0) hoặc (!isCreated) // iForest chưa được tạo Return -1; 2. c_n= 2 *( ln(n-1)+ e) – (2 * (n-1)/n) (với e là hằng Euler; e=0.5772156649) 3. temp=- getAveragePathLength(x)/c_n) 4. return s(x,n) = pow(2,temp) PathLength(x,T,e) Đầu vào: - x là một thể hiện trong tập test - T: một cây iTree - e là độ dài đường dẫn hiện tại, e=0 ở lần gọi đầu tiên Đầu ra: Độ dài đường dẫn của x Giải thuật: 34 Mô tả hàm PathLength: Hàm PathLength dùng để tính độ dài đường dẫn của một thể hiện x trên cây T, hàm nhận vào 3 tham số: thể hiện x, cây T, và độ cao hiện tại e của x trên T (ở lần gọi đầu tiên cho e=0). Đầu ra của giải thuật PathLength là nhận lại một giá trị là độ dài đường dẫn của x trên cây T. Bước 1,2,3: Xét xem x có phải là nút ngoài không, nếu đúng thì trả cho kết quả chiều cao x = độ dài hiện tại e + c(T.size), trong đó c(T.size) chính là chiều cao trung bình trên cây có kích thước T.sise. Bước 4: Lấy giá trị thuộc tính cắt splitAtt của nút T gán cho a Bước 5,6,7,8,9: Kiểm tra nếu giá trị của thể hiện x tại thuộc tính a (xa); nếu xa nhỏ hơn giá trị cắt của nút T thì trả về tính độ dài đường dẫn của x trên cây con trái của T, ngược lại thì trả về tính độ dài đường dẫn của x trên cây con phải của T. 3.6. Ví dụ minh họa cho việc xây dựng rừng cô lập Giả sử ta xây dựng rừng cô lập có số cây t=3 và kích thước mẫu Ψ=16, khi đó 3 mẫu (sub-sample) sẽ được lấy ngẫu nhiên (3.3) từ tập gốc có n phần tử ban đầu. Giả sử 3 mẫu được chọn mô tả như hình 3.4, 3.5, 3.6. Ta lần lượt xây dựng cây cô lập cho từng mẫu theo giải thuật 2 (3.5.1.2), kích thước mẫu Ψ=16 nên chiều cao giới hạn của các cây L=ceiling(log16)=4 (3.7) Bảng 3.1, 3.2, 3.3 mô tả các sub-sample có 16 thể hiện, dòng đầu tiên là các chỉ số của các thuộc tính từ 1
9, cột đầu tiên là các chỉ số của các thể hiện từ 1
16 (giống như cách lưu trữ trên mảng 2 chiều). Cột cuối cùng là thuộc tính lớp (chỉ có ý nghĩa dùng để đối chiếu trong quá trình đánh giá), thuộc tính này không tham gia vào quá trình dựng cây. 1. Nếu T là nút ngoài (external node) thì 2. return e + c(T.Size) 3. end if 4. a  T.splitAtt 5. if xa < T.splitValue then 6. return PathLength(x, T.Left, e+1) 7. else {xa >= T.splitValue } 8. return PathLength(x, T.Right, e+1) 9. end if 35 3.6.1. Giai đoạn huấn luyện (xây dựng rừng cô lập) Xây dựng cây cho mẫu thứ nhất (bảng 3.1): Các thể hiện ở các dòng 2, 4, 7, 13, 15, 16 thuộc lớp bất thường (lớp 1). Bảng 3.1: Mẫu sub-sample cho cây thứ nhất – cây T1 (hình 3.4). Tiêu đề cột (từ 1 đến 9) biểu diễn chỉ số cho các thuộc tính của tập dữ liệu. Tiêu đề dòng (từ 1 đến 16) biểu diễn chỉ số cho các thể hiện trong mẫu. Quá trình dựng cây là quá trình đệ qui, lần lượt chạy theo giải thuật 2 ta dựng được cây cô lập ở hình 3.4: cách chọn thuộc tính q và giá trị cắt p hoàn toàn ngẫu nhiên: - Thuộc tính q là giá trị nguyên được chọn ngẫu nhiên trong các giá trị [1,9], (q=generator.nextInt(9)) - Với thuộc tính q được chọn, p là giá trị ngẫu nhiên trong đoạn [min(q),max(q)], lấy theo số thực. (generator.nextDouble()*(max-min) + min). o Lần gọi đầu tiên: iTree(X,e,L) với X={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}, e=0<L Giá trị q, p được lấy ngẫu nhiên: q= 2, p= 4.179, chia tập X thành 2 tập con: XL={1,3,5,6,7,8,9,10,11,12,14,15}, XR={2,4,13,16} Tiếp tục gọi đệ qui xây dựng cây con trái, cây con phải. Thực hiện đến khi nào các cây có |X|<=1 hoặc cây đã đạt đến chiều cao giới hạn L thì giải thuật kết thúc. 2 cây cô lập còn lại ở hình 3.5, 3.6 được xây dựng tương tự như trên. Chỉ số 1 2 3 4 5 6 7 8 9 Lớp 1 2 1 1 1 2 1 1 1 1 0 2 5 6 6 8 6 10 4 10 4 1 3 3 2 1 1 2 2 3 1 1 0 4 10 8 8 2 3 4 8 7 8 1 5 1 1 1 1 1 1 1 1 1 0 6 4 1 1 1 2 1 3 1 1 0 7 7 4 7 4 3 7 7 6 1 1 8 1 1 1 1 1 1 3 1 1 0 9 3 1 1 1 2 1 1 1 1 0 10 2 1 1 1 2 1 2 1 1 0 11 2 1 1 1 1 1 1 1 1 0 12 6 1 3 2 2 1 1 1 1 0 13 8 10 10 7 10 10 7 3 8 1 14 1 1 1 1 2 1 3 1 1 0 15 8 4 4 1 6 10 2 5 2 1 16 4 8 7 10 4 10 7 5 1 1 36 1,2,3,4,5,6,7,8,9,10, 11,12,13,14,15,16 1,3,5,6,7,8,9,10,11, 12,14,15 2,4,13,16 q= 2 p= 4.179 1,3,5,6,8,9,10,11, 12,14,15 7 q= 4 p= 2.0058 exNode(size=1) 15 exNode(size=1) 1,3,5,6,8,9,10,11, 12,14 q= 8 p= 2.0058 12 exNode(size=1) q= 4 p= 2.0058 exNode(size=9) 2 exNode(size=1) 4,13,16 q= 3 p= 6.0514 4 exNode(size=1) 13,16 q= 6 p= 5.0914 16 13 q= 2 p= 8.5128 exNode(size=1) exNode(size=1) Hình 3.4: Cây T1 được xây dựng cho tập mẫu 16 phần tử, chiều cao giới hạn ≤log16 T1 1,3,5,6,8,9,10,11,14 37 Bảng 3.2: Mẫu sub-sample cho cây thứ 2 – cây T2 (hình 3.5): Các phần tử thuộc lớp bất thường trong bảng 3.2 là 1, 10, 11, 14, 15, 16 Bảng 3.3: Mẫu sub-sample cho cây thứ 3 – cây T3 (hình 3.6): Các phần tử thuộc lớp bất thường trong bảng 3.3 là 1, 2, 9, 10, 11, 14 Chỉ số 1 2 3 4 5 6 7 8 9 Lớp 1 5 10 6 1 10 4 4 10 10 1 2 2 1 1 2 3 1 2 1 1 0 3 1 1 1 1 2 1 3 1 1 0 4 3 1 1 2 2 1 1 1 1 0 5 4 1 1 1 2 1 3 1 1 0 6 1 1 1 1 2 1 2 1 1 0 7 2 1 1 1 2 1 3 1 1 0 8 1 1 1 1 2 1 3 1 1 0 9 2 1 1 2 2 1 1 1 1 0 10 9 6 9 2 10 6 2 9 10 1 11 7 5 6 10 5 10 7 9 4 1 12 1 1 1 1 2 5 1 1 1 0 13 8 3 3 1 2 2 3 2 1 0 14 3 4 5 2 6 8 4 1 1 1 15 9 9 10 3 6 10 7 10 6 1 16 10 7 7 4 5 10 5 7 2 1 Chỉ số 1 2 3 4 5 6 7 8 9 Lớp 1 10 10 10 10 5 10 10 10 7 1 2 5 10 10 10 4 10 5 6 3 1 3 5 1 1 1 2 1 3 2 1 0 4 1 1 1 1 2 1 1 1 1 0 5 1 1 1 1 2 1 1 1 1 0 6 1 1 1 1 2 1 1 1 2 0 7 3 1 1 1 3 2 1 1 1 0 8 2 1 1 1 2 1 1 1 1 0 9 5 10 10 3 7 3 8 10 2 1 10 4 8 6 4 3 4 10 6 1 1 11 8 7 4 4 5 3 5 10 1 1 12 3 1 1 1 2 1 1 1 1 0 13 3 1 4 1 2 1 1 1 1 0 14 10 10 7 8 7 1 10 10 3 1 15 4 2 4 3 2 2 2 1 1 0 16 4 1 1 1 2 1 1 1 1 0 38 1,2,3,4,5,6,7,8,9,10, 11,12,13,14,15,16 2,3,4,5,6,7,8,9, 11,12,13,16 1,10,14,15 q=5 p= 5.46 2,3,4,5,6,7,8,9, 12,13 11,16 q= 7 p= 4.8 13 2,3,4,5,6,7 8,9,12 q= 3 p= 1.5 2 q= 5 p= 2.4 exNode(size=8) 10,15 q=1 p= 5.7 14 exNode (size=1) Hình 3.5: Cây T2 được xây dựng cho tập mẫu 16 phần tử [bảng 3.2], chiều cao giới hạn ≤log16 T2 3,4,5,6,7,8,9,12 16 11 q= 9 p= 3.5 1,14 1 q= 3 p= 5.4 q= 8 p= 9.2 10 15 exNode (size=1) exNode (size=1) exNode (size=1) exNode (size=1) exNode (size=1) exNode (size=1) exNode (size=1) 39 1,2,3,4,5,6,7,8,9,10, 11,12,13,14,15,16 3,4,5,6,7,8,11, 12,13,15,16 1,2,9,10,14 q= 2 p= 7.3 3,4,5,6,7,8, 12,13,15,16 11 q= 5 p= 4.47 6 exNode(size=2) 4,5,6 q= 1 p=1.006 3,7,8, 12,13,15,16 exNode(size=1) q= 9 p= 1.023 exNode(size=2) 1,2,10 q= 6 p= 3.7 2 1 q= 3 p=9.012 exNode(size=1) exNode(size=1) Hình 3.6: Cây T3 được xây dựng cho tập mẫu 16 phần tử [bảng 3.3], chiều cao giới hạn ≤log16 T3 4,5 3,7,8,12,16 13,15 q= 4 p= 2.7 exNode(size=5) 14 9 9,14 10 1,2 q= 5 p=3.911 q= 1 p=7.8 exNode (size=1) exNode (size=1) exNode (size=1) exNode (size=1) 40 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. Trong ví dụ này, chọn thể hiện x1 (phần tử thuộc lớp bất thường) và x2 (phần tử thuộc lớp bình thường). Thể hiện x1 có giá trị dữ liệu sau đây: Chỉ số thuộc tính 1 2 3 4 5 6 7 8 9 Lớp 8 6 4 10 5 5 6 4 1 1 Lần 1: Lần gọi đầu tiên e=0, PathLength(x, T, 0) a=T.q = 2; xa =6 > T.p nên gọi PathLength(x,T.Right,1) Lần 2: a=T.q = 3; xa=4< T.p nên gọi PathLength(x, T.Left, 2) Lần 3: Do T là nút ngoài nên return e+c(size)=2+c(1)=2 Kết thúc giải thuật với độ dài đường dẫn của x1 trên cây T1 là h(x1,T1)=2. Với cách tương tự ta tính được h(x1,T2)=3 và h(x1,T3)=2. Khi đó tính được độ dài đường dẫn trung bình của x1 trên rừng cô lập là E(h(x1))=(h(x1,T1)+h(x1,T2)+h(x1,T3))/t = (2+3+2)/3=2.3333 Thể hiện x2 có giá trị dữ liệu sau đây: Chỉ số thuộc tính 1 2 3 4 5 6 7 8 9 Lớp 5 1 1 1 2 1 1 1 1 0 Lần 1: Lần gọi đầu tiên e=0, PathLength(x, T, 0) a=T.q = 2; xa =1 < T.p nên gọi PathLength(x,T.Left,1) Lần 2: a=T.q = 4; xa=1 < T.p nên gọi PathLength(x, T.Left, 2) Lần 3: a=T.q = 8; xa=1 <T.p nên gọi PathLength(x, T.Left, 3) Lần 4: a=T.q=4; xa=1 < T.p nên gọi PathLength(x, T.Left,4) Lần 5: T là nút ngoài với size = 9 Trả về độ dài đường dẫn của x2 trên cây T1 là h(x2,T1)=e+c(size)= 4 + c(9) = 4 + 3.7711=7.7711 Kết thúc giải thuật với độ dài đường dẫn của x2 trên cây T1 là h(x2,T1)=7.7711. Với cách tương tự ta tính được h(x2,T2)=7.56331 và 41 h(x2,T3)=6.77331. Khi đó tính được độ dài đường dẫn trung bình của x2 trên rừng cô lập là E(h(x2))=(h(x2,T1)+h(x2,T2)+h(x2,T3))/3=7.36924 Có được các E(h(x)), ta sẽ tính được điểm số bất thường của các thể hiện x trên tập Test theo hàm AnomalyScore(x). Giả sử tập gốc ban đầu có tổng số phần tử là 699 (n=699). Theo phần 3.1.4 và hàm AnomalyScore (3.5.2.1) ta tính được C(n): C(n)=12.2566  s(x1,n)=0.87638; s(x2,n)=0.65918 Vậy s(x1,n)>s(x2,n), điểm số bất thường của x1 tiến gần về 1. Theo nhận xét ở phần 3.1.4 thì E(h(x1)) có xu hướng tiến về 0 (gần nút gốc). Hay nói cách khác x1 bị cô lập gần nút gốc của cây, x1 có khả năng cao là điểm bất thường. Ngược lại x2 có điểm số lân cận với 0.5, x2 có khả năng cao là điểm bình thường. Nhận xét: Những thể hiện x thuộc lớp bất thường có xu hướng bị cô lập nhanh gần nút gốc của cây. Điều này hầu như đúng (qua thực nghiệm) cho tất cả các thể hiện khác. 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). iTree là một cây nhị phân với mỗi nút có chính xác hai nút con hoặc không con. Giả sử rằng tất cả các thể hiện trong tập dữ liệu đều phân biệt nhau, mỗi thể hiện được cô lập đến nút ngoài, khi đó iTree là cây nhị phân hoàn chỉnh, trong trường hợp này số nút ngoài của cây là n; số nút trong là n-1; tổng số nút trên iTree là 2n-1; vì thế yêu cầu về bộ nhớ thì bị giới hạn theo n và chỉ tăng một cách tuyến tính theo n. Trên thực tế, do tính chất “ít và khác” của các thể hiện bất thường nên chúng dễ bị cô lập gần nút gốc của cây, vì thế trong quá trình xây dựng cây, một trong những điều kiện dừng việc phát triển cây là khi cây đạt đến chiều cao giới hạn (tương đương với thời gian tìm kiếm trung bình trên BST là O(log n)) [30]. iTree có cấu trúc tương tự như cấu trúc của cây BST (quan sát bảng 3.4), ước lượng độ dài đường dẫn trung bình h(x) cho một nút ngoài giống như việc tìm kiếm không thành công trên BST. 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 iTree BST Cây nhị phân đích thực Cây nhị phân đích thực Nút kết thúc ngoài của iTree Tìm kiếm không thành công trên BST Không thể ứng dụng được Tìm kiếm thành công 42 Mượn phân tích của BST về ước lượng độ dài đường dẫn trung bình của tìm kiếm không thành công trên BST để tính giá trị tại nút kết thúc ngoài có kích thước size. Tính c(size) tại nút kết thúc ngoài (nút đã đạt đến chiều cao giới hạn logn), với size là số thể hiện trên nút này. C(size) = 2*(ln(size-1)+e)-(2*((size-1)/size)); với e=0.5772156649 43 CHƯƠNG 4 CÀI ĐẶT MÔ HÌNH RỪNG CÔ LẬP 4.1. Xây dựng rừng cô lập 4.1.1. Cấu trúc cây cô lập 4.1.1.1. Nút tổng quát Một cây có thể được định nghĩa là một tập các nút tạo thành. Trong một cây cô lập, có hai loại nút: nút trong và nút ngoài. Chúng ta có thể tổng quát hóa thành một loại nút chung như sau: Một nút tổng quát được định nghĩa gồm một nút con bên trái và một nút con phải phải. 4.1.1.2. Nút trong Nút trong là nút có hai con có thuộc tính cắt và giá trị cắt. 4.1.1.3. Nút ngoài Nút ngoài là nút không có nút con nên giá trị con bên trái và con bên phải của nó được đặt là rỗng (null). Ngoài ra nút ngoài còn có thuộc tính chỉ ra số thể hiện còn lại tại nút ngoài trong quá trình xây dựng nút. 4.1.2. Cấu trúc rừng cô lập Một rừng cô lập được tạo nên bởi một tập các cây cô lập cùng với các thuộc tính thể hiện đặc trưng của nó. Các thuộc tính bao gồm thông tin về các điểm dữ liệu dùng để xây dựng rừng như tập thể hiện, số thuộc tính (số chiều) của thể hiện, số thể hiện. Ngoài ra còn có 2 thuộc tính quan trọng như số lượng cây trong rừng, public class Node { Node leftChild; Node rightChild; public Node(){ leftChild = null; rightChild = null;} } public class InNode extends Node{ int splitAtt; double splitValue;} public class ExtNode extends Node{ int exSize; public ExtNode() { leftChild=rightChild=null; exSize = 0; } } 44 kích thước mẫu trong mỗi cây trong rừng. 2 thuộc tính này ảnh hưởng rất lớn đến quá trình xây dựng cây. 4.2. Triển khai một số giải thuật trên rừng cô lập 4.2.1. Lấy mẫu ngẫu nhiên Trong quá trình xây dựng cây cô lập, một trong các bước quan trọng là chọn ngẫu nhiên tập mẫu từ tập thể hiện ban đầu, sử dụng mẫu được chọn để xây dựng cây. Nhằm giảm thiểu việc sử dụng bộ nhớ, tăng tốc độ chương trình, các phần tử trong mẫu ngẫu nhiên sẽ được truy vấn bởi chỉ số trong mảng các thể hiện ban đầu. Như vậy, chỉ có một bản duy nhất thể hiện đầu vào và quá trình lấy mẫu sẽ trả về danh sách chỉ mục vị trí của các phần tử được chọn làm mẫu trong mảng dữ liệu ban đầu. public class IForest { double[][] inputData; // tập dữ liệu các phần tử int numAtt; // số thuộc tính trong dữ liệu int numInstance; // số lượng phần tử trong tập dữ liệu int numTree; // số lượng cây int sampleSize; // kích cỡ mẫu trên mỗi cây Node[] iTree; // tập các cây trong rừng } public int[] getSample() { int[] temp = new int[sampleSize]; //mảng chứa chỉ mục của phần tử được chọn Random generator = new Random(); int j=0; int count =0; while (count<sampleSize) { j= generator.nextInt(numInstance); if (count==0) // phần tử đầu tiên { temp[count]=j; count++; } else { if (Arrays.binarySearch(temp, 0, count, j)<0) //phần tử chưa được chọn { temp[count]=j; count++; Arrays.sort(temp,0,count); } } } return temp; //trả về danh sách chỉ mục của các phần tử được chọn. 45 4.2.2. Chọn giá trị cắt ngẫu nhiên Trong quá trình xây dựng cây, sau khi chọn một thuộc tính cắt, việc chọn giá trị cắt của thuộc tính này là ngẫu nhiên trong đoạn giá trị từ giá trị lớn nhất đến nhỏ nhất của nó. 4.2.3. Xây dựng cây cô lập Cây cô lập là một tập các nút trong và nút ngoài thõa mãn điều kiện của rừng cô lập. Xây dựng cây cô lập được tiến hành theo phương thức đệ qui trên từng nút. Để xây dựng một nút trên cây cô lập, chúng ta phải có các thông số sau: - Danh sách các phần tử mẫu dạng chỉ mục (xIndex): Danh sách này chứa chỉ mục các phần tử được chọn, được dùng để tham chiếu đến mảng thể hiện đầu vào. - Số phần tử được chọn (noInstance) - Chiều cao hiện tại của nút (currentHeight) - Chiều cao tối đa cho phép (heightLimit) public double getSplitValue(int[] xIndex, int attIndex, int noInstance) { Random generator = new Random(); double max,min; max=min= inputData[xIndex[0]][attIndex]; //Tìm giá trị lớn nhất và nhỏ nhất của thuộc tính cắt for (int i=1;i<noInstance;i++) { if (inputData[xIndex[i]][attIndex]<min) min=inputData[xIndex[i]][attIndex]; if (inputData[xIndex[i]][attIndex]>max) max=inputData[xIndex[i]][attIndex]; } //Trả về giá trị ngẫu nhiên. return (generator.nextDouble()*(max-min) + min); } public Node createITree(int[] xIndex, int noInstance, int currentHeight, int heightLimit) { if ((currentHeight>=heightLimit) || (noInstance<=1)) // Nút ngoài { return (new ExtNode(noInstance)); } Else //Nút trong { InNode inNode = new InNode(); //Chọn ngẫu nhiên một thuộc tính chia tách Random generator = new Random(); inNode.splitAtt = generator.nextInt(numAtt); //Chọn ngẫu nhiên giá trị chia tách inNode.splitValue= getSplitValue(xIndex,inNode.splitAtt,noInstance); 46 4.2.4. Xác định độ dài đường dẫn của một thể hiện Thông số được dùng tính toán điểm số để xác định mức độ bất thường của một thể hiện là độ dài đường đi của thể hiện, khi chúng ta cho thể hiện duyệt qua từ nút gốc đến nút lá theo điều kiện kiểm tra và giá trị kiểm tra tại các nút trong một cây cô lập. Việc xác định độ dài đường dẫn của một thể hiện là quá trình đệ qui từ nút gốc đến khi gặp nút ngoài. public double getPathLength(double[] x, Node tree, double currentLength) { if (tree instanceof ExtNode) { //Nút ngoài int xSize=((ExtNode)tree).exSize; double temp=currentLength; if (xSize>1) temp= currentLength+2*(Math.log(xSize-1)+0.5772156649) -(2*(double)((xSize-1)/xSize)); return temp; } else { //Nút trong int splitAtt=((InNode)tree).splitAtt; double splitValue = ((InNode)tree).splitValue; if (x[splitAtt]<splitValue) { //Thuộc con bên trái return getPathLength(x, tree.leftChild, currentLength+1); } else { //Thuộc con bên phải return getPathLength(x, tree.rightChild, currentLength+1);}}} int[] rxIndex = new int[noInstance]; int[] lxIndex = new int[noInstance]; int rcount=0, lcount=0; for (int i=0;i<noInstance;i++) { //Con bên trái if (inputData[xIndex[i]][inNode.splitAtt]<inNode.splitValue) { lxIndex[lcount]=xIndex[i]; lcount++; } //Con bên phải else if (inputData[xIndex[i]][inNode.splitAtt]>=inNode.splitValue) { rxIndex[rcount]=xIndex[i]; rcount++; } } Arrays.sort(lxIndex, 0, lcount); Arrays.sort(rxIndex, 0, rcount); //Gọi đệ qui để tiến hành xây dựng nút cấp thấp hơn. inNode.leftChild=createITree(lxIndex,lcount,currentHeight+1, heightLimit); inNode.rightChild=createITree(rxIndex,rcount,currentHeight+1, heightLimit); return inNode; } } 47 Do rừng cô lập gồm nhiều cây, việc tính độ dài đường dẫn của một thể hiện sẽ được thực hiện trên các cả các cây và xác định giá trị trung bình. 4.2.5. Tính điểm số bất thường Sau khi rừng cô lập được xây dựng, nó sẽ được sử dụng để tính điểm số bất thường của các thể hiện. 4.2.6. Sử dụng mô hình rừng cô lập để kiểm tra dữ liệu 4.2.6.1. Dữ liệu đầu vào Dữ liệu được sử dụng phổ biến trong khai mỏ dữ liệu thường được lưu trữ dưới định dạng CSV (Comma Separated Values). Trong định dạng này, mỗi một hàng là một thể hiện. Trong mỗi hàng, giá trị của các thuộc tính được phân cách bởi dấu phẩy. Dữ liệu đầu vào được đưa vào mô hình bởi hàm sau đây: public double getAveragePathLength(double[] x) { double length=0; if ((numTree<=0) || (!isCreated)) //Cây chưa được tạo return -1; for (int i=0;i<numTree;i++) //Duyệt qua tất cả các cây để xác định độ dài { length=length+getPathLength(x,iTree[i],0); } return (double)(length/numTree); } public double getScore(double[] x) { if ((numTree<=0) || (!isCreated)) // Cây chưa được tạo return -1; // Độ cao trung bình trên cây iTree có n phần tử double c_n=(double)2*(Math.log(numInstance-1)+0.5772156649) -(2*(double)((numInstance-1)/numInstance)); //Độ cao trung bình trên của thể hiện x double temp = -(double)(getAveragePathLength(x)/c_n); return Math.pow(2.0, temp); } public boolean importDataFromFile(String fileName) { //Chứa dữ liệu tạm thời đọc từ tập tin csv ArrayList myArr = new ArrayList(); try { BufferedReader in = new BufferedReader(new InputStreamReader(new FileInputStream(fileName), "UTF-8")); while (true) { //Đọc toàn bộ nội dung tập tin String line = in.readLine(); if ((line != null) && (!line.isEmpty())) { myArr.add(line); 48 4.2.6.2. Xây dựng rừng cô lập từ dữ liệu đầu vào Khi dữ liệu đầu vào đã được nhập, việc xây dựng rừng cô lập sẽ được tiến hành dựa trên thông số về số cây trong rừng và số lượng thể hiện trên mỗi cây. Sau khi rừng được xây dựng, giá trị điểm số bất thường cũng được tính và hiển thị theo thứ tự từ cao đến thấp. } else { in.close(); break; } } } catch (Exception e) { e.printStackTrace(System.out); } if (myArr.size()==0) //Không có dữ liệu return false; else { //Có dữ liệu //Xác định số thể hiện numInstance=myArr.size(); //Chia tách các thuộc tính numAtt= myArr.get(0).split(",").length-1; inputData = new double[numInstance][numAtt+1]; String[] strList; for (int i=0;i<numInstance;i++) { //Lưu trữ từng thể hiện vào mảng strList = myArr.get(i).split(","); for (int j=0;j<=numAtt;j++) { inputData[i][j]=Double.valueOf(strList[j].trim()); } } return true; } } private void jBuildButtonActionPerformed(java.awt.event.ActionEvent evt) { //Số lượng cây int noTree = Integer.parseInt(jNoTreeTextField.getText().trim()); //Số lượng thể hiện trên mỗi cây int sampleSize = Integer.parseInt(jSampleSizeTextField.getText().trim()); //Thiết lập thông số trên rừng iForest.setNumTree(noTree); iForest.setSampleSize(sampleSize); //Xây dựng rừng iForest.createIForest(); //Xác định điểm số bất thường cho mỗi cây int numInstance = iForest.getNumInstance(); int numAtt = iForest.getNumAtt(); currentData = iForest.getInputData(); //Lưu trữ điểm số bất thường cho mỗi thể hiện double[] score = new double[numInstance]; 49 4.2.6.3. Kiểm thử dữ liệu Sau khi rừng cô lập được xây dựng, việc xác định điểm số bất thường của tập được dùng xây dựng rừng đã được thực hiện và hiển thị. Tuy nhiên, trong một số trường hợp chúng ta muốn kiểm thử dữ liệu khác với dữ liệu được sử dụng xây dựng rừng. Điều này có thể thực hiện bằng hàm sau đây. 4.3. Giới thiệu giao diện của mô hình rừng cô lập: - Mô hình cho phép người dùng nhận vào một tập dữ liệu có định dạng .csv [4.2.6.1] score = new Score[numInstance]; for (int i=0;i<numInstance;i++) { score[i] = new Score(); score[i].index=i; score[i].label = currentData[i][numAtt]; score[i].score= iForest.getScore(currentData[i]); } //Sắp xếp lại điểm số để hiển thị theo thứ tự từ cao đến thấp Arrays.sort(score, new ScoreComp()); display(currentData,score,numInstance,numAtt, true); jTestButton.setEnabled(true); jFilterButton.setEnabled(true); } private void jTestButtonActionPerformed(java.awt.event.ActionEvent evt) { //Dữ liệu kiểm tra được đưa vào từ tập tin String filename = openFile(); if (filename!=null) { //Đọc dữ liệu từ tập tin csv currentData =iForest.readDataFromFile(filename); if (currentData!=null) {//Có dữ liệu //Xác định số lượng thể hiện int numInstance = currentData.length; //Tính điểm số bất thường cho các thể hiện score = new Score[numInstance]; for (int i=0;i<numInstance;i++) { score[i] = new Score(); score[i].index=i; score[i].label = currentData[i][iForest.getNumAtt()]; score[i].score= iForest.getScore(currentData[i]); } //Sắp xếp theo thứ tự Arrays.sort(score, new ScoreComp()); display(currentData, score, numInstance, iForest.getNumAtt(), true); } } 50 - Nhập vào số cây (No of Trees), kích thước mẫu (Sample size), kế đó chọn Build để xây dựng rừng cô lập. Công việc này được lập lại với số lần không giới hạn. - Kết quả sau khi dựng rừng cô lập là điểm số bất thường của tất cả các thể hiện trên tập Test (nếu không chọn tập Test khác, thì mặc nhiên tập Test và tập Training là một). Điểm số mặc định được sắp xếp theo thứ tự giảm dần. - Để đánh giá hiệu quả của mô hình trên tập dữ liệu đưa vào, người dùng có thể đưa vào ngưỡng chọn bất thường, khi đó sẽ thu được các kết quả là các độ đo TPR và FPR. Công việc này được lập lại với số lần không giới hạn. Hình 4.1 minh hoạ giao diện mô hình rừng cô lập. Hình 4.1. Giao diện mô hình rừng cô lập 51 CHƯƠNG 5: NỘI DUNG VÀ KẾT QUẢ THỰC NGHIỆM 5.1. Chọn các tập dữ liệu thực nghiệm iForest là một trong những kỹ thuật phát hiện bất thường dựa trên mô hình unsupervised [8], các kỹ thuật theo loại này đòi hỏi các tập dữ liệu được chọn cho thực nghiệm phải thoả mãn cả 2 giả định: số lượng các thể hiện bất thường phải ít hơn rất nhiều so với các thể hiện bình thường trong tập (giả định 1) và giá trị dữ liệu của các thể hiện bất thường phải thực sự khác biệt đối với các thể hiện bình thường còn lại tr