随机森林(精)

1、随机森林定义:随机森林是一个分类器,它有一系列的单株树决策器h（X,&x ）；k=l,.I来组成，其中& 是独立同分布的随机变量。再输入X时，每一棵树只投一票给 它认为最合适的类。在机器学习中，随机森林是一个包含多个决策树的分类器， 并且其输出的类别是山个别树输出的类别的众数而定，构成随机森林的基础分类 器称为决策树。Leo Breiman和Adele Cutler发展出推论出随机森林的算法。这 个术语是1995年山贝尔实验室的Tin Kam Ho所提出的随机决策森林（random decision forests）而来的。这个方法则是结合 Breimans 的 HBootst

2、rap aggregating*1 想法和Ho的"random subspace method""以建造决策树的集合。随机森林是一 个组合分类器，构成随机森林的基础分类器是决策树。决策树算法决策树可以视为一个树状预测模型，它是山结点和有向边组成的层次结构。树中 包含3个节点：根节点。内部节点，终节点（叶子节点）。决策树只有一个根节 点，是全体训练集的结合。树中的每个内部节点都是一个分裂问题，它将到达该 节点的样本按某个特定的属性进行分割，可以将数据集合分割成2块或若干块。 每个终结点（叶子节点）是带有分裂标签的数据集合，从决策树的根节点到叶子 节点的每一条路径都形

3、成一个类；决策树的算法很多，例如ID3算法，CART算 法等。这些算法均釆用自上而下的贪婪的算法，每个内部节点选择分类效果最好 的属性进行分裂节点，可以分为两个或若干个子节点，继续此过程到这可决策树 能够将全部训练数据准确的分类，或所有属性都被用到为止。具体步骤如下：1）假设T为训练样本集。2）选择一个最能区分T中样本的一个属性。3）创建一个数的节点，它的值是所选择的属性，创建此节点的子节点，每个子链 代表所选属性的唯一值，适用子链的值进一步将样本细分为子类。对于3）创建的三个子类（1）如果子类的样本满足预定义的标准，或者树的这条路的剩余可选属性集为 空，为沿此路径的新的样本指定类别。（2）如

4、果子类不满足于定义的标准，或者至少有一个属性能细分树的路径，设 T为当前子类样本的集合，返回步骤2）,以下简单的给出二分树的结构图示： 建树算法在属性的选择标准非常重要。属性的选择的方法有很多种，例如信息增 益（information gain） 信息增益比（information gain ratio） Gini 指标（Gini Index） 等方法。规则2ID3算法依据信息增益来选择属性。信息增益是在爛作为尺度的，是衡量属性对 训练数据的分类的能力的标准。CART算法是利用Gini指标作为尺度来分裂属 性的。Gini指标适用于二进制连续数值等类型的字段。为了防止决策树和训练样 本集的过度拟

5、合，需要对决策树进行剪枝。剪枝通常有事先剪枝法和事后剪枝法 两种方法。事先剪枝法事建树过程中判断当前节点是否需要继续划分的简直方 法。通常是通过重要性检测（才或信息增益等）判断是否停止分裂节点。事后 剪枝方法是让树“充分成长”之后在判断是否进行停止分裂节点。常用到的方法 是根据错误分类率（或决策树编码长度）进行决策树的事后剪枝。决策树具有以 下四个优点：决策树方法不需要假设先验概率的分布，这种非参数化的特点使其具有更好的灵 活性和鲁棒性。决策树方法不仅可以利用连续实数或离散的数值样本，而且可以利用“语义数据” 比如离散的语义数据：东、南、西、北等。决策树方法产生的决策树或产生式规则具有结构简单

6、直观，容易理解以及计算效 率高的特点。决策树方法能够有效地抑制训练样本噪音和解决属性缺失问题。因此可以防止山 于训练样本存在噪声和数据确实引起的精度降低。但决策树也有与生俱来的缺点：1）分类规则杂2）收敛到非全局的局部最优解3）过度拟合山于分类复杂则它可能过于适合噪声从而导致过度拟合问题。为了克服以上的缺点，引入了另一种预测模式一一随机森林。随机森林的特征随机森林具有以下的特征：在现有的算法中随机森林算法的精度是无可比拟的。随机森林能够有效地处理大的数据集。随机森里面可以处理没有删减的成千上万的变量。随机森林能够在分类的过程中可以生成一个泛化误差的内部无偏估计。随机森林是一种有效地估计缺失数据

