数据挖掘中的利器--XGBoost理论篇

XGBoost是各种数据挖掘或机器学习算法类比赛中每个团队都会使用且精度相对最好的算法之一(Deep Learning算法除外)。也就是说,对于刚转向机器学习领域的同胞们,在掌握数据挖掘的基本常识概念之后,要想在比赛中有所收获,掌握XGBoost算法也是当务之急。


1、XGBoost算法优点

XGBoost 是 Extreme Gradient Boosting的简称。它是Gradient Boosting Machine的一个C++实现.创建之初为受制于现有库的计算速度和精度,XGBoost最大的特点,它能够自动利用CPU的多线程进行并行,同时,在算法上加以改进提高了精度[1]。

传统的GBDT(Gradient Boosted Decision Trees)模型,在1999年,由Jerome Friedman提出,最早Yahoo将GBDT模型应用于CTR预估。GBDT是一个加权回归模型,通过Boosting迭代弱学习器,相对于LR的优势是不需要做特征的归一化,可以自动进行特征选择,模型可解释性较好,可以适应多种损失函数如SquareLoss,LogLoss等[2]。但作为非线性模型,其相对线性模型的缺点比较明显,Boosting是串行的过程,不能并行化,计算复杂度较高,同时其不太适合高维稀疏特征,通常采用稠密的数值特征。

XGBoost不同于传统的GBDT只利用了一阶导数的信息,而XGBoost对损失函数做了二阶泰勒展开,并在目标函数中加入了正则项,整体求最优解,用以权衡目标函数和模型的复杂程度,防止过拟合。

除理论与传统GBDT存在差别外, XGBoost的设计理念主要有如下几点优点:

  • 速度快。让一个程序在必要时占领一台机器,并且在所有迭代的时候一直跑到底,防止重新分配资源的开销。机器内部采用单机多线程方式来并行加速,机器之间通信基于Rabit实现的All Reduce的同步接口。
  • 可移植,少写代码。大多数分布式机器学习算法的结构都是分布数据,在每个子集上面算出一些局部的统计量,然后整合出全局的统计量,然后再分配给每个计算节点进行下一轮的迭代。根据算法本身的需求,抽象出合理的接口,如All Reduce,并通过通用的Rabit库让平台实现接口的需求,最终使得各种比较有效的分布式机器学习抽象地实现在各个平台上。
  • 可容错。Rabit版本的All Reduce有一个很好的性质,支持容错,而传统的MPI不支持。由于All Reduce中,每一个节点最后拿到相同的结果,这意味着可以让一部分节点记住结果,当有节点挂掉重启的时候,可以直接向还活着的节点索要结果。

2、XGBoost算法与目标函数

XGBoost算法是基于树的Boosting算法,并在其优化目标函数中加了正则化项,其目标函数为

式中Lm表示第m次迭代中生成树模型fm的叶子节点数,

表示fm各个叶子节点的输出值。Ƴ和λ是正则化系数,从公式中能看出这两个值控制着模型的复杂度和目标函数的输出,当Ƴ和λ都为零时,只含有损失函数部分,即生成树的规模和叶子节点的输出值不受限制。加了正则化项,使得算法会选择简单而性能较好的模型fm,公式中的正则化项只是抑制在迭代过程中弱学习器fm(X)过拟合,并不参与最终模型的集成。式中

应至少满足是二阶连续可导的凸函数。

XGBoost算法跟Gradient Boosting算法一样采用分步前向加性模型,区别在于,Gradient Boosting算法是学习一个弱学习器fm(X)来近似损失函数在点Pm-1=Fm-1(X)处的负梯度,而XGBoost算法是先求损失函数在该点的二阶泰勒近似值,然后最小化该近似损失函数来训练弱学习器fm(X),得到

式中

表示损失函数假设在点Pm-1(X)处的第i个分量Fm-1(xi)的一阶偏导数,

为损失函数在点Pm-1(X)处的第i个分量Fm-1(xi)的二阶偏导数,使用上式作为近似优化目标函数。对上式变形,得到

式中第一项在每次迭代过程中是常数,不会影响优化目标函数的结果,因此,最终优化目标函数变为


3、具体代码实例

扯了一大推理论,感觉还是来点干货靠谱(题外之话了,大家在应用每一个算法之前,最好理解算法的原理,这样才能在使用算法过程中,调好算法的每一个参数)。

Python代码:

参考文献:

[1] Chen T, Guestrin C. Xgboost: A scalable tree boosting system[C]//Proceedings of the 22Nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2016: 785-794.

[2] Friedman J H. Greedy function approximation: a gradient boosting machine[J]. Annals of statistics, 2001: 1189-1232.

原文发布于微信公众号 - 机器学习算法全栈工程师(Jeemy110)

原文发表时间:2017-08-13

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器学习之旅

理论:随机森林-枝剪问题

剪枝的意义是:防止决策树生成过于庞大的子叶,避免实验预测结果过拟合,在实际生产中效果很差

622
来自专栏杨熹的专栏

支持向量机

Udacity Machine Learning Support Vector Machine ---- 在做分类问题时,想要找到最好的那条线: ? 会选择...

3235
来自专栏机器学习之旅

总结:常见算法工程师面试题目整理(一)

最近抽风,出去面试了不少公司,和不少算法工程师招聘的朋友有所交流,整理了相关比较有意思的题目,供大家参考:

553
来自专栏PPV课数据科学社区

【R系列】概率基础和R语言

R语言是统计语言,概率又是统计的基础,所以可以想到,R语言必然要从底层API上提供完整、方便、易用的概率计算的函数。让R语言帮我们学好概率的基础课。 1. 随机...

2698
来自专栏本立2道生

亚像素数值极值检测算法总结

在计算机视觉领域,经常需要检测极值位置,比如SIFT关键点检测、模板匹配获得最大响应位置、统计直方图峰值位置、边缘检测等等,有时只需要像素精度就可以,有时则需要...

772
来自专栏数据科学与人工智能

【算法】xgboost算法

小编邀请您,先思考: 1 XGBoost和GDBT算法有什么差异? XGBoost的全称是 eXtremeGradient Boosting,2014年2月诞生...

3219
来自专栏小鹏的专栏

一个隐马尔科夫模型的应用实例:中文分词

什么问题用HMM解决 现实生活中有这样一类随机现象,在已知现在情况的条件下,未来时刻的情况只与现在有关,而与遥远的过去并无直接关系。 比如天气预测,如果我...

2447
来自专栏数据科学与人工智能

决策树算法那些事--CART|机器学习

一、树算法介绍 当前数据挖掘领域中存在10个火热的算法、它们涉及到数据的聚类、分类、关联规则、排序等方面。今天就跟大家说说基于树的分类算法--决策树,决策树有非...

3135
来自专栏阮一峰的网络日志

理解矩阵乘法

大多数人在高中,或者大学低年级,都上过一门课《线性代数》。这门课其实是教矩阵。 ? 刚学的时候,还蛮简单的,矩阵加法就是相同位置的数字加一下。 ? 矩阵减法也类...

3277
来自专栏深度学习自然语言处理

【机器学习】决策树的理论与实践

zenRRan二十出头了,到了婚配的年龄啦。又因为家是名门望族,所以一堆人抢着想来应聘配偶的职位。但是zenRRan比较挑剔,必须达到他的要求才能有机会成为他的...

631

扫描关注云+社区