Bài 29: Random Forest — ensemble nhiều decision tree

Bài 28 trình bày Decision Tree — model phi tuyến, dễ hiểu, không cần scale, xử lý được hỗn hợp feature số và categorical. Nhược điểm chính: variance cao. Thay đổi nhỏ trong tập train (thêm/bớt vài sample, thay seed split) có thể sinh ra cây với cấu trúc khác hẳn — root split khác, depth khác, leaf khác.

Hệ quả: single tree dễ overfit, accuracy test dao động mạnh giữa các lần train. max_depth nhỏ thì underfit; sâu thì overfit. Tinh chỉnh không bao giờ ổn định.

Random Forest sinh ra để giải đúng vấn đề này — giữ ưu điểm của tree, đẩy variance xuống bằng cách train nhiều tree độc lập rồi gộp kết quả.

Ensemble Learning: kết hợp nhiều "weak learner" (model đơn giản, hơi yếu) thành một "strong learner" có hiệu năng cao hơn từng model thành phần. Nguyên lý số học cơ bản: nếu lấy trung bình \( K \) ước lượng độc lập có cùng kỳ vọng và variance \( \sigma^2 \), variance của trung bình giảm còn \( \sigma^2 / K \). Bias giữ nguyên, variance giảm.

Hai họ ensemble phổ biến nhất:

• Bagging (Bootstrap Aggregating) — train song song nhiều model trên các tập con khác nhau của data, average kết quả. Mục tiêu chính: giảm variance. Random Forest thuộc nhóm này.
• Boosting — train tuần tự, mỗi model mới tập trung sửa lỗi của model trước. Mục tiêu chính: giảm bias. Gradient Boosting, XGBoost (Bài 30) thuộc nhóm này.

Bài này tập trung bagging; boosting sẽ bàn ở Bài 30.

Bagging có hai bước:

• Bootstrap — từ tập train kích thước \( n \), sample \( n \) sample có hoàn lại (with replacement). Mỗi bootstrap dataset cùng kích thước với tập gốc, nhưng có sample lặp và một số sample không xuất hiện. Lặp lại \( K \) lần để có \( K \) dataset khác nhau.
• Aggregate — train \( K \) model độc lập trên \( K \) dataset đó. Khi predict:
  • Classification: vote đa số (majority vote) — class được nhiều tree dự đoán nhất thắng.
  • Regression: trung bình — \( \hat{y} = \frac{1}{K} \sum_{k=1}^K \hat{y}_k \).

Vì sao bootstrap giảm variance: các tập con bootstrap khác nhau làm cây sinh ra cũng khác nhau. Trung bình hoá nhiều tree làm "nhiễu" của từng tree triệt tiêu, giữ lại tín hiệu chung. Bias gần như không đổi — mỗi tree vẫn unbiased — nhưng variance giảm.

Bagging không chỉ áp dụng cho tree. Có thể bag bất kỳ base learner nào (Neural Network, k-NN, …). Nhưng tree là lựa chọn lý tưởng: variance cao sẵn (nên bagging giúp nhiều), train nhanh, không cần scale, song song hoá dễ.

Bagging tree đơn thuần có giới hạn: nếu trong data có một feature rất mạnh (information gain lớn hơn hẳn), mọi tree sẽ chọn nó làm root split. Cấu trúc của các cây vì vậy rất giống nhau → correlated — bagging giảm variance ít hiệu quả vì lấy trung bình các biến tương quan cao không giảm variance bao nhiêu.

Random Forest (Breiman, 2001) thêm một bước nữa để decorrelate các tree:

• Tại mỗi node của mỗi tree, không xét toàn bộ feature mà chỉ random pick một subset \( m \) feature, rồi chọn split tốt nhất trong \( m \) feature đó.
• Convention mặc định:
  • Classification: \( m = \sqrt{d} \) (\( d \) là tổng số feature).
  • Regression: \( m = d/3 \).

Hiệu ứng: vì mỗi node chỉ thấy một phần feature, các tree có cơ hội chọn feature khác nhau làm split. Tree đa dạng hơn → ít correlated → trung bình hoá hiệu quả hơn → variance giảm mạnh hơn so với bagging thuần.

