LightGBM在很多方面会比XGBoost表现的更为优秀。它有以下优势：
- 更快的训练效率
- 低内存使用
- 更高的准确率
- 支持并行化学习
- 可处理大规模数据
- 支持直接使用category特征
从下图实验数据可以看出， LightGBM比XGBoost快将近10倍，内存占用率大约为XGBoost的1/6，并且准确率也有提升。
看完这些惊人的实验结果以后，对下面两个问题产生了疑惑：XGBoost已经十分完美了，为什么还要追求速度更快、内存使用更小的模型？对GBDT算法进行改进和提升的技术细节是什么？
提出LightGBM的动机
常用的机器学习算法，例如神经网络等算法，都可以以mini-batch的方式训练，训练数据的大小不会受到内存限制。而GBDT在每一次迭代的时候，都需要遍历整个训练数据多次。如果把整个训练数据装进内存则会限制训练数据的大小；如果不装进内存，反复地读写训练数据又会消耗非常大的时间。尤其面对工业级海量的数据，普通的GBDT算法是不能满足其需求的。
LightGBM提出的主要原因就是为了解决GBDT在海量数据遇到的问题，让GBDT可以更好更快地用于工业实践。
XGBoost的优缺点
精确贪心算法
每轮迭代时，都需要遍历整个训练数据多次。如果把整个训练数据装进内存则会限制训练数据的大小；如果不装进内存，反复地读写训练数据又会消耗非常大的时间。
优点：
- 可以找到精确的划分条件
缺点：
- 计算量巨大
- 内存占用巨大
- 易产生过拟合
Level-wise迭代方式
预排序方法（pre-sorted）：首先，空间消耗大。这样的算法需要保存数据的特征值，还保存了特征排序的结果（例如排序后的索引，为了后续快速的计算分割点），这里需要消耗训练数据两倍的内存。其次时间上也有较大的开销，在遍历每一个分割点的时候，都需要进行分裂增益的计算，消耗的代价大。
优点：
- 可以使用多线程
- 可以加速精确贪心算法
缺点：
- 效率低下，可能产生不必要的叶结点
对cache优化不友好
在预排序后，特征对梯度的访问是一种随机访问，并且不同的特征访问的顺序不一样，无法对cache进行优化。同时，在每一层长树的时候，需要随机访问一个行索引到叶子索引的数组，并且不同特征访问的顺序也不一样，也会造成较大的cache miss。
LightGBM在哪些地方进行了优化？
以上与其说是XGBoost的不足，倒不如说是LightGBM作者们构建新算法时着重瞄准的点。解决了什么问题，那么原来模型没解决就成了原模型的缺点。
概括来说，lightGBM主要有以下特点：
- 基于Histogram的决策树算法
- 带深度限制的Leaf-wise的叶子生长策略
- 直方图做差加速
- 直接支持类别特征(Categorical Feature)
- Cache命中率优化
- 基于直方图的稀疏特征优化
- 多线程优化
决策树算法
XGBoost使用的是pre-sorted算法，能够更精确的找到数据分隔点。
- 首先，对所有特征按数值进行预排序。
- 其次，在每次的样本分割时，用O(# data)的代价找到每个特征的最优分割点。
- 最后，找到最后的特征以及分割点，将数据分裂成左右两个子节点。
这种pre-sorting算法能够准确找到分裂点，但是在空间和时间上有很大的开销。
- 由于需要对特征进行预排序并且需要保存排序后的索引值（为了后续快速的计算分裂点），因此内存需要训练数据的两倍。
- 在遍历每一个分割点的时候，都需要进行分裂增益的计算，消耗的代价大。
LightGBM使用的是histogram算法，占用的内存更低，数据分隔的复杂度更低。其思想是将连续的浮点特征离散成k个离散值，并构造宽度为k的Histogram。然后遍历训练数据，统计每个离散值在直方图中的累计统计量。在进行特征选择时，只需要根据直方图的离散值，遍历寻找最优的分割点。
使用直方图算法有很多优点。首先最明显就是内存消耗的降低，直方图算法不仅不需要额外存储预排序的结果，而且可以只保存特征离散化后的值，而这个值一般用8位整型存储就足够了，内存消耗可以降低为原来的1/8。
然后在计算上的代价也大幅降低，预排序算法每遍历一个特征值就需要计算一次分裂的增益，而直方图算法只需要计算k次（k可以认为是常数），时间复杂度从O(#data*#feature)优化到O(k*#features)。
Histogram algorithm
Histogram algorithm应该翻译为直方图算法，直方图算法的思想也很简单，首先将连续的浮点数据转换为bin数据，具体过程是首先确定对于每一个特征需要多少的桶bin，然后均分，将属于该桶的样本数据更新为bin的值，最后用直方图表示。（看起来很高大上，其实就是直方图统计，最后我们将大规模的数据放在了直方图中）
直方图算法有几个需要注意的地方：
- 使用bin替代原始数据相当于增加了正则化；
- 使用bin意味着很多数据的细节特征被放弃了，相似的数据可能被划分到相同的桶中，这样的数据之间的差异就消失了；
- bin数量选择决定了正则化的程度，bin越少惩罚越严重，欠拟合风险越高。
直方图算法需要注意的地方：
- 构建直方图时不需要对数据进行排序（比XGBoost快），因为预先设定了bin的范围；
- 直方图除了保存划分阈值和当前bin内样本数以外还保存了当前bin内所有样本的一阶梯度和（一阶梯度和的平方的均值等价于均方损失）；
- 阈值的选取是按照直方图从小到大遍历，使用了上面的一阶梯度和，目的是得到划分之后△loss最大的特征及阈值。
Histogram 算法的优缺点：
- Histogram算法并不是完美的。由于特征被离散化后，找到的并不是很精确的分割点，所以会对结果产生影响。但在实际的数据集上表明，离散化的分裂点对最终的精度影响并不大，甚至会好一些。原因在于decision tree本身就是一个弱学习器，采用Histogram算法会起到正则化的效果，有效地防止模型的过拟合。
- 时间上的开销由原来的O(#data * #features)降到O(k * #features)。由于离散化，#bin远小于#data，因此时间上有很大的提升。
Histogram算法还可以进一步加速。一个叶子节点的Histogram可以直接由父节点的Histogram和兄弟节点的Histogram做差得到。一般情况下，构造Histogram需要遍历该叶子上的所有数据，通过该方法，只需要遍历Histogram的k个捅。速度提升了一倍。
决策树生长策略
在Histogram算法之上，LightGBM进行进一步的优化。首先它抛弃了大多数GBDT工具使用的按层生长 (level-wise)的决策树生长策略，而使用了带有深度限制的按叶子生长 (leaf-wise)算法。
XGBoost采用的是按层生长level（depth）-wise生长策略，能够同时分裂同一层的叶子，从而进行多线程优化，不容易过拟合；但不加区分的对待同一层的叶子，带来了很多没必要的开销。因为实际上很多叶子的分裂增益较低，没必要进行搜索和分裂。
LightGBM采用leaf-wise生长策略，每次从当前所有叶子中找到分裂增益最大（一般也是数据量最大）的一个叶子，然后分裂，如此循环。因此同Level-wise相比，在分裂次数相同的情况下，Leaf-wise可以降低更多的误差，得到更好的精度。Leaf-wise的缺点是可能会长出比较深的决策树，产生过拟合。因此LightGBM在Leaf-wise之上增加了一个最大深度的限制，在保证高效率的同时防止过拟合。
直方图差加速
LightGBM另一个优化是Histogram（直方图）做差加速。一个容易观察到的现象：一个叶子的直方图可以由它的父亲节点的直方图与它兄弟的直方图做差得到。通常构造直方图，需要遍历该叶子上的所有数据，但直方图做差仅需遍历直方图的k个桶。利用这个方法，LightGBM可以在构造一个叶子的直方图后，可以用非常微小的代价得到它兄弟叶子的直方图，在速度上可以提升一倍。