作者:熊先明,腾讯 CDG 应用研究员

XGBoost是一种经典的集成式提升算法框架,具有训练效率高、预测效果好、可控参数多、使用方便等特性,是大数据分析领域的一柄利器。在实际业务中,XGBoost经常被运用于用户行为预判、用户标签预测、用户信用评分等项目中。XGBoost算法框架涉及到比较多数学公式和优化技巧,比较难懂,容易出现一知半解的情况。由于XGBoost在数据分析领域实在是太经典、太常用,最近带着敬畏之心,对陈天奇博士的Paper和XGBoost官网重新学习了一下,基于此,本文对XGBoost算法的来龙去脉进行小结。

本文重点解析XGBoost算法框架的原理,希望通过本文能够洞悉XGBoost核心算法的来龙去脉。对于XGBoost算法,最先想到的是Boosting算法。Boosting提升算法是一种有效且被广泛使用的模型训练算法,XGBoost也是基于Boosting来实现。Boosting算法思想是对弱分类器基础上不断改进提升,并将这些分类器集成在一起,形成一个强分类器。简而言之,XGBoost算法可以说是一种集成式提升算法,是将许多基础模型集成在一起,形成一个很强的模型。这里的基础模型可以是分类与回归决策树CART(Classification and Regression Trees),也可以是线性模型。如果基础模型是CART树(如图1所示),比如第1颗决策树tree1预测左下角男孩的值为+2,对于第1颗决策树遗留下来的剩余部分,使用第2颗决策树预测值为+0.9,则对男孩的总预测值为2+0.9=2.9。

XGBoost算法框架可以分为四个阶段来理解(如图2所示)。 第一个阶段,如何构造目标函数? 在进行优化求解时,首先需要构造目标函数,有了目标函数才能进行优化求解。这种思路和LR模型(Logistic Regression)是一致。在LR模型中,首先,对于回归问题构造平方项损失,对于分类问题构造最大似然损失作为目标函数,然后基于构造好的目标函数,才会考虑采用梯度下降算法进行优化求解,比如随机梯度下降、Mini-Batch批量梯度下降、梯度下降等。在这个阶段,我们可以得到XGBoost的基本目标函数结构。

第二个阶段,目标函数优化求解困难,如何对目标函数近似转换? 在第一个阶段得到的基本目标函数较为复杂,不是凸函数,没法使用连续性变量对目标函数直接优化求极值。因此,使用泰勒级数对目标函数进行展开,对目标函数规整、重组后,将目标函数转换为 关于预测残差的多项式函数

第三个阶段,如何将树的结构引入到目标函数中? 第二个阶段得到的多项式目标函数是一个复合函数。被预测的残差和模型复杂度还是未知的函数,需要对这两个函数进行参数化表示,即将决策树的结构信息通过数学符号表示出来。在第三个阶段,在树的形状确定情况下,可以优化求解出局部最优解。

第四个阶段,如何确定树的形状,要不要使用贪心算法? 如何在模型空间里面寻找最优的决策树形状,这是一个NP-Hard问题,我们很难对可能存在的树结构全部罗列出来,尤其在特征个数很多情况下。因此,在这里需要使用贪心算法来求得局部最优解。

1.如何构造目标函数?

当使用多棵树来预测时,假设已经训练了 棵树,则对于第 个样本的(最终)预测值为:

在公式1中, 表示对 个样本的预测值, 属于 集合范围内, 表示通过第 棵树对第 个样本进行预测,比如第1棵树预测值为 ,第2棵树预测值为 ,依次类推,将这些树的预测值累加到一起,则得到样本的最终预测值 。因此,如果要得到样本的最终预测值,需要训练得到 棵树。

如果要训练得到 棵树,首先需要构造训练的目标函数(如公式2所示)。在构建模型时, 不仅需要考虑到模型的预测准确性,还需要考虑到模型的复杂程度,既准确又简单的模型在实际应用中的效果才是最好的。因此,目标函数由两部分构成,第一部分表示损失函数,比如平方损失、交叉熵损失、折页损失函数等。第一部分表示 个样本总的损失函数值。因为在这里通过样本预测值 和样本真实值 的比较,可以计算出针对样本 的模型预测损失值 。这里可以暂时先不用考虑损失函数的具体形式,因为这里的损失函数,可以统一表示回归与分类问题的损失函数形式。

