Bài giảng Máy học và mạng Neural - Bài 3: Cây quyết định - Vũ Đức Lung

07/08/2013 1 Bài 03 – Cây quyết định Decision tree learning 1 Nội dung  Định nghĩa, giới thiệu  Biểu diễn mô hình/giả thuyết bằng DT.  Khả năng ứng dụng của DT.  Giải thuật học cơ bản.  Các vấn đề học với cây quyết định  Thuật toán ID3.  Các vấn đề trong DT.  Giới thiệu C4.5. 2 07/08/2013 2 Định Nghĩa  Cây Quyết định là một cây phân lớp  Nút nội : là nút thử nghiệm  Nút lá : nút phân loại ( phân lớp )  Cây phân lớp bằng cách lọc mẫu nhập từ trên xuống  Kết quả là phân biệt và đầy đủ 3 Định Nghĩa Cây quyết định có thể khác nhau trên một số khía cạnh : – Nút thử nghiệm có thể là đơn biến hay đa biến – Có thể có 2 hoặc hơn 2 kết quả đầu ra – Các đặc trưng hoặc thuộc tính có thể là phân loại hoặc là số – Đầu ra (cuối cùng) có thể có hai hoặc nhiều lớp 4 07/08/2013 3 Định Nghĩa  Ví dụ 5 Giới thiệu Cây quyết định là phương pháp suy luận qui nạp được sử dụng và thực hành rộng rãi nhất. Là một phương pháp xấp xỉ hàm mục tiêu của tập các giá trị rời rạc. Cách biểu diễn các hàm học được – Cây quyết định hoặc – Tập các luật if-then mà người có thể đọc được. 6 07/08/2013 4 Giới thiệu (tt) Các phương pháp học được sử dụng rộng rãi: – ID3 – ASSISTANT – C4.5 Nhiệm vụ của các phương pháp học: – Tìm kiếm không gian giả thuyết hoàn chỉnh – Loại bỏ khó khăn của không gian giả thuyết có giới hạn. 7 Cách biểu diễn cây quyết định Cây quyết định phân loại các thể hiện bằng cách sắp xếp chúng vào một cây từ gốc đến lá – Mỗi node trong cây là một thuộc tính của các thể hiện – Mỗi nhánh là một giá trị có thể có của các thuộc tính này Cây quyết định được sử dụng trong phân lớp bằng cách duyệt từ nút gốc của cây cho đến khi đụng đến nút lá, từ đó rút ra lớp của đối tượng cần xét 8 07/08/2013 5 Mô hình cây quyết định Ví dụ 1: Playing Tennis. Day Outlook Temp. Humidity Wind Play tennis 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 Cold 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 9 Decision Tree for PlayTennis Outlook Sunny Overcast Rain Humidity High Normal Wind Strong Weak No Yes Yes Yes No 10 07/08/2013 6 Decision Tree for PlayTennis Outlook Sunny Overcast Rain Humidity High Normal No Yes Each internal node tests an attribute Each branch corresponds to an attribute value node Each leaf node assigns a classification 11 No Decision Tree for PlayTennis Outlook Sunny Overcast Rain Humidity High Normal Wind Strong Weak No Yes Yes Yes No Outlook Temperature Humidity Wind PlayTennis Sunny Hot High Weak ? 12 07/08/2013 7 Decision Tree for Conjunction Outlook Sunny Overcast Rain Wind Strong Weak No Yes No Outlook=Sunny  Wind=Weak No 13 Decision Tree for Disjunction Outlook Sunny Overcast Rain Yes Outlook=Sunny  Wind=Weak Wind Strong Weak No Yes Wind Strong Weak No Yes 14 07/08/2013 8 Decision Tree for XOR Outlook Sunny Overcast Rain Wind Strong Weak Yes No Outlook=Sunny XOR Wind=Weak Wind Strong Weak No Yes Wind Strong Weak No Yes 15 Decision Tree Outlook Sunny Overcast Rain Humidity High Normal Wind Strong Weak No Yes Yes Yes No decision trees represent disjunctions (or) of conjunctions (and) (Outlook=Sunny  Humidity=Normal)  (Outlook=Overcast)  (Outlook=Rain  Wind=Weak) 16 07/08/2013 9 Mô hình cây quyết định Ví dụ 2: Ngồi bàn đợi tại một restaurant: Alternate: Có restaurant nào cạnh đây không? Bar: Liệu có khu vực quầy bar có thể ngồi không? Fri/Sat: hôm nay là thứ 8 hay thứ 7? Hungry: có đang đói không? Patrons: Số người trong restaurant (None, Some, Full) Price: khoảng giá ($, $$, $$$) Raining: ngoài trời có mưa không? Reservation: đã đặt trước chưa? Type: loại restaurant (French, Italian, Thai, Burger) WaitEstimate: thời gian chờ đợi (0-10, 10-30, 30-60, >60) 17 Mô hình cây quyết định Ví dụ 2: Ngồi bàn đợi tại một restaurant: 18 07/08/2013 10 Mô hình cây quyết định Ví dụ 2: Ngồi bàn đợi tại một restaurant: 19 – D = {t1, , tn} trong đó ti= – Cơ sở dữ liệu gồm có quan hệ {A1, A2, , Ah} – Các lớp C={C1, ., Cm} Một cây là cây quyết định (hay Cây phân lớp) của D nếu: – Mỗi nút trong được gán nhãn thuộc tính Ai – Mỗi cung được gán nhãn một mệnh đề thuộc tính-giá trị với thuộc tính là nhãn nút xuất phát của cung. – Mỗi nút lá được gán nhãn Cj. Mô hình cây quyết định 20 07/08/2013 11 Khả năng biểu diễn  Cây quyết định có khả năng dùng để biểu diễn bất cứ hàm nào.  E.g. hàm Boolean:  Với một cây quyết định nhất quán với tập mẫu huấn luyện thì mỗi input, output của hàm tương ứng với một đường đi trong cây. Nhưng cũng có thể khả năng khái quát hoá không cao đối với các ví dụ mới chưa biết. Mô hình cây quyết định 21 Các vấn đề thường dùng cây quyết định để giải quyết  Các thể hiện được biểu diễn dưới dạng cặp thuộc tính – giá trị – Các thuộc tính này thường là cố định (vd: nhiệt độ) và các giá trị của nó cũng cố định (vd: nóng) – Thuộc tính thường là các giá trị rời rạc nhưng cũng cho phép xử lý trên các giá trị thực (phải mở rộng các thuật toán cơ bản).  Các hàm chức năng (target-functions) có các giá trị đầu ra là rời rạc – Trong ví dụ trên có 2 phân lớp là Yes và No 22 07/08/2013 12 Các vấn đề thường dùng cây quyết định để giải quyết  Có thể yêu cầu biểu diễn dưới dạng biểu thức luận lý  Dữ liệu huấn luyện có thể có lỗi. – Cây quyết định là một phương pháp xử lý tốt với các trường hợp lỗi (lỗi trong phân lớp và lỗi trong giá trị thuộc tính)  Dữ liệu huấn luyện có thể bị khuyết giá trị Ứng dụng: – Classification. – Medical diagnosis – Credit risk analysis – Object classification for robot manipulator (Tan 1993) 23 Giải thuật học cơ bản  Hầu hết các giải thuật học trên cây quyết định là các biến thể của giải thuật học top-down, tìm kiếm tham lam (greedy search)  Giải thuật học gồm các bước như sau: – Cây được thiết lập từ trên xuống dưới – Rời rạc hóa các thuộc tính dạng phi số – Các mẫu huấn luyện nằm ở gốc của cây – Chọn một thuộc tính để phân chia thành các nhánh. Thuộc tính được chọn dựa trên độ đo thống kê hoặc độ đo heuristic – Tiếp tục lặp lại việc xây dựng cây quyết định cho các nhánh 24 07/08/2013 13 Giải thuật học cơ bản  Điều kiện dừng – Tất cả các mẫu rơi vào một nút thuộc về cùng một lớp (nút lá) – Không còn thuộc tính nào có thể dùng để phân chia mẫu nữa – Không còn lại mẫu nào tại nút 25 Lựa chọn thuộc tính phân lớp Độ đo để lựa chọn thuộc tính: Thuộc tính được chọn là thuộc tính có lợi nhất cho quá trình phân lớp (tạo ra cây nhỏ nhất) Có 2 độ đo thường dùng – Độ lợi thông tin (Information gain) • Giả sử tất cả các thuộc tính dạng phi số • Có thể biến đổi để áp dụng cho thuộc tính số • Xác định số bits tối thiểu của thông tin cần để mã hóa phân loại một thành viên tùy ý của S – Chỉ số Gini (Gini index) • Giả sử tất cả các thuộc tính dạng số • Giả sử tồn tại một vài giá trị có thể phân chia giá trị của từng thuộc tính • Có thể biến đổi để áp dụng cho thuộc tính phi số 26 07/08/2013 14 Một số vấn đề với DT Không gian tìm kiếm khổng lồ. Lựa chọn thuộc tính để phân hoạch ntn? Cách phân hoạch ra sao? Quản lý cấu trúc cây ntn? Tiêu chuẩn dừng? Các vấn đề với dữ liệu huấn luyện. Các vấn đề với thuộc tính dữ liệu. Over-fitting và nhu cầu đơn giản hoá mô hình. 27 Các vấn đề học với cây quyết định  Chọn lựa kiểu cho thử nghiệm  Dùng Độ lợi thông tin (information gain) để chọn thử nghiệm  Thuộc tính không phải nhị phân (non-binary) 28 07/08/2013 15  Chọn lựa kiểu cho thử nghiệm – Thông thường có n thuộc tính – Thuộc tính nhị phân • Giá trị thuộc tính ở nút thử nghiệm là 0 hoặc 1 – Thuộc tính phân loại ( không phải nhị phân ) • Chia giá trị thuộc tính vào các tập con phân biệt và đầy đủ Các vấn đề học với cây quyết định 29 Các vấn đề học với cây quyết định  Ví dụ chọn lựa kiểu cho thử nghiệm 30 07/08/2013 16  Dùng Độ lợi thông tin (information gain) để chọn thử nghiệm – Vấn đề : chọn thứ tự các thử nghiệm – Với các thuộc tính phân loại và số => chọn giá trị thích hợp cho thử nghiệm – Giải pháp : giảm tối đa entropy (đo tính thuần khiết) Các vấn đề học với cây quyết định 31  Thuộc tính không phải nhị phân (non-binary) – Vẫn sử dụng kỹ thuật trên – Đặt ngưỡng với miền giá trị thực – Chọn gom nhóm phân loại với những giá trị phân loại Các vấn đề học với cây quyết định 32 07/08/2013 17 Mạng tương đương với cây Quyết định  Cây Quyết định luận lý đơn biến cài đặt hàm DNF (disjunctive normal form) sẽ tương đương với mạng neuron truyền thẳng 2 lớp 33 Giải thuật ID3  Lựa chọn thuộc tính phân lớp dựa trên độ lợi thông tin (Information gain)  Thuộc tính nào là tốt nhất?  Là giải thuật tham ăn (greedy) mở rộng cây từ gốc đến ngọn A1=? True False [21+, 5-] [8+, 30-] [29+,35-] A2=? True False [18+, 33-] [11+, 2-] [29+,35-] 34 07/08/2013 18 Độ đo sự đồng nhất của mẫu s s s s ppSentropy i m i i i m i i 2 1 2 1 loglog)(     pi: tần suất xuất hiện của các mẫu trong lớp Ci với i = {1, , m}  S: số lượng tập huấn luyện  Si: số các mẫu của S nằm trong lớp Ci  Thông tin cần biết để phân lớp một mẫu 35 Một số lưu ý  Trong trường hợp phân lớp nhị phân: – Entropy = 0: khi tất cả thuộc về 1 lớp – Entropy = 1: số lượng các ví dụ ở cả hai lớp bằng nhau – Còn lại: 0<entropy<1   ppppSentropy 22 loglog)( 36 07/08/2013 19 Độ lợi thông tin )()(A),G( )( v AValuesv v SEntropy S S SEntropyS     Thuộc tính A có các giá trị {a1, a2, ,an}  Dùng thuộc tính A để phân chia tập huấn luyện thành n tập con {S1, S2, , Sn}  Độ lợi thông tin dựa trên phân nhánh bằng thuộc tính A:  Tại mỗi cấp, chúng ta chọn thuộc tính có độ lợi lớn nhất để phân nhánh cây hiện tại 37 Information Gain  Gain(S,A): expected reduction in entropy due to sorting S on attribute A A1=? True False [21+, 5-] [8+, 30-] [29+,35-] A2=? True False [18+, 33-] [11+, 2-] [29+,35-] Gain(S,A)=Entropy(S) - vvalues(A) |Sv|/|S| Entropy(Sv) Entropy([29+,35-]) = -29/64 log2 29/64 – 35/64 log2 35/64 = 0.99 s s s s ppSentropy i m i i i m i i 2 1 2 1 loglog)(    38 07/08/2013 20 Information Gain A1=? True False [21+, 5-] [8+, 30-] [29+,35-] Entropy([21+,5-]) = 0.71 Entropy([8+,30-]) = 0.74 Gain(S,A1)=Entropy(S) -26/64*Entropy([21+,5-]) -38/64*Entropy([8+,30-]) =0.27 Entropy([18+,33-]) = 0.94 Entropy([8+,30-]) = 0.62 Gain(S,A2)=Entropy(S) -51/64*Entropy([18+,33-]) -13/64*Entropy([11+,2-]) =0.12 A2=? True False [18+, 33-] [11+, 2-] [29+,35-] 39 Ví dụ Day Outlook Temp. Humidity Wind Play? 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 Cold 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 40 07/08/2013 21 Ví dụ 940.0 14 5 log 14 5 14 9 log 14 9 )5,9()S,Entropy(S 2221  Entropy  Ta có – S = 14 – m = 2 – C1 = “Yes”, C2 = “No” – S1 = 9, S2 = 5 41 Ví dụ 985.0 7 4 log 7 4 7 3 log 7 3 22  Gain(S,Humidity) =0.940 – (7/14)*0.985 – (7/14)*0.592 =0.151 E=0.985 E=0.592 Humidity Normal [3+, 4-] High [6+, 1-] 592.0 7 1 log 7 1 7 6 log 7 6 22  42 07/08/2013 22 Ví dụ 811.0 8 2 log 8 2 8 6 log 8 6 22  Gain(S,Wind) =0.940 – (8/14)*0.811 – (6/14)*1.000 =0.048 E=0.811 E=1.000 Wind Strong [6+, 2-] Weak [3+, 3-] 000.1 6 3 log 6 3 6 3 log 6 3 22  43 Ví dụ Gain(S,Temperature) = 0.029 Temperature Mild [2+, 2-] Hot [4+, 2-] [3+, 1-] Cold 44 07/08/2013 23 Ví dụ Gain(S,Outlook) =0.940 – (5/14)*0.971 – (4/14)*0.0 – (5/14)*0.0971 =0.247 E=0.971 E=0.000 Outlook Overcast [2+, 3-] Sunny [4+, 0-] E=0.971 [3+, 2-] Rain Gain(S,Humidity)=0.151 Gain(S,Wind)=0.048 Gain(S,Temperature) = 0.029 45 Ví dụ ??? ??? Outlook Yes Sunny Overcast Rain Gain(Ssunny, Humidity) = 0.971 – (3/5)*0.0 – (2/5)*0.0 = 0.971 Gain(Ssunny, Temperature) = 0.971 – (2/5)*0.0 – (2/5)*1.0 – (1/5)*0.0 = 0.571 Gain(Ssunny, Wind) = 0.971 – (2/5)*1.0 – (3/5)*0.918 = 0.02 Which attribute should be tested here? 46 07/08/2013 24 ID3 Algorithm Outlook Sunny Overcast Rain Humidity High Normal Wind Strong Weak No Yes Yes Yes No [D3,D7,D12,D13] [D8,D9,D11] [D6,D14] [D1,D2] [D4,D5,D10] 47 Biến đổi cây quyết định thành luật  Biểu diễn tri thức dưới dạng luật IF-THEN Mỗi luật tạo ra từ mỗi đường dẫn từ gốc đến lá Mỗi cặp giá trị thuộc tính dọc theo đường dẫn tạo nên phép kết (phép AND – và)  Các nút lá mang tên của lớp 48 07/08/2013 25 Biến đổi cây quyết định thành luật Wind Humidity Outlook Yes No Yes Sunny Overcast Rain Yes No High Normal Strong Weak R1: If (Outlook=Sunny)  (Humidity=High) Then Play=No R2: If (Outlook=Sunny)  (Humidity=Normal) Then Play=Yes R3: If (Outlook=Overcast) Then Play=Yes R4: If (Outlook=Rain)  (Wind=Strong) Then Play=No R5: If (Outlook=Rain)  (Wind=Weak) Then Play=Yes 49 Ưu và khuyết điểm của ID3 Không gian giả thuyết: là một tập hợp các cây quyết định 50 07/08/2013 26 Ưu và khuyết điểm của ID3  Ưu điểm: – Không gian giả thuyết này là đầy đủ (gồm các giá trị rời rạc hữu hạn: Yes/ No) giả thuyết chắc chắn thuộc về không gian này – Tại mỗi bước, ID3 xét hết tất cả các mẫu huấn luyện, đưa ra kết quả dựa vào thống kê kết quả ít bị lỗi – Dễ xây dựng – Phân lớp mẫu mới nhanh – Dễ dàng diễn giải cho các cây kích thước nhỏ 51 Ưu và khuyết điểm của ID3  Khuyết điểm – Phương pháp thực hiện của ID3 là phương pháp leo đồi đi từ đơn giản đến phức tạp, chỉ duy trì một tình trạng giả thuyết  giả thuyết không có khả năng đại diện toàn cục – Không quay lui (No Backtracking)  cực tiểu địa phương – Gặp tình trạng quá khớp (Overfitting) 52 07/08/2013 27 Cây quyết định học bởi ID3 từ ví dụ 2 mô hình cây quyết định: Nhỏ hơn cây quyết định đưa ra lúc đầu Ví dụ Ngồi bàn đợi tại một restaurant 53 Thiên hướng quy nạp (Inductive Bias)  Vì dữ liệu huấn luyện thường hạn chế, nên thường được khái quát hóa theo một số khía cạnh nào đóheuristic (sử dụng inductive bias)  Inductive bias đề cập đến những giả định bổ sung (additional assumptions) mà người học sẽ dùng để dự đoán đầu ra đúng cho các tình huống chưa gặp phải trước đây. • Inductive bias: thường sử dụng cho những cây quyết định nhỏ  Phân loại: – Restriction Bias: giới hạn một số giả thuyết trong quá trình học – Preference Bias: có sự ưu tiên cho một số giả thuyết  ID3 thuộc preference bias 54 07/08/2013 28 Occam’s razor  Thế giới vốn dĩ là đơn giản  Cách giải thích đơn giản nhất bao phủ được toàn bộ dữ liệu là cách hiệu quả nhất  Tại sao??? William of Ockham (1285–1349) 55 Occam’s razor  Lí do: – Số lượng giả thuyết ngắn, đơn giản thường ít hơn nhiều so với số lượng các giả thuyết dài, phức tạp – Các giả thuyết ngắn thường tránh được sự trùng hợp ngẫu nhiên  Hạn chế: – Nếu có nhiều giả thuyết ngắn, thì cái nào là phù hợp??? – Kích thước của giả thuyết là bao nhiêu thì tốt?  tùy thuộc vào cách xác định của mỗi người  có thể cho kết luận khác nhau trên cùng một vấn đề 56 07/08/2013 29 Thiên hướng quy nạp của ID3  Ưu tiên chọn cây ngắn  Chọn cây với các thuộc tính có độ lợi thông tin lớn nhất mà gần gốc nhất 57 Cây định danh (1) Hair color Lotion used  Emily Alex Pete John Sarah Annie Dana Katie blonde red brown No Yes 58 07/08/2013 30 Cây định danh (2) Hair color Weight Alex Annie Blonde Red Brown Height Short Average Tall Weight Dana Pete Sarah Hair color Blonde Red Brown Katie Emily John Average Heavy Light Average Heavy Light 59 Cây định danh (1) Hair color Lotion used  Emily Alex Pete John Sarah Annie Dana Katie blonde red brown No Yes Chọn cây 1 60 07/08/2013 31 Cây định danh (3) Hair color Weight Annie Blonde Red Brown Height Short Average Tall Weight Dana Pete Sarah Hair color Blonde Red Brown Katie Emily John Average Heavy Light Gain = 0.97 Gain = 0.85 61 Cây định danh (4) Hair color Weight Annie Blonde Red Brown Height Short Heavy Tall Weight Dana Pete Sarah Hair color Blonde Red Brown Katie Emily John Average Average Light Gain = 0.85 Gain = 0.95 62 07/08/2013 32 Cây định danh (3) Hair color Weight Annie Blonde Red Brown Height Short Average Tall Weight Dana Pete Sarah Hair color Blonde Red Brown Katie Emily John Average Heavy Light Gain = 0.97 Gain = 0.85 Chọn cây 3 63 Các vấn đề trong cây quyết định Kết hợp các thuộc tính có giá trị liên tục Lựa chọn thuộc tính bằng độ đo thay thế Xử lý mẫu huấn luyện với thuộc tính có giá trị khuyết Xử lý thuộc tính với chi phí khác nhau  Tập trung cho thuật toán ID3 64 07/08/2013 33 Thuộc tính có giá trị liên tục Thuật toán ID3 bắt buộc dùng thuộc tính có giá trị rời rạc – Thuộc tính đích, dùng ra quyết định – Thuộc tính dẫn dắt quyết định Phân chia giá trị liên tục thành các khoảng rời rạc, và có thể đưa vào cây quyết định Cho A là thuộc tính có giá trị liên tục, việc phân tách tạo 2 giá trị logic Ac với: với c là điểm phân tách  Chọn giá trị c tối ưu?       cAfalse cAtrue Ac , , 65 Giới thiệu C4.5  Là phần mềm cài đặt và cải tiến ID3, tác giả Ross Quinlan. Địa chỉ download (program, source code in C, documentation): s/c4.5/tutorial.html Gói phần mềm WEKA (source code in JAVA): 66 07/08/2013 34 Đọc thêm  Giáo trình - chương 3.  R. Quinlan, C4.5: Programs for Machine Learning, Morgan Kaufmann, 1993. 67 Câu hỏi ôn tập 1. cây quyết định là gì? 2. Nêu các đặc điểm của các bài toàn giải bằng cây quyết định 3. Trình bày thuật toán học cho cây quyết định? 4. Trình bày nội dung/đặc điểm của thuật toán ID3. 5. Nêu các vấn đề và giải pháp trong học/khái quát hoá của ID3. 6. Nêu các vấn đề và giải pháp trong xử lý thuộc tính của ID3. 7. Ứng dụng C4.5 để giải các bài toán thực tế. 68 07/08/2013 35 Bài tập mẫu 1 69 Dùng ID3 vẽ cây quyết định khi biết tập dữ liệu training sau: Bài tập mẫu 2 An muốn áp dụng giải thuật ID3 để xây dựng cây quyết định với tập dữ liệu rèn luyện trên. Áp dụng các công thức tính entropy và gain, hãy giúp An xác định thuộc tính nào (A1, A2 hay A3) là thuộc tính tốt nhất để hỏi đầu tiên nhằm tạo ra một cây quyết định đơn giản nhất. (Lưu ý: phải trình bày các tính toán entropy và gain để đi đến kết luận). 70 07/08/2013 36 Bài tập mẫu 3 Cho tập các dữ liệu lưu trữ 10 ngày cuối tuần mà Mike đã làm gì như sau. Trong đó thời tiết (Weather) có 3 thuộc tính, Cha mẹ (Parents) có hoặc không có nhà và Tiền (Money) có nhiều(rich) hoặc ít (poor). Có 4 lớp là xem phim (Cinema), chơi Tennis, mua sắm (Shopping) hoặc ở nhà (Stay in). Hãy vẽ cây quyết định cho tập huấn luyện trên (chỉ cần vẽ cây cho thuộc tính thứ nhất và thuộc tính thứ hai cho giá trị đầu tiên cửa thuộc tính thứ nhất). (Lưu ý: phải trình bày các tính toán entropy và gain để đi đến kết luận). 71 Weekend (Example) Weather Parents Money Decision (Category) W1 Sunny Yes Rich Cinema W2 Sunny No Rich Tennis W3 Windy Yes Rich Cinema W4 Rainy Yes Poor Cinema W5 Rainy No Rich Stay in W6 Rainy Yes Poor Cinema W7 Windy No Poor Cinema W8 Windy No Rich Shopping W9 Windy Yes Rich Cinema W10 Sunny No Rich Tennis