"作者：熊先明，腾讯 CDG 应用研究员 XGBoost是一种经典的集成式提升算法框架，具有训练效率高、预测效果好、可控参数多、使用方便等特性，是大数据分析领域的一柄利器。在实际业务中，XGBoost经常被运用于用户行为预判、用户标签预测、用户信用评分等项目中。XGBoost算法框架涉及到比较多数学公 ...."

Fork me on GitHub

alg
本助手集算力、智能于一身，为您提供最精彩全面的人工智能技术资讯
XGBoost 机器学习 • 0 回帖 • 3K 浏览 • 3 年前

腾讯技术 | 数据分析利器：XGBoost 算法最佳解析

作者：熊先明，腾讯 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.如何构造目标函数？

当使用多棵树来预测时，假设已经训练了 $K$ 棵树，则对于第 $i$ 个样本的（最终）预测值为：

$\hat{y}_{i}=\sum_{k=1}^{K} f_{k}\left(\mathbf{x}_{i}\right), \quad f_{k} \in \mathcal{F} \tag {1}$

在公式1中， $\hat{y}_{i}$ 表示对 $i$ 个样本的预测值， $f_{k}$ 属于 $\mathcal{F}$ 集合范围内， $f_{k}\left(\mathbf{x}_{i}\right)$ 表示通过第 $k$ 棵树对第 $i$ 个样本进行预测，比如第1棵树预测值为 $f_{1}\left(\mathbf{x}_{i}\right)$ ，第2棵树预测值为 $f_{2}\left(\mathbf{x}_{i}\right)$ ，依次类推，将这些树的预测值累加到一起，则得到样本的最终预测值 $\hat{y}_{i}$ 。因此，如果要得到样本的最终预测值，需要训练得到 $K$ 棵树。

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

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

$obj=\underbrace{\sum_{i=1}^{n} l\left(y_{i},\hat{y}_{i}\right)}_{损失值}+\underbrace{\sum_{k=1} \Omega\left(f_{k}\right)}_{正则项} \tag {2}$

在损失函数中 $l\left(y_{i},\hat{y}_{i}\right)$ ，是有很多个模型（决策树）共同参与，通过叠加式的训练得到。如图2所示，训练完第一颗树 $f_{1}(x_i)$ 后，对于第一棵树没有训练好的地方，使用第二颗树 $f_{2}(x_i)$ 训练，依次类推，训练第 $K-1$ 个棵树，最后训练第 $K$ 颗树 $f_{k}(x_i)$ 。当在训练第 $K$ 棵树时，前面的第1棵树到第 $K-1$ 颗树是已知的，未知的是第 $K$ 棵树，即基于前面构建的决策树已知情况下，构建第 $K$ 棵树。

对于样本 $x_i$ ，首先初始化假定第0棵树为 $f_{0}(x_i)$ ，预测值为 $\hat{y}_{i}^{(0)}=0$ ，然后在第0棵树基础上训练第1棵树，得到预测值 $\hat{y}_{i}^{(1)}$ ，在第1棵树基础上训练第2颗树，又可以得到预测值 $\hat{y}_{i}^{(2)}$ ，依次类推，当训练第 $k$ 棵树的时候，前面 $k-1$ 棵树的总预测值为 $\hat{y}_{i}^{(k-1)}$ ，递推训练具体过程如下所示：

$\begin{aligned} & \hat{y}_{i}^{(0)}=0 \\ & \hat{y}_{i}^{(1)}=f_1(x_i)=\hat{y}_{i}^{(0)}+f_1(x_i) \\ & \hat{y}_{i}^{(2)}=f_1(x_i)+f_2(x_i)=\hat{y}_{i}^{(1)}+f_2(x_i) \\ & ...... \\ & \hat{y}_{i}^{(k)}=\underbrace{\left(f_1(x_i)+f_2(x_i)+......+f_{k-1}(x_i)\right)}_{前面k-1棵树对残差的预测值}+f_k(x_i)=\sum_{j=1}^{k-1} f_{j}(x_{i})+f_k(x_i) \\ & =\underbrace{\hat{y}_{i}^{(k-1)}}_{第k-1棵树的预测值}+f_k(x_i) \end{aligned} \\$

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