公式2的第二部分表示正则项,是用来控制模型的复杂度,模型越复杂,惩罚力度越大,从而提升模型的泛化能力,因为越复杂的模型越容易过拟合。XGBoost的正则化思路跟 模型中加 / 正则化思路一致,不同的地方在于正则化项具体物理含义不同。在这里 表示第 棵树的复杂度,接下来的问题是如何对树的复杂度进行参数化表示,这样后面才能进行参数优化。

在损失函数中 ,是有很多个模型(决策树)共同参与,通过叠加式的训练得到。如图2所示,训练完第一颗树 后,对于第一棵树没有训练好的地方,使用第二颗树 训练,依次类推,训练第 个棵树,最后训练第 颗树 。当在训练第 棵树时,前面的第1棵树到第 颗树是已知的,未知的是第 棵树,即 基于前面构建的决策树已知情况下,构建第 棵树

对于样本 ,首先初始化假定第0棵树为 ,预测值为 ,然后在第0棵树基础上训练第1棵树,得到预测值 ,在第1棵树基础上训练第2颗树,又可以得到预测值 ,依次类推,当训练第 棵树的时候,前面 棵树的总预测值为 ,递推训练具体过程如下所示:

根据XGBoost的递推训练过程,每棵决策树训练时会得到样本对应的预测值,根据样本预测值和真实值比较,可以计算得到模型预测损失值。又因为训练所得的每棵决策树都有对应的结构信息,因此可以得到每棵决策树的复杂度 。根据这些信息,可以对目标函数公式2进行简化,得到公式3。

在公式3中, 表示训练样本个数, 颗决策树累加的预测值, 颗决策树总的复杂度,在训练第 颗决策树时,这两个东西是已知的,即 在对目标函数进行求最小值优化时候, 为已知。因此,将常数项 拿掉,得到公式4作为XGBoost的目标函数。

2.目标函数优化困难,如何对函数近似转换?

在公式4中,已经得到了需要优化的目标函数,这个目标函数已经是简化后的函数。对于公式4,没法进行进一步优化。为了解决目标函数无法进行进一步优化, XGBoost原文是使用泰勒级数展开式技术对目标函数进行近似转换,即使用函数的1阶、2阶、3阶… 阶导数和对应的函数值,将目标函数进行多项式展开,多项式阶数越多,对目标函数的近似程度越高。这样做的好处是便于后面优化求解

,带入到目标函数公式4,得到基于二阶泰勒展开式的函数(如公式5所示),其中

在训练第 颗树时,目标函数(公式5)中, 是已知的。因此,可以将已知常数项 去掉,得到进一步简化后的目标函数(公式6)。 分别表示第 颗决策树的损失函数的1阶、2阶导数。 前面 颗决策树预测后,通过 将前面第 颗决策树的预测损失信息传递给第 颗决策树。在公式6中,第 颗树的预测函数 、树复杂度函数 对于我们来说,仍然都是未知的,因此需要将其参数化,通过参数形式表示出来,才能进行下一步的优化求解。

3.如何将树结构引入到目标函数中?

接下来的问题是如何对函数 进行参数化表示。首先,对于 叶子权重函数 ,如图4所示决策树,有1号、2号、3号叶子节点,这三个叶子节点对应的取值分别为15,12,20,在1号叶子节点上,有{1,3}两个样本,在2号叶子节点上,有{4}一个样本,在3号叶子节点上,有{2,5}两个样本。在这里,使用 来表示决策树的叶子权重值,三个叶子节点对应的叶子权重值为 。对于样本 落在决策树叶子节点的位置信息,使用 表示, 表示样本1落在第1个叶子节点上, 表示样本1落在第3个叶子节点上, 表示样本4落在第2个叶子节点上。

