《机器学习高频面试题详解》1.14：LightGBM算法

点击上方卡片链接就可以进入专栏，专栏右上角有订阅选项，欢迎大家订阅～

前言

大家好，我是鬼仔，今天带来《机器学习高频面试题详解》专栏的第1.14节：LightGBM算法。这是鬼仔第一次开设专栏，每篇文章鬼仔都会用心认真编写，希望能将每个知识点讲透、讲深，帮助同学们系统性地学习和掌握机器学习中的基础知识，希望大家能多多支持鬼仔的专栏～

目前这篇是试读，后续的文章需要订阅才能查看哦，专栏预计更新30+篇文章（只增不减），具体内容可以看专栏介绍，大家的支持是鬼仔更新的动力！

一、LightGBM原理

常见的机器学习算法，如神经网络，可以通过mini-batch方式训练，不受内存限制。但GBDT每次迭代都需要多次遍历整个数据集。如果将数据集全部加载到内存中，则会限制数据集的大小；如果不加载，则会花费大量时间进行读写。因此，普通GBDT算法无法满足工业级海量数据的需求。

上篇文章讲解了XGBoost，一种基于预排序方法的决策树算法，虽然做了很多工程上的优化，但仍有很大的提升空间，LightGBM应运而生。LightGBM（Light Gradient Boosting Machine）是一个高效实现GBDT算法的框架，它支持并行训练，具有更快的训练速度、更低的内存消耗、更高的准确率，并且支持分布式处理海量数据。

下面详细分点介绍lightGBM优化算法。

1. 直方图算法

GBDT算法中，决策树节点分裂时需要遍历整个数据集中的每个特征，以找到最佳分裂特征值。尽管许多优化版本（如Xgboost）采用了预排序策略，但构建决策树仍然需要遍历全局样本，这非常耗时。因此，LightGBM引入了直方图算法。

直方图算法其实就是直方图统计，把连续数据离散化，其核心思想是将连续的浮点特征值离散化为K个整数，并构建一个宽度为K的直方图。在遍历数据时，根据离散化后的值作为索引在直方图中累积统计量。遍历一次数据后，直方图累积了所需的统计量，然后根据直方图的离散值遍历寻找最佳分割点。

特征离散化具有很多优点，如存储方便、运算更快、鲁棒性强、模型更加稳定等。直方图算法有以下两个最直接优点：

内存占用更小：直方图算法只保存特征离散化后的值，而这个值一般用8位整型存储就足够了，极大地降低了内存消耗；
计算代价更小：预排序算法XGBoost每遍历一个特征值就需要计算一次分裂的增益，而直方图算法LightGBM只需要计算 K 次（常数），直接将时间复杂度从 $O(n(data)*n(feat))$ 降低到 $O(k*n(feat))$ 。

Histogram算法也有缺点，它用离散化的特征来寻找不太精确的分割点，这会影响最终的效果。但实际上，在不同的数据集上，离散化分割点对精度的影响并不明显，有时甚至会更优。这是因为决策树本身就是弱模型，分割点是否精确并不关键；而且粗略的分割点也有正则化作用，可以有效避免过拟合；即使单棵树的训练误差稍微大一些，但在梯度提升（Gradient Boosting）框架下也不会有太大问题。

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

2. 互斥特征绑定

高维度的数据往往是稀疏的，LightGBM设计了一种无损的方法来减少特征的维度：互斥特征绑定算法（Exclusive Feature Bundling, EFB）。在稀疏特征空间中，许多特征是互斥的（即特征不会同时为非零值，像one-hot），因此，可以绑定互斥的特征为单一特征构建特征直方图，而不丟失信息。如果两个特征并不是完全互斥 (部分情况下两个特征都是非零值)，可以用一个指标（冲突比率）对特征不互斥程度进行度量，当这个值较小时，可以选择把不完全互斥的两个特征绑定，而不影响最后的精度。

这样在构建直方图时的时间复杂度从 $O(n(data)*n(feat))$ 变为 $O(n(data)*n(bundle))$ ，其中 $n(bundle)$ 指特征融合绑定后特征包的个数, 一般远小于特征个数。

3. Leaf-wise生长策略

XGBoost 采用 Level-wise（按层生长）的增长策略，该策略遍历一次数据可以同时分裂同一层的叶子，方便多线程并行优化，也能控制模型复杂度，防止过拟合。但其实Level-wise算法效率不高，它对同层的叶子一视同仁，其实很多叶子的分裂增益很低，不需要搜索和分裂，这样就造成了很多没必要的计算开销。

LightGBM采用带有深度限制的Leaf-wise（按叶子生长）的增长策略，该策略每次从所有叶子里，选出分裂增益最大的一个叶子，进行分裂，循环这个过程。和Level-wise比起来，Leaf-wise的优点是：在相同的分裂次数下，Leaf-wise可以减少更多的误差，提高精度；Leaf-wise的缺点是：可能会生成比较深的决策树，导致过拟合。因此LightGBM在Leaf-wise基础上加了一个最大深度的限制，在保持高效率的同时防止过拟合。

4. 类别特征处理优化

大多数传统机器学习算法都无法直接支持类别特征，一般需要把类别特征通过类似one-hot 编码，转化到多维的0/1特征，但这降低了空间和时间的效率。决策树一般不推荐使用 one-hot 编码，尤其当类别个数很多的情况下，会存在很多问题，比如：

1）维度爆炸

one-hot编码的思想是把类别特征做成独热的向量，如果某个类别特征的特征值个数巨大，就需要编码一个很高维度的特征向量，很明显这是不合理的。

2）决策树构建中无法进行特征切分

使用one-hot编码的话，意味着在每一个决策节点上只能使用one vs rest方式进行切分，当类别值很多时，每个类别上的数据可能会比较少，这时候切分会产生不平衡，这意味着切分增益也会很小，因为不平衡的切分和不切分没有区别。

3）弱化决策树的学习能力

决策树构建使用的是样本的统计信息，若按照one-hot编码方式，会有很多样本量很小的类别特征，这样的样本由于数据量较小，很有可能有统计问题，这种统计问题会被带到决策树的学习过程当中，使模型产生过拟合风险。

为了解决one-hot编码处理类别特征的不足, LightGBM优化了对类别特征的支持，可以直接输入类别特征，不需要额外的0/1展开，并产生如上图右侧的效果。LightGBM 采用 many-vs-many 的切分方式将类别特征分为两个子集，实现类别特征的最优切分。假设某个特征有 $k$ 个类别，则有 $2^{k-1}-1$ 种可能, 时间复杂度为 $O(2^k)$ ，LightGBM 基于 Fisher的《On Grouping For Maximum Homogeneity》论文实现了 $O(klogk)$ 的时间复杂度。