BÀI 2 CÂY QUYẾT ĐỊNH (DECISION TREE) Giảng viên: TS. Hoàng Văn Thông Email: thonghv@utc.edu.vn – ĐT: 0988.113.679 1 NỘI DUNG I. BÀI TOÁN PHÂN LỚP II. ỨNG DỤNG CỦA PHÂN LỚP III. PHÂN LỚP DỰA TRÊN CÂY QUYẾT ĐỊNH IV. BÀI TẬP 2 I. BÀI TOÁN PHÂN LỚP • Cho một tập mẫu dữ liệu D ={ (xi, Ci), i = 1,..,N }, xi là một véc tơ n chiều có dạng (xi1, xi2,.., xin), xij Uj là miền xác định của các biến (thuộc tính) 𝔛j của bài toán, với j = 1,..,n, Ci  C tập các nhãn có m lớp, i = 1,.., m, N là số mẫu dữ liệu. • Từ tập mẫu dữ liệu D xây dựng một mô hình cho phép phân lớp bất kỳ mẫu dữ liệu p  U = U1  ...  Un. • Mô hình là một ánh xạ f từ U vào C 3 Minh họa bài toán phân lớp 4 Các phương pháp phân lớp cơ bản 1. 2. 3. 4. Decision Tree based Methods Rule-based Methods Naïve Bayes and Bayesian Belief Networks Support Vector Machines 5 II. ỨNG DỤNG PHÂN LỚP – Trong y học: chẩn đoán bệnh (dựa trên các triệu chứng, kết quả xét nghiệm phân loại bệnh) – Trong sinh học: xác định loài – Trong sản xuất: phân loại sản phẩm – Trên web: phân lớp email, phân lớp website,... – Nhận dạng: chữ viết, hình ảnh,... 6 III. PHÂN LỚP DỰA TRÊN CÂY QUYẾT ĐỊNH 1. Cây quyết định 2. Một số khái niệm 3. Các thuật toán xây dựng cây quyết 4. Thuật toán xây dựng cây quyết định tổng quát 5. Cây quyết định ID3 6. Cây quyết định C4.5 7. Cây quyết định CART 8. Kiểu dữ liệu của thuộc tính 9. Cắt tỉa cây 10. Rừng ngẫy nhiên 7 1. Cây QĐ sinh ra từ dữ liệu • Mỗi cây quyết định cho môt tâp quy tắc phân lớp: • Mỗi đường di từ gốc đến là cho 1 luật • Mỗi nút ≠ lá biểu thị một thuộc tính/điều kiện kiểm tra • Mỗi cạnh biểu thị giá trị kiểm tra của thuộc tính tương ứng • Mỗi lá cho một giá trị nhãn xác định bởi luật 8 Ví dụ Cây QĐ sinh ra từ dữ liệu 9 2. Một số khái niệm • Độ trong suốt (pure) của DB: một DB có độ trong suốt cao nếu nó có ít lớp (trong trường hợp lý tưởng là có 1 lớp). • Độ đo lựa chọn thuộc tính (Attribute selection measure): là độ đo của mỗi thuộc tính dùng để lựa chọn thuộc tính phân hoạch tập dữ liệu có độ trong suốt cao nhất. 10 3. Các thuật toán xây dựng cây quyết định • Dựa trên đô đo lựa chọn thuộc tính ta có các thuật toán – ID3 - Iterative Dichotomise, tác giả J. Ross Quinlan (1970s-1980s), sử dụng độ đo Gain Information – C4.5 (Khắc phục nhược điểm ID3), tác giả J. Ross Quinlan (1993), sử dụng độ đo Gain ratio (hiện tại có phiên bản C5.0) – CART - Classification and Regression Trees , tác giả L. Breiman, J. Friedman, R. Olshen, and C. Stone (1984), sử dụng độ đo Gini index – Một số độ đo khác: CHAID, C-SEP, MDL 11 4. Thuật toán xây dựng cây quyết định tổng quát 12 5. Cây quyết định ID3 Độ đo lựa chọn thuộc tính Infomation Gain (Gain) - Dựa trên lý thuyết thông tin của Claude Shannon - Một thuộc tính được chọn nếu nó có giá trị Gain lớn nhất Ta có: - - 𝐼𝑛𝑓𝑜 𝐷 = − 𝑚 𝑖=1 𝑝𝑖 × 𝑙𝑜𝑔2 𝑝𝑖 trong đó 𝑝𝑖 = Thuộc tính A có các giá trị là {a1, a2, ..., av} - 𝐼𝑛𝑓𝑜𝐴 𝐷 = 𝑣 |𝐷𝑗 | 𝑗=1 |𝐷| × |𝐷 𝐶𝑖 | |𝐷| 𝑖𝑛𝑓𝑜 𝐷𝑗 - Độ đo Infomation gain của A 𝐺𝑎𝑖𝑛 𝐴 = 𝐼𝑛𝑓𝑜 𝐷 − 𝐼𝑛𝑓𝑜𝐴 𝐷 - Nhược điểm của độ đo này là có xu hướng lựa chọn thuộc tính có nhiều giá trị => khả năng tạo ra các phân hoạch dữ liệu có tính trong suốt cao => có Gain->min. (Ví dụ: thuộc tính ID) 13 Ví dụ: Xây dựng cây ID3 cho bài toán sau đây 14 6. Cây quyết đinh C4.5 Độ đo lựa chọn thuộc tính Gain ratio - Khắc phục nhược điểm của độ đo Infomation gain - Một thuộc tính A được chọn nếu nó có giá trị Gain Ratio lớn nhất Tính: 𝑆𝑝𝑙𝑖𝑡𝐼𝑛𝑓𝑜𝐴 𝐷 = − 𝑮𝒂𝒊𝒏𝑹𝒂𝒕𝒊𝒐 𝑨 = 𝑣 |𝐷𝑗 | 𝑗=1 |𝐷| × 𝑮𝒂𝒊𝒏(𝑨) 𝑺𝒑𝒍𝒊𝒕𝑰𝒏𝒇𝒐𝑨 (𝑫) 𝑙𝑜𝑔2 |𝐷𝑗 | |𝐷| 15 7. Cây quyết định CART Độ đo lựa chọn thuộc tính Gini index - Gini index đo độ không trong suốt của tập dữ liệu D - Tính: 2 𝐺𝑖𝑛𝑖 𝐷 = 1 − 𝑚 𝑖=1 𝑝𝑖 Trong đó pi là xác suất một bộ trong D thuộc lớp Ci, được tính 𝑝𝑖 = |𝐷 𝐶𝑖 | |𝐷| - Thuộc tính A có các giá trị là {a1, a2, ..., av} - 𝐺𝑖𝑛𝑖𝐴 𝐷 = 𝑣 |𝐷𝑗 | 𝑗=1 |𝐷| × 𝐺𝑖𝑛𝑖 𝐷𝑗 - Độ đo Infomation gain của A ∆𝐺𝑖𝑛𝑖 𝐴 = 𝐺𝑖𝑛𝑖 𝐷 − 𝐺𝑖𝑛𝑖𝐴 𝐷 16 8. Các kiểu dữ liệu của thuộc tính • Kiểu thuộc tính – Định danh – Thứ tự – Dữ liệu liên tục • Các cách chia – 2-way split – Multi-way split 17 Cách phân chia • Multi-way split: Sử dụng một số giá trị khác nhau CarType Family Luxury Sports • Binary split: Chia giá trị thành 2 tập con. {Sports, Luxury} CarType {Family} Hoặc {Family, Luxury} CarType {Sports} 18 Dữ liệu liên tục • Có 2 cách để giải quyết – Rời rạc hóa để hình thành thuộc tính phân loại • Tĩnh: Rời rạc hóa ngay từ đầu • Động: Các khoảng có thể được xác định: khoảng bằng nhau, tần xuất bằng nhau (phần trăm) hoặc phân cụm – Phân chia nhị phân: (A < v) or (A  v) • Xem xét tất cả các khả năng chia để tìm điểm chia tốt nhất 19 9. Cắt tỉa cây - Lý do phải cắt tỉa - Một số nhánh cây bất thường (do dữ liệu bị nhiễu, phần tử ngoại lai) - Giải quyết vấn đề quá khớp dữ liệu (overfitting data) - Làm cho cây trở nên đơn giản hơn => dễ hiểu với người dùng - Các hướng tiếp cận - Cắt tỉa trước (prepruning): dừng (halting) sơm trong quá trình xây dựng cây, không phân hoạch tiếp mà tạo ra nút lá với nhãn là lớp có số lượng cao nhất - Dừng lại khi cây đạt độ cao cho trước - Dừng lại khi độ đo lựa chọn thuộc tính < ngưỡng cho trước - Cắt tỉa sau (postpruning): cắt tỉa sau khi cây đã phát triển đầy đủ. - Thay thế một cây con bằng một nút lá có nhãn là lớp chủ yếu của cây con 20 10. Rừng ngẫu nhiên (Random Forest) • Tại sao lại là rừng ngẫu nhiên? • Rừng ngẫu nhiên là gì? (Breiman) • Rừng ngẫu nhiên là một bộ mô hình bao gồm một tập cây quyết định được kết hợp theo phương thức bỏ phiếu (Vote). • Các cây QĐ cơ sở được xây dựng từ các tập DL con gồm các mẫu dữ liệu có các thuốc tính khác nhau được lấy ngẫu nhiên từ tập DL học. 21 Tạo Rừng ngẫu nhiên • Gồm 3 pha 22 Thủ tục xây dựng rừng ngẫu nhiên • Gồm 3 phá – Tạo dữ liệu ngẫu nhiên – Tạo cây QĐ cơ sở – Kết hợp các cây QĐ cơ sở theo phương thức bỏ phiếu • Pha tạo dữ liệu từ tập dữ liệu 𝐷 = 𝑥𝑖 , 𝑦𝑖 𝑁 𝑖=1 , 𝑥𝑖 ∈ 𝑅𝑛 – Chọn ngâu nhiên M (<N) và m (<n) để tạo ra cơ sở dữ liệu con Dk – Theo gợi ý của Breiman thì m được chọn như sau: Với bài toán phân lớp thì m = n , bài toán hồi qui m = n/3 23 Thuật toán xây dựng rừng ngẫu nhiên • Bước 1. For k=1 to L 1.1. Lấy ngẫu nhiên m thuộc tính {𝐴𝑘𝑖1 , .., 𝐴𝑘𝑖𝑚 } của D; 1.2. Lấy ngẫy nhiên 𝑅𝑘 gồm M mẫu dữ liệu trong D; 1.3. 𝐷𝑘 = 𝑅𝑘 chiếu trên {𝐴𝑘𝑖1 , .., 𝐴𝑘𝑖𝑚 } 1.4 Xây dựng cây 𝑇𝑘 từ tâp 𝐷𝑘 ; ta có mô hình 𝑐𝑘 ; • Bước 2. Kết hợp bỏ phiếu chọn trong 𝐶𝑘 𝐿 𝑘=1 24 IV. Bài tập • Cho cơ sở dữ liệu điểm có câu trúc như hình bên. • Yêu cầu: – Chuyển đổi điểm về dạng chữ (F, D, …) – Chuyển điểm TBC thành xếp loại (<5.0 : Yếu, 5 ≤ và <7: Trung Bình, 7≤ và <8: Khá, 8 ≤ và <9: Giỏi, 9 ≤ : Xuất sắc – Xây dựng cây quyết định từ CSDL này – Nhập vào một bộ điểm của 1 sinh viên cho biết sinh viên này được xếp loại nào 25 Dữ liệu phân lớp mẫu • https://archive.ics.uci.edu/ml/datasets.html?format=&task=cla&att=&area=&numAtt=&numIns=&ty pe=&sort=nameUp&view=table 26