Đổi lại: từng tree riêng lẻ kém hơn tree thường (vì có thể không thấy feature tốt nhất tại một số node), nhưng tập hợp lại thì tổng thể tốt hơn. Đây là một trade-off có chủ đích.

Cho dataset \( D = \{(\mathbf{x}_i, y_i)\}_{i=1}^n \), số tree \( K \), số feature mỗi split \( m \).

Training:

• For \( k = 1, \ldots, K \):
  • Bootstrap sample \( D_k \) — sample \( n \) sample có hoàn lại từ \( D \).
  • Train một decision tree \( T_k \) trên \( D_k \), với ràng buộc: tại mỗi node, chỉ xét \( m \) feature random rồi chọn split tốt nhất.
  • Thường để tree mọc sâu hết cỡ (không prune, không giới hạn max_depth). Vì ensemble đã giảm variance, từng tree có thể overfit — ensemble vẫn ổn.

Prediction cho sample mới \( \mathbf{x} \):

• Classification: \( \hat{y} = \text{mode}(T_1(\mathbf{x}), \ldots, T_K(\mathbf{x})) \) (vote đa số). sklearn dùng soft vote — trung bình probability của các tree rồi argmax: \( \hat{p} = \frac{1}{K} \sum_{k=1}^K T_k.\text{predict\_proba}(\mathbf{x}) \).
• Regression: \( \hat{y} = \frac{1}{K} \sum_{k=1}^K T_k(\mathbf{x}) \).

Hai nguồn ngẫu nhiên (bootstrap sampling và random feature mỗi split) khiến mỗi tree khác nhau — đảm bảo tính đa dạng cần thiết để ensemble hoạt động.

API tối thiểu:

from sklearn.ensemble import RandomForestClassifier, RandomForestRegressor

rf = RandomForestClassifier(
    n_estimators=100,
    max_depth=None,
    random_state=42,
    n_jobs=-1,
)
rf.fit(X_train, y_train)

y_pred = rf.predict(X_test)
y_proba = rf.predict_proba(X_test)

Khác biệt so với DecisionTreeClassifier:

• n_estimators — số tree.
• n_jobs — số core CPU để train song song. Random Forest embarrassingly parallel (các tree độc lập), set -1 để dùng hết core.
• bootstrap, oob_score, max_features — các tham số đặc thù ensemble.

Mọi tham số kiểm soát cây con (max_depth, min_samples_split, min_samples_leaf, criterion) hoạt động giống DecisionTreeClassifier — áp dụng cho mỗi tree thành phần.

• n_estimators (mặc định 100) — số tree. Càng nhiều càng ổn định, nhưng diminishing return sau ngưỡng vài trăm. Thời gian train và inference tăng tuyến tính.
• max_depth (mặc định None) — độ sâu tối đa của mỗi tree. None = không giới hạn (mọc tới leaf thuần). Với RF, None thường OK vì ensemble đã chống overfit. Set giá trị cụ thể nếu RAM/thời gian là vấn đề.
• max_features — số feature random tại mỗi split:
  • "sqrt" (mặc định cho classification) — \( \sqrt{d} \).
  • "log2" — \( \log_2 d \).
  • 1.0 hoặc None (mặc định cho regression) — toàn bộ \( d \) feature. Lưu ý: với max_features=1.0 RF biến thành bagging thuần — mất phần "random feature".
  • Số nguyên: dùng đúng số feature đó.
  • Số float trong (0, 1): tỉ lệ của \( d \).
• min_samples_split (mặc định 2), min_samples_leaf (mặc định 1) — kiểm soát kích thước node tối thiểu, giống Decision Tree.
• bootstrap (mặc định True) — bật bagging. Đặt False → mỗi tree train trên toàn bộ data (chỉ còn random feature làm nguồn đa dạng) — biến thành ExtraTrees-like, thường kém hơn.
• oob_score (mặc định False) — bật để tính OOB score (mục 8). Chỉ dùng khi bootstrap=True.
• n_jobs — số core. Train và predict song song trên các tree.
• random_state — seed cho bootstrap sampling và random feature.
• class_weight — "balanced" hoặc "balanced_subsample" cho dataset imbalanced.

