这世界总有虚有实，有人说我做的是虚的，可我觉得做的实的。不同企业，不同阶段，不同需求、不同层次视角和判断会有极大的差异。我第一家公司都有自己的研究院，就集中精力做研究，引领行业发展，是企业发展的引擎，难道是在做虚的事情吗。

今天我们来谈一谈机器学习算法中的各种树形算法，包括ID3、C4.5、CART以及基于集成思想的树模型Random Forest和GBDT。本文对各类树形算法的基本思想进行了简单的介绍，重点谈一谈被称为是算法中的“战斗机”，机器学习中的“屠龙刀”的GBDT算法。

1. 决策树的模型

　　决策树是一种基本的分类与回归方法，它可以被认为是一种if-then规则的集合。决策树由节点和有向边组成，内部节点代表了特征属性，外部节点（叶子节点）代表了类别。

　　下图为决策树的一个图例：

http://ww1/large/4024b3f7jw1f5q80fex6pj20en08n74b.jpg

决策树根据一步步地属性分类可以将整个特征空间进行划分，从而区别出不同的分类样本，如下图所示：

http://ww2/large/4024b3f7jw1f5q81n63zrg20dc0dcwgy.gif

根据上图其实我们不难可以想到，满足样本划分的决策树有无数种，什么样的决策树才算是一颗好的决策树呢？

性能良好的决策树的选择标准是一个与训练数据矛盾较小的决策树，同时具有很好的泛化能力。言外之意就是说，好的决策树不仅对训练样本有着很好的分类效果，对于测试集也有着较低的误差率。
2. 决策树的基本知识

一个完整的决策树学习算法包含有三大步骤，分别为：

1) 特征的选择；

2) 决策树的生成；

3) 决策树的剪枝。

在介绍决策树学习算法之前，我们先简单谈几个基本的概念：

1) 熵（entropy）

在信息论和概率统计中，熵是表示随机变量不确定性的度量。

设X是一个取有限个值的离散随机变量，其概率分布为：P(X=xi)=pi, i=1,2, ... , n则随机变量X的熵定义为：H(X)=- ∑ pi * logpi, i=1,2, ... , n　　熵只依赖X的分布，和X的取值没有关系，熵是用来度量不确定性，当熵越大，概率说X=xi的不确定性越大，反之越小，在机器学期中分类中说，熵越大即这个类别的不确定性更大，反之越小，当随机变量的取值为两个时，熵随概率的变化曲线如下图：

http://ww2/large/4024b3f7jw1f5q82vxqtnj209y08laai.jpg

当p=0或p=1时，H(p)=0,随机变量完全没有不确定性，当p=0.5时，H(p)=1,此时随机变量的不确定性最大。

条件熵（conditional entropy）：表示在一直随机变量X的条件下随机变量Y的不确定性度量。　　设随机变量(X, Y)，其联合概率分布为 P(X, Y) = pij(i=1,2, ... , n; j=1,2, ... , m)，随机变量X给定的条件下随机变量Y的条件熵H(Y|X)，定义为X给定条件下Y的条件概率分布的熵对X的数学期望：H(Y|X)=∑ pi*H(Y|X=xi)这里，pi=P(X=xi), i=1,2, ... , n.

2) 信息增益（information gain）

信息增益表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。

特征A对训练数据集D的信息增益g(D, A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即g(D, A)=H(D)-H(D|A)

信息增益大的特征具有更强的分类能力。

3) 信息增益比（information gain ratio）

信息增益比gR(D, A)定义为其信息增益g(D, A)与训练数据集D关于特征A的值的熵HA(D)之比，即gR(D, A)=g(D, A)/HA(D)其中，HA(D)=-∑|Di|/|D|*log2|Di|/|D|, n是特征A取值的个数。

4) 基尼指数（gini index）

分类问题中，假设有K个类，样本属于第k类的概率为pk，则概率分布的基尼指数定义为：Gini(p)=∑pk(1-pk)=1-∑pk2

对于二分类问题，若样本点属于第1个类的概率是p，则概率分布的基尼指数为：Gini(p)=2p(1-p)　　对于给定的样本集合D，其基尼指数为：Gini(D)=1-∑(|Ck|/|D|)2

这里，Ck是D中属于第k类的样本子集，k是类的个数。

如果样本集合D根据特征A是否取到某一可能值a被分割成D1和D2两部分，则在特征A的条件下，集合D的基尼指数定义为：Gini(D,A)=|D1|/|D|*Gini(D1) |D2|/|D|*Gini(D2)

基尼指数Gini(D)表示集合D的不确定性，基尼指数越大，样本集合的不确定性也就越大，这一点与熵相似。
3. ID3、C4.5&CART

其实不同的决策树学习算法只是它们选择特征的依据不同，决策树的生成过程都是一样的（根据当前环境对特征进行贪婪的选择）。

ID3算法的核心是在决策树各个节点上应用信息增益准则选择特征，每一次都选择使得信息增益最大的特征进行分裂，递归地构建决策树。

ID3算法以信息增益作为划分训练数据集的特征，有一个致命的缺点。选择取值比较多的特征往往会具有较大的信息增益，所以ID3偏向于选择取值较多的特征。

针对ID3算法的不足，C4.5算法根据信息增益比来选择特征，对这一问题进行了校正。

CART指的是分类回归树，它既可以用来分类，又可以被用来进行回归。CART用作回归树时用平方误差最小化作为选择特征的准则，用作分类树时采用基尼指数最小化原则，进行特征选择，递归地生成二叉树。

