Bài 28: Decision Tree — cây quyết định và entropy/gini

Decision Tree là model tree-based: học bằng cách split data thành các nhóm con dựa trên feature và threshold, lặp lại đệ quy cho đến khi mỗi nhóm con đủ thuần (gần như chỉ chứa một class) hoặc chạm điều kiện dừng.

Khác biệt căn bản so với Logistic Regression (Bài 22) hoặc KNN (Bài 27):

• Logistic Regression học một hyperplane tuyến tính chia toàn không gian.
• KNN không học gì cả, chỉ lưu data và so sánh khoảng cách lúc predict.
• Decision Tree học một chuỗi rule if-then dạng "nếu feature \( x_j \leq t \) thì sang nhánh trái, ngược lại sang nhánh phải" — boundary là tập hợp các đoạn thẳng vuông góc với trục feature.

Vì split theo từng feature riêng lẻ, tree không cần scale feature — khác với mọi model linear hoặc distance-based đã gặp. Đây cũng là model đầu tiên trong series chạy ra một mô hình có thể "đọc bằng mắt" như một flowchart.

Một Decision Tree gồm ba loại node:

• Root node — node gốc, chứa toàn bộ training data trước khi split lần đầu.
• Internal node — mỗi internal node chứa một split rule dạng feature_j ≤ threshold. Sample đi vào node được chia thành nhánh trái (rule đúng) và nhánh phải (rule sai).
• Leaf node — node lá, chứa prediction. Với classification, leaf giữ class chiếm đa số trong các sample rơi vào leaf đó (hoặc phân phối probability của các class). Với regression, leaf giữ giá trị trung bình của target.

Mỗi path từ root xuống một leaf chính là một rule chuỗi: "nếu \( x_1 \leq 2.5 \) và \( x_3 > 0.7 \) và \( x_2 \leq 1.2 \) thì class = A". Tổng số leaf của tree bằng số rule. Vì vậy tree có thể tự diễn giải mà không cần thêm thuật toán explainability nào ngoài cách đọc đường đi.

Trong sklearn, tree mặc định là binary tree (mỗi internal node tách thành đúng 2 nhánh), kể cả khi feature là categorical (sklearn yêu cầu encode thành số trước, mỗi split vẫn là dạng \( x_j \leq t \)).

Thuật toán train là greedy recursive splitting (CART — Classification And Regression Trees, Breiman 1984):

1. Bắt đầu với toàn bộ data tại root node.
2. Tại mỗi node, duyệt qua mọi feature và mọi threshold ứng viên (giá trị giữa các sample đã sort theo feature đó), tính impurity sau split. Chọn cặp (feature, threshold) giảm impurity nhiều nhất.
3. Tạo hai child node theo split vừa chọn, gán subset sample tương ứng.
4. Đệ quy bước 2–3 trên từng child node.
5. Dừng khi gặp một trong các điều kiện: max_depth đạt giới hạn, số sample của node nhỏ hơn min_samples_split, hoặc node đã thuần (impurity = 0).

Hai chú ý:

• Greedy — mỗi bước chỉ tối ưu cục bộ (split tốt nhất ngay tại node hiện tại), không đảm bảo tree toàn cục tối ưu. Tìm tree tối ưu toàn cục là NP-hard nên không khả thi trong thực tế.
• Không cần scale — split theo điều kiện \( x_j \leq t \) chỉ dùng thứ tự sample theo feature \( j \), không phụ thuộc đơn vị. Đổi feature từ "mét" sang "centimet" làm threshold đổi theo nhưng cây sinh ra tương đương về quyết định.

Impurity đo "độ pha trộn" của các class trong một node. Node thuần (chỉ chứa 1 class) có impurity = 0; node trộn đều các class có impurity tối đa.

Mục tiêu của split: chia node hiện tại thành các child node có impurity trung bình thấp hơn node cha. Khoảng giảm impurity là tiêu chí chọn split.

