Random Forest

发表于 | 分类于 | 阅读数 次
字数统计: 2.9k 字 | 阅读时长 ≈ 10 分钟

随机森林

随机森林实际上是一种特殊的bagging方法，它将决策树用作bagging中的模型。随机森林顾名思义，是用随机的方式建立一个森林，森林里面有很多的决策树组成，随机森林的每一棵决策树之间是没有关联的。

随机森林由决策树组成，决策树实际上是将空间用超平面进行划分的一种方法，每次分割的时候，都将当前的空间一分为二，比如说下面的决策树（其属性的值都是连续的实数）：

pic1
这一颗树将样本空间划分为成的样子为：

pic2

随机森林构造流程

  1. 假如有N个样本，则有放回的随机选择N个样本(每次随机选择一个样本，然后返回继续选择)。这选择好了的N个样本用来训练一个决策树，作为决策树根节点处的样本。
  2. 当每个样本有M个属性时，在决策树的每个节点需要分裂时，随机从这M个属性中选取出m个属性，满足条件m << M。然后从这m个属性中采用某种策略（比如说信息增益）来选择1个属性作为该节点的分裂属性。
  3. 决策树形成过程中每个节点都要按照步骤2来分裂（很容易理解，如果下一次该节点选出来的那一个属性是刚刚其父节点分裂时用过的属性，则该节点已经达到了叶子节点，无须继续分裂了）。一直到不能够再分裂为止。注意整个决策树形成过程中没有进行剪枝。
  4. 按照步骤1~3建立大量的决策树，这样就构成了随机森林了。

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

决策树有很多的优点：

  1. 在数据集上表现良好，两个随机性的引入，使得随机森林不容易陷入过拟合
  2. 在当前的很多数据集上，相对其他算法有着很大的优势，两个随机性的引入，使得随机森林具有很好的抗噪声能力
  3. 它能够处理很高维度（feature很多）的数据，并且不用做特征选择，对数据集的适应能力强：既能处理离散型数据，也能处理连续型数据，数据集无需规范化
  4. 可生成一个Proximities=（pij）矩阵，用于度量样本之间的相似性： pij=aij/N, aij表示样本i和j出现在随机森林中同一个叶子结点的次数，N随机森林中树的颗数
  5. 在创建随机森林的时候，对generlization error使用的是无偏估计f. 训练速度快，可以得到变量重要性排序（两种：基于OOB误分率的增加量和基于分裂时的GINI下降量
  6. 在训练过程中，能够检测到feature间的互相影响h. 容易做成并行化方法

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

许多研究表明， 组合分类器比单一分类器的分类效果好，随机森林（random forest）是一种利用多个分类树对数据进行判别与分类的方法，它在对数据进行分类的同时，还可以给出各个变量（基因）的重要性评分，评估各个变量在分类中所起的作用。随机森林算法得到的随机森林中的每一棵都是很弱的，但是大家组合起来就很厉害了。我觉得可以这样比喻随机森林算法：每一棵决策树就是一个精通于某一个窄领域 的专家（因为我们从M个feature中选择m让每一棵决策树进行学习），这样在随机森林中就有了很多个精通不同领域的专家，对一个新的问题（新的输入数 据），可以用不同的角度去看待它，最终由各个专家，投票得到结果。而这正是群体智慧（swarm intelligence），经济学上说的看不见的手，也是这样一个分布式的分类系统，由每一自己子领域里的专家，利用自己独有的默会知识，去对一项产品进行分类，决定是否需要生产。随机森林的效果取决于多个分类树要相互独立，要想经济持续发展，不出现overfiting（就是由政府主导的经济增长，但在遇到新情况后产生泡沫），我们就需要要企业独立发展，独立选取自己的feature 。

参考文献

1. https://www.zhihu.com/search?type=content&q=%E9%9A%8F%E6%9C%BA%E6%A3%AE%E6%9E%97

Random Forest的两个随机性

pic3

  1. 样本的随机性(适用bootstrap)
  2. 特征集合的随机性

    随机森林如何进行特征选择的呢？(发生在模型的建模过程中)

    要进行特征选择，得现有一个对特征好坏的度量，我们先来看一下，随机森林是如何度量一个特征的好坏的，再来看它如何进行的特征选择
    这里指用随机森林做特征选择这个任务,而不是在随机森林中用特征选择.

    特征重要性

    对每一颗决策树，选择相应的袋外数据（out of bag，OOB）​计算袋外数据误差，记为$err_{OOB1}$.(简单的说袋外数据就是bootstrap的时候没有抽取过的数据,会作为验证集)

