专栏首页程飞翔的专栏XGBoost 源码阅读笔记 ( 1 ) :代码逻辑结构
原创

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 条评论
登录 后参与评论

相关文章

  • XGBoost 源码阅读笔记(2):树构造之 Exact Greedy Algorithm

    本篇将继续向大家介绍 XGBoost 源码是如何构造一颗回归树,不过在分析源码之前,还是有必要先和大家一起推导下 XGBoost 的目标函数。

    程飞翔
  • linux环境下R语言的安装运行以及程序包的下载

    R是一种多功能型统计绘图软件,可以方便的编写函数、建立模型,具有良好的扩展性。目前在R网站上约有2400个程序包,涵盖了基础统计学、社会学、经济学、生态学、空间...

    HUBU生信
  • JavaScript 的闭包用于什么场景

    本文翻译自 MDN ( Mozilla Developer Network ): 原文地址:MDN 译文地址:shixinzhang 的博客 词法作用域 考虑如...

    张拭心 shixinzhang
  • Kotlin Vocabulary | 揭秘协程中的 suspend 修饰符

    Kotlin 协程把 suspend 修饰符引入到了我们 Android 开发者的日常开发中。您是否好奇它的底层工作原理呢?编译器是如何转换我们的代码,使其能够...

    Android 开发者
  • Eclipse下maven使用嵌入式(Embedded)Neo4j创建Hello World项目

    代码可以在github上看到:https://github.com/neo4j/neo4j/blob/2.3.3/community/embedded-exam...

    用户3148308
  • Neo4j批量插入(Batch Insertion)

    代码可以在github上看到:https://github.com/neo4j/neo4j/blob/2.3.3/community/embedded-exam...

    用户3148308
  • 通信之道:4G大变局(上)

    新时代新杀入的力量是Intel,它是IT界人士,就是搞计算机互联网那边的。有一个无人不晓的东西叫作Wi-Fi,它是也IT 界搞出来的东西。在Wi-Fi 取得了成...

    博文视点Broadview
  • 《重构-代码整洁之道TypeScript版》第4天

    描述?:你有一个复杂的if..else if ...else语句,可以把它从复杂的代码中提取出来

    疯狂的技术宅
  • 前端测试题:关于新特性Generator函数的描述,错误的是?

    形式上,Generator 函数是一个普通函数,但是有两个特征。一是,function关键字与函数名之间有一个星号;二是,函数体内部使用yield表达式,定义不...

    舒克
  • 产业安全专家谈 | 主机安全为什么是企业上云的「必需品」?

    随着近年来5G、云计算、AI等技术的成熟和普及,企业上云已经成为了当下的主流趋势。年初疫情所催生的海量云复工需求,叠加云计算被正式划入“新基建”范围的利好信息,...

    腾讯安全

扫码关注云+社区

领取腾讯云代金券