$obj=\sum_{i=1}^{n} l\left(y_{i},\hat{y}_{i}^{(k-1)}+f_k(x_i)\right)+\sum_{j=1}^{k-1} \Omega\left(f_{j}\right)+\Omega(f_{k}) \tag {3}$

在公式3中， $n$ 表示训练样本个数， $\hat{y}_{i}^{(k-1)}$ 为 $k-1$ 颗决策树累加的预测值， $\sum_{j=1}^{k-1} \Omega\left(f_{j}\right)$ 为 $k-1$ 颗决策树总的复杂度，在训练第 $k$ 颗决策树时，这两个东西是已知的，即在对目标函数进行求最小值优化时候， $\hat{y}_{i}^{(k-1)}$ 和 $\sum_{j=1}^{k-1} \Omega\left(f_{j}\right)$ 为已知。因此，将常数项 $\sum_{j=1}^{k-1} \Omega\left(f_{j}\right)$ 拿掉，得到公式4作为XGBoost的目标函数。

$Minimize_{Obj}=\sum_{i=1}^{n} l\left(y_{i},\hat{y}_{i}^{(k-1)}+f_k(x_i)\right)+\Omega(f_{k}) \tag {4}$

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

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

$TaylorExpression: f(x+\Delta x) \approx f(x)+f^{\prime}(x) \cdot \Delta x+\frac{1}{2} f^{\prime \prime}(x) \cdot \Delta x^{2} \\$

令 $f(x)=\ell(y_{i}, \underbrace{\hat{y}_{i}^{(k-1)}}_{x})$ ， $f(x+\Delta x)=\ell(y_{i}, \underbrace{\hat{y}_{i}^{(k-1)}}_{x}+\underbrace{\left.f_{k}\left(x_{i}\right)\right)}_{\Delta x}$ ，带入到目标函数公式4，得到基于二阶泰勒展开式的函数(如公式5所示)，其中 $g_i=\partial_{\hat{y}_{i}^{(k-1)}} \ell\left(y_{i}, \hat{y}_{i}^{(k-1)}\right)$ ， $h_i=\partial_{\hat{y}_{i}^{(k-1)}}^{2}\ell\left(y_{i}, \hat{y}_{i}^{(k-1))}\right)$ 。

$\begin{aligned} Obj_k & = \sum_{i=1}^{n} \ell(y_{i}, \underbrace{\hat{y}_{i}^{(k-1)}}_{x}+\underbrace{\left.f_{k}\left(x_{i}\right)\right)}_{\Delta x}+\Omega(f_{k}) \\ & = \sum_{i=1}^{n}\left[ \ell\left(y_{i}, \hat{y}_{i}^{(k-1)}\right) + \partial_{\hat{y}_{i}^{(k-1)}} \ell\left(y_{i}, \hat{y}_{i}^{(k-1)}\right) \cdot f_{k}\left(x_{i}\right)+\frac{1}{2} \partial_{\hat{y}_{i}^{(k-1)}}^{2}\ell\left(y_{i}, \hat{y}_{i}^{(k-1))}\right) \cdot f_{k}^{2}\left(x_{i}\right) \right]+\Omega(f_{k}) \\ & = \sum_{i=1}^{n}\left[ \underbrace{\ell\left(y_{i}, \hat{y}_{i}^{(k-1)}\right)}_{第k-1颗树预测损失值} + g_i \cdot f_{k}\left(x_{i}\right)+\frac{1}{2} h_i \cdot f_{k}^{2}\left(x_{i}\right) \right]+\Omega(f_{k}) \end{aligned} \tag {5}$

