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 删除。

编辑于

我来说两句

2 条评论
登录 后参与评论

相关文章

来自专栏人工智能LeadAI

基于Tensorflow实现多层感知机网络MLPs

github:https://github.com/sladesha/deep_learning

812
来自专栏专知

如何在TensorFlow上高效地使用Dataset

【导读】近日,机器学习工程师Francesco Zuppichini发表一篇教程,讲解了在TensorFlow中高效地输入数据集的方法,作者首先抛弃了feed-...

8945
来自专栏人工智能LeadAI

第一章 | 使用python机器学习

python经常作为机器学习的首选,有一个统计,50%以上的机器学习开发者使用python。在学习机器学习之前需要熟悉以下几个python模块: numpy P...

3725
来自专栏深度学习入门与实践

【深度学习系列】PaddlePaddle之数据预处理

  上篇文章讲了卷积神经网络的基本知识,本来这篇文章准备继续深入讲CNN的相关知识和手写CNN,但是有很多同学跟我发邮件或私信问我关于PaddlePaddle如...

2178
来自专栏Deep Learning 笔记

MNIST__数字识别__SOFTMAX

本次MNIST的手写数字识别未采用input_data.py文件,想尝试一下用原始的数据集来运行这个DEMO。

1011
来自专栏应兆康的专栏

100个Numpy练习【4】

翻译:YingJoy 网址: https://www.yingjoy.cn/ 来源: https://github.com/rougier/numpy-100...

4058
来自专栏海天一树

按出现次数从少到多的顺序输出数组中的字符串(纠正)

问题 有一个数组为{"Liu Yi", "Chen Er", "Zhang San", "Chen Er", "Chen Er", "Li Si", "Li S...

3147
来自专栏人工智能LeadAI

存储Tensorflow训练网络的参数

训练一个神经网络的目的是啥?不就是有朝一日让它有用武之地吗?可是,在别处使用训练好的网络,得先把网络的参数(就是那些variables)保存下来,怎么保存呢?其...

3038
来自专栏人工智能LeadAI

pytorch入门教程 | 第一章:Tensor

1 pytorch安装 安装pytorch之前,需要安装好python,还没安装过python的宝宝请先移步到廖雪峰的python教程,待安装熟悉完之后,再过来...

3159
来自专栏用户2442861的专栏

用python简单处理图片(4):图像中的像素访问

前面的一些例子中,我们都是利用Image.open()来打开一幅图像,然后直接对这个PIL对象进行操作。如果只是简单的操作还可以,但是如果操作稍微复杂一些,就...

482

扫码关注云+社区