Trang 1
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@fit.hcmuns.edu.vn
Trang 2
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 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
Đượ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
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)
Trang 6
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 7
Ví dụ Huấn luyện
Trang 8
Ví dụ (tt)
Hrain = – 3/5.log23/5 – 2/5.log22/5 = 0.442 + 0.529 = 0.971
H = 0
H = 0.971
H = 0.971
Hovercast = – 4/4.log24/4 – 0/4.log20/4 = 0 + 0 = 0
Hsunny = – 2/5.log22/5 – 3/5.log23/5 = 0.529 + 0.442 = 0.971
Trang 9
Ví dụ (tt)
Outlook
3+,2-
4+,0-
2+,3-
Rain
Overcast
Sunny
Temparature
2+,2-
4+,2-
3+,1-
Hot
Mild
Cool
H = 0
H = 0.971
H = 0.971
H = 0.918
H = 0.811
H = 1
AE = 5/14*.971 + 4/14*0 + 5/14*.971
= 0.694
AE = 4/14*1 + 6/14*.918 + 4/14*.811
= 0.911
Trang 10
Ví dụ (tt)
Humidity
3+,4-
6+,1-
High
Normal
Wind
6+,2-
3+,3-
Weak
Strong
H = 0.592
H = 0.985
H = 1
H = 0.811
AE = 7/14*.985 + 7/14*.592
= 0.788
AE = 8/14*.811 + 6/14*1
= 0.892
Chọn Outlook là thuộc tính quyết định
Trang 11
Ví dụ (tt)
Outlook
3+,2-
2+,3-
Rain
Overcast
Sunny
Yes
Chọn thuộc tính gì tiếp theo?
Tiếp tục thực hiện việc phân chia
Trang 12
Ví dụ (tt)
Outlook
3+,2-
2+,3-
Rain
Overcast
Sunny
Yes
AE (Rain, Temperature) = 2/5*1 + 3/5*.918 = 0.951
AE (Rain, Humidity) = 2/5*1 + 3/5*.918 = 0.951
AE (Rain, Wind) = 2/5*0 + 3/5*0 = 0
Trang 13
Ví dụ (tt)
Outlook
3+,2-
2+,3-
Rain
Overcast
Sunny
Yes
AE (Sunny, Temperature) = 2/5*0 + 2/5*1 + 1/5*0= 0.4
AE (Sunny, Humidity) = 2/5*0 + 3/5*0 = 0
AE (Sunny, Wind) = 2/5*1 + 3/5*.918 = 0.951
Trang 14
Ví dụ (tt)
Outlook
Rain
Overcast
Sunny
Yes
Wind
Humidity
Yes
No
Yes
No
Weak
Strong
Normal
High
Trang 15
Tri thức dạng luật
Tri thức được biểu diễn dưới dạng luật:
IF Điều kiện 1 ^ Điều kiện 2… THEN Kết luận

Dễ hiểu với con người, được sử dụng chủ yếu trong các hệ chuyên gia

Rút luật từ cây quyết định: đi từ nút gốc đến nút lá, lấy các phép thử làm tiền đề và phân loại của nút lá làm kết quả

Trang 16
Rút luật từ cây quyết định
IF Outlook = Overcast THEN Yes
IF Outlook = Rain AND Wind=Weak THEN Yes
IF Outlook = Rain AND Wind=Strong THEN No
IF Outlook = Sunny AND Humidity=Normal THEN Yes
IF Outlook = Sunny AND Humidity=High THEN No
Trang 17
Thuật giải Học Quy nạp (ILA)
Dùng để rút các luật phân lớp từ tập mẫu dữ liệu:
1. Chia tập mẫu thành các tập con ứng với thuộc tính quyết định
2. Với mỗi bảng con
3. Với mỗi tổ hợp thuộc tính có thể bắt (bắt đầu với số lượng = 1)
4. Tìm các giá trị chỉ xuất hiện ở bảng con này mà không xuất hiện ở các bảng con khác
5. (Nếu có nhiều tổ hợp thì chọn tổ hợp có số lượng mẫu tin nhiều nhất)
6. Sử dụng tổ hợp thuộc tính, giá trị vừa tìm được để tạo luật
7. Đánh dấu các dòng đã xét
8. Nếu còn dòng chưa xét, lặp lại bước 3
9. Lặp lại bước 2 với các bảng con
Trang 18
Ví dụ ILA
Trang 19
Ví dụ ILA (tt)
Trang 20
Ví dụ ILA (tt)
Chọn thuộc tính Màu sắc
với giá trị Xanh lá
Trang 21
Ví dụ ILA (tt)
IF Màu sắc = Xanh lá THEN Quyết định = Mua
Trang 22
Ví dụ ILA (tt)
IF Màu sắc = Xanh lá THEN Quyết định = Mua
IF Kích cỡ = Vừa THEN Quyết định = Mua
Trang 23
Ví dụ ILA (tt)
IF Màu sắc = Xanh lá THEN Quyết định = Mua
IF Kích cỡ = Vừa THEN Quyết định = Mua
IF Hình dáng= Cầu THEN Quyết định = Mua
Trang 24
Ví dụ ILA (tt)
IF Hình dáng = Nón THEN Quyết định = Không mua
Trang 25
Ví dụ ILA (tt)
IF Hình dáng = Nón THEN Quyết định = Không mua
Trang 26
Ví dụ ILA (tt)
IF Hình dáng = Nón THEN Quyết định = Không mua
IF Kích cỡ = Lớn AND Màu sắc = Đỏ THEN Quyết định = Không mua
Trang 27
Điều cần nắm
Nắm được khái niệm cây quyết định
Hiểu và vận dụng thuật toán ID3
Hiểu và vận dụng thuật toán học quy nạp