XGBoost 源码阅读笔记 ( 1 ) :代码逻辑结构

一. XGBoost 简介

XGBoost(eXtreme Gradient Boosting) 是基于 GB(Gradient Boosting)模型框架实现的一个高效,便捷,可扩展的一个机器学习库。该库先由陈天奇在 2014 年完成 v0.1 版本之后开源到 github[1]上,当前最新版本是 v0.6。目前在各类相关竞赛中都可以看到其出现的身影,如 kaggle[2],在 2015 年 29 个竞赛中,top3 队伍发表的解决方案中有 17 个方案使用了 XGBoost,而只有 11 个解决方案使用了深度学习;同时在 2015KDDCup 中 top10 队伍都使用了 XGBoost[3]。由于其与 GBDT(Gradient Boosting decision Tree)存在一定相似之处,网上也经常会有人将 GBDT 和 XGBoost 做个对比 [4]。最近正好读了陈天奇的论文《XGBoost: A Scalable Tree Boosting System》[3], 从论文中可以看出 XGBoost 新颖之处在于:

1、使用了正则化的目标函数,其加入的惩罚项会控制模型复杂度(叶子个数) 和叶子结点的得分权重

图 1-1 目标函数

2、使用 Shrinkage,通过一个因子η缩减每次最新生成树的权重,其目的是为了降低已生成的树对后续树的影响。

3、支持列(特征) 采样,该方式曾被用于随机森林。可以预防过拟合且加快模型训练速度。

4、并行计算。Boost 方式树是串行生成的,所以其在寻找树分裂点时候进行并行计算,加快模型训练速度。

在寻找分裂点时候论文中也提到多种方式:

1、基本枚举贪婪搜索算法。该方式将特征按其值排序之后,枚举每个特征值作为其分裂点并计算该分裂点的增益,然后选择最大增益的分裂点

2、近似贪婪搜索算法。该方式在寻找分裂点前会将所有的特征按其对应值进行排序后选择其百分位的点作为候选集合,在执行基本穷举贪婪搜索法。

3、加权分位数法(weighted quantile sketch)。该方法可以用于对加权数据的处理。

4、稀疏分裂点查找。可以加快模型对稀疏数据处理。

其与 GBDT 不同之一在于其对目标函数进行二阶泰勒展开,使用了二阶导数加快了模型收敛速度。总的来说 XGBoost 受到欢迎最重要的一个因素在于其快速的训练过程。

二. 源码下载及编译

Linux 上的源码下载和编译过程如下 [5]:

git clone --recursive https://github.com/dmlc/xgboost

cd xgboost

make

使用--recursive 命令是因为 XGBoost 使用了作者自己编写的分布式计算库,通过这个命令可以下载对应的库,编译好之后就可以开始阅读源码了,XGBoost 主要代码目录结构如下:

|--xgboost
    |--include
        |--xgboost        //定义了 xgboost 相关的头文件
    |--src  
        |--c_api               
        |--common        //一些通用文件,如对配置文件的处理
        |--data           //使用的数据结构,如 DMatrix
        |--gbm            //定义了若分类器,如 gbtree 和 gblinear
        |--metric          //定义评价函数
        |--objective       //定义目标函数
        |--tree            //对树的一些列操作

三. 源码逻辑结构

程序的执行入口在 cli_main.cc 文件中

//cli_main.cc

|--main()

    |--CLIRunTask()

        |--CLIParam::configure()

        |--switch(param.task)

            {  
                Case kTrain: CLITrain(param);break;

                Case KDumpModel: CLIDumpModel(param);break;

                Case KPredict: CLIPredict(param);break;

            }

在 main 函数中只调用了 CLIRunTask() 函数,在该函数中可以看出,程序通过函数 configure() 解析配置文件后,根据参数 task 选择对应的执行函数。我们这里主要看下训练函数 CLITrain();

//cli_main.cc

|--CLITrain()

    |--DMatrix::Load()

    |--Learner::Create()

    |--Learner::Configure()

    |--Learner::InitModel()

    |--for (int iter = 0; iter < max_iter;   iter)

        {

                Learner::UpdateOneIter();

                Learner::EvalOneIter();

        }

在 CLI 函数中, 先是将训练数据加载到内存中,然后开始创建 Learner 类实例, 接着调用 Learner 的 configure 函数配置参数,调用 InitModel() 初始化模型。然后就开始 XGboost 的 Boosting 训练,主要调用的是 Learner 的 UpdateOneIter() 函数。

//learner.cc

|--UpdateOneIter()

    |--learner::LazyInitDMatrix()

    |--learner::PredictRaw()

    |--ObjFunction::GetGradient()

    |--GradientBooster::DoBoost()

