LightGBM 由微软提出，主要用于解决 GDBT 在海量数据中遇到的问题，以便其可以更好更快地用于工业实践中，其相对 XGBoost 具有训练速度快、内存占用低的特点。
LightGBM与XGBoost相比，主要有以下几个优势：
(1) 更快的训练速度。
(2) 更低的内存消耗。
(3) 更好的准确率。
(4) 分布式支持，可快速处理海量数据。
1.1 LightGBM算法思想
LightGBM与XGBoost相比，主要有以下几个改进：
(1) 基于梯度的单边采样算法(Gradient-based One-Side Sampling, GOSS)；
(2) 互斥特征捆绑算法(Exclusive Feature Bundling, EFB)；
(3) 直方图算法(Histogram)；
(4) 基于最大深度的 Leaf-wise 的垂直生长算法。
可以用公式来表示两者区别：
LightGBM = XGBoost + GOSS + EFB+ Histogram
1.基于梯度的单边采样算法(Gradient-based One-Side Sampling, GOSS)
GOSS 算法的主要思想是通过对样本采样的方法来减少计算目标函数增益时候的复杂度。
GOSS 算法保留了梯度大的样本，并对梯度小的样本进行随机抽样，为了不改变样本的数据分布，在计算增益时为梯度小的样本引入一个常数进行平衡。如果一个样本的梯度很小，说明该样本的训练误差很小，或者说该样本已经得到了很好的训练(Well-Trained)。
我们可以看到 GOSS 事先基于梯度的绝对值对样本进行排序(无需保存排序后结果)，然后拿到前的梯度大的样本，和总体样本的，在计算增益时，通过乘上来放大梯度小的样本的权重。一方面算法将更多的注意力放在训练不足的样本上，另一方面通过乘上权重来防止采样对原始数据分布造成太大的影响。
GOSS 算法思路：
输入：训练数据，迭代步数，大梯度数据的采样率，小梯度数据的采样率，损失函数和若学习器的类型(一般为决策树)
输出：训练好的强学习器
(1) 根据样本点的梯度的绝对值对它们进行降序排序；
(2) 对排序后的结果选取前
的样本生成一个大梯度样本点的子集；
(3) 对剩下的样本集合的样本，随机的选取个样本点，生成一个小梯度样本点的集合；
(4) 将大梯度样本和采样的小梯度样本合并；
(5) 将小梯度样本乘上一个权重系数；
(6) 使用上述的采样的样本，学习一个新的弱学习器；
(7) 不断地重复(1)~(6)步骤直到达到规定的迭代次数或者收敛为止。
对图1中的数据进行分箱操作，得到如图2所示的结果。
图2 分箱操作，分成了bin1、bin2和bin3排序完了之后，我们就选出个梯度大的，然后从剩下的那些样本里面选出个梯度小的：
这里是8个样本，所以，，
即先选出2个梯度大的样本，然后从剩下的里面随机选出2个梯度小的样本，图3中，选取两个大的(样本序号6、样本序号7)，然后随机选择两个小的样本(样本序号2、样本序号4)。
图4 GOSS的结果2.互斥特征捆绑算法(Exclusive Feature Bundling, EFB)
高维特征往往是稀疏的，而且特征间可能是相互排斥的(如两个特征不同时取非零值)，如果两个特征并不完全互斥(如只有一部分情况下是不同时取非零值)，可以用互斥率表示互斥程度。EFB算法指出如果将一些特征进行融合绑定，则可以降低特征数量。
原始论文给出特征合并算法，其关键在于原始特征能从合并的特征中分离出来。
举例说明：
如图5，假设 Bundle中有两个特征值，A取值为[0,10]，B取值为[0,20]，为了保证特征A、B的互斥性，我们可以给特征B添加一个偏移量转换为C[10,30]，Bundle后的特征取值为[0,30]，这样便实现了特征合并。
图5 EFB工作流程3.直方图算法(Histogram)
直方图算法的基本思想是将连续的特征离散化为个离散特征，同时构造一个宽度为的直方图用于统计信息(含有个bin)。利用直方图算法我们无需遍历数据，只需要遍历个 bin即可找到最佳分裂点。计算方法可以见图6。
图7 直方图分箱操作如图7所示，数据被分为3个bin，分别计算bin样本的之和、bin内所有样本的一阶导之和以及bin内所有样本的二阶导之和。
直方图加速的方法：在构建叶节点的直方图时，我们还可以通过父节点的直方图与相邻叶节点的直方图相减的方式构建，从而减少了一半的计算量。即：一个叶子节点的直方图可以由它的父亲节点的直方图与其兄弟的直方图做差得到。如节点分裂成两个时，右边叶子节点的直方图等于其父节点的直方图减去左边叶子节点的直方图。从而大大减少构建直方图的计算量。
直方图算法还可以进一步加速：一个叶子节点的直方图可以由它的父亲节点的直方图与其兄弟的直方图做差得到，工作流程见图8，这里的右叶子节点的直方图，由父节点的直方图减去左叶子节点的直方图得到。
图8 直方图做差操作直方图算法还可以进一步加速：一个叶子节点的直方图可以由它的父亲节点的直方图与其兄弟的直方图做差得到。图9是一个直方图做差的例子，计算非常简单。
图9 直方图做差的案例4.基于最大深度的 Leaf-wise 的垂直生长算法
在建树的过程中有两种策略：
Level-wise：基于层进行生长，直到达到停止条件；
Leaf-wise：每次分裂增益最大的叶子节点，直到达到停止条件。
图10 建树过程的两种方法：Level-wise和Leaf-wise图10中，上图是XGBoost的建树过程，下图是LightGBM的建树过程，XGBoost 采用 Level-wise 的增长策略，方便并行计算每一层的分裂节点，提高了训练速度，但同时也因为节点增益过小增加了很多不必要的分裂，降低了计算量；LightGBM 采用 Leaf-wise 的增长策略减少了计算量，配合最大深度的限制防止过拟合，由于每次都需要计算增益最大的节点，所以无法并行分裂。
1.2 LightGBM算法总结
总结下 LightGBM 相对于 XGBoost 的优点，从内存和速度两方面进行介绍。
1.内存更小
(1) XGBoost 使用预排序后需要记录特征值及其对应样本的统计值的索引，而 LightGBM 使用了直方图算法将特征值转变为 bin 值，且不需要记录特征到样本的索引，将空间复杂度从降低为
，极大的减少了内存消耗；
(2) LightGBM 采用了直方图算法将存储特征值转变为存储 bin 值，降低了内存消耗；
(3) LightGBM 在训练过程中采用互斥特征捆绑算法减少了特征数量，降低了内存消耗。
2.速度更快
(1) LightGBM 采用了直方图算法将遍历样本转变为遍历直方图，极大的降低了时间复杂度；
(2) LightGBM 在训练过程中采用单边梯度算法过滤掉梯度小的样本，减少了大量的计算；
(3) LightGBM 采用了基于 Leaf-wise 算法的增长策略构建树，减少了很多不必要的计算量；
(4) LightGBM 采用优化后的特征并行、数据并行方法加速计算，当数据量非常大的时候还可以采用投票并行的策略；
(5) LightGBM 对缓存也进行了优化，增加了缓存命中率。
