Day 9｜决策树与随机森林:从「if-else 树」到「民主投票箱」（AI 学习笔记 · 经典机器学习周 · 第 9 篇）

决策树把分类/回归问题拆成一连串「是 / 否」问题,像 20 问游戏——可解释、可视化、白盒模型。但单棵树方差大、易过拟合。随机森林用「多棵树 + Bagging + 特征随机」三个独立机制把单棵树的方差压下来,几乎成为表格数据的默认 baseline——Kaggle 80% 的表格赛冠军都从它起步。

1. 决策树:递归二分特征空间

1.1 一棵树的生长过程

从根节点出发,每一步:

1. 遍历所有特征 f 和候选阈值 t,计算「按 (f ≤ t) 切分后,左右子节点的纯度提升」
2. 选提升最大的 (f, t),把当前节点切成两个子节点
3. 在每个子节点上递归继续,直到满足停止条件(max_depth / min_samples_leaf / 纯度)

叶子节点给出预测:分类任务 = 多数类;回归任务 = 均值。

1.2 直观:20 问游戏

判断「今天打不打网球」:

Outlook = Sunny ?
├── Yes → Humidity 高 ?
│         ├── Yes → 不打
│         └── No  → 打
└── No  → Wind 强 ?
          ├── Yes → 不打
          └── No  → 打

每个内部节点问一个特征,每条路径对应一个 if-else 规则。树的深度 = 最长路径的问答数。

1.3 为什么决策树至今仍被使用

• 可解释:整棵树就是 if-else,业务方能直接看
• 无需特征标准化:不依赖距离/梯度
• 处理异质特征:数值 + 类别混用都行
• 能捕捉非线性关系 + 特征交互
• 预测快:O(树深度)

代价:单棵树方差大、训练数据小变化可能结构大变 → 集成(随机森林 / GBDT)登场。

1.4 回归树 vs 分类树

2. 不纯度度量:熵、Gini、信息增益

2.1 信息熵(Entropy)

H(p) = -\sum_{k=1}^{K} p_k \log_2 p_k

• 衡量节点里类别有多「乱」
• 最纯(只有 1 类):H = 0
• 最乱(K 类均匀):H = log₂ K
• 例子:[50 正, 50 负] 的 H = 1.0;[100 正, 0 负] 的 H = 0

2.2 Gini 不纯度

\text{Gini}(p) = 1 - \sum_{k=1}^{K} p_k^2

• 同样衡量混乱度,曲线和熵几乎重合
• 二分类时 Gini = 2p(1−p),是熵的泰勒一阶近似
• 不算 log,计算更快 1 个量级
• sklearn 默认用 Gini

2.3 三种不纯度对比

2.4 信息增益(ID3)

\text{Gain}(f, t) = H(\text{parent}) - \frac{N_L}{N} H(L) - \frac{N_R}{N} H(R)

切分后不纯度下降越多,信息增益越大,特征越有用。

缺陷:ID3 对「取值多的特征」有偏心——比如「身份证号」可以把每个样本单独切到子节点,Gain 极大但毫无泛化能力。

2.5 增益率(C4.5)

C4.5 用「信息增益率」修正:

\text{GainRatio} = \frac{\text{Gain}(f, t)}{\text{SplitInfo}(f, t)}

\text{SplitInfo}(f, t) = -\sum \frac{N_i}{N} \log_2 \frac{N_i}{N}

归一化掉了「切得越碎 Gain 越大」的偏心。

2.6 CART 的 Gini 选择

CART 总是二分裂,选 Gini 下降最大的 (f, t)。Gini 计算比熵快且数学性质接近,工业界首选。sklearn 的 DecisionTreeClassifier 默认 criterion=’gini’。

2.7 三种算法的工程取舍

3. 剪枝:防止过拟合

3.1 过拟合表现

树在训练集上完美(每个叶子纯度 100%),但在测试集上塌方——典型的「过拟合」,学到了训练集的噪声。

3.2 预剪枝(Pre-pruning)

边长树边限:

• max_depth:最大深度,常用 5~10
• min_samples_split:节点最少样本数才继续分裂
• min_samples_leaf:叶子最少样本数
• min_impurity_decrease:分裂必须带来的最小不纯度下降
• max_leaf_nodes:最多叶子数

优点:训练快、防过拟合;缺点:贪心、可能欠拟合。

3.3 后剪枝(Post-pruning)

先长满一棵树,再用验证集把没用的子树「合并回去」:

C_\alpha(T) = \text{Loss}(T) + \alpha \cdot |T|

|T| = 叶子数,α 控制复杂度惩罚。sklearn 用 cost-complexity pruning(CCP):

clf = DecisionTreeClassifier(random_state=42)
path = clf.cost_complexity_pruning_path(X_train, y_train)
for ccp_alpha in path.ccp_alphas:
    clf_t = DecisionTreeClassifier(random_state=42, ccp_alpha=ccp_alpha)
    clf_t.fit(X_train, y_train)
    # 用验证集挑最佳 α

优点:不贪心、效果上限高;缺点:训练慢一截(需先长满)。

3.4 预剪枝 vs 后剪枝对比

3.5 信用卡欺诈检测:为什么后剪枝更稳

信用卡欺诈正样本 < 0.1%,严重不平衡。预剪枝可能在「欺诈模式还没充分暴露」时就停手,导致召回率塌方。后剪枝靠验证集兜底,能更好保留稀有模式的细节。

4. 随机森林:Bagging + 特征随机

4.1 核心思想

单棵树方差大 → 训练 N 棵树「投票」降方差。N 棵树去相关是关键,Bagging 和特征随机是两条独立去相关路径:

\hat{y} = \text{mode}\{T_1(x), T_2(x), ..., T_N(x)\}

N 棵树投票(分类)或取均值(回归)。

4.2 Bagging(样本随机)

每棵树从训练集中有放回地抽 N 个样本(bootstrap 采样)。大约 37% 样本不会被抽到,这就是 OOB(Out-of-Bag)样本。

直觉:每棵树看到的「世界」略有不同,学到的模式不同,集成后多样性高。

4.3 特征随机(column subsampling)

每棵树在每个分裂节点只看随机 m 个特征,而不是全部 d 个:

• 分类:m = √d (sklearn 默认 max_features='sqrt')
• 回归:m = d / 3

直觉:防止最强特征垄断每棵树的根节点分裂。

4.4 为什么两个随机都必要

只看 Bagging 不做特征随机:

所有树都会优先用最强特征(比如「信用分」)在根节点分裂,树之间高度相关,Bagging 的方差下降打折扣。

加入特征随机后:

每棵树被迫学「非主流特征」的判别力,多样性显著提升,泛化能力增强。

类比:一群同质化的「专家」(都看信用分)vs 一群异质化的「专家」(有的看信用分、有的看收入、有的看负债),后者的「三个臭皮匠」效应强得多。

4.5 OOB 估计:免费 CV

每棵树有 ~37% 的样本没被抽到,直接当验证集:

from sklearn.ensemble import RandomForestClassifier

clf = RandomForestClassifier(n_estimators=300, oob_score=True, random_state=42)
clf.fit(X_train, y_train)
print(clf.oob_score_)  # OOB 准确率,等价于一次交叉验证

优点:省下一次完整 CV 耗时,适合大 N 数据集。

4.6 两种特征重要性

from sklearn.inspection import permutation_importance

# MDI(内置)
importances = clf.feature_importances_

# Permutation importance
result = permutation_importance(clf, X_test, y_test, n_repeats=10, random_state=42)
sorted_idx = result.importances_mean.argsort()

4.7 超参数速查

5. PyTorch / sklearn 实战

5.1 sklearn:RandomForest 跑 Titanic

import pandas as pd
import numpy as np
from sklearn.ensemble import RandomForestClassifier
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score, classification_report

# 假设已加载 Titanic 数据 + 预处理(Pclass/Sex/Age/Fare/Embarked)
df = pd.read_csv('titanic.csv')
X = df[['Pclass', 'Sex', 'Age', 'Fare', 'Embarked']].copy()
X['Sex'] = (X['Sex'] == 'male').astype(int)
X['Age'] = X['Age'].fillna(X['Age'].median())
X['Embarked'] = X['Embarked'].fillna('S')
X = pd.get_dummies(X, columns=['Embarked'], drop_first=True)
y = df['Survived']

X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.2, random_state=42, stratify=y)

rf = RandomForestClassifier(n_estimators=300, max_features='sqrt',
                            min_samples_leaf=3, oob_score=True, n_jobs=-1, random_state=42)
rf.fit(X_tr, y_tr)

print(f"OOB score:    {rf.oob_score_:.4f}")
print(f"Test accuracy: {accuracy_score(y_te, rf.predict(X_te)):.4f}")
print(classification_report(y_te, rf.predict(X_te)))

