Max Blog

树模型第三节，机器学习两大主流模型，LightGbm和XGBoost

1 XGBOOST

1 介绍

XGBoost属于boosting方法，具有速度快和效果好的特点。相对之前的GBDT等，XGB具有以下4个创新点：

• 我们设计和构建高度可扩展的端到端提升树系统。

• 我们提出了一个理论上合理的加权分位数略图。 (这个东西就是推荐分割点的时候用，能不用遍历所有的点，只用部分点就行，近似地表示，省时间。)

• 我们引入了一种新颖的稀疏感知算法用于并行树学习。( 令缺失值有默认方向。)

• 我们提出了一个有效的用于核外树形学习的缓存感知块结构。 (用缓存加速寻找排序后被打乱的索引的列数据的过程。)

2 算法原理

2.1 目标函数

模型的目标函数由损失函数L和抑制模型复杂度的正则项$\Omega$共同组成：

$O b j=\sum_{i=1}^{n} l\left(\hat{y}_{i}, y_{i}\right)+\sum_{t=1}^{k} \Omega\left(f_{t}\right)$

因为boosting模型使用前向算法，以第t步为例，目标函数可以写为：

$\begin{aligned} O b j^{(t)} &=\sum_{i=1}^{n} l\left(y_{i}, \hat{y}_{i}^{t}\right)+\sum_{i=1}^{t} \Omega\left(f_{i}\right) \\ &=\sum_{i=1}^{n} l\left(y_{i}, \hat{y}_{i}^{t-1}+f_{t}\left(x_{i}\right)\right)+\sum_{i=1}^{t} \Omega\left(f_{i}\right) \end{aligned}$

此时对目标函数进行最优化，相当于求解$f(x_i)$。

根据泰勒公式，把函数$f(x+\Delta x)$在点x处进行泰勒展开，可得：

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

因为$\hat{y}_{i}^{t}=\hat{y}_{i}^{t-1}+f_{t}\left(x_{i}\right)$，把$\hat{y}_{i}^{t-1}$看成x,$f_{t}\left(x_{i}\right)$看成$\Delta x$,目标函数可以写成：

$O b j^{(t)}=\sum_{i=1}^{n}\left[l\left(y_{i}, \hat{y}_{i}^{t-1}\right)+g_{i} f_{t}\left(x_{i}\right)+\frac{1}{2} h_{i} f_{t}^{2}\left(x_{i}\right)\right]+\sum_{i=1}^{t} \Omega\left(f_{i}\right)$

其中，$g_i$为损失函数一阶导，$h_i$为损失函数二阶导。这里是对$\hat{y}_{i}^{t-1}$求导。

以平方损失函数为例：

$\begin{array}{c} \sum_{i=1}^{n}\left(y_{i}-\left(\hat{y}_{i}^{t-1}+f_{t}\left(x_{i}\right)\right)\right)^{2} \\ g_{i}=\frac{\partial\left(\hat{y}^{t-1}-y_{i}\right)^{2}}{\partial \hat{y}^{t-1}}=2\left(\hat{y}^{t-1}-y_{i}\right) \\ h_{i}=\frac{\partial^{2}\left(\hat{y}^{t-1}-y_{i}\right)^{2}}{\hat{y}^{t-1}}=2 \end{array}$

在第t步时，$l\left(y_{i}, \hat{y}_{i}^{t-1}\right)$是常数，因此目标函数可以写成

$O b j^{(t)} \approx \sum_{i=1}^{n}\left[g_{i} f_{t}\left(x_{i}\right)+\frac{1}{2} h_{i} f_{t}^{2}\left(x_{i}\right)\right]+\sum_{i=1}^{t} \Omega\left(f_{i}\right)$

因此，只需要求出每一步损失函数的一阶导和二阶导，然后最优化目标函数，就可以得到f(x)，最后根据加法模型得到一个整体数值。其中，因为$\hat{y}_{i}^{t-1}$在前一步已知，所以对应的求导值为常数。

2.2 基于决策树的目标函数

以决策树为例，介绍xgb基于决策树的目标函数

决策树定义：$f_{t}=w_{q(x)}$,x为某个样本，q(x)表示该样本在哪个叶子节点上，$w_q$表示叶子节点的取值$w$。这里$w_{q(x)}$表示了每个样本的预测值w。

