NO.46.tip： XGBoost

背景

XGBoost基础

XGBoost是 eXtreme Gradient Boosting 的缩写。XGBoost 是提升算法的一种，提升算法是将许多弱分类器集成在一起，形成一个强分类器。因为 XGBoost 是一种提升树模型，所以它是将许多树模型集成在一起，形成一个强分类器。其中用到的树模型是 CART 回归树。XGBoost 在 GBDT 的基础上进行了改进，使之更强大，适用于更大的范围。

XGBoost 是一个开源软件库，为 C++、Java、Python、R、Julia、Perl 和 Scala 而设计安装。XGBoost 一般和 sklearn 一起使用，但是由于 sklearn 中没有集成 XGBoost，所以需要单独下载和安装。

XGBoost 是一个可扩展、可移植和分布式的梯度提升（GBM、GBRT、GBDT）库。它可以在单机运行，也可以在分布式处理框架 Apache Hadoop、Apache Spark、Apache Flink 和 Dask 上运行。XGBoost 算法可以给预测模型带来能力的提升。最近，作为许多机器学习竞赛获胜团队的首选算法，它获得了很多人的青睐和关注。它有如下优势：

• 正则化。XGBoost 以"正则化提升"（regularized boosting）技术而闻名。XGBoost 在代价函数里加入了正则项，用于控制模型的复杂度。正则项里包含树的叶子节点个数，以及每个叶子节点上输出得分的 L2 模的平方和。从权衡偏差与方差的角度来讲，正则项降低了模型的方差，使学习出来的模型更加简单，可防止过拟合，这也是 XGBoost 优于传统 GBDT 的一个特性。
• 并行处理。XGBoost 工具支持并行。众所周知，提升算法是顺序处理的，这意味着提升传统 GBDT 的一个模型是串行处理的。注意，XGBoost 的并行并不是树粒度的并行，需要一次迭代完才能进行下一次迭代（包含在第 t 次迭代的代价函数里）。XGBoost 的并行是在特征粒度上的，也就是说每一棵树的构造都依赖于前一棵树。

我们知道，决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点）。XGBoost 在训练之前预先对数据进行排序，然后保存为块结构，后面的迭代中重复使用这个结构，大大减小了计算量。这个块结构也使得并行成为可能。在进行迭代中重复便用这个结构大大减小计算量。这个块结构也使得并行成为可能。

源与流

XGBoost核心原理

XGBoost 既是对提升树模型的创新，也是对提升树模型的一种工程优化实现，特别是针对并行和分布式环境下的加速实现。因此，对于它的核心原理，也需要从两方面认识。

作为一种提升树，XGBoost 模型的假设空间也是一系列 CART 树的集成，输出为：

模型参数为 K 棵树：

$$F=\{f_1,f_2,\cdots ,f_K\}$$

$${\hat{y}}_i=\sum _{k=1}^K{f}_k(x_i),f_i\in F$$

XGBoost 的目标函数和一般监督模型一样，包括损失函数部分 L 和正则化项部分 Ω。损失函数衡量模型在训练数据上的拟合程度，正则化项衡量模型的复杂度。

对于 XGBoost，假设给定数据集 D 中有 n 个样本，每个样本有 m 维特征，通过训练数据集 D，我们得到 K 棵树。这 K 棵树累加的值就是预测值 ŷ。

XGBoost 的目标函数为：

$$Obj(x_i)=\sum _{i=1}^{n}L(y_i,{\hat{y}}_i)+\sum _{j=1}^K\Omega (f_j)$$

其中，L(y_i, ŷ_i) 是损失函数，根据具体的问题，损失函数可以做不同的设定，例如，回归是 MSE，分类是交叉熵。损失函数 L(y_i, ŷ_i) 与传统提升树的损失函数一样，回归可以使用平方误差，分类可以使用对数损失。

损失函数及正则化项

由于 XGBoost 是一个加法模型，因此，在 K 次迭代中，可以将树展开为每棵树预测值的累加，即：

