GBDT(梯度提升决策树)算法(详细版)

一、前言

通过之前的文章GBDT算法(简明版)对GBDT的过程做了大概的讲解,我们可以了解到GBDT是一种迭代的决策树算法,由多棵决策树组成,所有树的结论累加起来做最终答案。GBDT是一个应用很广泛的算法,可以用于分类,回归和特征选择,特别是用于和其他算法进行模型组成时,如logistic+GBDT,该算法在很多数据上都有不错的效果,GBDT还有其他的名字,如MART,GBRT和Tree Net等。

二、基础知识

2.1 决策树(DT)

决策树这种算法有着很多良好的特性,比如说训练时间复杂度较低,预测的过程比较快速,模型容易展示(容易将得到的决策树做成图片展示出来)等。但是同时,单决策树又有一些不好的地方,比如说容易over-fitting,虽然有一些方法,如剪枝可以减少这种情况,但是还是不够的。模型组合(比如说有Boosting,Bagging等)与决策树相关的算法比较多,这些算法最终的结果是生成N(可能会有几百棵以上)棵树,这样可以大大的减少单决策树带来的毛病,有点类似于三个臭皮匠等于一个诸葛亮的做法,虽然这几百棵决策树中的每一棵都很简单(相对于C4.5这种单决策树来说),但是他们组合起来确是很强大。

决策树分为两大类,分类树和回归树,分类树是我们比较熟悉的决策树,用于分类标签值,如阴天/晴天,性别预测,垃圾邮件分类,而回归树用于预测实数值,如明天的温度、用户的年龄和网页的相关程度,也就是分类树是定性的,回归树是定量的。

GBDT的核心在于累加所有树的结果作为最终结果,比如对年龄的累加来预测年龄,而分类树的结果显然是没办法累加的,所以GBDT中的树是回归树,不是分类树。

2.2 boosting提升方法

adaboost其实是boosting算法的特例,因为adaboost可以表示为boosting的前向分布算法(Forward stagewise additive modeling)的一个特例,boosting可以表示为:

其中的w是权重,Φ是弱分类器(回归器)的集合,其实就是一个加法模型(即基函数的线性组合),前向分布算法实际上是一个贪心算法,也就是在每一步求解弱分类器Φ(m)和其参数w(m)的时候不去修改之前已经求好的分类器和参数:

以上就是提升方法(之前向分布算法)的大致结构了,可以看到其中存在变数的部分其实就是极小化损失函数 这关键的一步了,如何选择损失函数决定了算法的最终效果。几个常见的boosting:

Gradient Boost (GB)

GB其实是一个框架,里面可以套入很多不同的算法。Gradient Boost与传统的Boost的区别是,每一次的计算是为了减少上一次的残差(residual),而为了消除残差,我们可以在残差减少的梯度(Gradient)方向上建立一个新的模型。所以说,在Gradient Boost中,每个新的模型的建立是为了使得之前模型的残差往梯度方向减少,与传统Boost对正确、错误的样本进行加权有着很大的区别。我们设F(x,P)是分类函数,P是参数集。将加法函数延伸成如下格式:

上式h(x;a)是基函数,是对输入变量x的单参数化函数,其中a={a1,a2,...,am}。在不同的基函数中,a代表着不同的意思,比如本文的选择基函数CART中,每个函数h(x;am)是表示一棵小的回归树。回归树中参数am表示树的划分变量,划分位置和每棵树中叶子结点的均值等。

对于上式两个参数的求解,是通过优化损失函数求的。

以上可解决方案是利用Greedy Stagewise方法,

然后得到最终分类函数:

上面选用了梯度下降法(是一种线搜索方法)来优化目标值,该方法在之前讲解logistic算法中有详细讲解,可查看前面有关logistic了解。求最小值取负梯度方法为最优下降方向,即:

因此上面上个参数可通过优化如下式求的:

可以看到,参数am是对梯度方向进行最小二乘法拟合,即优化参数am,使得构建的下一个基函数(如m-1到m个)能够最接近负梯度方向(最优下降方向)。pm则根据损失函数L的不同的得到不同的算法。对于Gradient Boost算法的伪算法如下:

7. endFor

end Algorithm

四、应用

4.1 损失函数为最小二乘法

那么残差则为:

那么LS_Boost伪算法表示如下:

还有更多的损失函数的不同,可以得到相应的Gradient Boost算法,其中常见的如下

4.2 回归树

当基函数选用的是回归树时,即本文的提到的算法GBDT。在此之前,我们假定每个基函数是由J个结点组成的回归树,对于回归树需要理解为对特征空间的分割,讲解决策树算法文章时,已有提及。那么回归树模型的加法模型可以表示成如下:

上式中l(.)是指示函数,表示如果x在空间Rj中则为1,否则为0。bj是回归树结点上的值。其实就是对应Gradient Boost伪算法中的通过最小二乘法得到的am参数,那么对于回归树,对应Gradient Boost算法的为:

上式可以更新为

其中,

因此对于GBDT算法的伪代码可以表示为如下:

