Python机器学习算法实现
Author：louwill
Machine Learning Lab
第17讲我们谈到了竞赛大杀器XGBoost，本篇我们来看一种比XGBoost还要犀利的Boosting算法——LightGBM。LightGBM全称为轻量的梯度提升机(Light Gradient Boosting Machine)，由微软于2017年开源出来的一款SOTA Boosting算法框架。跟XGBoost一样，LightGBM也是GBDT算法框架的一种工程实现，不过更加快速和高效。
XGBoost可优化的地方
XGBoost通过预排序的算法来寻找特征的最佳分裂点，虽然预排序算法能够准确的找出特征的分裂点，但该方法占用空间的代价太大，在数据量和特征量都比较多的情况下，会严重影响算法性能。XGBoost寻找最佳分裂点的算法复杂度可以估计为：
复杂度=特征数量*特征分裂点的数量*样本数量
既然XGBoost的复杂度是由特征数量、特征分裂点的数量和样本数量所决定的，那么LightGBM的优化空间自然是从这三个角度来考虑。LightGBM总体上仍然属于GBDT算法框架，关于GBDT算法特征我们已经在第15篇的时候重点叙述过，这里不再重复。我们重点梳理上述三个优化角度的基本原理即可。
Histogram算法
为了减少特征分裂点的数量和更加高效寻找最佳特征分裂点，LightGBM区别于XGBoost的预排序算法，采用Histogram直方图的算法寻找最佳特征分裂点。其基本想法是将连续的浮点特征值进行离散化为k个整数并构造一个宽度为k的直方图。对某个特征数据进行遍历的时候，将离散化后的值用为索引作为直方图的累积统计量。遍历完一次后，直方图便可累积对应的统计量，然后根据该直方图寻找最佳分裂点。直方图算法如下图所示。
直方图算法并不什么特别的创新之举，本质上就是一种数据离散化和分箱操作，但架不住速度快性能优，计算代价和内存占用都大大减少。
直方图另外一个好处在于差加速。一个叶子节点的直方图可由其父节点的直方图与其兄弟节点的直方图做差得到，这也可以加速特征节点分裂。
所以，从特征寻找最优分裂点角度，LightGBM使用了直方图算法进行优化。完整的直方图算法流程如下伪代码所示：
GOSS算法
GOSS全称为单边梯度抽样算法(Gradient-based One-Side Sampling)，是LightGBM从减少样本角度进行优化还设计的算法，算是LightGBM的核心原理之一。单边梯度抽样算法的主要思路是从减少样本的角度出发，将训练过程中大部分权重较小的样本剔除，仅对剩余样本数据计算信息增益。
第16讲我们谈到了Adaboost算法，该算法的一个关键要素就是样本权重，通过在训练过程不断调整样本分类权重而达到最优分类效果的过程。但在GBDT系列中并没有样本权重的相关设计，GBDT采用样本梯度来代替权重的概念。一般来说，训练梯度小的样本，其经验误差也相对较小，说明这部分数据已经获得了较好的训练，GBDT的想法就是再一下的残差拟合中丢弃掉这部分样本，但这样做可能会改变训练样本的数据分布，对最终的训练精度有影响。
针对以上问题，LightGBM提出采用GOSS采样算法。其目的就是最大效率的保留对计算信息增益有帮助的样本，提高模型训练速度。GOSS的基本做法是先将需要进行分裂的特征按绝对值大小降序排序，取绝对值最大的前a%个数据，假设样本大小为n，在剩下的(1-a)%个数据中随机选择b%个数据，将这b%个数据乘以一个常数(1-a)/b，这种做法会使得算法更加关注训练不够充分的样本，并且原始的数据分布不会有太大改变。最后使用a+b个数据来计算该特征的信息增益。GOSS算法流程伪代码如下所示。
GOSS算法主要是从减少样本的角度来对GBDT进行优化的。丢弃梯度较小的样本并且在不损失太多精度的情况下提升模型训练速度，这使得LightGBM速度较快的原因之一。
EFB算法
直方图算法对应于特征分裂点的优化、单边梯度抽样对应于样本量的优化，最后还剩下特征数量的优化没有谈到。而EFB算法就是针对于特征的优化。EFB算法全称为互斥特征捆绑算法(Exclusive Feature Bundling)，通过将两个互斥的特征捆绑在一起，合为一个特征，在不丢失特征信息的前提下，减少特征数量，从而加速模型训练。大多数时候两个特征都不是完全互斥的，可以用定义一个冲突比率对特征不互斥程度进行衡量，当冲突比率较小时，可以将不完全互斥的两个特征捆绑，对最后的模型精度也没有太大影响。
所谓特征互斥，即两个特征不会同时为非零值，这一点跟分类特征的one-hot表达有点类似。互斥特征捆绑算法的关键问题有两个，一个是如何判断将哪些特征进行绑定，另外一个就是如何将特征进行绑定，即绑定后的特征如何进行取值的问题。
针对第一个问题，EFB算法将其转化为图着色(Graph Coloring Problem)的问题来求解。其基本思路是将所有特征看作为图的各个顶点，用一条边连接不相互独立的两个特征，边的权重则表示为两个相连接的特征的冲突比例，需要绑定在一起的特征就是图着色问题中要涂上同一种颜色的点(特征)。基于图着色问题的EFB求解算法伪代码如下：
第二个问题是要确定绑定后的特征如何进行取值，其关键在于能够将原始的特征从合并后的特征中进行分离，也就是说绑定到一个特征后，我们仍然可以在这个绑定的bundle里面识别出原始特征。EFB算法针对该问题尝试从直方图的角度来处理，具体做法是将不同特征值分到绑定的bundle中不同的直方图箱子中，通过在特征取值中加一个偏置常量来进行处理。举个简单的例子，假设我们要绑定特征A和特征B两个特征，特征A的取值区间为[10,20)，特征B的取值范围为[10,30)，我们可以给特征B的取值范围加一个偏置量10，则特征B的取值范围变成了[20,40)，绑定后的特征取值范围变成了[10,40)，这样特征A和特征B即可进行愉快的融合了。特征合并算法伪代码如下所示：
以上三个算法就是LightGBM在XGBoost基础上，针对特征分裂点、样本数量和特征数量分别做出的优化处理方法。
Leaf-Wise
除了Histogram、GOSS和EFB算法之外，LightGBM还提出了区别于XGBoost的按层生长的叶子节点生长方法，即带有深度限制的按叶子节点生长(Leaf-Wise)的决策树生成算法。具体如下图所示：
XGBoost采用按层生长的Level-Wise算法，好处是可以多线程优化，也方便控制模型复杂度，且不易过拟合。但缺点是不加区分的对待同一层所有叶子节点，大部分的节点分裂和增益计算不是必须的，带来了多余的计算开销。LightGBM提出了按叶子节点生长的Leaf-Wise算法，精度更高且更有效率，能够节约不必要的计算开销，同时为防止某一节点过分生长而加上一个深度限制机制，能够在保证精度的同时一定程度上防止过拟合。
除了以上四点改进算法之外，LightGBM在工程实现上也有一些改进和优化。比如可以直接支持类别特征(不需要再对类别特征进行one-hot等处理)、高效并行和Cache命中率优化等。这里不做详述，读者朋友们可以查找LightGBM原文研读。
LightGBM实现
从头开始实现了一个完整的LightGBM算法是一个复杂的系统性工程，限于时间和精力，这里笔者就不再进花时间手撸该算法。LightGBM开发团队提供了该算法的完整实现，这使得我们能够方便的进行调用。
pip直接安装即可：
pip install lightgbmLightGBM提供了分类和回归两大类接口，下面以分类问题和iris数据集为例给出原生LightGBM接口的一个使用示例：
import pandas as pd import lightgbm as lgb from sklearn.metrics import mean_squared_error from sklearn.datasets import load_iris from sklearn.model_selection import train_test_split from sklearn.datasets import make_classification # 导入数据 iris = load_iris() data = iris.data target = iris.target X_train, X_test, y_train, y_test =train_test_split(data, target, test_size=0.2) # 创建模型 gbm = lgb.LGBMRegressor(objective='regression', num_leaves=31, learning_rate=0.05, n_estimators=20) # 模型训练 gbm.fit(X_train, y_train,eval_set=[(X_test, y_test)],eval_metric='l1',early_stopping_rounds=5) # 预测测试集 y_pred = gbm.predict(X_test, num_iteration=gbm.best_iteration_) # 模型评估 print(mean_squared_error(y_test, y_pred) ** 0.5) # 查看特征重要性 print(list(gbm.feature_importances_))下面给出一个LightGBM回归模型五折交叉验证训练的代码模板，仅供大家参考。
import time import numpy as np import pandas as pd import lightgbm as lgb from sklearn.model_selection import KFold from sklearn.metrics import mean_squared_error # 训练特征，使用时label要换为实际标签名称 features = [f for f in df.columns if f not in [label]] # 自定义模型评估方法 def evalerror(pred, df): label = df.get_label().values.copy() score = mean_squared_error(label, pred)*0.5 return ('mse', score, False) # 指定超参数 params = { 'learning_rate': 0.01, 'boosting_type': 'gbdt', 'objective': 'regression', 'metric': 'mse', 'sub_feature': 0.7, 'num_leaves': 60, 'colsample_bytree': 0.7, 'feature_fraction': 0.7, 'min_data': 100, 'min_hessian': 1, 'verbose': -1, } t0 = time.time() train_preds = np.zeros(train.shape[0]) # 五折交叉验证训练 kf = KFold(n_splits=5, shuffle=True, random_state=43) for i, (train_index, valid_index) in enumerate(kf.split(train)): print('train for {} epoch...'.format(i)) train2 = train.iloc[train_index] valid2 = train.iloc[valid_index] lgb_train = lgb.Dataset(train2[features], train2['total_cost'], categorical_feature=['hy', 'sex', 'pay_type']) lgb_valid = lgb.Dataset(valid2[features], valid2['total_cost'], categorical_feature=['hy', 'sex', 'pay_type']) model = lgb.train(params, lgb_train, num_boost_round=3000, valid_sets=lgb_valid, verbose_eval=300, feval=evalerror, early_stopping_rounds=100) # 特征重要性排序 feat_importance = pd.Series(model.feature_importance(), index=features).sort_values(ascending=False) train_preds[valid_index] += model.predict(valid2[features], num_iteration=model.best_iteration) print('Validset score: {}'.format(mean_squared_error(labels, train_preds)*0.5)) print('Cross Validation spend {} seconds'.format(time.time() - t0))以上就是本篇文章的主要内容。下一篇我们将关注另一种高效的Boosting框架——CatBoost。
参考资料：
LightGBM: A Highly Efficient Gradient Boosting Decision Tree
https://lightgbm.readthedocs.io/en/latest/
往期精彩：
数学推导+纯Python实现机器学习算法27：LDA线性判别分析
一个算法工程师的成长之路
长按二维码.关注机器学习实验室
喜欢您就点个在看！