随机森林

随机森林

?k）定义：随机森林是一个分类器，它有一系列的单株树决策器{h（X,，；k=1，......}

来组成,其中{?k}是独立同分布的随机变量。再输入X时，每一棵树只投一票给它认为最合适的类。在机器学习中，随机森林是一个包含多个决策树的分类器，

并且其输出的类别是由个别树输出的类别的众数而定,构成随机森林的基础分类器称为决策树。 Leo Breiman和Adele Cutler发展出推论出随机森林的算法。 这个术语是1995年由贝尔实验室的Tin Kam Ho所提出的随机决策森林（random decision forests）而来的。这个方法则是结合 Breimans 的 \想法和 Ho 的\以建造决策树的集合。 随机森林是一个组合分类器，构成随机森林的基础分类器是决策树。 决策树算法

决策树可以视为一个树状预测模型，它是由结点和有向边组成的层次结构。树中包含3个节点：根节点。内部节点，终节点（叶子节点）。决策树只有一个根节点，是全体训练集的结合。树中的每个内部节点都是一个分裂问题，它将到达该节点的样本按某个特定的属性进行分割，可以将数据集合分割成2块或若干块。每个终结点（叶子节点）是带有分裂标签的数据集合，从决策树的根节点到叶子节点的每一条路径都形成一个类；决策树的算法很多，例如ID3算法，CART算法等。这些算法均采用自上而下的贪婪的算法，每个内部节点选择分类效果最好的属性进行分裂节点，可以分为两个或若干个子节点，继续此过程到这可决策树能够将全部训练数据准确的分类，或所有属性都被用到为止。具体步骤如下： 1)假设T为训练样本集。

2)选择一个最能区分T中样本的一个属性。

3)创建一个数的节点，它的值是所选择的属性，创建此节点的子节点，每个子链代表所选属性的唯一值，适用子链的值进一步将样本细分为子类。 对于3)创建的三个子类

（1）如果子类的样本满足预定义的标准，或者树的这条路的剩余可选属性集为空，为沿此路径的新的样本指定类别。

（2）如果子类不满足于定义的标准，或者至少有一个属性能细分树的路径，设T为当前子类样本的集合，返回步骤2），以下简单的给出二分树的结构图示： 根节点 规则1 中间节点 叶节点 规则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(X,Y)?avI(h(x)?y)?maxgkkj?yavkI(hk(x)?j)

其中I(.)是示性函数，

avk(.)表示取平均。于是，边际函数刻画了在正确分类Y

PE?PX,Y(mg(X,Y)?0)?下X的得票超过其他分类的最大平均得票数的程度。该值越大，表明分类器的置信度越高。泛化误差由下式得出：

其中，下标X,Y表明了概率的定义空间。 在随机森林中，hk(x)

=h（x，θk）。当树的数目很大时，它会遵循大数定律，

?pE因此树的结构为：随着分类树数目的增加，由于所有的序列θi，几乎处处

收敛到

