GDBT模型、XGBoost和LightGBM之间的区别与联系

GBDT提升树与XGBoost树

相比于经典的GBDT，xgboost做了一些改进，从而在效果和性能上有明显的提升，在这里，通过整理了一些资料，总结了一下：

第一，GBDT将目标函数泰勒展开到一阶，而xgboost将目标函数泰勒展开到了二阶。

使用泰勒展开到二阶的原因：
1. 统一损失函数求导的形式以支持自定义损失函数
2. 二阶信息本身就能让梯度收敛更快更准确

第二，GBDT是给新的基模型寻找新的拟合标签（前面加法模型的负梯度），而xgboost是给新的基模型寻找新的目标函数（目标函数关于新的基模型的二阶泰勒展开）

第三，xgboost加入了和叶子权重的L2正则化项，因而有利于模型获得更低的方差。

第四，xgboost增加了自动处理缺失值特征的策略。通过把带缺失值样本分别划分到左子树或者右子树，比较两种方案下目标函数的优劣，从而自动对有缺失值的样本进行划分，无需对缺失特征进行填充预处理。

第五：XGBoost采用了Shrinkage 和Column Subsampling方法，这两种方法都能在一定程度上防止过拟合。

Shrinkage方法就是每次迭代中对树的每个叶子节点的分数乘上一个缩减权重n，可以使得每个树的影响力不会太大，留下更多的空间给后面的树去优化。
Column Subsampling，一种按层随机采样，在在对同一层内每个节点分裂之前，先随机选择一部分特征，然后遍历这部分特征来寻找最优切分点。（近似算法，分桶也能降低过拟合风险）

第六：同级的节点可以并行化训练

XGBoost的优缺点：

优点：

1）使用了许多策略去防止过拟合，如：正则化项、Shrinkage、Column Subsampling等。

2）目标函数使用了损失函数关于待求函数的二阶导数

3）支持并行化同级层节点可并行化，具体的对于某个节点，节点内选择最佳分裂点，候选分裂点计算增益用多线程并行，加快训练速度。

4）添加了对稀疏数据的处理

5）采用了交叉验证以及early stop，防止建树过深

6）支持设置样本权重，可以通过调整权重可以更加关注一些样本。

缺点：

1）xgBoosting采用预排序，在迭代之前，对结点的特征做预排序，遍历选择最优分割点，数据量大时，贪心法耗时，LightGBM方法采用histogram算法，占用的内存低，数据分割的复杂度更低；

2）xgBoosting采用level-wise生成决策树，同时分裂同一层的叶子，从而进行多线程优化，不容易过拟合，但很多叶子节点的分裂增益较低，没必要进行跟进一步的分裂，这就带来了不必要的开销；LightGBM采用深度优化，leaf-wise生长策略，每次从当前叶子中选择增益最大的结点进行分裂，循环迭代，但会生长出更深的决策树，产生过拟合，因此引入了一个阈值进行限制，防止过拟合.

XGBoost树与LightGBM树：

LightGBM主要改进点：

1. Histogram算法： 直方图算法的基本思想是先把连续的浮点特征值离散化成k个整数（其实又是分桶的思想，而这些桶称为bin，比如[0,0.1)→0, [0.1,0.3)→1），同时构造一个宽度为k的直方图。

在遍历数据的时候，根据离散化后的值作为索引在直方图中累积统计量，当遍历一次数据后，直方图累积了需要的统计量，然后根据直方图的离散值，遍历寻找最优的分割点。

优点： 首先，最明显就是内存消耗的降低，直方图算法不仅不需要额外存储预排序的结果，而且可以只保存特征离散化后的值，而这个值一般用8位整型存储就足够了，内存消耗可以降低为原来的1/8。然后在计算上的代价也大幅降低，预排序算法每遍历一个特征值就需要计算一次分裂的增益，而直方图算法只需要计算k次

2.带深度限制的Leaf-wise的叶子生长策略 在XGBoost中，树是按层生长的，称为Level-wise tree growth，同一层的所有节点都做分裂，最后剪枝，如下图所示：

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

在Histogram算法之上，LightGBM进行进一步的优化，采用的Leaf-wise则是一种更为高效的策略，每次从当前所有叶子中，找到分裂增益最大的一个叶子，然后分裂，如此循环。

因此同Level-wise相比，在分裂次数相同的情况下，Leaf-wise可以降低更多的误差，得到更好的精度。Leaf-wise的缺点是可能会长出比较深的决策树，产生过拟合。因此LightGBM在Leaf-wise之上增加了一个最大深度的限制，在保证高效率的同时防止过拟合

3.直方图差加速

在树中，一个叶子的直方图可以由它的父亲节点的直方图与它兄弟的直方图做差得到。利用这个方法，LightGBM可以在构造一个叶子的直方图后，可以用非常微小的代价得到它兄弟叶子的直方图，在速度上可以提升一倍。

4.直接支持类别特征

一般算法，需要把类别特征转化到多维的0/1特征，然而会降低了空间和时间的效率。 LightGBM优化了对类别特征的支持，可以直接输入类别特征，不需要额外的0/1展开

LIghtGBM的优缺点：

优点：

1）速度较快，是XGBoost速度的16倍，内存占用率为XGBoost的1/6

2）采用了直方图算法，将连续的浮点型特征值离散化成K个整数

3）使用带有深度限制的leaf-wise的叶子生长策略。

缺点：

1）可能会长出比较深的决策树，产生过拟合。因此LightGBM在Leaf-wise之上增加了一个最大深度限制，在保证高效率的同时防止过拟合

2）基于偏差的算法，会对噪点较为敏感

3）在寻找最优解时，依据的最优切分变量，没有将最优解是全部特征的综合这一理念来考虑