Hai hàm impurity phổ biến cho classification trong sklearn:

• Gini Impurity (mục 5) — mặc định, rẻ tính.
• Entropy (mục 6) — gốc từ information theory.

Cho regression, impurity là variance hoặc MSE trong node (mục 15).

Cho node chứa data với phân phối class \( p_1, p_2, \ldots, p_K \) (\( p_k \) là tỉ lệ class \( k \) trong node):

Diễn giải: Gini bằng xác suất phân loại sai nếu ta gán nhãn cho một sample ngẫu nhiên trong node bằng cách bốc thăm theo phân phối class của node đó. Càng pha trộn → xác suất sai càng cao → Gini càng lớn.

Range:

• \( \text{Gini} = 0 \) khi node thuần (\( p_k = 1 \) cho một class duy nhất).
• Tối đa \( 1 - 1/K \). Với binary (\( K = 2 \)), tối đa là \( 0.5 \) khi \( p_1 = p_2 = 0.5 \).

Ví dụ binary: node có 60 sample class 0 và 40 sample class 1 → \( p_0 = 0.6, p_1 = 0.4 \) → Gini = \( 1 - 0.6^2 - 0.4^2 = 1 - 0.36 - 0.16 = 0.48 \). Node có 90 class 0 và 10 class 1 → Gini = \( 1 - 0.81 - 0.01 = 0.18 \). Node thứ hai "thuần" hơn nên Gini thấp hơn.

Gini là default trong DecisionTreeClassifier của sklearn.

Entropy xuất phát từ information theory (Shannon 1948), đo "lượng thông tin trung bình" cần để mô tả class của một sample ngẫu nhiên trong node:

Quy ước \( 0 \log_2 0 = 0 \).

Range:

• \( H = 0 \) khi node thuần.
• Tối đa \( \log_2 K \) khi phân phối uniform \( p_k = 1/K \). Với binary, tối đa \( \log_2 2 = 1 \) khi \( p_0 = p_1 = 0.5 \).

Cùng ví dụ trên với 60/40: \( H = -0.6 \log_2 0.6 - 0.4 \log_2 0.4 \approx 0.971 \). Với 90/10: \( H \approx 0.469 \).

Trong sklearn dùng entropy bằng cách set criterion="entropy". Algorithm chọn split không đổi — chỉ thay hàm impurity.

Information Gain (IG) là khoảng giảm impurity sau khi split node cha thành các child node:

Trong đó \( n \) là tổng số sample tại node cha, \( n_i \) là số sample tại child \( i \), \( H \) là hàm impurity (Gini hoặc Entropy). Phần tổng có trọng số đảm bảo child có nhiều sample đóng góp nhiều hơn.

Thuật toán train chọn cặp (feature, threshold) cực đại IG tại mỗi node. Vì \( H(\text{parent}) \) cố định khi split tại một node, cực đại IG tương đương cực tiểu impurity trung bình có trọng số của child.

Ví dụ binary với node cha 100 sample (60 class 0, 40 class 1, Gini = 0.48). Một split chia thành child trái (50 sample: 45/5, Gini ≈ 0.18) và child phải (50 sample: 15/35, Gini = 0.42). IG = \( 0.48 - (0.5 \cdot 0.18 + 0.5 \cdot 0.42) = 0.48 - 0.30 = 0.18 \). Split nào có IG cao hơn 0.18 (trong số mọi feature × threshold) sẽ được chọn.

Cả Gini và Entropy đều đạt cực tiểu (= 0) khi node thuần và cực đại khi phân phối uniform. Chúng cho ra thứ tự split gần như giống nhau trong phần lớn dataset thực tế.

Khác biệt thực dụng:

