LightGBM模型详解

1.背景

  LightGBM 是微软开发的 boosting 集成模型，和 XGBoost 一样是对 GBDT 的优化和高效实现，原理有一些相似之处，但它很多方面比 XGBoost 有着更为优秀的表现。官方给出的这个工具库模型的优势如下：

• 更快的训练效率
• 低内存使用
• 更高的准确率
• 支持并行化学习
• 可处理大规模数据
• 支持直接使用 category 特征

  下图是一组实验数据，LightGBM比XGBoost快将近 $10$ 倍，内存占用率大约为XGBoost的 $1/6$，并且准确率也有提升。

2.LightGBM 动机

  常用的机器学习算法，例如神经网络等算法，都可以以mini-batch的方式训练，训练数据的大小不会受到内存限制。而GBDT在每一次迭代的时候，都需要遍历整个训练数据多次。

• 如果把整个训练数据装进内存则会限制训练数据的大小；
• 如果不装进内存，反复地读写训练数据又会消耗非常大的时间。

尤其面对工业级海量的数据，普通的GBDT算法是不能满足其需求的。 LightGBM 提出的主要原因之一，就是为了解决上述大数据量级下的 GBDT 训练问题，以便工业实践中能支撑大数据量并保证效率。

3.XGBoost 优缺点

3.1 精确贪心算法

  每轮迭代时，都需要遍历整个训练数据多次。如果把整个训练数据装进内存则会限制训练数据的大小；如果不装进内存，反复地读写训练数据又会消耗非常大的时间。
Gain= 1 2[ ( ∑ i∈ I L gi ) 2 ∑ i∈ I Lh i+λ + ( ∑ i∈ I R gi ) 2 ∑ i∈ I Rh i+λ − ( ∑ i∈ I I gi ) 2 ∑ i∈ I Ih i+λ ]−γGain= \frac{1}{2}\Big[\frac{(\sum_{i\in I_L} gi)^2}{\sum_{i\in I_L}h_i+\lambda} + \frac{(\sum_{i\in I_R} gi)^2}{\sum_{i\in I_R}h_i+\lambda}-\frac{(\sum_{i\in I_I} gi)^2}{\sum_{i\in I_I}h_i+\lambda}\Big] – \gamma Gain=21​[∑i∈IL​​hi​+λ(∑i∈IL​​gi)2​+∑i∈IR​​hi​+λ(∑i∈IR​​gi)2​−∑i∈II​​hi​+λ(∑i∈II​​gi)2​]−γ

• 优点：可以找到精确的划分条件。
• 缺点：计算量巨大、内存占用巨大、易产生过拟合。

3.2 Level-wise生长方式

  XGBoost 采用 Level-wise 的增长策略：基于层进行生长，直到达到停止条件。这种增长策略方便并行计算每一层的分裂节点，提高了训练速度，但同时也因为节点增益过小增加了很多不必要的分裂，增加了计算量。

• 优点：可以使用多线程、可以加速精确贪心算法。
• 缺点：效率低下，可能产生不必要的叶结点。

3.3 对cache优化不友好

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

4.LightGBM 优化点

lightGBM主要有以下特点：

• 基于Histogram的决策树算法
• 带深度限制的Leaf-wise的叶子生长策略
• 直方图做差加速
• 直接支持类别特征(Categorical Feature)
• Cache命中率优化
• 基于直方图的稀疏特征优化
• 多线程优化
  

4.1 决策树算法

4.1.1 XGBoost ：Pre-sorted算法

XGBoost 使用的是 Pre-sorted 算法，能够更精确的找到数据分隔点。

