随机森林算法

1.随机森林使用背景

1.1随机森林定义

随机森林是一种比较新的机器学习模型。经典的机器学习模型是神经网络，有半个多世纪的历史了。神经网络预测精确，但是计算量很大。上世纪八十年代Breiman等人发明分类树的算法（Breiman et al. 1984），通过反复二分数据进行分类或回归，计算量大大降低。2001年Breiman把分类树组合成随机森林（Breiman 2001a），即在变量（列）的使用和数据（行）的使用上进行随机化，生成很多分类树，再汇总分类树的结果。随机森林在运算量没有显著提高的前提下提高了预测精度。随机森林对多元公线性不敏感，结果对缺失数据和非平衡的数据比较稳健，可以很好地预测多达几千个解释变量的作用（Breiman 2001b），被誉为当前最好的算法之一（Iverson et al. 2008）。

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

1.2随机森林优点

随机森林是一个最近比较火的算法，它有很多的优点：

a. 在数据集上表现良好，两个随机性的引入，使得随机森林不容易陷入过拟合

b. 在当前的很多数据集上，相对其他算法有着很大的优势，两个随机性的引入，使得随机森林具有很好的抗噪声能力

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

d. 可生成一个Proximities=（pij）矩阵，用于度量样本之间的相似性： pij=aij/N, aij表示样本i和j出现在随机森林中同一个叶子结点的次数，N随机森林中树的颗数

e. 在创建随机森林的时候，对generlization error使用的是无偏估计

f. 训练速度快，可以得到变量重要性排序（两种：基于OOB误分率的增加量和基于分裂时的GINI下降量

g. 在训练过程中，能够检测到feature间的互相影响

h. 容易做成并行化方法

i. 实现比较简单

(3)能够估计哪个特征在分类中更重要；

(6)可以并行处理。

缺点

（1）对小量数据集和低维数据集的分类不一定可以得到很好的效果。

（2）执行速度虽然比Boosting等快，但是比单个的决策树慢很多。

（3）可能会出现一些差异度非常小的树，淹没了一些正确的决策。

二、随机森林生成步骤

1、从原始训练数据集中，应用bootstrap方法有放回地随机抽取k个新的自助样本集，并由此构建k棵分类回归树，每次未被抽到的样本组成了Ｋ个袋外数据（out-of-bag,BBB）。

2、设有n个特征，则在每一棵树的每个节点处随机抽取mtry个特征，通过计算每个特征蕴含的信息量，特征中选择一个最具有分类能力的特征进行节点分裂。

3、每棵树最大限度地生长， 不做任何剪裁

4、将生成的多棵树组成随机森林， 用随机森林对新的数据进行分类， 分类结果按树分类器投票多少而定。

三、变量重要性度量

随机森林程序通常提供４种变量重要性度量，其中importance()函数就属于其中。其中平均精度下降（MeanDecreaseAccuracy”）重要性评分；Gini指数。

1、变量重要性测度

定义为袋外数据自变量值发生轻微扰动后的分类正确率与扰动前分类正确率的平均减少量。

（1）：对于每棵决策树，利用袋外数据进行预测，将袋外数据的预测误差将记录下来。其每棵树的误差是：vote1，vote2····，voteb；

（2）：随机变换每个预测变量，从而形成新的袋外数据，再利用袋外数据进行验证，其每个变量的误差是：vote11，vote12，···，vote1b。

（3）：对于某预测变量来说，计算其重要性是变换后的预测误差与原来相比的差的均值。

importance

a matrix with nclass + 2 (for classification) or two (for regression) columns. For classification, the first nclass columns are the class-specific measures computed as mean descrease in accuracy. The nclass + 1st column is the mean descrease in accuracy over all classes. The last column is the mean decrease in Gini index. For Regression, the first column is the mean decrease in accuracy and the second the mean decrease in MSE. If importance=FALSE, the last measure is still returned as a vector.

IncMSE  IncNodePurity，分别是什么含义啊，哪个大神能解答下吗？我看文献上，不应该是MeanDecreaseAccuracy  MeanDecreaseGini这两个指标么？

特征重要性评价标准：

IncMSE 等价于 MeanDecreaseAccuracy。均方误差。就是对每一个变量 比如 X1 随机赋值, 如果 X1重要的话, 预测的误差会增大,所以 误差的增加就等同于 准确性的减少，

IncNodePurity等价于MeanDecreaseGini，结点的纯度

r语言中代码：

rf <- randomForest(Species ~ ., data=a, ntree=100, proximity=TRUE,importance=TRUE)

2、Gini指数法

gini指数表示节点的纯度，gini指数越大纯度越低。gini值平均降低量表示所有树的变量分割节点平均减小的不纯度。对于变量重要度衡量，步骤如同前面介绍，将变量数据打乱，gini指数变化的均值作为变量的重要程度度量。

gini(T)=1−∑j=1np2j

1.3随机森林应用范围

随机森林主要应用于回归和分类。本文主要探讨基于随机森林的分类问题。随机森林和使用决策树作为基本分类器的（bagging）有些类似。以决策树为基本模型的bagging在每次bootstrap放回抽样之后，产生一棵决策树，抽多少样本就生成多少棵树，在生成这些树的时候没有进行更多的干预。而随机森林也是进行bootstrap抽样，但它与bagging的区别是：在生成每棵树的时候，每个节点变量都仅仅在随机选出的少数变量中产生。因此，不但样本是随机的，连每个节点变量（Features）的产生都是随机的。

许多研究表明， 组合分类器比单一分类器的分类效果好，随机森林（random forest）是一种利用多个分类树对数据进行判别与分类的方法，它在对数据进行分类的同时，还可以给出各个变量（基因）的重要性评分，评估各个变量在分类中所起的作用。

