RF,GBDT,XGBOOST, LightGBM之间的爱恨情仇

1. 前言

RF,GBDT,XGBoost,lightGBM都属于集成学习（Ensemble Learning），集成学习的目的是通过结合多个基学习器的预测结果来改善基本学习器的泛化能力和鲁棒性。

根据基本学习器的生成方式，目前的集成学习方法大致分为两大类：即基本学习器之间存在强依赖关系、必须串行生成的序列化方法；以及基本学习器间不存在强依赖关系、可同时生成的并行化方法。前者的代表就是Boosting，后者的代表是Bagging和“随机森林”（Random Forest）。

本文主要从下面四个广泛讨论和使用的方法进行了对比分析总结：
RF（随机森林）,GBDT（梯度提升决策树）,XGBoost,lightGBM

2. RF（随机森林）

2.1 算法原理

介绍RF之前需要先了解一下Bagging，其可以简单的理解为：放回抽样，多数表决（分类）或简单平均（回归）,同时Bagging的基学习器之间属于并列生成，不存在强依赖关系。

回到RF身上，他其实是Bagging的一个扩展变体，主要可以概括为如下四步：

1、随机选择样本（放回抽样）；
2、随机选择特征（相比普通通bagging多了特征采样）；
3、构建决策树；
4、随机森林投票（平均）。

2.2 特性

在构建决策树的时候，RF的每棵决策树都最大可能的进行生长而不进行剪枝；在对预测输出进行结合时，RF通常对分类问题使用简单投票法，回归任务使用简单平均法。

RF的重要特性是不用对其进行交叉验证或者使用一个独立的测试集获得无偏估计，它可以在内部进行评估，也就是说在生成的过程中可以对误差进行无偏估计，由于每个基学习器只使用了训练集中约63.2%的样本，剩下约36.8%的样本可用做验证集来对其泛化性能进行“包外估计”。

2.3 RF和Bagging对比：

随机选择样本和Bagging相同，随机选择特征是指在树的构建中，会从样本集的特征集合中随机选择部分特征，然后再从这个子集中选择最优的属性用于划分，这种随机性导致随机森林的偏差会有稍微的增加（相比于单棵不随机树），但是由于随机森林的‘平均’特性，会使得它的方差减小，而且方差的减小补偿了偏差的增大，因此总体而言是更好的模型。

RF的起始性能较差，特别当只有一个基学习器时，但随着学习器数目增多，随机森林通常会收敛到更低的泛化误差。随机森林的训练效率也会高于Bagging，因为在单个决策树的构建中，Bagging使用的是‘确定性’决策树，在选择特征划分结点时，要对所有的特征进行考虑，而随机森林使用的是‘随机性’特征数，只需考虑特征的子集。

2.4 优缺点

优点：

1. 训练可以高度并行化，对于大数据时代的大样本训练速度有优势，算是主要优势；
2. 能够处理很高维的数据，并且不用特征选择，而且在训练完后，给出特征的重要性；
3. 相对于Boosting系列的Adaboost和GBDT， RF实现比较简单。
   　　
   缺点：在噪声较大的分类或者回归问题上容易过拟合。

3. GBDT（梯度提升决策树）

3.1 算法原理

首先是基于Boosting的，提升树是加法模型，学习算法为前向分布算法时的算法。但GBDT与传统的Boosting区别较大，是对提升树的改进，不过它限定基本学习器为决策树。它的每一次计算都是为了减少上一次的残差，而为了消除残差，我们可以在残差减小的梯度方向上建立模型,所以说，在GradientBoost中，每个新的模型的建立是为了使得之前的模型的残差往梯度下降的方法，与传统的Boosting中关注正确错误的样本加权有着很大的区别。

具体的算法求解过程可以参考这篇博客或者原始论文。

3.2 特性

对于二分类问题，损失函数为指数函数，就是把AdaBoost算法中的基本学习器限定为二叉决策树就可以了；对于回归问题，损失函数为平方误差，此时，拟合的是当前模型的残差。提升树算法只适合误差函数为指数函数和平方误差，对于一般的损失函数，梯度提升树算法利用损失函数的负梯度在当前模型的值，作为残差的近似值。