$${\hat{y}}_i^{(K)}=\sum _{j=1}^K{f}_j(x_i)=f_1(x_i)+f_2(x_i)+\cdots +f_{K-1}(x_i)+f_K(x_i)$$

这与传统提升树一样。在 K 次迭代中，可以将树展开。

节点的分裂时，需要计算每个特征的增益，最终选择增益最大的特征进行分裂，那么各个特征的增益计算就可以多线程并行。

• 特征的增益计算有了一个全新的维度，所以我们的处理不会受到任何限制。
• 灵活性。XGBoost 支持用户自定义目标函数和评估函数，只要目标函数二阶可导即可。它对模型增加了一个新的维度，用户需要提供一阶和二阶导数信息。XGBoost 对代价函数进行二阶泰勒展开，可以同时使用一阶和二阶导数，并且支持自定义代价函数，只要函数可一阶和二阶求导。
• 缺失值处理。对于特征的值有缺失的样本，XGBoost 可以自动学习出分裂方向。XGBoost 内置了处理缺失值的规则。用户需要提供一个和其他样本不同的值，然后把它作为一个参数放进去，并且会学习未来遇到缺失值时的处理方法。
• 剪枝。XGBoost 先从顶到底建立所有可以建立的子树，再从底到顶反向进行剪枝，比起 GBM，这样不容易陷入局部最优解。
• 内置交叉验证。XGBoost 允许在每一轮提升迭代中使用交叉验证，因此可以方便地获得最优提升迭代次数，而 GBM 使用网格搜索，只能检测有限个值。

继续第 K 棵树的时候，目标函数 obj 可以表示为：

$$ob{j}^{(K)}(x_i)=L+\Omega =\sum _{i=1}^{n}L(y_i,{\hat{y}}_i^{(K-1)}+f_K(x_i))+\sum _{j=1}^K\Omega (f_j)+\Omega (f_K)$$

XGBoost 中的基学习器都是 CART 决策树。对于每一棵 CART 树，每个叶子节点都有一个预测值（这里也称为叶子节点索引）：q 表示每棵树的结构：它将样本映射到相应的叶子节点索引；T 表示一棵树的叶子节点个数；每个叶子节点的预测值（权重值）为 w_i。因此，一棵 CART 树可以表示为：

$$f_i=\{w_q(x_i)|q:R^m\to T,w\in R^T\}$$

由上式已知项，则目标函数 obj 变为：

$$ob{j}^{(K)}(x_i)=\sum _{i=1}^{n}L(y_i,{\hat{y}}_i^{(K-1)}+f_K(x_i))+\Omega (f_K)$$

对公式作变量 x 进行二阶泰勒展开得到近似目标函数：

$$ob{j}^{(K)}(x_i)\approx \sum _{i=1}^n[L(y_i,{\hat{y}}_i^{(K-1)})+{\partial }_{{\hat{y}}_i^{(K-1)}}L(y_i,{\hat{y}}_i^{(K-1)})f_K(x_i)+\frac{1}{2}{\partial }_{{\hat{y}}_i^{(K-1)}}^{2}L(y_i,{\hat{y}}_i^{(K-1)})f_K^2(x_i)]+\Omega (f_K)$$

其中，

$$g_i={\partial }_{{\hat{y}}_i^{(K-1)}}L(y_i,{\hat{y}}_i^{(K-1)}),h_i={\partial }_{{\hat{y}}_i^{(K-1)}}^{2}L(y_i,{\hat{y}}_i^{(K-1)})$$

需要指出的是 L(y_i, ŷ_i^(K-1)) 是常数，最小化时可以不考虑，那么优化目标简化为：

$${\widetilde{obj}}^{(K)}(x_i)=\sum _{i=1}^n[g_i{f}_K(x_i)+\frac{1}{2}{h}_i{f}_K^2(x_i)]+\Omega (f_K)$$

Ω(f) 用于抑制模型的复杂度和防止过拟合，与一棵决策树的叶子节点个数 T 和每个叶子节点的预测值 w_j 有关，定义如下：

