什么是 LightGBM？

LightGBM 的工程优化有哪些？

LightGBM如何处理类别特征？

LightGBM和XGBoost的主要区别和优势是什么？

LightGBM的优缺点有哪些?

什么是 LightGBM

LightGBM（Light Gradient Boosting Machine）是一个高效实现 GBDT 算法的框架，它支持并行训练，具有更快的训练速度、更低的内存消耗、更高的准确率，并且支持分布式处理海量数据。LightGBM 相对 XGBoost 具有训练速度快、内存占用低的特点。

那么 LightGBM 到底如何做到更快的训练速度和更低的内存使用的呢？下面我们来一探究竟。

单边梯度抽样算法

GBDT 算法的梯度大小可以反应样本的权重，梯度越小说明模型拟合的越好，单边梯度抽样算法（Gradient-based One-Side Sampling, GOSS）利用这一信息对样本进行抽样，减少了大量梯度小的样本，在接下来的计算中只需关注梯度高的样本，极大的减少了计算量。

GOSS 算法保留了梯度大的样本，并对梯度小的样本进行随机抽样，为了不改变样本的数据分布，在计算增益时为梯度小的样本引入一个常数进行平衡。具体算法如下所示。

我们可以看到 GOSS 事先基于梯度的绝对值对样本进行排序（无需保存排序后的结果），然后拿到前 a% 的梯度大的样本， 之后在剩下的小梯度样本中随机采样 b% 比率的样本，在计算增益时，通过乘上 \(\frac{1-a}{b}\) 来放大小梯度样本的权重，从而进一步的避免样本的分布不一致问题。一方面算法将更多的注意力放在训练不足的样本上，另一方面通过乘上权重来防止采样对原始数据分布造成太大的影响。

直方图算法

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

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

特征离散化具有很多优点，如存储方便、运算更快、鲁棒性强、模型更加稳定等。

对于直方图算法来说最直接的有以下两个优点

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

虽然将特征离散化后无法找到精确的分割点，可能会对模型的精度产生一定的影响，但较粗的分割也起到了正则化的效果，一定程度上降低了模型的方差。

直方图加速

LightGBM 还可以利用 Histogram（直方图）做差加速。

在构建叶节点的直方图时，我们还可以通过父节点的直方图与相邻叶节点的直方图相减的方式构建，从而减少了一半的计算量。在实际操作过程中，我们还可以先计算直方图小的叶子节点，然后利用直方图作差来获得直方图大的叶子节点。

稀疏特征优化

XGBoost 在进行预排序时只考虑非零值进行加速，而 LightGBM 也采用类似策略，只用非零特征构建直方图。

互斥特征捆绑算法

高维特征往往是稀疏的，LightGBM 设计了一种无损的方法来减少特征的维度：互斥特征绑定算法（Exclusive Feature Bundling, EFB）。

在稀疏特征空间中，许多特征是互斥的（即特征不会同时为非零值，像one-hot），因此，可以绑定互斥的特征为单一特征构建特征直方图，而不丟失信息。如果两个特征并不是完全互斥 (部分情况下两个特征都是非零值)，可以用一个指标（互斥率）对特征不互斥程度进行度量，当这个值较小时，可以选择把不完全互斥的两个特征绑定，而不影响最后的精度。

互斥特征捆绑算法（Exclusive Feature Bundling, EFB）指出如果将一些特征进行融合绑定，则可以降低特征数量。

针对这种想法，我们会遇到两个问题：

1. 哪些特征可以一起绑定？
2. 特征绑定后，特征值如何确定？

对于问题一：EFB 算法利用特征和特征间的关系构造一个加权无向图，并将其转换为图着色算法。我们知道图着色是个 NP-Hard 问题，故采用贪婪算法得到近似解，具体步骤如下：

1. 构造一个加权无向图，顶点是特征，边是两个特征间互斥程度；
2. 根据节点的度进行降序排序，度越大，与其他特征的冲突越大；
3. 遍历每个特征，将它分配给现有特征包，或者新建一个特征包，使得总体冲突最小。

