随机森林论文答辩

随机森林论文答辩

摘 要

人体识别是计算机视觉领域的一大类热点问题，其研究内容涵盖了人体的监测与跟踪、手势识别、动作识别、人脸识别、性别识别和行为与事件识别等，有着非常广泛的应用价值。随机森林以它自身固有的特点和优良的分类效果在众多的机器学习算法中脱颖而出。随机森林算法的实质是一种树预测器的组合，其中每一棵树都依赖于一个随机向量，森林中的所有的向量都是独立同分布的。本文简单介绍了随机森林的原理，并对近几年来随机森林在姿势识别和人脸识别中的应用进行讨论。

1.人体识别概述

人体识别是计算机视觉领域的一大类热点问题，其研究内容涵盖了人体的监测与跟踪、手势识别、动作识别、人脸识别、性别识别和行为与事件识别等。其研究方法几乎囊括了所有的模式识别问题的理论与技术，例如统计理论，变换理论，上下文相关性，分类与聚类，机器学习，模板匹配，滤波等。人体识别有着非常广泛的应用价值。

绝大多数人脸识别算法和人脸表情分析算法在提取人脸特征之前,需要根据人脸关键点的位置(如眼角,嘴角)进行人脸的几何归一化处理。即使在已知人脸粗略位置的情况下,人脸关键点精确定位仍然是一个很困难的问题,这主要由外界干扰和人脸本身的形变造成。

当前比较流行的算法有：基于启发式规则的方法、主成分分析(PCA)、独立元分析(ICA)、基于K-L 变换、弹性图匹配等。

2.随机森林综述

随机森林顾名思义，使用随机的方式建立一个森林，森林里面有很多的决策树组成，随机森林的每一棵决策树之间是没有关联的。在得到森林之后，当有一个新的输入样本进入的死后，就让森林的每一棵决策树分别进行一下判断，看看这个样本应该属于哪一类（对于分类算法），然后看看哪一类能被选择最多，就预测这个样本为那一类。

随机森林是一种统计学习理论，其随机有两个方面：首先是在训练的每一轮中，都是对原始样本集有放回的抽取固定数目的样本点，形成k个互不相同的样本集。第二点是：对于每一个决策树的建立是从总的属性中随机抽取一定量的属性作分裂属性集，这样对于k个树分类器均是不相同的。由随机生成的k个决策树组成了随机森林。

对于每一个决策树来讲，其分裂属性是不断的选取具有最大信息增益的属性进行排列。整个随机森林建立后，最终的分类标准采用投票机制得到可能性最高的结果。

下图是随机森林构建的过程：

图1 随机森林构建过程

3.随机森林在人体识别中的应用

3.1 随机森林应用于姿势识别

以[1]一文来讨论，论文中所涉及到的人体识别过程主要分为两步，首先是，身体部位标记：对于从单张景深图像中对人体进行分段，并标记出关键节点。之后进行身体关节定位，将标记的各个人体部分重新映射到三维空间中，对关键节点形成高可靠的空间定位。

图2 深度图像-身体部位标记-关节投影

文的最主要贡献在于将姿势识别的问题转化成了物体识别的问题，通过对身体不同部位的空间位置的确定来实现，做到了低计算消耗和高精确度。在身体部位标记的过程中，将问题转化成了对每个像素的分类问题，对于每个像素点，从景深的角度来确定该点的局域梯度特征。该特征是点特征与梯度特征的良好结合。

举个例子，对于不同点的相同属性值的判别，如下图，图a中的两个测量点的像素偏移间均具有较大的景深差，而图b中的景深差则明显很小。由此看出，不同位置像素点的特征值是有明显差别的，这就是分类的基础。

图3 景深图像特质示例

文中对于决策树的分裂属性的选择来说。由于某两个像素点、某些图像特征选取的随意性，将形成大量的备选划分形式，选择对于所有抽样像素对于不同的分裂属性划分前后的信息熵增益进行比较，选取最大的一组ψ=(θ, τ)作为当前分裂节点。（信息增益与该图像块最终是否正确地分类相关，即图像块归属于正确的关键特征点区域的概率。）

