Topic hoc cay quyet dinh ID3, vi du quyet dinh an toan khi tham gia giao thong

Cây quyết định ID3 (Iterative Dichotomiser 3) là một thuật toán học máy được sử dụng để tạo ra một cây quyết định từ một tập hợp dữ liệu. Mục tiêu của cây quyết định là dự đoán giá trị của một biến mục tiêu (target variable) dựa trên các giá trị của các biến đầu vào (input variables).

Cách hoạt động của ID3

Thuật toán ID3 hoạt động dựa trên nguyên tắc entropy và information gain.

* Entropy: Đo lường mức độ không chắc chắn hoặc ngẫu nhiên của một tập hợp dữ liệu. Entropy càng cao, dữ liệu càng ngẫu nhiên và khó dự đoán. Công thức tính entropy của một tập hợp S với c lớp (categories) là:

H(S) = -\sum_{i=1}^{c} p_i \log_2(p_i)

Trong đó, p_i là tỷ lệ số lượng mẫu thuộc lớp i trong tập S.

* Information Gain (Độ lợi thông tin): Đo lường mức độ giảm entropy khi chúng ta chia tập dữ liệu dựa trên một thuộc tính (attribute) cụ thể. Thuộc tính nào có độ lợi thông tin cao nhất sẽ được chọn làm nút gốc (root node) hoặc nút bên trong (internal node) của cây. Công thức tính information gain khi chia tập S theo thuộc tính A là:

IG(S, A) = H(S) - \sum_{v \in Values(A)} \frac{|S_v|}{|S|} H(S_v)

Trong đó, Values(A) là tập hợp các giá trị của thuộc tính A, S_v là tập hợp con của S mà thuộc tính A có giá trị v, và |S_v|, |S| là số lượng phần tử trong S_v và S tương ứng.

Các bước của thuật toán ID3:

* Tính Entropy ban đầu của tập dữ liệu.

* Với mỗi thuộc tính, tính toán Information Gain nếu chia tập dữ liệu dựa trên thuộc tính đó.

* Chọn thuộc tính có Information Gain cao nhất làm nút của cây.

* Tạo các nhánh cho mỗi giá trị có thể có của thuộc tính đã chọn.

* Lặp lại quy trình cho từng nhánh con với tập dữ liệu tương ứng, cho đến khi:

* Tất cả các mẫu trong một nhánh thuộc cùng một lớp (pure node).

* Không còn thuộc tính nào để chia.

* Không còn mẫu nào trong một nhánh.

Ví dụ về cây quyết định ID3: Quyết định an toàn khi tham gia giao thông

Giả sử chúng ta có một tập dữ liệu nhỏ về các tình huống tham gia giao thông và kết quả là an toàn hay không an toàn.

|---|---|---|---|

| Tốt | Trung bình | Có | An toàn |

| Tốt | Nhanh | Có | Không an toàn |

| Tốt | Chậm | Có | An toàn |

| Xấu | Chậm | Có | An toàn |

Mục tiêu: Xây dựng cây quyết định để dự đoán "Kết quả" (An toàn/Không an toàn).

Bước 1: Tính Entropy ban đầu của "Kết quả"

Trong 8 mẫu dữ liệu, có 5 mẫu "An toàn" và 3 mẫu "Không an toàn".

p(\text{An toàn}) = \frac{5}{8}

p(\text{Không an toàn}) = \frac{3}{8}

H(\text{Kết quả}) = -(\frac{5}{8} \log_2(\frac{5}{8}) + \frac{3}{8} \log_2(\frac{3}{8}))

H(\text{Kết quả}) \approx -(0.625 \times -0.678 + 0.375 \times -1.415)

H(\text{Kết quả}) \approx -(-0.423 - 0.530) \approx 0.953

Bước 2: Tính Information Gain cho từng thuộc tính

a. Information Gain cho "Thời tiết"

* Thời tiết = Tốt (5 mẫu): 4 An toàn, 1 Không an toàn

H(\text{Kết quả} | \text{Thời tiết = Tốt}) = -(\frac{4}{5} \log_2(\frac{4}{5}) + \frac{1}{5} \log_2(\frac{1}{5})) \approx 0.722

* Thời tiết = Xấu (3 mẫu): 1 An toàn, 2 Không an toàn

H(\text{Kết quả} | \text{Thời tiết = Xấu}) = -(\frac{1}{3} \log_2(\frac{1}{3}) + \frac{2}{3} \log_2(\frac{2}{3})) \approx 0.918

IG(\text{Kết quả}, \text{Thời tiết}) = H(\text{Kết quả}) - (\frac{5}{8} H(\text{Kết quả} | \text{Thời tiết = Tốt}) + \frac{3}{8} H(\text{Kết quả} | \text{Thời tiết = Xấu}))

IG(\text{Kết quả}, \text{Thời tiết}) = 0.953 - (\frac{5}{8} \times 0.722 + \frac{3}{8} \times 0.918)

IG(\text{Kết quả}, \text{Thời tiết}) = 0.953 - (0.451 + 0.344) = 0.953 - 0.795 = 0.158

b. Information Gain cho "Tốc độ"

