算法工程师常见面试问题总结之LightGBM常见面试题总结

理论知识：通俗易懂的LightGBM理论知识
LightGBM是什么：LightGBM（Light Gradient Boosting Machine）是一个实现GBDT算法的框架，支持高效率的并行训练，并且具有更快的训练速度、更低的内存消耗、更好的准确率、支持分布式可以快速处理海量数据等优点。

1.LightGBM算法对XGBoost算法进行了什么优化
XGBboos相对LightGBM的缺点：
1） 空间消耗大：存储连续数据值为32位的浮点型，提前预排序和预存储，保存排序后的索引，消耗数据的两倍内存；
2）计算消耗大：每次都需要遍历，都需要 进行分裂增益计算（对于连续值而言比较复杂，以及所有的特征都要遍历）
3） cache优化不友好：在预排序后，特征对梯度的访问是一种随机访问，并且不同的特征访问的顺序不一样，无法对cache进行优化。
LightGBM优化：
1）基于Histogram的决策树法 （降低了存储使用和提高了寻找最优分裂点的速度）
2）等深度限制的leaf-wise的叶子生长策略：（减少不必要的分裂，提高训练速度和改善过拟合）
3）直方图差加速（一个叶子的直方图可以由它的父亲节点的直方图与它兄弟的直方图做差得到，提高训练速度）
4）直接支持类别特征（直接输入类别特征，不需要额外的0/1展开，提高预处理速度）
5）单边梯度采样法（梯度大的保留，梯度小的按比例抽取，提高训练速度）
6）互斥特征捆绑：（减少用于构建直方图的特征数量，提高训练速度和改善过拟合）
7）支持高效并行：（多台机子并行处理数据，再进行数据合并）
8）Cache命中率优化（lightGBM划分的特征分桶就是有顺序的，所以无需额外存储叶子索引的数组）
LightGBM缺点：

1. leaf-wise，有可能生成较深的决策树，所以需要增加深度限制，保证效率的同时防止过拟合。
   2）LightGBM是基于偏差的算法，会对噪音较为明显。
   3）没有考虑切分的最优解，只是取得了相对最优。

2.LightGBM的直方图算法是什么？

答：直方图算法：首先，在训练之前对每一个特征的特征值进行预排序，在排序之后，对特征值进行分桶（算法默认划分256个bin），累积分桶的样本数和导数值形成形成直方图。在遍历特征值寻找最优分裂点的时候，只需以分桶后的bin值作为索引进行遍历寻找最优的分割点。

2.1 LightGBM的直方图算法中的分桶是是什么原则呢？

答：直方图算法是等宽分桶，每个特征的值被均匀划分为若干个桶，每个桶的宽度相同，然后对每个桶中的样本计算直方图统计量，lightgbm默认分桶数256，此参数可以自定义。等宽分桶的方法可以有效地减少划分特征值的计算量，同时也可以降低噪声对特征值分布的影响。

2.2 LightGBM的直方图算法会对离散值进行分桶吗？

答：是的，LightGBM的直方图算法会对离散值进行分桶。在构建直方图时，LightGBM会先将特征值按照特定规则分成多个桶（bin），然后对每个桶内的样本计算统计信息。对于离散值，LightGBM会将其视为一类特殊的连续值，并将其放入其中一个桶中。这样可以利用离散值之间的排序关系提高模型性能。

2.3 LightGBM的直方图算法的优缺点是什么？

LightGBM的直方图算法相比于传统的基于排序的算法（如GBDT）具有以下优点：

1. 更快的训练速度：直方图算法将特征值进行分桶后，可以大幅减少每次分裂需要遍历的样本数，从而加快模型训练速度。
2. 更低的内存占用：直方图算法将数据集以均匀宽度的bin为单位进行存储，可以大幅减少内存需求。
3. 更好的并行计算能力：直方图算法每个特征分别构建直方图，因此可以更好地利用多线程计算。

但是也存在一些缺点：