对于第 颗树的叶子权重函数 ,根据叶子权重值和样本所在叶子的位置信息,即可确定函数 。因此,我们引入决策树叶子权重值 和样本所在叶子的位置信息 两个变量,将其参数化表示成 。然而, 是一个函数,作为 的下标是不利于优化求解。因此,这里需要将 转化为 形式。 是根据样本落在叶子节点的位置信息直接遍历计算损失函数。 ** 是从叶子节点的角度,对每个叶子节点中的样本进行遍历计算损失函数,其中, 表示树的叶子节点**。假设 ,即 表示 有哪些样本落在第j个叶子节点上,比如 表示样本{1,3}落在叶子节点1上, 表示样本{4}落在叶子节点2上, 表示样本{2,5}落在叶子节点3上(如上文图4所示)。在这里强调一下,将 转换为 形式,是可以从数学公式推到得到(比如下式)。根据样本所在叶子节点位置,计算所有样本的一阶损失得到第一行等式,其中, 表示样本 的一阶损失, 表示样本 对应的叶子节点, 表示叶子节点 对应的叶子权重值。

对于 模型复杂度 表示第 颗树的复杂度。在决策树里面,如果要降低树的复杂度,在训练决策树时,可以通过叶子节点中样本个数、树的深度等控制决策树的复杂度。 在XGBoost中,是通过叶子节点个数、树的深度、叶子节点值来控制模型复杂度。XGBoost中的决策树是分类与回归决策树CART(Classification and Regression Trees)。由于CART是二叉树,控制叶子节点个数等同于控制了树的深度。因此,可以使用叶子节点个数来评估树的复杂度,即叶子节点个数越多(树的深度越深),决策树结构越复杂。对于叶子节点值,由于叶子节点值越大,相当于样本预测值分布在较少的几颗决策树的叶子节点上,这样容易出现过拟合。如果叶子节点值越小,相当于预测值分布在较多的决策树叶子节点上,每颗决策树参与预测其中的一小部分,过拟合的风险被分散。因此,叶子节点值越大,模型越容易过拟合,等同于决策树的复杂度越高。综合起来,如公式7所示,使用叶子节点个数 、叶子节点值 评估第 颗决策树的复杂度,其中 为超参数。如果希望叶子个数尽量少,则将 值尽量调大,如果希望叶子权重值尽量小,则将 尽量调大。

和公式7带入目标函数(公式6)中,可以得到参数化的目标函数(公式8)。在公式8中,在训练第 颗决策树时, 这两部分是已知, 为超参数。令 ,对公式8进行调整,此时得到 目标函数是关于 的一元二次抛物线,是目标函数最终的参数化表示形式。抛物线是有极值,对抛物线求极值可以直接套用抛物线极值公式,求解很方便。

基于公式8,对目标函数关于 求导,可以求得树的叶子节点 最优的权重值,如公式9所示。

将等式9带入到公式8中,计算得到树的目标损失值(如等式10),该等式表示决策树损失分数 ,分数越小,说明树的预测准确度越高、复杂度越低。

4.如何确定树的形状?

这里需要注意到一点, 树的叶子节点最优解 和损失函数极小值 是在树的形状给定后的优化求解。因此,如果要求得叶子节点最优解和损失函数极小值,首先需要确定树的形状。如何寻找树的形状?最直接的方式是枚举所有可能的形状,然后计算每种形状的损失函数 ,从中选择损失函数最小的形状作为模型训练使用。这样在树的形状确定后,就可以对叶子节点值和损失函数值进行优化求解。这种方式在实际应用中一般不会采用,因为当样本的特征集很大时,树的形状个数是呈指数级增加,计算这些形状树对应损失函数 需要消耗大量的计算资源。

为了寻找树的形状,我们一般使用贪心算法来简化计算,降低计算的复杂度。贪心算法是在局部寻找最优解,在每一步迭代时,选择能使当前局部最优的方向。XGBoost寻找树的形状的思路和传统决策树模型建立树的思路一致。比如传统决策树在进行节点分割时,基于信息熵,选择信息熵下降最大的特征进行分割;对于XGBoost树模型,基于损失函数,选择能让损失函数下降最多的特征进行分割。如图5所示,虚线框是已经构造好的树形状,如果需要在蓝色节点做进一步分裂,此时需要按照某种标准,选择最好的特征进行分割。在这里,XGBoost使用损失函数下降最大的特征作为节点分裂。

