Read more »
Các bước cơ bản của thuật toán ID3:
* Tính Entropy của tập dữ liệu gốc: Entropy là thước đo độ hỗn loạn hay không chắc chắn của dữ liệu. Nếu tất cả các mẫu trong tập dữ liệu đều thuộc cùng một lớp, entropy là 0 (không có sự hỗn loạn). Nếu các mẫu được phân bố đều giữa các lớp, entropy là cao nhất.
Công thức Entropy:
H(S) = - \sum_{i=1}^{c} p_i \log_2(p_i)
trong đó:
* S là tập dữ liệu.
* c là số lượng lớp mục tiêu.
* p_i là tỷ lệ số mẫu thuộc lớp i trong tập S.
* Tính Information Gain cho từng thuộc tính: Information Gain đo lường mức độ giảm entropy khi chia tập dữ liệu theo một thuộc tính cụ thể. Thuộc tính có Information Gain cao nhất được chọn làm node phân chia.
Công thức Information Gain:
IG(S, A) = H(S) - \sum_{v \in Values(A)} \frac{|S_v|}{|S|} H(S_v)
trong đó:
* IG(S, A) là Information Gain của thuộc tính A trên tập dữ liệu S.
* Values(A) là tập hợp các giá trị có thể có của thuộc tính A.
* S_v là tập con của S mà thuộc tính A có giá trị v.
* |S_v| là số lượng mẫu trong S_v.
* |S| là số lượng mẫu trong S.
* Chọn thuộc tính có Information Gain cao nhất: Thuộc tính này sẽ trở thành nút (node) trong cây quyết định.
* Tạo các nhánh con: Với mỗi giá trị có thể có của thuộc tính đã chọn, tạo một nhánh con và phân chia tập dữ liệu thành các tập con tương ứng.
* Lặp lại quá trình: Áp dụng đệ quy các bước trên cho từng tập con, cho đến khi:
* Tất cả các mẫu trong một tập con thuộc cùng một lớp (trở thành node lá).
* Không còn thuộc tính nào để phân chia.
* Không còn mẫu nào trong tập con.
Ví dụ với nội dung văn hóa Việt Nam:
Hãy tưởng tượng chúng ta muốn xây dựng một cây quyết định để dự đoán liệu một món ăn có được coi là "Món ăn truyền thống của Tết Nguyên Đán" ở Việt Nam hay không, dựa trên một số thuộc tính.
Tập dữ liệu ví dụ:
| Món ăn | Thành phần chính | Cách chế biến | Có cúng gia tiên | Phù hợp ăn nguội | Món ăn truyền thống Tết |
|---|---|---|---|---|---|
| Bánh Chưng | Nếp, thịt, đỗ | Hấp, luộc | Có | Có | Có |
| Giò Lụa | Thịt heo | Hấp | Có | Có | Có |
| Nem Rán | Thịt, miến, mộc nhĩ | Chiên | Có | Không | Có |
| Canh Măng | Măng khô, sườn | Nấu | Có | Không | Có |
| Gỏi Cuốn | Bánh tráng, tôm, thịt | Cuốn, tươi | Không | Có | Không |
| Phở | Bánh phở, thịt bò | Nấu | Không | Không | Không |
| Bún Chả | Thịt nướng, bún | Nướng, chấm | Không | Không | Không |
| Chè Trôi Nước | Bột nếp, đường | Luộc, ngọt | Có | Có | Có |
| Bánh Xèo | Bột gạo, tôm, thịt | Chiên | Không | Không | Không |
| Bánh Tét | Nếp, thịt, đỗ | Hấp, luộc | Có | Có | Có |
Mục tiêu: Dự đoán "Món ăn truyền thống Tết" (Có/Không)
Bước 1: Tính Entropy của tập dữ liệu gốc
* Tổng số mẫu: 10
* Số mẫu "Có" (Món ăn truyền thống Tết): 6
* Số mẫu "Không" (Món ăn truyền thống Tết): 4
* p_{Có} = 6/10 = 0.6
* p_{Không} = 4/10 = 0.4
* H(S) = -(0.6 \log_2 0.6 + 0.4 \log_2 0.4) \approx 0.971
Bước 2: Tính Information Gain cho từng thuộc tính
Hãy tính Information Gain cho thuộc tính "Có cúng gia tiên":
* Giá trị "Có":
* Các món ăn có "Có cúng gia tiên": Bánh Chưng, Giò Lụa, Nem Rán, Canh Măng, Chè Trôi Nước, Bánh Tét (6 mẫu)
* Trong 6 mẫu này, có 6 mẫu "Có" (Món ăn truyền thống Tết) và 0 mẫu "Không".
* H(S_{Có}) = -(1 \log_2 1 + 0 \log_2 0) = 0
* Giá trị "Không":
* Các món ăn có "Không cúng gia tiên": Gỏi Cuốn, Phở, Bún Chả, Bánh Xèo (4 mẫu)
* Trong 4 mẫu này, có 0 mẫu "Có" và 4 mẫu "Không".
* H(S_{Không}) = -(0 \log_2 0 + 1 \log_2 1) = 0
* IG(S, \text{Có cúng gia tiên}) = H(S) - \left( \frac{6}{10} H(S_{Có}) + \frac{4}{10} H(S_{Không}) \right)
IG(S, \text{Có cúng gia tiên}) = 0.971 - \left( \frac{6}{10} \times 0 + \frac{4}{10} \times 0 \right) = 0.971
Tương tự, bạn sẽ tính Information Gain cho các thuộc tính khác như "Thành phần chính", "Cách chế biến", "Phù hợp ăn nguội".
Bước 3: Chọn thuộc tính có Information Gain cao nhất
Trong trường hợp này, thuộc tính "Có cúng gia tiên" có Information Gain cao nhất (0.971), vì nó giúp phân loại hoàn toàn các mẫu thành hai nhóm rõ rệt. Do đó, "Có cúng gia tiên" sẽ được chọn làm node gốc.
Bước 4: Tạo các nhánh con và lặp lại
* Nhánh "Có cúng gia tiên" = "Có": Tất cả các mẫu ở nhánh này đều là "Món ăn truyền thống Tết" = "Có". Đây là một node lá.
* Nhánh "Có cúng gia tiên" = "Không": Tất cả các mẫu ở nhánh này đều là "Món ăn truyền thống Tết" = "Không". Đây cũng là một node lá.
Cây quyết định thu được:
Có cúng gia tiên?
/ \
Có Không
/ \
(Món ăn truyền thống Tết = Có) (Món ăn truyền thống Tết = Không)
Giải thích:
Trong ví dụ này, chỉ cần một thuộc tính "Có cúng gia tiên" đã đủ để phân loại hoàn toàn các món ăn thành "Món ăn truyền thống Tết" hay không. Điều này cho thấy thuộc tính này có tính phân tách rất cao đối với tập dữ liệu cụ thể này.
Lưu ý:
* Trong thực tế, các tập dữ liệu thường phức tạp hơn và có thể cần nhiều thuộc tính và các bước lặp lại để xây dựng cây.
* Thuật toán ID3 thường được sử dụng cho các thuộc tính phân loại (categorical attributes). Đối với các thuộc tính liên tục, cần có các phương pháp xử lý khác (ví dụ: chia thành các khoảng giá trị).
* ID3 có xu hướng ưu tiên các thuộc tính có nhiều giá trị, điều này có thể dẫn đến việc "quá khớp" (overfitting) với dữ liệu huấn luyện. Các thuật toán kế nhiệm như C4.5 ra đời để khắc phục nhược điểm này.
Hy vọng ví dụ này giúp bạn hiểu rõ hơn về cách hoạt động của cây quyết định ID3!
0 Reviews