随机森林
θk）；k=1，......}定义：随机森林是一个分类器，它有一系列的单株树决策器{h（X,，
θk}是独立同分布的随机变量。再输入X时，每一棵树只投一票给来组成,其中{
它认为最合适的类。在机器学习中，随机森林是一个包含多个决策树的分类器，并且其输出的类别是由个别树输出的类别的众数而定,构成随机森林的基础分类器称为决策树。Leo Breiman和Adele Cutler发展出推论出随机森林的算法。这个术语是1995年由贝尔实验室的Tin Kam Ho所提出的随机决策森林（random decision forests）而来的。这个方法则是结合Breimans 的"Bootstrap aggregating" 想法和Ho 的"random subspace method"" 以建造决策树的集合。随机森林是一个组合分类器，构成随机森林的基础分类器是决策树。
决策树算法
决策树可以视为一个树状预测模型，它是由结点和有向边组成的层次结构。树中包含3个节点：根节点。内部节点，终节点（叶子节点）。决策树只有一个根节点，是全体训练集的结合。树中的每个内部节点都是一个分裂问题，它将到达该节点的样本按某个特定的属性进行分割，可以将数据集合分割成2块或若干块。每个终结点（叶子节点）是带有分裂标签的数据集合，从决策树的根节点到叶子节点的每一条路径都形成一个类；决策树的算法很多，例如ID3算法，CART算法等。这些算法均采用自上而下的贪婪的算法，每个内部节点选择分类效果最好的属性进行分裂节点，可以分为两个或若干个子节点，继续此过程到这可决策树能够将全部训练数据准确的分类，或所有属性都被用到为止。具体步骤如下：
1)假设T为训练样本集。
2)选择一个最能区分T中样本的一个属性。
3)创建一个数的节点，它的值是所选择的属性，创建此节点的子节点，每个子链代表所选属性的唯一值，适用子链的值进一步将样本细分为子类。
对于3)创建的三个子类
（1）如果子类的样本满足预定义的标准，或者树的这条路的剩余可选属性集为空，为沿此路径的新的样本指定类别。
（2）如果子类不满足于定义的标准，或者至少有一个属性能细分树的路径，设T为当前子类样本的集合，返回步骤2），以下简单的给出二分树的结构图示：
建树算法在属性的选择标准非常重要。属性的选择的方法有很多种，例如信息增益（information gain）、信息增益比（information gain ratio）Gini指标（Gini Index）等方法。
ID3算法依据信息增益来选择属性。信息增益是在熵作为尺度的，是衡量属性对训练数据的分类的能力的标准。CART算法是利用Gini指标作为尺度来分裂属性的。Gini指标适用于二进制连续数值等类型的字段。为了防止决策树和训练样本集的过度拟合，需要对决策树进行剪枝。剪枝通常有事先剪枝法和事后剪枝法两种方法。事先剪枝法事建树过程中判断当前节点是否需要继续划分的简直方
法。通常是通过重要性检测（ 2或信息增益等）判断是否停止分裂节点。事后
剪枝方法是让树“充分成长”之后在判断是否进行停止分裂节点。常用到的方法是根据错误分类率（或决策树编码长度）进行决策树的事后剪枝。决策树具有以下四个优点：
决策树方法不需要假设先验概率的分布，这种非参数化的特点使其具有更好的灵活性和鲁棒性。
决策树方法不仅可以利用连续实数或离散的数值样本，而且可以利用“语义数据”比如离散的语义数据：东、南、西、北等。
决策树方法产生的决策树或产生式规则具有结构简单直观，容易理解以及计算效率高的特点。
决策树方法能够有效地抑制训练样本噪音和解决属性缺失问题。因此可以防止由于训练样本存在噪声和数据确实引起的精度降低。
但决策树也有与生俱来的缺点：
1）分类规则杂
2）收敛到非全局的局部最优解
3）过度拟合由于分类复杂则它可能过于适合噪声从而导致过度拟合问题。
为了克服以上的缺点，引入了另一种预测模式——随机森林。
随机森林的特征
随机森林具有以下的特征：
在现有的算法中随机森林算法的精度是无可比拟的。
随机森林能够有效地处理大的数据集。
随机森里面可以处理没有删减的成千上万的变量。
随机森林能够在分类的过程中可以生成一个泛化误差的内部无偏估计。
随机森林是一种有效地估计缺失数据的一种方法，当数据集中有大比例的数据缺失时仍然可以保持精度不变。
在不平衡的数据集的类别总图中可以平衡误差。
保存生成的随机森林以备解决其他的数据。
技术原型的计算可以给出变量之间的相关性和分类的信息。
可以计算实例组之间的相似度，可以用来做聚类分析，确定异常点（通过缩放比例）给出数据集的有趣诠释。
上述的能力可以为没有标签的数据导出无监督的聚类方法和异常点检测。
随机森林提供了一种检测变量交互作用的实验方式。特别值得注意的是随机森林的运行速度非常的块并且不会产生过度拟合，可以根据需要来生成任意多的树。
基于随机树上的诸多优点，随机森林在当前的机器学习领域是一个新的研究热点。
随机森林的理论基础
随机森林之所有那么多的优点，是因为有强大的数学知识做后盾。一个随机森林是否能够进行正确的分类，分类的效果如何，以及如何评价随机森林的分类效果都有数学知识的基础。
R.F 不会过度拟合的保证——大数定律
随机森林的一个与众不同的特征就是它不会产生过度拟合。那么它为什么不会产生过度拟合呢？不会产生过度拟合的理论依据是什么呢？下面解释这一个问题。 给定一系列分类器h （x ，θ1），h （x ，θ2），，，，，，h （x ，θk ）随机取出服从随机向量Y ,X 分布的训练集。定义边际函数为：
))((m ax
))((),(j x I a y x I a Y X h v h v m k k y j k k g =-==≠ 其中I(.)是示性函数，(.)v k a 表示取平均。于是，边际函数刻画了在正确分类Y
下X 的得票超过其他分类的最大平均得票数的程度。该值越大，表明分类器的
置信度越高。泛化误差由下式得出：
)0),((,<=*Y X P m P E g Y X 其中，下标X,Y 表明了概率的定义空间。
在随机森林中，)(x h k =h （x ，θk ）。当树的数目很大时，它会遵循大数定律，
因此树的结构为：随着分类树数目的增加，由于所有的序列θi ，*pE 几乎处处
收敛到
)
0),((m ax )),(((,<=-==≠j x h y y X h p p p Y
j Y X θθθθ
其中θ是对应单棵树决策树的随机变量，h （x ，θ）是基于x 和θ的输出。 这以结果解释了为什么随机森林不会随着分布树的增加而产生过拟合，但是却有一个有限的繁华误差值。它的依据是大数定律。
在有关随机森林的实验中，装袋方法和随机特征选择并行应用。袋装方法的每一个新的训练集都是在原始训练集中通过一种叫做步步为营法随机重复采样得到的。应用这种方法的训练集一般只能包含原训练集中大约百分之六十七的样本，其余的样本作为袋外数据，基于新的训练集生成树可以充分的成长，不进行剪枝。
应用袋装方法的两个原因。其一，当使用随机特征时，结合袋装方法可以提高精度。其二，袋装方法可以对一个树集的总体泛化误差*pE 不断变化的上界进行估计，与效能和相关性的估计一样的好。这一估计是由袋装的分类器给出的，解释如下。
假定在任何训练集中用一种方法构造分类器。给定一个特殊的训练集T,构造步步为营训练集T k ，构建分类器h （X,T k ）,由投票构成松弛的预测器。对于训练集T 中的每一个数y ，x
将不包含y ，x 的分类器T k 上得到的票数累加起来，称之为袋外数据分类器。繁
华误差的袋外数据估计就是训练集上的袋外数据分类器的误差率。
在步步为营法的训练集中，大约三分之一的样本被取出。这样给出的内部股就有利于理解分类器的精度，有利于找到提高精度的方法。另外一个重要的应用在于刻画变量的重要性。
随机森林的重要性是计算单个特征的重要性。对于重要性的度量基于以下的启发式思维：当一个相关特征（即对预测的准确率可能起重要作用的特征）加入噪声后，随机森林的预测准确率将显著降低。具体做法如下：
1）对已生成的随机森林用袋外数据测试其性能，得到一个袋外准确率；
2）随机的改变袋外数据集中的某个特征值（即人为的加入噪声）再用加入噪声的袋外数据测试随机森林的性能，又得到一个新的袋外数据准确率。
3）原始的袋外数据的准确率与加入噪声后的袋外准确率之差，可以作为所选特征的重要性的度量值。这一值越大说明所选的特征的重要性越高。
随机森林的这一性能可以用来寻找某一个烟具过程中最重要的一些变量。找到这些变量之后可以通过这些重要的变量来控制整个研究的进程。从而可已将一个复杂的研究过程简单化。
随机森林的常见的构建方法
构建随机森林的方法可谓是多种多样，我们可以结合自己的需要找到适合自己的构建随机森林的方法。
（1）袋装法是一个统计冲采样的组合技术，它以步步为营和数据融合技术为基础。袋装法最基本的思想是利用步步为营的法重采样来生成多个版本的预测器，然后把这些分类器融合。实际上是将所有的分类器进行组合。通常情况下的组合的分类器会给出比单一分类器的效果要好，原因是最终解决问题时结合了所有单独分类器的特点。步步为营法是以可重复的随机采样为基础的。在训练集上可重复的随机采样，就可以得到没有或者含有很少的误导率的训练样本集。如前所述，当在训练集上采样步步为营的方法采样时，平均百分之三十七的根部不会出现在步步为营采集的样本集合中，这就意味着训练集中的 这些可能的“异常点”往往不会出现在步步为营法采集的样本集合中。因此，与在原始的数据上构建分类器相比，在步步为营法采集的样本结合中更容易得到好的分类器。所以，比其他步步为营的版本在最终的判断更稳健。
Bagging RF 算法课描述如下：
Step1:对于给定的一个训练样本，通过n 次随机的可重复的采样，从数据（x1，
y1）.....（x n ,y n ）出发构建一个步步为营的样本（x *
1，y *1），.......（x n *
， y n *
）。
Step2:基于每一个步步为营样本，构建一颗决策树。
Step3:重复Step1-2，可以得到多棵树。 Step4:让每一棵树都对输入的向量x i 进行投票。
Step5:计算所有的投票数，找出其中票数最高的一个就是向量x i 的分类标签。 Step6:于正确的分类标签不一样的比例，就是随机森林的错误分类率。
（2）更新权重的随机森林方法有三只：Adaboost ，加弧法，Arc —x4算法。Adaboost 算法是所有更新权重算法中最重要的一个。很多的随机森林的分类效
果都是将Adaboost作为参照系的。
Adaboost算法是一个确定的算法目的是在前面分类器的错误分类的基础上为下一个分类器的输入选择训练集上的权重，每个分类器都可以利用一个训练集和一个加权训练集来改进。考虑如下的随机森林：
设w(1),.....w(k)
)0
)
(
1
)
(
(>=
=
∑k
k w
w j
j
j
为关于训练集的K个不同的权重的
向量，对训练集进行K种不同方式的加权，那么，所得到的加权数据全体构成
一个大集合，特别取权重为概率p（1）.......p（k）且∑
=
=
k
i
i
p
1
1
)(
时，依据概率p
（1）....p（k）从1,2,........k中抽取整数，记为θ。若θ=k，则利用训练集与权重w（k）产生分离器h（x，θ）。
使用Adaboost在某一数据集上运行了75次产生75个权重系数向量，舍弃前25个，保留后50个，记为w（1），w（2)........w(50).
第k个权系数向量的概率与Q(w k)=log()
[])(
/)
(
1k
error
k
error
-成正比，其中
)
(k
error是以w（k）为、加权的训练集产生的第k个分类器的误差。运行250次，其中在少量的数据集上重复了100次，每一次拿出百分之十作为检测集，然后将这100次的检测误差平均。
在每一个数据集上，Adaboost的误差率都非常的接近随机森林误差率。Adaboost具有许多优点，它运行快，简单，能够容易的进行编程。除了运行次数在没有其他的参数需要调节。不需要有关弱学习器的预备知识，并且容易结合任何方法结合来寻弱假设。结合这一系列的理论依据能够提供足够的数据和一个弱假设学习器，这一弱假设学习器能够有效地提供净度适中的弱假设。另外aDaboost还有一些注意事项。在特定的问题上，助推法的实际运行情况很明显的依赖于数据本身和弱学习器，理论上，如果所给的数据不够充分，并且是在复杂的弱假设或者弱的弱假设集上的话，助推法不会很好的表现。另外助推法特别容易受到噪声的影响。
（3）基于输入构建随机森林
基于输入创建随机森林的方法根据输入方式的不同给出了三种不同形式的构建方法。第一种是Forestes—RI，第二种是Forestes—RC，第三种是分类变数。Forestes—RI对输入的变量随机分组（每组变量的个数F是一个定值）。然后对于每组随机变量，利用CART的方法种植一株树，并让其充分成长，不进行剪枝。在每个节点上，对输入该节点的变量，重复上面的随机分组，再重复CART方法直到将所有的节点均为叶子节点为止。一般F有两种选择，首先是F=1；再次取F为小于log（m+1）的最大正整数，其中M是输入变量的个数。
该方法的优点如下：
由此构建的随机森林的精度可以与Adaboost相媲美。
与利用所有随机变量构建随机森林运行时间复杂度是F*log（N）/M，其中N是样本的数目。
利用F=1时的误差与F为小于log（M+1）的最大整数的误差之间的绝对误差不超过百分之一。
Forestes—RC是将随机特征进行线性组合，然后再作为输入变量来构建随机森林的方法。随机选择L个输入变量进行线性的组合得到新的特征（不同的L值对应不同的特征）。在每个节点上，随机选出L个变量v1，v2,......vl 及L个随机数
ki做不同的线性组合
]1,1
[
,
1
-
∈
=∑
=
k
v
k i i
l
i
i
V
。一般的，对于给定的集合Ｍ具有Ｏ
（l
M）种不同的输入变量的组合，为此我们仅仅考虑L=3的情形。由于袋外数据估计依赖F的选择，F=2时接近最小值，分类效能会随着F的增大而增大，但是相关性不会有明显的增加。所以再大的数据集上，一般选择F=8可以给出较好的效果。这种方法的优点如下：
可以处理具有不同量纲的输入变量的数据集。
在打烊本的数据输入集上有最佳的表现。
精度与Adaboost的精度最接近。
（4）基于输出构建随机森林
装袋法和助推法通过改变输入输出来构建扰动训练集，他们都降低了误差。如果仅仅只是对输出进行扰动，是否可以得到相似的性能。我们研究了两种随机化输出的方法。一种是输出拖尾法，指的是将高斯噪声加入到输出过程中，另一种是输出浮动法，指的是改变某一个或者若干个输出的分类的标签改变的程度是由一个称为浮动率的实值参数来衡量的。浮动输出法与拖尾法不同的是，输出浮动依赖于浮动率的选则。共同点是两种方法都可以进行回归和分类而且效果都好于袋装法。
基于输出构建的随机森林的一个重要特征是能计算单个特征的重要性。对特征重要性的度量是基于以下的富有启发的思路：当对一个特征加入噪声之后，RF的准确率将会发生变化，如果加噪声后的袋装估计的误差率大幅度的增加，就说明该特征的重要性较高。将每个特征的袋外估计的增幅都算出来之后，进行比较，其中增幅最大的一个就是最重要的一个。
Dietterrich的研究表明，当训练集结果标签的一小部分被随机的改变时，Adaboost 的精度会降低，而袋装法和随机分裂选择都对噪声有很强的免疫力。由于输出结果中往往混入噪声，鲁棒性是防止噪声的一个理想性质。Dietterrich的试验如下：每次改变二十分之一的标签（注入百分之五的噪声），在试验中一次数据集中随机分出的百分之十的检测集，将剩余的作为训练集，首先在该训练集上进行，然后将训练集中的百分之五的分类标签更改作为新的训练集进行新的运算。针对AdAaboost 森林—RI，森林—RC三种，将这一过程重复50次并且将50次的检测结果平均，百分比的增加是因为考虑噪声的缘故。至于两种随机森林，我们采用的特征是Breiman的试验中已经证明了具有最低的误差集合。考虑到运算时间长度，只选择了九个较小的数据集。针对这九个数据集合他们列出了由噪声引起的误差的增量。
由引入噪声导致的误差率的增加
的比较稳定，变化较小。Adaboost表现出了不同寻常的数据依赖性，在glass与ecoli还有diabetes三个集合中，Adaboost受噪声影响最小。实验表明，错误标签将导致错误分类。总之，Adaboost因在乎放大具有噪声的事件的权重而有偏颇；随机森林不会集中权重于具体的子集，因此噪声对其影响较小。
（5）基于随机选择的特征子空间构建随机森林
由随机选择的子空间来构建随机森林的方法是依赖于一个自主的，伪随机的从给定的特征空间选择少量维数的过程。在每一个传递中，都是惊醒一次这样的选择，并且子空间是固定的，这以子空间中的所有的点在没有选定的维数中都对应一个个值。所有的样本被添加到这一个子空间中，并且利用别的样本被添加到同样的
子空间，并利用相应的树进行分类。、对于已给定的n维空间可以做n2种那样的
选择，对于每一个选择都可以构建一个决策树。如果子空间是在数的内部变化，也就是说每一次的分割中采用不同维数的特征的话，就可以得到更多不同的树。在选择维数的时候利用随机性只是便于找到可能性。在每一个选定的子空间上构建的树，都是利用所有的数据充分分割得到的。因此，它们都能够正确的认识训练集中的那些被假设为没有模糊性的样本。对于与训练集样本只是在没有选中的特征是上的不同的点来说，每棵树的分类是不变的，这样的每棵树都以不同的方式生成一个类。在高维的特征空间中大量的子空间就可以提供比实际需要多的选择。这样，在多数的其他类型的分类器都在饱受够面性造成的痛苦的时候，随机选择的子空间来构建随机森林的方法可以以高维数作为一个特征。随机选择的子空间来构建随机森林的方法随着它的构造的复杂化会提高整体的精度。随机选择的子空间来构建随机森林的方法是一种并行学习的算法。即随机选择的子空间来构建随机森林的方法中的每一颗决策树的生成都是独立的。这就是得它能够适应于快速学习的并行实现，在一些实际问题中快速学习是备受关注的。还有就是，因为这里没有山可以爬，所以就没有陷入举步优选的困境。将利用子空间得到的森林和其他方式得到的随机森林进行了比较，得到这样的结论：在实验中多用到的四个数据集中随机选择的子空间来构建随机森林的方法明显要由于单的分类效果，随机选择的子空间来构建随机森林的方法在相关的低维空间上也能够正常的工作。将随机选择的子空间来构建随机森林的方法与步步为营的方法、助推法进行比较，结果表明虽然就独立树而言，步步为营法、助推法这些利用冲采样办法得到的树有时会有更好的精度，但是对于多棵树而言，随机选择的子空间来构建随机森林的方法的镜度是最优的。
随机森林算法的优点：
对于很多种资料，它可以产生高准确度的分类器。
它可以处理大量的输入变量。
它可以在决定类别时，评估变量的重要性。
在建造森林时，它可以在内部对于一般化后的误差产生不偏差的估计。
它包含一个好方法可以估计遗失的资料，并且，如果有很大一部分的资料遗失，仍可以维持准确度。
它提供一个实验方法，可以去侦测variable interactions 。
对于不平衡的分类资料集来说，它可以平衡误差。
它计算各例中的亲近度，对于数据挖掘、侦测偏离者（outlier）和将资料视觉化非常有用。
随机森林算法的应用
随机森林作为一个有效快捷的分类器，被应用到很多的领域上和专业内。举例如下：
（1）随机森林在经济中的应用
在经济迅猛发展的今天，企业的信用已经成为一个备受关注的问题，尤其是在银行的贷款业务中，能够准确的评估企业的信用就意味着能够有效地回收贷款。因此建立能够准确评估企业信用的模型成为了一个研究的热点。由于目前国内的信用研究评估学者采用的指标也各不相同，因此专家建议，采用适当的学习算法确定信用评估中的指标的重要性，并在此基础上进一步确定评估模型所需的指标体系。由于信用评估模型的数据特征很多、噪声很大、而随机森林特备适合对于高维度空间进行特征选择，当噪声出现的时候也能表现出较好的性能，并且随机森林还有一个显著地特征是能够计算单个特征的重要性，所以将随机森林应用到了评估模型指标体系确定中。
（2）随机森林在文档检索中的应用
随着信息的发展，信息处理已经成为人们获取有用信息不可缺少的工具。随机森林中的数据挖掘的功能是其他分类方法不能比拟的。随机森林在文档检索中的应用算法如下：
首先，建立向量模型，采用给定的权重计算方法，所有的样本用词向量表示。其次，构造随机森林分类器。
最后，利用随机森林进行分类，把测试集作为上一步训练得到的模型的输入，最终由投票来决定各实例的类标签。
（3）随机森林在医学诊断上的应用
随机森林自身的结构决定了它能够处理具有很多弱输入的数据集。而这种弱输入的数据集在医院诊断里是最常见的。因此将随机森林引入到医学诊断中是一个必然的趋势。随机森林是由多个分类器组合得到的组合分类器，是一种能够提高分类标准率的方法。将自助法采样、未剪枝的二叉树分类应用到多普磁共振的图像分割技术中。为了精确地测试随机森里吗的分类效果，引入了加拿大里尔神经学学院的数据采用了DSC来计算随机森林的分割效果。随机森林在多普磁共振的图像分割的应用中显示出实现简单、速度快、精度高的特点。是一种有前景的多通道图像分割方法。因为在这以应用中没有考虑到体素之间的相关性，所以随机森林受噪声影响的程度较大。
随机森林的展望
随机森林作为一种非常快捷的机器学习的方法在分类和回归中都有重要的应用。虽然它的回归和分类的效果已经达到了相当的水平，但是并能睡随机森林就没有再发展的空间了我们今后的工作是找到改善随机森林的方法；进一步发展新的或完善已有的支持随机森林的软件；将随机森林应用到更广阔的范围上。