在GradientBoosting算法中，关键就是利用损失函数的负梯度方向在当前模型的值作为残差的近似值，进而拟合一棵CART回归树。GBDT的会累加所有树的结果，而这种累加是无法通过分类完成的，因此GBDT的树都是CART回归树，而不是分类树（尽管GBDT调整后也可以用于分类但不代表GBDT的树为分类树）。

3.3 优缺点：

优点：

1. 它能灵活的处理各种类型的数据；
2. 在相对较少的调参时间下，预测的准确度较高，这个是相对SVM来说的。

缺点：基学习器之前存在串行关系，难以并行训练数据。

4 XGBoost

4.1 算法原理

XGBoost的性能在GBDT上又有一步提升，而其性能也能通过各种比赛管窥一二。坊间对XGBoost最大的认知在于其能够自动地运用CPU的多线程进行并行计算，同时在算法精度上也进行了精度的提高。由于GBDT在合理的参数设置下，往往要生成一定数量的树才能达到令人满意的准确率，在数据集较复杂时，模型可能需要几千次迭代运算。但是XGBoost利用并行的CPU更好的解决了这个问题。

针对XGBoost细节可以参考本人对原始论文的译文以及本人的另一篇专门针对XGBoost原理的详解的博客。

4.2 特性

这里的特性也一般是XGBoost本身加的很多tricks，也是算法的优势所在。

4.2.1 基分类器
传统GBDT以CART树作为基分类器，xgboost还支持线性分类器，这个时候xgboost相当于带L1和L2正则化项的逻辑斯蒂回归（分类问题）或者线性回归（回归问题）。—可以通过booster[default=gbtree]设置参数:gbtree: tree-based models/gblinear: linear models。

4.2.2 目标函数
传统GBDT在优化时只用到一阶导数信息，xgboost则对代价函数进行了二阶泰勒展开，同时用到了一阶和二阶导数。顺便提一下，xgboost工具支持自定义代价函数，只要函数可一阶和二阶求导。

对损失函数做了改进（泰勒展开），我们知道目标函数定义如下：

$$\mathcal L^{(t)} = \sum_{t=1}^n l(y_i,\hat y_i^{(t-1)} + f_t(x_i)) + \Omega(f_t) + constant$$

其中： $\Omega(f) = \gamma T + \frac{1}{2} \lambda ||w||^2$

上述目标函数的第二项是正则项，包含了L1和L2正则。且最后一项constant是常数项，优化中可以先忽略，后面我们不再提。然后我们对目标函数进行二阶的泰勒展开来近似，所以有：

$$\mathcal L^{(t)} \simeq \sum_{t=1}^n [l(y_i,\hat y^{(t-1)}) + g_i f_t(x_i) + \frac{1}{2} h_i f_t^2(x_i)] + \Omega(f_t)$$

其中，$g_i = \partial_{\hat y^{(t-1)}} l(y_i,\hat y^{(t-1)})$和$h_i = \partial_{\hat y^{(t-1)}}^2 l(y_i,\hat y^{(t-1)})$，

我们可以很清晰地看到，最终的目标函数只依赖于每个数据点的在误差函数上的一阶导数和二阶导数。

4.2.3 正则项
xgboost在代价函数里加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和。从 Bias-variance tradeoff 角度来讲，正则项降低了模型 variance，使学习出来的模型更加简单，防止过拟合，这也是xgboost优于传统GBDT的一个特性。正则化包括了两个部分，都是为了防止过拟合，剪枝是都有的，叶子结点输出L2平滑是新增的。

4.2.4 shrinkage
还是为了防止过拟合，shrinkage缩减类似于学习速率，在每一步 tree boosting 之后增加了一个参数$\eta$（权重），即有$F^{t} =F^{t-1} + \eta f^t$。 通过这种方式来减小每棵树的影响力，给后面的树提供空间去优化模型。权重一般在0-1之间，经验上<=0.1的时候比较好。（补充：传统GBDT的实现也有学习速率）

