Luminosity

外观

第五讲：决策树与随机森林

约 2425 字大约 8 分钟

Machine LearningDecision TreeRandom Forest

本文由 GPT-5.6-sol 完成。

决策树把预测写成一串可读的判断：先问一个问题，根据答案进入不同分支，再继续提问，直到叶节点给出结论。它不要求特征与标签之间满足线性关系，也能自然表达变量之间的交互。

不过，“每次选择最好的问题”并不自动得到全局最优的树。本讲的关键是理解三件事：怎样衡量一次划分的好坏，为什么树会过拟合，以及为什么许多彼此不同的树合在一起反而更可靠。

一、树模型的基本结构

一棵决策树由三类节点组成：

  • 根节点包含全部训练样本；
  • 内部节点根据某个特征测试把样本分到子节点；
  • 叶节点输出类别、概率或回归值。

训练通常采用自顶向下的贪心递归：在当前节点枚举候选划分，选择使子节点更“纯”的一个，然后对子节点重复。由于搜索所有树结构是组合优化问题，实际算法并不保证找到全局最优树。

二、怎样衡量节点纯度

设节点 DD 中共有 KK 类样本，第 kk 类比例为 pkp_k。

1. 分类错误率

若叶节点预测为多数类，则误分类率为

Ierror(D)=1−max⁡kpk.I_{\mathrm{error}}(D)=1-\max_k p_k.

它含义直接，但对类别比例的小变化不够敏感，因此较少用来指导逐步分裂。

2. 信息熵

H(D)=−∑k=1Kpklog⁡2pk.H(D)=-\sum_{k=1}^K p_k\log_2 p_k.

节点只有一个类别时熵为零；类别越均匀，熵越大。若按特征 AA 分成 D1,…,DmD_1,\ldots,D_m，条件熵为

H(D∣A)=∑j=1m∣Dj∣∣D∣H(Dj).H(D\mid A)=\sum_{j=1}^m \frac{|D_j|}{|D|}H(D_j).

信息增益定义为

Gain⁡(D,A)=H(D)−H(D∣A).\operatorname{Gain}(D,A) =H(D)-H(D\mid A).

它测量得知划分结果后，标签不确定性减少了多少。

3. Gini 不纯度

Gini⁡(D)=1−∑k=1Kpk2.\operatorname{Gini}(D) =1-\sum_{k=1}^Kp_k^2.

可以把它理解为：按节点中的类别分布随机给一个样本贴标签，标签错误的概率。一次划分后的加权不纯度是

Gini⁡split=∑j=1m∣Dj∣∣D∣Gini⁡(Dj).\operatorname{Gini}_{\mathrm{split}} =\sum_{j=1}^m\frac{|D_j|}{|D|} \operatorname{Gini}(D_j).

熵与 Gini 往往给出相近的分裂结果。真正影响树结构的，不只是公式名称，还包括候选阈值、缺失值处理、停止规则与剪枝策略。

三、ID3：最大化信息增益

ID3 在每个节点选择信息增益最大的离散特征：

A∗=arg⁡max⁡AGain⁡(D,A).A^*=\arg\max_A\operatorname{Gain}(D,A).

若节点样本属于同一类别、没有特征可用，或继续划分的收益太小，就停止递归并建立叶节点。

信息增益有一个明显偏好：取值很多的特征容易把样本切成大量小分支，从而获得很高的训练纯度。例如“学号”几乎可以一人一个分支，却没有可泛化的预测意义。这不是信息论出了问题，而是纯粹追求训练条件熵所付出的复杂度代价没有被计入。

四、C4.5：对多值特征做校正

1. 信息增益率

C4.5 引入划分本身的内在信息

IV⁡(A)=−∑j=1m∣Dj∣∣D∣log⁡2∣Dj∣∣D∣,\operatorname{IV}(A) =-\sum_{j=1}^m \frac{|D_j|}{|D|} \log_2\frac{|D_j|}{|D|},

并定义增益率

GainRatio⁡(D,A)=Gain⁡(D,A)IV⁡(A).\operatorname{GainRatio}(D,A) =\frac{\operatorname{Gain}(D,A)} {\operatorname{IV}(A)}.

分支过多时 IV⁡(A)\operatorname{IV}(A) 较大，增益率会对其施加惩罚。实践中通常先筛选信息增益不低的特征，再比较增益率，避免一味偏向分支极少的划分。

2. 连续特征

对连续特征 AA，先将观测值排序，在相邻取值之间选择候选阈值 tt，形成二分：

D≤t={x:A(x)≤t},D>t={x:A(x)>t}.D_{\le t}=\{x:A(x)\le t\}, \qquad D_{>t}=\{x:A(x)>t\}.

然后像离散划分一样计算增益或增益率。一个连续特征可以在树的不同位置重复使用，因为不同分支对应不同的局部区间。

3. 缺失值与特征代价

训练时可用非缺失样本估计划分质量，再按各分支的样本比例把缺失样本的权重分配下去；预测时也可以沿多个分支传播概率权重。若不同特征的获取成本差异很大，还可把收益与测试成本共同纳入选择标准。

五、CART：统一的二叉树框架

CART 即 Classification and Regression Trees。无论特征类型如何，CART 都构造二叉树。

1. 分类树

分类 CART 通常选择使加权 Gini 不纯度最小的划分：

(A∗,t∗)=arg⁡min⁡A,t[∣DL∣∣D∣Gini⁡(DL)+∣DR∣∣D∣Gini⁡(DR)].(A^*,t^*) =\arg\min_{A,t} \left[ \frac{|D_L|}{|D|}\operatorname{Gini}(D_L) +\frac{|D_R|}{|D|}\operatorname{Gini}(D_R) \right].

