Decision tree

Cấu trúc

Mỗi nút trong hỏi một câu dạng $x_j \le t$ (“tuổi $\le 30$?”, “số lần đăng nhập $\le 2$?”). Trả lời có thì đi nhánh trái, không thì đi nhánh phải. Đi từ nút gốc xuống tới nút lá, nơi không còn câu hỏi nào. Mỗi lá chứa một dự đoán: lớp chiếm đa số (phân loại) hoặc giá trị trung bình (hồi quy) của các mẫu train rơi vào lá đó.

Về hình học, cây chia không gian đặc trưng thành các hộp chữ nhật có cạnh song song với trục, mỗi hộp một dự đoán.

Thế nào là một câu hỏi tốt

Câu hỏi tốt tạo ra các nhóm con thuần (pure): gần như toàn một lớp. Độ “lẫn lộn” của một nút với tỉ lệ các lớp $p_1, \dots, p_K$ được đo bằng

Cả hai bằng 0 khi nút thuần và lớn nhất khi các lớp chia đều. Gini là xác suất đoán sai nếu gán nhãn ngẫu nhiên theo đúng tỉ lệ trong nút; entropy là lượng thông tin, tính bằng bit, cần để biết nhãn. Trong thực tế hai cách cho cây gần như giống nhau; Gini tính nhanh hơn vì không có log.

Ví dụ:

• Nút có 4 mẫu “Đạt”, 2 mẫu “Trượt”: entropy là $-\tfrac46\log_2\tfrac46 - \tfrac26\log_2\tfrac26 \approx 0.92$ bit. (Dùng log tự nhiên thì ra $0.64$, sai đơn vị.)
• Ba lớp với số mẫu 6, 2, 2: Gini $= 1 - 0.6^2 - 0.2^2 - 0.2^2 = 0.56$.

Một phép chia đưa nút cha có $n$ mẫu thành hai con $n_L$ và $n_R$ mẫu. Độ giảm tạp chất (impurity decrease) của phép chia là

Với entropy, $\Delta$ được gọi là information gain. Với hồi quy, thay $I$ bằng phương sai của $y$ trong nút: chia tốt là chia sao cho mỗi bên có $y$ đồng đều.

Giờ dùng Gini để so hai cách chia. Nút cha có 5 mẫu dương và 5 mẫu âm, nên $\text{Gini} = 1 - 0.5^2 - 0.5^2 = 0.5$:

Cách B tạo được một nút hoàn toàn thuần, trông hấp dẫn, nhưng nút đó chỉ có 2 mẫu và nút còn lại vẫn rất lộn xộn. Cách A tốt hơn. Dùng entropy cũng ra cùng kết luận: gain của A là 0.278, của B là 0.236.

Huấn luyện: tham lam từng bước

Tìm cây tối ưu toàn cục là bài toán NP-khó. Thuật toán CART dùng chiến lược tham lam: ở mỗi nút, thử mọi đặc trưng và mọi ngưỡng, chọn phép chia có $\Delta$ lớn nhất, rồi đệ quy xuống hai con.

Với một đặc trưng, sắp các mẫu theo giá trị rồi chỉ cần thử ngưỡng nằm giữa hai giá trị liên tiếp. Duyệt từ trái sang phải và cập nhật số đếm từng lớp bằng tiền tố, mỗi ngưỡng tính trong $O(1)$. Tổng chi phí cho một nút là $O(d\, n \log n)$, chủ yếu do sắp xếp. Histogram gradient boosting (bài 2.7) gom giá trị vào khoảng 256 thùng để chỉ phải thử vài trăm ngưỡng; DecisionTreeClassifier thông thường thì thử mọi ngưỡng giữa các giá trị khác nhau.

Khi nào dừng

Khi không có hồ sơ đặc trưng trùng nhau mang nhãn mâu thuẫn và không có ràng buộc dừng, cây có thể mọc tới các lá thuần, lỗi train bằng 0, và cây thuộc lòng cả nhiễu. Các cách hãm:

• max_depth: giới hạn độ sâu.
• min_samples_leaf: mỗi lá phải có ít nhất bấy nhiêu mẫu. Thường là tham số hiệu quả nhất. Nó chặn luôn số lá: 100 mẫu với min_samples_leaf=20 thì cây có nhiều nhất 5 lá.
• min_impurity_decrease: không chia nếu lợi ích quá nhỏ.
• Cắt tỉa (pruning): mọc cây đầy đủ rồi cắt bớt nhánh. Cost-complexity pruning cực tiểu $\text{lỗi} + \alpha \cdot (\text{số lá})$, cũng là kiểu “lỗi + phạt” quen thuộc ở bài 2.2.

Điểm mạnh, điểm yếu

Mạnh

• Không cần chuẩn hóa đặc trưng: câu hỏi $x_j \le t$ không quan tâm đơn vị đo. Đổi đơn vị hay lấy log một cột chỉ dời ngưỡng, vì thứ tự các giá trị giữ nguyên; cách chia các mẫu không đổi.
• Tự bắt được quan hệ phi tuyến và tương tác giữa các đặc trưng.
• Đọc được như một bộ luật; dễ giải thích cho người không học máy.

Yếu

• Variance rất cao: đổi vài mẫu train là cây có thể khác hẳn từ gốc.
• Ranh giới chỉ gồm các đoạn song song với trục; một đường chéo đơn giản phải xấp xỉ bằng hình bậc thang. Biết trước ranh giới là $x_1 = x_2$ thì thêm cột $x_1 - x_2$, một câu hỏi là đủ.
• Dự đoán là hằng số từng khúc, nên không ngoại suy: giá trị vượt quá vùng train vẫn chỉ nhận giá trị của lá ngoài cùng.