4.2.5 column subsampling 列(特征)抽样，说是从随机森林那边学习来的，防止过拟合的效果比传统的行抽样还好（xgb同样也包含行抽样功能），并且有利于后面提到的并行化处理算法。

4.2.6 split finding algorithms(划分点查找算法)：

exact greedy algorithm—贪心算法获取最优切分点;
approximate algorithm—近似算法，提出了候选分割点概念，先通过直方图算法获得候选分割点的分布情况，然后根据候选分割点将连续的特征信息映射到不同的buckets中，并统计汇总信息。详细见论文3.3节
Weighted Quantile Sketch—分布式加权直方图算法，论文3.4节

可并行的近似直方图算法。树节点在进行分裂时，我们需要计算每个特征的每个分割点对应的增益，即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下，贪心算法效率就会变得很低，所以xgboost还提出了一种可并行的近似直方图算法，对特征排序后仅选择常数个候选分裂位置作为候选分裂点，用于高效地生成候选的分割点。这里的加权就是指当进行某一个特征划分点查找的时候，利用样本的二阶导即$h_i$值作为样本的权重，而并不是按照样本原始个数取找分位数。

4.2.7 对缺失值的处理。
对于特征的值有缺失的样本，xgboost可以自动学习出它的分裂方向。稀疏感知算法，论文3.4节，Algorithm 3: Sparsity-aware Split Finding。具体处理方式可以概述如下：

1. 在特征k上寻找最佳 split point 时，不会对该列特征 missing 的样本进行遍历，而只对该列特征值为 non-missing 的样本上对应的特征值进行遍历，通过这个技巧来减少了为稀疏离散特征寻找 split point 的时间开销。
2. 在逻辑实现上，为了保证完备性，会将该特征值missing的样本分别分配到左叶子结点和右叶子结点，两种情形都计算一遍后，选择分裂后增益最大的那个方向（左分支或是右分支），作为预测时特征值缺失样本的默认分支方向。

一棵树中每个结点在分裂时，寻找的是某个特征的最佳分裂点（特征值），完全可以不考虑存在特征值缺失的样本，也就是说，如果某些样本缺失的特征值缺失，对寻找最佳分割点的影响不是很大。

4.2.8 Built-in Cross-Validation（内置交叉验证)。
XGBoost允许在每一轮boosting迭代中使用交叉验证。因此，可以方便地获得最优boosting迭代次数。而GBM使用网格搜索，只能检测有限个值。

4.2.9 continue on Existing Model（接着已有模型学习）。
XGBoost可以在上一轮的结果上继续训练。这个特性在某些特定的应用上是一个巨大的优势。

4.2.10 High Flexibility（高灵活性）。
XGBoost 允许用户定义自定义优化目标和评价标准，它对模型增加了一个全新的维度，所以我们的处理不会受到任何限制。

4.2.11 并行化处理—系统设计模块,块结构设计等

• XGBoost的并行，并不是说每棵树可以并行训练，XGB本质上仍然采用boosting思想，每棵树训练前需要等前面的树训练完成才能开始训练。

• XGBoost的并行，指的是特征维度的并行：在训练之前，每个特征按特征值对样本进行预排序，并存储为Block结构，在后面查找特征分割点时可以重复使用，而且特征已经被存储为一个个block结构，那么在寻找每个特征的最佳分割点时，可以利用多线程对每个block并行计算。

4.2.12 剪枝

1. 在目标函数中增加了正则项：使用叶子结点的数目和叶子结点权重的L2模的平方，控制树的复杂度。
2. 在结点分裂时，定义了一个阈值，如果分裂后目标函数的增益Gain小于该阈值(最小划分损失min_split_loss)，则不分裂。
3. 当引入一次分裂后，重新计算新生成的左、右两个叶子结点的样本权重和。如果任一个叶子结点的样本权重低于某一个阈值（最小样本权重和min_child_weight），也会放弃此次分裂。
4. XGBoost 先从顶到底建立树直到最大深度，再从底到顶反向检查是否有不满足分裂条件的结点，进行剪枝。
5. 当树达到最大深度时，停止建树，因为树的深度太深容易出现过拟合，这里需要设置一个超参数max_depth。