Tính chất số học của bootstrap: với \( n \) lớn, xác suất một sample không bị chọn vào một bootstrap dataset xấp xỉ \( (1 - 1/n)^n \to 1/e \approx 0.368 \). Tức là mỗi tree không nhìn thấy khoảng 37% dataset gốc — những sample này gọi là out-of-bag (OOB) cho tree đó.

Ý tưởng OOB score:

• Với mỗi sample \( i \) trong tập train, tìm các tree không chứa nó trong bootstrap → predict bằng tập tree đó → so với label thật.
• Trung bình lỗi qua tất cả sample → OOB error.

Mỗi sample được dự đoán bởi ~37% số tree (đủ nhiều để vote ổn định khi \( K \) lớn). OOB error là estimate gần đúng của test error mà không cần tập validation riêng — vì OOB sample chưa từng được tree đó nhìn thấy, vai trò tương đương held-out data.

Trong sklearn:

rf = RandomForestClassifier(n_estimators=200, oob_score=True, random_state=42, n_jobs=-1)
rf.fit(X_train, y_train)
print(f"OOB score: {rf.oob_score_:.4f}")

Lưu ý: OOB score là một dạng cross-validation "miễn phí" cho Random Forest — khác với cross_val_score vì không cần train lại model. Tuy nhiên với n_estimators nhỏ (vài chục), OOB estimate kém ổn định; nên dùng khi \( K \geq 100 \).

Random Forest cho hai cách đo độ quan trọng của feature.

Mean Decrease in Impurity (MDI) — rf.feature_importances_:

• Với mỗi tree, tính tổng giảm impurity (Gini hoặc entropy) khi mỗi feature được dùng split, có trọng số theo số sample qua node.
• Trung bình qua tất cả tree → vector importance, tổng = 1.
• Stable hơn nhiều so với một single tree (do ensemble), nhưng có hai bias đã biết:
  • Thiên vị feature có nhiều giá trị (numeric continuous, categorical cardinality cao).
  • Tính trên train data → có thể đánh giá cao feature mà tree dùng để overfit.

Permutation Importance — đo trên test/validation:

• Lấy baseline score trên test.
• Với mỗi feature \( j \): shuffle cột \( j \) trong test → predict lại → đo score sụt bao nhiêu.
• Sụt nhiều = feature quan trọng. Lặp nhiều lần để có trung bình + độ lệch chuẩn.

from sklearn.inspection import permutation_importance

result = permutation_importance(rf, X_test, y_test, n_repeats=10, random_state=42, n_jobs=-1)
for idx in result.importances_mean.argsort()[::-1]:
    print(f"{feature_names[idx]:20s} {result.importances_mean[idx]:.4f} +/- {result.importances_std[idx]:.4f}")

Permutation importance không phụ thuộc model — áp dụng được cho mọi estimator. Khi nghi ngờ MDI bias, dùng permutation importance làm chuẩn.

Ưu điểm:

• Baseline rất mạnh cho tabular data — thường nằm trong top 3 ứng viên cùng Gradient Boosting.
• Capture được quan hệ phi tuyến và interaction giữa feature mà không cần feature engineering thủ công.
• Không cần scale (giống tree đơn).
• Robust với outlier — vote/average che giấu ảnh hưởng của vài tree bị nhiễu.
• OOB score thay được cross-validation, tiết kiệm thời gian.
• Embarrassingly parallel — scale theo số core.
• Cho feature importance ổn định hơn single tree.

Nhược điểm:

• Mất tính interpretability của single tree — không vẽ được "luật if-else" rõ ràng nữa, chỉ có importance tổng hợp.
• Inference chậm: với n_estimators=100, predict tốn ~100 lần một tree đơn. Quan trọng khi latency thấp (real-time bidding, mobile inference).
• RAM tốn: lưu \( K \) tree đầy đủ. Tree sâu × 100 → vài chục MB tới hàng GB.
• Extrapolation kém (regression): predict bị chặn trong khoảng \( [\min y_{train}, \max y_{train}] \) — giống tree.
• Trên dataset rất lớn, Gradient Boosting (Bài 30) thường vượt RF cả về accuracy lẫn kích thước model.