决策树的复杂度由叶子数T组成，叶子节点应该数量较少，且不应该含有较高的权重，因此正则项定义：

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

即决策树模型的复杂度由生成的所有决策树的叶子节点数量，和所有节点权重所组成的向量的L2范式共同决定。

对目标函数进行公式推导：

$\begin{aligned} O b j^{(t)} & \approx \sum_{i=1}^{n}\left[g_{i} f_{t}\left(x_{i}\right)+\frac{1}{2} h_{i} f_{t}^{2}\left(x_{i}\right)\right]+\Omega\left(f_{t}\right) \\ &=\sum_{i=1}^{n}\left[g_{i} w_{q\left(x_{i}\right)}+\frac{1}{2} h_{i} w_{q\left(x_{i}\right)}^{2}\right]+\gamma T+\frac{1}{2} \lambda \sum_{j=1}^{T} w_{j}^{2} \\ &=\sum_{j=1}^{T}\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 T \end{aligned}$

为了简化表达，定义$G_{j}=\sum_{i \in I_{j}} g_{i}, \quad H_{j}=\sum_{i \in I_{j}} h_{i}$，则目标函数简化成：

$O b j^{(t)}=\sum_{j=1}^{T}\left[G_{j} w_{j}+\frac{1}{2}\left(H_{j}+\lambda\right) w_{j}^{2}\right]+\gamma T$

对最后一棵树的叶子结点$w_j$求一阶导，令其等于0，叶子节点j的对应权值为：

$w_{j}^{*}=-\frac{G_{j}}{H_{j}+\lambda}$

目标函数最终简化为：

$O b j=-\frac{1}{2} \sum_{j=1}^{T} \frac{G_{j}^{2}}{H_{j}+\lambda}+\gamma T$

以上图为例，对每个节点的每个样本，计算其一阶导$g_i$和二阶导$h_i$，然后计算每个节点的$G_i$和$H_i$,然后再遍历决策树的各个节点，就可以求得目标函数的值。

2.3 子采样和权值收缩

对于shrinkage 和 column subsampling，就是相当于学习速率和对于列的采样骚操作。调低eta能减少个体的影响，给后续的模型更多学习空间。对于列的重采样，根据一些使用者反馈，列的subsampling比行的subsampling效果好，列的subsampling也加速了并行化的特征筛选。这里就跟RF差不多吧，不过论文没说具体怎么column subsampling，API里有个参数能控制subsampe的比例。

3 切分算法

Xgboost支持两种分裂节点的方法：贪心算法和近似算法

3.1 贪心算法

算法步骤：

1. 从深度为0的树开始，对每个叶节点枚举所有的可用特征；
2. 针对每个特征，把属于该节点的训练样本根据该特征值进行升序排列，通过线性扫描的方式来决定该特征的最佳分裂点，并记录该特征的分裂收益；
3. 选择收益最大的特征作为分裂特征，用该特征的最佳分裂点作为分裂位置，在该节点上分裂出左右两个新的叶节点，并为每个新节点关联对应的样本集
4. 回到第 1 步，递归执行到满足特定条件为止

计算特征的分裂收益

假设对于某一节点，分裂前的目标函数为：

$O b j_{1}=-\frac{1}{2}\left[\frac{\left(G_{L}+G_{R}\right)^{2}}{H_{L}+H_{R}+\lambda}\right]+\gamma$

分裂后，目标函数为：

$O b j_{2}=-\frac{1}{2}\left[\frac{G_{L}^{2}}{H_{L}+\lambda}+\frac{G_{R}^{2}}{H_{R}+\lambda}\right]+2 \gamma$

基于以上两式，分裂后的收益为：

$\text { Gain }=\frac{1}{2}\left[\frac{G_{L}^{2}}{H_{L}+\lambda}+\frac{G_{R}^{2}}{H_{R}+\lambda}-\frac{\left(G_{L}+G_{R}\right)^{2}}{H_{L}+H_{R}+\lambda}\right]-\gamma$

该特征收益也可作为特征重要性输出的重要依据

计算示例

上图为选择最佳分割点的示例。从左向右做一遍扫描，就可以枚举出所有分割的梯度以及对应的$G_L$和$G_R$。然后根据上一步的公式计算收益，最终选择最佳收益。

节点分裂后，未必会比分裂前收益好。因此会通过一个阈值来决定是否需要在当前节点分割。如果收益小于阈值，则不进行分割。

