15.2 随机森林的定义

自助聚合（bagging）的基本思想(第 8.7 节）是对多个噪声（方差）大但基本无偏差的模型做平均，从而降低方差。树模型是自助聚合的理想备选模型，因为它们能捕捉到数据之间复杂的交互结构，并且足够深的树就有相对低的偏差。由于众所周知树模型的噪声（方差）大，因此对它们的平均可获得很大的改进。而且因为自助聚合中的每个树模型是同分布的（i.d.），$B$ 个这些树模型的平均的期望与其中任意单个模型的期望一致。这意味着树模型自助聚合后的期望与单个（自助抽样）树模型的一样，而唯一的改进之处是缩减方差。这与提升方法是相反的，提升方法以一个自适应的方式训练树模型从而排除偏差，所以其中的树模型不是同分布的。

$B$ 个方差为 $\sigma^2$ 的独立同分布（i.i.d.）随机变量的平均数，方差为 $\frac{\sigma^2}{B}$。若这些变量只是同分布（分布相同，但不一定独立），假设两两之间有正相关系数 $\rho$，则平均数的方差是（练习 15.1）：

随着 $B$ 增大，第二项将趋于零，但第一项仍存在，所以自助聚合数模型之间相关性的大小限制了取平均带来的改进效果。随机森林（算法 15.1）的思想是在不过多增加方差的前提下，通过降低树模型之间的相关性来改进自助聚合带来的方差降低。这是通过在训练树模型的过程中进行输入变量的随机筛选实现的。具体来说，当在一个自助抽样数据集上训练树模型时：

在每次分割（split）前，从输入变量中随机选取 $m\leq p$ 个作为分割时的备选变量。

一般 $m$ 的取值为 $\sqrt{p}$ 或者甚至低至 1。

训练了 $B$ 个这样的树模型 $\{T(x;\Theta_b)\}_1^B$ 之后，随机森林（回归）预测函数为：

与第 10.9 节类似，$\Theta_b$ 为描述了第 $b$ 个随机树模型的参数，包括了分割特征变量、每个节点的分割点、和终节点上的取值。直观来说，降低 $m$ 就会降低集成模型中每两个树模型之间的相关性，因此通过 15.1 式得知也会降低平均值的方差。

算法 15.1 回归问题或分类问题的随机森林

1. 对每个 $b = 1,\dots,B$：
   1. 从训练集中抽取大小为 $N$ 的自助抽样 $\mathbf{Z}^*$。
   2. 在自助抽样数据上训练随机森林树模型 $T_b$，即对树模型的每个终节点循环地进行以下步骤操作，直到达成了最小节点大小 $n_\text{min}$。
      1. 从 $p$ 个特征变量中随机选择 $m$ 个特征变量。
      2. 在这 $m$ 个特征变量中选择最佳分割的特征变量和分割点。
      3. 将这个节点分割为两个子节点。
2. 输出树模型 $\{T_b\}_1^B$ 的集成（ensemble）。

对一个新数据点 $x$ 的预测则为：

• 回归问题：$\hat{f}_{rf}^B(x)=\frac{1}{B}\sum_{b=1}^BT_b(x)$
• 分类问题：记 $\hat{C}_b(x)$ 为第 $b$ 个随机森林树模型的类别预测结果。则 $\hat{C}_{rf}^B(x)=\operatorname{majority vote }\{\hat{C}_b(x)\}_1^B$。

并不是所有的估计方法都可以通过这样的数据处理来改进。看起来高度非线性的估计方法，比如树模型，最能从中受益。对于自助抽样的树模型来说，$\rho$ 一般比较小（通常为 0.05 或更小，可参考图 15.9），而 $\sigma^2$ 却并没有比原始的树模型方差增大多少。不过另一方面来说，自助聚合并不会对线性的估计量有改动，例如样本均值（以及样本均值的方差）；自助抽样均值两两之间的相关性大概为 50%（练习 15.4）。

随机森林方法非常流行。Leo Breiman¹ 的合作者 Adele Cutler 维护了一个关于随机森林的网站²，从中可免费获取软件（2002 年时已有 3000 次下载）。R 中有 randomForest 扩展包，由 Andy Liaw 维护，可从 CRAN 网站获取。

一些作者对随机森林的成就给予很高的评价，例如“最准确的”、“最可解释的”、等等。以我们的经验来看，随机森林效果非常地好，而且不需要进行太多调参。在垃圾邮件的测试集上，随机森林分类器达到了 4.88% 的误分类误差率，这好于大部分其他方法，并且只略差于梯度提升方法的 4.5%。自助聚合的误差率为 5.4%，要显著差于这两者（使用了练习 10.6 中介绍的 McNemar 测试方法），因此可见在这个例子里（随机森林中）额外的随机操作带来了改进。

图 15.1 展示了三个方法随着树模型个树增加至 2500 的测试误差率变化趋势。在这里梯度提升方法看起来存在一些过拟合，不过 10 折交叉验证仍然选择了全两的 2500 个树模型。

图 15.2 展示了在嵌套球形的模拟问题³中（第十章的 10.2 式）随机森林和梯度提升的对比结果。在这里提升方法很明显优于随机森林。注意到这里 $m$ 小的模型表现更好，不过一部分原因可能是因为真实的决策边界是加性的。

图 15.3 在一个回归问题中比较了随机森林和（有收缩的）提升方法，使用的是加利福尼亚州房屋数据（第 10.14.1 节）。能看出两个明显的结果：

• 随机森林在 200 个树模型后基本稳定，而提升方法在 1000 个树模型处仍在继续变好。收缩，以及更小的树模型，使提升方法的改进逐渐放缓。
• 在这里提升方法的表现好于随机森林。在 1000 个树模型处，较弱的提升模型（深度为 4 的 GBM）和较强的随机森林（$m=6$ 的 RF）相比误差率更小；两个误差绝对值的平均差值的 Wilcoxon 检验 p 值为 0.007。$m$ 更大时的随机森林也并没有变得更好。

本节练习

练习 15.1

Derive the variance formula (15.1). This appears to fail if ρ is negative; diagnose the problem in this case.

练习 15.4

Suppose x i , i = 1, . . . , N are iid $(\mu,\sigma^2)$. Let x̄ ∗ 1 and x̄ ∗ 2 be two bootstrap realizations of the sample mean. Show that the sampling correlation $\operatorname{corr}(\bar{x}_1^*,\bar{x}_2^*)=\frac{n}{2n-1}\approx50\%$. Along the way, derive var(x̄ ∗ 1 ) and the variance of the bagged mean x̄ bag . Here x̄ is a linear statistic; bagging produces no reduction in variance for linear statistics.