预期:OOB ≈ 0.81,Test ≈ 0.82~0.84(Titanic 的经典区间)。

5.2 特征重要性可视化

import matplotlib.pyplot as plt

# MDI
mdi = pd.Series(rf.feature_importances_, index=X.columns).sort_values(ascending=True)

fig, axes = plt.subplots(1, 2, figsize=(14, 5))

mdi.plot(kind='barh', ax=axes[0], color='steelblue')
axes[0].set_title('MDI Feature Importance')
axes[0].set_xlabel('Mean Decrease Impurity')

# Permutation
from sklearn.inspection import permutation_importance
result = permutation_importance(rf, X_te, y_te, n_repeats=10, random_state=42)
perm = pd.Series(result.importances_mean, index=X.columns).sort_values(ascending=True)
perm.plot(kind='barh', ax=axes[1], color='coral')
axes[1].set_title('Permutation Importance')
axes[1].set_xlabel('Accuracy drop after shuffling')

plt.tight_layout()
plt.show()

Top-3 通常是 Sex / Fare / Pclass——业务上完全合理(妇女儿童优先、票价反映舱位、舱位反映逃生位置)。

5.3 从零实现 CART(简化版)

import numpy as np

def gini(y):
    p = np.bincount(y) / len(y)
    return 1 - np.sum(p ** 2)


def best_split(X, y):
    best_gain, best_feat, best_thr = -1, None, None
    parent = gini(y)
    for feat in range(X.shape[1]):
        for thr in np.unique(X[:, feat]):
            left = y[X[:, feat] <= thr]
            right = y[X[:, feat] > thr]
            if len(left) == 0 or len(right) == 0:
                continue
            gain = parent - (len(left) * gini(left) + len(right) * gini(right)) / len(y)
            if gain > best_gain:
                best_gain, best_feat, best_thr = gain, feat, thr
    return best_feat, best_thr, best_gain


class Node:
    def __init__(self, feat=None, thr=None, left=None, right=None, value=None):
        self.feat = feat; self.thr = thr
        self.left = left; self.right = right
        self.value = value  # 叶子节点的预测


class CartTree:
    def __init__(self, max_depth=8, min_samples_leaf=2):
        self.max_depth = max_depth
        self.min_samples_leaf = min_samples_leaf

    def fit(self, X, y):
        self.root = self._grow(X, y, depth=0)

    def _grow(self, X, y, depth):
        if depth >= self.max_depth or len(y) < 2 * self.min_samples_leaf or gini(y) == 0:
            return Node(value=np.bincount(y).argmax())
        feat, thr, gain = best_split(X, y)
        if gain == 0:
            return Node(value=np.bincount(y).argmax())
        left_mask = X[:, feat] <= thr
        return Node(feat=feat, thr=thr,
                   left=self._grow(X[left_mask], y[left_mask], depth + 1),
                   right=self._grow(X[~left_mask], y[~left_mask], depth + 1))

    def predict(self, X):
        return np.array([self._traverse(x, self.root) for x in X])

    def _traverse(self, x, node):
        if node.value is not None:
            return node.value
        if x[node.feat] <= node.thr:
            return self._traverse(x, node.left)
        return self._traverse(x, node.right)


tree = CartTree(max_depth=6, min_samples_leaf=5)
tree.fit(X_tr.values, y_tr.values)
print(f"Hand-crafted CART acc: {accuracy_score(y_te, tree.predict(X_te.values)):.4f}")

预期:手写 CART 在 Titanic 上 ~0.78~0.82,略低于 sklearn 的 RF(~0.83),但结构和 sklearn 基本对齐。

5.4 网格搜 + 后剪枝

from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import GridSearchCV

param_grid = {
    'max_depth': [3, 5, 7, 10, None],
    'min_samples_leaf': [1, 3, 5, 10],
    'ccp_alpha': [0.0, 0.001, 0.005, 0.01],  # 后剪枝强度
}
grid = GridSearchCV(DecisionTreeClassifier(random_state=42),
                    param_grid, cv=5, scoring='accuracy', n_jobs=-1)
grid.fit(X_tr, y_tr)
print(f"Best params: {grid.best_params_}")
print(f"Best CV: {grid.best_score_:.4f}")
print(f"Test: {grid.score(X_te, y_te):.4f}")

ccp_alpha 是 sklearn 的 cost-complexity 后剪枝 α,α 越大剪得越狠。

6. vs 其他方法对比

6.1 决策树 vs RF vs Boosting

6.2 集成学习的两大流派

