Decision tree - split, impurity và pruning

Giới thiệu

Bài này học cây quyết định hỏi dần rồi đoán nhãn. Cây này giúp vừa đoán vừa giải thích được luật.

Kiến thức cần nhớ

Cây hỏi dần

• Nút trong là câu hỏi cắt trên một đặc trưng.
• Nhánh là đáp án của câu hỏi đó.
• Lá là nhãn dự đoán cuối cùng.
• Ví dụ đời thường: hỏi sốt không, ho không rồi kết luận bệnh.

Độ tạp và điểm cắt

• Độ tạp đo mức lẫn lộn nhãn trong một nút.
• Nút một màu thì tạp 0, nửa nọ nửa kia thì tạp max.
• Cắt tốt là cắt tách cừu khỏi dê gọn nhất.
• Ví dụ đời thường: nhát cắt tách bi đỏ khỏi bi xanh sạch nhất.

Mạnh yếu và cắt tỉa

• Mạnh: đọc được luật, khỏi scaling, bắt quan hệ cong.
• Yếu: dễ học thuộc lòng, nhạy nhiễu, ranh giới bậc thang.
• Cắt tỉa: mọc đầy rồi cắt ngược nhánh vô ích.
• Ví dụ đời thường: tỉa cành sâu để cây khỏe hơn.

# Dự đoán cây: thả từ gốc tới lá
def doan(nut, x):
    while not nut.la:  # chưa tới lá
        if x[nut.dac_trung] <= nut.nguong:  # hỏi cắt
            nut = nut.trai  # rẽ trái
        else:
            nut = nut.phai  # rẽ phải
    return nut.nhan  # tới lá lấy nhãn

Ví dụ

• Input: dữ liệu tách thẳng hoàn hảo, cây sâu 1 -> Output: đúng 100% train và test.
• Câu này cho thấy bài dễ thì cây nông đã thắng.
• Input: nút nửa nọ nửa kia 2 lớp -> Output: Gini bằng 0.5.
• Câu này kiểm tra công thức tạp ở biên lẫn nhất.

💻 Bài tập

Ngôn ngữ: Python 3 với NumPy. Không dùng sklearn.tree trừ khi đối chiếu. Nộp vào day-053/.

Bài 1: Độ tạp và điểm cắt

gini([0,0,1,1]) -> 0.5; gini([1,1,1]) -> 0
entropy([0,0,1,1]) -> 1.0
X = [[1],[2],[8],[9]], y = [0,0,1,1] -> cắt cột 0 tại 5.0, gain = 0.5

Bài 2: Cây quyết định

class DecisionTree:
    def __init__(self, max_depth=None, min_samples_split=2, criterion="gini"): ...
    def fit(self, X, y): ...
    def predict(self, X): ...
    def depth(self) -> int: ...
    def print_rules(self, feature_names): ...   # in dạng "nếu petal_length <= 2.45 thì setosa"

Chạy trên bộ Iris. Chia 70/30. In accuracy train và test với max_depth = 1, 2, 3, 5, None.

Bài 3: Học thuộc và cắt tỉa (nâng cao)

1. Thêm 20% nhãn nhiễu vào tập train Iris. Cây không giới hạn độ sâu: in accuracy train và test.
2. Cài reduced-error pruning: từ dưới lên, thay nút bằng lá nếu accuracy trên tập validation không giảm.
3. In độ sâu, số lá, accuracy test trước và sau cắt tỉa.
4. So với sklearn.tree.DecisionTreeClassifier cùng tham số.

✅ Tiêu chí hoàn thành

• Test mẫu pass.
• Bảng accuracy theo max_depth có số thật.
• Cắt tỉa giảm số lá và không giảm accuracy test đáng kể.
• print_rules in được luật đọc hiểu được.

❓ Câu hỏi ôn tập

• Nút, nhánh, lá trong cây là gì?
• Độ tạp cao nghĩa là lẫn thế nào?
• Cắt tỉa chống overfitting ra sao?
• Khi nào nên dùng cây quyết định?

🌕 Bạn đã hoàn thành ngày 53. Làm hết bài tập phía trên rồi sang ngày tiếp theo.