XGBoost之切分点算法
欢迎关注天善智能，我们是专注于商业智能BI，人工智能AI，大数据分析与挖掘领域的垂直社区，学习，问答、求职一站式搞定！
对商业智能BI、大数据分析挖掘、机器学习，python，R等数据领域感兴趣的同学加微信：tstoutiao，邀请你进入数据爱好者交流群，数据爱好者们都在这儿。
作者：张磊 从事AI医疗算法相关工作
个人微信公众号：
机器学习算法那些事（微信ID：zl13751026985）
前言
上文介绍了XGBoost的算法原理并引出了衡量树结构好坏的打分函数（目标函数），根据特征切分点前后的打分函数选择最佳切分点，但并未对节点的切分算法作详细的介绍。本文详细的介绍了XGBoost的切分点算法，内容参考陈天奇博士《XGBoost ：A scalable Tree Boosting System》，后台回复XGBoost，获取论文下载链接。
目录
并行原理
切分点算法之贪婪算法
切分点算法之分位点算法
切分点算法之权重分位点算法
稀疏数据的切分算法
总结
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》
推荐阅读：
XGBoost算法原理小结
scikit-learn K近邻法类库使用小结
从0开始如何用一个月杀进机器学习比赛Top25%
2018年终精心整理|人工智能爱好者社区历史文章合集（作者篇）
2018年终精心整理 | 人工智能爱好者社区历史文章合集（类型篇）
公众号后台回复关键词学习
回复 免费 获取免费课程
回复 直播 获取系列直播课
回复 Python 1小时破冰入门Python
回复 人工智能 从零入门人工智能
回复 深度学习 手把手教你用Python深度学习
回复 机器学习 小白学数据挖掘与机器学习
回复 贝叶斯算法 贝叶斯与新闻分类实战
回复 数据分析师 数据分析师八大能力培养
回复 自然语言处理 自然语言处理之AI深度学习