Thuật toán Quinlan – Bài tập

0
7992

Một số ví dụ áp dụng giải thuật Quinlan:

Bài 1: 

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à :

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ẹ) = (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 :

Bài 2: Dựa vào bảng mô tả, hãy rút ra tập luật.

Giải

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

Thuộc tính: Vóc dáng

VV.Dáng (Nhỏ) = (T(Nhỏ,A),T(Nhỏ,B))

Số người vóc dáng nhỏ là : 3

Số người vóc dáng nhỏ và nhóm A là : 1

Số người vóc dáng nhỏ và nhóm B là: 2

Do đó

Vv.Dáng (Nhỏ) =(T(Nhỏ,A),T(Nhỏ,B))= (1/3,2/3)

Vv.Dáng (Lớn) =(T(Lớn,A),T(Lớn,B))=(2/5, 3/5) = (0,1)

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

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

Thuộc tính: Quốc tịch

VQ.Tịch (Đức) = (T(Đức,A),T(Đức,B)) =(2/4,2/4)

VQ.Tịch (Pháp) = (T(Pháp,A),T(Pháp,B)) = (1/1,0/1) = (1,0)

VQ.Tịch (Ý) = (T(Ý,A),T(Ý,B))= (0/3,3/3) = (0,1)

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

Thuộc tính: Gia cảnh

VG.Cảnh (Độc thân) = (T(Độc thân,A),T(Độc thân,B)) =(3/5,2/5)

VG.Cảnh(Có gia đình) = (T(Có gia đình,A),T(Có gia đình,B)) = (0/3,3/3) = (0,1)

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

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

Sau khi phân hoạch theo quốc tịch xong, chỉ có phân hoạch theo quốc tịch (PĐức) là còn chứa những người nhóm A và B 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 (vóc dáng, gia cảnh,nhóm). Trong phân hoạch PĐức, tập dữ liệu của chúng ta còn lại là :

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

Thuộc tính: Vóc dáng

Vv.Dáng (Nhỏ) =(T(Nhỏ,A),T(Nhỏ,B))= (1/2,1/2)

Vv.Dáng (Lớn) =(T(Lớn,A),T(Lớn,B))=(1/2,1/2)

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

Thuộc tính: Gia cảnh

VG.Cảnh (Độc thân) = (T(Độc thân,A),T(Độc thân,B)) =(2/2,0/2) = (1,0)

VG.Cảnh(Có gia đình) = (T(Có gia đình,A),T(Có gia đình,B)) = (0/2,2/2) = (0,1)

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

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

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

Vậy ta có tập luật:

IF Quốc tịch = Pháp THEN Nhóm = A;

IF Quốc tịch = Ý THEN Nhóm = B;

IF Quốc tịch = Đức AND Gia cảnh = Độc thân THEN Nhóm = A;

IF Quốc tịch = Đức AND Gia cảnh = Có gia đình THEN Nhóm = B;

Từ tập luật ta có thể suy ra:

Người có vóc dáng nhỏ,mang quốc tịch Pháp, có gia đình thì thuộc nhóm A

Hết

Chúc các bạn thành công!

Xem thêm: Áp dụng giải thuật ID3 vào bài toán dự đoán

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