图4 决策时分类说明

决策树的建立后，某个叶子节点归属于特定关键特征点区域的概率可以根据训练图像最终分类的情况统计得到，这就是随机森林在实际检测特征点时的最重要依据。

在人体关节分类中，我们由形成的决策森林，来对每一个像素点的具体关节属性进行判断，并进行颜色分类。随机森林这种基于大量样本统计的方法能够对由于光照、变性等造成的影响，实时地解决关键特征点定位的问题。

如图所示，是对于景深图像处理后的结果展示。

图5 姿势识别处理结果

应该这样说，这篇文章在算法的层面对随机森林没有太大的贡献。在划分函数的形式上很简单。这个团队值得称道的地方是通过计算机图形学造出了大量的不同体型不同姿势的各种人体图像，用作训练数据，这也是成为2011年CVPR Best Paper的重要原因。正是因为论文的成果运用于Kinect，在工业界有着巨大的作用，落实到了商用的硬件平台上，推动了随机森林在计算机视觉、多媒体处理上的热潮。

3.2 随机森林应用于人脸识别

基于回归森林的脸部特征检测通过分析脸部图像块来定位人脸的关键特征点，在此基础上条件回归森林方法考虑了全局的脸部性质。对于[2]进行分析，这篇论文是2012年CVPR上的论文，本文考虑的是脸部朝向作为全局性质。其主要描述的问题是如何利用条件随机森林，来确定面部10个关键特征点的位置。与之前不同的是，在随机森林的基础上，加入了面部朝向的条件约束。

图6 脸部10个特征点

对于面部特征标记的问题转化成了对大量图像块的分类问题。类似于人体识别中的局域梯度特征识别。本文中，对于每一个图像块来说，从灰度值、光照补偿、相位变换等图像特征，以及该图像块中心与各个特征点的距离来判断图像块的位置特征。在决策树的分裂属性确定过程，依然使用“最大信息熵增益”原则。

图7 条件随机森林算法说明

文中提出了更进一步基于条件随机森林的分类方法，即通过设定脸部朝向的约束对决策树分类，在特征检测阶段能够根据脸部朝向选择与之相关的决策树进行回归，提高准确率和降低消耗。此论文还对条件随机森林，即如何通过脸部朝向对决策进行分类进行了说明，但这与随机森林算法没有太大关系，这里就不再继续讨论了。随机森林这种基于大量样本统计的方法能够对由于光照、变性等造成的影响，实时地解决关键特征点定位的问题。

另一篇文章[3]对于脸部特征标记，提出了精确度更高、成本更低的方法。即，基于结构化输出的随机森林的特征标记方式。文中将面部划分为20个特征点，对于各个特征点来说，不仅有独立的图像块分类标记，还加入了例如，点4，对于其他嘴唇特征点3,18,19的依赖关系的判断。这样的方法使特征点标记准确率大大增加。

该方法依然是使用随机森林的方法，有所不同的是引入了如式中所示的与依赖节点之间的关系。对于决策树的建立依然是依赖信息熵增益原则来决定，叶子节点不仅能得到特征的独立划分还会得到该特征对依赖特征的贡献，最终特征节点的判断会综合原始投票及空间约束。

图8 脸部特征标记

图9 决策树依赖关系

例如当对下图中人脸特征点进行分类时，使用简单的随机森林方法，经过判断会将各个点进行标注，可以看到 红色的点，标注出的鼻子特征。如果利用依赖节点进行判断，鼻子的点会被局限在其他鼻子特征点的周围，进行叠加后，得到了这个结果。显然，对于此节点的判断，利用结构输出的方式，准确度更高了。

图10 结构化输出结果

4.随机森林总结

大量的理论和实证研究都证明了RF具有很高的预测准确率，对异常值和噪声具有很好的容忍度，且不容易出现过拟合。可以说，RF是一种自然的非线性建模工具，是目前数据挖掘算法最热门的前沿研究领域之一。具体来说，它有以下优点：

1.通过对许多分类器进行组合，它可以产生高准确度的分类器；

2.它可以处理大量的输入变量；

3.它可以在决定类别时，评估变量的重要性；