Bagging(Bootstrap AGGregatING):并行训 N 个独立模型,投票/平均。代表:随机森林。降方差。

Boosting:串行训,每棵新树去拟合前一棵的「错误」(残差 / 负梯度)。代表:AdaBoost / GBDT / XGBoost。降偏差。

直觉:Bagging 是「多个人独立答卷然后投票」,Boosting 是「一个学生反复纠错」。

6.3 RF vs Extra Trees

Extra Trees 用随机阈值,增加随机性 → 方差更低,适合极端噪声数据。

7. 常见坑

7.1 训练集和测试集分布不一致时 OOB 不准

症状:OOB score 虚高,实部署效果差 原因:OOB 来自训练集 bootstrap,如果有时间漂移 / 分布漂移,OOB 失效 修法:用 TimeSeriesSplit 或按业务分层采样做真实 CV,OOB 仅作快速 sanity check

7.2 类别特征直接当数值喂

症状:Sex=male=1, female=2, other=3 被决策树当作「other > male > female」的有序关系 修法:① 用 sklearn 的 OrdinalEncoder(树模型可接受);② 类别多时用 OneHotEncoder(树也能跑,只是分裂数增加);③ 树模型对有序类别用 ordinal,对名义类别用 onehot

7.3 max_depth=None 默认值让树长到 100% 训练准确率

症状:Train 99%,Test 70%,典型过拟合 修法:必须设 max_depth=5~15、min_samples_leaf=5+,或在网格搜里加约束

7.4 类别不平衡 RF 全预测多数类

症状:欺诈 / 罕见病 recall < 5% 修法:class_weight='balanced' 或者 SMOTE 过采样;评估用 PR-AUC 而非 accuracy

7.5 n_estimators 设 1000 但 n_jobs=-1 时内存爆

症状:MemoryError 或 swap 爆 修法:减小 n_jobs,或用 joblib.Parallel 流式训练

7.6 把 feature_importances_ 当因果

症状:「性别重要」→ 业务误判「性别是因果」 原因:MDI 只反映「对模型的贡献」,可能是相关性而非因果 修法:Permutation importance + SHAP,做因果推断要靠 A/B test 或因果图

7.7 决策树直接处理高维稀疏特征(如 TF-IDF)

症状:训练慢、效果差 原因:树对高维稀疏特征不友好,split 搜索爆炸 修法:稀疏高维走线性模型(LogReg / SVM + L2),密集低维走树

7.8 训练时间想降,但忘了 n_jobs=-1

症状:RF 训 10 分钟才发现是单核 修法:RF/ET 是 embarrassingly parallel,默认开 n_jobs=-1(全核)

7.9 预测时输入含 NaN

症状:sklearn 0.24+ 直接抛 ValueError 修法:RF 不原生支持 NaN,预处理用 SimpleImputer(中位数 / 众数);或换 xgboost(原生支持 NaN)

7.10 验证集 leak:用全部数据做特征选择再 split

症状:Test acc 虚高 5~10 个百分点 修法:先 train_test_split,再在训练集上做特征选择 / 网格搜,验证集独立评估

8. 自检三问

A. CART 用 Gini 而 ID3 用信息增益,这两者数学上什么关系?为什么工业界更爱 Gini?

要点:Gini 是熵在 p=0.5 附近的泰勒一阶近似:H(p) ≈ log₂ e · [2p(1−p)] ≈ 1.44 × Gini(p)。曲线几乎重合,但 Gini 不算 log,每次分裂计算快一个量级;sklearn / XGBoost 等工业实现全选 Gini。详见 §2.6 + §2.3。

B. 随机森林的「随机」体现在两个独立层面——样本层面的 Bagging 和特征层面的 column subsampling。如果只做 Bagging 不做特征随机,在「最强特征 + 弱相关特征」场景下会出什么问题?

要点:所有树都会优先用最强特征(比如「信用分」)在根节点分裂 → 每棵树的「骨架」几乎相同 → 树之间高度相关 → Bagging 的方差下降打折扣。加入特征随机后,每棵树被迫在「非最强特征」上找分裂,多样性显著提升。详见 §4.4。

C. 预剪枝 max_depth=3 vs 后剪枝让 full tree 收敛到 depth≈10,两种在偏差-方差谱上各在哪一端?为什么信用卡欺诈这种严重不平衡的数据集,后剪枝往往更稳?