对于最后一点，XGBoost会一直分裂到指定的最大深度(max_depth)，然后回过头来剪枝，即后剪枝。如果某个节点之后不再有正值，它会去除这个分裂。这种做法的优点，当一个负损失（如-2）后面有个正损失（如+10）的时候，就显现出来了。预剪枝会在-2处停下来，因为它遇到了一个负值。但是XGBoost会继续分裂，然后发现这两个分裂综合起来会得到+8，因此会保留这两个分裂。

4.2.13 高速缓存压缩感知算法
xgboost还设计了高速缓存压缩感知算法，这是系统设计模块的效率提升。当梯度统计不适合于处理器高速缓存和高速缓存丢失时，会大大减慢切分点查找算法的速度。

针对 exact greedy algorithm采用缓存感知预取算法
针对 approximate algorithms选择合适的块大小

4.2.14 处理不平衡数据
对于不平衡的数据集，例如用户的购买行为，肯定是极其不平衡的，这对XGBoost的训练有很大的影响，XGBoost有两种自带的方法来解决：

• 第一种，如果你在意AUC，采用AUC来评估模型的性能，那你可以通过设置scale_pos_weight来平衡正样本和负样本的权重。例如，当正负样本比例为1:10时，scale_pos_weight可以取10；

• 第二种，如果你在意概率(预测得分的合理性)，你不能重新平衡数据集(会破坏数据的真实分布)，应该设置max_delta_step为一个有限数字来帮助收敛（基模型为LR时有效）。

原理是增大了少数样本的权重。除此之外，还可以通过上采样、下采样、SMOTE算法或者自定义代价函数的方式解决正负样本不平衡的问题。

4.3 XGBoost不足之处：

1. 每轮迭代时，都需要遍历整个训练数据多次。如果把整个训练数据装进内存则会限制训练数据的大小；如果不装进内存，反复地读写训练数据又会消耗非常大的时间。
2. 预排序方法（pre-sorted）：首先，空间消耗大。这样的算法需要保存数据的特征值，还保存了特征排序的结果（例如排序后的索引，为了后续快速的计算分割点），这里需要消耗训练数据两倍的内存。其次时间上也有较大的开销，在遍历每一个分割点的时候，都需要进行分裂增益的计算，消耗的代价大。
3. 对cache优化不友好。在预排序后，特征对梯度的访问是一种随机访问，并且不同的特征访问的顺序不一样，无法对cache进行优化。同时，在每一层长树的时候，需要随机访问一个行索引到叶子索引的数组，并且不同特征访问的顺序也不一样，也会造成较大的cache miss。

4.4 常用问题解答

4.4.1 RF和GBDT的区别

他们都是由多棵树组成，最终的结果都是由多棵树一起决定。而不同点主要有：

• 集成学习：RF属于bagging思想，而GBDT是boosting思想；
• 偏差-方差权衡：RF不断的降低模型的方差，而GBDT不断的降低模型的偏差；
• 训练样本：RF每次迭代的样本是从全部训练集中有放回抽样形成的，而GBDT每次使用全部样本；
• 并行性：RF的树可以并行生成，而GBDT只能顺序生成(需要等上一棵树完全生成)；
• 最终结果：RF最终是多棵树进行多数表决（回归问题是取平均），而GBDT是加权融合；
• 数据敏感性：RF对异常值不敏感，而GBDT对异常值比较敏感；
• 泛化能力：RF不易过拟合，而GBDT容易过拟合。

4.4.2 XGBoost与GBDT有什么不同

