Thuật toán Quinlan: Là thuật toán học theo quy nạp dùng luật, đa mục tiêu.  Nó được phát triển bởi John Ross Quinlan – nhà khoa học máy tính – đưa ra năm 1979 với ý tưởng: chọn thuộc tính quan trọng nhất để tạo cây quyết định. Thuộc tính quan trọng nhất là thuộc tính phân loại bảng quan sát thành các bảng con sao cho từ mỗi bảng con này dễ phân tích để tìm quy luật chung.

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.

Cách tính vectơ đặc trư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à jcó 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

——————————-^_^ Hoang mang quá, chưa hiểu gì cả..hiuhiu——————————-

Những lời ở trên đó là mình lấy từ slide bài giảng môn Trí tuệ nhân tạo mà ra đó. Mới đầu mình đọc, mình không hiểu ý nó nói gì cả. Lúc ấy trong đầu mình hiện ra ngàn câu nói ( hơi quá ..hihi) ‘ Làm ơn dịch sang ngôn ngữ trái đất đê, viết gì mà chả hiểu như thế này … -_-‘ . Nhưng cũng nhờ thông qua các bài tập ví dụ để mô tả về thuật toán Quinlan mà mình cũng có thể hiểu được ý tưởng của thuật toán này rồi.. ohyeah…

Dưới đây là một số ví dụ về bài tập Quilan để mọi người có thể dễ hiểu hơn về nó..

Bài 1:

q1

Giải

Vector đặc trưng cho các thuộc tính:

Thuộc tính: Màu tóc

VTóc (vàng) = ( T(vàng, cháy nắng), T(vàng, không cháy nắng))

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

Do đó:

VTóc(vàng) = (2/4 , 2/4) = (0.5, 0.5)

VTóc(nâu) = ( T(nâu, cháy nắng), T(nâu, không cháy nắng)) = (0/3, 3/3) = (0,1)

VTóc(đỏ) = (T(đỏ, cháy nắng), T(đỏ, không cháy nắng)) = (1/1, 0/1) = (1,0)

=> Tổng số vector đơn vị của thuộc tính màu tóc là 2.

Các thuộc tính khác được tính tương tự, kết quả như sau :

Thuộc tính: Chiều cao

VC.Cao(Cao) = ( T(cao, cháy nắng), T(cao, không cháy nắng) ) = (0/2,2/2) = (0,1)

VC.Cao(T.B) =( T(T.B, cháy nắng), T(T.B, không cháy nắng) ) = (2/3,1/3)

VC.Cao(Thấp) = ( T(Thấp, cháy nắng), T(Thấp, không cháy nắng) ) = (1/3,2/3)

=> Tổng số vector đơn vị của thuộc tính chiều cao là 1

Thuộc tính: Cân nặng

VC.Nặng (Nhẹ) = (T(Nhẹ,cháy nắng),T(Nhẹ không cháy nắng))=(1/2,1/2)

VC.Nặng (T.B) = (T(T.B,cháy nắng),T(T.B không cháy nắng))=(1/3,2/3)

VC.Nặng (Nặng) =(T(Nặng,cháy nắng),T(Nặng, không cháy nắng))= (1/3,2/3)

          => Tổng số vector đơn vị của thuộc tính cân nặng là 0

Thuộc tính: Dùng kem

VKem (Có) = (T(Có,cháy nắng),T(Có, không cháy nắng))=(3/3,0/3) = (1,0)

VKem (Không) = (T(Không,cháy nắng),T(Không, không cháy nắng))=(3/5,2/5)

          => Tổng số vector đơn vị của thuộc tính dùng kem là 1

Như vậy thuộc tính màu tóc có số vector đơn vị nhiều nhất nên sẽ được chọn để phân hoạch.

Sau khi phân hoạch theo màu tóc xong, chỉ có phân hoạch theo tóc vàng (Pvàng) là còn chứa những người cháy nắng và không cháy nắng nên ta sẽ tiếp tục phân hoạch tập này. Ta sẽ thực hiện thao tác tính vector đặc trưng tương tự đối với các thuộc tính còn lại (chiều cao, cân nặng, dùng kem). Trong phân hoạch Pvàng, tập dữ liệu của chúng ta còn lại là :

kq_1_1.PNG

Thuộc tính :Chiều cao

VC.Cao(Cao) = (T(cao,cháy nắng),T(cao, không cháy nắng))=(0/1,1/1) = (0,1)

VC.Cao(T.B) =(T(T.B,cháy nắng),T(T.B, không cháy nắng))= (1/1,0/1) = (1,0)

VC.Cao(Thấp) = (T(Thấp,cháy nắng),T(Thấp, không cháy nắng))=(1/2,1/2)     

 => Tổng số vector đơn vị của thuộc tính chiều cao là 2

Thuộc tính :Cân nặng

VC.Nặng (Nhẹ) = (1/2,1/2)

VC.Nặng (T.B) = (1/2,1/2)

VC.Nặng (Nặng) = (0,0)

VC.Nặng (Nhẹ) = (T(Nhẹ,cháy nắng),T(Nhẹ không cháy nắng))=(1/2,1/2)

VC.Nặng (T.B) = (T(T.B,cháy nắng),T(T.B không cháy nắng))=(1/2,1/2)

VC.Nặng (Nặng) =(T(Nặng,cháy nắng),T(Nặng, không cháy nắng))= (0,0)

          => Tổng số vector đơn vị của thuộc tính cân nặng là 0

Thuộc tính :Dùng kem

VKem (Có) = (T(Có,cháy nắng),T(Có, không cháy nắng))=(0/2,2/2) = (0,1)

VKem (Không) = (T(Không,cháy nắng),T(Không, không cháy nắng))=(2/2,0/2) = (1,0)

          => Tổng số vector đơn vị của thuộc tính dùng kem là 2

2 thuộc tính dùng kem và chiều cao đều có 2 vector đơn vị.

Ta chọn phân hoạch theo thuộc tính dùng kem (vì ta thấy chỉ có thuộc tính dùng kem là không còn phân hoạch những người cháy nắng và không cháy nắng )

Kết luận: Kết quả Cây định danh cuối cùng :

kq1_2.PNG

Như vậy từ cây định danh ta đưa ra tập luật như sau:

IF(màu tóc = nâu) THEN kết quả= không cháy nắng;

IF(màu tóc = đỏ) THEN kết quả= có cháy nắng;

IF(màu tóc = vàng AND dùng kem = có) THEN kết quả = không cháy nắng;

IF( màu tóc = vàng AND dùng kem = không ) THEN kết quả = cháy nắng.

Kết thúc giải thuật

NGUYỄN THỊ YẾN NHI

nguyennhipuka@gmail.com

Advertisements