Cây Quyết Định

Learning Objectives

• ✓Tính Gini, Entropy và Information Gain để chọn điểm chia
• ✓Hiểu cách chọn ngưỡng chia cho đặc trưng số và thuật toán CART
• ✓Kiểm soát overfitting bằng max_depth, min_samples_leaf, ccp_alpha
• ✓Đánh giá ổn định bằng K-Fold và Stratified K-Fold
• ✓Tinh chỉnh siêu tham số bằng GridSearchCV và RandomizedSearchCV

Cây Quyết Định & Tiêu Chí Chia

Decision Tree đặt câu hỏi Yes/No liên tiếp về đặc trưng, mỗi câu hỏi chia dữ liệu thành 2 nhánh tinh khiết hơn, tạo tập luật If-Then con người đọc hiểu được — dùng cho cả hồi quy và phân loại, không cần feature scaling, xử lý tốt quan hệ phi tuyến. Độ tinh khiết đo bằng: Gini Impurity (min 0, max 0.5 — mặc định sklearn, nhanh vì không cần log) hoặc Entropy (min 0, max 1.0 bit — nhạy hơn khi phân phối lệch). Information Gain = Impurity(cha) − Σ(nₖ/n)·Impurity(conₖ); chọn feature/ngưỡng có Gain LỚN NHẤT.

# 10 bệnh nhân: 4 High, 6 Low → Gini gốc = 1-(0.4²+0.6²) = 0.480
# Chia theo "Hút thuốc=Yes?":
#   Nhánh YES (3H 1L): Gini = 1-(0.75²+0.25²) = 0.375
#   Nhánh NO  (1H 5L): Gini = 1-(0.167²+0.833²) = 0.278
gini_weighted = 4/10 * 0.375 + 6/10 * 0.278   # = 0.317
gini_gain = 0.480 - 0.317                       # = 0.163 → chọn split này

Chọn Ngưỡng Chia & Thuật Toán CART

Với đặc trưng số, thuật toán sắp xếp giá trị rồi thử tất cả midpoints giữa các cặp liên tiếp (n−1 ngưỡng ứng viên), tính Gini Gain cho mỗi ngưỡng và chọn ngưỡng có Gain lớn nhất. Lưu ý: đặc trưng liên tục có nhiều ngưỡng hơn đặc trưng nhị phân → dễ bị ưu tiên (cardinality bias). Thuật toán CART (Classification And Regression Trees): tại mỗi node duyệt tất cả feature × tất cả ngưỡng → chọn split có Gain lớn nhất → chia 2 nhánh → lặp đệ quy đến khi đạt điều kiện dừng (node tinh khiết, đạt max_depth, hoặc số mẫu < min_samples_split).

Kiểm Soát Overfitting

Cây để phát triển tự do (depth=None) dễ đạt Train Accuracy = 100% nhưng Test chỉ ~72% — học thuộc lòng, không tổng quát. Các siêu tham số kiểm soát: max_depth (số tầng tối đa, thử 3–6), min_samples_leaf (số mẫu tối thiểu ở lá, thử 10–50), min_samples_split (mặc định 2), max_leaf_nodes (thay thế max_depth), và ccp_alpha (hệ số cắt tỉa — cost-complexity pruning, tìm qua CV). Chiến lược thực hành: bắt đầu max_depth=3 → tăng dần, vẽ train/test → dừng khi test giảm → GridSearchCV tối ưu.

from sklearn.tree import DecisionTreeClassifier

tree = DecisionTreeClassifier(
    criterion='gini',
    max_depth=5,           # best trên ví dụ slide (Test Acc = 0.765)
    min_samples_leaf=20,
    random_state=42
).fit(X_train, y_train)

print("Train:", tree.score(X_train, y_train))
print("Test :", tree.score(X_test, y_test))

Cross-Validation

Train/Test split một lần cho kết quả phụ thuộc cách chia. K-Fold Cross-Validation chia K phần, mỗi fold làm test đúng một lần → đánh giá ổn định hơn, báo cáo mean ± std (chuẩn: K=5 hoặc 10). Stratified K-Fold giữ tỷ lệ lớp trong mỗi fold — quan trọng khi dữ liệu mất cân bằng (là mặc định của sklearn cho classification). Repeated K-Fold lặp nhiều lần với seed khác để giảm variance của ước lượng.

from sklearn.model_selection import cross_val_score, StratifiedKFold

skf = StratifiedKFold(n_splits=5, shuffle=True, random_state=42)
scores = cross_val_score(tree, X, y, cv=skf, scoring='accuracy')
print(f'CV Accuracy: {scores.mean():.3f} ± {scores.std():.3f}')

Tinh Chỉnh Siêu Tham Số

GridSearchCV thử TẤT CẢ tổ hợp trong lưới đã định (đảm bảo tìm best nhưng chậm khi nhiều tham số — dùng khi ≤2-3 tham số); RandomizedSearchCV chọn ngẫu nhiên n tổ hợp (nhanh, cover nhiều vùng hơn — dùng khi không gian lớn). Kèm theo hai công cụ chẩn đoán: Learning Curve (trục X = số mẫu train; hai đường hội tụ = OK, khoảng cách lớn = overfitting, cả hai thấp = underfitting) và Validation Curve (trục X = giá trị siêu tham số; chọn điểm validation cao nhất trước khi giảm).

from sklearn.model_selection import GridSearchCV, RandomizedSearchCV
from scipy.stats import randint

param_grid = {
    'max_depth': [3, 4, 5, 6, 7],
    'min_samples_leaf': [5, 10, 20, 50],
    'criterion': ['gini', 'entropy'],
}  # 5×4×2 = 40 tổ hợp × 5-fold = 200 lần fit
grid = GridSearchCV(DecisionTreeClassifier(random_state=42),
                    param_grid, cv=5, scoring='accuracy', n_jobs=-1)
grid.fit(X_train, y_train)
print("Best params:", grid.best_params_)
print("Best CV Acc:", grid.best_score_)