$$\Omega (f)=\gamma \cdot T+\frac{1}{2}\lambda \cdot \sum _{j=1}^T{w}_j^2$$

正则化项值越小，（决策树）模型的复杂度越低，泛化能力越强。

定义 I_j = {i | q(x_i) = j} 作为叶子节点 j 上的实例集合，我们可以重写上式，因为预测的结果就是落到叶子节点的输出，这里每个叶子节点都有一个权重，即输出 w_j，因此，约简后的目标函数为：

$${\widetilde{obj}}^{(K)}(x_i)=\sum _{j=1}^T[(\sum _{i\in I_j}{g}_i)w_j+\frac{1}{2}(\sum _{i\in I_j}{h}_i+\lambda )w_j^2]+\gamma \cdot T$$

因为 f_i = {w_q(x_i) | q: R^m → T, w ∈ R^T}，所以 f_K(x_i) = w_j | q(x_i) = j，替换 f_K 得到上式。

对于固定的树结构 q(x)，我们可以求导，然后取零计算得到叶子节点 j 的最优权重 w_j，令

$$G_j=\sum _{i\in I_j}{g}_i,H_j=\sum _{i\in I_j}{h}_i，则$$

$${\widetilde{obj}}^{(K)}(x_i)=\sum _{j=1}^T[G_j{w}_j+\frac{1}{2}(H_j+\lambda )w_j^2]+\gamma \cdot T$$

针对 w_j 求导，得 G_j + (H_j + λ)w_j = 0，因此，w_j = -G_j/(H_j + λ)，计算这棵树的目标最优值：

$${\widetilde{obj}}^{(K)}(x_i)=-\frac{1}{2}\sum _{j=1}^T[\frac{G_j^2}{H_j+\lambda }]+\gamma \cdot T$$

这样叶子节点的权值就求出来了，进而可以求出目标函数，类似于用不纯度（基尼系数）来衡量一棵树的质量，如图 6.3 所示的公式。公式视作衡量函数来测量树结构 q 的质量，类似于用不纯度（基尼系数）来衡量一棵树的优劣程度。接下来，我们引用 XGBoost 原论文里的图例展示如何计算一棵树的分值。

决策树的构造过程

一棵树的生成是由一个节点一分为二，然后不断分裂最终形成整棵树。那么，树如何分裂就成为接下来要探讨的关键。XGBoost 的作者在其原始论文中给出了一种分裂节点的方法：枚举所有不同树结构的贪心法。具体做法分为两步：对于每个可行划分，计算划分后的目标函数 obj(f)，然后选择 obj(f) 降低最小的分割点。首先枚举所有的分割点，计算信息增益最大的划分，之后继续同样的操作直到满足条件（比如满足阈值或者无法划分）：

$$Gain(\varphi )=-\frac{1}{2}\sum _{j=1}^T\frac{(G_{Lj}+G_{Rj}{)}^2}{H_{Lj}+H_{Rj}+\lambda }+\gamma -(-\frac{1}{2}\sum _{j=1}^T\frac{G_{Lj}^2}{H_{Lj}+\lambda }+\gamma -\frac{1}{2}\sum _{j=1}^T\frac{G_{Rj}^2}{H_{Rj}+\lambda }+\gamma )$$

其中，G_L 和 G_R 分别表示左叶子和右叶子节点的 G_j 值，分裂前的目标函数是

$$-\frac{1}{2}\sum _{j=1}^T\frac{G_j^2}{H_j+\lambda }+\gamma$$

分裂后的目标函数是

$$-\frac{1}{2}\sum _{j=1}^T\frac{(G_{Lj}+G_{Rj}{)}^2}{H_{Lj}+H_{Rj}+\lambda }+\gamma$$

这个公式的计算结果通常用于在实践中评估候选分裂节点是否应该分裂，我们应尽量找到最大的特征值划分点。