在训练第 $k$ 颗树时，目标函数（公式5）中， $\ell\left(y_{i}, \hat{y}_{i}^{(k-1)}\right)$ ， $g_i$ 、 $h_i$ 是已知的。因此，可以将已知常数项 $\ell\left(y_{i}, \hat{y}_{i}^{(k-1)}\right)$ 去掉，得到进一步简化后的目标函数（公式6）。 $g_i$ 、 $h_i$ 分别表示第 $k-1$ 颗决策树的损失函数的1阶、2阶导数。前面 $k-1$ 颗决策树预测后，通过 $g_i$ 、 $h_i$ 将前面第 $k-1$ 颗决策树的预测损失信息传递给第 $k$ 颗决策树。在公式6中，第 $k$ 颗树的预测函数 $f_{k}\left(x_{i}\right)$ 、树复杂度函数 $\Omega(f_{k})$ 对于我们来说，仍然都是未知的，因此需要将其参数化，通过参数形式表示出来，才能进行下一步的优化求解。

$Minimize_{obj} = \sum_{i=1}^{n} \left[ g_i \cdot f_{k}\left(x_{i}\right)+\frac{1}{2} h_i \cdot f_{k}^{2}\left(x_{i}\right) \right]+\Omega(f_{k}) \tag {6}$

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

接下来的问题是如何对函数 $f_{k}\left(x_{i}\right)$ 、 $\Omega(f_{k})$ 进行参数化表示。首先，对于叶子权重函数 $f_{k}\left(x_{i}\right)$ ，如图4所示决策树，有1号、2号、3号叶子节点，这三个叶子节点对应的取值分别为15，12，20，在1号叶子节点上，有{1,3}两个样本，在2号叶子节点上，有{4}一个样本，在3号叶子节点上，有{2,5}两个样本。在这里，使用 $w$ 来表示决策树的叶子权重值，三个叶子节点对应的叶子权重值为 $(w_1、w_2、w_3)=(15,12,20)$ 。对于样本 $x$ 落在决策树叶子节点的位置信息，使用 $q(x)$ 表示， $q(x_1)=1$ 表示样本1落在第1个叶子节点上， $q(x_2)=3$ 表示样本1落在第3个叶子节点上， $q(x_4)=2$ 表示样本4落在第2个叶子节点上。

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

$\begin{aligned} \sum_{i=1}^{n} g_i \cdot f_{k}(x_i) & = g_1\cdot w_{q(x_1)}+g_2\cdot w_{q(x_2)}+g_3\cdot w_{q(x_3)}+g_4\cdot w_{q(x_4)}+g_5\cdot w_{q(x_5)} \\ & = \underbrace{(g_1\cdot w_1 + g_3\cdot w_1)}_{第1个叶子样本的1阶损失} + \underbrace{g_4\cdot w_2}_{第2个叶子样本的1阶损失} + \underbrace{(g_2\cdot w_3+g_5\cdot w_3)}_{第3个叶子样本的1阶损失} \\ & = \sum_{j=1}^{T} \left(\sum_{i \in I_{j}} g_{i}\right) \cdot w_j \end{aligned} \\$

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

$\Omega\left(f_{k}\right)=\gamma T+\frac{1}{2} \lambda \sum_{j=1}^{\top} w_{j}^{2} \tag {7}$

将 $f_k(x_i)=w_{q(x_i)}$ 和公式7带入目标函数（公式6）中，可以得到参数化的目标函数（公式8）。在公式8中，在训练第 $k$ 颗决策树时， $\sum_{i \in I_{j}} g_{i}$ 和 $\sum_{i \in I_{j}} h_{i}$ 这两部分是已知， $\gamma,\lambda$ 为超参数。令 $G_j=\sum_{i \in I_{j}} g_{i}$ ， $H_j=\sum_{i \in I_{j}} h_{i}$ ，对公式8进行调整，此时得到目标函数是关于 $w_j$ 的一元二次抛物线，是目标函数最终的参数化表示形式。抛物线是有极值，对抛物线求极值可以直接套用抛物线极值公式，求解很方便。

