- BÀI 2 CÂY QUYẾT ĐỊNH (DECISION TREE) Giảng viên: TS. - PHÂN LỚP DỰA TRÊN CÂY QUYẾT ĐỊNH IV. - BÀI TOÁN PHÂN LỚP • Cho một tập mẫu dữ liệu D. - 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. - PHÂN LỚP DỰA TRÊN CÂY QUYẾT ĐỊNH 1. - Cây quyết định 2. - 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â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. - Độ đ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. - 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. - 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ó: 𝑚 |𝐷 𝐶𝑖. - Thuộc tính A có các giá trị là {a1, a2. - 𝑖𝑛𝑓𝑜 𝐷𝑗 - Độ đ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. - (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: 𝑣 |𝐷𝑗 | |𝐷𝑗 | 𝑆𝑝𝑙𝑖𝑡𝐼𝑛𝑓𝑜𝐴 𝐷. - 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: 𝐺𝑖𝑛𝑖 𝐷 = 1 − 𝑚 2 𝑖=1 𝑝𝑖 Trong đó pi là xác suất một bộ trong D thuộc lớp Ci, được tính 𝑝𝑖 = |𝐷 𝐶𝑖 | |𝐷. - 𝐺𝑖𝑛𝑖 𝐷𝑗 - Độ đ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, CarType Hoặc {Family, CarType Luxury} {Family} Luxury} {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. - 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. - Rừng ngẫu nhiên (Random Forest. - 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