LightGBM简介

LightGBM是GBDT算法地实现框架之一，设计的初衷是并行、高效。特点是训练速度快、内存消耗小、可并行运算、支持类别变量。

LightGBM优化点

直方图算法

不同于XGBoost的预排序，LightGBM将区间离散化，划分为桶（bin），确定每个样本属于哪个桶。在遍历数据找最优划分点时，只需要遍历每个桶即可。

在这里插入图片描述

XGBoost预排序算法每遍历一个特征值就需要计算一次分裂的增益，而直方图算法只需要计算 $k$ 次（ $k$ 可以认为是常数），时间复杂度从 $O(\#data * \#feature)$ 优化到 $\#features)$ 。在内存消耗上，预排序储存排序索引和特征值，而直方图算法只需储存bin的索引，减少了内存的消耗。
在这里插入图片描述

当然，Histogram算法并不是完美的。由于特征被离散化后，找到的并不是很精确的分割点，所以会对结果产生影响。但在不同的数据集上的结果表明，离散化的分割点对最终的精度影响并不是很大，甚至有时候会更好一点。原因是决策树本来就是弱模型，分割点是不是精确并不是太重要；较粗的分割点也有正则化的效果，可以有效地防止过拟合；即使单棵树的训练误差比精确分割的算法稍大，但在梯度提升（Gradient Boosting）的框架下没有太大的影响。

直方图作差优化

一个叶子的直方图可以由它的父亲节点的直方图与它兄弟的直方图做差得到。通常构造直方图，需要遍历该叶子上的所有数据，但直方图做差仅需遍历直方图的k个桶。利用这个方法，LightGBM可以在构造一个叶子的直方图后（父节点在上一轮就已经计算出来了），可以用非常微小的代价得到它兄弟叶子的直方图，在速度上可以提升一倍。
在这里插入图片描述

leaf-wise算法

LightGBM采用leaf-wise算法。当叶子数量相同时，leaf-wise算法精度更高。为了避免生成较深的树，设置了max_depth的限制。

单边梯度采样法（GOSS）

单边梯度采样法，又称为Gradient-based one-side sampling。GBDT每个样本都有不同的梯度值，将其作为采样的依据。梯度较小的样本，说明其拟合得已经比较好了，于是可以考虑减少它的权重。具体操作如下

首先将要进行分裂的特征的所有梯度值按照绝对值大小降序排序（XGBoost一样也进行了排序，但是LightGBM不用保存排序后的结果），选取绝对值最大的前 $a\%$ 个数据。然后在剩下的较小梯度数据中随机选择 $b\%$ 个数据。为避免改变数据得分布，在计算增益时将小梯度数据扩大 $\frac{1-a}{b}$ 。通过这种方法，可以既减少数据量，又保证精度。

直接支持类别特征

实际上大多数机器学习工具都无法直接支持类别特征，一般需要把类别特征，通过 one-hot编码，转化到多维的0/1特征，降低了空间和时间的效率。但我们知道对于决策树来说并不推荐使用 one-hot 编码，尤其当类别特征中类别个数很多的情况下，会增加维度。LightGBM支持直接输入类别变量

one-hot产生的其他问题：

会产生样本切分不平衡问题，导致切分增益非常小（即浪费了这个特征）。使用 one-hot编码，这一系列特征上可能只有少量样本为 1，大量样本为
0，这时候切分样本会产生不平衡，这意味着切分增益也会很小。较小的那个切分样本集，它占总样本的比例太小，无论增益多大，乘以该比例之后几乎可以忽略；较大的那个拆分样本集，它几乎就是原始的样本集，增益几乎为零。比较直观的理解就是不平衡的切分和不切分没有区别。
会影响决策树的学习。因为就算可以对这个类别特征进行切分，独热编码也会把数据切分到很多零散的小空间上，如下图左边所示。而决策树学习时利用的是统计信息，在这些数据量小的空间上，统计信息不准确，学习效果会变差。但如果使用下图右边的切分方法，数据会被切分到两个比较大的空间，进一步的学习也会更好。下图右边叶子节点的含义是X=A或者X=C放到左孩子，其余放到右孩子。

支持并行运算

特征并行

在不同机器、在不同的特征集合上分别寻找最优的分割点，然后在机器间同步最优的分割点。
在这里插入图片描述

数据并行

让不同的机器先在本地构造直方图，然后进行全局的合并，最后在合并的直方图上面寻找最优分割点。合并直方图时通信代价比较大。

在这里插入图片描述

基于投票的数据并行

从本地找最优特征，再投票找到可能是最优的特征，只合并这些特征的直方图。
在这里插入图片描述

参数调整

防止过拟合：

较小的num_leaves
较大的min_data_in_leaf
feature_sampling

算法比较

LightGBM优化点

采用基于Histogram的决策树算法。
单边梯度采样 Gradient-based One-Side Sampling(GOSS)：使用GOSS可以减少大量只具有小梯度的数据实例，这样在计算信息增益的时候只利用剩下的具有高梯度的数据就可以了，相比XGBoost遍历所有特征值节省了不少时间和空间上的开销。
互斥特征捆绑 Exclusive Feature Bundling(EFB)：使用EFB可以将许多互斥的特征绑定为一个特征，这样达到了降维的目的。
带深度限制的Leaf-wise的叶子生长策略：大多数GBDT工具使用低效的按层生长 (level-wise) 的决策树生长策略，因为它不加区分的对待同一层的叶子，带来了很多没必要的开销。实际上很多叶子的分裂增益较低，没必要进行搜索和分裂。LightGBM使用了带有深度限制的按叶子生长 (leaf-wise) 算法。
直接支持类别特征(Categorical Feature)
支持高效并行
Cache命中率优化