伪代码

3.2 近似算法

贪婪算法可以的到最优解，但当数据量太大时则无法读入内存进行计算，近似算法主要针对贪婪算法这一缺点给出了近似最优解。

该算法会首先根据特征分布的分位数提出候选划分点，然后将连续型特征映射到由这些候选点划分的桶中，然后聚合统计信息找到所有区间的最佳分裂点。

在提出候选切分点时有两种策略：

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

我们可以看到 Global 策略在候选点数多时（eps 小）可以和 Local 策略在候选点少时（eps 大）具有相似的精度。此外我们还发现，在 eps 取值合理的情况下，分位数策略可以获得与贪婪算法相同的精度。

伪代码

3.3 加权分位数缩略图(Weighted Quantile Sketch)

分位数的计算理论上是按照个数进行划分，以三分位数为例，9个样本的话划分点分别在第3和第4个数据之间以及第6和第7个数据之间。

加权分位数缩略图不是直接按样本个数进行分位，而是以二阶导数值$h_{i}$作为样本的权重进行划分。

对目标函数进行整理：

$\begin{aligned} O b j^{(t)} & \approx \sum_{i=1}^{n}\left[g_{i} f_{t}\left(x_{i}\right)+\frac{1}{2} h_{i} f_{t}^{2}\left(x_{i}\right)\right]+\sum_{i=1}^{t} \Omega\left(f_{i}\right) \\ &=\sum_{i=1}^{n}\left[g_{i} f_{t}\left(x_{i}\right)+\frac{1}{2} h_{i} f_{t}^{2}\left(x_{i}\right)+\frac{1}{2} \frac{g_{i}^{2}}{h_{i}}\right]+\Omega\left(f_{t}\right)+C \\ &=\sum_{i=1}^{n} \frac{1}{2} h_{i}\left[f_{t}\left(x_{i}\right)-\left(-\frac{g_{i}}{h_{i}}\right)\right]^{2}+\Omega\left(f_{t}\right)+C \end{aligned}$

可以看出$h_{i}$就是平方损失函数中样本的权重。

对于样本权值相同的数据集来说，找到候选分位点已经有了解决方案（GK 算法），但是当样本权值不一样时，论文给出了一个 Weighted Quantile Sketch 算法。

3.4 感知稀疏值

XGBoost 在构建树的节点过程中只考虑非缺失值的数据遍历，而为每个节点增加了一个缺失方向，当样本相应的特征值缺失时，可以被归类到缺失方向上，最优的缺失方向可以从数据中学到。

最优缺失方向学习思路：分别枚举特征缺失的样本归为左右分支后的增益，选择增益最大的枚举项即为最优缺失方向。

伪代码

算法在构建树的过程中只考虑了特征未缺失的样本，算法所需比那里的样本量减少。因此速度比basic算法要快。

4 工程实现

4.1 块结构设计

XGBoost 在训练之前对根据特征对数据进行了排序，然后保存到块结构中，并在每个块结构中都采用了稀疏矩阵存储格式（Compressed Sparse Columns Format，CSC）进行存储，后面的训练过程中会重复地使用块结构，可以大大减小计算量。

• 每一个块结构包括一个或多个已经排序好的特征；
• 缺失特征值将不进行排序；
• 每个特征会存储指向样本梯度统计值的索引，方便计算一阶导和二阶导数值；

主要目的是方便计算，特征之间独立计算，使得xgboost可以分布式或多线程计算。

4.2 缓存访问优化算法

特征值通过索引访问样本梯度统计值的设计会导致访问操作的内存空间不连续，这样会造成缓存命中率低，从而影响到算法的效率。

XGBoost 提出了缓存访问优化算法：为每个线程分配一个连续的缓存区，将需要的梯度信息存放在缓冲区中，这样就是实现了非连续空间到连续空间的转换，提高了算法效率。

4.3 核外块计算

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

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

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

5 总结

5.1 优点

1. 精度高

   相较GBDT，引入了二阶导。增加了精度

2. 更灵活

   基分类器除了支持CART树，还支持线性分类器

   可以自定义损失函数

3. 正则化

   通过控制模型复杂度，防止过拟合。

4. Shrinkage

   类似learning rate，削弱了每棵树的影响

5. 列抽样

   降低过拟合，减少计算

6. 缺失值处理优化

   稀疏感知算法，加快了分裂速度