Gain 是计算出来的收益，这个公式跟 ID3 算法采用信息熵计算增益、C4.5 算法使用信息增益率计算增益和 CART 算法采用基尼指数计算增益是一致的，都是用分裂前的某种值减去分裂后的某种值，从而得到增益。关于分割点的详细算法请参见论文 "XGBoost: A scalable tree boosting system"。

为了限制树的生长，我们可以加入阈值，当增益大于阈值时才让节点分裂。上式中的 γ 即阈值，它是正则项里叶子节点数 T 的系数，所以 XGBoost 在优化目标函数的同时相当于做了剪枝。另外，上式中还有一个系数 λ，是正则项里关于叶子节点的 L2 模平方的系数，它对叶子节点的复杂度做了平滑，也起到了防止过拟合的作用，这个是传统 GBDT 不具备的特性。

XGBoost 系统设计及其并行化加速

XGBoost 的系统特性体现在多个方面，下文将进行简要分析。

分块并行

在建树的过程中，最耗时的是找最优切分点。分块并行结构加速了找切分点的过程，只需要在建树前排序一次，保存到块结构中，后面节点分裂时直接根据索引得到梯度信息，大大减少了计算量。

此过程值得注意的有以下几点：

• 对特征进行预排序，以分块并行的结构存于内存中。
• 每个特征会存储指向样本梯度统计值的索引，方便计算一阶和二阶导数值。
• 每个块结构中都采用稀疏矩阵存储格式进行存储，一个块存储一个或多个特征值。
• 缺失特征值将不进行排序。

重复上述操作，直到划分好所有节点为止，这样就建立了一棵 CART 分类决策树。

1. 基本的精确贪婪算法

基本的精确贪婪算法（basic exact greedy algorithm）单机版本的 XGBoost 支持这种算法，如下所示。

算法：分割查找的精确贪婪算法

输入：当前节点的实体集合 $I$。

输入：特征维度 $d$。

$$\text{gain}\leftarrow 0$$

$$G\leftarrow \sum _{i\in I}{g}_i,H\leftarrow \sum _{i\in I}{h}_i$$

$$\text{for }k=1\text{ to }m\text{ do}$$

$$G_L\leftarrow 0,H_L\leftarrow 0$$

$$\text{for }j\text{ in sorted}(I,\text{by }{X}_{jk})\text{ do}$$

$$G_L\leftarrow G_L+g_j,H_L\leftarrow H_L+h_j$$

$$G_R\leftarrow G-G_L,H_R\leftarrow H-H_L$$

$$\text{score}\leftarrow \max \left(\text{score},\frac{G_L^2}{H_L+\lambda }+\frac{G_R^2}{H_R+\lambda }-\frac{G^2}{H+\lambda }\right)$$

$$\text{end}$$

$$\text{end}$$

输出：以最高分数分割。

为了高效找到最佳分裂节点，算法必须先将该特征的所有取值进行排序，之后按顺序取值并计算增益，其时间复杂度是 O(N_u)，N_u 是这个特征不同取值的个数。

2. 近似算法

对于每个特征，近似算法（approximate algorithm）只考察分位点，从而减少计算复杂度，如下所示。

算法：分割查找的近似算法

假设 $S_k=\{S_{k1},S_{k2},\cdots ,S_{kl}\}$ 为特征 $k$ 上的百分比。

$$\text{for }k:=1\text{ to }m\text{ do}$$

$$\text{Propose }{S}_k=\{S_{k1},S_{k2},\cdots ,S_{kl}\}\text{ by percentiles on feature }k$$

$$\text{Proposal can be per tree (global), or per split (local)}$$

$$\text{end}$$

$$\text{for }k:=1\text{ to }m\text{ do}$$

$$G_{kv}\leftarrow \sum _{j\in \{j\mid S_{kv}\le X_{jk}<S_{k,v+1}\}}{g}_j$$

$$H_{kv}\leftarrow \sum _{j\in \{j\mid S_{kv}\le X_{jk}<S_{k,v+1}\}}{h}_j$$

$$\text{end}$$

按照与上一节相同的步骤，只在假设的分割中找到最大分数。