4.在建造森林时，它可以在内部对于一般化后的误差产生不偏差的估计；

5.它包含一个好方法可以估计遗失的资料，并且，如果有很大一部分的资料遗失，仍可以维持准确度。

6.它提供一个实验方法，可以去侦测变量之间的相互作用；

7.学习过程是很快速的；

8.对异常值和噪声具有很好的容忍度，且不容易出现过拟合；

随机森林的缺点：

1.对于有不同级别的属性的数据，级别划分较多的属性会对随机森林产生更大的影响，所以随机森林在这种数据上产出的属性权值是不可信的；

2.单棵决策树的预测效果很差：由于随机选择属性，使得单棵决策树的预测效果很差。

参考文献：

[1] Shotton, J.; Fitzgibbon, A.; Cook, M.; Sharp, T.; Finocchio, M.; Moore, R.; Kipman, A.; Blake, A., “Real-time human pose recognition in parts from single depth images,”Computer Vision and Pattern Recognition (CVPR), 2011 IEEE Conference on , vol., no., pp.1297,1304, 20-25 June 2011

[2] Dantone M, Gall J, Fanelli G, et al. Real-time facial feature detection using conditional regression forests[C]//Computer Vision and Pattern Recognition (CVPR), 2012 IEEE Conference on. IEEE, 2012: 2578-2585.

[3] Heng Yang, Ioannis Patras, “Face Parts Localization Using Structured-output Regression Forests”, ACCV2012， Dajeon, Korea.

本文转自：，仅供学习交流

随机森林

随机森林是一种集成算法(Ensemble Learning)，它属于Bagging类型，通过组合多个弱分类器，最终结果通过投票或取均值，使得整体模型的结果具有较高的精确度和泛化性能。其可以取得不错成绩，主要归功于 "随机"和“森林” ，一个使它具有抗过拟合能力，一个使它更加精准。

Bagging 是一种在原始数据集上通过有放回抽样重新选出k个新数据集来训练分类器的集成技术。它使用训练出来的分类器的集合来对新样本进行分类，然后用多数投票或者对输出求均值的方法统计所有分类器的分类结果，结果最高的类别即为最终标签。此类算法可以有效降低bias，并能够降低variance。

【 自助法 】它通过自助法（bootstrap）重采样技术，从训练集里面采集固定个数的样本，但是每采集一个样本后，都将样本放回。也就是说，之前采集到的样本在放回后有可能继续被采集到。

【OOB】 在Bagging的每轮随机采样中，训练集中大约有36.5%的数据没有被采样集采集中。 对于这部分没有采集到的数据，我们常常称之为袋外数据(Out of Bag, 简称OOB) 。这些数据没有参与训练集模型的拟合，因此可以用来检测模型的泛化能力。

【随机性】 对于我们的Bagging算法，一般会对样本使用boostrap进行随机采集，每棵树采集相同的样本数量，一般小于原始样本量。这样得到的采样集每次的内容都不同 ，通过这样的自助法生成K个分类树组成随机森林，做到样本随机性 。

【输出】 Bagging的集合策略也比较简单，对于分类问题，通常使用简单投票法，得到最多票数的类别或者类别之一为最终的模型输出。对于回归问题，通常使用简单平均法，对T个弱学习器得到的回归结果进行算术平均得到的最终的模型输出。

【弱分类器】 首先，RF使用了CART决策树作为弱学习器。换句话说，其实我们只是将实验CART决策树作为弱学习器的Bagging方法称为随机森林。

【随机性】 同时，在生成每棵树的时候， 每个树选取的特征都不仅仅是随机选出的少数特征，一般默认取特征总数m的开方。 而一般的CART树则会选取全部的特征进行建模。因此 ，不但特征是随机的，也保证了特征随机性 。

【样本量】 相对于一般的Bagging算法，RF会选择采集和训练集样本数N一样个数的样本。、

【特点】 由于随机性，对于降低模型的方差很有作用，故随机森林一般不需要额外剪枝，即可以取得较好的泛化能力和抗拟合能力(Low Variance)。当然对于训练集的拟合程度就会差一点，也就是模型的偏倚会大一些(High Bias)，仅仅是相对的。