Chính điểm yếu thứ nhất là lý do người ta ít dùng một cây đơn lẻ, mà gộp nhiều cây lại ở bài 2.6 và 2.7.

Độ quan trọng đặc trưng

Muốn biết đặc trưng nào quan trọng, có hai cách:

• Impurity importance: cộng dồn $\Delta$ (có trọng số theo số mẫu) của mọi phép chia dùng đặc trưng $j$. Cách này nhanh nhưng thiên vị các đặc trưng có nhiều giá trị khác nhau, như ID hay số thực. Cực đoan nhất là cột mã học sinh, mỗi mẫu một giá trị: chia theo nó cho toàn lá thuần, information gain tối đa mà chẳng học được gì. (Thuật toán C4.5 chia gain cho entropy của chính phép chia, gọi là gain ratio, để hãm chuyện này.)
• Permutation importance: xáo trộn cột $j$ trên tập validation rồi đo điểm giảm bao nhiêu. Cách này đáng tin hơn.

Cài một nút trước khi cài cả cây

Ta bắt đầu nhỏ hơn CART đầy đủ: chỉ một đặc trưng, một phép chia, gọi là decision stump. Bốn điểm có tọa độ 1, 2, 3, 4 và nhãn 0, 0, 1, 1. Nút gốc có hai lớp ngang nhau nên Gini bằng $1-(1/2)^2-(1/2)^2=0.5$. Chia ở 2.5 tạo hai lá thuần, Gini sau chia bằng 0; mức giảm là 0.5.

Điểm đáng chú ý là Gini sau chia phải lấy trung bình có trọng số số mẫu. Một lá có 1 mẫu và một lá có 99 mẫu không thể có tiếng nói ngang nhau. Ta chỉ xét ngưỡng giữa hai giá trị liên tiếp khác nhau: trong khoảng đó không điểm nào đổi bên nên xét thêm cũng vô ích.

import numpy as np

def gini(labels):
    counts = np.bincount(labels, minlength=2)
    probabilities = counts / len(labels)
    return 1.0 - np.sum(probabilities ** 2)

x_small = np.array([1., 2., 3., 4.])
y_small = np.array([0, 0, 1, 1])
best = None
for threshold in [1.5, 2.5, 3.5]:
    left = x_small <= threshold
    right = ~left
    after = left.mean() * gini(y_small[left]) + right.mean() * gini(y_small[right])
    gain = gini(y_small) - after
    print(threshold, round(float(gain), 3))
    if best is None or gain > best[0]:
        best = (gain, threshold)
print("ngưỡng:", best[1])
assert best[1] == 2.5

Kết quả1.5 0.167
2.5 0.5
3.5 0.167
ngưỡng: 2.5

Đọc cột gain: ngưỡng 2.5 thắng hai ngưỡng còn lại, dù cả ba đều chia được dữ liệu thành hai phần. Cài cả cây là lặp lại việc này cho từng nút bằng đệ quy, dừng khi lá đủ thuần, quá ít mẫu hoặc đạt độ sâu. Khi nhiều phép chia hòa gain, cần quy tắc phá hòa. Bản nhỏ trên giữ ngưỡng gặp trước; thư viện có quy tắc và ngẫu nhiên riêng nên không được đòi mọi cây giống hệt nhau.

Vì sao tham lam có giới hạn

Decision tree tìm phép chia tốt nhất ngay ở nút hiện tại, không thử mọi cây tương lai. Một ví dụ là XOR: hai bit đầu vào 00, 01, 10, 11 có nhãn 0, 1, 1, 0. Chia theo bit nào ở gốc cũng có gain 0, nhưng chia thêm ở tầng sau thì phân loại được hết. Nếu đặt điều kiện chỉ chia khi gain dương rõ rệt, cây có thể bỏ lỡ tương tác này. Câu “cây tự học mọi tương tác” vì vậy cần hiểu là khả năng biểu diễn, chưa bảo đảm thuật toán tham lam sẽ tìm ra.

Đối với hồi quy, một lá dự đoán trung bình nhãn các mẫu train rơi vào lá đó. Dự đoán luôn ở trong khoảng các nhãn lá, nên đưa $x$ ra xa vùng train cũng chỉ nhận cùng một giá trị ở lá ngoài cùng. Đây là lý do cây không kéo dài xu hướng như linear regression. Nếu bài có giá trị tương lai vượt xa lịch sử, hãy kiểm ngoại suy trên validation có cấu trúc tương tự, thay vì chỉ random split.

Dùng thư viện

from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import cross_val_score
from sklearn.tree import DecisionTreeClassifier, export_text

X, y = load_breast_cancer(return_X_y=True)
for depth in [1, 3, 5, None]:
    tree = DecisionTreeClassifier(max_depth=depth, random_state=0)
    print(depth, round(cross_val_score(tree, X, y, cv=5).mean(), 3))

tree = DecisionTreeClassifier(max_depth=2, random_state=0).fit(X, y)
print(export_text(tree, feature_names=list(load_breast_cancer().feature_names)))

Kết quả1 0.9
3 0.917
5 0.916
None 0.917
|--- worst radius <= 16.80
|   |--- worst concave points <= 0.14
|   |   |--- class: 1
|   |--- worst concave points >  0.14
|   |   |--- class: 0
|--- worst radius >  16.80
|   |--- worst texture <= 19.91
|   |   |--- class: 1
|   |--- worst texture >  19.91
|   |   |--- class: 0

Đọc cột CV: sâu 3 đạt 0.917, không giới hạn độ sâu cũng 0.917. Cây sâu 3 nông hơn, đọc được thành một bộ luật ngắn, nên là lựa chọn tự nhiên khi điểm ngang nhau.