所谓袋外数据是指，每次建立决策树时，通过重复抽样得到一个数据用于训练​决策树，这时还有大约1/3的数据没有被利用，没有参与决策树的建立。这部分数据可以用于对决策树的性能进行评估，计算模型的预测错误率，称为袋外数据误差。

随机对袋外数据OOB所有样本的特征X加入噪声干扰（可以随机改变样本在特征X处的值），再次计算袋外数据误差，记为$err_{OOB2}$。

假设森林中有N棵树，则$特征X的重要性=\sum(err_{OOB2}-err_{OOB1})/N。$这个数值之所以能够说明特征的重要性是因为，如果加入随机噪声后，袋外数据准确率大幅度下降（即$err_{OOB2}$上升），说明这个特征对于样本的预测结果有很大影响，进而说明重要程度比较高。

特征选择()

在特征重要性的基础上，特征选择的步骤如下：

  1. 计算每个特征的重要性，并按降序排序

  2. 确定要剔除的比例，依据特征重要性剔除相应比例的特征，得到一个新的特征集

  3. 用新的特征集重复上述过程，直到剩下m个特征（m为提前设定的值）

  4. 根据上述过程中得到的各个特征集和特征集对应的袋外误差率，选择袋外误差率最低的特征集

oob误分率是随机森林泛化误差的一个无偏估计，它的结果近似于需要大量计算的k折交叉验证。

特征选择基于特征重要性的评估,不仅有OOB的方法还有Gini指数的方法,都可以用作变量重要性测量(variable importance measures).
(参考:https://blog.csdn.net/zjuPeco/article/details/77371645)

借此总结一下各个树模型的特征重要性评估方法

Random Forests

https://blog.csdn.net/tinkle181129/article/details/80231871

  1. OOB
  2. Gini系数评价指标 （和GBDT的方法相同）

GBDT

  1. 利用Gini计算特征的重要性

XGBoost

在XGBoost中提供了三种特征重要性的计算方法：
‘weight’ - the number of times a feature is used to split the data across all trees.
‘gain’ - the average gain of the feature when it is used in trees
‘cover’ - the average coverage of the feature when it is used in trees

  1. weight就是在所有树中特征用来分割的节点个数总和；
  2. gain就是特征用于分割的平均增益
  3. cover 的解释有点晦涩，在[R-package/man/xgb.plot.tree.Rd]有比较详尽的解释：(https://github.com/dmlc/xgboost/blob/f5659e17d5200bd7471a2e735177a81cb8d3012b/R-package/man/xgb.plot.tree.Rd)：the sum of second order gradient of training data classified to the leaf, if it is square loss, this simply corresponds to the number of instances in that branch. Deeper in the tree a node is, lower this metric will be。实际上coverage可以理解为被分到该节点的样本的二阶导数之和，而特征度量的标准就是平均的coverage值。

影响分类效果的参数

随机森林的分类效果（即错误率）与以下两个因素有关：
1）森林中任意两棵树的相关性：相关性越大，错误率越大
2）森林中每棵树的分类能力：每棵树的分类能力越强，整个森林的错误率越低

减小特征选择个数m，树的相关性和分类能力也会相应的降低；增大m，两者也会随之增大。所以关键问题是如何选择最优的m（或者是范围），这也是随机森林唯一的一个参数。

Random Forest遇到数据不均衡

假设正负样本比为9:1,则生成9棵树,正负样本1:1的采样.(按比例采样)

其他参考文献：

  1. https://www.jiqizhixin.com/articles/2017-07-31-3
  2. http://lindongding.com/2018/04/24/%E4%BB%8E%E7%A0%8D%E5%88%80%E5%88%B0%E7%81%AB%E7%AE%AD%E7%82%AE%EF%BC%9AXGBoost%E5%B8%A6%E4%BD%A0%E8%A3%85%E9%80%BC%E5%B8%A6%E4%BD%A0%E9%A3%9E/
-------------本文结束感谢您的阅读-------------