根据公式10,可以计算到蓝色节点在分裂前和分裂后的的损失函数值: 。两式相减,则得到特征如果作为分裂节点时,所能带来的损失函数下降值大小。因此,依据如下等式,选择能使 最大的特征作为分裂节点。

5.其它常见问题

关于XGBoost的常见经典问题,这类问题对于深入理解XGBoost模型很重要,因此,本文对此也进行了梳理小结。

(1) XGBoost为什么需要对目标函数进行泰勒展开?

根据XGBoost官网(如图6所示),目标损失函数之间存在较大的差别,比如平方损失函数、逻辑损失函数等。对目标函数进行泰勒展开,就是为了统一目标函数的形式,针对回归和分类问题,使得平方损失或逻辑损失函数优化求解,可以共用同一套算法框架及工程代码。另外,对目标函数进行泰勒展开,可以使得XGBoost支持自定义损失函数,只需要新的损失函数二阶可导即可,从而 提升算法框架的扩展性

相对于GBDT的一阶泰勒展开,XGBoost采用二阶泰勒展开,可以更精准的逼近真实的损失函数, 提升算法框架的精准性。另外,一阶导数描述梯度的变化方向,二阶导数可以描述梯度变化方向是如何变化的,利用二阶导数信息更容易找到极值点。因此,基于二阶导数信息能够让梯度收敛的更快,类似于牛顿法比SGD收敛更快。

(2) XGBoost如何进行采样?

XGBoost算法框架,参考随机森林的Bagging方法,支持样本采样和特征采样。由于XGBoost里没有交代是有放回采样,认为这里的样本采样和特征采样都是无放回采样。每次训练时,对数据集采样,可以增加树的多样性,降低模型过拟合的风险。另外,对数据集采样还能减少计算,加快模型的训练速度。在降低过拟合风险中,对特征采样比对样本采样的效果更显著。

样本采样(如图7所示),默认是 不进行样本采样。样本的采样的方式有两种,一种是认为每个样本平等水平,对样本集进行相同概率采样;另外一种认为每个样本是不平等,每个样本对应的一阶、二阶导数信息表示优先级,导数信息越大的样本越有可能被采到。

特征采样(如图8所示),默认 对特征不进行采样。对特征的采样方式有三种,第一种是在建立每棵树时进行特征采样;第二种特征采样范围是在第一种的基础上,对于树的每一层级(树的深度)进行特征采样;第三种特征采样范围是在第二种的基础上,对于每个树节点进行特征采样。这三种特征采样方式有串行效果。比如,当第一、二、三种的特征采样比例均是0.5时,如果特征总量为64个,经过这三种采样的综合效果,最终采样得到的特征个数为8个。

(3)XGBoost为什么训练会比较快?

XGBoost训练速度快,这个主要是工程实现优化的结果,具体的优化措施如下几点: 第一、支持并行化训练。XGBoost的并行,并不是说每棵树可以并行训练,XGBoost本质上仍然采用Boosting思想,每棵树训练前需要等前面的树训练完成后才能开始训练。XGBoost的并行,指的是 特征维度的并行。在训练之前,每个特征按特征值大小对样本进行预排序,并存储为Block结构(如图8所示),在后面查找特征分割点时可以重复使用,而且特征已经被存储为一个个Block结构,那么在寻找每个特征的最佳分割点时,可以利用多线程对每个Block并行计算。

第二、采用近似算法技术,得到候选分位点。在构造决策树分裂节点时,当采用 精确贪心算法 穷举计算每个特征下的所有特征值增益,如果特征个数多、特征取值大,会造成较大的计算量。当样本数据量大时,特征值无法完全加载到内存中,计算效率低。对于分布式数据集,同样会面临无法将特征值全部加载到本地内存的问题。因此,基于这两个现实问题,采用 近似直方图算法,将每个特征取值划分为常数个分位点,作为候选分割点,从中选择相对最优的分割点作为决策树分裂节点。

