Thuật toán Quinlan hay còn được gọi là thuật toán vector đặc trưng.
Quinlan quyết định thuộc tính phân hoạch bằng cách xây dựng các vector đặc trưng cho mỗi giá trị của từng thuộc tính dẫn xuất và thuộc tính mục tiêu.
Ứng với mỗi thuộc tính dẫn xuất A còn có thể sử dụng để phân hoạch, tính :
VA(j) = (T(j,r1), T(j,r2), ..., T(j,rn))
T(j,ri) = (tổng số phân tử trong phân hoạch có giá trị thuộc tính dẫn xuất A là j và có giá trị thuộc tính mục tiêu là rj ) / (tổng số phân tử trong phân hoạch có giá trị thuộc tính dẫn xuất A là j).
Một vector VA (j) được gọi là vecto đơn vị nếu nó chỉ có duy nhất thành phần có giá trị l và nhũng thành phần khác có giá trị 0.
Thuộc tính được chọn để phân hoạch là thuộc tính có nhiều Vector đơn vị nhất.
Xét một vidu: Xây dựng các quy luật để có thể kết luận một người như thế nào khi đi tắm biển thì bị cháy nắng :
Stt | Tóc | Chiều cao | Cân nặng | Dùng kem | Kết quả |
1 | Vàng | Trung bình | Nhẹ | Không | Cháy |
2 | Vàng | Cao | Trung bình | Có | Không |
3 | Nâu | Thấp | Trung bình | Có | Không |
4 | Vàng | Thấp | Trung bình | Không | Cháy |
5 | Đỏ | Trung bình | Năng | Không | Cháy |
6 | Nâu | Cao | Nặng | Không | Không |
7 | Nâu | Trung bình | Nặng | Không | Không |
8 | Vàng | Thấp | Nhẹ | Có | Không |
Giải:
Tìm vector đặc trưng cho mỗi thành phần:
VTóc(vàng) = (T(vàng, cháy), T(vàng, không cháy))
Từ bảng CSDL ta có : số người tóc vàng là : 4
Số người tóc vàng và cháy nắng là : 2
Số người tóc vàng và không cháy nắng là : 2
Suy ra: VTóc(vàng) = (2/4 , 2/4) = (0.5 , 0.5)
Áp dụng tương tự cho mỗi thành phần ta có ;
VTóc(nâu) = (0/3 , 3/3) = (0 , 1) (vector đơn vi)
VTóc(đỏ) = (1/1 , 0/1) = (1 , 0) (vector đơn vi)
Thuộc tính "Chiều cao"
VChiều cao(cao) = (0/2 , 2/2) = (0 , 1) (vector đơn i=vị)
VChiều cao(trung bình) = (2/3 , 1/3)
VChiều cao(thấp) = (1/3 , 2/3)
Thuộc tính "Cân nặng":
VCân năng(nhẹ) = (1/2 , 1/2)
VCân năng(trung bình) = (1/3 , 2/3)
VCân năng(nặng) = (1/3 , 2/3)
Thuộc tính "Dùng kem":
VDùng kem (có) = (3/3 , 0/3) = (1,0) (vector đơn vị)
VDùng kem (không) = (3/5 , 2/5)
Như vậy thuộc tính "tóc " có nhiều vector đơn vị nhất nên ta dùng để phân hoạch.
Sau khi phân hoạch theo "tóc": thì ta thấy màu tóc = "nâu" thì luôn cho kết quả = "không" & màu tóc = "đỏ" cho kết quả là = "cháy" còn màu tóc = "vàng" cho kết quả là "cháy" và "không" nên ta dùng nó để phân hoạch.
Ta có bảng CSDL mới :
Stt | Chiều cao | Cân nặng | Dùng kem | Kết quả |
1 | Trung bình | Nhẹ | Không | Cháy |
2 | Cao | Trung bình | Có | Không |
4 | Thấp | Trung bình | Không | Cháy |
8 | Thâp | Nhẹ | Có | Không |
Áp dụng cách giải ở trên ta có cây quyết định như sau:
Từ cây quyết định rút ra được các tập luật :
r1: if(tóc = "nâu") then không cháy nắng
r2: if(tóc = "đỏ") then cháy nắng
r3: if(tóc = "vàng") and (dùng kem = "có ") then không cháy nắng
r4: if(tóc = "vàng") and (dùng kem = "không") then cháy nắng.
Bạn cũng có thể thực hành code tại Đây.
Bình luận bài viết