要点:① 预剪枝深度浅 → 偏差高、方差低(欠拟合);后剪枝深度深 → 偏差低、方差略高(需 α 调平衡);② 信用卡欺诈正样本 < 0.1%,稀有模式需要足够深的树才能学到,预剪枝在「欺诈信号充分暴露前」就停手 → 召回率塌方;后剪枝靠验证集兜底能保留稀有模式细节。详见 §3.5。

9. 推荐资源

视频

• StatQuest《Decision Trees》《Random Forests》合集—— 图解最直观
• 李宏毅《机器学习》决策树章节—— 中文系统讲解
• Andrew Ng《Machine Learning Specialization》Week 4—— Bagging / Boosting
• CS229(Stanford)《Decision Trees and Ensemble Methods》—— 数学推导

教科书

• 《统计学习方法》(李航) 第 5 章—— 决策树 ID3 / C4.5 / CART
• **《机器学习》(周志华)》第 4 章—— 决策树 + 集成学习
• 《Hands-On Machine Learning》(Aurélien Géron) 第 6-7 章—— sklearn 实战
• 《The Elements of Statistical Learning》(Hastie et al.) 第 8 / 15 章—— 决策树 / RF 数学

论文

• Quinlan 1986《Induction of Decision Trees》—— ID3 起源
• Quinlan 1993《C4.5: Programs for Machine Learning》—— C4.5
• Breiman et al. 1984《CART》—— CART 算法 + cost-complexity 剪枝
• Breiman 2001《Random Forests》—— RF 原始论文,MDI 特征重要性
• Geurts et al. 2006《Extremely Randomized Trees》—— Extra Trees
• Louppe 2014《Understanding Random Forests》—— PhD 论文,数学最严谨

博客 / 课程

• Lilian Weng《Random Forest》—— 集成学习全景
• 《Interpretable ML》(Christoph Molnar)—— 特征重要性 + SHAP
• Distill.pub《Visualizing Representations》—— 树的可视化
• fast.ai 课程 Random Forest 章节—— 工程视角

代码

• sklearn.ensemble.RandomForestClassifier / Regressor—— 工业默认
• xgboost / lightgbm—— 表格数据 SOTA,内部用 CART 作基学习器
• ranger(C++ 实现)—— 高性能 RF,处理超大数据集
• SHAP—— 解释 RF 特征贡献,优于纯 MDI

10. 本节要点

• 决策树 = 递归二分特征空间,每个内部节点一个 (feature, threshold),叶子给出预测;白盒、可解释,但单棵方差大。
• 不纯度:熵 H = −Σ p log p(信息论)、Gini = 1 − Σ p²(快一档,sklearn 默认)、信息增益 = 父节点熵 − 加权子节点熵。
• 三种算法:ID3(信息增益,偏心)、C4.5(增益率,归一化)、CART(Gini,工业默认,二分裂)。

• 剪枝:预剪枝(便宜易欠拟合)vs 后剪枝(慢但稳,CCP α·

  T

  );不平衡数据后剪枝更稳。

• 随机森林 = N 棵决策树 + Bagging(bootstrap)+ 特征随机(m=√d),两路独立去相关,降方差。
• OOB 估计:每棵树的 ~37% 未抽到样本当验证集,免费 CV;MDI 和 Permutation 两种特征重要性互补。
• vs 单棵树 / GBDT:RF 降方差,GBDT 降偏差;RF 默认首选,GBDT Kaggle 冲榜。

11. 下一节:Day 10 · 梯度提升 XGBoost / LightGBM

主题:从 Bagging 的「并行降方差」翻转到 Boosting 的「串行降偏差」。覆盖:

• Boosting 核心:每棵新树去拟合前一棵的残差 / 负梯度,串行纠错
• Gradient Boosting 统一视角:损失 L,每轮学 fₜ 让 L(y, Fₜ₋₁(x)+fₜ(x)) 最小,fₜ ≈ −∂L/∂F
• XGBoost:二阶泰勒展开 + 正则化项(叶子数 + 叶子权重 L2),工程加速(近似分位直方图、稀疏感知)
• LightGBM 三大杀器:Histogram-based split + GOSS(单边梯度采样)+ EFB(互斥特征捆绑),比 XGBoost 快一个数量级

产出物:① 在 Titanic 上 XGBoost vs LightGBM 跑同一份数据,对比 AUC + 训练时间;② 用 SHAP 解释 XGBoost 预测,对比 Day 9 RF 的 MDI 重要性。

作者:林馨予 + 林晓月 最后更新:2026-07-04 版权:CC BY-NC-SA 4.0