第三、缓存感知访问技术。对于有大量数据或者说分布式系统来说,不可能将所有的数据都放进内存里面。因此,需要将其放在外存上或者将数据分布式存储。但是会有一个问题,这样做每次都要从外存上读取数据到内存,这将会是十分耗时的操作。在XGBoost中,采用预读取的方式, 将下一块将要读取的数据预先放进内存里面。这个过程是多开了一个线程,该线程与训练的线程独立并负责数据读取。此外,还要考虑Block的大小问题。如果设置最大的Block来存储所有样本在 特征上的值和梯度,Cache未必能一次性处理如此多的梯度做统计。如果设置过小的Block-size,这样不能充分利用多线程的优势。这样会出现训练线程已经训练完数据,但是预读取线程还没把数据放入内存或者cache中。经过测试,Block-size设置为2^16个特征值是效果最好。

第四、Blocks核外计算优化技术。为了高效使用系统资源,对于机器资源,除了CPU和内存外,磁盘空间也可以利用起来处理数据。为了实现这个功能,XGBoost在模型训练时,会将数据分成多个块并将每个块存储在磁盘上。在计算过程中,使用独立的线程将Block预提取到主内存缓冲区,这样数据计算和磁盘读取可以同步进行,但由于IO非常耗时,所以还采用了两种技术来改进这种核外计算。

  • Block Compression:块压缩,并且加载到主内存时由独立的线程进行解压缩。
  • Block Sharding:块分片,即将数据分片到多个磁盘,为每个磁盘分配一个线程,将数据提取到内存缓冲区,然后每次训练线程的时候交替地从每个缓冲区读取数据,有助于在多个磁盘可用时,增加读取的吞吐量。

除了这些技术,XGBoost的特征采样技术也可以提升计算效率。如果设定特征采样比例colsample_by* < 1.0,则在选择最佳特征分割点作为分裂节点时,特征候选集变小,挑选最佳特征分割点时计算量降低。

(4)XGBoost如何处理缺失值问题?

XGBoost的一个优点是允许特征存在缺失值。对缺失值的处理方式如图9所示: 在特征 上寻找最佳分割点时, 不会对该列特征missing的样本进行遍历,而只对该特征值为non-missing的样本上对应的特征值进行遍历。对于稀疏离散特征,通过这个技巧可以大大减少寻找特征最佳分割点的时间开销。

在逻辑实现上,为了保证完备性,会将该特征值missing的样本分别分配到左叶子节点和右叶子节点,两种情形都计算一遍后,选择分裂后增益最大的那个方向(左分支或是右分支),作为预测时特征值缺失样本的默认分支方向。 如果在训练中没有缺失值而在预测中出现缺失,那么会自动将缺失值的划分方向放到右子节点。

(5)XGBoost和GBDT的区别是什么?

XGBoost和GBDT都是基于Boosting思想实现。XGBoost可以认为是在GBDT基础上的扩展。两者的主要不同如下: 基分类器:GBDT是以分类与回归决策树CART作为基分类器,XGBoost的基分类器不仅支持CART决策树,还支持线性分类器,此时XGBoost相当于带L1和L2正则化项的Logistic回归(分类问题)或者线性回归(回归问题)。 导数信息:GBDT在优化求解时,只是用到一阶导数信息,XGBoost对代价函数做了二阶泰勒展开,同时用到一阶和二阶导数信息。另外,XGBoost工具支持自定义代价函数,只要函数可以一阶和二阶求导即可。 正则项:XGBoost在代价函数里加入正则项,用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出的预测值的 模的平方和。正则项有利于降低模型的方差variance,使学习出来的模型更加简单,防止过拟合。GBDT的代价函数中是没有正则项。 缺失值处理:对于特征的取值有缺失的样本,XGBoost可以自动学习出它的分裂方向。 另外,XGBoost还做了其它工程优化,包括 特征值Block化、并行化计算特征增益、近似直方图算法、特征采样技术

(6)如何使用XGBoost进行模型训练?