7、的一种方法，肖数据集中有大比例的数据缺 失时仍然可以保持精度不变。在不平衡的数据集的类别总图中可以平衡误差。保存生成的随机森林以备解决其他的数据。技术原型的计算可以给出变量之间的相关性和分类的信息。可以计算实例组之间的相似度，可以用来做聚类分析，确定异常点（通过缩放比 例）给岀数据集的有趣诠释。上述的能力可以为没有标签的数据导出无监督的聚类方法和异常点检测。随机森林提供了一种检测变量交互作用的实验方式。特别值得注意的是随机森林 的运行速度非常的块并且不会产生过度拟合，可以根据需要来生成任意多的树。 基于随机树上的诸多优点，随机森林在当前的机器学习领域是一个新的研究热 点。随机森林的理论基础随机

8、森林之所有那么多的优点，是因为有强大的数学知识做后盾。一个随机森林 是否能够进行正确的分类，分类的效果如何，以及如何评价随机森林的分类效果 都有数学知识的基础。R.F不会过度拟合的保证一一大数定律 随机森林的一个与众不同的特征就是它不会产生过度拟合。那么它为什么不会产 生过度拟合呢？不会产生过度拟合的理论依据是什么呢？下面解释这一个问题。 给定一系列分类器h (x, 0 1), h (x, 0 2), h (x, 0 k)随机取出服从 随机向量Y,X分布的训练集。定义边际函数为：mX,Y) = a Vk(x) = y) - max 庄"必叽=7)其中1(.)是示性函数，"必

9、°)表示取平均。于是，边际函数刻画了在正确分类Y 下X的得票超过其他分类的最大平均得票数的程度。该值越大，表明分类器的 置信度越高。泛化误差由下式得出：PE 川曲x，Y)<°) 其中，下标X,Y表明了概率的定义空间。在随机森林中，(X)=h (x, Ok)。当树的数目很大时，它会遵循大数定律， 因此树的结构为：随着分类树数LI的增加，山于所有的序列0i, pF儿乎处处 收敛到Px.y(PM(X£)= y) = >'-max 寸 p&(h(x,0) = j<0)其中0是对应单棵树决策树的随机变量，h (x, 0 )是基于x和0的输出

10、。 这以结果解释了为什么随机森林不会随着分布树的增加而产生过拟合，但是却有 一个有限的繁华误差值。它的依据是大数定律。在有关随机森林的实验中，装袋方法和随机特征选择并行应用。袋装方法 的每一个新的训练集都是在原始训练集中通过一种叫做步步为营法随机重复采 样得到的。应用这种方法的训练集一般只能包含原训练集中大约白分之六十七的 样本，其余的样本作为袋外数据基于新的训练集生成树可以充分的成长，不进 行剪枝。应用袋装方法的两个原因。其一，当使用随机特征时，结合袋装方法可以提高精 度。其二，袋装方法可以对一个树集的总体泛化误差不断变化的上界进行估 计，与效能和相关性的佔计一样的好。这一估计是由袋装的分类

11、器给出的，解释 如下。假定在任何训练集中用一种方法构造分类器。给定一个特殊的训练集T,构造步步 为营训练集匚，构建分类器h (X,几)，由投票构成松弛的预测器。对于训练集 T中的每一个数y, x将不包含y, x的分类器丁女上得到的票数累加起来，称之为袋外数据分类器。繁 华误差的袋外数据估计就是训练集上的袋外数据分类器的误差率。在步步为营法的训练集中，大约三分之一的样本被取出。这样给出的内部股就有 利于理解分类器的精度，有利于找到提高精度的方法。另外一个重要的应用在于 刻画变量的重要性。随机森林的重要性是计算单个特征的重要性。对于重要性的度量基于以下的启发 式思维：当一个相关特征（即对预测的准确

