XGBoost之切分点算法

浏览: 617

作者:张磊 从事AI医疗算法相关工作

个人微信公众号:

机器学习算法那些事(微信ID:zl13751026985)


前言

上文介绍了XGBoost的算法原理并引出了衡量树结构好坏的打分函数(目标函数),根据特征切分点前后的打分函数选择最佳切分点,但并未对节点的切分算法作详细的介绍。本文详细的介绍了XGBoost的切分点算法,内容参考陈天奇博士《XGBoost :A scalable Tree Boosting System》,后台回复XGBoost,获取论文下载链接。

目录


  1. 并行原理

  2. 切分点算法之贪婪算法

  3. 切分点算法之分位点算法

  4. 切分点算法之权重分位点算法

  5. 稀疏数据的切分算法

  6. 总结

1. 并行原理

XGBoost是串行生成CART树,但是XGBoost在处理特征时可以做到并行处理,XGBoost并行原理体现在最优切分点的选择,假设样本数据共M个特征,对于某一轮CART树的构建过程中,选择最佳切分点算法如下图:

1. 红色框表示根据每个特征大小对训练数据进行排序,保存为block结构,block个数与特征数量相等。                                                             

2. 绿色宽表示对每个block结构选择最佳特征切分点 ,节点切分标准是目标函数下降的程度,目标函数含义可参考上文 

3. 黑色框表示比较每个block结构的最佳特征切分点的目标函数下降的增益,选择最佳切分点。

2. 切分点算法之贪婪算法

每一个block结构的切分点算法思路是相同的,因此,我重点介绍某一块block结构的切分点算法。

XGBoost分位点算法:根据特征对样本数据进行排序,然后特征从小到大进行切分,比较每次切分后的目标函数大小,选择下降最大的节点作为该特征的最优切分点。最后比较不同block块结构最优切分点的目标函数下降值,选择下降最大的特征作为最优切分点。


流程图如下:


【例】下表表示样本的某一列特征数值

根据特征大小对样本重新排序:

贪婪算法切分节点:

红箭头表示每一次的切分节点,选择目标函数下降最大的点作为切分节点。

3. 切分点算法之分位点算法

若特征是连续值,按照上述的贪婪算法,运算量极大 。当样本量足够大的时候,使用特征分位点来切分特征。流程图如下:

【例】下表表示样本的某一列特征数值,用三分位作为切分节点 。

根据特征大小进行样本排序:

用特征的三分位点作切分节点:

红箭头表示每一次的切分节点,选择目标函数下降最大的点作为切分节点。

4. 切分点算法之权重分位点算法

上节假设样本权重相等,根据样本的分位点来均分损失函数存在偏差,本节用样本权重来均分损失函数。

损失函数如下:

对其变形得到:

xi损失函数可以看做是以以−gi/hi作为label的均方误差,乘以大小hi的权重,换句话说,xi对loss的贡献权重为hi ,构建样本权重的分位点等于误差的均分。

上节假设样本权重相等,特征值的分位点作为切分点,本节假设样本权重是hi,构建样本权重的均分点步骤:

(1)根据特征大小对样本进行排序

(2)定义排序函数:

其中x,z表示特征

(3)设置排序函数的分位点为切分点

【例】如下图

特征与对应的排序函数值的关系,如下表:

红色箭头表示以三分位点作为切分点。

最后,选择最优切分点。

5. 稀疏数据的切分算法

稀疏数据在实际项目是非常常见,造成稀疏数据的原因主要有:1. 数据缺失;2. 统计上的 0;3. one-hot编码的特征表示。

稀疏数据的切分点算法:

当出现特征值缺失时,包含缺失特征值的样本被映射到默认的方向分支,然后计算该节点的最优切分点,最优切分点对应的默认切分方向就是特征值缺失时默认的方向。

6. 总结

本文内容是作者对陈天奇博士论文《XGBoos:A Scalable Tree Boosting System》的理解,若有不同的想法,欢迎交流。

参考

陈天奇《XGBoos:A Scalable Tree Boosting System》

推荐阅读:

  1. XGBoost算法原理小结

  2. scikit-learn K近邻法类库使用小结

  3. 从0开始如何用一个月杀进机器学习比赛Top25%

  4. 2018年终精心整理|人工智能爱好者社区历史文章合集(作者篇)

  5. 2018年终精心整理 | 人工智能爱好者社区历史文章合集(类型篇)

公众号后台回复关键词学习

回复 免费                获取免费课程

回复 直播                获取系列直播课

回复 Python           1小时破冰入门Python

回复 人工智能         从零入门人工智能

回复 深度学习         手把手教你用Python深度学习

回复 机器学习         小白学数据挖掘与机器学习

回复 贝叶斯算法      贝叶斯与新闻分类实战

回复 数据分析师      数据分析师八大能力培养

回复 自然语言处理  自然语言处理之AI深度学习

推荐 0
本文由 人工智能爱好者社区 创作,采用 知识共享署名-相同方式共享 3.0 中国大陆许可协议 进行许可。
转载、引用前需联系作者,并署名作者且注明文章出处。
本站文章版权归原作者及原出处所有 。内容为作者个人观点, 并不代表本站赞同其观点和对其真实性负责。本站是一个个人学习交流的平台,并不用于任何商业目的,如果有任何问题,请及时联系我们,我们将根据著作权人的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。

0 个评论

要回复文章请先登录注册