RandomForest and ExtraTree

二月啦！整个一月过得漫长而五味杂陈，很多计划也都没有提上日程:(
希望二月会有好消息 一定会的!:)
今天来记叙一下随机森林和它的变形极端随机树

RandomForest（随机森林）

概念理解

随机森林（RF）就是通过集成学习的思想将多棵树集成的一种算法，它的基本单元是决策树，而它的本质属于机器学习的一大分支——集成学习方法。

注意：这边需要做一个小区分，随机森林的集成学习方法是bagging ，和bagging 不同的是bagging只使用bootstrap有放回的采样样本，随机森林是随机采样样本，也就是随机选择特征，可防止过拟合能力更强，降低方差。

那么，从字面上来看，随机森林分为两部分，“随机”和“森林”，这里的“随机”是指：样本随机 、特征随机 、参数随机 、模型随机（ID3 ,C4.5）。森林是由很多棵树组成的，随机森林的结果是依赖于多棵决策树的结果。如下图所示：

举个栗子：森林里新来了一只动物，森林举办森林大会，判断这到底是什么动物，每棵树都必须发表意见，票数最多的结果将是最终的结果。随机森林最终的模型见下图示：

随机森林的构造过程

随机森林的构造主要分为四步

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

随机森林模型评价因素

1.每棵树生长越茂盛，组成森林的分类性能越好；
2.每棵树之间的相关性越差，或树之间是独立的，森林的分类性能越好。

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

对于分类问题（将某个样本划分到某一类），也就是离散变量问题，CART使用Gini值作为评判标准。定义为Gini=1-∑(P(i)XP(i)),P(i)为当前节点上数据集中第i类样本的比例。例如：分为2类，当前节点上有100个样本，属于第一类的样本有70个，属于第二类的样本有30个，则Gini=1-0.7×07-0.3×03=0.42，可以看出，类别分布越平均，Gini值越大，类分布越不均匀，Gini值越小。
在寻找最佳的分类特征和阈值时，评判标准为：argmax（Gini-GiniLeft-GiniRight），即寻找最佳的特征f和阈值th，使得当前节点的Gini值减去左子节点的Gini和右子节点的Gini值最大。

优缺点

优点：
a）随机森林算法能解决分类与回归两种类型的问题，表现良好，由于是集成学习，方差和偏差都比较低，泛化性能优越；
b）随机森林对于高维数据集的处理能力很好，它可以处理成千上万的输入变量，并确定最重要的变量，因此被认为是一个不错的降维方法。此外，该模型能够输出特征的重要性程度，这是一个非常实用的功能。
c) 可以应对缺失数据；
d ) 高度并行化，易于分布式实现
e) 由于是树模型 ，不需要归一化即可之间使用
缺点：
a）随机森林在解决回归问题时并没有像它在分类中表现的那么好，这是因为它并不能给出一个连续型的输出。当进行回归时，随机森林不能够作出超越训练集数据范围的预测，这可能导致在对某些还有特定噪声的数据进行建模时出现过度拟合。
b）对于许多统计建模者来说，随机森林给人的感觉像是一个黑盒子——你几乎无法控制模型内部的运行，只能在不同的参数和随机种子之间进行尝试。
c) 忽略属性之间的相关性

代码实战参考:随机森林的原理分析及Python代码实现

ExtraTree(极端随机树)

ET或Extra-Trees（Extremely randomized trees，极端随机树）算法与随机森林算法十分相似，都是由许多决策树构成。ET随机是指：特征随机 、参数随机 、模型随机（ID3 ,C4.5） 、分裂随机 .
Extra tree是RF的一个变种, 仅有区别有：
1） 对于每个决策树的训练集，RF采用的是随机采样bootstrap来选择采样集作为每个决策树的训练集，而extra tree一般不采用随机采样，即每个决策树采用原始训练集。RandomForest应用的是Bagging模型，ExtraTree使用的所有的样本，只是特征是随机选取的，因为分裂是随机的，所以在某种程度上比随机森林得到的结果更加好.
2） 在选定了划分特征后，RF的决策树会基于信息增益，基尼系数，均方差之类的原则，选择一个最优的特征值划分点，这和传统的决策树相同。但是Extra tree比较的激进，会随机的选择一个特征值来划分决策树。

从第二点可以看出，由于随机选择了特征值的划分点位，而不是最优点位，这样会导致生成的决策树的规模一般会大于RF所生成的决策树。也就是说，模型的方差相对于RF进一步减少，但是bias相对于RF进一步增大。在某些时候，Extra tree的泛化能力比RF更好.

可以使用 sklearn 的ExtraTreesClassifier来创建一个Extra-Tree分类器。他的 API 跟RandomForestClassifier是相同的，相似的，ExtraTreesRegressor跟RandomForestRegressor也是相同的 API.

友情链接：随机森林的推广(Extra Trees)
一文看懂随机森林

Ending~