12、率可能起重要作用的特征）加入噪声 后，随机森林的预测准确率将显著降低。具体做法如下：1）对已生成的随机森林用袋外数据测试其性能，得到一个袋外准确率；2）随机的改变袋外数据集中的某个特征值（即人为的加入噪声）再用加入噪声 的袋外数据测试随机森林的性能，乂得到一个新的袋外数据准确率。3）原始的袋外数据的准确率与加入噪声后的袋外准确率之差，可以作为所选特 征的重要性的度量值。这一值越大说明所选的特征的重要性越高。随机森林的这一性能可以用来寻找某一个烟具过程中最重要的一些变量。找到这 些变量之后可以通过这些重要的变量来控制整个研究的进程。从而可已将一个复 杂的研究过程简单化。随机森林的常见的构建方法构

13、建随机森林的方法可谓是多种多样，我们可以结合自己的需要找到适合自己的 构建随机森林的方法。（1）袋装法是一个统汁冲釆样的组合技术，它以步步为营和数据融合技术为基 础。袋装法最基本的思想是利用步步为营的法重采样来生成多个版本的预测器， 然后把这些分类器融合。实际上是将所有的分类器进行组合。通常情况下的组合 的分类器会给岀比单一分类器的效果要好，原因是最终解决问题时结合了所有单 独分类器的特点。步步为营法是以可重复的随机釆样为基础的。在训练集上可重 复的随机采样，就可以得到没有或者含有很少的误导率的训练样本集。如前所述, 当在训练集上采样步步为营的方法采样时，平均白分之三十七的根部不会出现在 步步

14、为营釆集的样本集合中，这就意味着训练集中的这些可能的“异常点”往 往不会出现在步步为营法采集的样本集合中。因此，与在原始的数据上构建分类 器相比，在步步为营法釆集的样本结合中更容易得到好的分类器。所以，比其他 步步为营的版本在最终的判断更稳健。Bagging RF算法课描述如下：Stepl：对于给定的一个训练样本，通过n次随机的可重复的采样，从数据（xl, * yl）（凡，）'“）出发构建一个步步为营的样本（兀，i）,（兀”，0 ）。Step2:基于每一个步步为营样本，构建一颗决策树。Step3：重复Stepl-2,可以得到多棵树。Step4:让每一棵树都对输入的向量兀进行投票。Ste

15、P5:计算所有的投票数，找出其中票数最高的一个就是向量兀的分类标签。Step6:于正确的分类标签不一样的比例，就是随机森林的错误分类率。（2）更新权重的随机森林方法有三只：Adaboost,加弧法，Arcx4算法。Adaboost算法是所有更新权車算法中最巫要的一个。很多的随机森林的分类效果都是将Adaboost作为参照系的。Adaboost算法是一个确定的算法U的是在前面分类器的错误分类的基础上为下 一个分类器的输入选择训练集上的权重，每个分类器都可以利用一个训练集和一 个加权训练集来改进。考虑如下的随机森林：(工 W“)Tw丿伙)>=0)设w(l),.w(k)-为关于训练集的K个不同

16、的权重的向量，对训练集进行K种不同方式的加权，那么，所得到的加权数据全体构成X “=1一个大集合，特别取权重为概率p (1)p (k)且I时，依据概率P(1) .p (k)从1,2,.k中抽取整数，记为0。若0二k,则利用训练集与权重 W (k)产生分离器h (x, o )o使用Adaboost在某一数据集上运行了 75次产生75个权重系数向量，舍弃前25 个，保留后50个，记为w (1), w (2)w(50).第k个权系数向量的概率与Q(冋)二g(l-劲"伙)/M"伙)成正比，其中 纣厂"伙)是以w (k)为、加权的训练集产生的第k个分类器的误差。运行250

17、次，其中在少量的数据集上重复了 100次，每一次拿出白分之十作为检测集，然 后将这100次的检测误差平均。在每一个数据集上，Adaboost的误差率都非常的接近随机森林误差率。Adaboost具有许多优点，它运行快，简单，能够容易的进行编程。除了运行次数 在没有其他的参数需要调节。不需要有关弱学习器的预备知识，并且容易结合任 何方法结合来寻弱假设。结合这一系列的理论依据能够提供足够的数据和一个 弱假设学习器，这一弱假设学习器能够有效地提供净度适中的弱假设。另外 aDaboost还有一些注意事项。在特定的问题上，助推法的实际运行情况很明显的 依赖于数据本身和弱学习器，理论上，如果所给的数据不够充

