XGBoost原理简介
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(学习率)的设置,这些可以用来防止过拟合.
- 缺失值的处理
参考资料
- XGBoost 与 Boosted Tree:http://www.52cs.org/?p=429
- CART博客:http://www.cnblogs.com/en-heng/p/5035945.html
- Boosting:https://en.wikipedia.org/wiki/Boosting(machine_learning)
- Boosted Tree:http://xgboost.readthedocs.io/en/latest/model.html
- 李航《统计机器学习》
- Friedman:Greedy Function Approximation: A Gradient Boosting Machine
- XGBoost: A Scalable Tree Boosting System: https://arxiv.org/pdf/1603.02754.pdf
- XGBoost: https://github.com/dmlc/xgboost
- Wepe的ppt:https://link.zhihu.com/?target=http%3A//wepon.me/files/gbdt.pdf