作者: 张磊 从事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》
推荐阅读:
公众号后台回复关键词学习
获取免费课程
回复 直播 获取系列直播课
回复 Python 1小时破冰入门Python
回复 人工智能 从零入门人工智能
回复 深度学习 手把手教你用 Python 深度学习
回复 机器学习 小白学数据挖掘与机器学习
回复 贝叶斯算法 贝叶斯与新闻分类实战
回复 数据分析师 数据分析师八大能力培养
回复 自然语言处理 自然语言处理之AI深度学习
本文由人工智能爱好者社区 创作,采用 知识共享署名-相同方式共享 3.0 中国大陆许可协议 进行许可。
转载、引用前需联系作者,并署名作者且注明文章出处。
本站文章版权归原作者及原出处所有 。内容为作者个人观点, 并不代表本站赞同其观点和对其真实性负责。本站是一个个人学习交流的平台,并不用于任何商业目的,如果有任何问题,请及时联系我们,我们将根据著作权人的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- 如何量化模块切分的合理性?
- DB 分库分表的基本思想和切分策略
- Linux 下使用 cut 命令,实现更好切分数据
- GoFrame v1.12 发布,数据库驱动开发、日志滚动切分等等新特性
- 出来混总是要还的-JS正则常用的有四种操作: 验证、切分、提取、替换
- 通俗易懂--决策树算法、随机森林算法讲解(算法+案例)
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
明解C语言(第3版)
[日] 柴田望洋 / 管杰、罗勇、杜晓静 / 人民邮电出版社 / 2015-11-1 / 79.00元
本书是日本的C语言经典教材,自出版以来不断重印、修订,被誉为“C语言圣经”。 本书图文并茂,示例丰富,第3版从190段代码和164幅图表增加至205段代码和220幅图表,对C语言的基础知识进行了彻底剖析,内容涉及数组、函数、指针、文件操作等。对于C语言语法以及一些难以理解的概念,均以精心绘制的示意图,清晰、通俗地进行讲解。原著在日本广受欢迎,始终位于网上书店C语言著作排行榜首位。一起来看看 《明解C语言(第3版)》 这本书的介绍吧!