pX,Y(p(h(X,?)?y)?y?max?j?Yp?(h(x,?)?j?0)

其中θ是对应单棵树决策树的随机变量，h（x，θ）是基于x和θ的输出。

这以结果解释了为什么随机森林不会随着分布树的增加而产生过拟合，但是却有一个有限的繁华误差值。它的依据是大数定律。

在有关随机森林的实验中，装袋方法和随机特征选择并行应用。袋装方法的每一个新的训练集都是在原始训练集中通过一种叫做步步为营法随机重复采样得到的。应用这种方法的训练集一般只能包含原训练集中大约百分之六十七的样本，其余的样本作为袋外数据，基于新的训练集生成树可以充分的成长，不进行剪枝。

应用袋装方法的两个原因。其一，当使用随机特征时，结合袋装方法可以提高精

?pE度。其二，袋装方法可以对一个树集的总体泛化误差不断变化的上界进行估

计，与效能和相关性的估计一样的好。这一估计是由袋装的分类器给出的，解释

如下。

假定在任何训练集中用一种方法构造分类器。给定一个特殊的训练集T,构造步步为营训练集Tk，构建分类器h（X,Tk）,由投票构成松弛的预测器。对于训练集T中的每一个数y，x

将不包含y，x的分类器Tk上得到的票数累加起来，称之为袋外数据分类器。繁

华误差的袋外数据估计就是训练集上的袋外数据分类器的误差率。 在步步为营法的训练集中，大约三分之一的样本被取出。这样给出的内部股就有利于理解分类器的精度，有利于找到提高精度的方法。另外一个重要的应用在于刻画变量的重要性。

随机森林的重要性是计算单个特征的重要性。对于重要性的度量基于以下的启发式思维：当一个相关特征（即对预测的准确率可能起重要作用的特征）加入噪声后，随机森林的预测准确率将显著降低。具体做法如下：

1）对已生成的随机森林用袋外数据测试其性能，得到一个袋外准确率；

2）随机的改变袋外数据集中的某个特征值（即人为的加入噪声）再用加入噪声的袋外数据测试随机森林的性能，又得到一个新的袋外数据准确率。

3）原始的袋外数据的准确率与加入噪声后的袋外准确率之差，可以作为所选特征的重要性的度量值。这一值越大说明所选的特征的重要性越高。

随机森林的这一性能可以用来寻找某一个烟具过程中最重要的一些变量。找到这些变量之后可以通过这些重要的变量来控制整个研究的进程。从而可已将一个复杂的研究过程简单化。 随机森林的常见的构建方法

构建随机森林的方法可谓是多种多样，我们可以结合自己的需要找到适合自己的构建随机森林的方法。

（1）袋装法是一个统计冲采样的组合技术，它以步步为营和数据融合技术为基础。袋装法最基本的思想是利用步步为营的法重采样来生成多个版本的预测器，然后把这些分类器融合。实际上是将所有的分类器进行组合。通常情况下的组合的分类器会给出比单一分类器的效果要好，原因是最终解决问题时结合了所有单独分类器的特点。步步为营法是以可重复的随机采样为基础的。在训练集上可重复的随机采样，就可以得到没有或者含有很少的误导率的训练样本集。如前所述，当在训练集上采样步步为营的方法采样时，平均百分之三十七的根部不会出现在步步为营采集的样本集合中，这就意味着训练集中的 这些可能的“异常点”往往不会出现在步步为营法采集的样本集合中。因此，与在原始的数据上构建分类器相比，在步步为营法采集的样本结合中更容易得到好的分类器。所以，比其他步步为营的版本在最终的判断更稳健。 Bagging RF算法课描述如下：

Step1:对于给定的一个训练样本，通过n次随机的可重复的采样，从数据（x1，

yy1）.....（x,

nyn）出发构建一个步步为营的样本（x，

?1?1），.......（xn ，

?）。

Step2:基于每一个步步为营样本，构建一颗决策树。 Step3:重复Step1-2，可以得到多棵树。

ny?Step4:让每一棵树都对输入的向量xi进行投票。

Step5:计算所有的投票数，找出其中票数最高的一个就是向量xi的分类标签。 Step6:于正确的分类标签不一样的比例，就是随机森林的错误分类率。

（2）更新权重的随机森林方法有三只：Adaboost，加弧法，Arc—x4算法。Adaboost算法是所有更新权重算法中最重要的一个。很多的随机森林的分类效

果都是将Adaboost作为参照系的。

Adaboost算法是一个确定的算法目的是在前面分类器的错误分类的基础上为下一个分类器的输入选择训练集上的权重，每个分类器都可以利用一个训练集和一个加权训练集来改进。考虑如下的随机森林： 设w(1),.....w(k)

(?wj(k)?1wj(k)??0)j为关于训练集的K个不同的权重的

向量，对训练集进行K种不同方式的加权，那么，所得到的加权数据全体构成

一个大集合，特别取权重为概率p（1）.......p（k）且i?1?p(i)?1k时，依据概率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(wk)=log??1?error(k)?/error(k)?成正比，其中

error(k)是以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）的最大整数的误差之间的绝对误差不超过百分之一。