• 基分类器：XGBoost的基分类器不仅支持CART决策树，还支持线性分类器，此时XGBoost相当于带L1和L2正则化项的Logistic回归（分类问题）或者线性回归（回归问题）。
• 导数信息：XGBoost对损失函数做了二阶泰勒展开，GBDT只用了一阶导数信息，并且XGBoost还支持自定义损失函数，只要损失函数一阶、二阶可导。
• 正则项：XGBoost的目标函数加了正则项， 相当于预剪枝，使得学习出来的模型更加不容易过拟合。
• 列抽样和缩减：XGBoost支持列采样，与随机森林类似，同时对每棵树输出使用shrinkage，都是用于防止过拟合。
• 缺失值处理：对树中的每个非叶子结点，XGBoost可以自动学习出它的默认分裂方向。如果某个样本该特征值缺失，会将其划入默认分支。
• 并行化：注意不是tree维度的并行，而是特征维度的并行。XGBoost预先将每个特征按特征值排好序，存储为块结构，分裂结点时可以采用多线程并行查找每个特征的最佳分割点，极大提升训练速度。
• 可并行的近似直方图算法：树节点在进行分裂时，我们需要计算每个特征的每个分割点对应的增益。当数据无法一次载入内存或者在分布式情况下，贪心算法效率就会变得很低，所以xgboost还提出了一种可并行的近似直方图算法，用于高效地生成候选的分割点。

4.4.3 XGBoost为什么使用泰勒二阶展开

• 精准性：相对于GBDT的一阶泰勒展开，XGBoost采用二阶泰勒展开，阶信息本身就能让梯度收敛更快更准确。这一点在优化算法里的牛顿法里已经证实了。可以简单认为一阶导指引梯度方向，二阶导指引梯度方向如何变化。
• 可扩展性：Xgboost官网上有说，当目标函数是MSE时，展开是一阶项（残差）+二阶项的形式（官网说这是一个nice form），而其他目标函数，如logloss的展开式就没有这样的形式。为了能有个统一的形式，所以采用泰勒展开来得到二阶项，这样就能把MSE推导的那套直接复用到其他自定义损失函数上。简短来说，就是为了统一损失函数求导的形式以支持自定义损失函数。

4.4.4 XGBoost为什么快

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

4.4.5 XGBoost防止过拟合的方法

• 目标函数添加正则项：叶子节点个数+叶子节点权重的L2正则化
• 列抽样：训练的时候只用一部分特征（不考虑剩余的block块即可）
• 子采样：每轮计算可以不使用全部样本，使算法更加保守
• shrinkage: 可以叫学习率或步长，为了给后面的训练留出更多的学习空间
• 剪枝：多种方式限制树的复杂度，参考4.2.12。

4.4.6 XGBoost中叶子结点的权重如何计算出来

$\mathcal F = {f(x) = w_{q(x)}}(q: \mathbb R^m \rightarrow T, w \in \mathbb R^T)$是回归树（也叫做CART）的空间。

$q$表示将样本映射到叶节点的树的结构。$T$是每棵树叶子的数量。每个$F_k$对应了独立的树结构$q$和叶权值$w$。与决策树不同，每棵回归树的每个叶子上包含连续的连续值打分，我们用$w_i$表示第$i$个叶子的打分。

即这里每个样本最终在$q$结构的树上最终只会落在某一个叶子节点上，那么对应的$w$这个权重即为输出值。所以我们需要确定最优的$w$，而这个就需要根据最优的损失目标来确定。有$T$个叶子节点所以有$T$个$w$

定义$I_j = {i|q(x_i)=j}$为叶子结点j里面的样本，我们可以通过扩展$\Omega$来重写公式（3）：

$$\tilde{\mathcal L}^{(t)} = \sum_{t=1}^n [g_i f_t(x_i) + \frac{1}{2} h_i f_t^2(x_i)] + \gamma T + \frac{1}{2} \lambda \sum_{j=1}^T w_j^2 \\ =\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 T$$

对于一个固定的结构$q(x)$，我们可以根据二次函数求最值的方法计算叶子结点$j$的最优权重$w_j^{*}$，即在$w_j^{*}$取如下值的时候目标函数能够取最小值：