算法允许两两特征并不完全互斥来增加特征捆绑的数量，通过设置最大互斥率 \(\gamma\) 来平衡算法的精度和效率。

EFB 算法的伪代码如下所示：

对于问题二：论文给出特征合并算法，其关键在于原始特征能从合并的特征中分离出来。假设 Bundle 中有两个特征值，A 取值为 [0, 10]、B 取值为 [0, 20]，为了保证特征 A、B 的互斥性，我们可以给特征 B 添加一个偏移量转换为 [10, 30]，Bundle 后的特征其取值为 [0, 30]，这样便实现了特征合并。具体算法如下所示：

带深度限制的 Leaf-wise 算法

在建树的过程中有两种策略：

• 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 编码，尤其当类别个数很多的情况下，会存在很多问题，比如：

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}\) 种可能，时间复杂度为 \(O(2^k)\)，不过 LightGBM 基于 Fisher的 《On Grouping For Maximum Homogeneity》论文实现了 \(O(klogk)\)的时间复杂度。

算法流程如下图所示，在枚举分割点之前，先把直方图按照每个类别对应的 label 均值进行排序；然后按照排序的结果依次枚举最优分割点。此外，为了防止过拟合，LightGBM 也增加了很多约束和正则化。

最后，LightGBM 作者表示，通过这种方法在 500 棵 255 深度的树上，LightGBM 的这单点优化带来了1.5点的 auc 提升，而在耗时上，只增加了20%。

一个案例

下面是使用 LGBMClassifier 进行分类的案例，用到的数据集是经典的泰坦尼克号数据集。

import numpy as np
import pandas as pd
import seaborn as sns
import lightgbm as lgb
from sklearn.metrics import classification_report
from sklearn.model_selection import train_test_split

titanic = sns.load_dataset('titanic')
# Drop unnecessary columns
titanic = titanic.drop(['deck', 'embark_town', 'alive'], axis=1)

# Replace missing values with the median or mode
titanic['age'] = titanic['age'].fillna(titanic['age'].median())
titanic['fare'] = titanic['fare'].fillna(titanic['fare'].mode()[0])
titanic['embarked'] = titanic['embarked'].fillna(titanic['embarked'].mode()[0])

# Convert categorical variables to numerical variables
titanic['sex'] = pd.Categorical(titanic['sex']).codes
titanic['embarked'] = pd.Categorical(titanic['embarked']).codes

# Split the dataset into input features and the target variable
X = titanic.drop('survived', axis=1)
y = titanic['survived']

# Split the dataset into training and testing sets
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

class_dict = {
"Third": 3,
"First": 1,
"Second": 2
}
who_dict = {
"child": 0,
"woman": 1,
"man": 2
}
X_train['class'] = X_train['class'].apply(lambda x: class_dict[x])
X_train['who'] = X_train['who'].apply(lambda x: who_dict[x])
X_test['class'] = X_test['class'].apply(lambda x: class_dict[x])
X_test['who'] = X_test['who'].apply(lambda x: who_dict[x])

params = {
'objective': 'binary',
'boosting_type': 'gbdt',
'num_leaves': 31,
'learning_rate': 0.05,
'feature_fraction': 0.9
}
clf = lgb.LGBMClassifier(**params)
clf.fit(X_train, y_train)

predictions = clf.predict(X_test)
print(classification_report(y_test, predictions))

LightGBM 的工程优化有哪些？

特征并行

特征并行的主要思想是不同机器在不同的特征集合上分别寻找最优的分割点，然后在机器间同步最优的分割点。XGBoost 使用的就是这种特征并行方法。

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

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

数据并行

传统的数据并行策略主要为水平划分数据，让不同的机器先在本地构造直方图，然后进行全局的合并，最后在合并的直方图上面寻找最优分割点。

