决策树、决策森林和GBDT

最近看了一些关于决策树和随机森林的东西，在这里简单整理一下。

决策树

决策数其实就是一个树状模型嘛（用来预测从而进行决策的分析方法），和其它树模型一样，分有根节点，叶节点和子节点。

它的思想就是来寻找最纯净的划分方法。方法呢，就是对特征进行划分和判断。

我对此的理解就是，它每一项特征都得通过，不允许出现“偏科”的情况。比如说，你要判断一个学生，他是不是优秀学生。
如果是线性模型的，比如说考试成绩40%+思想品德30%+竞赛奖项*30%，这样算出的成绩，比如过90分，则说明是个优秀学生。
而决策树呢，它分成若干节点，依次判断。比如，先判断考试成绩，没过90分，淘汰，过了，进行下一轮判断，直到全部判断通过，则证明他是一个优秀学生。
（有点像闯关，没过这关，死了，过了这关，进入下一关，直到通关。）

它运用建树和剪枝来达到寻找最纯净的划分的目的（建立模型）。

建树：

1.按次序选择属性。就是如何选择树结点的先后问题（按重要程度从大到小）。在ID3算法*中，运用信息增益；C4.5算法用信息增益率；cart算法用基尼系数来衡量这些变量的重要性。

·ID3算法，基于奥卡姆剃刀原理（“如无必要，勿增实体”，即剔除所有累赘，越简单越好。）它的基本思路就是认为，越是小型的决策树越好（也有例外）。
在信息论中，期望信息越小，那么信息增益就越大，从而纯度就越高。ID3算法的核心思想就是以信息增益*来度量属性的选择，选择分裂后信息增益最大的属性进行分裂。该算法采用自顶向下的贪婪搜索遍历可能的决策空间。
信息增益是针对一个一个特征而言的，就是看一个特征，系统有它和没有它时的信息量各是多少，两者的差值就是这个特征给系统带来的信息量，即信息增益。
信息熵 H(x); X为事件，P为事件的概率
则H（x）=-[P1log2(p1)+p2log2(p2)+……pn*log2(pn)]；熵越大，则说明携带的信息量越大。

C4.5算法，是基于ID3算法后，改进的一种重要算法。相比于ID3：
1.它运用信息增益率。
2.在树构造过程中进行剪枝，不容易导致overfitting（过拟合）*。
3.对非离散数据也可以处理。
4.能够对不完整数据进行处理。

cart算法，cart算法是一种二分递归分割技术，把当前样本划分为两个子样本，使得生成的每个非叶子结点都有两个分支，因此cart算法生成的决策树是结构简介的二叉树。由于cart算法构成的一个二叉树，它在每一步的决策都只能是“yes”和“no”，即使一个对象有多个取值，也把数据分为两个部分。在cart算法中，主要分为两个步骤：
1）将样本递归划分进行建树过程。
2）用验证数据进行剪枝。
（Gini(D)反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率，因此Gini(D)越小，则数据集D的纯度越高。）

三种方法对比：
ID3的缺点，倾向于选择水平数量较多的变量，可能导致训练得到一个庞大且深度浅的树；另外输入变量必须是分类变量（连续变量必须离散化）；最后无法处理空值。
C4.5选择了信息增益率替代信息增益。
CART以基尼系数替代熵；最小化不纯度而不是最大化信息增益。

决策树会把所有特征试一遍，选择产生纯度增益最大的点，作为父节点。

（在决策树构造过程中可能会出现这种情况：所有属性都作为分裂属性用光了，但有的子集还不是纯净集，即集合内的元素不属于同一类别。在这种情况下，由于没有更多信息可以使用了，一般对这些子集进行“多数表决”，即使用此子集中出现次数最多的类别作为此节点类别，然后将此节点作为叶子节点。）

剪树：

如何停止分裂
   下面这六种情况都会停止分裂。树的剪枝分为预剪枝和后剪枝，预剪枝，及早的停止树增长控制树的规模，方法可以参考如下6点停止分类的条件。后剪枝在已生成过拟合决策树上进行剪枝，删除没有意义的组，可以得到简化版的剪枝决策树，包括REP（设定一定的误分类率，减掉对误分类率上升不超过阈值的多余树）、PEP，还有一种CCP，即给分裂准则—基尼系数加上惩罚项，此时树的层数越深，基尼系数的惩罚项会越大。

