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

 Học máy là hướng tiếp cận trong đó thay vì con người phải chỉ ra những tri thức cần thiết để giải quyết bài toán, máy tính sẽ tự động rút trích tri thức này một cách từ những dữ liệu được cung cấp. Học máy mô phỏng quá trình học của con người qua các mức từ đơn giản đến phức tạp: đầu tiên máy tính ghi nhớ những trường hợp đã xuất hiện và cuối cùng học những trường hợp tổng quát chưa từng xuất hiện.

 Trong một bài toán học máy, đầu vào là một tập dữ liệu huấn luyện bao gồm các mẫu dữ liệu. Mỗi mẫu dữ liệu bao gồm một tập giá trị ứng với các thuộc tính. Tập thuộc tính được chia làm hai phần: thuộc tính quan sát và thuộc tính kết quả. Mục tiêu của học máy là tìm một ánh xạ từ thuộc tính quan sát vào thuộc tính kết quả (tìm mối quan hệ giữa thuộc tính quan sát và thuộc tính kết quả) ứng với tập dữ liệu huấn luyện. Ánh xạ này sẽ được áp dụng lên những mẫu quan sát mới để rút ra kết quả tương ứng.

 Bảng dưới đây trình bày một ví dụ của học máy, bài toán dự đoán việc có chơi tennis hay không.

         Trong bài toán này, học máy sẽ tìm một mối quan hệ giữa các thuộc tính quan sát: Outlook (quang cảnh), Temperature (Nhiệt độ), Humidity (Độ ẩm), Wind (Sức gió) với thuộc tính kết quả Target. Kết quả này sẽ dùng dự đoán giá trị Target khi nhập vào thuộc tính quan sát cho các mẫu mới ví dụ:

 Việc dự đoán cho mẫu 15 có thể tương đối dễ dàng, vì mẫu này có các giá trị quan sát tương tự mẫu số 11 nên giá trị Target cũng tương tự là Yes (trường hợp học máy đơn giản – ghi nhớ). Tuy nhiên việc dự đoán cho mẫu 16 sẽ khó khăn hơn vì mẫu này không giống bất kỳ một trong những mẫu đã biết. Đây là trường hợp tổng quát của học máy – gặp những trường hợp chưa từng xuất hiện. Các phương pháp học máy đưa ra nhằm giải quyết bài toán trong trường hợp tổng quát.

Áp dụng thuật toán ID3 cho bài toán học chơi tennis:

Lặp lần 1: Xét lần lượt các thuộc tính

Tính AE

So sánh ta thấy thuộc tính Outlook có entropy trung bình thấp nhất nên chọn thuộc tính này làm nút gốc.

Lặp lần 2: xét nhánh Rain

AE (Rain, Temperature) = 2/5*1 + 3/5*.918 = 0.951
AE (Rain, Humidity) = 2/5*1 + 3/5*.918 = 0.951
AE (Rain, Wind) = 2/5*0 + 3/5*0 = 0

Thuộc tính Wind có entropy trung bình thấp nhất nên chọn làm nút nhánh

Lặp lần 3: xét nhánh Sunny

AE (Sunny, Temperature) = 2/5*0 + 2/5*1 + 1/5*0= 0.4
AE (Sunny, Humidity) = 2/5*0 + 3/5*0 = 0
AE (Sunny, Wind) = 2/5*1 + 3/5*.918 = 0.951

Thuộc tính Humidity có entropy trung bình thấp nhất nên chọn làm nút nhánh

Ta có Cây quyết định kết quả

Sau khi xây dựng cây, ta có thể rút ra các luật tương ứng bằng cách duyệt các đường đi trên cây từ nút gốc đến nút lá, mỗi đường đi ứng với một luật:

IF Outlook = Overcast THEN Yes
• IF Outlook = Rain AND Wind=Weak THEN Yes
• IF Outlook = Rain AND Wind=Strong THEN No
• IF Outlook = Sunny AND Humidity=Normal THEN Yes
• IF Outlook = Sunny AND Humidity=High THEN No

Vậy mẫu số 16 sẽ có kết quả là No

Có thể bạn quan tâm: Ví dụ về thuật toán Quinlan