$$w_j^* = -\frac{\sum_{i \in I_j} g_i} {\sum_{i \in I_j} h_i + \lambda}$$

并通过下式计算相应的目标函数最优值：

$$\tilde{\mathcal{L}}^{(t)}(q)=-\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$$

我们需要检测这次分裂是否会给损失函数带来增益，增益的定义如下：

$$\mathcal{L}_{\text {split}}=\frac{1}{2}\left[\frac{\left(\sum_{i \in I_{L}} g_{i}\right)^{2}}{\sum_{i \in I_{L}} h_{i}+\lambda}+\frac{\left(\sum_{i \in I_{R}} g_{i}\right)^{2}}{\sum_{i \in I_{R}} h_{i}+\lambda}-\frac{\left(\sum_{i \in I} g_{i}\right)^{2}}{\sum_{i \in I} h_{i}+\lambda}\right]-\gamma$$

4.4.7 XGBoost如何评价特征的重要性
官方文档主要介绍了三种方法来评判XGBoost模型中特征的重要程度：

weight ：该特征在所有树中被用作分割样本的特征的总次数。
gain ：该特征在其出现过的所有树中产生的平均增益。
cover ：该特征在其出现过的所有树中的平均覆盖范围。

注意：覆盖范围这里指的是一个特征用作分割点后，其影响的样本数量，即有多少样本经过该特征分割到两个子节点。

除了这一部分，本人在实际项目中为了做模型的可解释性，发现了另一种方法。得益于XGBoost本身依然是树结构的模型，所以我们能够得到样本在打分过程中在每一棵树上所到达的每一个节点的权重值，通过这样的路径和权重值我们能够通过叶子结点沿着路径反向计算权重的差值即可得到每一个特征在各个节点处的贡献值。

4.4.8 XGBoost如何选择最佳分裂点

在分裂一个结点时，我们会有很多个候选分割点，寻找最佳分割点的大致步骤如下：

1. 遍历每个结点的每个特征；
2. 对每个特征，按特征值大小将特征值排序；
3. 线性扫描，找出每个特征的最佳分裂特征值；
4. 在所有特征中找出最好的分裂点（分裂后增益最大的特征及特征值）。

上面是一种贪心的方法，每次进行分裂尝试都要遍历一遍全部候选分割点，也叫做全局扫描法。

但当数据量过大导致内存无法一次载入或者在分布式情况下，贪心算法的效率就会变得很低，全局扫描法不再适用。基于此，XGBoost提出了一系列加快寻找最佳分裂点的方案，也即4.2.6中提到的近似分位数（直方图）算法：

• 特征预排序+缓存：XGBoost在训练之前，预先对每个特征按照特征值大小进行排序，然后保存为block结构，后面的迭代中会重复地使用这个结构，使计算量大大减小。
• 分位点近似法：对每个特征按照特征值排序后，采用类似分位点选取的方式，仅仅选出常数个特征值作为该特征的候选分割点，在寻找该特征的最佳分割点时，从候选分割点中选出最优的一个。
• 并行查找：由于各个特性已预先存储为block结构，XGBoost支持利用多个线程并行地计算每个特征的最佳分割点，这不仅大大提升了结点的分裂速度，也极利于大规模训练集的适应性扩展。

5 LightGBM

5.1 算法原理

它是微软出的新的boosting框架，基本原理与XGBoost一样，只是在框架上做了一优化（重点在模型的训练速度的优化）。对于其细节算法可以参考本人对原始论文的译文博客。

5.2 LightGBM和XGBoost的区别

5.2.1 树生长策略

XGB采用level-wise的分裂策略，LGB采用leaf-wise的分裂策略。XGB对每一层所有节点做无差别分裂，但是可能有些节点增益非常小，对结果影响不大，带来不必要的开销。Leaf-wise是在所有叶子节点中选取分裂收益最大的节点进行的，但是很容易出现过拟合问题，所以需要对最大深度做限制 。