• Tốc độ — Gini không có \( \log \), chỉ là phép nhân và cộng → rẻ hơn entropy về chi phí tính toán, đặc biệt khi tree có hàng nghìn node và nhiều split ứng viên. Đây là lý do sklearn chọn Gini làm mặc định.
• Range và scale — Gini binary tối đa 0.5; Entropy binary tối đa 1.0. Giá trị IG vì vậy có scale khác, nhưng vì so sánh chỉ trong cùng một criterion nên không quan trọng.
• Performance — gần như không khác biệt trên test set. Khi tune model, đổi criterion ít khi là cải thiện đáng kể; tune max_depth và min_samples_leaf đáng tiền hơn.

Khuyến nghị: giữ default Gini. Chỉ đổi sang entropy nếu cần so sánh với tài liệu information theory hoặc khi yêu cầu cụ thể của bài toán.

API tối thiểu, giống mọi estimator khác:

from sklearn.tree import DecisionTreeClassifier, DecisionTreeRegressor

tree = DecisionTreeClassifier(
    criterion="gini",
    max_depth=5,
    random_state=42,
)
tree.fit(X_train, y_train)

y_pred = tree.predict(X_test)
y_proba = tree.predict_proba(X_test)  # ti le class trong leaf

random_state quan trọng vì khi có nhiều split tie (IG bằng nhau), sklearn break tie ngẫu nhiên — không set seed sẽ ra tree khác mỗi lần fit.

Hai estimator chính:

• DecisionTreeClassifier — target rời rạc, mặc định Gini.
• DecisionTreeRegressor — target liên tục, mặc định "squared_error" (MSE trong node).

Cả hai không yêu cầu scale, không yêu cầu encode one-hot cho ordinal feature (label encoding đã đủ vì tree chỉ so sánh thứ tự). Nhưng với nominal category nhiều giá trị (như city, product_id), cần encode hợp lý — split theo label encoding nominal sẽ áp đặt thứ tự giả.

Các tham số kiểm soát kích thước và độ phức tạp của tree:

• criterion — "gini" (mặc định) hoặc "entropy". "log_loss" trong sklearn 1.0+ là alias của entropy.
• max_depth — độ sâu tối đa của tree. None (mặc định) tức không giới hạn — tree sẽ split đến khi mỗi leaf thuần hoặc chạm min_samples_split, gần như chắc chắn overfit.
• min_samples_split (mặc định 2) — số sample tối thiểu để được tiếp tục split. Tăng giá trị này → tree nông hơn, ít overfit.
• min_samples_leaf (mặc định 1) — số sample tối thiểu mỗi leaf phải có. Set ≥ 5 hoặc 10 để tránh leaf chỉ chứa 1 sample (rule quá đặc thù).
• max_features — số feature xét tại mỗi split (mặc định xét tất cả). Khi đặt nhỏ hơn, tree biến thành "randomized" — đây là cơ chế cốt lõi của Random Forest (Bài 29).
• max_leaf_nodes — chặn tổng số leaf, dùng best-first growth thay vì depth-first.
• class_weight — set "balanced" để cân lại trọng số class khi dataset imbalanced.
• ccp_alpha (mặc định 0.0) — tham số cho post-pruning (mục 11). Tăng làm tree bị cắt nhiều hơn.
• random_state — seed để reproducible.

Combo baseline an toàn: DecisionTreeClassifier(max_depth=5, min_samples_leaf=10, random_state=42). Sau đó tune max_depth và min_samples_leaf bằng cross-validation.

Decision Tree không giới hạn sẽ overfit hoàn toàn: nó có thể tách đến mức mỗi sample train rơi vào một leaf riêng, đạt accuracy train = 100% trong khi accuracy test sụp đổ. Đây không phải lý thuyết — chạy DecisionTreeClassifier() mặc định trên hầu hết dataset đều cho kết quả này.

Hai chiến lược chống overfit:

• Pre-pruning (early stopping) — chặn tree không phát triển quá to ngay trong lúc train. Cụ thể là set max_depth, min_samples_split, min_samples_leaf, hoặc max_leaf_nodes. Cách này dễ và nhanh, là chuẩn industry mặc định.
• Post-pruning (Cost Complexity Pruning, CCP) — train tree đầy đủ trước, sau đó cắt bớt các subtree đóng góp ít vào việc giảm impurity. Sklearn implement qua tham số ccp_alpha: với mỗi giá trị \( \alpha \), tree tối ưu là tree cực tiểu \( R(T) + \alpha |T| \), trong đó \( R(T) \) là tổng impurity của các leaf, \( |T| \) là số leaf. \( \alpha = 0 \) giữ nguyên tree; \( \alpha \) lớn cắt mạnh.

Pipeline post-pruning gọn:

tree_full = DecisionTreeClassifier(random_state=42).fit(X_train, y_train)
path = tree_full.cost_complexity_pruning_path(X_train, y_train)
alphas = path.ccp_alphas  # cac gia tri alpha noi tree thay doi
# Cross-validate tren cac alpha, chon alpha tot nhat

Trong thực tế, pre-pruning với max_depth + min_samples_leaf đủ tốt cho phần lớn bài toán. Post-pruning hữu ích khi cần tree nhỏ nhất có thể với accuracy chấp nhận được (ví dụ deploy lên edge device).

Pros:

• Interpretable — đọc rule từ root đến leaf là đủ giải thích quyết định. Visualize được bằng plot_tree. Quan trọng cho ngành ngân hàng, y tế, bảo hiểm.
• Không cần scale feature.
• Xử lý mixed dtype tự nhiên — numerical, ordinal (sau label encode) đều được. Sklearn vẫn yêu cầu encode trước, nhưng tree không quan tâm phân phối của feature.
• Không giả định về distribution của data — không cần normal, không cần linear separable.
• Bắt được tương tác phi tuyến giữa feature qua các split kế tiếp (split theo \( x_1 \), rồi split theo \( x_2 \) trong subtree).

Cons:

• Variance cao — một thay đổi nhỏ trong train data (thêm/bớt vài sample) có thể làm split ở root đổi → toàn bộ tree đổi hẳn cấu trúc. Đây là điểm yếu lớn nhất của tree đơn lẻ.
• Greedy không tối ưu toàn cục — split tốt nhất hiện tại có thể chặn split rất tốt ở bước sau.
• Dễ overfit nếu không pruning. Tree không giới hạn gần như luôn memorize train.
• Boundary vuông góc với trục feature → không hiệu quả khi quan hệ thực sự nghiêng (ví dụ \( x_1 + x_2 = c \) cần nhiều split xấp xỉ).
• Bias về feature có nhiều giá trị unique — feature với nhiều threshold ứng viên có lợi thế khi chọn split.

Variance cao chính là động lực để chuyển sang Random Forest (Bài 29) — train nhiều tree trên các subset data + subset feature, vote/average kết quả. Bộ tổng hợp này giảm variance đáng kể trong khi giữ phần lớn ưu điểm của tree.

Sklearn cung cấp hai cách visualize:

import matplotlib.pyplot as plt
from sklearn.tree import plot_tree, export_text

plot_tree(
    tree,
    feature_names=iris.feature_names,
    class_names=iris.target_names,
    filled=True,
    rounded=True,
)
plt.show()

# Hoac in text rule:
print(export_text(tree, feature_names=list(iris.feature_names)))

Trong mỗi node của plot_tree hiển thị:

• Split rule (ví dụ petal length (cm) <= 2.45).
• gini hoặc entropy của node.
• samples — số sample trong node.
• value — số sample mỗi class trong node.
• class — class chiếm đa số (prediction nếu node là leaf).

Đọc rule cho một prediction: từ root, theo nhánh trái nếu split rule đúng, nhánh phải nếu sai, đi đến khi vào leaf — class của leaf là prediction. Cùng cách diễn giải áp dụng cho export_text, dạng plain text dễ copy vào báo cáo.

Tree quá lớn (max_depth lớn) sẽ không đọc được bằng mắt; visualize chỉ hữu ích cho tree nông (depth ≤ 5).