决策树的剪枝：我们知道，决策树在生成的过程中采用了贪婪的方法来选择特征，从而达到对训练数据进行更好地拟合（其实从极端角度来看，决策树对训练集的拟合可以达到零误差）。而决策树的剪枝是为了简化模型的复杂度，防止决策树的过拟合问题。

4. Random Forest

随机森林是一种集成学习 决策树的分类模型，它可以利用集成的思想（投票选择的策略）来提升单颗决策树的分类性能（通俗来讲就是“三个臭皮匠，顶一个诸葛亮”）。　　集集成学习和决策树于一身，随机森林算法具有众多的优点，其中最为重要的就是在随机森林算法中每棵树都尽最大程度的生长，并且没有剪枝过程。

随机森林引入了两个随机性——随机选择样本（bootstrap sample）和随机选择特征进行训练。两个随机性的引入对随机森林的分类性能至关重要。由于它们的引入，使得随机森林不容易陷入过拟合，并且具有很好得抗噪能力（比如：对缺省值不敏感）。

5. GBDT

迭代决策树GBDT（Gradient Boosting Decision Tree）也被称为是MART（Multiple Additive Regression Tree)）或者是GBRT（Gradient Boosting Regression Tree），也是一种基于集成思想的决策树模型，但是它和Random Forest有着本质上的区别。不得不提的是，GBDT是目前竞赛中最为常用的一种机器学习算法，因为它不仅可以适用于多种场景，更难能可贵的是，GBDT有着出众的准确率。这也是为什么很多人称GBDT为机器学习领域的“屠龙刀”。

这么牛叉的算法，到底是怎么做到的呢？说到这里，就不得不说一下GBDT中的“GB”（Gradient Boosting）。Gradient Boosting的原理相当的复杂，但是看不懂它也不妨碍我们对GBDT的理解和认识

“Boosting，迭代，即通过迭代多棵树来共同决策。这怎么实现呢？难道是每棵树独立训练一遍，比如A这个人，第一棵树认为是10岁，第二棵树认为是0岁，第三棵树认为是20岁，我们就取平均值10岁做最终结论？当然不是！且不说这是投票方法并不是GBDT，只要训练集不变，独立训练三次的三棵树必定完全相同，这样做完全没有意义。之前说过，GBDT是把所有树的结论累加起来做最终结论的，所以可以想到每棵树的结论并不是年龄本身，而是年龄的一个累加量。GBDT的核心就在于，每一棵树学的是之前所有树结论和的残差，这个残差就是一个加预测值后能得真实值的累加量。比如A的真实年龄是18岁，但第一棵树的预测年龄是12岁，差了6岁，即残差为6岁。那么在第二棵树里我们把A的年龄设为6岁去学习，如果第二棵树真的能把A分到6岁的叶子节点，那累加两棵树的结论就是A的真实年龄；如果第二棵树的结论是5岁，则A仍然存在1岁的残差，第三棵树里A的年龄就变成1岁，继续学。这就是Gradient Boosting在GBDT中的意义。”

其实从这里我们可以看出GBDT与Random Forest的本质区别，GBDT不仅仅是简单地运用集成思想，而且它是基于对残差的学习的。我们在这里利用一个GBDT的经典实例进行解释。　　假设我们现在有一个训练集，训练集只有4个人，A,B,C,D，他们的年龄分别是14,16,24,26。其中A、B分别是高一和高三学生；C,D分别是应届毕业生和工作两年的员工。如果是用一棵传统的回归决策树来训练，会得到如下图1所示结果：

http://ww3/large/4024b3f7jw1f5q85u6pppj20hd098ta0.jpg

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

http://ww4/large/4024b3f7jw1f5q86tublaj20hs05p0tk.jpg

图2　　在第一棵树分枝和图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，即每个人都得到了真实的预测值。　　

最后GBDT的预测结果为：　　

A: 14岁高一学生，购物较少，经常问学长问题；预测年龄A = 15 – 1 = 14；　　

B: 16岁高三学生；购物较少，经常被学弟问问题；预测年龄B = 15   1 = 16；　　

C: 24岁应届毕业生；购物较多，经常问师兄问题；预测年龄C = 25 – 1 = 24；　　

D: 26岁工作两年员工；购物较多，经常被师弟问问题；预测年龄D = 25   1 = 26。　　

那么哪里体现了Gradient呢？其实回到第一棵树结束时想一想，无论此时的cost function是什么，是均方差还是均差，只要它以误差作为衡量标准，残差向量(-1, 1, -1, 1)都是它的全局最优方向，这就是Gradient。　　

注：图1和图2 最终效果相同，为何还需要GBDT呢？答案是过拟合。过拟合是指为了让训练集精度更高，学到了很多“仅在训练集上成立的规律”，导致换一个数据集当前规律就不适用了。只要允许一棵树的叶子节点足够多，训练集总是能训练到100%准确率的。在训练精度和实际精度（或测试精度）之间，后者才是我们想要真正得到的。我们发现图1为了达到100%精度使用了3个feature（上网时长、时段、网购金额），其中分枝“上网时长>1.1h” 很显然已经过拟合了，这个数据集上A,B也许恰好A每天上网1.09h, B上网1.05小时，但用上网时间是不是>1.1小时来判断所有人的年龄很显然是有悖常识的；相对来说图2的boosting虽然用了两棵树 ，但其实只用了2个feature就搞定了，后一个feature是问答比例，显然图2的依据更靠谱。　　

可见，GBDT同随机森林一样，不容易陷入过拟合，而且能够得到很高的精度。