1. 对异常值比较敏感：由于离群值会显著影响特征的分布情况，从而影响到bin的划分和分裂。因此，直方图算法对于异常值比传统算法更为敏感。
2. 容易过拟合：直方图算法在构建树时只关注局部的bin信息，可能会导致某些bins的统计信息被极端化，从而增加过拟合风险。
3. 不适用于高维稀疏数据：直方图算法需要将特征值进行分桶，因此不太适合于高维稀疏数据，这时候可以使用Sparase特征优化算法。

2.4 LightGBM的分桶与XGBoost分桶有什么区别

LightGBM和XGBoost都使用了分桶的技术来加速决策树的构建。它们的主要区别在于：

1. 分桶策略不同：LightGBM使用基于直方图的离散化方法，而XGBoost使用的是一种基于质量分数的离散化方法。具体来说，LightGBM将特征值按照特定规则分成多个桶（bin），每个桶中包含若干个特征值。而XGBoost会计算每个特征值的质量分数，并将其作为桶的界限，从而实现特征值的离散化。
2. 分裂点选择不同：由于分桶策略的不同，两种算法在选择分裂点时也有所区别。LightGBM通过枚举候选分裂点，选择对目标函数增益最大的分裂点；而XGBoost会先对所有特征进行排序，然后选择可能成为最佳分裂点的若干个位置进行考虑，再从这些位置中选择最佳的分裂点。
3. 计算信息增益的方式不同： LightGBM使用基于直方图的近似算法来计算信息增益，而XGBoost使用准确的梯度统计方法计算信息增益。因此，在模型性能和训练速度方面，两者也会有所不同。

2.5 XGBoost的分桶策略是什么

答 ：XGBoost中也使用了分桶的策略来加速模型训练过程。在XGBoost中，分桶的方法被称为“离散化”，它可以将连续的特征值划分成若干个离散的区间（也称为桶或箱），然后用每个区间的代表值（例如区间的平均值）作为该特征的值。
XGBoost使用的是一种基于质量分数的离散化方法，具体而言，它会计算每个特征值的质量分数，并将其作为桶的界限，从而实现特征值的离散化。这种方式与LightGBM的基于直方图的离散化方法不同。
XGBoost中的分桶技术有助于减少决策树构建过程中需要考虑的候选分裂点数目，从而加快模型的训练速度，并且可以避免决策树因过拟合而变得更深和更复杂。

2.6.LightGBM的直方图差加速

答：直方图算法还可以进一步加速。一个容易观察到的现象：一个叶子节点的直方图可以直接由父节点的直方图和兄弟节点的直方图做差得到。通常构造直方图，需要遍历该叶子上的所有数据，但直方图做差仅需遍历直方图的k个bin。利用这个方法，LightGBM可以在构造一个叶子的直方图后，可以用非常微小的代价得到它兄弟叶子的直方图，在速度上可以提升一倍。

3.LightGBM的leaf-wise分裂的优势和缺点

优点：

1. 更快的训练速度：相对于XGBoost的按层生成（level-wise），level-wise不加区分的对待同一层的叶子，虽然同一层叶子可以并行寻找分裂点，但是这带来了很多没必要的开销，很多叶子的分裂增益较低，没必要进行搜索和分裂。而LightGBM是叶子生长（leaf-wise），每次从当前所有叶子中，找到分裂增益最大的一个叶子，然后分裂。
2. 更高的精度：由于leaf-wise分裂可以更准确地选择最优的分裂点，所以在一些复杂的任务中，可以得到更高的预测精度。

缺点

1. 容易过拟合：因为leaf-wise分裂会在每层中一个节点上只选取一个样本进行分裂，如果这个样本恰好是一个噪声点，则可能导致过拟合。
2. 不稳定性高：因为leaf-wise分裂对数据的变化敏感，所以在数据集发生较大变化时，可能导致模型产生较大的变化。

4.LightGBM的单边梯度采样是什么

