转载

[Machine Learning & Algorithm] 决策树与迭代决策树(GBDT)

[Machine Learning & Algorithm] 决策树与迭代决策树(GBDT)

谈完数据结构中的树(详情见参照之前博文《数据结构中各种树》),我们来谈一谈机器学习算法中的各种树形算法,包括ID3、C4.5、CART以及基于集成思想的树模型Random Forest和GBDT。本文对各类树形算法的基本思想进行了简单的介绍,重点谈一谈被称为是算法中的“战斗机”,机器学习中的“屠龙刀”的GBDT算法。

1. 决策树的模型

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

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

[Machine Learning & Algorithm] 决策树与迭代决策树(GBDT)

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

[Machine Learning & Algorithm] 决策树与迭代决策树(GBDT)

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

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

2. 决策树的基本知识

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

1) 特征的选择;

2) 决策树的生成;

3) 决策树的剪枝。

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

1) 熵(entropy)

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

P(X=x i )=p i , i=1,2, ... , n

则随机变量X的熵定义为:

H(X)=- ∑ p i *  logp i , i=1,2, ... , n

熵只依赖X的分布,和X的取值没有关系,熵是用来度量不确定性,当熵越大,概率说X=xi的不确定性越大,反之越小,在机器学期中分类中说,熵越大即这个类别的不确定性更大,反之越小,当随机变量的取值为两个时,熵随概率的变化曲线如下图:

[Machine Learning & Algorithm] 决策树与迭代决策树(GBDT)

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

条件熵(conditional entropy):表示在一直随机变量X的条件下随机变量Y的不确定性度量。

设随机变量(X, Y ),其联合概率分布为 P(X, Y) = p ij (i=1,2, ... , n; j=1,2, ... , m),随机变量X给定的条件下随机变量Y的条件熵H(Y|X),定义为X给定条件下Y的条件概率分布的熵对X的数学期望:

H(Y|X)=∑ p i* H(Y|X=x i )

这里,p i =P(X=x i ), 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)

信息增益比g R (D, A)定义为其信息增益g(D, A)与训练数据集D关于特征A的值的熵H A (D)之比,即

g R (D, A)=g(D, A)/H A (D)

其中,H A (D)=-∑|D i |/|D|*log 2 |D i |/|D|, n是特征A取值的个数。

4) 基尼指数(gini index)

分类问题中,假设有K个类,样本属于第k类的概率为p k ,则概率分布的基尼指数定义为:

Gini(p)=∑p k (1-p k )=1-∑p k 2

对于二分类问题,若样本点属于第1个类的概率是p,则概率分布的基尼指数为:

Gini(p)=2p(1-p)

对于给定的样本集合D,其基尼指数为:

Gini(D)=1-∑(|C k |/|D|) 2

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

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

Gini(D,A)=|D 1 |/|D|*Gini(D 1 )+|D 2 |/|D|*Gini(D 2 )

基尼指数Gini(D)表示集合D的不确定性,基尼指数越大,样本集合的不确定性也就越大,这一点与熵相似。

3. ID3、C4.5&CART

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

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

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

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

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

决策树的剪枝:我们知道,决策树在生成的过程中采用了贪婪的方法来选择特征,从而达到对训练数据进行更好地拟合(其实从极端角度来看,决策树对训练集的拟合可以达到零误差)。 而决策树的剪枝是为了简化模型的复杂度,防止决策树的过拟合问题。 具体的决策树剪枝策略可以参见李航的《统计学习方法》。

4. Random Forest

随机森林是一种集成学习+决策树的分类模型,它可以利用集成的思想(投票选择的策略)来提升单颗决策树的分类性能(通俗来讲就是“三个臭皮匠,顶一个诸葛亮”)。

集集成学习和决策树于一身,随机森林算法具有众多的优点,其中最为重要的就是在随机森林算法中 每棵树都尽最大程度的生长,并且没有剪枝过程。

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

有关随机森林的详细介绍可以参见之前的一篇博文 《随机森林(Random Forest)》 。

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的理解和认识,有关Gradient Boosting的详细解释请见 wiki百科 。

在这里引用另外一个网友的解释来说明一下对GBDT中的Gradient Boosting的理解:

以下一段内容引自《 GBDT(MART) 迭代决策树入门教程 | 简介 》。

“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所示结果:

[Machine Learning & Algorithm] 决策树与迭代决策树(GBDT)

图1

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

[Machine Learning & Algorithm] 决策树与迭代决策树(GBDT)

图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同随机森林一样,不容易陷入过拟合,而且能够得到很高的精度。

6. 参考内容

[1] 李航《统计学习方法》

[2]  GBDT(MART) 迭代决策树入门教程 | 简介

正文到此结束
Loading...