* Tốc độ = Trung bình (3 mẫu): 3 An toàn, 0 Không an toàn

H(\text{Kết quả} | \text{Tốc độ = Trung bình}) = 0 (hoàn toàn thuần khiết)

* Tốc độ = Nhanh (3 mẫu): 0 An toàn, 3 Không an toàn

H(\text{Kết quả} | \text{Tốc độ = Nhanh}) = 0 (hoàn toàn thuần khiết)

* Tốc độ = Chậm (2 mẫu): 2 An toàn, 0 Không an toàn

H(\text{Kết quả} | \text{Tốc độ = Chậm}) = 0 (hoàn toàn thuần khiết)

IG(\text{Kết quả}, \text{Tốc độ}) = H(\text{Kết quả}) - (\frac{3}{8} \times 0 + \frac{3}{8} \times 0 + \frac{2}{8} \times 0)

IG(\text{Kết quả}, \text{Tốc độ}) = 0.953 - 0 = 0.953

c. Information Gain cho "Kinh nghiệm"

* Kinh nghiệm = Có (5 mẫu): 4 An toàn, 1 Không an toàn

H(\text{Kết quả} | \text{Kinh nghiệm = Có}) = -(\frac{4}{5} \log_2(\frac{4}{5}) + \frac{1}{5} \log_2(\frac{1}{5})) \approx 0.722

* Kinh nghiệm = Không (3 mẫu): 1 An toàn, 2 Không an toàn

H(\text{Kết quả} | \text{Kinh nghiệm = Không}) = -(\frac{1}{3} \log_2(\frac{1}{3}) + \frac{2}{3} \log_2(\frac{2}{3})) \approx 0.918

IG(\text{Kết quả}, \text{Kinh nghiệm}) = H(\text{Kết quả}) - (\frac{5}{8} H(\text{Kết quả} | \text{Kinh nghiệm = Có}) + \frac{3}{8} H(\text{Kết quả} | \text{Kinh nghiệm = Không}))

IG(\text{Kết quả}, \text{Kinh nghiệm}) = 0.953 - (\frac{5}{8} \times 0.722 + \frac{3}{8} \times 0.918)

IG(\text{Kết quả}, \text{Kinh nghiệm}) = 0.953 - (0.451 + 0.344) = 0.953 - 0.795 = 0.158

Bước 3: Chọn thuộc tính có Information Gain cao nhất

Trong trường hợp này, "Tốc độ" có Information Gain cao nhất (0.953). Do đó, "Tốc độ" sẽ là nút gốc của cây quyết định.

Bước 4: Tạo các nhánh và lặp lại

* Nếu Tốc độ = Trung bình: Tất cả các mẫu đều "An toàn". Nhánh này kết thúc.

* Nếu Tốc độ = Nhanh: Tất cả các mẫu đều "Không an toàn". Nhánh này kết thúc.

* Nếu Tốc độ = Chậm: Tất cả các mẫu đều "An toàn". Nhánh này kết thúc.

Cây quyết định hoàn chỉnh:

Tốc độ

/ | \

Trung bình Nhanh Chậm

| | |

An toàn Không an toàn An toàn

Ưu và nhược điểm của ID3

Ưu điểm:

* Dễ hiểu và giải thích: Cây quyết định có cấu trúc trực quan, dễ dàng hình dung và giải thích cho người không chuyên về kỹ thuật.

* Không yêu cầu chuẩn hóa dữ liệu: ID3 không yêu cầu các thuộc tính phải được chuẩn hóa hoặc xử lý trước.

* Xử lý được dữ liệu định tính: Thuật toán này rất phù hợp với các thuộc tính phân loại (categorical attributes).

Nhược điểm:

* Thiên vị các thuộc tính có nhiều giá trị: ID3 có xu hướng chọn các thuộc tính có nhiều giá trị riêng biệt, ngay cả khi chúng không thực sự mang lại nhiều thông tin.

* Không xử lý tốt dữ liệu số: ID3 cần dữ liệu định tính, do đó dữ liệu số cần được rời rạc hóa (discretized) trước khi sử dụng, điều này có thể làm mất thông tin.

* Dễ bị quá khớp (overfitting): Nếu cây quá sâu, nó có thể học quá chi tiết các nhiễu trong dữ liệu huấn luyện và hoạt động kém trên dữ liệu mới.

* Không ổn định: Một thay đổi nhỏ trong dữ liệu có thể dẫn đến một cây quyết định hoàn toàn khác.

* Chỉ xây dựng cây đơn lẻ: ID3 không sử dụng kỹ thuật ensemble (như Random Forest, Gradient Boosting) để cải thiện hiệu suất.

Tổng kết

Thuật toán ID3 là một khởi đầu tuyệt vời để hiểu về cây quyết định và cách chúng hoạt động dựa trên các khái niệm entropy và information gain. Mặc dù có một số hạn chế, nhưng nó đặt nền móng cho nhiều thuật toán cây quyết định phức tạp hơn như C4.5 và CART, vốn đã khắc phục được một số nhược điểm của ID3.

Bạn có muốn tìm hiểu sâu hơn về cách giải quyết các nhược điểm của ID3, ví dụ như với thuật toán C4.5 không?