答：LightGBM单边梯度采样（GOSS）是一种加速训练的技术，它的基本思想是在保持精度的同时，尽可能地减少参与到分裂决策中的数据样本个数。
具体内容是GOSS算法的创新之处在于它只对梯度绝对值较小的样本按照一定比例进行采样，而保留了梯度绝对值较大的样本。这就是所谓的单边采样。由于目标函数增益主要来自于梯度绝对值较大的样本，因此这种方法在计算性能和计算精度之间取得了很好的平衡。

5.LightGBM的互拆特征捆绑是什么

答：LightGBM的互拆特征捆绑（EFB）是一种特征工程技术，它可以绑定互拆的特征位单一特征，减少寻找分裂点时的计算量。如果两个特征并不是完全互拆的（部分情况下两个特征都是非零值），则可以用一个指标对特征不互斥程度进行衡量，称之为冲突比率，当这个值较小时，我们可以选择把不完全互斥的两个特征捆绑一起，而不影响最后的精度。改方法有效的在不损失精度的情况下，降低了时间复杂度。

5.1LigthGBM怎么判定那些特征应该绑在一起？

答：LightGBM的EFB算法将这个问题转化为图着色问题来求解，将所有的特征视为图的各个顶点，将不相互独立的特征用一条边连接起来，边的权重就是两个相连接的特征的总冲突值，这样需要绑定的特征就是在图着色问题中要涂上同一种颜色的那些点（特征)，如果算法允许一小部分的冲突，则可以得到更少的特征包，进一步提高计算效率。

1. 如果算法允许一小部分的冲突，则可以得到更少的特征包，进一步提高计算效率。
2. 根据节点的度进行降序排序，度越大，与其他特征的冲突越大。
3. 遍历排序之后的每个特征，将它分配给现有特征包，或者新建一个特征包，使得总体冲突最小。算法允许两两特征并不完全互斥，从而增加特征捆绑的数量，通过设置最大冲突比率γ来平衡算法的精度和效率。

5.2LigthGBM怎么把特征绑在一起？

答：特征合并算法的关键在于原始特征能从合并的特征中分离出来。绑定几个特征在同一个束里需要保证绑定前的原始特征值在束中可被识别，鉴于直方图算法存储离散值而不是连续特征值，我们通过将互斥特征放在不同的分箱中来构建束，这可以通过在特征原始值中加一个偏置常量来解决。比如，我们在束中绑定了两个特征A和B，A特征的原始取值为区间［0，10］，B特征的原始取值为区间［0，20］。我们可以在B特征的取值上加一个偏置常量10，将其取值范围变为［10，30］，通过这种做法，就可以安全地将A、B特征合并，绑定后的特征取值范围为［0，30］。具体的特征合并算法如下所示。

6. LightGBM的支持高效并行

答：数据分块：LightGBM使用数据并行的方式，将数据集按行进行分块，每个线程或计算节点处理一个或多个数据块，从而实现对大规模数据的高效处理。
特征并行：LightGBM支持特征并行的计算方式，可以将特征的直方图计算任务分配给不同的线程或计算节点并行处理。
多线程：LightGBM内置了多线程的支持，可以利用多核CPU并行计算，加快模型训练和预测的速度。
分布式计算：LightGBM还支持分布式计算，可以将数据集分布到多个计算节点上进行处理，从而实现对大规模数据的高效处理。

7. LightGBM怎么支持类似特征

答：LightGBM优化了对类别特征的支持，可以直接输入类别特征，不需要额外的0/1展开。并在决策树算法上增加了类别特征的决策规则，直接原生支持类别特征，不需要转化，提高了近8倍的速度。

参考：
https://blog.csdn.net/u010366748/article/details/113816465
https://blog.csdn.net/weixin_41510260/article/details/95378749
https://blog.csdn.net/pearl8899/article/details/106159264
https://zhuanlan.zhihu.com/p/85044159
https://zhuanlan.zhihu.com/p/78293497
https://zhuanlan.zhihu.com/p/35155992