随机森林

论文与问题

Leo Breiman 的论文《随机森林》（Random Forests）于 2001 年 10 月发表在《Machine Learning》期刊，刊于第 45 卷，第 5–32 页。Breiman 当时在加州大学伯克利分校统计系。^[1] 论文讨论的对象不是一棵决策树，而是由许多树预测器（tree predictor）组成的分类器。树预测器通过一系列分裂来做出预测；随机森林把许多这样的预测器组合起来。论文要解决的问题是：怎样定义一个由随机性参与构造的树集合，并分析这个组合的误差。^[1]

方法：随机向量与随机特征

论文摘要把随机森林定义为树预测器的组合：森林中的每一棵树都依赖于一个随机向量（random vector）的取值，而这些随机向量是独立抽取的，并且对森林中的所有树都服从同一分布。^[1] 换句话说，每棵树都从同一个分布中得到自己的一份随机抽样，这份抽样影响该树的构造，因此树与树并不完全相同。论文还使用随机特征选择来划分每个节点。^[1] 节点是树中把数据分开的位置；在随机森林中，节点分裂时特征的选取带有随机性。森林就是这些树的组合。^[1]

泛化误差、强度与相关性

论文指出，当森林中的树的数量变得很大时，森林的泛化误差（generalization error）几乎必然收敛到一个极限。^[1] 泛化误差是对新数据的误差，不是对建树数据的误差；收敛结果说明，在树很多时，森林的误差会趋于一个稳定值。由树分类器组成的森林，其泛化误差取决于单棵树的强度（strength）以及树与树之间的相关性（correlation）。^[1] 强度描述单棵树作为分类器的表现，相关性描述树与树的行为有多相似，包括它们是否容易一起犯错。因此，森林的误差不只是各棵树误差的平均，还反映了树之间的共同一致程度。^[1]

结果与内部估计

论文报告，使用随机特征选择来划分每个节点，得到的错误率与 Adaboost 相比是有利的，同时对噪声更稳健。^[1] 论文比较了这种错误率与 Adaboost 的表现，并强调随机森林在噪声下的稳健性。论文还指出，内部估计可以监测误差、强度和相关性，也被用来衡量变量重要性（variable importance）。^[1] 内部估计是在森林构造中产生的估计，论文把它们用作森林的诊断量，并用它们给变量按重要性排序。论文还指出，这些想法同样适用于回归（regression）。^[1]

为什么重要

这篇论文的贡献在于：给随机森林一个精确的定义，用强度和相关性的框架分析其泛化误差，并提供一组内部诊断量。^[1] 这些内容把大型树集合的行为与可测量的树属性联系起来。随机特征选择不只是实现细节，而是论文所分析的定义的一部分。内部估计增加了实用的一面：同一片森林可以被监测误差、强度和相关性，其中的变量也可以按重要性排序。^[1] 论文指出这些想法也适用于回归，因此这个框架并不局限于分类。^[1] 对学习机器学习的人来说，这篇论文展示了怎样在一个框架里描述、分析和诊断一种集成方法。