Sau khi fit, đọc attribute tree.feature_importances_ — array shape (n_features,) chứa tỉ lệ contribution của mỗi feature trong việc giảm impurity tổng cộng (tính trên các node nội bộ, có trọng số theo số sample đi qua).

• Giá trị trong khoảng \( [0, 1] \), tổng bằng 1.
• Feature không bao giờ được dùng để split có importance = 0.
• Feature có importance cao → tree split theo feature đó nhiều hoặc tại node gốc (có nhiều sample).

import pandas as pd

importances = pd.Series(
    tree.feature_importances_,
    index=iris.feature_names,
).sort_values(ascending=False)
print(importances)

Hai cảnh báo khi dùng feature importance của tree:

• Bias về cardinality — feature có nhiều giá trị unique (nhiều threshold ứng viên) thường được chọn nhiều hơn, importance hiển thị cao hơn thực tế.
• Variance cao — train lại trên subset khác có thể ra ranking khác. Random Forest trả ra importance ổn định hơn nhiều vì lấy trung bình trên hàng trăm tree.

Để đo importance chính xác hơn, dùng permutation importance (sklearn.inspection.permutation_importance) — đo độ giảm score khi shuffle ngẫu nhiên giá trị của một feature.

DecisionTreeRegressor dùng cùng thuật toán greedy splitting, nhưng:

• Impurity = variance hoặc MSE trong node (mặc định "squared_error"). Các option khác: "friedman_mse", "absolute_error", "poisson".
• Leaf prediction = mean của target các sample trong leaf (với MSE). Nếu dùng "absolute_error" thì là median.
• Output là một hàm bậc thang — mỗi vùng feature (lá) trả về một hằng số. Không tạo ra prediction trơn như Linear Regression.

Hệ quả thực tế: tree regression dự đoán giá trị nằm trong khoảng [min, max] của target trong train data — không extrapolate ra ngoài. Khác Linear Regression có thể trả về bất kỳ giá trị nào.

from sklearn.tree import DecisionTreeRegressor
from sklearn.datasets import fetch_california_housing
from sklearn.model_selection import train_test_split
from sklearn.metrics import mean_squared_error

X, y = fetch_california_housing(return_X_y=True)
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.2, random_state=42,
)

reg = DecisionTreeRegressor(max_depth=8, min_samples_leaf=20, random_state=42)
reg.fit(X_train, y_train)
pred = reg.predict(X_test)
print(f"RMSE: {mean_squared_error(y_test, pred) ** 0.5:.4f}")

Tree regression đơn lẻ thường yếu hơn Linear/Ridge trên dataset có quan hệ trơn. Sức mạnh thực sự đến khi ensemble — Random Forest Regressor và Gradient Boosting (XGBoost, LightGBM, sẽ bàn ở Module sau).

Demo full trên iris: train tree, in feature importance, so sánh max_depth=3 vs unlimited, mô tả cách visualize.

import numpy as np
import pandas as pd
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier, plot_tree, export_text
from sklearn.metrics import accuracy_score
import matplotlib.pyplot as plt

iris = load_iris()
X, y = iris.data, iris.target

X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.3, random_state=42, stratify=y,
)

# Tree co pre-pruning: max_depth = 3
tree = DecisionTreeClassifier(max_depth=3, random_state=42)
tree.fit(X_train, y_train)

print(f"train acc: {accuracy_score(y_train, tree.predict(X_train)):.4f}")
print(f"test acc:  {accuracy_score(y_test, tree.predict(X_test)):.4f}")

# Feature importance
importances = pd.Series(
    tree.feature_importances_,
    index=iris.feature_names,
).sort_values(ascending=False)
print(importances)
# Thuong petal length va petal width chiem gan het importance

# In rule dang text
print(export_text(tree, feature_names=list(iris.feature_names)))