上面伪算法2的意思是利用梯度值rim和输入x构建一棵回归树,回归树将划分出Rjm个空间。同样我们会根据损失L(.)的不同得到不同的GBDT算法,如LS_TreeBoost,LAD_TreeBoost(Least absolute deviation)等。上面也就是GBDT算法的整个框架了,总之所谓Gradient就是去拟合Loss function的梯度,将其作为新的弱回归树加入到总的算法中即可。

五、正则化(regularization)

通常,对训练集拟合太紧密会导致模型泛化能力的下降,正则化通过约束拟合过程能够减小过拟合的影响。常用的技术手段是通过控制决策树M的深度和缩减(Shrinkage)Gredient Boost。

在基函数选用决策树中,增加M值能够减小训练集的误差,但是太大会导致过拟合现象。最佳值M能够通过模型选择方法来估计,如使用独立测试集或交叉验证方法。

而缩减的方法,是算法每次只学习一点点来减小单个特征对整体的影响,修改Gradient Boost的更新规则为:

参数v称为学习率,通常学习率会选择较小的值,小于0.1能够提高算法的泛化能力,但是越小的学习率也会增加算法的迭代次数。

六、总结

本文简单介绍的boost提升方法和讲解了Gredient Boost框架和Gredient Boost框架的应用GBDT,并且介绍了提高算法泛化能力的方法,正则化。还有一些内容本文没有提及,比如Gredient Boost中M回归问题,二分类和M分类的应用,还有其他的一些损失函数相关的应用。如果有兴趣可以参考Friedman大牛的文章:Greedy function approximation : A Gradient Boosting Machine。

PS:文章一些算法的伪代码来自不同教材,个别参数不一致,但是意思是一样的。

参考内容:

http://blog.csdn.net/dark_scope/article/details/24863289

Greedy function approximation : A Gradient Boosting Machine。

李航:《统计学习方法》

免责声明:本文系网络转载。版权归原作者所有。如涉及版权,请联系删除!

原文发布于微信公众号 - 智能算法(AI_Algorithm)

原文发表时间:2017-05-03

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器学习AI算法工程

神经网络中的激活函数具体是什么?为什么ReLu要好过于tanh和sigmoid function?

为什么引入激活函数? 如果不用激励函数(其实相当于激励函数是f(x) = x),在这种情况下你每一层输出都是上层输入的线性函数,很容易验证,无论你神经网络有多少...

717100
来自专栏人工智能LeadAI

TensorFlow从0到1 | 第十五章 重新思考神经网络初始化

上一篇14 交叉熵损失函数——克服学习缓慢从最优化算法层面入手,将二次的均方误差(MSE)更换为交叉熵作为损失函数,避免了当出现“严重错误”时导致的学习缓慢。 ...

34580
来自专栏数据派THU

【一图看懂】计算机视觉识别简史:从 AlexNet、ResNet 到 Mask RCNN

原文:medium 来源:新智元 作者:Đặng Hà Thế Hiển 编译:新智元编辑部 本文长度为5000字,建议阅读8分钟 本文通过一张信息图示,讲述计...

35970
来自专栏TensorFlow从0到N

TensorFlow从0到1 - 15 - 重新思考神经网络初始化

上一篇14 交叉熵损失函数——克服学习缓慢从最优化算法层面入手,将二次的均方误差(MSE)更换为交叉熵作为损失函数,避免了当出现“严重错误”时导致的学习缓慢。...

47470
来自专栏SIGAI学习与实践平台

深入浅出聚类算法

聚类问题是机器学习中无监督学习的典型代表,在数据分析、模式识别的很多实际问题 中得到了应用。在本文中,SIGAI 将为大家深入浅出的介绍聚类问题的定义以及各种典...

23710
来自专栏机器学习算法与Python学习

主流机器学习算法优缺点总结,先从基础玩起!

决策树分类方法,采用基于最小距离的基尼指数估计函数,用来决定由该子数据集生成的决策树的拓展形。决策树回归方法,采用切分点与切分变量来计算的损失来估计函数。如果目...

18020
来自专栏AI科技大本营的专栏

笔记 |《深度学习原理与TensorFlow实践》学习笔记(三)

作者 | 王清 目录 图像识别的经典课题 计算机视觉 图像识别课题 卷积神经网络原理 前深度学习时代 卷积操作Convolution 池化Pooling ReL...

38750
来自专栏信数据得永生

《Scikit-Learn与TensorFlow机器学习实用指南》第5章 支持向量机

56980
来自专栏深度学习

神经网络相关名词解释

很多人认为深度学习很枯燥,大部分情况是因为对深度学习的学术词语,特别是专有名词很困惑,即便对相关从业者,亦很难深入浅出地解释这些词语的含义。 

39170
来自专栏灯塔大数据

原创译文|从神经网络说起:深度学习初学者不可不知的25个术语和概念(下)

人工智能,深度学习和机器学习,不论你现在是否能够理解这些概念,你都应该学习。否则三年内,你就会像灭绝的恐龙一样被社会淘汰。 ——马克·库班(NBA小牛队老板,...

48270

扫码关注云+社区

领取腾讯云代金券