基本的精确贪婪算法可以非常有效地找到分裂节点，但是当数据量很大时，数据不可能一次性全部读入内存中；在分布式计算中，也不可能使用所有数据来计算分裂节点之后的树结构得分。为解决这个问题，研究者设计了近似算法。近似算法首先按照特征取值中统计分布的一些百分位点确定候选分裂点，然后算法将连续的值映射到桶中，接着汇总统计数据在候选节点中找到最佳节点。

XGBoost 采用的近似算法主要有两个变体：

• 全局：学习每棵树前就提出候选切分点，并在每次分裂时都采用这种分割。
• 局部：每次分裂前重新提出候选切分点。

找到其中最大的信息增益的划分方法如下：

$$Gain=max\{Gain,\frac{G_1^2}{H_1+\lambda }+\frac{G_{23}^2}{H_{23}+\lambda }-\frac{G_{123}^2}{H_{123}+\lambda }-\gamma ,\frac{G_{12}^2}{H_{12}+\lambda }+\frac{G_3^2}{H_3+\lambda }-\frac{G_{123}^2}{H_{123}+\lambda }-\gamma \}$$

然而，这种划分分位点的方法在实际中可能效果不是很好，所以 XGBoost 采用加权分位数略图方法做近似划分，其中以二阶导数值作为权重。

3. 加权分位数略图算法

对于加权分位数略图算法（weighted quantile sketch algorithm），可以先令集合

$$D_k=\{(x_{1k},h_1),(x_{2k},h_2),\cdots ,(x_{nk},h_n)\}$$

表示第 $k$ 个特征的每个训练样本的二阶梯度统计，其中 $h_{ik}$ 可以被看作第 $i$ 个样例的第 $k$ 个特征值的权重。我们可以定义一个排序函数 $r_k:R\to [0,+\infty )$，并根据这个值来取值：

$$r_k(z)=\frac{1}{{\sum }_{(x,h)\in D_k}h}\sum _{(x,h)\in D_k,x<z}h$$

上式表示特征值 $k$ 小于 $z$ 的实例比例。目标是寻找候选分裂点集 $\{S_{k1},S_{k2},\cdots ,S_{kl}\}$。

该排序函数的输入为某个特征值 $z$，计算的是该特征所有可取值中小于 $z$ 的特征值的总权重占所有可取值的总权重的比例，输出为一个比例值。

其中，$s_{k1}$ 是特征 $k$ 的取值 $x_{ik}$ 中最小的值，$s_{kl}$ 是特征 $k$ 的取值 $x_{ik}$ 中最大的值。$\epsilon$ 是近似因子或者称为扫描步幅，按照步幅 $\epsilon$ 挑选出分位略图序列中的最小值和最大值，组成候选点集，这意味着有大概 $1/\epsilon$ 个候选点。这里每个数据点的权重看成是相应的 $h_i$。

至于为什么用 $h_i$ 加权，可把目标函数整理成以下形式：

$${\widetilde{obj}}^{(K)}(x_i)=\sum _{i=1}^n\left[g_i{f}_K(x_i)+\frac{1}{2}{h}_i{f}_K^2(x_i)\right]+\Omega (f_K)+\gamma \cdot T$$

$$=\sum _{i=1}^n\left[\left(\sum _{i\in I_j}{g}_i\right)w_j+\frac{1}{2}\left(\sum _{i\in I_j}{h}_i+\lambda \right)w_j^2\right]+\gamma \cdot T$$

$$=\sum _{i=1}^n\left[g_i{f}_i(x_i)+\frac{1}{2}{h}_i{f}_i^2(x_i)\right]+\Omega (f_i)+constant$$

$$=\sum _{i=1}^n\frac{1}{2}{h}_i{\left[f_i(x_i)-\left(-\frac{g_i}{h_i}\right)\right]}^2+\Omega (f_i)+constant$$

最后的代价函数就是一个加权平方误差，权值为 $h_i$，标签为 $-g_i/h_i$，所以可以将特征 $k$ 的取值看成对应的 $h_i$。