在关于随机森林的原始论文中，显示随机森林错误率取决于两件事：

      森林中任何两棵树之间的相关性。增加相关性会增加森林错误率。

      森林中每棵树的力量(具有低错误率的树是强分类器)。增加单棵数据的强度(分类更精确)会降低森林错误率。

    随机森林的弱分类器使用的是CART树，CART决策树又称为分类回归树。当数据集的因变量为连续型数值时，该树算法就是一个回归树，可以用叶节点观察的均值作为预测值；当数据集的因变量为离散型数值时，该树算算法就是一个分类树，可以很好地解决分类问题。但是需要注意的是，该算法是一个二叉树，即每一个叶节点只能引申出两个分支，所以当某个非叶节点是多水平(2个以上)的离散变量时，该变量就有可能被多次使用。同时，若某个非叶节点是连续变量时，决策树也将把他当做离散变量来处理(即在有限的可能值中做划分)。

    特征选择目前比较流行的方法是信息增益、增益率、基尼系数和卡方检验。这里主要介绍基于基尼系数(Gini)的特征选择，因为随机森林采用的CART决策树就是基于基尼系数选择特征的。

    基尼系数的选择的标准就是每个子节点达到最高的纯度，即落在子节点中的所有观察都属于同一分类，此时基尼系数最小，纯度最高，不确定度最小。对于一般的决策树，加入总共有K类，样本属于第K类的概率：pk,则该概率分布的基尼指数为：

基尼指数越大，说明不确定性就越大；基尼系数越小，不确定性越小，数据分割越彻底，越干净。

对于CART树而言，由于是二叉树，可以通过下面的表示：

在我们遍历每个特征的每个分割点时，当使用特征A=a，将D划分为两部分，即D1（满足A=a的样本集合），D2（不满足A=a的样本集合）。则在特征A=a的条件下D的基尼指数为：

Gini(D)：表示集合D的不确定性。

Gini(A,D)：表示经过A=a分割后的集合D的不确定性。

随机森林中的每棵CART决策树都是通过不断遍历这棵树的特征子集的所有可能的分割点，寻找Gini系数最小的特征的分割点，将数据集分成两个子集，直至满足停止条件为止。

    首先，正如Bagging介绍中提到的，每个树选择使用的特征时，都是从全部m个特征值随机产生的，本身就已经降低了过拟合的风险和趋势。模型不会被特定的特征值或特征组合所决定，随机性的增加，将控制模型的拟合能力不会无限提高。

    第二，与决策树不同，RF对决策树的简历做了改进。对于普通的决策树，我们会在节点上所有的m个样本特征中选择一个最优的特征来做决策树的左右子树划分。但是RF的每个树，其实选用的特征是一部分，在这些少量特征中，选择一个最优的特征来做决策树的左右子树划分，将随机性的效果扩大，进一步增强了模型的泛化能力。

    假设每棵树选取msub个特征，msub越小，此时模型对于训练集的拟合程度会变差，偏倚增加，但是会泛化能力更强，模型方差减小。msub越大则相反。在实际使用中，一般会将msub的取值作为一个参数，通过开启OOB验证或使用交叉验证，不断调整参数以获取一个合适的msub的值。

优点：

    （1）由于采用了集成算法，本身精度比大多数单个算法要好。

    （2）在测试集上表现良好，由于两个随机性的引入，使得随机森林不容易陷入过拟合( 样本随机，特征随机 )

    （3）在工业上，由于两个随机性的引入，使得随机森林具有一定的抗噪声能力，对比其他算法具有一定优势。

    （4）由于树的组合，使得随机森林可以处理非线性数据，本身属于非线性分类(拟合)模型。

    （5） 它能够处理很高维度(feature很多)的数据 ，并且不用做特征选择，对数据集的适应能力强：既能处理离散型数据，也能处理连续型数据，数据集无需规范化。

    （6）训练速度快，可以运用在大规模数据集上。

    （7）由于袋外数据(OOB)，可以在模型生成过程中取得真实误差的无偏估计，且不损失训练数据量。

    （8）在训练过程中，能够检测到feature间的互相影响， 且可以得出feature的重要性 ，具有一定参考意义。

    （9）由于每棵树可以独立、同时生成，容易做成并行化方法。

    （10）由于实现简单、 精度高、抗过拟合能力强 ，当面对非线性数据时，适于作为基准模型。

