Trang 1
Cây quyết định (ID3) và
Cây quyết định (ID3) và
Học Quy nạp (ILA)
Học Quy nạp (ILA)
Tô Hoài Việt
Khoa Công nghệ Thông tin
Đại học Khoa học Tự nhiên TPHCM
thviet@fit.hcmuns.edu.vn
Trang 2
Nội dung
Nội dung
•Cây quyết định
•Học cây quyết định – Thuật toán ID3
•Biểu diễn tri thức bằng luật
•Rút luật từ cây quyết định
•Thuật toán học quy nạp
Trang 3
Cây quyết định
Cây quyết định
Cây quyết định biểu diễn:
• Mỗi nút trong kiểm tra
một thuộc tính
• Mỗi nhánh tương ứng
với giá trị thuộc tính
• Mỗi nút lá được gán một
phân lớp
Định luật Occam: những
cây đơn giản là những
cây quyết định tốt hơn
Trang 4
Thuật toán học ID3
Thuật toán học ID3
Được phát triển đồng thời bởi Quinlan trong AI và Breiman, Friedman,
Olsen và Stone trong thống kê
Lặp:
1. Chọn A thuộc tính quyết định “tốt nhất” cho nút kế tiếp
2. Gán A là thuộc tính quyết định cho nút
3. Với mỗi giá trị của A, tạo nhánh con mới của nút
4. Phân loại các mẫu huấn luyện cho các nút lá
5. Nếu các mẫu huấn luyện được phân loại hoàn toàn thì NGƯNG,
Ngược lại, lặp với các nút lá mới.
Thuộc tính tốt nhất là gì?
Trang 5
Entropy
Entropy
•S là tập các mẫu huấn luyện
•p là tỷ lệ các mẫu dương trong S
•H – p.log2p – (1 – p).log2(1 – p)