4. 带缺失值时的分裂方法

在很多现实业务数据中，训练数据可能很稀疏。造成这个问题的原因可能是存在大量缺失值，或采用了独热编码。

XGBoost 算法能够处理稀疏模式数据，其通过在树节点中添加默认划分方向的方法来解决这个问题。

当有缺失值时，系统将实例分到默认方向的叶子节点。每个分支都有两个默认方向，最佳缺失方向可以从训练数据中学习到。算法如下所示。

算法：稀疏感知分裂查找

输入：当前节点的实体集合 $I$。

输入：$I_k\leftarrow \{i\in I\mid x_{ik}\ne \text{missing}\}$。

输入：特征维度 $d$。

$$\text{gain}\leftarrow 0$$

$$G\leftarrow \sum _{i\in I}{g}_i,H\leftarrow \sum _{i\in I}{h}_i$$

$$\text{for }k=1\text{ to }m\text{ do}$$

（同精确贪婪算法内层循环，略）

$$\text{end}$$

同样适用于其他适当的设置，只将未丢失条目的统计信息收集到桶中。

• 对于列的块，并行的切分点查找算法很容易实现。
• 这种块结构存储的特征之间相互独立，方便计算机进行并行计算。在对节点进行分裂时需要选择增益最大的特征，这时各个特征的增益计算可以同时进行，这也是 XGBoost 能够实现分布式或者多线程计算的原因。

缓存优化

虽然分块并行设计可以减少节点分裂时的计算量，但其按特征大小顺序存储，相应样本的梯度信息是分散的，这会造成内存的不连续访问，降低 CPU cache 命中率。解决办法是为每个线程分配一个连续的缓冲区，将需要的梯度信息存放在缓冲区中，这样就实现了从非连续空间到连续空间的转换，提高了算法效率。

缓存优化方法还可以适当调整块大小，这也有助于缓存优化的实现。

核外块计算

当数据量过大时，无法将数据全部加载到内存中，只能先将无法加载到内存中的数据暂存到硬盘中，直到需要时再进行加载计算，而这种操作必然涉及因内存与硬盘速度不同而造成的资源浪费和性能瓶颈。为了解决这个问题，XGBoost 独立一个线程专门用于从硬盘读入数据，以实现处理数据和读入数据同时进行。

此外，XGBoost 还采用了两种方法来降低硬盘读写的开销：

• 块压缩：对块进行按列压缩，并在读取时进行解压。
• 块拆分：将每个块存储到不同的磁盘中，从多个磁盘读取可以增加吞吐量。

并行化加速设计

XGBoost 的并行指的是特征维度的并行。树节点在进行分裂时，需要计算每个特征的每个分割点对应的增益，即用贪心算法枚举所有可能的分割点。当数据无法一次载入内存或者在分分布式情况下，贪心算法的效率就会变得很低，所以XGBoost还提出了一种可并行的近似直方图算法，用于高效地生成候选的分割点。这种算法把连续的浮点特征值离散化成 k 个整数，同时构造一个宽度为 k 的直方图。在遍历数据的时候，将离散化后的值作为索引在直方图中累积统计量。遍历一次数据后，直方图累积了需要的统计量，然后根据直方图的离散值，遍历寻找最优的分割点。

此过程值得注意的有以下几点：

• 分块并行：训练前每个特征按特征值进行排序并存储为块结构，后面查找特征分割点时重复使用，并且支持并行查找每个特征的分割点。
• 候选分位点：每个特征采用常数个分位点作为候选分割点。
• CPU cache 命中优化：使用缓存预取的方法，对每个线程分配一个连续的缓冲区，读取每个块中样本的梯度信息并存入连续的缓冲区中。
• 块处理优化：块预先放入内存并按列解压缩，通过将块划分到不同硬盘来提高吞吐。

其他特性

XGBoost 的其他特性还包括：

