Ví dụ về thuật toán Quinlan

0
3409

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!

This site uses Akismet to reduce spam. Learn how your comment data is processed.