Áp dụng giải thuật ID3 vào bài toán dự đoán
Giải thuật ID3 là gì?
Giải thuật ID3 (thường được gọi tắt là ID3) được phát triển bởi Quinlan trong AI và Breiman, Friedman, Olsen và Stone trong thống kê. ID3 là một giải thuật học khá đơn giản nhưng lại đem lại rất nhiều thành công trong các lĩnh vực khác nhau.
ID3 là một giải thuật hay ho, Bizfly Cloud sẽ đưa ra các lý do sau đây:
- Cách biểu diễn tri thức học được của nó.
- Tiếp cận trong việc quản lý tính phức tạp
- Heuristic dùng cho việc chọn lựa các khái niệm ứng viên
- Tiềm năng đối với việc xử lý dữ liệu nhiễu.
ID3 biểu diễn các khái niệm (concept) ở dạng các cây quyết định (decision tree). Biểu diễn này cho phép xác định phân loại một đối tượng bằng cách kiểm tra các giá trị của nó trên một số thuộc tính nào đó.
Như vậy, nhiệm vụ của giải thuật ID3 là học cây quyết định từ một tập các ví dụ rèn luyện (training example) hay còn gọi là dữ liệu rèn luyện (training data).
- Input: Một tập hợp các ví dụ. Mỗi ví dụ bao gồm các thuộc tính mô tả một tình huống, hay một đối tượng nào đó, và một giá trị phân loại của nó.
- Output: Cây quyết định có khả năng phân loại đúng đắn các ví dụ trong tập dữ liệu rèn luyện, và hy vọng là phân loại đúng cho cả các ví dụ chưa gặp trong tương lai.
Giải thuật ID3 xây dựng cây quyết định
Lặp:
1. Chọn A <= thuộc tính quyết định "tốt nhất" cho nút kế tiếp.
2. Gán A là thuộc tính quyết định cho nút.
3. Với mỗi giá trị của A, tạo nhánh con mới của nút.
4. Phân loại các mẫu huấn luyện cho các nút lá.
5. Nếu các mẫu huấn luyện được phân loại hoàn toàn thì NGƯNG.
Ngược lại, lặp với các nút lá mới.
Thuộc tính tốt nhất ở đây là thuộc tính có entropy trung bình thấp nhất theo thuộc tính kết quả với Entropy được tính như sau:
Gọi S là tập các mẫu huấn luyện Gọi p là tỷ lệ các mẫu dương trong S Ta có H ≡ – p.log2p – (1 – p).log2(1 – p)
Entropy trung bình của một thuộc tính bằng trung bình theo tỉ lệ của entropy các nhánh:
Áp dụng giải thuật ID3 vào bài toán dự đoán
Sau đây là bài toán về sự dự đoán có chơi tennis hay không chơi tennis.
Lúc 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, Temperature, Humidity, Wind 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.
>> Có thể bạn quan tâm: Failover và Load Balancing - các khái niệm cơ bản