18、分，并且是在复杂 的弱假设或者弱的弱假设集上的话，助推法不会很好的表现。另外助推法特别容 易受到噪声的影响。(3) 基于输入构建随机森林基于输入创建随机森林的方法根据输入方式的不同给出了三种不同形式的构建 方法。第一种是Forestes一RI,第二种是ForestesRC,笫三种是分类变数。Forestes-RI对输入的变量随机分组(每组变量的个数F是一个定值)。然后对 于每组随机变量，利用CART的方法种植一株树，并让其充分成长，不进行剪枝。 在每个节点上，对输入该节点的变量，重复上面的随机分组，再重复CART方法 直到将所有的节点均为叶子节点为止。一般F有两种选择，首先是F=l；再次取 F

19、为小于log (m+1)的最大正整数，其中M是输入变量的个数。该方法的优点如下：由此构建的随机森林的精度可以与Adaboost相媲美。与利用所有随机变量构建随机森林运行时间复杂度是F*log (N) /M,其中N是 样本的数目。利用F=1时的误差与F为小于log (M+1)的最大整数的误差之间的绝对误差不 超过白分之一。Forestes-RC是将随机特征进行线性组合，然后再作为输入变量来构建随机森林 的方法。随机选择L个输入变量进行线性的组合得到新的特征（不同的L值对 应不同的特征）。在每个节点上，随机选出L个变量vl, v2,.vl及L个随机数/=工化必&引一1，11ki做不同的线性

20、组合j。一般的，对于给定的集合M具有0（M）种不同的输入变量的组合，为此我们仅仅考虑L=3的情形。由于袋外数 据估讣依赖F的选择，F=2时接近最小值，分类效能会随着F的增大而增大，但 是相关性不会有明显的增加。所以再大的数据集上，一般选择F=8可以给岀较 好的效果。这种方法的优点如下： 可以处理具有不同量纲的输入变量的数据集。在打炜本的数据输入集上有最佳的表现。 精度与Adaboost的精度最接近。（4）基于输出构建随机森林装袋法和助推法通过改变输入输出来构建扰动训练集，他们都降低了误差。如果 仅仅只是对输出进行扰动，是否可以得到相似的性能。我们研究了两种随机化输 出的方法。一种是输出拖尾法，

21、指的是将高斯噪声加入到输出过程中，另一种是 输岀浮动法，指的是改变某一个或者若干个输出的分类的标签改变的程度是山一 个称为浮动率的实值参数来衡量的。浮动输出法与拖尾法不同的是，输出浮动依 赖于浮动率的选则。共同点是两种方法都可以进行回归和分类而且效果都好于袋 装法。基于输出构建的随机森林的一个重要特征是能计算单个特征的重要性。对特征重 要性的度量是基于以下的富有启发的思路：当对一个特征加入噪声之后，RF的 准确率将会发生变化，如果加噪声后的袋装佔计的误差率大幅度的增加，就说明 该特征的重要性较高。将每个特征的袋外估计的增幅都算岀来之后，进行比较， 其中增幅最大的一个就是最重要的一个。Diett

22、errich的研究表明，当训练集结果标签的一小部分被随机的改变时，Adaboost 的精度会降低，而袋装法和随机分裂选择都对噪声有很强的免疫力。山于输出结 果中往往混入噪声，鲁棒性是防止噪声的一个理想性质。Dietterrich的试验如下: 每次改变二十分之一的标签（注入百分之五的噪声），在试验中一次数据集中随 机分出的白分之十的检测集，将剩余的作为训练集，首先在该训练集上进行，然 后将训练集中的白分之五的分类标签更改作为新的训练集进行新的运算。针对 AdAaboost森林一RL森林一RC三种，将这一过程重复50次并且将50次的检 测结果平均，白分比的增加是因为考虑噪声的缘故。至于两种随机森林

