Luận văn Ứng dụng thuật toán fuzzy random forest trong phát hiện xâm nhập mạng không dây

g sự [42] tiếp đến Jose M. Cadenas và cộng sự đã có nhiều cải tiến cho thuật toán fuzzy random forest ban đầu [43] bằng cách mở rộng xử lý thông tin trong bộ FRF để kết hợp các dữ liệu có chứa các thuộc tính được đo bằng các giá trị khoảng cách và các thuộc tính được đo bằng các giá trị mờ có thể khác với các giá trị mờ tạo thành phân chia mờ của thuộc tính và do đó mức độ tương đồng của các giá trị mờ này cho mỗi phần tử của phân vùng mờ của thuộc tính có thể nhỏ hơn 1. Matteis và cộng sự [16] đề xuất phương pháp tạo phân vùng mờ đồng thời với việc tạo cây quyết định mờ, khi tạo nút quyết định thông qua ba bộ mờ tam giác. Cốt lõi của tập mờ trung gian trùng với các cực trị phải và trái của các giá đỡ của tập mờ trái và phải. Do đó, phân vùng được xác định hoàn toàn bởi một điểm duy nhất: cốt lõi của bộ fuzzy trung gian. Đối với mỗi thuộc tính trong tập các thuộc tính được chọn ngẫu nhiên cho nút, chúng ta đánh giá các vị trí khác nhau của lõi và chọn vị trí cung cấp lợi ích thông tin cao nhất. Thu được thông tin được tính bằng cách sử dụng entropy mờ. Do đó, nút cha mẹ được chia thành ba nút con (một cho mỗi tập mờ), chứa các đối tượng của nút cha với các giá trị thành viên cao hơn 0.5 đến tập mờ tương ứng. Cùng một biến liên tục có thể được xem xét trong các nút quyết định khác nhau từ gốc đến lá: cho mỗi nút quyết định chúng ta áp dụng cùng một phân vùng mờ. Vì mỗi nút này tập trung vào một khoảng thời gian cụ thể của vũ trụ của biến liên tục, điều này tương ứng với việc thực hiện phóng to ở khoảng thời gian cụ thể. Việc học của cây quyết định mờ sẽ chấm dứt khi không có nút nào có thể được tách ra thêm dựa trên các điều kiện xác định. Meenakshi và Venkatachalam [44] đã đề xuất phương pháp sử dụng fuzzy entropy để tìm kiếm một cách tốt nhất cây quyết định đối với những bài toán về dữ liệu không chắc chắn. Vitaly và Penka [45] đã sử dụng một kỹ thuật tính toán tích lũy thông tin và tích lũy entropy cho tập dữ liệu mờ làm giảm chi phí tạo cây quyết định tối thiểu dựa trên các tiêu chí tối ưu mới thu được một cái quyết định có trật tự. 2.2 Thuật toán Decision Tree Trong lĩnh vực máy học cây quyết định là một kiểu mô hình dự báo, nghĩa là một ánh xạ từ các quan sát về một sự vật/hiện tượng tới các kết luận về giá trị mục tiêu của sự vật/hiện tượng. Mỗi một nút trong tương ứng với một biến; đường nối giữa nó với nút con của nó thể hiện một giá trị cụ thể cho biến đó. Mỗi nút lá đại diện cho giá trị dự đoán của biến mục tiêu, cho trước các giá trị của các biến được biểu diễn bởi đường đi từ nút gốc tới nút lá đó. Kỹ thuật máy học dùng trong cây quyết định được gọi là học bằng cây quyết định, hay chỉ gọi với cái tên ngắn gọn là cây quyết định [11]. Học bằng cây quyết định cũng là một phương pháp thông dụng trong khai phá dữ liệu. Khi đó, cây quyết định mô tả một cấu trúc cây, trong đó, các lá đại diện cho các phân loại còn cành đại diện cho các kết hợp của các thuộc tính dẫn tới phân loại đó. Một cây quyết định có thể được học bằng cách chia tập hợp nguồn thành các tập con dựa theo một kiểm tra giá trị thuộc tính. Quá trình này được lặp lại một cách đệ quy cho mỗi tập con dẫn xuất. Quá trình đệ quy hoàn thành khi không thể tiếp tục thực hiện việc chia tách được nữa, hay khi một phân loại đơn có thể áp dụng cho từng phần tử của tập con dẫn xuất. Một bộ phân loại random forest sử dụng một số cây quyết định để có thể cải thiện tỉ lệ phân loại [11]. Giải thuật ID3 (gọi tắt là ID3) Được phát triển đồng thời bởi Quinlan trong AI và Breiman, Friedman, Olsen và Stone trong thống kê. ID3 là một giải thuật học đơn giản nhưng tỏ ra thành công trong nhiều lĩnh vực. ID3 là một giải thuật hay vì cách biểu diễn tri thức học được của nó, tiếp cận của nó trong việc quản lý tính phức tạp, heuristic của nó dùng cho việc chọn lựa các khái niệm ứng viên, và tiềm năng của nó đối với việc xử lý dữ liệu nhiễu [12]. ID3 biểu diễn các khái niệm ở dạng các cây quyết định. Biểu diễn này cho phép chúng ta xác định phân loại của một đối tượng bằng cách kiểm tra các giá trị của nó trên một số thuộc tính nào đó. Như vậy, nhiệm vụ của giải thuật ID3 là học cây quyết định từ một tập các ví dụ rèn luyện hay còn gọi là dữ liệu rèn luyện. Input: Một tập hợp các ví dụ. Mỗi ví dụ bao gồm các thuộc tính mô tả một tình huống, hay một đối tượng nào đó, và một giá trị phân loại của nó. Output: Cây quyết định có khả năng phân loại đúng đắn các ví dụ trong tập dữ liệu rèn luyện, và hy vọng là phân loại đúng cho cả các ví dụ chưa gặp trong tương lai. Giải thuật ID3 xây dựng cây quyết định được trình bày như sau [12]: Lặp: 1. Chọn A <= thuộc tính quyết định “tốt nhất” cho nút kế tiếp 2. Gán A là thuộc tính quyết định cho nút 3. Với mỗi giá trị của A, tạo nhánh con mới của nút 4. Phân loại các mẫu huấn luyện cho các nút lá 5. Nếu các mẫu huấn luyện được phân loại hoàn toàn thì NGƯNG, Ngược lại, lặp với các nút lá mới. Thuộc tính tốt nhất ở đây là thuộc tính có entropy trung bình thấp nhất theo thuộc tính kết quả với Entropy được tính như sau: Gọi S là tập các mẫu huấn luyện Gọi p là tỷ lệ các mẫu dương trong S Ta có H ≡ – p.log2p – (1 – p).log2(1 – p) Ví dụ: Training data Bảng 2.1: Dữ liệu phân lớp sử dụng cây quyết định # Outlook Temperature Humidity Wind Decision 1 Sunny Hot High Weak No 2 Sunny Hot High Strong No 3 Overcast Hot High Weak Yes 4 Rain Mild High Weak Yes 5 Rain Cool Normal Weak Yes 6 Rain Cool Normal Strong No 7 Overcast Cool Normal Strong Yes 8 Sunny Mild High Weak No 9 Sunny Cool Normal Weak Yes Test data Bảng 2.2: Dữ liệu kiểm thử thuật toán cây quyết định 1 Rain Mild Normal Weak Yes 2 Sunny Mild Normal Strong Yes 3 Overcast Mild High Strong Yes 4 Overcast Hot Normal Weak Yes 5 Rain Mild High Strong No Entropy: 2 1 ( ) log ( ) n i i i E p p p = = − Information Gain: ( , ) ( ) ( | )Gain X T E X E X T= − E(Decision) = -(p(no).log2(p(no) + p(yes).log2(p(yes))) = - (4/9.log2(4/9)+5/9.log2(5/9)) = 0.991 E(Decision|Outlook) = p(Sunny).E(Sunny|Decision) + p(Overcast).E(Overcast|Decision) + p(Rain).E(Rain|Decision) = 4/9.-(3/4. log2(3/4) + 1/4. log2(1/4)) + 2/9.0 + 3/9.-(1/3. log2(1/3)+2/3. log2(2/3)) = 2/3 Gain(Decision|Outlook) = E(Decision) – E(Decision| Outlook) = 0.991-0.667 = 0.324 E(Decision|Temperature) = p(Hot).E(Hot|Decision) + p(Mild).E(Mild|Decision) + p(Cool).E(Cool|Decision) = 3/9.-(2/3. log2(2/3) + 1/3. log2(1/3)) + 2/9.-(1/2. log2(1/2) + 1/2. log2(1/2)) + 4/9.-(1/4. log2(1/4)+3/4. log2(3/4)) = 8/9 Gain(Decision|Temperature) = E(Decision) – E(Decision| Temperature) = 0.991-8/9=0.1 E(Decision|Humidity) = p(High).E(High|Decision) + p(Normal).E(Normal|Decision) = 5/9.- (3/5. log2(3/5) + 2/5. log2(2/5)) + 4/9.-(1/4. log2(1/4) + 3/4. log2(3/4)) = 0.8999 Gain(Decision|Humidity) = E(Decision) – E(Decision| Humidity) = 0.991-0.8999=0.09 E(Decision|Wind) = p(Weak).E(Weak|Decision) + p(Strong).E(Strong|Decision) = 6/9.-(2/6. log2(2/6) + 4/6. log2(4/6)) + 3/9.-(2/3. log2(2/3) + 1/3. log2(1/3)) = 0.92 Gain(Decision|Wind) = E(Decision) – E(Decision|Wind) = 0.991-0.92=0.071 Hình 2.1: Hình ảnh cây sau vòng lặp đầu tiên của thuật toán DT Xét nhánh Overcast : Tất cả record trả về Yes = > Dừng E(Sunny) = -(3/4. log2(3/4) + 1/4. log2(1/4)) = 0.81 E(Rain) = -1/3.log2(1/3)-2/3.log2(2/3) = 0.918 Gain(Sunny|Temperature) = 0.81 - 2/4.0 - 1/4.0 + 1/4.0 = 0.81 Gain(Sunny|Humidity) = 0.81 – 3/4.0 – 1/4.0 = 0.81 Gain(Sunny|Wind) = 0.81 – 3/4.(-2/3.log2(2/3)-1/3.log2(1/3)) – 1/4.0 = 0.12 Bảng 2.3: Tất cả thuộc tính Sunny của Outlook # Outlook Temperature Humidity Wind Decision 1 Sunny Hot High Weak No 2 Sunny Hot High Strong No 8 Sunny Mild High Weak No 9 Sunny Cool Normal Weak Yes Gain(Rain|Temperature) = 0.918 - 1/3.0 – 2/3.(-1/2.log2(1/2)-1/2.log2(1/2)) = 0.25 Gain(Rain|Hunidity) = 0.918 - 1/3.0 – 2/3.(-1/2.log2(1/2)-1/2.log2(1/2)) = 0.25 Gain (Rain|Wind) = 0.918 – 2/3.0 – 1/3.0 = 0.918 Bảng 2.4: Tất cả thuộc tính Rain của Outlook # Outlook Temperature Humidity Wind Decision 4 Rain Mild High Weak Yes 5 Rain Cool Normal Weak Yes 6 Rain Cool Normal Strong No Hình 2.2: Cây phân lớp sau vòng lặp thứ 2 của thuật toán DT Xét nhánh High: All record return No => Stop Xét nhánh Normal: All record return Yes = > Stop Xét nhánh Weak: All record return Yes => Stop Xét nhánh Strong: All record return No => Stop Hình 2.3: Cây phân lớp cuối cùng của thuật toán DT Test result Bảng 2.5: Bảng đánh giá và kiểm tra kết quả của thuật toán DT # Outlook Temperature Humidity Wind Decision Tree result 1 Rain Mild Normal Weak Yes Yes 2 Sunny Mild Normal Strong Yes Yes 3 Overcast Mild High Strong Yes Yes 4 Overcast Hot Normal Weak Yes Yes 5 Rain Mild High Strong No No 2.3 Thuật toán Fuzzy Decision Tree Fuzzy Decision Tree là mở rộng của cây quyết định áp dụng lý thuyết mờ trong việc phân lớp [34] [56]. Hình 2.4: Ví dụ về cây quyết định với phân lớp mờ và phân lớp rõ Hình trên cho thấy sự khác biệt của cây quyết định thông thường và cây quyết định mờ. Với cây quyết định thông thường đường phân tách sắc nét (a). Với hình (b) sử dụng phân giải mềm [56]. Tương tự như cây quyết định thông thường, ta thấy ở cả 2 cây quyết định từ điểm gốc đến lá đều được thiết lập theo một quy tắc phân loại. Tuy nhiên với cây quyết định thông thường sử dụng rời rạc hóa do đó đừng phân loại sắc nét tập không gian phân lớp chồng chéo như hình (a). Đối với cây quyết định mờ kết quá trong phạm vi trong khoảng [0,1] để lấy làm mức độ khả năng phù hợp của mỗi đối tượng [56]. Ví dụ với 2 cây quyết định trên ta có đối tượng (x1=81, x2=25). Với cây quyết định thông thường kết quá là c3. Tuy nhiên nếu điểm lấy dữ liệu di chuyển nhỏ tới một điểm mới do nhiễu ví dụ (x1 = 79, x2 = 25) thì cây quyết định cổ điển sẽ cho kết quả sai: lớp c2. Ngược lại, cây quyết định mờ cho kết quả về các khả năng mà đối tượng thuộc về các lớp c1, c2, c3 tương ứng π1=0, π2=0.52, π3=0.48. Theo kết quả này người dùng có thể đưa ra quyết định hoặc tiến hành thử nghiệm và điều tra thêm. Kết quả phân loại sai có thể bị giảm [56]. Mỗi nhánh của cây quyết định mờ, từ gốc tới lá, tạo thành một quy tắc quyết định, có thể được biểu diễn theo định dạng “nếu 1x là 1A và .... ix là iA .... và mx là mA sau đó là lớp là cj”, trong cái ' 1x là 1A ' .... ' ix là iA ' .... và ' mx là mA ' là các quyết định mờ ở các nút và các nhánh liên kết, và cj là lớp trong lá. Một ví dụ về quy tắc thu được trong hình 1 (b) là “nếu x2là B2 và x1 là A1 thì lớp là c2” [56]. Để phân loại cho một đối tượng không xác định được lấy từ các mức độ phù hợp của đối tượng đến từng nút từ gốc đến lá. Trong ví dụ trên, khả năng của một đối tượng thuộc lớp 2c được tính bằng: )](),([ 11222 xAxB= , ⊗ là phép nhân mờ trực tiếp (mức tối thiểu hoặc trọng số trung bình được sử dụng) , )( 22 xB và )( 11 xA là độ phụ thuộc 2x đến 2B và 1x đến 1A tương ứng. Từ đó tính được độ phụ thuộc của một đối tượng đến một lớp bằng kii ~1}{ = . Nếu nhiều hơn một lá có liên thuộc với ci thì giá trị πI=⊕(πj) được dùng làm khả năng tương ứng với ⊕ là phép tổng mờ trực tiếp. Cuối cùng một giá trị lớn nhất ví dụ K với KiK   thì lớp Kc sẽ được gán cho đối tượng, nếu không cây quyết định dự đoán phân phối trên tất cả các lớp [56]. Với tập thông thường thì 1 tập Ac được định nghĩa → aaAc };1,0{:)( Với tập mờ thì có A là độ phụ thuộc với → aaA ];1,0[:)( A(a) là khả năng A có giá trị a∈  Hình 2.5: Lớp rõ và lớp mờ Entropy mờ của một tập S được xác định bởi )S,(log)S,()S( 1 j k j jF cpcpE  == với   += ji ca iij aAaAcp ))()(()S,( 21 là tỷ lệ mờ của S. [56] )S()S()S;,( 2S S 1S S 11 F F F F F F F E N N E N N TAE += (2.1) )S,(log)S,()S( 11 11 j k j jF cpcpE  =−= (2.2) )S,(log)S,()S( 21 22 j k j jF cpcpE  =−= (2.3) 2,1,)S,( SS == kNNcp kjk F c Fkj (2.4) Với:  = += || 1 21 S ))()((Si iiF aAaAN (2.5)  == || 1 1 S )(1 Si iF aAN (2.6)  == || 1 2 S )(2 Si iF aAN (2.7)  = ji jk ca ik c F aAN )( S (2.8) Tướng ứng với cây quyết định thông thường có information gain )S;,()S( TAEE FF − được sử dụng làm tiêu chí đánh giá tốt nhất cho từng thuộc tính tương ứng. Ví dụ áp dụng vào bài toán chuẩn đoán lỗi máy. Dữ liệu gồm 5 lớp: (1) normal condition, (2) tap wear, (3) hole undersize, (4) hole oversize, and (5) misalignment 8 thuộc tính: (1) the peak torque (x1); (2) the mean torque (x2); (3) the variance of the torque (x3); (4) the mean of torque in retraction stroke (x4); (5) the mean of thrust force (x5); (6) the covariance of torque and thrust force (x6); (7) the correlation of torque and thrust force (x7) and (8) the correlation of torque and thrust force in retraction stroke (x8) [56]. Hình 2.6: Đồ thị biểu diễn các miền giá trị Ví dụ kết quả cho một thuộc tính x3 như sau Phân lớp cứng với decision tree. Decision tree với phân lớp mềm 2.4 Thuật toán Random Forest Tiếp cận Random Forest (rừng ngẫu nhiên) do (Breiman, 2001) đưa ra là một trong những phương pháp tập hợp mô hình thành công nhất. Giải thuật random forest tạo ra một tập hợp các cây quyết định (Breiman et al., 1984), (Quinlan, 1993) không cắt nhánh, mỗi cây được xây dựng trên tập mẫu bootstrap (lấy mẫu có hoàn lại từ tập học), tại mỗi nút phân hoạch tốt nhất được thực hiện từ việc chọn ngẫu nhiên một tập con các thuộc tính. Lỗi tổng quát của rừng phụ thuộc vào độ chính xác của từng cây thành viên trong rừng và sự phụ thuộc lẫn nhau giữa các cây thành viên. Giải thuật random forest xây dựng cây không cắt nhánh nhằm giữ cho thành phần lỗi bias thấp (thành phần lỗi bias là thành phần lỗi của giải thuật học, nó độc lập với tập dữ liệu học) và dùng tính ngẫu nhiên để điều khiển tính tương quan thấp giữa các cây trong rừng. Tiếp cận random forest cho độ chính xác cao khi so sánh với các thuật toán học có giám sát hiện nay. Như trình bày trong (Breiman, 2001), random forest học nhanh, chịu đựng nhiễu tốt và không bị tình trạng học vẹt. Giải thuật random forest sinh ra mô hình có độ chính xác cao đáp ứng được yêu cầu thực tiễn cho vấn đề phân loại, hồi quy [3]. x3=<1.03 x3=<0.92 4 x3 >0.92 x7=<0.71 5 x7 >0.71 1 x3>1.03 x3=<1.25 3 x3 >0.92 2 x3= x7= x3= 4 x3= 5 x3= 1 x3= x3= 3 x3= 2 Giải thuật xây dựng random forest • Từ tập dữ liệu học LS có m phần tử và n biến (thuộc tính), xây dựng T cây quyết định một cách độc lập nhau • Mô hình cây quyết định thứ t được xây dựng trên tập mẫu Bootstrap thứ t (lấy mẫu m phần tử có hoàn lại từ tập học LS) • Tại nút trong, chọn ngẫu nhiên n’ biến (n’<<n) và tính toán phân hoạch tốt nhất dựa trên n’ biến này • Cây được xây dựng đến độ sâu tối đa không cắt nhánh Kết thúc quá trình xây dựng T mô hình cơ sở, dùng chiến lược bình chọn số đông để phân lớp một phần tử mới đến X Hình 2.7: Mô hình thuật toán rừng ngẫu nhiên [3] Ví dụ: Xây dựng cây thứ 1: Chọn cấy thứ nhất là cây ví dụ trên mục 2. Thuật toán cây quyết định => Hình 22: Cây phân lớp cuối cùng của thuật toán DT Xây dựng cây thứ 2: Bảng 2.6: Tập dữ liệu phân lớp cho thuật toán RF # Outlook Temperature Humidity Wind Decision 1 Sunny Hot High Weak No 2 Sunny Hot High Strong No 3 Overcast Hot High Weak Yes 4 Rain Mild High Weak Yes 5 Rain Cool Normal Weak Yes 6 Rain Cool Normal Strong No 7 Overcast Cool Normal Strong Yes 8 Sunny Mild High Weak No 9 Sunny Cool Normal Weak Yes 10 Rain Mild Normal Weak Yes 11 Sunny Mild Normal Strong Yes 12 Overcast Mild High Strong Yes 13 Overcast Hot Normal Weak Yes 14 Rain Mild High Strong No Chọn ngẫu nhiên bản ghi làm tập training. Training data cây 2: Bảng 2.7: Dữ liệu được chọn ngẫu nhiên từ tập dữ liệu ban đầu cho cây 2 # Outlook Temperature Humidity Wind Decision 1 Sunny Hot High Weak No 4 Rain Mild High Weak Yes 5 Rain Cool Normal Weak Yes 6 Rain Cool Normal Strong No 8 Sunny Mild High Weak No 11 Sunny Mild Normal Strong Yes 12 Overcast Mild High Strong Yes 13 Overcast Hot Normal Weak Yes 13 Overcast Hot Normal Weak Yes Test data Bảng 2.8: Dữ liệu để kiểm tra độ chính xác thuật toán RF # Outlook Temperature Humidity Wind Decision 2 Sunny Hot High Strong No 3 Overcast Hot High Weak Yes 7 Overcast Cool Normal Strong Yes 9 Sunny Cool Normal Weak Yes 10 Rain Mild Normal Weak Yes 14 Rain Mild High Strong No E(Decision) = -(p(no).log2(p(no) + p(yes).log2(p(yes))) = - (3/9.log2(3/9)+6/9.log2(6/9)) = 0.918 E(Decision|Outlook) = p(Sunny).E(Sunny|Decision) + p(Overcast).E(Overcast|Decision) + p(Rain).E(Rain|Decision) = 3/9.-(2/3. log2(2/3) + 1/3. log2(1/3)) + 3/9.0 + 3/9.-(1/3. log2(1/3)+2/3. log2(2/3)) = 0.612 Gain(Decision|Outlook) = E(Decision) – E(Decision| Outlook) = 0.918-0.612 = 0.306 E(Decision|Temperature) = p(Hot).E(Hot|Decision) + p(Mild).E(Mild|Decision) + p(Cool).E(Cool|Decision) = 3/9.-(1/3. log2(1/3) + 2/3. log2(2/3)) + 2/9.-(1/2. log2(1/2) + 1/2. log2(1/2)) + 4/9.-(1/4. log2(1/4)+3/4. log2(3/4)) = 8/9 Gain(Decision|Temperature) = E(Decision) – E(Decision| Temperature) = 0.918-8/9=0.03 E(Decision|Humidity) = p(High).E(High|Decision) + p(Normal).E(Normal|Decision) = 5/9.- (1/5. log2(1/5) + 4/5. log2(4/5)) + 4/9.-(2/4. log2(2/4) + 2/4. log2(2/4)) = 0.8455 Gain(Decision|Humidity) = E(Decision) – E(Decision| Humidity) = 0.918-0.8455=0.0725 E(Decision|Wind) = p(Weak).E(Weak|Decision) + p(Strong).E(Strong|Decision) = 6/9.-(2/6. log2(2/6) + 4/6. log2(4/6)) + 3/9.-(1/3. log2(1/3) + 2/3. log2(2/3)) = 0.918 Gain(Decision|Wind) = E(Decision) – E(Decision|Wind) = 0.918-0.918=0 Hình 2.8: Cây RF 2 sau vòng lặp thứ nhất Xét nhánh Overcast: Tất cả record trả về Yes = > Dừng E(Sunny) = -(2/3. log2(2/3) + 1/3. log2(1/3)) = 0.918 Gain(Sunny|Temperature) = 0.918 – 1/3.0 – 2/3.(1/2.log2(1/2)+1/2.log2(1/2))= 0.25 Gain(Sunny|Humidity) = 0.918 – 2/3.0 – 1/3.0 = 0.918 Gain(Sunny|Wind) = 0.918 –2/3.0 – 1/3.0= 0.918 Bảng 2.9: Tất cả dữ liệu Sunny của Outlook # Outlook Temperature Humidity Wind Decision 1 Sunny Hot High Weak No 8 Sunny Mild High Weak No 11 Sunny Mild Normal Strong Yes E(Rain) = -1/3.log2(1/3)-2/3.log2(2/3) = 0.918 Gain(Rain|Temperature) = 0.918 - 1/3.0 – 2/3.(-1/2.log2(1/2)-1/2.log2(1/2)) = 0.25 Gain(Rain|Humidity) = 0.918 - 1/3.0 – 2/3.(-1/2.log2(1/2)-1/2.log2(1/2)) = 0.25 Gain (Rain|Wind) = 0.918 – 2/3.0 – 1/3.0 = 0.918 Bảng 2.10: Tất cả dữ liệu Rain của Outlook # Outlook Temperature Humidity Wind Decision 4 Rain Mild High Weak Yes 5 Rain Cool Normal Weak Yes 6 Rain Cool Normal Strong No Hình 2.9: Cây RF 2 sau vòng lặp thứ hai Xét nhánh Sunny-> Weak : All record return No => Stop Xét nhánh Sunny-> Strong : All record return Yes => Stop Xét nhánh Rain -> Weak : All record return Yes => Stop Xét nhánh Rain -> Strong All record return No => Stop Hình 2.10: Cây RF 2 hoàn chỉnh thứ nhất Xây dựng cây 3: Chọn ngẫu nhiên lấy training data cây 3 Bảng 2.11: Bảng đánh dấu dữ liệu được chọn ngẫu nhiên cho cây 3 # Outlook Temperature Humidity Wind Decision 1 Sunny Hot High Weak No 2 Sunny Hot High Strong No 3 Overcast Hot High Weak Yes 4 Rain Mild High Weak Yes 5 Rain Cool Normal Weak Yes 6 Rain Cool Normal Strong No 7 Overcast Cool Normal Strong Yes 8 Sunny Mild High Weak No 9 Sunny Cool Normal Weak Yes 10 Rain Mild Normal Weak Yes 11 Sunny Mild Normal Strong Yes 12 Overcast Mild High Strong Yes 13 Overcast Hot Normal Weak Yes 14 Rain Mild High Strong No Training data cây 3 Bảng 2.12: Bảng dữ liệu chọn ngẫu nhiên cho cây 3 # Outlook Temperature Humidity Wind Decision 2 Sunny Hot High Strong No 3 Overcast Hot High Weak Yes 4 Rain Mild High Weak Yes 6 Rain Cool Normal Strong No 7 Overcast Cool Normal Strong Yes 10 Rain Mild Normal Weak Yes 11 Sunny Mild Normal Strong Yes 12 Overcast Mild High Strong Yes 14 Rain Mild High Strong No E(Decision) = -(p(no).log2(p(no) + p(yes).log2(p(yes))) = - (3/9.log2(3/9)+6/9.log2(6/9)) = 0.918 E(Decision|Outlook) = p(Sunny).E(Sunny|Decision) + p(Overcast).E(Overcast|Decision) + p(Rain).E(Rain|Decision) = 2/9.-(1/2. log2(1/2) + 1/2. log2(1/2)) + 3/9.0 + 4/9.-(2/4. log2(2/4)+2/4. log2(2/4)) = 2/3 Gain(Decision|Outlook) = E(Decision) – E(Decision| Outlook) = 0.918-2/3 = 0.25 E(Decision|Temperature) = p(Hot).E(Hot|Decision) + p(Mild).E(Mild|Decision) + p(Cool).E(Cool|Decision) = 2/9.-(1/2. log2(1/2) + 1/2. log2(1/2)) + 2/9.-(1/2. log2(1/2) + 1/2. log2(1/2)) + 5/9.-(1/5. log2(1/5)+4/5. log2(4/5)) = 0.8455 Gain(Decision|Temperature) = E(Decision) – E(Decision| Temperature) = 0.918- 0.8455=0.0725 E(Decision|Humidity) = p(High).E(High|Decision) + p(Normal).E(Normal|Decision) = 5/9.- (1/5. log2(1/5) + 4/5. log2(4/5)) + 4/9.-(2/4. log2(2/4) + 2/4. log2(2/4)) = 0.8455 Gain(Decision|Humidity) = E(Decision) – E(Decision| Humidity) = 0.918-0.8455=0.0725 E(Decision|Wind) = p(Weak).E(Weak|Decision) + p(Strong).E(Strong|Decision) = 6/9.-(3/6. log2(3/6) + 3/6. log2(3/6)) + 3/9.0 = 2/3 Gain(Decision|Wind) = E(Decision) – E(Decision|Wind) = 0.918=0.25 Hình 2.11: Cây RF 3 sau vòng lặp 1 Xét nhánh Weak: All record return Yes E(Strong) = -(3/6. log2(3/6) + 3/6. log2(3/6)) = 1 Gain(Strong|Temperature) = 1 – 1/6.0 – 2/6.(-1/2.log2(1/2)-1/2.log2(1/2)) – 3/6.(- 1/3log2(1/3)-2/3log2(2/3))= 0.2 Gain(Strong|Humidity) = 1 –3/6(-2/3log2(2/3)-1/3log2(1/3)) – 3/6(-2/3log2(2/3)- 1/3log2(1/3))= 0.082 Gain(Strong|Outlook) = 1 – 2/6.(-1/2log2(1/2)-1/2log2(1/2)) - 2/6.0 – 2/6.0 = 0.3 Bảng 2.13: Tất cả dữ liệu nhánh Strong của Wind # Outlook Temperature Humidity Wind Decision 2 Sunny Hot High Strong No 6 Rain Cool Normal Strong No 7 Overcast Cool Normal Strong Yes 11 Sunny Mild Normal Strong Yes 12 Overcast Mild High Strong Yes 14 Rain Mild High Strong No Hình 2.12: Cây RF 3 sau vòng lặp 2 Xét nhánh Overcast : All record return Yes => Stop Xét nhánh Rain-> Strong : All record return No => Stop Bảng 2.14: Nhánh Sunny của Outlook nốt tiếp Strong của Wind # Outlook Temperature Humidity Wind Decision 2 Sunny Hot High Strong No 11 Sunny Mild Normal Strong Yes E(Sunny) = -1/2log2(1/2) – 1/2log2(1/2) = 1 Gain(Sunny|Temperature) = 1 – 1.0 = 1 Gain(Sunny|Humidity) = 1 – 1.0 = 1 Figure 2.13: Cây RF 3 hoàn thiện Test result Bảng 2.15: Đánh giá kết quả thuật toán RF # Outlook Tempe rature Humidity Wind Decision Tree 1 Tree 2 Tree 3 Conclusion 10 Rain Mild Normal Weak Yes Yes Yes Yes Yes 11 Sunny Mild Normal Strong Yes Yes Yes Yes Yes 12 Overcast Mild High Strong Yes Yes Yes Yes Yes 13 Overcast Hot Normal Weak Yes Yes Yes Yes Yes 14 Rain Mild High Strong No No No No No 2 Sunny Hot High Strong No No Yes No No 3 Overcast Hot High Weak Yes Yes Yes Yes Yes 7 Overcast Cool Normal Strong Yes Yes Yes Yes Yes 9 Sunny Cool Normal Weak Yes Yes No Yes Yes 2.5 Thuật toán Fuzzy Random Forest Trong Random Forest của Breiman [41], mỗi cây xây dựng với kích thước tối đa và không cắt tỉa. Trong quá trình xây dựng mỗi cây trong rừng, mỗi khi cần tách nút, chỉ có một tập con ngẫu nhiên của tập tất cả các thuộc tính được xem xét và một lựa chọn ngẫu nhiên có hoàn lại được thực hiện cho mỗi phép tách nút. Kích thước của tập con này là tham số duy nhất trong rừng ngẫu nhiên. Kết quả là, một số thuộc tính (bao gồm cả thuộc tính tốt nhất) không được xem xét cho mỗi phép tách nút, nhưng một số thuộc tính được loại trừ lại có thể được sử dụng tách nút khác trong cùng một cây. Random forest [41] có hai yếu tố ngẫu nhiên, một là bagging được sử dụng lựa chọn tập dữ liệu được sử dụng như dữ liệu đầu vào cho mỗi cây; và hai là tập các thuộc tính được coi là ứng cử viên cho mỗi nút chia. Tính ngẫu nhiên nhằm tăng sự đa dạng của cây và cải thiện chính xác kết quả dự báo sau khi tổng hợp dự báo trên các cây trong rừng. Khi random forest được xây dựng thì 1/3 đối tượng quan sát được loại bỏ ra khỏi dữ liệu huấn luyện của mỗi cây trong rừng. Các đối tượng này được gọi là “Out of bag - OOB” [41]. Mỗi cây sẽ có các tập đối tượng OOB khác nhau. Các đối tượng OOB không sử dụng để xây dựng cây và được sử dụng thử nghiệm cho mỗi cây tương ứng [41]. Thuật toán 2.1. Fuzzy Random Forest FRF (input: E, Fuzzy Partition; output: Fuzzy Random Forest) Begin 1. Tạo tập con: Lấy ngẫu nhiên có hoàn lại |E| mẫu từ tập dữ liệu huấn luyện E 2. Xây dựng cây quyết định mờ từ tập con (Thuật toán 2.2) 3. Lặp lại bước 1 và bước 2 cho tới khi tất cả các cây quyết định mờ được xây dựng. End. Thuật toán 2.2. Fuzzy Decision Tree FuzzyDecisionTree (input: E, Fuzzy Partition; output: Fuzzy Decision Tree) Begin 1. Khởi tạo các mẫu trong dữ liệu huấn luyện E với giá trị 1 (Xfuzzy_