Level-wise：此为XGBoost主要是用的方法，过一次数据可以同时分裂同一层的叶子，容易进行多线程优化，也好控制模型复杂度，不容易过拟合。但实际上Level-wise是一种低效算法，因为它不加区分的对待同一层的叶子，带来了很多没必要的开销，因为实际上很多叶子的分裂增益较低，没必要进行搜索和分裂。

Leaf-wise：LightGBM使用的方法，是一种更为高效的策略，每次从当前所有叶子中，找到分裂增益最大的一个叶子，然后分裂，如此循环。因此同Level-wise相比，在分裂次数相同的情况下，Leaf-wise可以降低更多的误差，得到更好的精度。但是可能会长出比较深的决策树，产生过拟合。因此LightGBM在Leaf-wise之上增加了一个最大深度限制，在保证高效率的同时防止过拟合。

注意：目前XGBoost现在两种方式都是支持的

5.2.2 分割点查找算法

lightgbm使用了基于histogram的切分点算法，这一点不同与xgboost中的预排序的 exact greedy 算法，histogram算法在内存和计算代价上都有不小优势。XGBoost里现在也提供了这一选项，不过默认的方法是对特征预排序。

直方图算法的基本思想：先把连续的浮点特征值离散化成k个整数，同时构造一个宽度为k的直方图。遍历数据时，根据离散化后的值作为索引在直方图中累积统计量，当遍历一次数据后，直方图累积了需要的统计量，然后根据直方图的离散值，遍历寻找最优的分割点。直方图算法是一种牺牲了一定的切分准确性而换取训练速度以及节省内存空间消耗的算法。

下面我们就看一下直方图算法的优势：

