Bài giảng Cây quyết định (ID3) và học quy nạp (ILA) - Tô Hoài Việt giới thiệu đến bạn đọc những nội dung về: 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. | Cây quyết định (ID3) và 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@ Trang 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 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 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 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 – – (1 – p).log2(1 – p) Trang 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 sẽ làm tối thiểu hoá entropy trung bình của dữ liệu trong các nút con Trang Ví dụ Huấn luyện Trang Ví dụ (tt) Outlook 3+,2- 4+,0- 2+,3- Rain Overcast Sunny Hrain = – 3/ – 2/ = + = H = 0 H = H = Hovercast = – 4/ – 0/ = 0 + 0 = 0 Hsunny = – 2/ – 3/ = + = Trang Ví dụ (tt) Outlook 3+,2- 4+,0- 2+,3- Rain Overcast Sunny Temparature 2+,2- 4+,2- | Cây quyết định (ID3) và 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@ Trang 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 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 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 Entropy S .