$\begin{aligned} Minimize_{obj} & = \sum_{i=1}^{n} \left[ g_i \cdot w_{q(x_i)}+\frac{1}{2} h_i \cdot w_{q(x_i)}^2 \right]+\gamma T+\frac{1}{2} \lambda \sum_{j=1}^{\top} w_{j}^{2} \\ & = \sum_{j=1}^{T}\left[\left(\sum_{i \in I_{j}} g_{i}\right) \cdot \omega_{j}+\frac{1}{2}\left(\sum_{i \in I_{j}} h_{i}+\lambda \right) \cdot \omega_{j}^{2} \right]+\gamma \cdot T \\ & = \sum_{j=1}^{T}\left[G_j \cdot \omega_{j}+ \frac{1}{2}\left(H_j+\lambda \right)\cdot \omega_{j}^{2} \right]+\gamma \cdot T \end{aligned} \tag {8}$

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

$\begin{aligned} w_{j}^{*} & = -\frac{\sum_{i \in I_{j}} g_{i}}{\sum_{i \in I_{j}} h_{i}+\lambda} \\ & = -\frac{G_j} {H_j+\lambda} \end{aligned} \tag {9}$

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

$\begin{aligned} obj^{*} & = -\frac{1}{2} \sum_{j=1}^{T} \frac{\left(\sum_{i \in I_{j}} g_{i}\right)^{2}}{\sum_{i \in I_{j}} h_{i}+\lambda}+\gamma T \\ & = -\frac{1}{2} \sum_{j=1}^{T} \frac{G_j^{2}}{H_j+\lambda}+\gamma T \end{aligned} \tag {10}$

4.如何确定树的形状？

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

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

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

$obj_{old}^{*}= -\frac{1}{2} \left[\frac{g_7+g_8}{h_7+h_8+\lambda}+ \frac{g_1+g_2+...+g_6}{h_1+h_2+...+g_6+\lambda} \right] + 2\gamma \\$ $obj_{new}^{*}= -\frac{1}{2} \left[\frac{g_7+g_8}{h_7+h_8+\lambda}+ \frac{g_1+g_3+g_5}{h_1+h_3+g_5+\lambda} + \frac{g_2+g_4+g_6}{h_2+h_4+g_6+\lambda}\right] + 3\gamma \\$ $obj_{old}^{*}-obj_{new}^{*}= \frac{1}{2} \left[ \frac{G_L^2}{H_L+\lambda}+\frac{G_R^2}{H_R+\lambda} - \frac{(G_L+G_R)^2}{(H_L+H_R+\lambda)^2} \right] - \gamma \\$

5.其它常见问题

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

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

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

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

(2) XGBoost如何进行采样？

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

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

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

（3）XGBoost为什么训练会比较快？

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

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

第三、缓存感知访问技术。对于有大量数据或者说分布式系统来说，不可能将所有的数据都放进内存里面。因此，需要将其放在外存上或者将数据分布式存储。但是会有一个问题，这样做每次都要从外存上读取数据到内存，这将会是十分耗时的操作。在XGBoost中，采用预读取的方式，将下一块将要读取的数据预先放进内存里面。这个过程是多开了一个线程，该线程与训练的线程独立并负责数据读取。此外，还要考虑Block的大小问题。如果设置最大的Block来存储所有样本在 $k$ 特征上的值和梯度，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所示：在特征 $k$ 上寻找最佳分割点时，不会对该列特征missing的样本进行遍历，而只对该特征值为non-missing的样本上对应的特征值进行遍历。对于稀疏离散特征，通过这个技巧可以大大减少寻找特征最佳分割点的时间开销。

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

（5）XGBoost和GBDT的区别是什么？

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

（6）如何使用XGBoost进行模型训练？

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

#### 导入数据分析基础包 #####
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 (8).Kaggle开源数据：https://www.kaggle.com/c/house-prices-advanced-regression-techniques

本文地址：https://www.6aiq.com/article/1607644635233
本文版权归作者和AIQ共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出

腾讯技术 | 数据分析利器：XGBoost 算法最佳解析

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

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

4.如何确定树的形状？

5.其它常见问题

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

(2) XGBoost如何进行采样？

（3）XGBoost为什么训练会比较快？

（4）XGBoost如何处理缺失值问题？

（5）XGBoost和GBDT的区别是什么？

（6）如何使用XGBoost进行模型训练？

6.小结

参考文章

相关帖子

随便看看

腾讯技术 | 数据分析利器：XGBoost 算法最佳解析