- Pham HUST 1 Cây quyết định là một kiểu mô hình dự báo Kỹ thuật học máy dùng trong cây quyết định được gọi là học bằng cây quyết định Phương tiện có tính mô tả dành cho việc tính toán các xác suất có điều kiện Sự kết hợp của các kỹ thuật toán học và tính toán nhằm hỗ trợ việc mô tả, phân loại và tổng quát hóa một tập dữ liệu cho trước Cây quyết định là một cấu trúc phân cấp của các nút và các nhánh ◦ 3 loại nút trên cây: Nút gốc Nút nội bộ: mang tên thuộc tính của CSDL Nút lá: mang tên lớp Ci ◦ Nhánh: mang giá trị có thể của thuộc tính 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á. - >ể thực hiện điều đó, anh cần hiểu được tại sao khách hàng quyết định chơi và tìm hiểu xem có cách giải thích nào cho việc đó hay không. - 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 No 6 Rain Cool Normal Strong Yes 7 Overcast Cool Normal Weak No 8 Sunny Mild High Weak Yes 9 Sunny Cold Normal Weak Yes 10 Rain Mild Normal Strong 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 Kiểm tra khi nào chơi golf, khi nào không chơi Outlook Sunny Overcast Rain Humidity Yes Wind High Normal Strong Weak No Yes No Yes Kiểm tra khi nào chơi golf, khi nào không chơi Outlook Sunny Overcast Rain Humidity Mỗi nút mang một thuộc tính (biến độc lập) High Normal Mỗi nhánh tương ứng với một giá trị của thuộc tính No Yes Mỗi nút lá là một lớp (biến phụ thuộc) Day Outlook Temp. - Humidity Wind Play? 1 Sunny Hot High Weak No Outlook Sunny Overcast Rain Humidity Yes Wind High Normal Strong Weak No Yes No Yes Outlook=Sunny ∧ Wind=Weak Outlook. - OR = hoặc Sunny Overcast Rain Wind No No Strong Weak No Yes Outlook=Sunny ∨ Wind=Weak Outlook Sunny Overcast Rain Yes Wind Wind Strong Weak Strong Weak No Yes No Yes (Outlook=Sunny ∧ Humidity=Normal. - Outlook=Overcast ∨ (Outlook=Rain ∧ Wind=Weak) Outlook Sunny Overcast Rain Humidity Yes Wind High Normal Strong Weak No Yes No Yes 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 >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 ộ đ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 ◦ 1. - >ộ 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ố ◦ 2. - 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ố 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 với i = {1. - log 2 i i =1 s s 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} Sij : số mẫu của lớp Ci thuộc tập con Sj (A=aj) Entropy của thuộc tính A: n s1 j. - s ) mj j =1 s >ộ lợi thông tin dựa trên phân nhánh bằng thuộc tính A: G(A. - E(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 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 No 6 Rain Cool Normal Strong Yes 7 Overcast Cool Normal Weak No 8 Sunny Mild High Weak Yes 9 Sunny Cold Normal Weak Yes 10 Rain Mild Normal Strong 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 Ta có ◦ S = 14 ◦ m=2 ◦ C1 = “Yes”, C2 = “No. - log 2 − log Humidity 3 3 4 4 − log 2 − log High Normal 6 6 1 1 − log 2 − log E=0.985 E=0.592 Gain(S,Humidity Ghi chú: >ể tính log25 bằng máy tính điện tử, nhấn: 5 log / 2 log Wind 6 6 2 2 − log 2 − log Weak Strong 3 3 3 3 − log 2 − log E=0.811 E=1.000 Gain(S,Wind Outlook Sunny Overcast Rain E=0.971 E=0.000 E=0.971 Gain(S,Wind)=0.048 Gain(S,Outlook Gain(S,Humidity Chỉ số Gini của nút t: 2 GINI(t. - GINI(i ) trong đó i =1 n ◦ ni là số mẫu trong nút i ◦ n là số mẫu trong nút p Chọn thuộc tính có GINIchia nhỏ nhất để phân nhánh Chỉ phân thành 2 nhánh A p p C1 6 N1 N2 C2 6 Gini(N Gini Ginichia Gini(N N1 N C1 5 1 C2 2 4 Gini Dựa trên một giá trị nếu TID Refund Marital Tax Cheat 1 Yes Single 125K No muốn phân chia nhị phân 2 No Married 100K No Dựa trên vài giá trị nếu 3 No Single 70K No muốn có nhiều nhánh 4 Yes Married 120K No Với mỗi giá trị tính các 5 No Divorced 95K Yes mẫu thuộc một lớp theo 6 No Married 60K No 7 Yes Divorced 220K No dạng Av 8 No Single 85K Yes Cách chọn giá trị v đơn 9 No Married 75K No giản: với mỗi giá trị v trong 10 No Single 90K Yes CSDL đều tính Gini của nó và lấy giá trị có Gini nhỏ Tax nhất kém hiệu quả > 80K < 80K Cách chọn giá trị v hiệu quả. - Sắp xếp các giá trị tăng dần ◦ Chọn giá trị trung bình của từng giá trị của thuộc tính để phân chia và tính chỉ số gini ◦ Chọn giá trị phân chia có chỉ số gini thấp nhấ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 Outlook Sunny Overcast Rain Humidity Yes Wind High Normal Strong Weak No Yes No Yes R1: If (Outlook=Sunny. - (Humidity=High) Then Play=No R2: If (Outlook=Sunny. - (Wind=Weak) Then Play=Yes Cây quyết định dễ hiểu Việc chuẩn bị dữ liệu cho một cây quyết định là cơ bản hoặc không cần thiết Cây quyết định có thể xử lý cả dữ liệu có giá trị bằng số và dữ liệu có giá trị là tên thể loại Cây quyết định là một mô hình hộp trắng Có thể thẩm định một mô hình bằng các kiểm tra thống kê Cây quyết định có thể xử lý tốt một lượng dữ liệu lớn trong thời gian ngắn Chuyển thành luật Phân lớp, khai phá dữ liệu Tỉa cây (tỉa cây trước-cùng với dựng cây, tỉa cây sau, sai số tỉa cây. - khử nhiễu Bảng quyết định - Cây quyết định - Mạng quyết định (có thêm nút HOẶC http://www.montefiore.ulg.ac.be/~geurts/dta pplet/dtexplication.html http://webdocs.cs.ualberta.ca/~aixplore/lear ning/DecisionTrees/Applet/DecisionTreeAppl et.html 39 13