在使用XGBoost前,可以根据官网说明文档进行安装(下面有链接,这里不赘述)。本文采用的数据集是Kaggle平台房价预测开源数据集(地址如参考文章8所示)。值得说明的一点,在进行模型训练前,一般需要做数据清洗、特征工程、样本划分、模型参数调优这些过程。针对这些过程,本文在这里不展开细讲。在进行模型训练前,本文已经完成数据清洗、特征工程、模型参数调优过程,并得到最终用于模型训练的样本集和最优模型参数。如下代码,是使用XGBoost进行模型训练过程。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#### 导入数据分析基础包 #####
import pandas as pd
import matplotlib
import numpy as np
import scipy as sp
import IPython
from IPython import display
import sklearn
import random
import time

#### 导入训练样本 #####
# 样本集特征
X_train=pd.read_csv('./final_train.csv',sep='\t',index=None)
# 样本集标签
y_train=pd.read_csv('./final_y_train.csv',sep='\t',index=None)

### 导入算法模型和评分标准 ####
from sklearn import svm, tree, linear_model, neighbors, naive_bayes, ensemble, discriminant_analysis, gaussian_process
from xgboost import XGBClassifier
#Common Model Helpers
from sklearn.preprocessing import OneHotEncoder, LabelEncoder
from sklearn import feature_selection
from sklearn import model_selection
from sklearn import metrics
#Visualization
import matplotlib as mpl
import matplotlib.pyplot as plt
import matplotlib.pylab as pylab
import seaborn as sns
from pandas.plotting import scatter_matrix
#Configure Visualization Defaults
#%matplotlib inline = show plots in Jupyter Notebook browser
%matplotlib inline
mpl.style.use('ggplot')
sns.set_style('white')
pylab.rcParams['figure.figsize'] = 12,8

from sklearn.tree import DecisionTreeRegressor
from sklearn.linear_model import LinearRegression, ElasticNet
from sklearn.ensemble import RandomForestRegressor
from sklearn.metrics import fbeta_score, make_scorer, r2_score ,mean_squared_error
from sklearn.linear_model import Lasso
from sklearn.svm import SVR
from xgboost import XGBRegressor
from sklearn.model_selection import KFold, cross_val_score, train_test_split
# 计算平方误差
def rmsle(y, y_pred):
    return np.sqrt(mean_squared_error(y, y_pred))

# 模型:Xgboost
from sklearn.model_selection import GridSearchCV
best_reg_xgb = XGBRegressor(learning_rate= 0.01, n_estimators = 5000
                max_depth= 4, min_child_weight = 1.5, gamma = 0,
                subsample = 0.7, colsample_bytree = 0.6,
                seed = 27)
best_reg_xgb.fit(X_train, y_train)
pred_y_XGB = best_reg_xgb.predict(X_train)

#
print (rmsle(pred_y_XGB, y_train))

6.小结

本文从目标函数构建、目标函数优化、树结构信息表示、树形状确定等四部分,对XGBoost算法框架进行解析。最后,针对XGBoost的常见问题进行小结。通过本文,洞悉XGBoost框架的底层算法原理。在用户行为预判、用户标签预测、用户信用评分等数据分析业务中,经常会使用到XGBoost算法框架。如果对XGBoost算法原理理解透彻,在实际业务中的模型训练过程中,有利于较好地理解模型参数,对模型调参过程帮助较大。

对于文章中表述不妥的地方,欢迎私信于我。

参考文章

(1).陈天奇XGBoost算法原著: https://dl.acm.org/doi/pdf/10.1145/2939672.2939785 (2).20道XGBoost面试题: https://cloud.tencent.com/developer/article/1500914 (3).XGBoost框架Parameters含义: https://xgboost.readthedocs.io/en/latest/parameter.html (4).XGBoost提升树官方介绍: https://xgboost.readthedocs.io/en/latest/tutorials/model.html (5).XGBoost官方论坛: https://discuss.xgboost.ai/ (6).GBDT提升树官方介绍: https://scikit-learn.org/stable/modules/ensemble.html#gradient-tree-boosting (7).XGBoost安装官网说明: [https://xgboost.readthedocs.io/en/latest/build.html](https://zshipu.com/t?url=https%3A%2