这种数据划分有一个很大的缺点，通讯开销过大。如果使用点对点通信，一台机器的通讯开销大约为 ；如果使用集成的通信，则通讯开销为 。

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

投票并行

基于投票的数据并行则进一步优化数据并行中的通信代价，使通信代价变成常数级别。

在数据量很大的时候，使用投票并行的方式只合并部分特征的直方图从而达到降低通信量的目的，可以得到非常好的加速效果。

大致步骤为两步：

1. 本地找出 Top K 特征，并基于投票筛选出可能是最优分割点的特征；
2. 合并时只合并每个机器选出来的特征。

具体过程如下图所示。

Cache 命中率优化

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

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

1. 首先，所有的特征都采用相同的方法获得梯度（区别于不同特征通过不同的索引获得梯度），只需要对梯度进行排序并可实现连续访问，大大提高了缓存命中；
2. 其次，因为不需要存储特征到样本的索引，降低了存储消耗，而且也不存在 Cache Miss的问题。

LightGBM做了哪方面的并行？

LightGBM 主要实现了两种类型的并行化来加速训练过程。

• 特征并行
• 数据并行

详细解释，请参照上文。

LightGBM如何处理类别特征？

为了解决 one-hot 编码处理类别特征的不足，LightGBM 优化了对类别特征的支持，可以直接输入类别特征，不需要额外的 0/1展开，并产生如上图右侧的效果。LightGBM 采用 many-vs-many 的切分方式将类别特征分为两个子集，实现类别特征的最优切分。

算法流程如下图所示，在枚举分割点之前，先把直方图按照每个类别对应的 label 均值进行排序；然后按照排序的结果依次枚举最优分割点。此外，为了防止过拟合，LightGBM 也增加了很多约束和正则化。

LightGBM 相对于 XGBoost 的优点是什么？

内存更小

1. XGBoost 使用预排序后需要记录特征值及其对应样本的统计值的索引，而 LightGBM 使用了直方图算法将特征值转变为 bin 值，且不需要记录特征到样本的索引，极大的减少了内存消耗；
2. LightGBM 采用了直方图算法将存储特征值转变为存储 bin 值，降低了内存消耗；
3. LightGBM 在训练过程中采用互斥特征捆绑算法减少了特征数量，降低了内存消耗。

速度更快

1. LightGBM 采用了直方图算法将遍历样本转变为遍历直方图，极大的降低了时间复杂度；
2. LightGBM 在训练过程中采用单边梯度算法过滤掉梯度小的样本，减少了大量的计算；
3. LightGBM 采用了基于 Leaf-wise 算法的增长策略构建树，减少了很多不必要的计算量；
4. LightGBM 采用优化后的特征并行、数据并行方法加速计算，当数据量非常大的时候还可以采用投票并行的策略；
5. LightGBM 对缓存也进行了优化，增加了缓存的命中率。

LightGBM的优缺点有哪些?

LightGBM 是一个基于决策树算法的高效梯度提升框架，由微软开发。它具有如下优缺点。

优点

1. 高效性能：LightGBM 使用基于直方图的算法，这使得它在处理大数据集时比传统的梯度提升方法更快、更高效。
2. 低内存使用：相比其他梯度提升库，LightGBM 在数据存储和计算方面更加高效，因此占用更少的内存。
3. 支持大规模数据处理：由于其高效的实现，LightGBM能够处理相对更大的数据集，这在很多其他机器学习算法中是难以做到的。
4. 支持类别特征：LightGBM 原生支持类别特征，这意味着用户不需要额外进行独热编码。

缺点

1. 过拟合风险：对于相对较小的数据集，LightGBM 可能容易过拟合。
2. 参数调优复杂：虽然提供了丰富的参数设置，但这也意味着需要较深的理解和经验来找到最优的参数组合。
3. 对噪声和异常值敏感：作为一个基于树的算法，LightGBM对数据中的噪声和异常值比较敏感。