• 列采样：XGBoost 借鉴了随机森林的做法，支持列采样，不仅能降低过拟合，还能减少计算。
• 缩减：这相当于学习率而言的。XGBoost 在进行完一次迭代后，会将叶子节点的权重乘上该系数，主要是为了削弱每棵树的影响，为后面的学习树提供更大的学习空间。
• 支持自定义损失函数（需二阶可导）。

XGBoost与传统提升树的比较

除了算法上与传统 GBDT 有一些不同外，XGBoost 还在工程实现上做了大量的优化。总的来说，两者之间的区别和联系可以总结成以下几个方面。

• GBDT 是机器学习算法，XGBoost 是该算法的工程实现。
• 在使用 CART 作为基分类器时，XGBoost 显式地加入了正则项来控制模型的复杂度，有利于防止过拟合，从而提高模型的泛化能力。
• GBDT 在模型训练时只使用代价函数的一阶导数信息，XGBoost 对代价函数进行二阶泰勒展开，可以同时使用一阶和二阶导数，并且支持自定义代价函数，只要函数可一阶和二阶求导。
• 传统的 GBDT 采用 CART 作为基分类器，XGBoost 支持多种类型的基分类器，比如线性分类器。这个时候 XGBoost 相当于带 L1 和 L2 正则化项的逻辑斯蒂回归（分类问题）或者线性回归（回归问题）。
• 传统的 GBDT 在每轮迭代时使用全部数据，XGBoost 则采用与随机森林相似的策略，支持对数据进行采样。
• 分裂节点的特征分割点选取使用近似算法——可并行的近似直方图算法。树节点在分裂节点的特征分割点和损失分割实现动态生长，结构分数代替了回归树的误差平方和。分裂节点时，需要计算每个特征的每个分割点对应的增益，即用贪心算法枚举所有可能的分割点。若数据无法一次载入内存或者在分布式情况下，贪心算法的效率就会变得很低，所以 XGBoost 还提出了一种可并行的近似直方图算法，用于高效地生成候选的分割点，同时减小内存消耗。
• XGBoost 可以处理稀疏、缺失数据（节点分裂算法能自动利用特征的稀疏性），可以学习出缺失值的处理策略。传统的 GBDT 无法对缺失值进行处理，XGBoost 能够自动学习出缺失值的处理策略。
• XGBoost 采用列采样（传统 GBDT 没有）和缩减（传统 GBDT 也有）。

XGBoost的缺点

XGBoost 的缺点如下：

• 每次迭代训练时需要读取整个数据集，耗时耗内存；每轮迭代时，都需要遍历整个训练数据多次。如果把整个训练数据装进内存则会限制训练数据的大小；如果不装进内存，反复读写训练数据又会消耗非常大的时间。
• 使用基本的精确贪婪算法计算最佳分裂节点时需要保存数据的特征值，并预先对特征值进行排序，排序之后还要保存排序结果，费时又费内存。
• 计算分裂节点时需要遍历每一个候选节点，然后计算分裂之后的信息增益，比较费时。
• 在数据分割点上，由于 XGBoost 对不同的数据特征使用预排序算法，而不同特征的排序是不同的，所以分裂时需要对每个特征单独做依次分割，时间上也有较大的开销，需要遍历（#data × #features）次才能将数据分裂到左右子节点上。
• 由于采用预排序处理数据，在寻找特征分裂点时会产生大量的 cache 随机访问。预先设置好树的深度之后，每一棵树都需要生长到所设置的深度，这样有些树在某次分裂之后可能没有提升，但仍然会继续划分树枝，导致无用功，并且非常耗时。
• 尽管使用了局部近似计算，但是处理粒度还是太细了，计算量巨大，内存占用巨大，易产生过拟合。
• 需要遍历数据集。
• 虽然利用预排序和近似算法可以降低寻找最佳分裂点的计算量，但在节点分裂过程中仍需要遍历数据集。
• 预排序过程的空间复杂度过高，不仅需要存储特征值，还需要存储特征对应样本的梯度统计值的索引，相当于消耗了两倍的内存。