• Accuracy: RF gần như luôn vượt single tree trên cùng dataset, đặc biệt khi tree đơn overfit.
• Variance: RF có variance thấp hơn nhiều — chạy lại với seed khác, kết quả chênh nhỏ.
• Train time: RF chậm hơn ~\( K \) lần (với n_estimators=K), nhưng song song hoá với n_jobs=-1 nên thực tế chỉ chậm hơn vài lần.
• Inference time: chậm hơn ~\( K \) lần, không song song bằng training (mỗi prediction phải đi qua tất cả tree).
• Interpretability: single tree visualize được; RF chỉ có feature importance.
• Hyperparameter: RF ít nhạy với tuning hơn — default thường chạy được; single tree phải tune max_depth/min_samples_leaf cẩn thận.

Khi nào nên dùng single tree thay vì RF: khi cần giải thích quyết định cho người không kỹ thuật (luật if-else), khi latency cực thấp, hoặc khi dataset rất nhỏ và model cần đơn giản. Còn lại — RF hầu như luôn là lựa chọn tốt hơn.

• n_estimators — thêm tree không bao giờ làm model tệ đi (chỉ làm chậm và tốn RAM). Diminishing return rõ: 100 → 200 cải thiện vài %, 500 → 1000 thường không đáng kể. Bắt đầu với 100–200, chỉ tăng khi cần thêm chút ổn định.
• max_depth — default None (mọc hết) thường ổn. Set giới hạn nếu RAM/inference time là vấn đề, hoặc nếu OOB score chỉ ra overfit.
• max_features — "sqrt" default đã được tuning bài bản qua nhiều benchmark. Có thể grid search ["sqrt", "log2", 0.5, 0.3] nếu muốn cuối cùng.
• min_samples_leaf — tăng (vd 5, 10) để regularize thêm khi dataset có noise nhiều.

GridSearchCV với Random Forest tốn tài nguyên (nhân với 5–10 fold × nhiều giá trị × n_estimators tree). Thực tế:

• Dùng OOB score thay vì CV để duyệt sơ bộ (tốn 1/5 thời gian).
• RandomizedSearchCV thay vì grid khi nhiều hyperparameter.
• Cố định n_estimators ở giá trị vừa phải khi tune các tham số khác, rồi tăng n_estimators ở cuối để thêm ổn định.

• Baseline mặc định cho tabular data — bắt đầu mọi project ML tabular với RF để có con số tham chiếu. Nếu RF chỉ đạt 60% accuracy thì bài toán khó, đừng kỳ vọng XGBoost lên 90%.
• Feature importance analysis — RF cho importance ổn định để filter feature trước khi tune model phức tạp.
• Banking risk scoring — credit default, fraud detection. Yêu cầu robust, không cần latency cực thấp, hỗ trợ feature importance để giải trình.
• Bioinformatics — gene expression classification, biomarker discovery. Dataset thường có nhiều feature \( d \gg n \), Random Forest xử lý tốt nhờ random feature subset.
• Telco churn, marketing response — phân loại với feature hỗn hợp số và categorical.
• Land cover classification trên ảnh vệ tinh (mỗi pixel là sample với feature spectral) — RF là chuẩn industry suốt một thập kỷ.

Demo trên breast cancer dataset (569 sample, 30 feature, binary).

import numpy as np
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier
from sklearn.ensemble import RandomForestClassifier
from sklearn.metrics import accuracy_score, roc_auc_score

data = load_breast_cancer()
X, y = data.data, data.target
feature_names = data.feature_names

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

# Single Decision Tree de so sanh
tree = DecisionTreeClassifier(random_state=42)
tree.fit(X_train, y_train)
tree_acc = accuracy_score(y_test, tree.predict(X_test))
tree_auc = roc_auc_score(y_test, tree.predict_proba(X_test)[:, 1])
print(f"DecisionTree   acc={tree_acc:.4f}  auc={tree_auc:.4f}")