对离散特征，本质上是在寻找类别取值集合的二分；对连续特征，则寻找阈值。

2. 回归树

回归树在每个叶节点输出该区域标签的均值。若候选划分产生区域 DL,DRD_L,D_R，目标是最小化区域内平方误差：

∑xi∈DL(yi−yˉL)2+∑xi∈DR(yi−yˉR)2.\sum_{x_i\in D_L}(y_i-\bar y_L)^2 +\sum_{x_i\in D_R}(y_i-\bar y_R)^2.

因此回归树学习的是分段常数函数。单棵树的预测会在分裂边界处跳变，这既赋予它表达非线性交互的能力，也使它对训练样本扰动较敏感。

六、树为什么容易过拟合

若不限制生长，树可以不断分裂，直至叶节点只剩一个或很少样本。训练误差会持续下降，但许多分裂只是在记忆噪声。

1. 预剪枝

在生长过程中提前停止，例如设置：

  • 最大深度；
  • 叶节点最少样本数；
  • 内部节点最少样本数；
  • 最小不纯度下降；
  • 最大叶节点数。

预剪枝计算便宜，却可能因一次短视的停止而错过后续有价值的组合划分。

2. 后剪枝与代价复杂度

先生长较完整的树，再从底部删除收益不足的子树。CART 常用代价复杂度目标

Rα(T)=R(T)+α∣T∣,R_\alpha(T)=R(T)+\alpha|T|,

其中 R(T)R(T) 是叶节点经验误差，∣T∣|T| 是叶节点数，α\alpha 控制对复杂结构的惩罚。可以生成一系列嵌套子树，再用验证集或交叉验证选择 α\alpha。

从学习理论看，叶节点越多、树越深，可实现的标记方式越丰富。剪枝就是在经验拟合与结构复杂度之间做显式权衡。

七、Bootstrap 与 Bagging

单棵深树通常偏差低、方差高。Bagging 的想法是：训练许多有差异的模型，再把它们平均。

对大小为 nn 的训练集，Bootstrap 每次有放回抽取 nn 个样本。某个样本一次都没被抽中的概率为

(1−1n)n⟶e−1≈36.8%.\left(1-\frac1n\right)^n \longrightarrow e^{-1}\approx36.8\%.

所以每个 Bootstrap 数据集大约包含原训练集 63.2%63.2\% 的不同样本。第 bb 个数据集训练模型 hbh_b 后，分类使用多数投票

H(x)=mode⁡{h1(x),…,hB(x)},H(x)=\operatorname{mode} \{h_1(x),\ldots,h_B(x)\},

回归则使用平均

H(x)=1B∑b=1Bhb(x).H(x)=\frac1B\sum_{b=1}^Bh_b(x).

平均能够有效降低方差，但前提是基学习器的错误不能完全同步。若所有树高度相关，再多的平均也难以获得显著收益。

袋外估计

对每棵树而言，未进入其 Bootstrap 样本的数据称为袋外（out-of-bag, OOB）样本。只用那些没有见过样本 ii 的树来预测 ii，即可得到近似验证误差，无需额外划分验证集。OOB 还可用于估计特征重要性，但重要性数值可能受高基数特征与相关特征影响，不能直接解释为因果作用。

八、随机森林：不仅随机样本，还随机特征

随机森林在 Bagging 的基础上再加入一层随机性：每个节点分裂时，只从随机抽取的特征子集里寻找最佳划分。

典型流程是：

  1. 对每棵树生成一个 Bootstrap 数据集；
  2. 生长一棵通常不剪枝的深树；
  3. 每个节点随机抽取 mtrym_{\mathrm{try}} 个特征；
  4. 只在这些特征中选择最佳分裂；
  5. 对全部树投票或平均。

分类任务常以 d\sqrt d 作为 mtrym_{\mathrm{try}} 的起点，但它只是经验默认值，应结合验证结果调整。

随机特征会略微削弱单棵树，却能降低树之间的相关性。若单棵树方差为 σ2\sigma^2、两两相关系数近似为 ρ\rho，BB 棵树平均的方差约为

\operatorname{Var}(\bar h) =\rho\sigma^2+ rac{1-\rho}{B}\sigma^2.

当 B→∞B\to\infty 时，第二项消失，残余方差仍由 ρ\rho 决定。这条式子清楚地说明：随机森林的关键不只是“树多”，更是设法让树彼此不同，同时保留足够的单树预测能力。

九、小结

决策树的主线可以概括为

不纯度⟶贪心划分⟶复杂度控制⟶重采样与平均⟶随机森林.\text{不纯度} \longrightarrow \text{贪心划分} \longrightarrow \text{复杂度控制} \longrightarrow \text{重采样与平均} \longrightarrow \text{随机森林}.

ID3、C4.5 与 CART 的差异集中在划分准则、分支形式和剪枝方式；Bagging 则换了一个层次，不再执着于找到一棵完美的树，而是利用多个高方差模型的平均来获得稳定预测。对树模型而言，深度决定单树的表达能力，随机性决定树之间的差异，二者共同决定森林的效果。

更新日志

2026/9/27 10:05
查看所有更新日志
  • eea03-update 0927 japaneseVocabulary.js于

版权归属：Luminosity

许可证：署名-非商业性-相同方式共享 4.0 国际 (CC-BY-NC-SA-4.0)

Powered by VuePress and Plume Theme
Copyright © 2026.08.03 Luminosity