23、，我们采 用的特征是Breiman的试验中已经证明了具有最低的误差集合。考虑到运算时间 长度，只选择了九个较小的数据集。针对这九个数据集合他们列出了山噪声引起 的误差的增量。山引入噪声导致的误差率的增加数据集AdaboostF RIF RCGlass1.60.4-04Breast cancer43.21.811.1Diabetes6.81.72.8Sonar15.1-6.64.2Ionosphere27.73.85.7Soybean26.93.28.5Ecoli7.57.97.8Votes48.96.34.6Liver10.3-0.24.8在白分之五的噪声的水平下，Adaboost更现显著地不

24、好，然而随机森林总体表现的比较稳定，变化较小。Adaboost表现出了不同寻常的数据依赖性，在glass与 ecoli还有diabetes三个集合中，Adaboost受噪声影响最小。实验表明，错误标签 将导致错误分类。总之，Adaboost因在乎放大具有噪声的事件的权重而有偏颇; 随机森林不会集中权重于具体的子集，因此噪声对其影响较小。（5）基于随机选择的特征子空间构建随机森林山随机选择的子空间来构建随机森林的方法是依赖于一个自主的，伪随机的从给 定的特征空间选择少量维数的过程。在每一个传递中，都是惊醒一次这样的选择, 并且子空间是固定的，这以子空间中的所有的点在没有选定的维数中都对应一个 个

25、值。所有的样本被添加到这一个子空间中，并且利用别的样本被添加到同样的 子空间，并利用相应的树进行分类。、对于已给定的n维空间可以做2"种那样的 选择，对于每一个选择都可以构建一个决策树。如果子空间是在数的内部变化， 也就是说每一次的分割中采用不同维数的特征的话，就可以得到更多不同的树。 在选择维数的时候利用随机性只是便于找到可能性。在每一个选定的子空间上构 建的树，都是利用所有的数据充分分割得到的。因此，它们都能够正确的认识训 练集中的那些被假设为没有模糊性的样本。对于与训练集样本只是在没有选中的 特征是上的不同的点来说，每棵树的分类是不变的，这样的每棵树都以不同的方 式生成一个类。

26、在高维的特征空间中大量的子空间就可以提供比实际需要多的选 择。这样，在多数的其他类型的分类器都在饱受够面性造成的痛苦的时候，随机 选择的子空间来构建随机森林的方法可以以高维数作为一个特征。随机选择的子 空间来构建随机森林的方法随着它的构造的复杂化会提高整体的精度。随机选择 的子空间来构建随机森林的方法是一种并行学习的算法。即随机选择的子空间来 构建随机森林的方法中的每一颗决策树的生成都是独立的。这就是得它能够适应 于快速学习的并行实现，在一些实际问题中快速学习是备受关注的。还有就是， 因为这里没有山可以爬，所以就没有陷入举步优选的困境。将利用子空间得到的 森林和其他方式得到的随机森林进行了比较

27、，得到这样的结论：在实验中多用到 的四个数据集中随机选择的子空间来构建随机森林的方法明显要山于单的分类 效果，随机选择的子空间来构建随机森林的方法在相关的低维空间上也能够正常 的丄作。将随机选择的子空间来构建随机森林的方法与步步为营的方法、助推法 进行比较，结果表明虽然就独立树而言，步步为营法、助推法这些利用冲采样办 法得到的树有时会有更好的精度，但是对于多棵树而言，随机选择的子空间来构 建随机森林的方法的镜度是最优的。随机森林算法的优点：对于很多种资料，它可以产生高准确度的分类器。它可以处理大量的输入变量。它可以在决定类别时，评估变量的重要性。在建造森林时，它可以在内部对于一般化后的误差产生不偏差的估计。它包含一个好方法可以估计遗失的资料，并且，如果有很大一部分的资料遗失， 仍可以维持准确度。它提供一个实验方法，可以去侦测variable intemctions °对于不平衡的分类资料集来说，它可以平衡误差。它计算各例中的亲近度，对于数据挖掘、侦测偏离者（outlier）和将资料视觉化 非常有用。随机森林算法的应用随机森林作为一个有效快捷的分类器，被应用到很多的领域上和专业内。举例如 下：（1）随机森林在经济中的应用在经济迅猛发展的今天，企业的信用已经成为一个备受关注的问题