http://images2015.cnblogs.com...

http://images2015.cnblogs.com...

决策树的优缺点：

优点
决策树易于理解和实现，人们在在学习过程中不需要使用者了解很多的背景知识，这同时是它的能够直接体现数据的特点，只要通过解释后都有能力去理解决策树所表达的意义。
对于决策树，数据的准备往往是简单或者是不必要的，而且能够同时处理数据型和常规型属性，在相对短的时间内能够对大型数据源做出可行且效果良好的结果。
易于通过静态测试来对模型进行评测，可以测定模型可信度；如果给定一个观察的模型，那么根据所产生的决策树很容易推出相应的逻辑表达式。
缺点
1)对连续性的字段比较难预测。
2)对有时间顺序的数据，需要很多预处理的工作。
3)当类别太多时，错误可能就会增加的比较快。
4)一般的算法分类的时候，只是根据一个字段来分类。

随机森林：

随机森林指的是利用多棵树对样本进行训练并预测的一种分类器。我对此的理解就是产生多棵决策树。

同一批数据，用同样的算法只能产生一棵树，这时Bagging*策略可以帮助我们产生不同的数据集。Bagging策略来源于bootstrap aggregation：从样本集（假设样本集N个数据点）中重采样选出Nb个样本（有放回的采样，样本数据点个数仍然不变为N），在所有样本上，对这n个样本建立分类器（ID3C4.5CARTSVMLOGISTIC），重复以上两步m次，获得m个分类器，最后根据这m个分类器的投票结果，决定数据属于哪一类。
随机森林在bagging的基础上更进一步：
1.  样本的随机：从样本集中用Bootstrap*随机选取n个样本

1.  特征的随机：从所有属性中随机选取K个属性，选择最佳分割属性作为节点建立CART决策树（泛化的理解，这里面也可以是其他类型的分类器，比如SVM、Logistics）
   3.  重复以上两步m次，即建立了m棵CART决策树

4.  这m个CART形成随机森林，通过投票表决结果，决定数据属于哪一类（投票机制有一票否决制、少数服从多数、加权多数）

·bagging：集成学习有两种流派，一个是boosting流派，它的特点是各个弱学习器之间有依赖关系。另种就是bagging流派，它的特点就是各个弱学习器之间没有依赖关系，可以并行拟合。

http://images2015.cnblogs.com...

Bagging的特点在于随机采样（boostrap)。从样本集中随机采取固定数的样本，每采集一次，都要把样本放回。

算法流程：　输入为样本集D={(x,y1),(x2,y2),...(xm,ym)}，弱学习器算法, 弱分类器迭代次数T。
　　　　 输出为最终的强分类器f(x)
　　　　 1）对于t=1,2...,T:
　　　　　　 a)对训练集进行第t次随机采样，共采集m次，得到包含m个样本的采样集Dm
　　　　　　 b)用采样集Dm训练第m个弱学习器Gm(x)
　　　　2) 如果是分类算法预测，则T个弱学习器投出最多票数的类别或者类别之一为最终类别。如果是回归算法，T个弱学习器得到的回归结果进行算术平均得到的值为最终的模型输出。
　　　　

随机森林（Random Forest)的优缺点：

　　主要优点有：
　　　　1） 训练可以高度并行化，对于大数据时代的大样本训练速度有优势。
　　　　2） 由于可以随机选择决策树节点划分特征，这样在样本特征维度很高的时候，仍然能高效的训练模型。
　　　　3） 在训练后，可以给出各个特征对于输出的重要性
　　　　4） 由于采用了随机采样，训练出的模型的方差小，泛化能力强。
　　　　5） 相对于Boosting系列的Adaboost和GBDT， RF实现比较简单。
　　　　6） 对部分特征缺失不敏感。
　　　　主要缺点有：
　　　　1）在某些噪音比较大的样本集上，RF模型容易陷入过拟合。
　　　　2) 取值划分比较多的特征容易对RF的决策产生更大的影响，从而影响拟合的模型的效果。
　　　　

