GBDT梯度提升树介绍

GBDT(Gradient Boosting Decision Tree) ,又叫 MART(Multiple Additive Regression Tree),是一种迭代的决策树算法,该算法由多棵决策树组成,所有树的结论累加起来做最终答案。它在被提出之初就和SVM一起被认为是泛化能力较强的算法。

GBDT中的树是回归树(不是分类树),GBDT用来做回归预测,调整后也可以用于分类。

决策树分为两大类,回归树和分类树。

  • 回归树用于预测实数值,如明天的温度、用户的年龄、网页的相关程度;
  • 分类树用于分类标签值,如晴天/阴天/雾/雨、用户性别、网页是否是垃圾页面。

这里要强调的是,回归树的结果加减是有意义的,如10岁+5岁-3岁=12岁,分类树则无意义,如男+男+女=到底是男是女?

回归树

1、回归树原理简介

先说分类树,我们知道C4.5分类树在每次分枝时,是穷举每一个特征的每一个阈值,找到使得按照特征<=阈值特征>阈值分成的两个分枝的熵最大的特征和阈值(熵最大的概念可理解成尽可能每个分枝的男女比例都远离1:1),按照该标准分枝得到两个新节点,用同样方法继续分枝直到所有人都被分入性别唯一的叶子节点,或达到预设的终止条件,若最终叶子节点中的性别不唯一,则以多数人的性别作为该叶子节点的性别

回归树(Regression Decision Tree)总体流程类似于分类树,区别在于,回归树的每一个节点都会得一个预测值,以年龄为例,该预测值等于属于这个节点的所有人年龄的平均值。分枝时穷举每一个特征的每个阈值找最好的分割点,但衡量最好的标准不再是最大熵,而是最小化平方误差。也就是被预测出错的人数越多,错的越离谱,平方误差就越大,通过最小化平方误差能够找到最可靠的分枝依据。分枝直到每个叶子节点上人的年龄都唯一(这太难了)或者达到预设的终止条件(如叶子个数上限),若最终叶子节点上人的年龄不唯一,则以该节点上所有人的平均年龄做为该叶子节点的预测年龄。

2、回归树示例

下面是一个示例数据集:

面积/平米价格/万
2040.1
2140.3
3570.4
3670.2

(1)、选择最优特征

  1. 按特征"面积" = 20划分数据集:

    • y1 均值为40.1
    • y2 均值为(40.3 + 70.4 + 70.2) / 3 = 60.3
    • 平方误差为:0 + (40.3 – 60.3)*2 + (70.4 – 60.3)*2 + (70.2 – 60.3)*2= 600.02
  2. 按特征"面积" = 21划分数据集:

    • y1 均值为(40.1 + 40.3)/ 2 = 40.2
    • y2 均值为(70.4 + 70.2) / 2 = 70.3
    • 平方误差为:(40.1 –40.2)*2 + (40.3 –40.2)*2 + (70.4 –70.3)*2 +(70.2 –70.3)*2 = 0.04
  3. 按特征"面积" = 35划分数据集:

    • y1 均值为(40.1 + 40.3 + 70.4) / 3 = 50.27
    • y2 均值为70.2
    • 平方误差为:(40.1 –50.27)*2 + (40.3 –50.27)*2 + (70.4 –50.27)*2 + 0 = 608.05

综上所述,由于按特征"面积" = 21 比特征"面积" = 20"面积" = 35划分的平方误差小,所以特征"面积" = 21为切分点。

(2)、按最优特征划分数据集

以特征"面积" = 21为切分点,将数据切分为{面积 = 20,价格 = 40.1; 面积 = 21, 价格 = 40.3}{面积 = 35,价格 = 70.4; 面积 = 36, 价格 = 70.2}两个子集。

其中子集{面积 = 20,价格 = 40.1; 面积 = 21, 价格 = 40.3}的目标变量非常接近,故不继续划分,得叶节点值(40.1 + 40.3) / 2 = 40.2; 同理得子集{面积 = 35,价格 = 70.4; 面积 = 36, 价格 = 70.2}的叶节点值为 (70.4 + 70.2) / 2 = 70.3

梯度提升树算法

梯度提升树(Gradient Boosting Decision Tree)是迭代多棵回归树来共同决策。当采用平方误差损失函数时,每一棵回归树学习的是之前所有树的结论和残差,拟合得到一个当前的残差回归树,残差的意义如公式:残差 = 真实值 - 预测值。提升树即是整个迭代过程生成的回归树的累加。

1、小例子

在这个例子里,我们通过传统的回归决策树梯度提升树两种方式来预测年龄。

训练集是4个人,A,B,C,D,年龄分别是14,16,24,26。样本中有购物金额上网时长经常到百度知道提问等特征。

如果是用一棵传统的回归决策树来训练,会得到如下图所示结果:

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

该例子很直观的能看到,梯度提升树的预测值等于所有树值得累加,如A的预测值 = 树1左节点 值 15 + 树2左节点 -1 = 14

2、Gradient体现在哪里

那么哪里体现了Gradient呢?

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

3、为何需要GBDT

既然传统的回归决策树和GBDT最终效果相同,为何还需要GBDT呢?

答案是过拟合。过拟合是指为了让训练集精度更高,学到了很多仅在训练集上成立的规律,导致换一个数据集当前规律就不适用了。其实只要允许一棵树的叶子节点足够多,训练集总是能训练到100%准确率的(大不了最后一个叶子上只有一个instance)。在训练精度和实际精度(或测试精度)之间,后者才是我们想要真正得到的。

我们发现传统的回归决策树为了达到100%精度使用了3个特征(上网时长、时段、网购金额),其中分枝“上网时长>1.1h” 很显然已经过拟合了。相对来说,GBDT虽然用了两棵树 ,但其实只用了2个特征就搞定了,后一个特征是问答比例,其分枝依据更合乎逻辑(当然这里是相比较于上网时长特征而言)。

4、GBDT适用范围

  • GBDT 可以适用于回归问题(线性和非线性),相对于 logistic regression 仅能用于线性回归,GBDT 适用面更广。
  • GBDT 也可用于二分类问题(设定阈值,大于为正,否则为负)和多分类问题。

参考

赞赏一杯咖啡
0%