7. 可并行化

   块结构可以支持并行计算

5.2 缺点

1. 计算量

   计算节点分裂过程中，任然需要遍历数据集

2. 内存消耗

   预排序过程空间复杂度高，需要存储特征值和对应样本的梯度统计值的索引。内存消耗两倍

2 LGBM

论文摘要

GBDT是一个很流行的算法，虽然其扩展算法，像XGBoost引入了一些工程上的优化，但是特征维度还是很高，当数据量很大时，效率不够高。原因是对于每一个特征，这些算法都需要扫描所有数据的可能划分点的信息增益，这非常耗时。

为了解决这个问题，提出了Gradient-based One-Side Sampling (GOSS)和Exclusive Feature Bundling (EFB)两个方法。

GOSS，排除了大部分梯度小的数据，只使用剩下的数据来计算信息增益。

EFB，打包了互斥的特征，减少了特征的数量。

LightGBM = GBDT + GOSS _ EFB， 实验效果表明lgbm速度更快，同时精度不会降低。

1 介绍

GBDT效率低的主要问题：传统的实现需要对每个特征扫描所有的数据，对所有可能的划分点来估计信息增益。因此，计算复杂度与特征数和实例数成正比。这使得处理大数据的时候非常耗时。

之前尝试的解决思路：一个直接的想法是减少数据数量和特征数量。但是这很困难，例如如何做数据采样就不是很清楚。有一些工作根据权重采样数据来加速训练，但是不能直接套用到GBDT上，因为GBDT没有任何采样权重。

lgbm使用的两种方法：

Gradient-based One-Side Sampling (GOSS)：单边梯度抽样算法。虽然没有数据权重，但是在计算信息增益时，不同梯度的数据扮演着不同的角色。根据信息增益的定义，较大梯度的数据贡献更多的信息增益。因此我们应该尽量保留梯度大的数据（大于预定义的阈值，或者在高百分比上），随即丢掉梯度小的数据。在相同的目标采样率，尤其是信息增益值有很大范围情况下，这个处理可以比均匀随机采样能得到更好的增益估计。

Exclusive Feature Bundling (EFB)：互斥特征捆绑算法。通常在实际应用中，有大量的特征，特征空间非常稀疏，这让我们可以设计一个基本没有损失的方法来减少有效特征数量。特别是，在稀疏特征空间，很多特征是（基本）互斥的，也就是说他们很少同时取到非0值。这样的例子包括one-hot特征。我们可以安全的把这些互斥的特征打包。最后，我们通过把最优打包问题转为图填色问题（把特征作为点，在没有互斥的特征两个特征中加入边），设计了一个高效的算法，通过固定近似率的贪心算法来解决它。

效果：在多个公开数据集上展示了它可以加速20倍，依旧能达到基本相同的准确率。

2 算法原理

2.1 单边梯度抽样算法

GBDT 算法的梯度大小可以反应样本的权重，梯度越小说明模型拟合的越好，单边梯度抽样算法（Gradient-based One-Side Sampling, GOSS）利用这一信息对样本进行抽样，减少了大量梯度小的样本，在接下来的计算锅中只需关注梯度高的样本，极大的减少了计算量。

GOSS 算法保留了梯度大的样本，并对梯度小的样本进行随机抽样，为了不改变样本的数据分布，在计算增益时为梯度小的样本引入一个常数进行平衡。

伪代码

GOSS先基于梯度的绝对值对样本进行排序(无需保存排序后的结果，节省内存)，然后取梯度排名前a%的样本，和剩余样本的b%。计算增益时，对小梯度的数据乘以$\frac{1-a}{b}$来放大梯度小的样本的权重。

一方面算法将更多注意力放在训练不足的样本上，另一方面通过乘上权重来防止采样对原始数据分布造成太大的影响。

2.2 直方图算法

直方图算法的基本思想是将连续的特征离散化为 k 个离散特征，同时构造一个宽度为 k 的直方图用于统计信息（含有 k 个 bin）。直方图算法无需遍历数据，只需要遍历 k 个 bin 即可找到最佳分裂点。

Histogram-based 算法不是lightGBM所特有的，其他GBDT算法也采用了这样的算法，XGB也有，但是lightGBM做了一定优化

对于直方图算法来说最直接的有以下两个优点（以 k=256 为例）：