2.随机森林方法理论介绍

2.1随机森林基本原理

随机森林由LeoBreiman（2001）提出，它通过自助法（bootstrap）重采样技术，从原始训练样本集N中有放回地重复随机抽取k个样本生成新的训练样本集合，然后根据自助样本集生成k个分类树组成随机森林，新数据的分类结果按分类树投票多少形成的分数而定。其实质是对决策树算法的一种改进，将多个决策树合并在一起，每棵树的建立依赖于一个独立抽取的样品，森林中的每棵树具有相同的分布，分类误差取决于每一棵树的分类能力和它们之间的相关性。特征选择采用随机的方法去分裂每一个节点，然后比较不同情况下产生的误差。能够检测到的内在估计误差、分类能力和相关性决定选择特征的数目。单棵树的分

类能力可能很小，但在随机产生大量的决策树后，一个测试样品可以通过每一棵树的分类结果经统计后选择最可能的分类。

2.2随机森林算法

2.2.1决策树

决策树（decision tree）是一个树结构（可以是二叉树或非二叉树）。其每个非叶节点表示一个特征属性上的测试，每个分支代表这个特征属性在某个值域上的输出，而每个叶节点存放一个类别。使用决策树进行决策的过程就是从根节点开始，测试待分类项中相应的特征属性，并按照其值选择输出分支，直到到达叶子节点，将叶子节点存放的类别作为决策结果。

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

在建立每一棵决策树的过程中，有两点需要注意采样与完全分裂。首先是两个随机采样的过程，random forest对输入的数据要进行行、列的采样。对于行采样，采用有放回的方式，也就是在采样得到的样本集合中，可能有重复的样本。假设输入样本为N个，那么采样的样本也为N个。这样使得在训练的时候，每一棵树的输入样本都不是全部的样本，使得相对不容易出现over-fitting。然后进行列采样，从M个feature中，选择m个（m << M）。之后就是对采样之后的数据使用完全分裂的方式建立出决策树，这样决策树的某一个叶子节点要么是无法继续分裂的，要么里面的所有样本的都是指向的同一个分类。一般很多的决策树算法都一个重要的步骤——剪枝，但是这里不这样干，由于之前的两个随机采样的过程保证了随机性，所以就算不剪枝，也不会出现over-fitting。

决策树中分裂属性的两个选择度量：

1）信息增益

信息熵

a) H(S)=∑Pi log2(pi)(i=1..m)

其中，数据集为S，m为S的分类数目，Pi≈|Si/|S|，Ci为某分类标号，Pi为任意样本属于Ci的概率，si为分类Ci上的样本数

b) H(S)越小，s1,s2,……,sm就越有序（越纯），分类效果就越好。熵越大说明数据越不纯

c) 由属性A划分为子集的熵，也就是条件熵：

A为属性，具有V个不同的取值， S被A 划分为V 个子集s1,s2,……,sv，sij是子集sj中类Ci的样本数。H(S|A)= sum sij/sj H(A_i)

d) 信息增益：Gain(A)= H(S) - H(S|A)

e) 分裂属性选择规则：选择具有最大信息增益的属性为分裂属性

2)信息增益率：G(A)/H(S|A)

信息增益趋向于选择某类数据量比较多的属性开始划分，而选择信息增益率可以避免这种情况

选择具有最大信息增益率的属性作为分裂属性

2）基尼指数

a) 集合T包含N个类别的记录，那么其Gini指标就是pj类别j出现的频率

b) 如果集合T分成m部分 N1 , N2 ,…, Nm 。每个部分出现的概率是：p1 p2 p3 p4 

那么这个分割的Gini就是:G = sum pi*(1-pi) = 1- sum pi*pi

c)分裂属性选择规则：选择具有最小Ginisplit的属性为分裂属性（对于每个属性都要遍历所有可能的分割方法）。

2.2.3随机森林模型的注意点

设有N个样本，每个样本有M个features，决策树们其实都是随机地接受n个样本（对行随机取样）的m个feature（对列进行随机取样），每颗决策树的m个feature相同。每颗决策树其实都是对特定的数据进行学习归纳出分类方法，而随机取样可以保证有重复样本被不同决策树分类，这样就可以对不同决策树的分类能力做个评价。

2.2.4随机森林实现过程

随机森林中的每一棵分类树为二叉树，其生成遵循自顶向下的递归分裂原则，即从根节点开始依次对训练集进行划分；在二叉树中，根节点包含全部训练数据， 按照节点纯度最小原则，分裂为左节点和右节点，它们分别包含训练数据的一个子集，按照同样的规则节点继续分裂，直到满足分支停止规则而停止生长。若节点n上的分类数据全部来自于同一类别，则此节点的

纯度I(n)=0，

纯度度量方法是Gini准则，即假设P(Xj)是节点n上属于Xj类样本个数占训练。

具体实现过程如下：

（1）原始训练集为N，应用bootstrap法有放回地随机抽取k个新的自助样本集，并由此构建k棵分类树，每次未被抽到的样本组成了k个袋外数据；

（2）设有mall个变量，则在每一棵树的每个节点处随机抽取mtry个变量(mtryn mall)，然后在mtry中选择一个最具有分类能力的变量，变量分类的阈值通过检查每一个分类点确定；

（3）每棵树最大限度地生长, 不做任何修剪；

（4）将生成的多棵分类树组成随机森林，用随机森林分类器对新的数据进行判别与分类，分类结果按树分类器的投票多少而定。

文章来源：http://www.zilhua.com/629.html