随机森林：这或许是集成学习中最经典的一个 Bagging 算法了

在 集成学习概述 中已经知道了常用的集成算法有两种：Bagging 和 Boosting。而在 Bagging 中，随机森林（Random Forest，RF）又是其中典型的代表了。没错，这篇文章我们就是来介绍随机森林的。

什么是随机森林

在 决策树基础 中我们介绍了单个决策树的形成过程，简单来说，如果采用 Bagging 方式来将多个决策树集成在一起就是随机森林了。从名字中可以看出包含了两个关键词：“随机”和“森林”。森林的意思是指多个决策树，那随机的意思呢？其实随机有两个含义，一个是数据的随机性，另一个是特征的随机性。关于随机的含义下面会更具体介绍。

随机森林是 Bagging 中的一种，所以随机森林的示意图可以用下图表示：

算法流程

对随机森林有个简单了解之后，我们来看下随机森林的算法流程。假设要我们要生成 T 个决策树，原始的训练集包含 m 个样本，特征个数为 n，那么整个流程如下：

1. 从原始的包含了 m 个样本的数据集中随机地有放回地采样 m 次，得到 m 个样本（会有重复样本）
2. 使用采样生成的数据集训练一个决策树
3. 重复步骤1和2共 T 次，得到 T 个训练好的决策树
4. 采用投票法（分类树）或简单平均法（回归树）从 T 个决策树的预测结果中生成最终的结果

可以看到，由于采用随机地有放回地采样得到训练集，这样不同的树用到的训练集会有所差异；其次，每个树在结点分裂时并非是从所有的特征中选择最优特征和划分点，而是先随机地从所有特征 n 中选择一个包含了 k 个特征的特征子集，然后从特征子集中选择最优特征和划分点，通过改变 k 的大小可以控制随机性的引入程度。随机森林中的“随机”含义指的就是前面说的这两个随机：数据随机和特征随机。

需要说明的是，如果在随机选择的特征子集只包含一个特征时，相当于每次随机选择一个特征进行划分；如果特征子集包含的特征个数等于所有特征个数 n，这时候与经典的决策树没有区别。

袋外误差

前面已经知道，对于每棵树训练时所用到的样本都是随机且有放回地采样得到的，大约有 36.8% 的样本没有被采样到，也就是说，在生成某棵树的训练样本时，这些没有被采样到的样本称为该树的袋外数据(Out Of Bag，OOB)。通过袋外数据，我们可以计算出袋外误差来评估模型的性能。

对于袋外数据，我们可以计算出袋外错误率，计算过程如下：

1. 对于每个样本，计算它作为某棵树的袋外数据时该树对它的预测结果
2. 由于一个样本可以是多颗树的袋外数据，所以采用投票法或简单平均法生成该样本最后的预测结果
3. 根据每个袋外数据的预测结果与其真实结果可以计算出对应的误差

最后，简单介绍下随机森林的优点。由于随机森林在生成 T 个数据集以及训练模型的时候彼此之间没有依赖，所以它可以做到并行化，这对于数据量较大的情况下训练速度的提升很明显。其次，如果特征较多时，通过控制随机选择特征的个数也可以优化训练速度。