决策树 决策树与迭代决策树（GBDT）

机器学习算法中有各种各样的树算法，包括ID3、C4.5、CART，以及基于集成思想的随机森林和GBDT树模型。简要介绍了各种树算法的基本思想，重点介绍了算法上被称为“斗士”的GBDT算法和机器学习上被称为“屠龙刀”的屠龙刀。

1.决策树模型

决策树是一种基本的分类和回归方法，可以看作是一组if-then规则。决策树由节点和有向边组成。内部节点代表要素属性，外部节点代表类别。

下图是决策树的图例:

决策树根据分步属性分类，可以对整个特征空进行划分，区分不同的分类样本，如下图所示:

根据上图，不难想到满足样本划分的决策树数不胜数。什么样的决策树是好的决策树？

性能好的决策树的选择准则是与训练数据矛盾小的决策树，具有良好的泛化能力。这意味着一个好的决策树不仅对训练样本有很好的分类效果，而且对测试集的错误率也很低。

2.决策树基础知识

一个完整的决策树学习算法包括三个主要步骤，即:

1)特征选择；

2)决策树的生成；

3)决策树的剪枝。

在介绍决策树学习算法之前，先简单说几个基本概念:

1)熵

在信息论和概率统计中，熵是表示随机变量不确定性的一种度量。设x是一个取值有限的离散随机变量，其概率分布为:

P=pi，i=1，2，...，n

随机变量x的熵定义为:

H=- ∑ pi * logpi，i=1，2，...，n

熵只取决于x的分布，与x的值无关，熵用来衡量不确定性。熵越大，X=xi的不确定性越大，反之亦然。在机学期的分类中，熵越大，这个类别的不确定性越大，反之则越小。当随机变量有两个值时，熵随概率变化的曲线如下:

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

条件熵:表示随机变量x不变条件下随机变量y的不确定性测度。

设随机变量有一个P = pij，随机变量X给定条件下随机变量Y的条件熵H定义为X给定条件下X上Y的条件概率分布熵的数学期望:

H=∑ pi*H

这里，π= p，i = 1，2，...，n。

2)信息增益

信息增益表示通过了解特征x的信息，降低y类信息不确定性的程度。

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

g=H-H

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

3)信息增益比

信息增益比gR定义为其信息增益g与训练数据集D的值相对于特征A的熵HA之比，即

gR=g/HA

其中ha=-∞| di |/| d | * log2 | di |/| d |，n为特征a的值个数..

4)基尼指数

在分类问题中，如果有k个类，样本属于k类的概率为pk，概率分布的基尼指数定义为:

基尼=∑pk=1-∑pk2

对于二元分类问题，如果样本点属于第一类的概率为p，则概率分布的基尼指数为:

基尼系数=2p

对于给定的样本集d，其基尼指数为:

基尼=1-∑2

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

如果根据特征A是否得到某个可能值A将样本集D分为D1和D2，则集D的基尼系数定义为:

基尼系数= | D1 |/| D | *基尼系数+| D2 |/| D | *基尼系数

基尼指数基尼表示集合D的不确定性，基尼指数越大，样本集的不确定性越大，类似熵。

3.ID3、C4.5 & amp手推车

其实不同的决策树学习算法只是选择特征的依据不同，决策树的生成过程是一样的。

ID3算法的核心是应用信息增益准则选择决策树各节点的特征，并对每次信息增益最大的特征进行拆分，从而递归构建决策树。

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

针对ID3算法的不足，C4.5算法根据信息增益比选取特征，并对这个问题进行了修正。

CART指分类回归树，分类回归都可以。Cart作为回归树选择特征，CART作为分类树选择特征，递归生成二叉树。

决策树剪枝:我们知道在生成决策树的过程中，采用贪婪的方法选择特征，从而更好的拟合训练数据。决策树的剪枝是为了简化模型的复杂性，防止决策树的过拟合。决策树的具体修剪策略可以在李航的统计学习方法中找到。

4.随机森林

随机森林是一种集成学习+决策树的分类模型，利用集成的思想可以提高单个决策树的分类性能。

随机森林算法结合集成学习和决策树，有很多优点，其中最重要的是每棵树都最大限度地生长，没有剪枝过程。

随机森林引入了两种随机性——自举样本和随机选择特征进行训练。两种随机性的引入对随机森林的分类性能至关重要。由于它们的引入，随机森林不容易陷入过拟合，并且具有很好的抗噪能力。

5.梯度提升决策树

迭代决策树，又称Mart或GBRT，也是基于集成思想的决策树模型，但与Random Forest有本质区别。必须提到的是，GBDT是目前比赛中最常用的机器学习算法，因为它不仅可以应用于各种场景，而且具有出色的准确性。这就是为什么许多人在机器学习领域称GBDT为“屠龙刀”。

这个牛逼的算法是怎么做到的？说到这里，我不得不说GBDT的“梯度推进”。梯度推进的原理相当复杂，但是我们不能理解它而不妨碍我们对GBDT的理解。关于梯度助推的详细解释，请参考维基百科。

这里引用另一位网友的解释来解释GBDT对梯度助推的理解:

以下段落引自GBDT迭代决策树简介。

“助推，迭代，也就是通过在多棵树上迭代一起做决策。如何做到这一点？是不是每棵树都是独立训练的，比如A，第一棵树认为10岁，第二棵树认为0岁，第三棵树认为20岁，那么我们就以平均年龄10岁作为最终结论？当然不是！更别说这是投票方式，不是GBDT。只要训练集不变，独立训练三次的三棵树一定是一模一样的，完全没有意义。

如前所述，GBDT总结了所有树的结论以做出最终结论，因此我们可以认为每棵树的结论不是年龄本身，而是年龄的积累。GBDT的核心是每棵树都学习所有先前树的结论之和的残差，这个残差是在加上预测值之后的实际值的累积。比如A的真实年龄是18岁，但是第一棵树的预测年龄是12岁，相差6岁，也就是残差是6岁。

然后在第二棵树上，我们把A的年龄设为6岁来学习。如果第二棵树真的能把A分成6岁的叶节点，那么累加两棵树的结论就是A的真实年龄；如果第二棵树的结论是5岁，A还有1岁的剩余，第三棵树A的年龄变成1岁。继续学习。这就是梯度推进在GBDT的含义。"

事实上，我们可以看到GBDT和兰登森林的本质区别。GBDT不仅基于积分思想，而且基于残差的学习。这里我们用一个GBDT的经典例子来解释。

假设我们有一个训练集，训练集中只有A、B、C、D四个人，他们的年龄分别是14岁、16岁、24岁、26岁。其中，A和B分别是高一和高三学生；c和d都是应届毕业生，工作两年的员工。如果您使用传统的回归决策树进行训练，您将获得如下结果，如图1所示:

图1

现在我们用GBDT来做这件事。因为数据太少，我们把叶节点限制在两个，即每棵树只有一个分枝，只能学习两棵树。我们将得到如下结果，如图2所示:

图2

在第一个树杈中，如图1所示，由于A和B年龄相近，C和D年龄相近，所以分为两组，每组用平均年龄作为预测值。

这个时候计算残差，那么A的残差是16-15=1的预测值。

此外，a，b，c和d的残差分别为-1，1，-1和1。然后我们取残差代替A，B，C，D的原值，在第二棵树上学习。如果我们的预测值等于它们的残差，我们只需要把第二棵树的结论加到第一棵树上就可以得到真实的年龄。

这里的数据显然是我能做的。第二棵树只有1和-1两个值，直接分成两个节点。这时候每个人的残差都是0，也就是每个人得到的都是真实的预测值。

最后，GBDT的预测结果是:

答:14岁高中生，购物少，经常问高三问题；预测年龄为a = 15–1 = 14；

b:16岁高中生；购物少，经常被同学提问；预测年龄为B = 15+1 = 16；；

C: 24岁应届毕业生；逛街比较多，经常问哥哥问题；预计年龄为c = 25–1 = 24岁。

d:工作两年的26岁员工；逛街比较多，经常被弟弟问问题；预测年龄为D = 25+1 = 26。

那么它在哪里反映渐变呢？其实第一棵树的最后，想想。无论此时的代价函数是什么，无论是均方差还是均差，只要以误差为度量标准，残差向量就是它的全局最优方向，就是梯度。

注:图1和图2最终效果相同。你为什么需要GBDT？答案是过度拟合。过拟合是指为了使训练集更精确，学习了很多“只建立在训练集上的规则”，导致改变一个数据集的当前规则不适用。

只要一棵树上有足够多的叶节点，训练集总能训练出100%的准确率。在训练精度和实际精度之间，后者才是我们真正想要的。

我们发现图1为了达到100%的准确率，使用了三个特征，其中“在线时间>:1.1h”这个分支已经明显拟合。在这个数据集上，a和b可能只是a每天上网1.09 h和b每天上网1.05 h。

但是是不是>:用1.1小时来判断每个人的年龄显然是违背常识的；相对来说，图2中的boosting虽然用了两棵树，但实际上只用了两个特性就完成了，后一个特性就是问答比。显然，图2的基础更可靠。

由此可见，GBDT像随机森林一样，不容易陷入过拟合，可以得到很高的精度。

补充示例

本文以李航博士的《统计学习方法》中的举树为例，进一步说明了GBDT的详细过程。

一直认为李航博士的机器学习更接近算法的本质。我们先来看看他是如何定义GBDT的。

提升法实际上采用的是加法模型和前向分步算法。基于决策树的提升方法称为提升树，它是用于分类问题的二元分类树和用于回归问题的二元回归树。提升树模型可以表示为决策树的加法模型:

其中，表示决策树；表示决策树的参数；m是树的数量。

提升树对不同问题的主要区别在于不同的损失函数，包括带平方误差损失函数的回归问题、带指数损失函数的分类问题和带一般损失函数的一般决策问题。

提升树的过程:

让我们通过一个例子来彻底看看提升树是如何一步步解决问题的。

觉得这篇文章有帮助？请与更多人分享

关注“猿助猿”，实现顶层发展

技术交流QQ群:517877452