缺点：

    （1）随机森林在解决回归问题时，并没有像它在分类中表现的那么好，这是因为它并不能给出一个连续的输出。当进行回归时，随机森林不能够作出超越训练集数据范围的预测，这可能导致在某些特定噪声的数据进行建模时出现过拟合。（PS:随机森林已经被证明在某些噪音较大的分类或者回归问题上会过拟合）

（2）对于许多统计建模者来说，随机森林给人感觉就像一个黑盒子，你无法控制模型内部的运行。只能在不同的参数和随机种子之间进行尝试。

（3）可能有很多相似的决策树，掩盖了真实的结果。

（4）对于小数据或者低维数据(特征较少的数据)，可能不能产生很好的分类。( 处理高维数据，处理特征遗失数据，处理不平衡数据是随机森林的长处 )。

（5）执行数据虽然比boosting等快，但是比单棵决策树慢多了。

（1） 不要求是线性特征，比如逻辑回归很难处理类别型特征 ，而树模型，是一些决策树的集合，可以很容易的处理这些情况。

（2） 由于算法构建的过程，这些算法很容易处理高维的数据，大量的训练数据的场景 。

极端随机树是随机森林的一个变种，原理几乎和RF一模一样，仅有区别有：

（1）对于每个决策树的训练集，RF采用的是随机采样bootstrap来选择采样集作为每个决策树的训练集，而extra trees一般不采用随机采样，即每个决策树采用原始训练集。

（2）在选定了划分特征后，RF的决策树会基于基尼系数，均方差之类的原则，选择一个最优的特征值划分点，这和传统的决策树相同。但是极端随机树比较的激进，他会随机的选择一个特征值来划分决策树。

随机森林特征重要性

在随机森林介绍中提到了随机森林一个重要特征：能够计算单个特征变量的重要性。并且这一特征在很多方面能够得到应用,例如在银行贷款业务中能否正确的评估一个企业的信用度,关系到是否能够有效地回收贷款。但是信用评估模型的数据特征有很多,其中不乏有很多噪音,所以需要计算出每一个特征的重要性并对这些特征进行一个排序,进而可以从所有特征中选择出重要性靠前的特征。

一：特征重要性
在随机森林中某个特征X的重要性的计算方法如下：
1：对于随机森林中的每一颗决策树,使用相应的OOB(袋外数据)数据来计算它的袋外数据误差,记为errOOB1.
2: 随机地对袋外数据OOB所有样本的特征X加入噪声干扰(就可以随机的改变样本在特征X处的值),再次计算它的袋外数据误差,记为errOOB2.
3：假设随机森林中有Ntree棵树,那么对于特征X的重要性=∑(errOOB2-errOOB1)/Ntree,之所以可以用这个表达式来作为相应特征的重要性的度量值是因为：若给某个特征随机加入噪声之后,袋外的准确率大幅度降低,则说明这个特征对于样本的分类结果影响很大,也就是说它的重要程度比较高。

二：特征选择
在论文 Variable Selection using Random Forests中详细的论述了基于随机森林的特征选择方法,这里我们进行一些回顾。
首先特征选择的目标有两个：
1：找到与应变量高度相关的特征变量。
2：选择出数目较少的特征变量并且能够充分的预测应变量的结果。
其次一般特征选择的步骤为：
1：初步估计和排序
a)对随机森林中的特征变量按照VI（Variable Importance）降序排序。
b)确定删除比例,从当前的特征变量中剔除相应比例不重要的指标，从而得到一个新的特征集。
c)用新的特征集建立新的随机森林,并计算特征集中每个特征的VI,并排序。
d)重复以上步骤,直到剩下m个特征。
2：根据1中得到的每个特征集和它们建立起来的随机森林,计算对应的袋外误差率(OOB err),将袋外误差率最低的特征集作为最后选定的特征集。