LightGBM算法

在学习了集成学习的一些基础算法之后，小编将继续介绍集成学习算法中比较热门的LightGBM，打起精神，跟着小编一起学习吧！

LightGBM

简介

GBDT (Gradient Boosting Decision Tree) 是机器学习中一个长盛不衰的模型，其主要思想是利用弱分类器（决策树）迭代训练以得到最优模型，该模型具有训练效果好、不易过拟合等优点。GBDT不仅在工业界应用广泛，通常被用于多分类、点击率预测、搜索排序等任务。

LightGBM(Light Gradient Boosting Machine) 是一个实现GBDT算法的框架，其主要是为了解决GBDT在海量数据遇到的问题，支持高效率的并行训练，并且具有更快的训练速度、更低的内存消耗、更好的准确率、支持分布式可以快速处理海量数据等优点。

缺点

在LightGBM提出之前，最有名的GBDT工具就是XGBoost了，它是基于预排序方法的决策树算法。这种构建决策树的算法基本思想是：

首先，对所有特征都按照特征的数值进行预排序。其次，在遍历分割点的时候用O(#data)的代价找到一个特征上的最好分割点。最后，在找到一个特征的最好分割点后，将数据分裂成左右子节点。

这样的预排序算法的优点是能精确地找到分割点。但是缺点也很明显：首先，空间消耗大。这样的算法需要保存数据的特征值，还保存了特征排序的结果（例如，为了后续快速的计算分割点，保存了排序后的索引），这就需要消耗训练数据两倍的内存。其次，时间上也有较大的开销，在遍历每一个分割点的时候，都需要进行分裂增益的计算，消耗的代价大。

最后，对cache优化不友好。在预排序后，特征对梯度的访问是一种随机访问，并且不同的特征访问的顺序不一样，无法对cache进行优化。同时，在每一层长树的时候，需要随机访问一个行索引到叶子索引的数组，并且不同特征访问的顺序也不一样，也会造成较大的cache miss。

优化

为了避免上述XGBoost的缺陷，并且能够在不损害准确率的条件下加快GBDT模型的训练速度，LightGBM在传统的GBDT算法上进行了如下优化：

1）基于Histogram的决策树算法；

2）单边梯度采样 Gradient-based One-Side Sampling (GOSS)；

3）互斥特征捆绑 Exclusive Feature Bundling (EFB)；

4）带深度限制的Leaf-wise的叶子生长策略；

5）直接支持类别特征(Categorical Feature)；

6）支持高效并行；

7）Cache命中率优化。

下面小编就从这七个方面详细介绍LightGBM优化算法。

基于Histogram的决策树算法

核心思想

将连续的特征值离散化成K个整数（bin数据），构造宽度为K的直方图，遍历训练数据，统计每个离散值在直方图中的累积统计量。在选取特征的分裂点的时候，只需要遍历排序直方图的离散值。

1）使用bin替代原始数据相当于增加了正则化；

2）使用bin很多数据的细节特征被放弃，相似的数据可能被划分到一起，数据之间的差异消失；

3）bin数量的选择决定了正则化的程度，K越少惩罚越严重，欠拟合风险越高。

具体算法如下图所示：

直方图做差加速

LightGBM另一个优化是Histogram（直方图）做差加速。一个叶子的直方图可以由它的父亲节点的直方图与它兄弟的直方图做差得到，在速度上可以提升一倍。通常构造直方图时，需要遍历该叶子上的所有数据，但直方图做差仅需遍历直方图的k个桶。在实际构建树的过程中，LightGBM还可以先计算直方图小的叶子节点，然后利用直方图做差来获得直方图大的叶子节点，这样就可以用非常微小的代价得到它兄弟叶子的直方图。

单边梯度采样

单边梯度采样( Gradient-based One-Side Sampling，GOSS)是一个样本的采样算法，核心作用是对训练集样本采样优化。核心思想如下为首先保留梯度较大的样本，然后对梯度较小的样本进行随机抽样，最后在计算增益时，对梯度较小的样本增加权重系数。

GOSS的具体算法如下图所示：

算法描述：

输入：训练数据，迭代步数d，大梯度数据的采样率a，小梯度数据的采样率b，损失函数和学习器的类型；

输出：训练好的强学习器；

1）根据样本点的梯度的绝对值进行降序排序；

2）对排序后的结果选取前a的样本生成一个大梯度样本点的子集；

3）对剩下的样本集合中的(1-a)个样本，随机的选取b个，生成一个小梯度样本点的集合；

4）将大梯度样本和采样的小梯度样本合并；

5）使用上述的采样的样本，学习一个新的弱学习器；

6）在新的弱学习器中，计算增益时将小梯度样本乘上一个权重系数；

7）重复（1）~（6）步骤直到达到规定的迭代次数或者收敛为止。

互斥特征捆绑

高维度的数据往往是稀疏的，这种稀疏性启发我们设计一种无损的方法来减少特征的维度。通常被捆绑的特征都是互斥的（即特征不会同时为非零值，像one-hot），这样两个特征捆绑起来才不会丢失信息。如果两个特征并不是完全互斥（部分情况下两个特征都是非零值），可以用一个指标对特征不互斥程度进行衡量，称之为冲突比率，当这个值较小时，我们可以选择把不完全互斥的两个特征捆绑，而不影响最后的精度，这就是互斥特征捆绑（Exclusive Feature Bundling ，EFB)。

具体算法如下图所示：