• 内存占用更小：XGBoost 需要用 32 位的浮点数去存储特征值，并用 32 位的整形去存储索引，而 LightGBM 只需要用 8 位去存储直方图，内存占用为原来的 1/8；
• 计算代价更小：计算特征分裂增益时，XGBoost 需要遍历一次数据找到最佳分裂点，而 LightGBM 只需要遍历一次 k 次，直接将时间复杂度从$O(\#data * \#feature )$ 降低到 $O(k * \#feature )$ 。

虽然将特征离散化后无法找到精确的分割点，可能会对模型的精度产生一定的影响，但较粗的分割也起到了正则化的效果，一定程度上降低了模型的方差。

直方图差加速：在构建叶节点直方图的时候，可以通过父节点的直方图和相邻节点的直方图相减的方式构建，从而减少计算量。直方图对象中存储了每个bin的一阶梯度之和、二阶梯度之和、样本数量、方便计算增益。

XGBoost进行预排序时只对非零值进行加速，LightGBM同样类似，只用非零特征构建直方图。对稀疏特征进行优化。

2.3 互斥特征捆绑算法

高维特征往往是稀疏的，而且特征间可能是相互排斥的（如两个特征不同时取非零值），如果两个特征并不完全互斥（如只有一部分情况下是不同时取非零值），可以用互斥率表示互斥程度。互斥特征捆绑算法（Exclusive Feature Bundling, EFB）指出如果将一些特征进行融合绑定，则可以降低特征数量。

特征捆绑有两个问题需要解决：

• 哪些特征可以绑定？
• 绑定后的特征，特征值如何确定？

针对问题1：

EFB 算法利用特征和特征间的关系构造一个加权无向图，并将其转换为图着色算法。图着色是个 NP-Hard 问题，采用贪婪算法得到近似解，具体步骤如下：

1. 构造一个加权无向图，顶点是特征，边是两个特征间互斥程度；
2. 根据节点的度进行降序排序，度越大，与其他特征的冲突越大；
3. 遍历每个特征，将它分配给现有特征包，或者新建一个特征包，使得总体冲突最小。

针对问题2：

论文给出特征合并算法，其关键在于原始特征能从合并的特征中分离出来。

由于每一个bundle当中，features的range都是不一样，所以我们需要重新构建合并后bundle feature的range。在第一个for循环当中，我们记录每个feature与之前features累积totalRange。在第二个for循环当中，根据之前的binRanges重新计算出新的bin value（F[j]bin[i] + binRanges[j]）保证feature之间的值不会冲突。这是针对于稀疏矩阵进行优化。

假设 Bundle 中有两个特征值，A 取值为 [0, 10]、B 取值为 [0, 20]，为了保证特征 A、B 的互斥性，可以给特征 B 添加一个偏移量转换为 [10, 30]，Bundle 后的特征其取值为 [0, 30]，这样便实现了特征合并。

2.4 带深度限制的Leaf-wise 算法

决策树的构建过程中有两种策略：

• Level-wise: 基于层进行生长，知道达到停止条件
• Leaf-wise：每次分裂增益最大的叶子节点，直到达到停止条件

XGBoost 采用 Level-wise 的增长策略，方便并行计算每一层的分裂节点，提高了训练速度，但同时也因为节点增益过小增加了很多不必要的分裂，降低了计算量；

LightGBM 采用 Leaf-wise 的增长策略减少了计算量，配合最大深度的限制防止过拟合，由于每次都需要计算增益最大的节点，所以无法并行分裂。

2.5 类别特征最优分割

大部分的机器学习算法都不能直接支持类别特征，一般都会对类别特征进行编码，然后再输入到模型中。

LightGBM 原生支持类别特征，采用 many-vs-many 的切分方式将类别特征分为两个子集，实现类别特征的最优切分。相较one-hot，更容易产生最优切分。

其基本思想在于每次分组时都会根据训练目标对类别特征进行分类，根据其累积值$\frac{\sum gradient}{\sum hessian}$对直方图进行排序，然后找到最佳分割。示例过程如图所示：

3 工程实现

3.1 特征并行

传统的特征并行算法在于对数据进行垂直划分，然后使用不同机器找到不同特征的最优分裂点，基于通信整合得到最佳划分点，然后基于通信告知其他机器划分结果。

传统的特征并行方法有个很大的缺点：需要告知每台机器最终划分结果，增加了额外的复杂度。

LightGBM 则不进行数据垂直划分，每台机器都有训练集完整数据，在得到最佳划分方案后可在本地执行划分而减少了不必要的通信。

3.2 数据并行

传统的数据并行策略主要为水平划分数据，然后本地构建直方图并整合成全局直方图，最后在全局直方图中找出最佳划分点。

这种数据划分有一个很大的缺点：通讯开销过大。

LightGBM 采用分散规约（Reduce scatter）的方式将直方图整合的任务分摊到不同机器上，从而降低通信代价，并通过直方图做差进一步降低不同机器间的通信。

3.3 投票并行

针对数据量特别大特征也特别多的情况下，可以采用投票并行。投票并行主要针对数据并行时数据合并的通信代价比较大的瓶颈进行优化，其通过投票的方式只合并部分特征的直方图从而达到降低通信量的目的。

大致步骤为两步：

1. 本地找出 Top K 特征，并基于投票筛选出可能是最优分割点的特征；
2. 合并时只合并每个机器选出来的特征。

3.4 缓存优化

XGBoost 的预排序后的特征是通过索引给出的样本梯度的统计值，因其索引访问的结果并不连续，XGBoost 提出缓存访问优化算法进行改进。

LightGBM 所使用直方图算法对 Cache 天生友好：

1. 首先，所有的特征都采用相同的方法获得梯度（区别于不同特征通过不同的索引获得梯度），只需要对梯度进行排序并可实现连续访问，大大提高了缓存命中；
2. 其次，因为不需要存储特征到样本的索引，降低了存储消耗，而且也不存在 Cache Miss的问题。

4 总结

LightGBM 相对于 XGBoost 的优点，主要在于内存和速度两个方面。

内存更小

• XGB使用预排序后，需要记录特征值及其对应样本的统计值的索引。LGB使用直方图算法将特征值转换成bin值，并且不需要记录样本索引。空间复杂度变化：$O(2*\#data) ---> O(\# bin)$
• LGB使用互斥特征捆绑算法减少了特征数量，降低了内存消耗

速度更快

• LGB使用直方图算法将遍历样本转变为遍历直方图，降低了时间复杂度
• 单边梯度算法过滤掉梯度小的样本，减少了计算量
• Leaf-wise算法构建树，减少了计算量
• 特征并行、数据并行以及投票并行等方法加速计算
• 对缓存也有优化，增加了cache hit的命中率

3 模型对比

	GBDT	XGBoost	LightGBM
基模型	CART	CART/线性分类器	CART
优化方法	梯度下降	牛顿法	牛顿法
正则项	不支持	L1/L2 正则	L1/L2 正则
行列抽样	不支持	支持	支持
缺失值	不支持	寻找切分点时只对 non-missing的样 本遍历，将缺失值 分到左子树和右子 树分别计算损失， 选择最优情况。若 训练集无缺失而测 试集有缺失，则将 缺失值自动放到右 子树	寻找切分点时只对 non-missing的样 本遍历，将缺失值 分到左子树和右子 树分别计算损失， 选择最优情况。若 训练集无缺失而测 试集有缺失，则将 缺失值自动放到右 子树
树生长策略		按层生⻓(level- wise)(广度优 先) 同时分裂同一 层 的叶子	带有深度限制按叶子生⻓(leaf- wise)(深度优先) 每次从当前所 有叶子中，找到分裂增益最大的一 个叶子，然后分裂
分裂优化		对所有特征按数值 进行预排序，保存 排序后的索引值， 在空间和时间上有 很大的开销 O(#data*#feature)	直方图算法，将连续特征离散 成k个离散值(bin)，并构造宽度为k 的Histogram，计算每个离散值在直 方图中的累计统计量。进行特征选 择时，根据直方图的离散值，遍历 寻找最优的分割点 O(k*#feature)
类别特征	不支持	不支持	1.统计特征下每一种离散值出现的次 数，并从高到低排序，超过maxbin 则过滤剩下的类别 2.bin<4则逐个扫 描每一个bin容器，找出最佳分裂 点。3.Bin>4则用(bin容器下所有 样本的一阶梯度之和 / 该bin容器下 所有样本的二阶梯度之和 + 正则 项)所得值进行排序，再从左右分 别搜索确定最优阈值，无需搜索所 有Bin，默认上限32个