• 首先，对所有特征按数值进行预排序。
• 其次，在每次的样本分割时，用 $O(\#data)$ 的代价找到每个特征的最优分割点。
• 最后，找到最后的特征以及分割点，将数据分裂成左右两个子节点。

这种pre-sorting算法能够准确找到分裂点，但是在空间和时间上有很大的开销。

• 由于需要对特征进行预排序并且需要保存排序后的索引值（为了后续快速的计算分裂点），因此内存需要训练数据的两倍。
• 在遍历每一个分割点的时候，都需要进行分裂增益的计算，消耗的代价大。

4.1.2 LightGBM ：直方图算法

  LightGBM 使用的是直方图算法（histogram algorithm），占用的内存更低，数据分割的复杂度更低。 其思想是将连续的浮点特征离散成 $k$ 个离散值，并构造宽度为 $k$ 的Histogram。然后遍历训练数据，统计每个离散值在直方图中的累计统计量。在进行特征选择时，只需要根据直方图的离散值，遍历寻找最优的分割点。

4.1.2.1 内存优化

  直方图算法可以很大程度降低内存消耗，它不仅不需要额外存储预排序的结果，还可以只保存特征离散化后的值；一般用 $8$ 位整型存储就足够了， 内存消耗可以降低为原来的 $1/8$ 。

4.1.2.2 计算量优化

  在计算上的代价也大幅降低，预排序算法每遍历一个特征值就需要计算一次分裂的增益，而直方图算法只需要计算 $k$ 次（$k$ 可以认为是常数），时间复杂度从 $O(\#data\ast \#feature)$ 优化到$O(k\ast \#features)$。

4.1.2.3 Histogram algorithm的理解

  Histogram algorithm应该翻译为直方图算法，直方图算法的思想也很简单，首先将连续的浮点数据转换为bin数据，具体过程是首先确定对于每一个特征需要多少的桶bin，然后均分，将属于该桶的样本数据更新为bin的值，最后用直方图表示。（看起来很高大上，其实就是直方图统计，最后我们将大规模的数据放在了直方图中）

直方图算法有几个需要注意的地方：

• 使用 bin 替代原始数据相当于增加了正则化；
• 使用 bin 意味着很多数据的细节特征被放弃了，相似的数据可能被划分到相同的桶中，这样的数据之间的差异就消失了；
• bin 数量选择决定了正则化的程度，bin 越少惩罚越严重，欠拟合风险越高。
• 构建直方图时不需要对数据进行排序（比XGBoost快），因为预先设定了 bin 的范围。
• 直方图保存「划分阈值」、「当前 bin 内样本数」、「当前 bin 内所有样本的一阶梯度和（一阶梯度和的平方的均值等价于均方损失）」。
• 阈值的选取是按照直方图从小到大遍历，使用了上面的一阶梯度和，目的是得到划分之后 $ △loss $ 最大的特征及阈值。

4.1.2.4 Histogram 算法的优缺点

• Histogram算法并不是完美的。由于特征被离散化后，找到的并不是很精确的分割点，所以会对结果产生影响。但在实际的数据集上表明，离散化的分裂点对最终的精度影响并不大，甚至会好一些。原因在于decision tree本身就是一个弱学习器，采用Histogram算法会起到正则化的效果，有效地防止模型的过拟合。
• 时间上的开销由原来的 $O(\#data\ast \#features)$ 降到 $O(k\ast \#features)$。由于离散化，$\#bin$ 远小于 $\#data$，因此时间上有很大的提升。
• Histogram算法还可以进一步加速。一个叶子节点的Histogram可以直接由父节点的Histogram和兄弟节点的Histogram做差得到。一般情况下，构造Histogram需要遍历该叶子上的所有数据，通过该方法，只需要遍历Histogram的 $k$ 个捅。速度提升了一倍。

4.2 决策树生长策略

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

4.2.1 XGBoost ：Level-wise

  XGBoost采用的是按层生长 level-wise 生长策略，能够同时分裂同一层的叶子，从而进行多线程优化，不容易过拟合；但不加区分的对待同一层的叶子，带来了很多没必要的开销。因为实际上很多叶子的分裂增益较低，没必要进行搜索和分裂。

4.2.2 LightGBM ：Leaf-wise

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

4.3 直方图差加速

  LightGBM另一个优化是Histogram（直方图）做差加速。一个容易观察到的现象：一个叶子的直方图可以由它的父亲节点的直方图与它兄弟的直方图做差得到。通常构造直方图，需要遍历该叶子上的所有数据，但直方图做差仅需遍历直方图的 $k$ 个桶。利用这个方法，LightGBM可以在构造一个叶子的直方图后，可以用非常微小的代价得到它兄弟叶子的直方图，在速度上可以提升一倍。

4.4 类别型特征支持

  实际上大多数机器学习工具都无法直接支持类别特征，一般需要把类别特征，转化one-hot 特征，降低了空间和时间的效率。而类别特征的使用是在实践中很常用的。基于这个考虑，LightGBM优化了对类别特征的支持，可以直接输入类别特征，不需要额外的 0/1展开。并在决策树算法上增加了类别特征的决策规则。

4.4.1 树模型与one-hot 编码

  one-hot编码是处理类别特征的一个通用方法，然而在树模型中，这可能并不一定是一个好的方法，尤其当类别特征中类别个数很多的情况下。主要的问题是：

Q：可能无法在这个类别特征上进行切分(即浪费了这个特征)。

使用one-hot编码的话，意味着在每一个决策节点上只能使用one vs rest（例如是不是狗，是不是猫等）的切分方式。当类别值很多时，每个类别上的数据可能会比较少，这时候切分会产生不平衡，这意味着切分增益也会很小（比较直观的理解是，不平衡的切分和不切分没有区别）。

Q：会影响决策树的学习。

因为就算可以在这个类别特征进行切分，也会把数据切分到很多零碎的小空间上，如图左边所示。而决策树学习时利用的是统计信息，在这些数据量小的空间上，统计信息不准确，学习会变差。但如果使用下图右边的分裂方式，数据会被切分到两个比较大的空间，进一步的学习也会更好。

4.4.3 LightGBM处理分类特征

  为了解决one-hot编码处理类别特征的不足。LightGBM采用了Many vs many的切分方式，实现了类别特征的最优切分。 用LightGBM可以直接输入类别特征，并产生上图右边的效果。在1个 $k$ 维的类别特征中寻找最优切分，朴素的枚举算法的复杂度是 O ( 2k)O(2^k)O(2k)，而LightGBM采用了如On Grouping For Maximum Homogeneity的方法实现了 $O(klogk)$的算法。

基本流程

• ① 在枚举分割点之前，先把直方图按每个类别的均值进行排序。

• ② 接着按照均值的结果依次枚举最优分割点。

从上图可以看到，$Sum(y)/Count(y)$ 为类别的均值。当然，这个方法很容易过拟合，所以在LGBM中加入了很多对这个方法的约束和正则化。 下图是一个简单的对比实验，可以看到该最优方法在AUC上提升了 $1.5$ 个点，并且时间只多了 $20\%$。

求解类别型特征的最优切分的具体流程如下：

① 离散特征建立直方图的过程

统计该特征下每一种离散值出现的次数，并从高到低排序，并过滤掉出现次数较少的特征值。然后为每一个特征值，建立一个 bin 容器，对于在 bin 容器内出现次数较少的特征值直接过滤掉，不建立 bin 容器。

② 计算分裂阈值的过程

• 先看该特征下划分出的 bin 容器的个数，如果 bin 容器的数量小于 $4$ ，直接使用 one vs other 方式，逐个扫描每一个 bin 容器，找出最佳分裂点。

• 对于 bin 容器较多的情况，先进行过滤，只让子集合较大的 bin 容器参加划分阈值计算，对每一个符合条件的 bin 容器进行公式计算，得到一个值，根据该值对 bin 容器从小到大进行排序，然后分从左到右、从右到左进行搜索，得到最优分裂阈值。公式如下：
  该bin容器下所有样本的一阶梯度之和该bin容器下所有样本的二阶梯度之和 +正则项(参数ca t smooth )\frac{该bin容器下所有样本的一阶梯度之和}{该bin容器下所有样本的二阶梯度之和}+正则项(参数cat_{smooth}) 该bin容器下所有样本的二阶梯度之和该bin容器下所有样本的一阶梯度之和​+正则项(参数catsmooth​)
  这里为什么不是label的均值呢？其实上例中只是为了便于理解，只针对了学习一棵树且是回归问题的情况， 这时候一阶导数是Y, 二阶导数是1)，得到一个值，根据该值对bin容器从小到大进行排序，然后分从左到右、从右到左进行搜索，得到最优分裂阈值。

  • 没有搜索所有的bin容器，而是设定了一个搜索bin容器数量的上限值，程序中设定是 $32$，即参数 max_num_cat。
  • LightGBM中对离散特征实行的是many vs many 策略，这 $32$ 个bin中最优划分的阈值的左边或者右边所有的bin容器就是一个many集合，而其他的bin容器就是另一个many集合。

③ 对于连续特征，划分阈值只有一个。对于离散值可能会有多个划分阈值，每一个划分阈值对应着一个 bin 容器编号。

当使用离散特征进行分裂时，只要数据样本对应的 bin 容器编号在这些阈值对应的 bin 集合之中，这条数据就加入分裂后的左子树，否则加入分裂后的右子树。

4.5 并行支持与优化

LightGBM 原生支持并行学习，目前支持「特征并行」和「数据并行」的两种，LightGBM 针对这两种并行方法都做了优化。

• 特征并行：在不同机器在不同的特征集合上分别寻找最优的分割点，然后在机器间同步最优的分割点。
• 数据并行：让不同的机器先在本地构造直方图，然后进行全局的合并，最后在合并的直方图上面寻找最优分割点。

4.5.1 特征并行

LightGBM 在特征并行算法中，通过在本地保存全部数据避免对数据切分结果的通信。

4.5.2 数据并行

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

基于投票的数据并行则进一步优化数据并行中的通信代价，使通信代价变成常数级别。在数据量很大的时候，使用投票并行可以得到非常好的加速效果。

4.6 网络通信优化

  XGBoost由于采用pre-sorted算法，通信代价非常大，所以在并行的时候也是采用histogram算法；LightGBM采用的histogram算法通信代价小，通过使用集合通信算法，能够实现并行计算的线性加速。

5.LightGBM原理

  提升树是利用加模型与前向分布算法实现学习的优化过程，它有一些高效实现，如XGBoost, pGBRT，GBDT(Gradient Boosting Decision Tree)等。

• GBDT采用负梯度作为划分的指标(信息增益) XGBoost则利用到二阶导数

二者的不足点： 计算信息增益需要扫描所有样本，从而找到最优划分点。

在面对大量数据或者特征维度很高时，它们的效率和扩展性很难使人满意。解决这个问题的直接方法就是减少特征量和数据量而且不影响精确度，有部分工作根据数据权重采样来加速booisting的过程，但由于GBDT没有样本权重不能应用。 微软开源的LightGBM(基于GBDT的)则很好的解决这些问题，它主要包含两个算法： 单边梯度采样，Gradient-based One-Side Sampling(GOSS) 和 互斥特征绑定，Exclusive Feature Bundling(EFB)。

5.1 单边梯度采样

  GOSS(从减少样本角度)：排除大部分小梯度的样本，仅用剩下的样本计算信息增益。GBDT虽然没有数据权重，但每个数据实例有不同的梯度，根据计算信息增益的定义，梯度大的实例对信息增益有更大的影响，因此在下采样时，我们应该尽量保留梯度大的样本(预先设定阈值，或者最高百分位间)，随机去掉梯度小的样本。我们证明此措施在相同的采样率下比随机采样获得更准确的结果，尤其是在信息增益范围较大时。

• 在AdaBoost中，样本权重是数据样本重要性的指标。然而在GBDT中没有原始样本权重，不能应用权重采样。
• GBDT中每个数据都有不同的梯度值，对采样十分有用，即实例的梯度小，实例训练误差也就较小，已经被学习得很好了，直接想法就是丢掉这部分梯度小的数据。然而这样做会改变数据的分布，将会影响训练的模型的精确度
• GOSS保留所有的梯度较大的实例，在梯度小的实例上使用随机采样
• 为了抵消对数据分布的影响，计算信息增益的时候，GOSS对小梯度的数据引入常量乘数。
• GOSS(基于梯度的边采样)的做法:
  • 根据数据的梯度绝对值排序，选取 $topa\ast 100\%$ 个样本
  • 在剩余的数据中随机采样 $b\ast 100\%$ 个样本
  • 计算信息增益时为采样出的小梯度数据乘以 $(1-a)/b$ (小梯度样本总数/随机采样出的小梯度样本数量)

  通过采样的方式，选出了我们的样本，两个梯度大的 $6$ 号和 $7$ 号，然后又从剩下的样本里面随机选了 $2$ 个梯度小的，$4$ 号和 $2$ 号，这时候我们重点看看基于采样样本的估计直方图长什么样子，毕竟我们从 $8$ 个里面选出了四个，如果直接把另外四个给删掉的话，这时候会改变数据的分布，但应该怎么做呢？也就是乘上1 − ab \frac{1-a}{b}b1−a​来放大梯度小的样本的权重到底是怎么算的？看下图：

  梯度小的样本乘上相应的权重之后，我们在基于采样样本的估计直方图中可以发现Ni的总个数依然是 $8$ 个， 虽然 $6$ 个梯度小的样本中去掉了 $4$ 个，留下了两个。但是这 $2$ 个样本在梯度上和个数上都进行了 $3$ 倍的放大，所以可以防止采样对原数数据分布造成太大的影响， 这也就是论文里面说的将更多的注意力放在训练不足的样本上的原因。GOSS的感觉就好像一个公寓里本来住了 $10$ 个人，感觉太挤了，赶走了 $6$ 个人，但是剩下的人要分摊他们 $6$ 个人的房租。

5.2 互斥特征绑定

  EFB(从减少特征角度)：捆绑互斥特征，也就是他们很少同时取非零值(也就是用一个合成特征代替)。通常真实应用中，虽然特征量比较多，但是由于特征空间十分稀疏，是否可以设计一种无损的方法来减少有效特征呢？特别在稀疏特征空间上，许多特征几乎是互斥的（例如许多特征不会同时为非零值，像one-hot），我们可以捆绑互斥的特征。最后，我们将捆绑问题归约到图着色问题，通过贪心算法求得近似解。

EBF的算法步骤如下：

• 将特征按照非零值的个数进行排序
• 计算不同特征之间的冲突比率
• 遍历每个特征并尝试合并特征，使冲突比率最小化。

看到上面的这些特征够稀疏了吧（大部分都是0），而每一个特征都只有一个训练样本是非0且都不是同一个训练样本，这样的话特征之间也没有冲突了。这样的情况就可以把这四个特征捆绑成一个，这样是不是维度就减少 。

所以互斥特征捆绑算法（Exclusive Feature Bundling）是从减少特征的角度去帮助Lightgbm更快， 它指出如果将一些特征进行融合绑定，则可以降低特征数量。

Q：哪些特征应该绑在一起？

• 首先将所有的特征看成图的各个顶点，将不相互独立的特征用一条边连起来，边的权重就是两个相连接的特征的总冲突值（也就是这两个特征上不同时为0的样本个数）。
• 然后按照节点的度对特征降序排序， 度越大，说明与其他特征的冲突越大
• 对于每一个特征， 遍历已有的特征簇，如果发现该特征加入到特征簇中的矛盾数不超过某一个阈值，则将该特征加入到该簇中。如果该特征不能加入任何一个已有的特征簇，则新建一个簇，将该特征加入到新建的簇中。

上面这个过程的时间复杂度其实是O(#feature s 2)O(\#features^2) O(#features2)的，因为要遍历特征，每个特征还要遍历所有的簇， 在特征不多的情况下还行，但是如果特征维度很大，就不好使了。所以为了改善效率，可以不建立图，而是将特征按照非零值个数进行排序，因为更多的非零值的特征会导致更多的冲突，所以跳过了上面的第一步，直接排序然后第三步分簇。

Q：特征绑在一起之后，特征值应该如何确定呢？

键就是原始特征能从合并的特征中分离出来

绑定几个特征在同一个bundle里需要保证绑定前的原始特征的值可以在bundle里面进行识别，考虑到直方图算法将连续的值保存为离散的bins，我们可以使得不同特征的值分到簇中的不同bins里面去，这可以通过在特征值中加入一个偏置常量来解决。

比如，我们把特征A和B绑定到了同一个bundle里面， A特征的原始取值区间[0,10), B特征原始取值区间[0,20), 这样如果直接绑定，那么会发现我从bundle里面取出一个值5， 就分不出这个5到底是来自特征A还是特征B了。所以我们可以再B特征的取值上加一个常量10转换为[10, 30)，这样绑定好的特征取值就是[0,30), 我如果再从bundle里面取出5， 就一下子知道这个是来自特征A的。这样就可以放心的融合特征A和特征B了。看下图：

结合使用 GOSS 和 EFB 的 GBDT 算法就是 LightGBM。

6.LightGBM实例

6.1 sklearn接口形式的LightGBM示例

import lightgbm as lgbfrom sklearn.metrics import mean_squared_errorfrom sklearn.model_selection import GridSearchCVfrom sklearn.datasets import load_irisfrom sklearn.model_selection import train_test_split# 加载数据iris = load_iris()data = iris.datatarget = iris.targetX_train, X_test, y_train, y_test = train_test_split(data, target, test_size=0.2)# 创建模型，训练模型gbm = lgb.LGBMRegressor(objective='regression', num_leaves=31, learning_rate=0.05, n_estimators=20)gbm.fit(X_train, y_train, eval_set=[(X_test, y_test)], eval_metric='l1', early_stopping_rounds=5)# 测试机预测y_pred = gbm.predict(X_test, num_iteration=gbm.best_iteration_)# 模型评估print('The rmse of prediction is:', mean_squared_error(y_test, y_pred) ** 0.5)# feature importancesprint('Feature importances:', list(gbm.feature_importances_))# 网格搜索，参数优化estimator = lgb.LGBMRegressor(num_leaves=31)param_grid = {'learning_rate': [0.01, 0.1, 1],'n_estimators': [20, 40]}gbm = GridSearchCV(estimator, param_grid)gbm.fit(X_train, y_train)print('Best parameters found by grid search are:', gbm.best_params_)

6.2 原生形式使用lightgbm

import lightgbm as lgbfrom sklearn.metrics import mean_squared_errorfrom sklearn.datasets import load_irisfrom sklearn.model_selection import train_test_splitiris = load_iris()data = iris.datatarget = iris.targetX_train, X_test, y_train, y_test = train_test_split(data, target, test_size=0.2)# 创建成lgb特征的数据集格式lgb_train = lgb.Dataset(X_train, y_train)lgb_eval = lgb.Dataset(X_test, y_test, reference=lgb_train)# 将参数写成字典下形式params = {'task': 'train','boosting_type': 'gbdt',# 设置提升类型'objective': 'regression',# 目标函数'metric': {'l2', 'auc'},# 评估函数'num_leaves': 31,# 叶子节点数'learning_rate': 0.05,# 学习速率'feature_fraction': 0.9,# 建树的特征选择比例'bagging_fraction': 0.8,# 建树的样本采样比例'bagging_freq': 5,# k 意味着每 k 次迭代执行bagging'verbose': 1# 0 显示信息}# 训练 cv and traingbm = lgb.train(params, lgb_train, num_boost_round=20, valid_sets=lgb_eval, early_stopping_rounds=5)# 保存模型到文件gbm.save_model('model.txt')# 预测数据集y_pred = gbm.predict(X_test, num_iteration=gbm.best_iteration)# 评估模型print('The rmse of prediction is:', mean_squared_error(y_test, y_pred) ** 0.5)

7.参数速查

参考链接：LightGBM使用