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

相关文章

来自专栏跟着阿笨一起玩NET

C# 通过HttpWebRequest在后台对WebService进行调用

http://www.cnblogs.com/macroxu-1982/archive/2009/12/23/1630415.html

4012
来自专栏DT乱“码”

简单的考勤系统

连接数据库类 package com.lianrui.it; import java.sql.Connection; import java.sql.Driv...

4049
来自专栏c#开发者

jquery easyui datagrid mvc server端分页排序筛选的实现

1自定义一个ModelBinder public class filterRule { public string field { g...

4309
来自专栏xingoo, 一个梦想做发明家的程序员

windows程序设计-第四章 system1.c

/*---------------------------------------------------- SYSMETS1.C -- System M...

30911
来自专栏张善友的专栏

Using sqlite with .NET

The other day I found that there is a .NET wrapper for sqlite. sqlite is a very ...

2688
来自专栏码匠的流水账

聊聊spring cloud的AbstractLoadBalancingClient

本文主要研究一下spring cloud的AbstractLoadBalancingClient

1192
来自专栏葡萄城控件技术团队

Table-values parameter(TVP)系列之二: 利用DataTable将其作为参数传给SP

一,回顾         上一部分讲述了“在T-SQL中创建和使用TVP”,通过T-SQL建立如下的对象:         1)Tables ...

2189
来自专栏c#开发者

C# : row-clickable GridView and get and set gridview rows using JavaScript

Complete C# code: ---------------- using System; using System.ComponentModel; ...

3266
来自专栏菩提树下的杨过

winform中linkLabel的用法(示例)

private void Form1_Load(object sender, EventArgs e)         {             this...

2065
来自专栏菩提树下的杨过

MSDN官方的ASP.Net异步页面的经典示例代码

示例1.演示异步获取一个网址的内容,处理后显示在OutPut这一Label上 using System; using System.Web; using S...

2235

扫码关注云+社区