# Visualize tree (mo ta — chay trong notebook se ve duoc)
fig, ax = plt.subplots(figsize=(12, 6))
plot_tree(
    tree,
    feature_names=iris.feature_names,
    class_names=iris.target_names,
    filled=True,
    rounded=True,
    ax=ax,
)
plt.tight_layout()
# plt.show()  # bo comment khi chay local

So sánh max_depth=3 vs unlimited:

for depth in [3, None]:
    t = DecisionTreeClassifier(max_depth=depth, random_state=42)
    t.fit(X_train, y_train)
    train_acc = accuracy_score(y_train, t.predict(X_train))
    test_acc = accuracy_score(y_test, t.predict(X_test))
    label = "unlimited" if depth is None else f"max_depth={depth}"
    print(f"{label:15s} | train={train_acc:.4f} | test={test_acc:.4f} | leaves={t.get_n_leaves()}")

Quan sát đặc trưng trên iris:

• max_depth=3: train acc ~0.97, test acc ~0.93, 4–5 leaves.
• unlimited: train acc = 1.00 (memorize), test acc tương đương hoặc thấp hơn, số leaf lớn hơn nhiều.

Iris đơn giản nên hai tree gần ngang nhau trên test, nhưng trên dataset khó hơn (Breast Cancer, Wine Quality) khoảng cách overfit thấy rõ — đây là nội dung Bài tập 1.

Bài 1 — Ảnh hưởng của max_depth trên iris. Load iris, split 70/30 với stratify=y. Train DecisionTreeClassifier với max_depth ∈ {1, 3, 5, None}, mỗi model dùng random_state=42. In cho mỗi model: train accuracy, test accuracy, số leaf (get_n_leaves()), độ sâu thực tế (get_depth()). Bảng kết quả cho thấy điều gì về overfit khi không giới hạn depth?

Bài 2 — Visualize tree max_depth=3. Vẫn trên iris, train DecisionTreeClassifier(max_depth=3, random_state=42). Vẽ tree bằng plot_tree(filled=True, rounded=True) với feature_names và class_names. Đọc trực tiếp từ hình: feature nào được dùng split ở root? Có bao nhiêu leaf? Mỗi leaf dự đoán class nào? In rule text bằng export_text và đối chiếu với hình vẽ.

Bài 3 — Gini vs Entropy. Trên iris, train 2 model giống nhau hoàn toàn ngoài criterion: một dùng "gini", một dùng "entropy". Set max_depth=5, random_state=42. So sánh: (a) test accuracy, (b) cấu trúc tree có giống nhau không (so get_n_leaves() và rule text). Khác biệt có đáng kể không?

Bài 4 — Tree regression trên California housing. Load fetch_california_housing(), split 80/20 random_state=42. Train DecisionTreeRegressor(max_depth=8, min_samples_leaf=20, random_state=42). In RMSE test (mean_squared_error(...) ** 0.5). Sau đó so sánh với DecisionTreeRegressor() mặc định (unlimited depth) — RMSE test khác nhau bao nhiêu? In get_n_leaves() của hai model.

Bài 5 — Feature importance trên Breast Cancer. Load load_breast_cancer() (30 feature), split 70/30. Train DecisionTreeClassifier(max_depth=5, random_state=42). In top-10 feature theo feature_importances_. Có bao nhiêu feature có importance = 0? In test accuracy.

Gợi ý Bài 1: với max_depth=1, tree chỉ split một lần (stump) — accuracy chắc chắn thấp. Với None, tree phát triển đến khi mỗi leaf thuần — train accuracy gần 1.0, test có thể vẫn tốt trên iris vì dataset dễ, nhưng số leaf nhiều hơn hẳn.

Bài 29: Random Forest — variance cao là điểm yếu chính của Decision Tree đơn lẻ. Random Forest giải bằng cách train nhiều tree trên các bootstrap sample và subset feature, vote/average kết quả. Ensemble này giảm variance đáng kể, giữ tính phi tuyến của tree, và là baseline mạnh cho hầu hết bài toán tabular.