在SIGAI之前的公众号文章“大话AdaBoost算法”中我们介绍了集成学习的思想以及Boosting算法，今天的文章中我们将为大家介绍另外一种集成学习算法-随机森林。随机森林由多棵决策树组成，采用多棵决策树联合进行预测可以有效提高模型的精度。这些决策树用对训练样本集随机抽样构造出的样本集训练得到。由于训练样本集由随机抽样构造，因此称为随机森林。随机森林不仅对训练样本进行抽样，还对特征向量的分量随机抽样，在训练决策树时，每次寻找最佳分裂时只使用一部分抽样的特征分量作为候选特征进行分裂
集成学习
集成学习（ensemble learning）是机器学习中的一种思想，而不是指某一具体算法，它通过多个模型的组合形成一个精度更高的模型，参与组合的模型称为弱学习器（weak learner）。在预测时使用这些弱学习器模型联合进行预测；训练时需要用训练样本集依次训练出这些弱学习器。这种集体决策的例子在我们的日常生活中经常会见到，如医生集体会诊，如果对某一病人的情况拿不定主意，可以让多位医生一起来诊断，用他们各自的诊断结果进行投票，得到最终的诊断结果。因此，集成学习是一种非常符合人类思维习惯的方法。
Bootstrap抽样
在概率论与数理统计中，我们学习过随机抽样的概念，统计学的核心思想是用样本推断整体，即用随机抽取的样本来研究所有样的特征。Bootstrap抽样是一种数据抽样方法，它是构成Bagging算法和随机森林的基础。所谓抽样是指从一个样本数据集中随机抽取一些样本，形成新的数据集。这里有两种选择：有放回抽样和无放回抽样。对于前者，一个样本被抽中之后会放回去，在下次抽样时还有机会被抽中。对于后者，一个样本被抽中之后就从抽样集中去除，下次不会再参与抽样，因此一个样本最多只会被抽中一次。在这里Bootstrap使用的是有放回抽样。我们可以给这种做法一个形象的解释，公司年会抽奖时，有两种做法，第一种是一个人中奖之后不能再继续参与抽奖，这是无放回抽样；否则就是有放回抽样，这会造成运气好的人多次中奖。
Bootstrap抽样的做法是在n个样本的集合中有放回的抽取n个样本形成一个数据集。在这个新的数据集中原始样本集中的一个样本可能会出现多次，也可能不出现。例如，如果有有10个样本，Bootstrap抽样从它们中随机的抽取出10个，下面两种情况都是可能发生的：
1 1 1 1 1 1 1 1 1 1
1 2 3 4 5 6 7 8 9 10
第一种结果是10次都抽中了1，第二种是1-10这10个样本每个都被抽中一次。
假设样本集中有n个样本，每次抽中其中任何一个样本的概率都为1/n，即等概率，一个样本在每次抽样中没被抽中的概率为1-1/n。由于是有放回的抽样，每两次抽样之间是独立的，因此对于连续n次抽样，一个样本没被抽中的概率为：
可以证明，当n趋向于无穷大时这个值的极限是1/e，约等于0.368，其中e是自然对数的底数。即如下结论成立：
证明过程很简单，在微积分中，有这样一个重要极限：
我们只要凑出这样的形式就可以了，感兴趣的读者可以自己证明。
如果样本量很大，在整个抽样过程中每个样本有0.368的概率不被抽中。由于样本集中各个样本是相互独立的，在整个抽样中所有样本大约有36.8%没有被抽中。这部分样本称为包外（Out Of Bag，简称OOB）数据，后面我们会看到它的用途。
Bagging算法
在日常生活中我们会遇到这样的情况：对一个决策问题，如果一个人拿不定主意，可以组织多个人来集体决策。如果要判断一个病人是否患有某种疑难疾病，可以组织一批医生来会诊。会诊的做法是让每个医生做一个判断，然后收集他们的判断结果进行投票协商，得票最多的那个判断结果作为最终的结果。这种思想在机器学习领域的应用就是集成学习算法。
在Bootstrap抽样的基础上可以构造出Bagging（Bootstrap Aggregating）算法。这种方法对训练样本集进行多次Bootstrap抽样，用每次抽样形成的数据集训练一个弱学习器模型，得到多个独立的弱学习器（对于分类问题，称为弱分类器），最后用它们的组合进行预测。训练流程为：
循环，对i = 1, ..., T 对训练样本集进行Bootstrap抽样，得到抽样后的训练样本集 用抽样得到的样本集训练一个模型h_{i}(x) 结束循环 输出模型组合
h_{1}(x),...,h_{T}(x)
其中T为弱学习器的数量。Bagging算法是一个抽象的框架，并没有指明每个弱学习器是什么类型的。如果弱学习器是决策树，这种方法就是随机森林
随机森林
随机森林由Breiman等人提出[1]，它由多棵决策树组成。在数据结构中我们学过森林的概念，它由多棵数组成，这里沿用了此概念。对于分类问题，一个测试样本会送到每一棵决策树中进行预测，然后进行投票，得票最多的类为最终分类结果。对于回归问题随机森林的预测输出是所有决策树输出的均值。例如随机森林有10棵决策树，有8课树的预测结果是第1类，1棵决策树的预测结果为第2类，2棵决策树的预测结果为第3类，则我们将样本判定成第1类。
使用多棵决策树联合进行预测可以有效降低模型的方差，下面给出一种不太严格的解释。对于n个独立同分布的随机变量
x_{i}
，假设它们的方差为
\sigma^{2}
，则它们均值的方差为：
x_{i}
，假设它们的方差为
\sigma^{2}
，则它们均值的方差为：
即将多个随机变量相加取均值，方差会减小。如果将每棵决策树的输出值看作随机变量，多棵树的输出值的均值的方差会比单棵树小，因此可以降低模型的方差。
由于使用了决策树进行投票，而决策是分段常数函数，因此随机森林也是分段常数函数，是一个非线性模型，而且是判别模型。下图是用随机森林对平面上2类样本（红色和蓝色）进行训练和分类的结果（来自SIGAI云端实验室）：
按照前面介绍的，随机森林不仅可以用于分类问题，还可以用于回归问题。另外，它也支持多分类问题，这是由决策树的能力所保证的。
训练算法
随机森林在训练时，循环依次训练每一棵决策树，每棵树的训练样本都是从原始训练集中进行Bootstrap抽样得到。在训练决策树的每个节点时所用的特征也是随机抽样得到的，即从特征向量中随机抽出部分特征参与训练。在SIGAI之前的公众号文章“理解决策树”中，我们已经介绍了决策树训练算法的原理，尤其是训练每个内部节点时寻找最佳分裂的原理，如果对此不清楚，可以先阅读这篇文章。随机森林对训练样本和特征向量的分量都进行了随机采样。
在这里决策树的训练算法与“理解决策树”中介绍的相同，这里唯一的不同是训练决策树的每个节点时只使用随机抽取的部分特征分量。下图是随机森林训练过程的示意图（来自SIGAI云端实验室），下图是完整的样本集：
下图是训练一棵决策树时随机抽取的一部分样本形成的样本集以及用它训练出来的决策树：
每次训练决策树时，都是从整个样本集随机选取的部分样本。最后训练得到的随机森林如下图所示：
样本的随机抽样可以用均匀分布的随机数构造，如果有m个训练样本，只需要将随机数变换到区间[0, m-1]即可。每次抽取样本时生成一个该区间内的随机数，然后选择编号为该随机数的样本。对特征分量的采样是无放回抽样，可以用随机洗牌算法实现，即将样本先随机乱序，然后挑选出前面的一部分。在c++的STL库中，random_shuffle函数实现了随机洗牌的功能，在其他语言中，也有类似的函数。
这里需要确定决策树的数量以及每次分裂时选用的特征数量，对此并没有标准的答案。第一个问题根据训练集的规模和问题的特点而定。第二个问题也没有一个精确的理论答案，可以通过实验确定。
正是因为有了这些随机性，随机森林可以在一定程度上消除过拟合。对样本进行采样是必须的，如果不进行采样，每次都用完整的训练样本集训练出来的多棵树是相同的，这没有任何意义。
包外误差
训练每一棵决策树时有一部分样本未参与训练，可以在训练时利用这些没有被选中的样本做测试，统计它们的预测误差，称为包外误差。这种做法与交叉验证类似。二者都是把样本集切分成多份，轮流用其中的一部分样本进行训练，用剩下的样本进行测试。不同的是交叉验证把样本均匀的切分成份，在训练集中同一个样本不会出现多次；后者在每次Bootstrap抽样时同一个样本可能会被选中多次。
利用包外样本作为测试集得到的包外误差与交叉验证得到的误差基本一致，因此可以用来代替交叉验证的结果，因此可以使用包外误差作为泛化误差的估计。下面给它包外误差的计算方法。对于分类问题，包外误差定义为被错分的包外样本数与总包外样本数的比值。对于回归问题，所有包外样本的回归误差和除以包外样本数。
实验结果证明，增加决策树的数量包外误差与测试误差会下降。这个结论为我们提供了确定决策树数量的一种思路，可以通过观察误差来决定何时终止训练。当训练误差稳定之后停止训练。
计算变量的重要性
随机森林有一个特点，可以在训练过程中输出变量的重要性，即哪个特征分量对分类更有用。实现的方法是置换法。它的原理是，如果某个特征分量对分类很重要，那么改变样本的该特征分量的值，样本的预测结果就容易出现错误。也就是说这个特征值对分类结果很敏感。反之，如果一个特征对分类不重要，随便改变它对分类结果没多大影响。
对于分类问题，训练某决策树时在包外样本集中随机挑选两个样本，如果要计算某一变量的重要性，则置换这两个样本的这个特征值。统计置换前和置换后的分类准确率。变量重要性的计算公式为：
这翻译的是置换前后的分类准确率变化值。
上面定义的是单棵决策树的变量重要性，计算出每棵树的变量重要性之后，对该值取平均就得到随机森林的变量重要性。计算出每个变量的重要性之后，将该值归一化得到最终的重要性值。
实际应用
因为采用了决策树作为弱学习器，随机森林同样具有运算量小、实现简单的优点，得到了广泛的应用。典型的应用包括各种图像和数据的分类[2][3]，人脸检测与关键点定位问题[4]。
总结
随机森林是一种集成学习算法，它将多棵决策树进行整合来完成预测。对于分类问题预测结果是所有决策树预测结果的投票；对于回归问题，是所有决策树预测结果的均值。训练时，通过Bootstrap抽样来形成每棵决策树的训练集，训练每棵决策树的每个节点时，所用的特征也是从整个特征向量中抽取的一部分特征。通过将多棵决策树集成，以及每次用采样的样本和特征分量训练每棵决策树，可以有效的降低模型的方差。
随机森林是一种判别模型，既支持分类问题，也支持回归问题，并且支持多分类问题。它是一种非线性模型，其预测函数为分段常数函数。
参考文献
[1] Breiman, Leo. Random Forests. Machine Learning 45 (1), 5-32, 2001.
[2] Jisoo Ham, Yangchi Chen, Melba M Crawford, Joydeep Ghosh. Investigation of the random forest framework for classification of hyperspectral data. IEEE Transactions on Geoscience and Remote Sensing. 2005.
[3] M Pal. Random forest classifier for remote sensing classification.International Journal of Remote Sensing. 2005.
[4] Dong Chen, Shaoqing Ren, Yichen Wei, Xudong Cao, Jian Sun. Joint Cascade Face Detection and Alignment. european conference on computer vision. 2014.
推荐阅读：
关注SIGAICN公众号，回复文章获取码，即可获得全文链接
[1] 机器学习-波澜壮阔40年 【获取码】SIGAI0413.
[2] 学好机器学习需要哪些数学知识？【获取码】SIGAI0417.
[3] 人脸识别算法演化史 【获取码】SIGAI0420.
[4] 基于深度学习的目标检测算法综述 【获取码】SIGAI0424.
[5] 卷积神经网络为什么能够称霸计算机视觉领域？【获取码】SIGAI0426.
[6] 用一张图理解SVM的脉络 【获取码】SIGAI0428.
[7] 人脸检测算法综述 【获取码】SIGAI0503.
[8] 理解神经网络的激活函数 【获取码】SIGAI0505.
[9] 深度卷积神经网络演化历史及结构改进脉络-40页长文全面解读 【获取码】SIGAI0508.
[10] 理解梯度下降法 【获取码】SIGAI0511.
[11] 循环神经网络综述—语音识别与自然语言处理的利器 【获取码】SIGAI0515.
[12] 理解凸优化 【获取码】SIGAI0518.
[13] 【实验】理解SVM的核函数和参数 【获取码】SIGAI0522.
[14] 【SIGAI综述】行人检测算法 【获取码】SIGAI0525.
[15] 机器学习在自动驾驶中的应用—以百度阿波罗平台为例(上)【获取码】SIGAI0529.
[16] 理解牛顿法 SIGAI 2018.5.31
[17] 【群话题精华】5月集锦—机器学习和深度学习中一些值得思考的问题 【获取码】SIGAI0601.
[18] 大话Adaboost算法 【获取码】SIGAI0602.
[19] FlowNet到FlowNet2.0：基于卷积神经网络的光流预测算法 【获取码】SIGAI0604.
[20] 理解主成分分析(PCA)【获取码】SIGAI0606.
[21] 人体骨骼关键点检测综述 【获取码】SIGAI0608.
[22] 理解决策树 【获取码】SIGAI0611.
[23] 用一句话总结常用的机器学习算法 【获取码】SIGAI0613.
[24] 目标检测算法之YOLO 【获取码】SIGAI0615.
[25] 理解过拟合 【获取码】SIGAI0618.
[26] 理解计算：从√2到AlphaGo ——第1季 从√2谈起 【获取码】SIGAI0620.
[27] 场景文本检测——CTPN算法介绍 【获取码】SIGAI0622.
[28] 卷积神经网络的压缩和加速 【获取码】SIGAI0625.
[29] k近邻算法 【获取码】SIGAI0627.
[30] 自然场景文本检测识别技术综述 【获取码】SIGAI0629.
[31] 理解计算：从√2到AlphaGo ——第2季 神经计算的历史背景 【获取码】SIGAI0702.
[32] 机器学习算法地图 【获取码】SIGAI0704.
[37] 人脸检测算法之S3FD 【获取码】SIGAI6
[38]基于深度负相关学习的人群计数方法 【获取码】SIGAI0718
[39] 流形学习概述 【获取码】SIGAI0721
[40] 关于感受野的总结 【获取码】SIGAI0723
