本文记录的目的是方便自己学习和复习，有误之处请谅解，欢迎指出。
LightGBM它和xgboost一样是对GBDT的高效实现，很多方面会比xgboost表现的更为优秀。GBDT采用负梯度作为划分的指标，XGBoost则利用到二阶导数。他们共同的不足是，计算信息增益需要扫描所有样本，从而找到最优划分点。在面对大量数据或者特征维度很高时，他们的效率和扩展性很难使人满意。
算法流程
LightGBM算法流程与GBDT、XGBoost基本类似，主要在几个地方做了加速改进。
改进点：
1）采样改进
LightGBM使用GOSS算法采样。
GOSS（基于梯度的单边采样）方法的主要思想就是，梯度大的样本点在信息增益的计算上扮演着主要的作用，也就是说这些梯度大的样本点会贡献更多的信息增益，因此为了保持信息增益评估的精度，当我们对样本进行下采样的时候保留这些梯度大的样本点，而对于梯度小的样本点按比例进行随机采样即可。
GOSS采样过程：
（1）根据样本点的梯度的绝对值对它们进行降序排序；
（2）对排序后的结果选取前a*100%的样本生成一个大梯度样本点的子集；
（3）剩下样本集合随机的选取b*（1-a）*100%个样本点，生成一个小梯度样本点的集合；
（4）将大梯度样本和小梯度样本合并；
（5）将小梯度样本乘上一个权重系数
（6）使用上述的采样的样本，学习一个新的弱学习器；
2）特征融合
LightGBM对特征进行了融合处理，加快训练速度。EFB算法。
通常在实际中高纬度的数据往往都是稀疏数据（如one-hot编码），这使我们有可能设计一种几乎无损的方法来减少有效特征的数量。尤其，在稀疏特征空间中许多特征都是互斥的（互斥表示不同时取非0的特征），我们可以安全的将互斥特征绑定在一起形成一个特征，从而减少特征维度。
以如下为例：假设现在有13个样本，每个样本有四个特征A,B,C,D,可以看到这很稀疏了吧（左图），那么怎么合并呢？很简单将ABCD捆绑为一个特征M就是右图
由于基于直方图的算法存储的是离散的bins而不是连续的特征值，我们可以通过让互斥特征驻留在不同的bins中来构造feature bundle。这可以通过增加特征原始值的偏移量来实现。比如，假设我们有两个特征，特征A的取值范围是[0,10)，而特征B的取值范围是[0,20)，我们可以给特征B增加偏移量10，使得特征B的取值范围为[10, 30)，最后合并特征A和B，形成新的特征，取值范围为[0,30)来取代特征A和特征B。
3）特征直方图
直方图算法是先把连续的浮点特征值离散化成k个整数，同时构造一个宽度为k的直方图。遍历数据时，根据离散化后的值作为索引在直方图中累积统计量，当遍历一次数据后，直方图累积了需要的统计量，然后根据直方图的离散值，遍历寻找最优的分割点。
优点如下：
（1）直方图只需对直方图统计量计算信息增益，相比较于预排序算法每次都遍历所有的值，信息增益的计算量要小很多
（2）通过利用叶节点的父节点和相邻节点的直方图的相减来获得该叶节点的直方图，从而减少构建直方图次数，提升效率
（3）存储直方图统计量所使用的内存远小于预排序算法
4）Leaf-wise建树
决策树有两种生长方式：Leaf-wise和Level-wise。大部分决策树的学习算法通过 level-wise 策略生长树，即一次分裂同一层的叶子，不加区分的对待同一层的叶子，而实际上很多叶子的分裂增益较低没必要进行分裂，带来了没必要的开销。
LightGBM 通过 leaf-wise (best-first)策略来生长树。它将选取具有最大信息增益最大的叶节点来生长。 leaf-wise 算法可以比 level-wise 算法减少更多的损失。当数据较小的时候，leaf-wise 可能会造成过拟合。 所以，LightGBM 可以利用额外的参数 max_depth 来限制树的深度并避免过拟合。
5）并行处理
（1）特征并行
在数据量很大时，传统并行方法无法有效地对特征进行并行，LightGBM 做了一些改变：不再垂直划分数据，即每个Worker都持有全部数据。 因此，LighetGBM中没有数据划分结果之间通信的开销，各个Worker都知道如何划分数据。 而且，样本量也不会变得更大，所以，使每个机器都持有全部数据是合理的。
LightGBM 中特征并行的流程：
a、每个Worker都在本地特征集上寻找最佳划分点｛特征， 阈值｝；
b、本地进行各个划分的通信整合并得到最佳划分；
c、执行最佳划分。
（2）数据并行
在数据并行中使用分散规约(Reduce scatter)把直方图合并的任务分摊到不同的机器，降低通信和计算，并利用树节点之间的关系直方图做差，进一步减少了一半的通信量。
