Khai phá dữ liệu (Datamining) - Chương 4: Phân lớp (Classification)

Nội dung text: Khai phá dữ liệu (Datamining) - Chương 4: Phân lớp (Classification)

1. Chương 4 Phân lớp (Classification) Nội dung 1 Phân lớp và dự báo 2 Cây quyết định quy nạp 3 Phân lớp Bayes 4 Bài tập lý thuyết
2. Chương 4 Phân lớp Phân lớp và dự báo . Cĩ thể dùng phân lớp và dự báo để xác lập mơ hình/mẫu nhằm mơ tả các lớp quan trọng hay dự đốn khuynh hướng dữ liệu trong tương lai . Phân lớp (classification) dự đốn các nhãn phân loại . Dự báo (prediction) hàm giá trị liên tục 2
3. Chương 4 Phân lớp Phân lớp dữ liệu . Phân lớp dữ liệu là tiến trình cĩ 2 bước . Huấn luyện: Dữ liệu huấn luyện được phân tích bởi thuật tĩan phân lớp ( cĩ thuộc tính nhãn lớp) . Phân lớp: Dữ liệu kiểm tra được dùng để ước lượng độ chính xác của bộ phân lớp. Nếu độ chính xác là chấp nhận được thì cĩ thể dùng bộ phân lớp để phân lớp các mẫu dữ liệu mới. 3
4. Chương 4 Phân lớp Phân lớp dữ liệu . Độ chính xác (accuracy) của bộ phân lớp trên tập kiểm tra cho trước là phần trăm của các mẫu trong tập kiểm tra được bộ phân lớp xếp lớp đúng correctly classified test sample Accuracy total number of test sampl 4
5. Chương 4 Phân lớp Chuẩn bị dữ liệu . Làm sạch dữ liệu . Lọc nhiễu . Thiếu giá trị . Phân tích liên quan (chọn đặc trưng) . Các thuộc tính khơng liên quan . Các thuộc tính dư thừa . Biến đổi dữ liệu 5
6. Chương 4 Phân lớp Đánh giá phương pháp phân lớp . Độ chính xác của dự đốn: khả năng bộ phân lớp dự đốn đúng dữ liệu chưa thấy . Tính bền vững: khả năng của bộ phân lớp thực hiện dự đốn đúng với dữ liệu cĩ nhiễu hay thiếu giá trị . Tính kích cỡ (scalability): khả năng tạo bộ phân lớp hiệu quả với số lượng dữ liệu lớn . Khả năng diễn giải: bộ phân lớp cung cấp tri thức cĩ thể hiểu được 6
7. Cây quyết định (Decision tree) LOGO
8. Chương 4 Phân lớp Cây quyết định Bài tốn: quyết định cĩ đợi 1 bàn ở quán ăn khơng, dựa trên các thơng tin sau: 1. Lựa chọn khác: cĩ quán ăn nào khác gần đĩ khơng? 2. Quán rượu: cĩ khu vực phục vụ đồ uống gần đĩ khơng? 3. Fri/Sat: hơm nay là thứ sáu hay thứ bảy? 4. Đĩi: chúng ta đã đĩi chưa? 5. Khách hàng: số khách trong quán (khơng cĩ, vài người, đầy) 6. Giá cả: khoảng giá ($, $$, $$$) 7. Mưa: ngồi trời cĩ mưa khơng? 8. Đặt chỗ: chúng ta đã đặt trước chưa? 9. Loại: loại quán ăn (Pháp, Ý, Thái, quán ăn nhanh) 10. Thời gian đợi: 0-10, 10-30, 30-60, >60 8
9. Chương 4 Phân lớp Cây quyết định . Các mẫu được miêu tả dưới dạng các giá trị thuộc tính (logic, rời rạc, liên tục) . Ví dụ, tình huống khi đợi 1 bàn ăn . Các loại của mẫu là mẫu dương (T) hoặc mẫu âm (F) 9
10. Chương 4 Phân lớp Cây quyết định . Các mẫu được miêu tả dưới dạng các giá trị thuộc tính (logic, rời rạc, liên tục) . Ví dụ, tình huống khi đợi 1 bàn ăn . Các loại của mẫu là mẫu dương (T) hoặc mẫu âm (F) 10
11. Chương 4 Phân lớp Cây quyết định . Là cách biểu diễn các giả thuyết 11
12. Chương 4 Phân lớp Cây quyết định Cây quyết định là cấu trúc cây sao cho: . Mỗi nút trong ứng với một phép kiểm tra trên một thuộc tính . Mỗi nhánh biểu diễn kết quả phép kiểm tra . Các nút lá biểu diễn các lớp hay các phân bố lớp . Nút cao nhất trong cây là nút gốc. 12
13. Chương 4 Phân lớp Ví dụ cây quyết định 13
14. Chương 4 Phân lớp Thuật tốn quy nạp xây dựng cây quyết định 1. Chọn thuộc tính “tốt nhất” theo một độ đo chọn lựa cho trước 2. Mở rộng cây bằng cách thêm các nhánh mới cho từng giá trị thuộc tính 3. Sắp xếp các ví dụ học vào nút lá 4. Nếu các ví dụ được phân lớp rõ Thì Stop nguợc lại lặp lại các bước 1-4 cho các nút lá 5. Tỉa các nút lá khơng ổn định Temperature Headache Temperature Flu normal high very high {e1, e4} {e3,e6} e1 yes normal no {e2, e5} e2 yes high yes no Headache Headache e3 yes very high yes yes no yes no e4 no normal no {e2} {e5} {e3} {e6} e5 no high no e6 no very high no yes no yes no 14
15. Chương 4 Phân lớp Bảng dữ liệu huấn luyện (Training data) Day Outlook Temp Humidity Wind PlayTennis D1 Sunny Hot High Weak No D2 Sunny Hot High Strong No D3 Overcast Hot High Weak Yes D4 Rain Mild High Weak Yes D5 Rain Cool Normal Weak Yes D6 Rain Cool Normal Strong No D7 Overcast Cool Normal Strong Yes D8 Sunny Mild High Weak No D9 Sunny Cool Normal Weak Yes D10 Rain Mild Normal Weak Yes D11 Sunny Mild Normal Strong Yes D12 Overcast Mild High Strong Yes D13 Overcast Hot Normal Weak Yes D14 Rain Mild High Strong No 15
16. Chương 4 Phân lớp Cây quyết định chơi Tennis temperature cool hot mild {D5, D6, D7, D9} {D1, D2, D3, D13} {D4, D8, D10, D11,D12, D14} outlook wind outlook sunny rain o’cast true false sunny o’cast rain {D9} {D5, D6} {D7} {D2} {D1, D3, D13} {D8, D11} {D12} {D4, D10,D14} yes no yes wind yes humidity wind humidity true false high normal true false high normal {D11} {D8} {D5} {D6} {D1, D3} {D3} {D4, D14} {D10} no wind no yes outlook yes yes yes true false sunny rain o’cast {D14} {D4} {D1} {D3} no null yes no yes 16
17. Chương 4 Phân lớp Cây quyết định đơn giản hơn (tốt hơn) outlook sunny o’cast rain {D1, D2, D8 {D3, D7, D12, D13} {D4, D5, D6, D10, D14} D9, D11} humidity yes wind high normal true false {D1, D2, D8} {D9, D10} {D6, D14} {D4, D5, D10} no yes no yes Cây sẽ đơn giản hơn nếu “outlook” được chọn làm gốc. Cách chọn thuộc tính tốt để tách nút quyết định? 17
18. Chương 4 Phân lớp Thuật tốn ID3 . Mục đích: tìm cây thoả mãn tập mẫu . Ý tưởng: (đệ quy) chọn thuộc tính quan trọng nhất làm gốc của cây/cây con ID3(Examples, Target_attribute, Attributes) /* Examples: các mẫu luyện Target_attribute: thuộc tính phân lớp Attributes: các thuộc tính quyết định. */ . Tạo 1 nút gốc Root cho cây . If ∀ Examples +, trả về cây chỉ cĩ 1 nút Root, với nhãn + . If ∀ Examples -, trả về cây chỉ cĩ 1 nút Root, với nhãn – . If Attributes rỗng, trả về cây chỉ cĩ 1 nút Root, với nhãn = giá trị thường xuất hiện nhất của Target_attribute trong Examples 18
19. Chương 4 Phân lớp Thuật tốn ID3 . Ngược lại, Begin: . A ← thuộc tính trong Attributes cho phép phân loại tốt nhất Examples . Thuộc tính quyết định của nút gốc ← A . Với các giá trị vi cĩ thể cĩ của A, • Thêm 1 nhánh mới dưới gốc, ứng với phép kiểm tra A = vi • Đặt Examples vi = tập con của Examples với giá trị thuộc tính A = vi • If Examples vi rỗng – Then, dưới nhánh mới này, thêm 1 lá với nhãn = giá trị thường xuất hiện nhất của Target_attribute trong Examples – Else, dưới nhánh mới này thêm cây con ID3(Examplesvi,Target_attribute, Attributes - {A})) . End . Return Root 19
20. Chương 4 Phân lớp Lựa chọn thuộc tính tốt nhất? Nút quyết định S cĩ 19 mẫu thuộc lớp cộng (+) và 35 mẫu thuộc lớp trừ (-), ta ký hiệu là [19+, 35-] Nếu các thuộc tính A1 và A2 (mỗi thuộc tính cĩ 2 giá trị) tách S thành các nút con với tỷ lệ của mẫu dương và mẫu âm như sau, thuộc tính nào là tốt hơn? [19+, 35 -] [19+, 35 -] A1 = ? A2 = ? [21+, 5-] [8+, 30 -] [18+, 33-] [11+, 2-] 20
21. Chương 4 Phân lớp Entropy – Độ hỗn tạp dữ liệu Entropy đặc trưng độ hỗn tạp (tinh khiết) của tập các mẫu bất kỳ. S là tập các mẫu thuộc lớp âm và lớp dương P là tỷ lệ các mẫu thuộc lớp dương trong S p là tỷ lệ các mẫu thuộc lớp âm trong S Entropy(S) = -p log2p - p log2p 21
22. Chương 4 Phân lớp Entropy – Độ hỗn tạp dữ liệu Hàm entropy tương ứng với phân lớp boolean, entropy khi tỷ lệ của p các mẫu thuộc lớp dương thay đổi giữa 0 và 1. c Entropy(S)   pilog2pi i 1 22
23. Chương 4 Phân lớp Entropy – Độ hỗn tạp dữ liệu Từ 14 mẫu của bảng Play-Tennis, 9 thuộc lớp dương và 5 mẫu âm (ký hiệu là [9+, 5-] ) Entropy([9+, 5-] ) = - (9/14)log2(9/14) - (5/14)log2(5/14) = 0.940 Lưu ý: 1. Entropy là 0 nếu tất cả các thành viên của S đều thuộc về cùng một lớp. Ví dụ, nếu tất cả các thành viên đều thuộc về lớp dương (p+ = 1) thì p- là 0 và Entropy(S) = -1*log2(1) – 0*log2(0) = -1*0 – 0*0 = 0 2. Entropy là 1 nếu tập hợp chứa số lượng bằng nhau các thành viên thuộc lớp dương và lớp âm. Nếu các số này là khác nhau, entropy sẽ nằm giữa 0 và 1. 23
24. Chương 4 Phân lớp Information Gain – Độ lợi thơng tin Ta định nghĩa độ đo information gain, phản ánh mức độ hiệu quả của một thuộc tính trong phân lớp. Đĩ là sự rút giảm mong muốn của entropy gây ra bởi sự phân hoạch các ví dụ theo thuộc tính này S v Gain(S, A) Entropy(S)  Entropy(Sv ) v V alue(A ) S Gía trị Value(A) là tập các giá trị cĩ thể cho thuộc tính A, và Sv là tập con của S mà A nhận giá trị v. 24
25. Chương 4 Phân lớp Information Gain – Độ lợi thơng tin Values(Wind) = {Weak, Strong}, S = [9+, 5-] Sweak là nút con với trị “weak” là [6+, 2-] Sstrong , là nút con với trị “strong”, là [3+, 3-] S v Gain(S, Wind) = Entropy(S) -  Entropy(Sv ) v {Weak, S trong} S = Entropy(S) - (8/14)Entropy(Sweak) - (6/14)Entropy(SStrong) = 0.940 - (8/14)0.811 - (6/14)1.00 = 0.048 25
26. Chương 4 Phân lớp Thuộc tính nào là phân lớp tốt nhất? S:[9+, 5-] S:[9+, 5-] E = 0.940 E = 0.940 Humidity Wind High Normal Weak Strong [3+, 4-] [6+, 1-] [6+, 2-] [3+, 3-] E = 0.985 E = 0.592 E = 0.811 E = 1.00 Gain(S, Humidity) Gain(S, Wind) = .940 - (7/14).985 - (7/14).592 = .940 - (8/14).811 - (6/14)1.00 = .151 = .048 26
27. Chương 4 Phân lớp Information gain của tất cả thuộc tính Gain (S, Outlook) = 0.246 Gain (S, Humidity) = 0.151 Gain (S, Wind) = 0.048 Gain (S, Temperature) = 0.029 27
28. Chương 4 Phân lớp Xây dựng cây quyết định {D1, D2, , D14} [9+, 5-] Outlook Sunny Overcast Rain {D1, D2, D8, D9, D11} {D3, D7, D12, D13} {D4, D5, D6, D10, D14} [2+, 3-] [4+, 0-] [3+, 2-] ? Yes ? Thuộc tính nào cần được kiểm tra? Ssunny = {D1, D2, D3, D9, D11} Gain(Ssunny, Humidity) = .970 - (3/5)0.0 - (2/5)0.0 = 0.970 Gain(Ssunny, Temperature) = .970 - (2/5)0.0 - (2/5)1.0 - (1/5)0.0 = 0.570 Gain(Ssunny, Wind) = .970 - (2/5)1.0 - (3/5)0.918 = 0.019 28
29. Chương 4 Phân lớp Điều kiện dừng 1. Từng thuộc tính đã được đưa vào dọc theo con đường trên cây 2. Các mẫu huấn luyện ứng với nút lá cĩ cùng giá trị thuộc tính đích (chẳng hạn, chúng cĩ entropy bằng zero) Lưu ý: Thuật tốn ID3 dùng Information Gain và C4.5, thuật tốn được phát triển sau nĩ, dùng Gain Ratio (một biến thể của Information Gain) 29
30. Chương 4 Phân lớp Tạo luật từ cây quyết định outlook sunny o’cast rain humidity yes wind true false high normal no yes no yes IF (Outlook = Sunny) and (Humidity = High) THEN PlayTennis = No IF (Outlook = Sunny) and (Humidity = Normal) THEN PlayTennis = Yes 30
31. Chương 4 Phân lớp Các thuộc tính cĩ nhiều giá trị . Nếu thuộc tính cĩ nhiều giá trị (ví dụ, các ngày trong tháng), ID3 sẽ chọn nĩ . C4.5 dùng GainRatio Gain(S, A) GainRatio(S,A) SplitInformation(S,A) c Si Si SplitInformation(S,A)  log2 i 1 S S where Si is subset of S with A has value vi 31
32. Phân lớp Bayes LOGO
33. Chương 4 Phân lớp Phân lớp Bayes . Bộ phân lớp Bayes cĩ thể dự báo các xác suất là thành viên của lớp, chẳng hạn xác suất mẫu cho trước thuộc về một lớp xác định . Bộ phân lớp Nạve Bayes là cĩ thể so sánh đuợc về cơng năng với Bộ phân lớp với cây quyết định và mạng nơron. Chúng giả định các thuộc tính là độc lập nhau (độc lập điều kiện lớp) 33
34. Chương 4 Phân lớp Định lý Bayes . X là mẫu dữ liệu chưa biết nhãn lớp . H là giả thuyết sao cho X thuộc về lớp C . Ấn định xác suất hậu nghiệm posterior probability P(H|X) sao cho H đúng khi cho trước quan sát X (H conditioned on X) . Giả sử thế giới các mẫu dữ liệu gồm trái cây, được mơ tả bằng màu sắc và hình dáng. - Giả sử X là màu đỏ và trịn - H là gỉa thuyết mà X là quả táo - Thì P(H|X) phản ánh độ tin cậy X là quả táo khi biết trước X cĩ màu đỏ và trịn 34
35. Chương 4 Phân lớp Định lý Bayes . P(X|H) là xác suất tiên nghiệm của X cĩ điều kiện trên H. Định lý Bayes P(X|H)P(H) P(H| X) P(X) . Khi cĩ n giả thuyết P(X|Hi )P(Hi) P(Hi | X) n P(X|H )P(H ) j 1 j j 35
36. Chương 4 Phân lớp Phân lớp Nạve Bayesian (NBC) . Mỗi mẫu dữ liệu được biểu diễn bằng X= (x1, x2, , xn) với các thuộc tính A1, A2, , An . Các lớp C1, C2, , Cm. Cho trước mẫu chưa biết X. NBC gán X vào Ci iff P(Ci|X) > P(Cj|X) với 1 j m, j i. Do vậy, chúng ta cực đại P(Ci|X). Lớp Ci sao cho P(Ci|X) là cực đại được gọi là giả thuyết hậu nghiệm cực đại (maximum posterior hypothesis). Theo định lý Bayes P(X|C )P(C ) P(C |X) i i i P(X) 36
37. Chương 4 Phân lớp Phân lớp Nạve Bayesian (NBC) . Do P(X) là hằng cho tất cả các lớp, chỉ cần cực đại P(X|Ci) P(Ci). Nếu chưa biết P(Ci) cần giả định P(C1)=P(C2)= = P(Cm) và chúng ta sẽ cực đại P(X|Ci). Ngược lại, ta cực đại P(X|Ci) P(Ci) . Nếu m là lớn, sẽ rất tốn kém khi tính P(X|Ci) P(Ci). NBC giả định độc lập điều kiện lớp n P(X|Ci ) P(xk |Ci) k 1 37
38. Chương 4 Phân lớp Phân lớp Nạve Bayesian (NBC) . Cĩ thể phỏng tính P(x1|Ci), , P(xn|Ci) từ các mẫu huấn luyện Nếu Ak được phân lớp thì P(xk|Ci) = sik/si với sik là số mẫu huấn luyện của Ci cĩ trị xk cho Ak và si là số các mẫu thuộc về lớp Ci Nếu Ak là liên tục thì nĩ được giả định cĩ phân bố Gaussian (x μ )2 k Ci 1 2σ 2 P(x |C ) g(x ,μ ,σ ) e Ci k i k Ci Ci 2πσ Ci 38
39. Chương 4 Phân lớp Phân lớp Nạve Bayesian (NBC) . Để phân lớp mẫu chưa biết X, ta tính P(X|Ci) P(Ci) cho từng Ci. Sau đĩ mẫu X được gán vào Ci nếu P(Ci|X) > P(Cj|X) for 1 j m, j i . Nĩi cách khác, NBC gán X vào lớp Ci sao cho P(X|Ci) P(Ci) là cực đại 39
40. Chương 4 Phân lớp Dữ liệu khách hàng 40
41. Chương 4 Phân lớp Dự đốn nhãn lớp với phân lớp Bayesian . X = (age=“<=30”, income=“medium”, student=“yes”, credit_rating=“fair”) . P(buys_computer = “yes”) = 9/14 = 0.643 P(buys_computer = “no”) = 5/14 = 0.357 . Để tính P(X|Ci) P(Ci), cho i = 1, 2, chúng ta tính: P(age = “<=30”| buys_computer = “yes”) = 2/9 = 0.222 P(age = “<=30”| buys_computer = “no”) = 3/5 = 0.600 P(income = “medium”| buys_computer = “yes”) = 4/9 = 0.444 P(income = “medium”| buys_computer = “no”) = 2/5 = 0.444 P(student = “yes”| buys_computer = “yes”) = 6/9 = 0.667 P(student = “yes”| buys_computer = “no”) = 1/5 = 0.200 P(credit_rating = “yes”| buys_computer = “yes”) = 6/9 = 0.667 P(credit_rating = “yes”| buys_computer = “no”) = 2/5 = 0.400 41
42. Chương 4 Phân lớp Dự đốn nhãn lớp với phân lớp Bayesian . P(X|buys_computer = “yes”) = 0.222 x 0.667 x 0.667 x 0.044 = 0.044 . P(X|buys_computer = “no”) = 0.600 x 0.400 x 0.200 x 0.400 = 0.019 . P(X|buys_computer = “yes”)P(buys_computer = “yes”) = 0.044 x 0.643 = 0.028 . P(X|buys_computer = “no”)P(buys_computer = “no”) = 0.019 x 0.357 = 0.007 . Vì vậy, NBC dự đốn buys_computer = “yes” cho mẫu X 42
43. Chương 4 Phân lớp Bài tập lý thuyết Dùng thuật tốn ID3 và Nạve Bayes để tìm luật phân lớp trong bảng dữ liệu “da rám nắng” sau: TT Màu Chiều cao Cân nặng Dùng Kết quả tĩc thuốc? 1 Đen Tầm thước Nhẹ Khơng Bị rám 2 Đen Cao Vừa phải Cĩ Khơng 3 Râm Thấp Vừa phải Cĩ Khơng 4 Đen Thấp Vừa phải Khơng Bị rám 5 Bạc Tầm thước Nặng Khơng Bị rám 6 Râm Cao Nặng Khơng Khơng 7 Râm Tầm thước Nặng Khơng Khơng 8 Đen Thấp Nhẹ Cĩ Khơng 43
44. Chương 4 Phân lớp Bài tập lý thuyết Dùng thuật tốn ID3 và Nạve Bayes để tìm luật phân lớp trong bảng dữ liệu “gia cảnh” sau: Vĩc dáng Quốc tịch Gia cảnh Nhĩm O1 Nhỏ Đức Độc thân A O2 Lớn Pháp Độc thân A O3 Lớn Đức Độc thân A O4 Nhỏ Ý Độc thân B O5 Lớn Đức Cĩ gia đình B O6 Lớn Ý Độc thân B O7 Lớn Ý Cĩ gia đình B O8 Nhỏ Đức Cĩ gia đình B 44