1605539161.jpg

THUÂT TOÁN QUINLAN.

Người đăng: Nguyễn Hoàng Anh Ngày đăng: 16-02-2021 571 lượt xem

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à r)  /  (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 V(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 :

Bảng cơ sở dữ liệu
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 Không
3 Nâu Thấp Trung bình 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 :

Bảng CSDL phân hoach theo tóc = "vàng"
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 Không
4 Thấp Trung bình Không Cháy
8 Thâp Nhẹ 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ài viết liên quan

Bình luận bài viết