在每次迭代过程中,LazyInitDMatrix() 先初始化需要用到的数据结构。GetGradient() 获取目标函数的一阶导和二阶导,最后 DoBoost() 执行 Boost 操作生成一棵回归树。Class GradientBoost 是一个抽象类,他定义了 Gradient Boost 的抽象接口。其派生出的两个类 Class GBTree 和 Class GBLinear 分别对应着配置文件里面的参数"gbtree"和"gblinear", Class GBTree 主要使用的回归树作为其弱分类器,而 Class GBLinear 使用的是线性回归或逻辑回归作为其弱分类器。

Class GBTree 用的比较多,其 DoBoost() 函数执行的操作如下:

//gbtree.cc

|--GBTree::DoBoost()

    |--GBTree::BoostNewTrees()

        |--GBTree::InitUpdater()

        |--TreeUpdater::Update()

DoBoost() 调用了 BoostNewTrees() 函数。在 BoostNewTrees() 中先初始化了 TreeUpdater 实例,在调用其 Update 函数生成一棵回归树。TreeUpdater 是一个抽象类,根据使用算法不同其派生出许多不同的 Updater,这些 Updater 都在 src/tree 目录下。

|--src

    |--tree

        |--updater_basemaker-inl.h

        |--updater_colmaker.cc

        |--updater_skmaker.cc

        |--updater_refresh.cc

        |--updater_prune.cc

        |--updater_hismaker.cc

        |--updater_fast_hist.cc

文件 updater_basemaker-inl.h 中定义了一个派生自 TreeUpdater 的类 BaseMaker。Class ColMaker 使用的是基本枚举贪婪搜索算法,通过枚举所有的特征来寻找最佳分裂点;Class SkMaker 派生自 BaseMaker,使用近似的 sketch 方法寻找最佳分裂点;Class TreeRefresher 用于刷新数据集上树的统计信息和叶子值;Class TreePruner 是树的剪枝操作;Class HistMaker 使用的是直方图法,该方法在论文中并没有提到,所以也不是很清楚。

至此便可以大致了解 XGBoost 源码的逻辑结构,目前源码只看到这里。等看了各算法的具体实现之后再在后续文章中写其具体实现细节。

四. 参考文献

[1].https://github.com/dmlc/xgboost [2].https://www.kaggle.com [3].Tianqi Chen and Carlos Guestrin. XGBoost: A Scalable Tree Boosting System. In 22nd SIGKDD Conference on Knowledge Discovery and Data Mining, 2016 [4].https://www.zhihu.com/question/41354392 [5].http://xgboost.readthedocs.io/en/latest/build.html

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏一棹烟波

3DLut表实现log视频的后期调色原理

现在越来越多的视频或者图像拍摄设备支持log模式,比如大疆无人机的D-Log模式等等,log模式的起源和发展就不多做介绍,其在普通显示器上显示画面通常看起来是平...

1432
来自专栏温安适的blog

贪婪算法-单源最短路径

2855
来自专栏数据科学与人工智能

【Python环境】Python数据分析入门

本文来分享一下如何通过Python来开始数据分析。 具体内容如下: 数据导入 导入本地的或者web端的CSV文件; 数据变换; 数据统计描述; 假设检验 单样本...

23010
来自专栏超智能体

YJango:TensorFlow中层API Datasets+TFRecord的数据导入

2. 对接性:TensorFlow中也加入了高级API (Estimator、Experiment,Dataset)帮助建立网络,和Keras等库不一样的是:这...

50123
来自专栏量化投资与机器学习

【干货分享】Python数据结构与算法设计总结篇

1.Python数据结构篇 数据结构篇主要是阅读[Problem Solving with Python](http://interactivepython.o...

2545
来自专栏落影的专栏

Metal入门教程(六)边界检测

Metal入门教程(一)图片绘制 Metal入门教程(二)三维变换 Metal入门教程(三)摄像头采集渲染 Metal入门教程(四)灰度计算 Metal入门教程...

2359
来自专栏IT派

TensorFlow中的那些高级API

摘要: 在这篇文章中,我们将看到一个使用了最新高级构件的例子,包括Estimator(估算器)、Experiment(实验)和Dataset(数据集)。值得注...

4765
来自专栏机器学习算法全栈工程师

深入理解TensorFlow中的tf.metrics算子

本文翻译自Avoiding headaches with tf.metrics,原作者保留版权。

901
来自专栏Small Code

【TensorFlow】理解 Estimators 和 Datasets

Google 在 2017 年 9 月 12 号的博文 Introduction to TensorFlow Datasets and Estimators 中...

8748
来自专栏潇涧技术专栏

Python Algorithms - C4 Induction and Recursion and Reduction

Python算法设计篇(4) Chapter 4: Induction and Recursion and Reduction

913

扫码关注云+社区