算法3的作用确定被捆绑的特征，算法4的作用是合并被捆绑特征。接下来小编将以下图为例详细介绍。

第一个表格是没做EFB的原表格。表格里有6个样本，每个样本有5个特征，前3个特征稀疏，后2个特征稠密。稠密特征不管，只看稀疏特征，目标是把这三个稀疏特征合并成一个新特征，并把这个新特征叫做Bundle。

当一行样本的3个稀疏特征中只有1个非零元素时，可以忽略0元素，只保留非零元素，这样就实现了3->1的降维。但是显然这样没办法实现1->3的还原，因为不清楚合并后得到的非零元素是哪个原始特征的，这就说明我们在合并时损失了一些信息。

可以通过数据分布范围内涵地表示合并后元素所属原特征。假设三个特征分布范围都为1~10，第一个特征不动，第二个特征错开第一个分布，全体元素在坐标轴上向右偏移10，第三个特征错开前两个特征，全体元素向右偏移20。这样就形成了箭头下方的第二个表格，每个元素可以根据大小范围判断属于哪个原特征。

读者们肯定注意到了样本3在合并的时候，有两个非零元素，不符合要求。LightGBM把这种情况定义为冲突。如果完全拒绝这种情况，那其实可以合并的特征会很少，所以没办法只能适当容忍冲突。

当几个特征冲突比例小的时候，影响不大，忽略冲突，把这几个特征叫做互斥特征；当冲突比例大的时候，不能忽略，EFB不适用。那么对于样本3这种冲突情况，以最后参与合并的特征为准，所以表格里是20+8而不是10+3。

叶子生长策略

在Histogram算法之上，LightGBM进行进一步地优化。首先它抛弃了大多数GBDT工具使用的按层生长(level-wise)的决策树生长策略，而使用了带有深度限制的按叶子生长(leaf-wise)算法。

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

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

直接支持类别特征

实际上大多数机器学习工具都无法直接支持类别特征，一般需要把类别特征，通过 one-hot 编码，转化到多维的0/1特征，降低了空间和时间的效率。但我们知道对于决策树来说并不推荐使用 one-hot 编码，尤其当类别特征中类别个数很多的情况下，会产生样本切分不平衡问题以及影响决策树的学习。

而类别特征的使用在实践中是很常见的。为了解决one-hot编码处理类别特征的不足，LightGBM优化了对类别特征的支持，可以直接输入类别特征，不需要额外的0/1展开。LightGBM采用many-vs-many的切分方式将类别特征分为两个子集，实现类别特征的最优切分。下图左边为基于one-hot编码进行分裂，右图为LightGBM基于many-vs-many进行分裂。

算法流程如下图所示，在枚举分割点之前，先把直方图按照每个类别对应的label均值进行排序；然后按照排序的结果依次枚举最优分割点。从下图可以看到类别的均值。当然，这个方法很容易过拟合，所以LightGBM里面还增加了很多对于这个方法的约束和正则化。

并行学习

特征并行

特征并行的主要思想是不同机器在不同的特征集合上分别寻找最优的分割点，然后在机器间同步最优的分割点。XGBoost使用的就是这种特征并行方法。这种特征并行方法有个很大的缺点：就是对数据进行垂直划分，每台机器所含数据不同，然后使用不同机器找到不同特征的最优分裂点，划分结果需要通过通信告知每台机器，增加了额外的复杂度。

LightGBM则不进行数据垂直划分，而是在每台机器上保存全部训练数据，在得到最佳划分方案后可在本地执行划分而减少了不必要的通信。

具体过程如下图所示。

数据并行

传统的数据并行策略主要为水平划分数据，让不同的机器先在本地构造直方图，然后进行全局的合并，最后在合并的直方图上面寻找最优分割点。这种数据划分有一个很大的缺点：通讯开销过大。

LightGBM在数据并行中使用分散规约 (Reduce scatter) 把直方图合并的任务分摊到不同的机器，降低通信和计算，并利用直方图做差，进一步减少了一半的通信量。

具体过程如下图所示:

投票并行

基于投票的数据并行则进一步优化数据并行中的通信代价，使通信代价变成常数级别。在数据量很大的时候，使用投票并行的方式只合并部分特征的直方图从而达到降低通信量的目的，可以得到非常好的加速效果。

大致步骤为两步：

1）本地找出Top K特征，并基于投票筛选出可能是最优分割点的特征；

2）合并时只合并每个机器选出来的特征。

具体过程如下图所示：

Cache命中率优化

XGBoost对cache优化不友好，如下图所示。在预排序后，特征对梯度的访问是一种随机访问，并且不同的特征访问的顺序不一样，无法对cache进行优化。同时，在每一层长树的时候，需要随机访问一个行索引到叶子索引的数组，并且不同特征访问的顺序也不一样，也会造成较大的cache miss。为了解决缓存命中率低的问题，XGBoost 提出了缓存访问算法进行改进。

而LightGBM 所使用直方图算法对Cache天生友好：

首先，所有的特征都采用相同的方式获得梯度（区别于XGBoost的不同特征通过不同的索引获得梯度），只需要对梯度进行排序并可实现连续访问，大大提高了缓存命中率；

其次，因为不需要存储行索引到叶子索引的数组，降低了存储消耗，而且也不存在Cache Miss的问题。

今天学习就到这里啦，欢迎提问！非常感谢各位同学们看到这里，想了解更多机器学习相关知识，可以持续关注本系列哦！

文案｜朱琪

指导老师｜曹菁菁 赵强伟

排版 | 邓诗怡