LightGBM算法原理、训练与预测

一、原理篇

LightGBM是个快速的，分布式的，高性能的基于决策树算法的梯度提升框架。可用于排序，分类，回归以及很多其他的机器学习任务中。

该算法是由微软亚洲研究院的机器学习组所开发，并开源至GitHub。由于其卓越的性能，在GitHub开源三天，就收到了1000+star，200+fork。

LightGBM算法是站在工程的角度上设计实现的，这使其更容易在大规模数据集中做模型的快速迭代，之所以说其性能卓越，主要是基于以下几个特性：

1、直方图优化

我们都知道，原始的GBDT算法在进行决策树节点分裂时，需要对全局数据集中的每一个特征分量进行遍历，以求出当前分裂节点的最优分裂特征值；而后续很多优化版本中都加入了预排序策略，其中包括了Xgboost算法，但是不管是否进行预排序优化，算法总归在构建决策树时需要遍历全局样本，这其实是非常耗时的。基于此，LightGBM采用了直方图优化策略，其主要原理是：在训练前，通过对样本中每一维特征进行排序，在排序后，对特征进行直方图划分（算法默认划分256个直方图），在后续的训练中，算法仅需要使用直方图作为"特征"进行决策树的构建，这大大减少了对样本集的遍历次数（#bins << #features）。

这样的优化，在某种程度上可能造成决策树分裂不能使用全局最优的分裂点，但实验证明，这种"不太准确"的分裂策略，在某种角度上起到了正则的作用，从而提升了模型的鲁棒性。

算法伪代码如下：

2、深度优先分裂策略（leaf-wise）

在LightGBM算法之前，大多数树模型在进行决策树构建时，均采用了层次宽度优先分裂（level-wise策略），即节点分裂时，在同一层的节点可以同时分裂，这在一定程度上可以多线程并行，加快构建决策树速度，但从另外一个角度讲，level-wise策略构建时只会考虑当前节点集合内的样本进行最优分裂，因此存在一种局部最优解的可能，另外，并行生成可能存在在同一层的部分节点没有必要进行额外的分裂（笔者认为即使分裂了，也可能会在决策树构建完毕后进行后剪枝操作，带来额外的开销）。基于此，LightGBM算法采用深度优先分裂策略，即每次对叶节点进行分裂时，均考虑了全局的样本，不会造成局部最优解的问题，同时也减少了后剪枝操作次数的可能。对于深度优先分裂策略，由于树的深度可能更深，造成过拟合，因此模型参数增加了对最大深度的限制，以减少过拟合的风险。

3、梯度单边采样策略（Gradient-based One-Side Sampling, GOSS）

单边采样的策略算法流程如下：

1、 选取前a%个较大梯度的值作为大梯度值的训练样本

2、 从剩余的1 - a%个较小梯度的值中，我们随机选取其中的b%个作为小梯度值的训练样本

3、 对于较小梯度的样本，也就是b% * (1 - 1%) * #samples，我们在计算信息增益时将其放大(1 - a) / b倍

算法伪代码如下：

我们都知道原始的GBDT的算法是利用了损失函数的负梯度近似等于残差的思想来实现的。与LightGBM算法相比，其他基于Boosting框架的树模型算法在每一次构建决策树时，使用了随机采样的策略抽取一定数量的样本进行梯度更新，参与决策树的构建，而LightGBM算法使用单边采样的策略，有针对性的对梯度较大的样本全部参与决策树构建，为保证样本的数据分布不被破坏，同时随机采样了梯度较小的样本参与构建决策树，实验证明，LightGBM算法侧单边采样策略好于随机采样策略。（笔者认为，LightGBM算法的单边采样策略一定程度上受到了AdaBoost思想的影响，个人看法）

4、互斥特征捆绑策略（Exclusive Feature Bundling, EFB）

顾名思义，互斥特征捆绑是将样本中不同维度的稀疏特征进行合并，作为一个特征进入模型参与决策树构建。 针对特征维度高，而高维的数据通常是稀疏的，能否设计一种无损的方法来减少特征的维度。特别的，稀疏特征空间中，许多特征是互斥的，例如他们从不同时为非零值。因此，我们可以绑定互斥的特征为单一特征，参与最终特征直方图的构建。

