Bài giảng Học máy - L5: Các phương pháp học có giám sát Học cây quyết định (Decision tree learnin

Nội dung text: Bài giảng Học máy - L5: Các phương pháp học có giám sát Học cây quyết định (Decision tree learnin

1. Nội dung môn học: „ Giới thiệu chung „ Đánh giá hiệunăng hệ thống họcmáy „ Các phương pháp họccd dựatrênxácsua trên xác suất „ Các phương pháp họccógiámsát „ Học cây quyết định (Decision tree learning) „ Các phương pháp học không giám sát „ Lọccộng tác „ Họctăng cường Học Máy – IT 4862 2
2. Ví dụ về DT: Những tin tức nào mà tôi quan tâm? “sport”? is present is absent “player”? “football”? is present is absent is present is absent Interested Uninterested Interested “goal”? is present is absent Interested Uninterested • ( ,“sport”, ,“player”, ) → Interested • ( ,“goal”, ) → Interested • ( ,“sport”, ) → Uninterested Học Máy – IT 4862 4
3. Biểu diễn câyyq quy ết định (()1) „ Mỗi nút trong (internal node) biểu diễn một thuộc tính cần kiểmtragiátrm tra giá trị (an attribute to be tested) đốivi với các ví dụ „ Mỗi nhánh (branch) từ một nút sẽ tương ứng với một giá trị có thể củathua thuộc tính gắnvn với nút đó „ Mỗi nút lá (leaf node) biểu diễn một phân lớp (a classification) „ Một cây quyết định học được sẽ phân lớp đối với một ví dụ, bằnggy cách duyệt cây từ nút gốc đến một nút lá → Nhãn lớp gắn với nút lá đó sẽ được gán cho ví dụ cần phân lớp ọ H c Máy – IT 4862 6
4. Những tin tức nào mà tôi quan tâm? “sport”? is present is absent “player”? “football”? is present is absent is present is absent Interested Uninterested Interested “goal”? is present is absent Interested Uninterested [(“ sport ” is pr esen t) ∧ (“ppayelayer” iss pr esen t)] ∨ [(“sport” is absent) ∧ (“football” is present)] ∨ [(“sport” is absent) ∧ (“football” is absent) ∧ (“goal” is present)] Học Máy – IT 4862 8
5. Giải thuật ID3 – Ý tưởng „ Thựchiệngiảithuật tìm kiếm tham lam (greedy search) đốivới không gian các cây quyết định có thể „ Xây dựng (học) một cây quyết định theo chiếnlược top-down, bắt đầu từ nút gốc „ Ở mỗi nút, thuộc tính kiểm tra (test attribute) là thuộc tính có khả năng phân loạitốtnhất đốivớicácvídụ họcgắnvới nút đó „ Tạomớimột cây con (sub-tree) của nút hiệntạichomỗigiátrị có thể của thuộc tính kiểm tra, và tập học sẽ được tách ra (thành các tập con) tương ứng với cây con vừatạo „ Mỗithuộc tính chỉđược phép xuấthiệntối đa1 lần đốivớibấtkỳ một đờđường đi nào trong cây „ Quá trình phát triển(học) cây quyết định sẽ tiếptụcchođếnkhi • Cây quyết định phân loại hoàn toàn (perfectly classifies) các ví dụ học, hoặc • Tấtcả các thuộc tính đã đượcsử dụng ọ H c Máy – IT 4862 10
6. Lựa chọn thuộc tính kiểm tra „ Tạimỗi nút, chọnthuộc tính kiểmtranhư thế nào? „ Chọn thuộc tính quan tr ọng nhất cho việc phân lớp các ví dụ học gắn với nút đó „ Làm thế nào để đánh giá khả năng củamột thuộc tính đốivớiviệc phân tách các ví dụ học theo nhãn lớp của chúng? → Sử dụng một đánh giá thống kê – Information Gain „ Ví dụ: Xét bài toán phân lớpcó2 lớp(c1, c2) → Thuộc tính nào, A1 hay A2, nên đượcchọnlàthuộc tính kiểmtra? (c : 35, c : 25) (c : 35, c : 25) A1=? 1 2 A2=? 1 2 v11 v21 v22 v13 v12 c1: 21 c1: 5 c1: 9 c1: 27 c1: 8 c2: 9 c2: 5 c2: 11 c2: 6 c2: 19 ọ H c Máy – IT 4862 12
7. Entropy – Ví dụ với 2 lớp „ S gồm 14 ví dụ, trong đó9 vídụ thuộcvề lớp c1 1 và 5 ví dụ thuộcvề lớp c2 „ Entropy củatập S đốivới phân lớpcó2 lớp: 0.5 Entropy(S) = -(9/14).log2(9/14)- tropy(S) (5/14).log2(5/14) ≈ 0.94 En 0 „ Entropy =0, nếutấtcả các ví dụ thuộc cùng một 0.5 1 lớp (c1 hoặc c2) p1 „ Entropy =1, số lượng các ví dụ thuộc về lớp c1 bằng số lượng các ví dụ thuộc về lớp c2 „ Entropy = một giá trị trong khoảng (0,1), nếu như số lượng các ví dụ thuộc về lớp c1 khác với số lượng các ví dụ thuộc về lớp c2 ọ H c Máy – IT 4862 14
8. Tập các ví dụ học Xét tập dữ liệu S ghi lại những ngày mà một người chơi (không chơi) tennis: Day Outlook Temperature Humidity Wind Play Tennis D1 Sunny Hot High Weak No D2 Sunny Hot High Strong No D3 Overcast Hot High Weak Yes D4 RiRain Mild Hig h WkWeak 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 [Mitchell, 1997] ọ H c Máy – IT 4862 16
9. Học câyyq quy ết định – Ví dụ (()1) „ Tại nút gốc, thuộc tính nào trong số {Outlook, Temperature, Humidity, Wind} nên đượcchọnlàthuộc tính kiểmtra? • Gain(S, Outlook) = = 0.246 Có giá trị IG • Gain(S, Temperature) = = 0.029 cao nhất • Gain(S, Humidity) = = 0. 151 • Gain(S, Wind) = = 0.048 →Vì vậy, Outlook đượcchọnlàthuộc tính kiểm tra cho nút gốc! Outlook=? S={9+, 5-} SunnyOvercast Rain Node1 Yes Node2 SOvercast={4+, 0-} SSunny={2+, 3-} SRiRain={3+, 2-} ọ H c Máy – IT 4862 18
10. Học cây quyết định – Chiến lược tìm kiếm (1) „ ID3 tìm kiếm trong không gian các giả thiết (các cây quyết định có thể)m) một cây quyết định phù hợp (fits) các ví dụ học „ ID3 thựchic hiệnchin chiếnln lược tìm ki ếmtm từ đơngin giản đếnphn phức tạp, bắt đầu với cây rỗng (empty tree) „ Quá trình tìm ki ếmmc củaaID3 ID3 được điềukhiu khiểnbn bởi độ đo đánh giá Information Gain „ ID3 chỉ tìm ki ếmmm một(cht (chứ không phảiit tấttc cả các) cây quyết định phù hợp với các ví dụ học ọ H c Máy – IT 4862 20
11. Ưu tiên trong học câyyq quy ết định (()1) „ Cả 2 cây quyết định dưới đây đều phù hợp với tập học đã cho „ Vậy thì , cây quyết định nào sẽ được ưuutiên( tiên (đượcch học) b ởi giải thuật ID3? Outlook=? Otlk?Outlook=? Sunny Rain Sunny Overcast Rain Overcast Humidity=? Yes Wind=? Temperature=? Yes Wiind=? High Normal Strong Weak Hot Cool Mild Strong Weak No Yes No Yes No Yes Humidity=? No Yes High Normal No Yes ọ H c Máy – IT 4862 22
12. Các vấn đề trong ID3 „ Cây quyết định học được quá phù hợp (over-fit) với các ví dụ học „ Xử lý các thuộc tính có kiểu giá trị liên tục (kiểu số thực) „ Các đáhánh g iáhùhiá phù hợp hơn (tốtht hơn IfInformati on G Gi)ain) đối với việc xác định thuộc tính kiểm tra cho một nút „ Xử lý các ví d ụ họccthi thiếugiátru giá trị thuộc tính (missing -value attributes) „ Xử lý các thuộc tính có chi phí (cost) khác nhau → Cải tiến của giải thuật ID3 với tất cả các vấn đề nêu trên đượcgic giải quyết: giảithui thuậtC45t C4.5 ọ H c Máy – IT 4862 24
13. Over-fitting trong học cây quyết định (1) Tiếp tục quá trình học cây quyết định sẽ làm giảm độ chính xác đối với tập thử nghiệm mặc dù tăng độ chính xác đối với tập học [Mitchell, 1997] ọ H c Máy – IT 4862 26
14. Giải quyết vấn đề over-fitting (2) „ Làm sao để chọn kích thước “phù hợp” của cây quyết định? • Đánh giá hiệu năng phân loại đối với một tập tối ưu (validation set) - Đây là phương pháp thường được sử dụng nhất - 2ff2 f.f. chí híhnh: reddduced-error pruning and rultle post-pruning • Áp dụng một thí nghiệm thống kê (vd: chi-square test) để đánh giá xem việc mở rộng (hay cắt tỉa) một nút có giúp cải thiện hiệu năng đối với tập huấn luyện • Đánh giá độ phức tạp của việc mã hóa (thể hiện) các ví dụ học và câyyq qu yết định,,g và ngừng việc học (phát triển))yqy cây quyết định khi kích thước của việc mã hóa này là tối thiểu - Dựa trên nguyên lý Minimum Description Length (MDL) - Cần cực tiểu hóa: size(()tree) + size((())misclassifications(tree)) ọ H c Máy – IT 4862 28
15. Rule post-pruning „ Học (phát triển) cây quyết định hoàn toàn phù hợp với tập huấn luyện Outlook=? Overcast Rain „ Chuyển biểu diễn cây quyết định học Sunny được thành một tập các luật tương ứng Yes (tạomo mộttlu luậttchom cho mỗi đường điit từ nút Humidity=? Wind=? gốc đến một nút lá) High Normal Strong Weak „ Rút gọn (tổng quát hóa) mỗi luật (độc lập No Yes No Yes vớicáclui các luật khác) , bằng cách loạiib bỏ bất kỳ điều kiện nào giúp mang lại sự cải thiện về hiệu quả phân loại của luật đó IF (Outlook=Sunny) Λ ((yHumidity=Normal) „ Sắp xếp cáálc luật đããút rút gọn theo kh ả năng (hiệu quả) phân loại, và sử dụng THEN (PlayTennis=Yes) thứ tự này cho việc phân loại các ví dụ trong tương lai ọ H c Máy – IT 4862 30
16. Các đánh giá khác cho lựa chọn thuộc tính „ Xu hướng của đánh giá Information Gain → Ưu tiên các thuộc tính có nhiều giá trị hơn các thuộc tính có ít giá trị Vd: Thuộc tính Date có số lượng rất lớn các giá trị có thể - Thuộc tính này sẽ có giá trị Information Gain cao nhất - Một mình thuộc tính này có thể phân loại hoàn hảo toàn bộ tập huấn luyện (thuộc tính này phân chia các ví dụ học thành rất nhiều các tập con có kích thước rất nhỏ) - Thuộc tính này được chọn là thuộc tính kiểm tra ở nút gốc (của cây quyết định chỉ có mức độ sâu bằng 1, nhưng rấttr rộng, rất nhi ều phân nhánh) „ Một đánh giá khác: Gain Ratio →Giảm ảnh hưởng của các thuộc tính có (rất) nhiều giá trị Gain(S, A) GainRatio(S, A) = SplitInformation(S, A) (trong đó Values(A) là tập S S các giá trị có thể của thuộc SplitInfor mation (S, A) = − v log v ∑ 2 tính A, và S ={x| x∈S, x =v}) v∈Values ( A) S S v A ọ H c Máy – IT 4862 32
17. Xử lý các thuộc tính thiếu giá trị (2) →Giải pháp 3: • Tính xác suất pv đối với mỗi giá trị có thể v của thuộc tính A • Gán phần (fraction) pv của ví dụ x đối với nhánh tương ứng của nút n • Những ví dụ mộtpht phần (fractional instances) này đượccs sử dụng để tính giá trị Information Gain . . . Ví dụ: • Mộttht thuộc tính ki ểu nhị phân (0/1) A Nút n • Nút n bao gồm: - Một ví dụ x (thiếu giá trị đối với A) A=1 A=0 - 4íd4 ví dụ cóiátó giá trị đối với A bằng 1à1, và •4 ví dụ có •6 ví dụ có - 6 ví dụ có giá trị đối với A bằng 0 giá trị đối giá trị đối với A =1 với A =0 p(xA=1) = 4/10 = 0.4 • 0.4 của • 0.6 của p(xA=0) = 6/10 = 0.6 x x ọ H c Máy – IT 4862 34
18. Học cây quyết định – Khi nào? „ Các ví dụ học được biểu diễn bằng các cặp (thuộc tính,giá trị) •Phù hợp với các thuộc tính có giá trị rời rạc •Đối với các thuộc tính có giá trị liên tục, phải rời rạc hóa „ Hàm mục tiêu có giá trị đầu ra là các giá trị rời rạc •Ví d ụ: Phân lo ạiicácvíd các ví dụ vào lớp phù hợp „ Rất phù hợp khi hàm mục tiêu được biểu diễn ở dạng tách rời (disjunctive form) „ Tập huấn luyện có thể chứa nhiễu/lỗi •Lỗi trong phân loại (nhãn lớp) của các ví dụ học •Lỗiti trong giá iát trị thuộc tính bi ểu diễn cááídc ví dụ học „ Tập huấn luyện có thể chứa các thuộc tính thiếu giá trị •Các gi á trị đối với mộttt thu ộctc tính là khô n g x ác định đối với mộtts số ví dụ học ọ H c Máy – IT 4862 36