• 内存上优势。很明显，直方图算法的内存消耗为(# data # features 1Bytes)(因为对特征分桶后只需保存特征离散化之后的值)，而预排序的 exact greedy 算法内存消耗为：(2 # data # features* 4Bytes)，因为后者既要保存原始feature的值，也要保存这个值的顺序索引，这些值需要32位的浮点数来保存。直方图算法则不需要从而减少了并行训练的通信代价。
• 计算上的优势。预排序算法在选择好分裂特征计算分裂收益时需要遍历所有样本的特征值，时间为O(# feature # data),而直方图算法只需要遍历桶就行了，时间为O(#feature # bins)。�𝑒×#𝑏�
• 直方图做差加速。一个子节点的直方图可以通过父节点的直方图减去兄弟节点的直方图得到，从而加速计算。

但实际上xgboost的近似直方图算法也类似于lightgbm这里的直方图算法，为什么xgboost的近似算法比lightgbm还是慢很多呢？

xgboost在每一层都动态构建直方图，因为xgboost的直方图算法不是针对某个特定的feature，而是所有feature共享一个直方图(每个样本的权重是二阶导),所以每一层都要重新构建直方图，而lightgbm中对每个特征都有一个直方图，所以构建一次直方图就够了。

5.2.3 支持离散变量

XGBoost无法直接输入类别型变量，因此需要事先对类别型变量进行编码（例如独热编码），而LightGBM可以直接输入 categorical 的 feature。在对离散特征分裂时，每个取值都当作一个桶，分裂时的增益算的是”是否属于某个category“的gain，类似于one-hot编码。

5.2.4 缓存命中率

使用collective communication算法替代了point-to-point communication算法提升了效率

• XGB使用Block结构的一个缺点是取梯度的时候，是通过索引来获取的，而这些梯度的获取顺序是按照特征的大小顺序的，这将导致非连续的内存访问，可能使得CPU cache缓存命中率低，从而影响算法效率。
• 而LGB是基于直方图分裂特征的，梯度信息都存储在一个个bin中，所以访问梯度是连续的，缓存命中率高。

5.2.5 并行策略

(1) 特征并行

• LGB特征并行：

1. 是每个worker留有一份完整的数据集（不经过采样的），这样就不必在切分后传输切分结果数据，因为每个机器已经持有完整的数据集；
2. 各个机器上的worker根据所分配的特征子集寻找到局部的最优切分点(特征、阈值)；
3. worker之间需要相互通信，通过比对损失来确定的最佳切分点；
4. 然后将这个最佳切分点的位置进行全局广播，每个worker进行切分即可。

• XGB的特征并行：

1. 对数据列采样，即不同的机器上保留不同的特征子集；
2. 各个机器上的worker根据所分配的特征子集寻找到局部的最优切分点(特征、阈值)；
3. 互相通信来从局部最佳切分点里得到最佳切分点；
4. 拥有最佳切分点的worker执行切分操作，然后将切分结果传送给其他的worker；
5. 其他的worker根据接收到的数据来切分数据。

二者的区别就导致了LGB中worker间通信成本明显降低，只需通信一个特征分裂点即可。而XGB中要广播样本索引，计算量太大，并没有提升切分的效率，时间复杂度为O(#data)(因为每个worker持有所有行，需要处理全部的记录)，当数据量较大时特征并行并不能提升速度切分结果的通信代价，大约为O(#data/8)(若一个数据样本为1bit)

Notes:LGB是典型的空间换时间，差别就是减少了传输切分结果的步骤，节省了这里的通信消耗

(2) 数据并行 ：
当数据量很大，特征相对较少时，需要考虑数据并行策略。

• XGB中的数据并行是传统做法

1. 行采样，对数据进行横向切分；
2. worker使用分配到的局部数据构建局部的直方图；
3. 合并局部直方图得到全局的直方图；
4. 对全局直方图寻找最优切分点，然后进行切分。

• LightGBM的做法(依然是降低通信代价)

1. 不同于合并所有的局部直方图获得全局的直方图，LightGBM通过Reduce Scatter方法来合并不同worker的无交叉的不同特征的直方图，这样找到该直方图的局部最优切分点，最后同步到全局最优切分点；
2. 基于直方图做差的方法，先计算样本量少的节点的样本索引，在通信的过程中可以只传输某一叶节点的直方图，而对于其邻居可通过直接相减得到子节点的样本索引，这个直方图算法使得worker间的通信成本降低一倍，因为只用通信以此样本量少的节点。通信的时间复杂度为O(0.5#feature#bin)

Notes: 传统做法的通信代价过高，若使用point-to-point的通信算法，每个机器的通信代价时间复杂度为O(# machine # feature # bin)，若使用collective通信算法则通信代价为O(2 # feature \ # bin)

(3) 投票并行（LGB）：

当数据量和维度都很大时，选用投票并行，该方法是数据并行的一个改进。数据并行中的合并直方图的代价相对较大，尤其是当特征维度很大时。大致思想是：每个worker首先会找到本地的一些优秀的特征，然后进行全局投票，根据投票结果，选择top的特征进行直方图的合并，再寻求全局的最优分割点。

5.2.6 Early Stopping

XGBoost,LightGBM都支持早停止，不过在细节上略有不同。XGBoost和LightGBM里的early_stopping则都是用来控制基学习器的数目的

• 两者都可以使用多组评价指标，但是不同之处在于XGBoost会根据指标列表中的最后一项指标控制模型的早停止，而LightGBM则会受到所有的评估指标的影响；
• 在使用early stopping控制迭代次数后，模型直接返回的是最后一轮迭代的学习器不一定是最佳学习器，而在做出预测时可以设置参数选择某一轮的学习器作出预测。

  • XGBoost里保存了三种状态的学习器，分别是bst.best_score, bst.best_iteration, bst.best_ntree_limit,官方的建议是在做预测时设置为bst.best_ntree_limit，实际使用时感觉bst.best_iteration和 bst.best_ntree_limit的表现上区别不大

• LightGBM则仅提供了bst.best_iteration这一种方式。

参考博文：
yealxxy: RF,GBDT,XGBoost,lightGBM的对比
data_scientist:F、GBDT、XGBoost、lightGBM原理与区别
启迪云:XGBoost超详细推导，终于有人讲明白了
AlwaysBeta:XGBoost20题
默一鸣:RF,GBDT,XGBOOST, LightGBM的对比和分析