# Random Forest, bat OOB
rf = RandomForestClassifier(
    n_estimators=200,
    max_depth=None,
    oob_score=True,
    random_state=42,
    n_jobs=-1,
)
rf.fit(X_train, y_train)
rf_acc = accuracy_score(y_test, rf.predict(X_test))
rf_auc = roc_auc_score(y_test, rf.predict_proba(X_test)[:, 1])
print(f"RandomForest   acc={rf_acc:.4f}  auc={rf_auc:.4f}")
print(f"OOB score:     {rf.oob_score_:.4f}  (uoc luong test acc)")

Đọc feature importance (MDI):

importances = rf.feature_importances_
order = np.argsort(importances)[::-1]
print("\nTop 10 feature theo MDI:")
for i in order[:10]:
    print(f"  {feature_names[i]:30s} {importances[i]:.4f}")

Kết quả điển hình: RF đạt accuracy ~0.96–0.97 và AUC ~0.99 trên test, single tree thường ~0.92–0.94. OOB score sai lệch test accuracy chỉ vài phần nghìn — đủ để dùng làm proxy cho CV trong quá trình tune.

Bài 1 — Ảnh hưởng của n_estimators. Trên breast cancer, train RandomForestClassifier lần lượt với n_estimators = 10, 100, 500, random_state=42, n_jobs=-1. Đo (a) accuracy test, (b) thời gian train bằng time.perf_counter(). Vẽ biểu đồ accuracy theo \( K \) và time theo \( K \). Accuracy có cải thiện liên tục không, hay bão hoà sau ngưỡng nào?

Bài 2 — Permutation importance. Train RandomForestClassifier(n_estimators=200, random_state=42) trên breast cancer. Tính:

• Top 10 feature theo rf.feature_importances_ (MDI).
• Top 10 feature theo permutation_importance(rf, X_test, y_test, n_repeats=20).

So sánh hai bảng. Có feature nào xếp cao ở MDI nhưng thấp ở permutation hoặc ngược lại? Đề xuất lý do.

Bài 3 — Bagging vs Random Forest. Train hai model trên breast cancer, cùng n_estimators=200:

• Model A: RandomForestClassifier(bootstrap=False, max_features=None, ...) — gần với bagging-less + dùng full feature mỗi split → các tree gần như giống hệt.
• Model B: RandomForestClassifier(bootstrap=True, max_features="sqrt", ...) — RF mặc định.
• Model C: RandomForestClassifier(bootstrap=True, max_features=None, ...) — bagging thuần, không random feature.

So sánh accuracy test và OOB score (chỉ bật được khi bootstrap=True). Random feature đóng góp bao nhiêu so với chỉ bagging?

Bài 4 — Đo correlation giữa các tree. Với RF 50 tree trên breast cancer, lấy rf.estimators_[k].predict_proba(X_test)[:, 1] cho \( k = 0, \ldots, 49 \) → ma trận shape (50, n_test). Tính ma trận tương quan Pearson giữa các tree (shape (50, 50)), in trung bình tương quan ngoài đường chéo. Lặp lại với max_features=None (bagging thuần). Trung bình tương quan nào cao hơn? Phù hợp với lý thuyết "random feature decorrelate trees" không?

Bài 5 — RF với class imbalanced. Tạo dataset imbalanced bằng make_classification(n_samples=2000, weights=[0.95, 0.05], random_state=42). Train hai model: RandomForestClassifier() mặc định và RandomForestClassifier(class_weight="balanced"). So sánh accuracy, recall của class minority, F1. class_weight="balanced" có cải thiện không?

Bài 30: Gradient Boosting và XGBoost — ensemble theo hướng boosting: train tuần tự, mỗi tree mới sửa lỗi của tổng các tree trước. Khác biệt cốt lõi so với bagging, vì sao boosting thường thắng RF trên tabular data, và XGBoost — implementation thực tế chuẩn industry suốt 10 năm.