这里就有两个问题：

1、 如何确定哪些特征用于融合且效果较好？

2、 如何将这些特征合并到一起？

问题一

对于第一个问题，这是一个NP-hard问题。我们把feature看作是图中的点（V），feature之间的总冲突看作是图中的边（E）。而寻找合并特征且使得合并的bundles个数最小，这是一个图着色问题。所以这个找出合并的特征且使得bundles个数最小的问题需要使用近似的贪心算法来完成（Algorithm 3），它将问题一换成图着色算法去解决。构建一个以feature为图中的点（V），以feature之间的总冲突为图中的边（E）这里说的冲突值应该是feature之间cos夹角值，因为我们是尽可能保证feature之间非0元素不在同一个row上。首先按照度来对每个点（feature）做降序排序（度数越大与其他点的冲突越大），然后将特征合并到冲突数小于K的bundle或者新建另外一个bundle。算法的时间复杂度为O(#feature^2)。

贪心算法解决特征绑定伪代码如下：

问题二

对于第二个问题，使用以下算法将这些bundles中的特征合并起来（Algorithm 4），由于每一个bundle当中，features的range都是不一样，所以我们需要重新构建合并后bundle feature的range。在第一个for循环当中，我们记录每个feature与之前features累积totalRange。在第二个for循环当中，根据之前的binRanges重新计算出新的bin value（F[j]bin[i] + binRanges[j]）保证feature之间的值不会冲突。这是针对于稀疏矩阵进行优化。由于之前GreedyBundling算法对features进行冲突检查确保bundle内特征冲突尽可能少，所以特征之间的非零元素不会有太多的冲突。

目前，我们的特征中类似于one-hot的特征不多，因此这个特性对我们模型的训练效果影响不大。

特征合并伪代码如下：

5、直接支持类别特征

原始的GBDT算法对于类别特征，需要手动进行one-hot编码，然后传入模型进行训练或预测，但是one-hot编码会给我们的训练或预测带来很多的问题：

维度爆炸

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

增加打分时的额外开销

如果样本中的特征进行了one-hot编码，服务端在进行模型打分计算前，需要对相应的原始类别特征进行one-hot编码，这在一定程度上会增加模型打分耗时。

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

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

弱化决策树的学习能力

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

为了解决one-hot编码处理类别特征的不足。LightGBM采用了Many vs many的切分方式，实现了类别特征的最优切分。用LightGBM可以直接输入类别特征，并产生如上图右侧的效果。

算法流程如下：

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

2、 然后按照均值的结果依次枚举最优分割点。从下图可以看到，Sum(y)/Count(y)为类别的均值。当然，这个方法很容易过拟合（ 笔者认为，此处的过拟合产生的原因是因为，这里的均值采用的是训练样本的统计信息，决策树很容易学到类别的均值信息，但是在面对预测时，由于预测样本的统计信息与训练样本不尽相同，因此原始训练好的模型会对预测样本预测时不能得到很好的泛化效果，因此此处说容易过拟合），所以在LightGBM中加入了很多对这个方法的约束和正则化。

下图是一个简单的对比实验，可以看到该最优方法在AUC上提升了1.5个点，并且时间只多了20%。

6、并行学习

Python版本的LightGBM算法原生支持三种并行模式，分别是：特征并行(Featrue Parallelization)和数据并行(Data Parallelization)以及基于投票的数据并行(Voting Parallelization)。而Spark版本的LightGBM不支持特征并行（笔者认为，特征并行不能很好的解决大数据集上的分布式并行处理，因此Spark取消了这种模式），仅支持数据并行和基于投票的数据并行。

特征并行

特征并行的主要思想是在不同机器、在不同的特征集合上分别寻找最优的分割点，然后在机器间同步最优的分割点。

数据并行

数据并行则是让不同的机器先在本地构造直方图，然后进行全局的合并，最后在合并的直方图上面寻找最优分割点。

基于投票的数据并行

在直方图合并的时候，通信代价比较大，基于投票的数据并行能够很好的解决这一点（笔者建议在设置参数时候，尽量设置为数据并行，不要设置投票并行，因为投票并行可能产生局部最优分割点。这是因为投票并行也是基于数据并行，而每个worker只统计了局部数据的最优分割点，可能在投票的过程中这个局部数据的最优分割点不能代表全局最优分割点）。

基于上述的特性，LightGBM算法可以快速地对超大规模数据集进行训练，并相比于Xgboost算法，直接支持类别特征传入的特性，这对于我们来说是一个巨大的福音。

以下是LightGBM算法与Xgboost算法在不同数据集上实验效果对比，足以见得LightGBM的优越性：

7、写在实战前

在使用该算法前，先在自己的项目中添加LightGBM算法的maven依赖配置：

<dependency><groupId> com.microsoft.ml.spark </groupId><artifactId> mmlspark_2.11 </artifactId><version> 1.0.0-rc1 </version></dependency>

本篇主要针对模型训练人员。

1、算法的重新编译

原生的Spark版本的LightGBM算法集成在了微软的开源项目MMLSPARK（Microsoft Machine Learning for Apache Spark），该项目是微软在认知工具包（Microsoft Cognitive Toolkit，曾用名 CNTK）的基础上开发的基于Apache Spark大数据框架的实现，由于mmlspark集成了大量了机器学习和深度学习算法，导致依赖该项目的maven后，项目打的jar包巨大（400M+），因此，需要对mmlspark项目进行一定阉割，只保留LightGBM算法（分类，回归均支持）进行重新编译。

2、训练代码的开发

以下是LightGBM二分类训练代码的demo，与其他Spark MLLIb中的算法的训练代码编写相似，以下是Scala示例代码：

import com.microsoft.ml.spark.{LightGBMClassificationModel, LightGBMClassifier}import org.apache.spark.SparkContextimport org.apache.spark.mllib.evaluation.BinaryClassificationMetricsimport org.apache.spark.rdd.RDDimport org.apache.spark.sql.{DataFrame, Dataset, Row, SparkSession}import scala.collection.mutable.ListBufferobject LightGBMTest {  def main(args: Array[String]): Unit = {    //    val session: SparkSession = SparkSession.builder().getOrCreate()    val sc: SparkContext = session.sparkContext    val data: DataFrame = session      .read      .format("libsvm")      .option("numFeatures", "949") //      .load(args(0))      .repartition(500)    val array: Array[Dataset[Row]] = data.randomSplit(Array(0.7, 0.3))    val train_data: Dataset[Row] = array(0)    val test_data: Dataset[Row] = array(1)    //    val lgbCl: LightGBMClassifier = new LightGBMClassifier()      .setLearningRate(0.005d)      .setMaxDepth(7)      .setNumIterations(100)      .setEarlyStoppingRound(20)      .setParallelism("data_parallel")      .setTimeout(600)      .setObjective("binary") //      .setNumLeaves(160)      .setMaxBin(511)    val model: LightGBMClassificationModel = lgbCl.fit(train_data)    val value: RDD[(Double, Double)] = model      .transform(test_data)      .select("label", "probability")      .rdd      .mapPartitions(iter => {        val listBuffer: ListBuffer[(Double, Double)] = new ListBuffer[(Double, Double)]        iter.foreach(row => {          listBuffer.+=((row.getDouble(0), row.get(1).asInstanceOf[org.apache.spark.ml.linalg.Vector].apply(1)))        })        listBuffer.iterator      })    val metrics: BinaryClassificationMetrics = new BinaryClassificationMetrics(value)    println("Area under precision-recall curve = " + metrics.areaUnderPR())    println("Area under ROC = " + metrics.areaUnderROC())    model.getModel.saveNativeModel(session, args(1), overwrite = true)    session.stop()  }}

基于业务以及需要自己对算法原理有着深刻理解的基础上，参数调优才能使算法达到较好的效果，以下给出通用的算法参数调优的方案：

针对更好的准确率

1、 使用较大的maxBin (这可能导致模型训练速度减慢)

2、 采用更小的learningRate及更大的numIterations（可能会过拟合）

3、 使用较大的numLeaves (可能会过拟合)

4、 增大训练数据集

处理过拟合

1、 使用较小的maxBin

2、 使用较小的numLeaves

3、 使用minSumHessianInLeaf

4、 通过设置baggingFraction和 baggingFreq来使用 bagging

5、 通过设置 featureFraction来使用特征子抽样

6、 增大训练数据集

7、 使用lambdaL1, lambdaL2 来使用正则化（当前版本不支持，下个版本2.0支持）

8、 尝试maxDepth来避免生成过深的树

三、预测篇

本篇主要针对服务端开发人员。

笔者在进行预测代码的开发中，踩了好多坑，一把辛酸泪。尝试了不同的预测打分方式，这其中包括了PMML解决方案、MMLSPARK原生预测解决方案以及Java重构的预测解决方案。最终选择了java重构的预测解决方案，放弃前两种解决方案的原因如下：

1、 PMML的解决方案会有一定的打分误差，并打分耗时不太满足当前业务

2、 MMLSPARK原生预测解决方案中代码依赖了底层的C++动态链接库，并且预测代码有一定的优化空间，打分耗时巨大（每次打分都需要重新初始化C++依赖的一些数据对象）

Java重构的预测解决方案在GitHub上有一个叫本（Ben Auffarth, PhD）的大佬开源了一款()，他是英国一个人力资源公司的首席数据科学家，Java重构预测的解决方案由他提供支持。以下给出LightGBM模型预测代码demo：

import com.mlspark.lightgbm.predictor.SparseVector;import com.mlspark.lightgbm.predictor.V2.Boosting;import com.mlspark.lightgbm.predictor.V2.OverallConfig;import com.mlspark.lightgbm.predictor.V2.Predictor;import java.util.HashMap;import java.util.List;import java.util.Map;public class Main {    public static void main(String[] args) throws Exception {        String modelPath = "模型地址";        Boosting boosting = Boosting.createBoosting(modelPath);        Map<String, String> map = new HashMap<String, String>();        OverallConfig config = new OverallConfig();        config.set(map);        Predictor predictor =                new Predictor(boosting, config.io_config.num_iteration_predict, config.io_config.                        is_predict_raw_score,                        config.io_config.is_predict_leaf_index, config.io_config.pred_early_stop,                        config.io_config.pred_early_stop_freq, config.io_config.pred_early_stop_margin);        int[] indices = new int[949];        for (int i = 0; i < indices.length; i++) {            indices[i] = i;        }        double[] values = {};        System.out.println(values.length);        SparseVector v = new SparseVector(values, indices);        List<Double> predicts = predictor.predict(v);        System.out.println("predict values " + predicts.toString());        values = new double[]{};        System.out.println(values.length);        v = new SparseVector(values, indices);        predicts = predictor.predict(v);        System.out.println("predict values " + predicts.toString());        long start = System.currentTimeMillis();        for (int i = 0; i < 1000; i++) {            v = new SparseVector(values, indices);            predicts = predictor.predict(v);        }    }}

在线打分效果：

在最终服务器线上测试发现，在线预测批量（batch）为1000，耗时10±ms，算是非常快的打分方式了。

总结

在树模型这一领域，使用最普遍的还是xgboost，而Lightgbm在实际应用中其实不是很广泛，究其原因，可能是在Lightgbm兴起的同时，深度学习抢占了树模型的风头吧。目前互联网界各个大厂几乎都用深度学习模型覆盖了，树模型感觉要"日落西山"，但是对于超大型的业务来说，深度学习模型有着其天然的推理耗时长的问题，所以如果某大型个性化业务在初期上马时，可以使用树模型来先顶一阵，尤其是使用LightGBM，毕竟可以用较少的服务器去支撑较大的业务量也是我们业务初期要考虑的问题。

如果喜欢我的文章，欢迎关注我的微信公众号软客圈（ID：recoquan）

纯手工打造，实属不易，欢迎大家分享和转发~

原创内容，转载需注明出处，否则视为侵权并将被追诉！