第十二讲 · 随机森林 | L.D.J 的私家工坊

一棵深决策树很会“因材施教”，也很容易把训练集中的偶然噪声当规律。随机森林的办法不是把一棵树修得无比完美，而是训练许多彼此有差异的树，再让它们共同决定答案。

要让集成有效，只有“树多”还不够：单棵树要有一定能力，同时树与树不能犯完全相同的错误。 随机森林用随机样本和随机特征降低树之间的相关性。

一、从决策树到随机树

普通决策树在每个节点遍历候选特征和切分阈值，选择信息增益最大的切分。分类数据集 $S$ 的熵为

H(S)=-\sum_c p_c\log_2p_c,

候选切分把数据分为 $S_L,S_R$ ，信息增益是

IG=H(S)-\frac{|S_L|}{|S|}H(S_L)-\frac{|S_R|}{|S|}H(S_R).

随机树不会在所有可能特征上追求唯一最优，而是先随机抽取一小组候选特征或切分函数，再从其中挑最好的。课件用二维点为例：随机生成若干直线 $f(v)=a x+b y$ 和阈值，保留信息增益最大的一条，然后对子节点递归。

这会牺牲一点单棵树的最优性，却能让不同树走出不同的划分路径。

二、随机森林的两层随机性

1. Bootstrap 样本

从 $n$ 个训练样本中有放回抽取 $n$ 次，得到一棵树的训练集。某些样本会重复，另一些不会被抽中。重复为不同树制造数据差异，未被抽中的样本称为这棵树的袋外样本（Out-of-Bag，OOB）。

单个样本一次不被抽中的概率是 $1-1/n$ ，连续 $n$ 次都没被抽中的概率为

\left(1-\frac1n\right)^n\approx e^{-1}\approx36.8\%.

所以每棵树大约能用其余三分之一的训练数据做近似验证。

课件伪代码写作将训练数据随机分成可重叠子集；标准随机森林中最常见的具体实现就是 Bootstrap。

2. 节点随机特征

假设总共有 $d$ 个特征，每个节点只随机考虑其中 $m$ 个。分类常用 $m\approx\sqrt d$ ，回归常用 $m\approx d/3$ ，但最佳值仍需验证。

$m$ 太大：单树更强，但树之间更相似；
$m$ 太小：相关性更低，但单树可能太弱。

这就是课件所说的随机性参数：要在“树的能力”和“树的差异”之间平衡。

三、训练与预测流程

训练 $T$ 棵树时，对每棵树独立执行：

Bootstrap 抽取训练样本；
在每个节点随机抽取候选特征；
从候选中选信息增益最大或不纯度下降最大的切分；
递归生长，通常不做强剪枝。

分类时，第 $t$ 棵树在叶节点给出类别分布 $P_t(c\mid x)$ ，森林平均为

P(c\mid x)=\frac1T\sum_{t=1}^T P_t(c\mid x), \qquad c^*=\arg\max_c P(c\mid x).

若叶子只输出一个类别，这就退化为多数投票。回归任务则直接平均各树的数值预测。

一个完整投票例子

三棵树对样本 $x$ 给出类别分布：

树	猫	狗	鸟
$t_1$	0.8	0.1	0.1
$t_2$	0.2	0.7	0.1
$t_3$	0.6	0.3	0.1

平均后为

P(c\mid x)=(0.533,0.367,0.100),

因此预测“猫”。虽然第二棵树更支持“狗”，其错误被另外两棵树抵消。

四、为什么平均许多树会更稳

把每棵树的预测误差看成方差为 $\sigma^2$ 、任意两棵树误差相关系数为 $\rho$ ， $T$ 棵树平均后的方差近似为

\operatorname{Var}(\bar f) =\rho\sigma^2+\frac{1-\rho}{T}\sigma^2.

增加树数 $T$ 只能压低第二项；若所有树高度相关，第一项仍然很大。因此随机样本和随机特征不是装饰，而是让 $\rho$ 下降的核心。

这也解释两个常见现象：

树数增加后测试误差通常趋于稳定，而不是像单棵深树那样继续剧烈过拟合；
完全相同的树复制再多遍也没有收益。

五、OOB 评估与特征重要性

OOB 误差

对每个训练样本，只汇总“训练时没见过它”的那些树的预测，再与真实标签比较。这样无需额外划分验证集，就能得到 OOB 误差估计。

两类常见特征重要性

不纯度下降重要性：累计某特征用于分裂时带来的 Gini 或熵下降；计算便宜，但可能偏爱可切分值较多的特征。
置换重要性：在 OOB 或验证数据中随机打乱一个特征，观察性能下降多少；更接近“模型真正依赖它多少”，但相关特征会相互替代，解释时要谨慎。

重要性表示模型在当前数据上的依赖，不等于因果关系。

六、与 AdaBoost 的关系

随机森林属于 Bagging 思路：树之间可并行训练，最后平均，主要降低方差。AdaBoost 是 Boosting：后一轮根据前一轮错误改变样本权重，必须串行，主要逐步修正偏差和难样本。

课件还比较了视觉检测中的级联 Boosting 与随机森林：级联往往是高度不平衡的拒绝树，适合海量背景窗口；随机森林的树通常更平衡，天然适合多类分类。

七、课件中的视觉应用

随机森林既可分类，也可回归、聚类或输出结构化预测。课件列出手写数字识别、关键点识别、视觉词聚类、语义分割、姿态估计、器官检测和三维点云分类。

Kinect 人体跟踪是典型例子：输入深度图，为每个像素提取与邻域深度差相关的特征，森林预测身体部位标签，再从像素标签恢复关节点。这个案例展示了随机森林的优势：多类输出、快速推理、特征测试简单，适合当时的实时设备。

八、常见误区与 sanity check

随机森林不是一棵“随机乱切”的树。 每个节点仍从随机候选中选择质量最好的切分。
样本随机与特征随机作用不同。 前者改变每棵树看到的数据，后者直接降低树间相关性。
分类概率要除以树数。 平均后的各类别概率应非负且总和约为 $1$ 。
树越多通常越稳，但收益会饱和。 若验证误差不再下降，应检查特征、数据和树相关性，而不是无限加树。
特征重要性不是因果解释。 高重要性只说明这个森林在当前数据和训练设置下频繁或有效地用了它。

第十二讲 · 随机森林