XGBoost原理简介

2020-06-12 17:13:44 浏览数 (1)

XGBoost

简介

在大数据竞赛中,XGBoost霸占了文本图像等领域外几乎80%以上的大数据竞赛.当然不仅是在竞赛圈,很多大公司也都将XGBoost作为核心模块使用,好奇的人肯定都很想揭开这个神奇的盒子的幕布,究竟是里面是什么,为什么这么厉害? 本篇notebook会从理论和实践的角度来讲述XGBoost以及关于它的一段历史与组成.

此处我们会按照下图的形式来讲述关于XGBoost的进化史.

CART(Classification and Regression Tree)

CART的全称是Classification and Regression Tree,翻译过来就是分类与回归树,是由四人帮Leo Breiman, Jerome Friedman, Richard Olshen与Charles Stone于1984年提出的,该算法是机器学习领域一个较大的突破,从名字看就知道其既可用于分类也可用于回归.

CART本质是对特征空间进行二元划分(即CART生成的决策树是一棵二叉树),它能够对类别变量与连续变量进行分裂,大体的分割思路是先对某一维数据进行排序(这也是为什么我们对无序的类别变量进行编码的原因[1]),然后对已经排好后的特征进行切分,切分的方法就是if … else …的格式.然后计算衡量指标(分类树用Gini指数,回归树用最小平方值),最终通过指标的计算确定最后的划分点[2],然后按照下面的规则生成左右子树:

If x < A: Then go to left; else: go to right.

分裂指标（分类树：Gini指数）

①.从Gini指数的数学形式中,我们可以很容易的发现,当 的时候Gini指数是最大的,这个时候分到每个类的概率是一样的,判别性极低,对我们分类带来的帮助很小,可以忽略. ②.当某些 较大,即第 类的概率较大,此时我们的Gini指数会变小意味着判别性较高.样本中的类别不平衡.

在CART分割时,我们按照Gini指数最小来确定分割点的位置[4].

例子

对于Categorical变量

对于连续变量

因为连续变量的部分已经通过某一个值进行了划分,所以计算的时候和Categorical变量的计算类似.

CART分割示意图

CART算法(分类树,无剪枝)

输入:训练数据集D,停止计算条件. 输出:CART决策树.

根据训练数据集,从根节点开始,递归地对每个结点进行以下操作,构建二叉决策树:

CART（回归树部分）

输入:训练数据集D,停止计算条件. 输出:CART回归树 .

在训练数据集所在的输入空间中,递归地将每个区域划分为两个子区域并决定每个子区域的输出值,构建二叉决策树:

附录

  • 由上面的分析我们可以知晓,CART是基于单特征的,没有考虑特征之间的关联性,但这也给了我们两个提示,①我们的特征是不需要进行归一化处理的[6];②有时我们需要通过特征之间的相关性来构建新的特征[7]..
  • 因为本篇notebook的核心是XGBoost,关于CART剪枝以及其他相关的内容就不再累述.

Boosting

上面是最常用的树模型的介绍,现在我们要介绍Boosting技术,Boosting在维基百科上面的解释是:

  • Boosting: a machine learning ensemble meta-algorithm for primarily reducing bias, and also variance in supervised learning, and a family of machine learning algorithms which convert weak learners to strong ones[8].

实际生活中,人们也常用"三个臭皮匠赛过诸葛亮"的话来描述Boosting(提升方法).当然这背后还有理论的支撑与保障,两个大牛Kearns和Valiant提出了强可学习和弱可学习概念同时在此概念下,Schapire证明的强可学习与弱可学习是等价的伟大理论[9].

服从Boosting维基百科的解释,我们用简单的数学对其进行表示,

Boosting Tree

Boosting的基本思想

提升树算法 (回归问题)[10]

问题

Gradient Boosting Decision Tree(梯度提升树)

Gradient Boosting的基本思想

梯度提升树算法[11]

注意

XGBoost

上面的部分讲述了GBDT的原理部分,现在正式进入主题,神奇的XGBoost,XGBoost展开的意思就是Extreme Gradient Boosting,其中Extreme是极致的意思,主要体现在工程设计层面,包括并发的程序执行,贪心的排序操作等,因为本篇notebook的核心不在于此,接下来我们着重介绍XGBoost在实现与原理上于传统GBDT的区别.

XGBoost与传统GBDT的算法层面的区别

XGBoost中的GBDT与传统的GBDT在算法层面有主要有两处较大的不同:

  • XGBoost中的导数不是一阶的,是二阶的[12];
  • XGBoost中的剪枝部分在对叶子的个数做惩罚的同时还加入权重的惩罚.换言之,正则项进行了改进[13].
XGBoost中的二阶梯度

其实这个对应的就是牛顿提升树.

Newton提升树 [12]

XGBoost中的正则项

传统的GBDT为了控制树的复杂度常常会对树的叶子个数加正则项进行控制, XGBoost不仅仅对于树中的叶子节点的个数进行控制,与此同时还对每个叶子节点的分数加入正则.即:

XGBoost的推导与算法构建

XGBoost的splitting准则的推导

  • 这个值被用来评估决策树的不纯洁性,类似于Gini指数等的作用,而这也确实是XGBoost的Splitting指标[13].

XGBoost初始算法(Exact Greedy Algorithm)
XGBoost近似算法

当我们数据的规模足够大的时候，我们的数据较难存到内存中去,而且大量的数据使得计算量也变得很大,此时Exact Greedy的算法就不太实用,所以我们往往会寻求一种近似算法,而XGBoost的作者陈天奇针对该问题提出了一个新的近似算法,算法的核心可以参考XGBoot论文的"3.3 Weighted Quantile Sketch"部分.

Extreme部分

XGBoost的核心算法思想还是属于GBDT那一套,但此外,XGBoost还有着它的其他优势,正如陈天奇所述的,XGBoost中Extreme部分更多的是系统设计层面的,它是将我们的机器用到了极致.其中核心的包括:

  • 用于并行计算的列模块
  • Cache-aware Access
  • 内存外的计算

具体的细节我就不再累述,可以参考陈天奇的论文以及他的代码进行细细的研究.

XGBoost的其他特性

XGBoost可以认为是一款集成了多种机器学习算法思想的一款利器:

  • 行(样本)采样,列(特征)采样 (降低方差)
  • Early stopping,Shrinkage(学习率)的设置,这些可以用来防止过拟合.
  • 缺失值的处理

参考资料

  1. XGBoost 与 Boosted Tree:http://www.52cs.org/?p=429
  2. CART博客:http://www.cnblogs.com/en-heng/p/5035945.html
  3. Boosting:https://en.wikipedia.org/wiki/Boosting(machine_learning)
  4. Boosted Tree:http://xgboost.readthedocs.io/en/latest/model.html
  5. 李航《统计机器学习》
  6. Friedman:Greedy Function Approximation: A Gradient Boosting Machine
  7. XGBoost: A Scalable Tree Boosting System: https://arxiv.org/pdf/1603.02754.pdf
  8. XGBoost: https://github.com/dmlc/xgboost
  9. Wepe的ppt:https://link.zhihu.com/?target=http://wepon.me/files/gbdt.pdf
数据分析 编程算法 决策树 网站

0 人点赞