Thuật toán Quinlan
Thuật toán 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.
Bước 1: Phân loại thuộc tính dẫn xuất và thuộc tính mục tiêu
Thuộc tính mục tiêu: là thuộc tính quan tâm.
Thuộc tính dẫn xuất: là thuộc tính quan quan sát.
Bước 2: Với mỗi thuộc tính dẫn xuất A, tính vector đặc trưng
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à 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 )
* r1, r2, … , rn là các giá trị của thuộc tính mục tiêu
Bước 3: Chọn thuộc tính có nhiều vector đơn vị nhất để phân hoạch.
Vector đơn vị là vector có duy nhất một thành phần có giá trị 1 và những thành phần khác có giá trị 0.
Bước 4: Loại bỏ các thuộc tính đã được phân hoạch.
Nếu vẫn còn thuộc tính đẫn xuất quay lại bước 2 để tính vector đặc trưng cho các thuộc tính dẫn xuất.
Ngược lại, kết thúc thuật toán.
Ví dụ ta có bảng dữ liệu quan sát như sau
| Day | Outlook | Temperature | Humidity | Wind | Play Tenis |
| 1 | Sunny | Hot | High | Weak | No |
| 2 | Sunny | Hot | High | Strong | No |
| 3 | Overcast | Hot | High | Weak | Yes |
| 4 | Rain | Mild | High | Weak | Yes |
| 5 | Rain | Cool | Normal | Weak | Yes |
| 6 | Rain | Cool | Normal | Strong | No |
| 7 | Overcast | Cool | Normal | Strong | Yes |
| 8 | Sunny | Mild | High | Weak | No |
| 9 | Sunny | Cool | Normal | Weak | Yes |
| 10 | Rain | Mild | Normal | Weak | Yes |
| 11 | Sunny | Mild | Normal | Strong | Yes |
| 12 | Overcast | Mild | High | Strong | Yes |
| 13 | Overcast | Hot | Normal | Weak | Yes |
| 14 | Rain | Mild | High | Strong | No |
| 15 | Sunny | Cool | High | Strong | ? |
*Xét thuộc tính Outlook
V_outlook(sunny)=(T(Sunny,Yes play),T(Sunny,No play))
Số sunny là: 5
Số sunny và yes play là: 2
Số sunny và no play là: 3
Do đó:
V_outlook(Sunny)=(2/5,3/5)=(0.4,0.6)
Tương tự:
V_outlook(Overcast)=(4/4,0/4)=(1,0) (vector đơn vị)
V_outlook(Rain)=(3/5,2/5)=(0.6,0.4)
*Các thuộc tính khác được tính tương tự, kết quả như sau:
V_temp(Hot)=(2/4,2/4)=(0.5,0.5)
V_temp(Mild)=(4/6,2/6)=(2/3,1/3)
V_temp(Cool)=(3/4,1/4)
V_hum(High)=(3/7,4/7)
V_hum(Normal)=(6/7,1/7)
V_win(Weak)=(6/8,2/8)=(0.75,0.25)
V_win(Strong)=(3/6,3/6)=(0.5,.05)
Như vậy, thuộc tính Oulook có nhiều vector đơn vị nhất, nên sẽ được chọn để phân hoạch.
-Phân hoạch P_Sunny, tập dữ liệu chúng ta còn lại:
| Day | Temperature | Humidity | Wind | Play Tenis |
| 1 | Hot | High | Weak | No |
| 2 | Hot | High | Strong | No |
| 3 | Mild | High | Weak | No |
| 4 | Cool | Normal | Weak | Yes |
| 5 | Mild | Normal | Strong | Yes |
V_temp(Hot)=(2/2,0/2)=(1,0) (vector đơn vị)
V_temp(Mild)=(1/2,1/2)
V_temp(Cool)=(1/1,0/1) (vector đơn vị)
V_hum(High)=(0/3,3/3)=(0,1) (vector đơn vị)
V_hum(Normal)=(2/2,0/2)=(1,0) (vector đơn vị)
V_wind(Weak)=(1/3,2/3)
V_wind(Strong)
2 thuộc tính Temperature và Humidity cùng có 2 vector đơn vị. Ta chọn phân hoạch theo thuộc tính Humidity.
-Phân hoạch P_Rain, tập dữ liệu chúng ta còn lại:
| Day | Temperature | Humidity | Wind | Play Tenis |
| 1 | Mild | High | Weak | Yes |
| 2 | Cool | Normal | Weak | Yes |
| 3 | Cool | Normal | Strong | No |
| 4 | Mild | Normal | Weak | Yes |
| 5 | Mild | High | Strong | No |
V_temp(Mild)=(2/3,1/3)
V_temp(Cool)=(1/2,1/2)=(0.5,0.5)
V_hum(Hight)=(1/2,1/2)=(0.5,0.5)
V_hum(Normal)=(2/3,1/3)
V_wind(Weak)=(3/3,0/3)=(1,0) (vector đơn vị)
V_wind(Strong)=(0/2,2/2)=(0,1) (vector đơn vị)
Thuộc tính Wind có nhiều vector đơn vị nhất nên sẽ được chọn để phân hoạch.
Kết quả cây định danh cuối cùng:
Kết luận:
- if(Outlook=Rain and Wind=Weak) then KQ=Yes
- if(Outlook=Rain and Wind=Strong) then KQ=No
- if(Outlook=Overcast) then KQ=Yes
- if(Outlook=Sunny and Humidity=Normal) then KQ=Yes
- if(Outlook=Sunny and Humidity=High) then KQ=No
Vậy Day=15 (Outlook=Sunny and Humidity=High) =>KQ=No
Chúc bạn thành công!
