RandomForest

1. 背景概述

1995 年，随机决策森林的一般方法由 Ho 首次提出。 Ho (1998) 写了许多关于“随机子空间”方法的论文，该方法随机选择特征子集以用于生长每棵树。

1997 年，在一篇关于书面字符识别的重要论文中，Amit 和 Geman 定义了大量的几何特征，并在这些几何特征的随机选择中搜索每个节点的最佳分割

2001 年，Leo Breiman 在一篇论文中对随机森林进行了适当的介绍。本文描述了一种使用类似 CART 的程序，结合随机节点优化和装袋来构建不相关树森林的方法。此外，本文结合了几种成分，一些是以前已知的，一些是新的，它们构成了随机森林现代实践的基础，特别是：使用袋外误差作为泛化误差的估计。通过排列测量变量的重要性。该报告还提供了随机森林的第一个理论结果，其为泛化误差的界限，这取决于森林中树木的强度及其相关性。

2. Bagging

随机森林是在 bagging 方法上进行改进的。bagging 是一种集成算法，也是通过多个弱分类器进行策略结合，使最终结果好于单个的分类器。

决策树模型通过贪婪学习算法，具有高度可解释性并且训练快速。但是，单个决策树为了逼近一个复杂的函数，需要使用一个大树。一个大树通常具有高方差并且容易过拟合。

Bagging 就是解决高方差的一种方法，采用多个树结构然后对输出结果取平均。

Bagging 主要有两个步骤:

(Bootstrap) 随机采样，从训练集中有放回的采集 $m$ 个样本，重复 $T$ 次得到对应的采样集，用每个采样集训练一个完整的决策树。
(Aggregate) 对结果进行聚合输出，如果是回归问题，$T$ 个弱学习器得到的回归结果进行算术平均得到的值为最终的模型输出，输出结果为 $\displaystyle y’ = \frac{1}{T}\sum_{t=1}^T \phi(\mathbf{x})$，如果是分类问题，则 $T$ 个弱学习器投出最多票数的类别为最终类别，$\displaystyle y’ = \arg\max_j{k:\phi_k(\mathbf{x})=j}$

Bagging 也就是 Bootstrap Aggregate 的缩写。

bagging 具有以下优点：

高能力——通过使用完整的树，每个模型都能够逼近复杂的函数和决策边界。
低方差——假设我们选择了足够多的树，对所有模型的预测进行平均可以减少最终预测的方差

主要缺点是期望偏差可能会变大，同时平均模型不再易于解释，不能像决策树一样来追踪每一个节点分裂和输出的逻辑。

3. 随机森林

假设每个决策树的预测变量 $\phi(\mathbf{x})$ 具有相同的方差 $\sigma$，同时 $\rho$ 代表两个决策树预测值之间的相关性，因此有

$\begin{aligned} \text{Var}\left(\frac{1}{T}\sum_{t=1}^T \phi(\mathbf{x})\right) &= \frac{1}{ T^2} \sum_{k,m}\text{Cov}(\phi_k, \phi_m)\\ &= \frac{1}{ T^2} \sum_{k\ne m}\text{Cov}(\phi_k, \phi_m)+\frac{1}{ T^2} \sum_{k}\text{Cov}(\phi_k, \phi_k) \\ &= \frac{1}{ T^2}(T^2-T)\rho \sigma^2 +\frac{1}{ T^2}T\sigma \\ &= \rho \sigma^2 + \frac{\sigma^2}{T}(1-\rho) \end{aligned}$

当随着 $T$ 的增加，上式中的第二项会越来越小，但第一项仍然存在。因此 bagging 最终受限于弱学习器之间的相关性。

随机森林相较于 bagging 更进一步的降低决策树之间的相关性。采用方法是对决策树划分子树的时候，会从节点上所有 $n$ 个特征中选择 $m$ 个部分样本特征，再在这 $m$ 中特征中选择最优的一个特征来做决策树的左右子树划分。

参考

1. Random forest - wiki
2. Random Forests - LEO BREIMAN
3. Lecture 10: Random Forests
4. Lecture #15: Regression Trees & Random Forests
5. XGBoost解读(2)—近似分割算法

Machine Learning

2022-07-28