Gradient Boosting Decision Tree(GBDT:梯度提升决策树）

GBDT（又叫MART：Multiple Additive Regression Tree）是一种迭代的决策树算法（不是分类树，分类树则是对每一个对象取一个阈值，高于阈值的为一类，低于的为一类。），也是由多棵决策树组成，所有树的结论累加起来做最终答案。是一种被认为泛化能力较强的算法。

回归树用于连续型（如温度、年龄、工资）；分类树用于离散型（如性别、气候）。

·泛化能力（generalization ability）是指机器学习算法对新鲜样本的适应能力。学习的目的是学到隐含在数据对背后的规律，对具有同一规律的学习集以外的数据，经过训练的网络也能给出合适的输出，该能力称为泛化能力。

那么它和决策森林的区别是什么呢？
1）组成随机森林的树可以是分类树，也可以是回归树；而GBDT只由回归树组成。
2）组成随机森林的树可以并行生成；而GBDT只能是串行生成。
3）对于最终的输出结果而言，随机森林采用多数投票；而GBDT则是将所有结果加权累加起来。
4）随机森林对异常值不敏感，GBDT对异常值非常敏感。
5）随机森林对训练集一视同仁，GBDT是基于权值的弱分类器的集成。
6）随机森林是通过减少模型方差提高性能，GBDT是通过减少模型偏差提高性能。

Boost是"提升"的意思，一般Boosting算法都是一个迭代的过程，每一次新的训练都是为了改进上一次的结果。
GBDT的核心就在于：每一棵树学的是之前所有树结论和的残差，这个残差就是一个加预测值后能得真实值的累加量。比如A的真实年龄是18岁，但第一棵树的预测年龄是12岁，差了6岁，即残差为6岁。那么在第二棵树里我们把A的年龄设为6岁去学习，如果第二棵树真的能把A分到6岁的叶子节点，那累加两棵树的结论就是A的真实年龄；如果第二棵树的结论是5岁，则A仍然存在1岁的残差，第三棵树里A的年龄就变成1岁，继续学习

举个例子：
年龄预测，简单起见训练集只有4个人，A,B,C,D，他们的年龄分别是14,16,24,26。其中A、B分别是高一和高三学生；C,D分别是应届毕业生和工作两年的员工。如果是用一棵传统的回归决策树来训练，会得到如下图1所示结果：
http://img.blog.csdn.net/2013...

 
        现在我们使用GBDT来做这件事，由于数据太少，我们限定叶子节点做多有两个，即每棵树都只有一个分枝，并且限定只学两棵树。我们会得到如下图2所示结果：
        http://img.blog.csdn.net/2013...

 
        在第一棵树分枝和图1一样，由于A,B年龄较为相近，C,D年龄较为相近，他们被分为两拨，每拨用平均年龄作为预测值。此时计算残差（残差的意思就是： A的预测值 + A的残差 = A的实际值），所以A的残差就是16-15=1（注意，A的预测值是指前面所有树累加的和，这里前面只有一棵树所以直接是15，如果还有树则需要都累加起来作为A的预测值）。进而得到A,B,C,D的残差分别为-1,1，-1,1。然后我们拿残差替代A,B,C,D的原值，到第二棵树去学习，如果我们的预测值和它们的残差相等，则只需把第二棵树的结论累加到第一棵树上就能得到真实年龄了。这里的数据显然是我可以做的，第二棵树只有两个值1和-1，直接分成两个节点。此时所有人的残差都是0，即每个人都得到了真实的预测值。
 
换句话说，现在A,B,C,D的预测值都和真实年龄一致了。Perfect!：
A: 14岁高一学生，购物较少，经常问学长问题；预测年龄A = 15 – 1 = 14
B: 16岁高三学生；购物较少，经常被学弟问问题；预测年龄B = 15 + 1 = 16
C: 24岁应届毕业生；购物较多，经常问师兄问题；预测年龄C = 25 – 1 = 24
D: 26岁工作两年员工；购物较多，经常被师弟问问题；预测年龄D = 25 + 1 = 26 

【出自作者：是蓝先生 链接：http://www.jianshu.com/p/d210...】

GBDT范围
GBDT几乎可用于所有回归问题（线性/非线性），GBDT的适用面非常广。亦可用于二分类问题（设定阈值，大于阈值为正例，反之为负例）。

算法步骤解释：
1、初始化，估计使损失函数极小化的常数值，它是只有一个根节点的树，即ganma是一个常数值。
2、
（a）计算损失函数的负梯度在当前模型的值，将它作为残差的估计
（b）估计回归树叶节点区域，以拟合残差的近似值
（c）利用线性搜索估计叶节点区域的值，使损失函数极小化
（d）更新回归树
3、得到输出的最终模型 f(x)