LightGBM: A Highly Efficient Gradient Boosting Decision Tree.

梯度提升决策树GBDT是把决策树作为基学习器的梯度提升方法，通过顺序生成基学习器构造强学习器。LightGBM（Light Gradient Boosting Machine）是一个实现GBDT算法的工程框架，支持高效率的并行训练，并且具有更快的训练速度、更低的内存消耗、更好的准确率、支持分布式、可以快速处理海量数据等特点。

GBDT在每一次迭代时都需要多次遍历整个训练数据集。如果把整个数据集装进内存则需要限制训练数据的大小；如果在硬盘中反复地读写数据又会消耗非常多的时间。在面对工业级的海量数据时，GBDT算法不能满足需求。LightGBM解决了GBDT在海量数据时遇到的问题，可以更好更快地用于工业实践。

LightGBM的主要优点是：

LightGBM的主要缺点是：

  1. 按叶生长可能会长出比较深的决策树，产生过拟合，需要限制树的最大深度；
  2. LightGBM是基于偏差的集成算法，对噪声点较为敏感；
  3. 在寻找最优解时，依次考虑每个特征的最优切分变量，没有综合考虑全部特征。

1. 直方图算法 Histogram algorithm

LightGBM把数据的每一个特征存储在一个直方图(histogram)中。直方图算法的基本思想是：先把连续的浮点特征值按照范围均分成$k$个区间，并离散化成$k$个整数；同时构造一个具有$k$个箱子(bin)的直方图。在遍历数据特征的时候，在直方图中累积离散化的特征值。在切分数据时根据直方图的离散值遍历寻找最优的分割点。

直方图算法的主要优点：

特征被离散化后找到的分割点并不是很精确，但对最终精度的影响并不是很大。原因是决策树本来就是一种弱学习器，分割点是否精确并不是太重要；较粗的分割点也有正则化的效果，可以有效地防止过拟合；即使单棵树的训练误差比精确分割的算法大，在梯度提升的框架下整体没有太大的影响。

把数据存储为直方图后，可以通过直方图做差加速。一个子结点的直方图可以由父结点的直方图与兄弟结点的直方图做差得到，并且直方图做差仅需遍历直方图的$k$个箱子。在实际构建树的过程中，LightGBM首先计算直方图小的子结点，然后利用直方图做差来获得直方图大的子结点，以实现较小的计算代价。

2. 决策树的按叶生长策略 Leaf-wise

大多数GBDT工具使用按层生长(level-wise)的决策树生长策略。该策略遍历一次数据时可以同时分裂同一层的结点，容易进行多线程优化，容易控制模型复杂度，不容易过拟合。但实际上按层生长是一种低效的算法，因为它不加区分的对待同一层的结点，实际上很多结点的分裂增益较低，没必要进行搜索和分裂，因此带来了很多不必要的计算开销。

LightGBM采用按叶生长(Leaf-wise)的决策树生长策略，该策略每次从当前所有结点中找到分裂增益最大的结点进行分裂，并循环该过程。在分裂次数相同的情况下，按叶生长可以降低更多的误差，得到更好的精度。按叶生长的缺点是可能会长出比较深的决策树，产生过拟合。因此LightGBM在按叶生长的基础上限制了树的最大深度，在保证高效率的同时防止过拟合。

3. 单边梯度采样算法 Gradient-based One-Side Sampling

单边梯度采样算法（GOSS）从减少样本量的角度出发，只使用具有较大梯度的样本和一小部分小梯度的样本计算分裂增益，在减少数据量和保证精度上实现平衡。

在LightGBM方法中，每个数据都有不同的梯度值，梯度小的样本训练误差也比较小，说明数据已经被模型学习得很好了；而梯度大的样本对分裂增益有更大的影响。GOSS的想法就是丢掉对计算分裂增益没有帮助的梯度小的数据，然而直接丢弃这些数据会改变原数据的总体分布，将会影响模型的训练精度。

GOSS首先将要进行分裂的特征的所有取值按照梯度绝对值大小降序排序，选取梯度绝对值最大的$a$个数据；然后在剩下的较小梯度数据中随机选择$b$个数据，将这$b$个数据乘以一个常数$\frac{1-a}{b}$。这样算法就会更关注训练不足的样本，而不会过多改变原数据集的分布。最后使用这$a+b$个数据来计算分裂增益。

4. 互斥特征捆绑算法 Exclusive Feature Bundling

高维度的数据往往是稀疏的，其中的部分特征是互斥的（即特征之间具有较强的相关性），把这些互斥特征捆绑起来不会丢失信息，能够无损地减少特征的数量。

互斥特征捆绑算法(EFB)把特征的互斥问题转化为图着色问题来求解，将所有的特征视为图的各个节点，把互斥的特征用一条边连接起来，边的权重就是两个相连接的特征的互斥值。此时需要捆绑的特征就是在图着色问题中要涂上同一种颜色的点。具体步骤如下：

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

可以用互斥比率 $\gamma$ 衡量总体互斥程度，$\gamma$越小则可以得到更少的特征包，进一步提高计算效率，同时对精度的影响为$O([(1-\gamma)n]^{-2/3})$；通过设置合适的$\gamma$能够完成精度和效率之间的平衡。

EFB算法的时间复杂度和特征数量的平方成正比。当特征数量特别大时，LightGBM提出了一种更加高效的无图的排序策略：将特征按照非零值的个数排序，因为更多的非零值通常会导致特征的互斥。

对互斥的特征进行捆绑时，应能保证原始特征能从合并的特征中分离出来。由于特征在保存时将连续的值保存为直方图中离散的箱子，可以通过在特征值中加一个偏置常量，使得不同特征的值分到不同箱子中。比如捆绑两个特征A和B，A特征的原始取值为区间$[0,10)$，B特征的原始取值为区间$[0,20)$，可以在B特征的取值上加一个偏置常量$10$，将其取值范围变为$[10,30)$，最终捆绑后的特征取值范围为$[0,30)$。

5. 支持类别特征

大多数机器学习工具都无法直接支持类别特征，一般需要把类别特征通过one-hot编码转化到多维的$0/1$特征。但决策树并不推荐使用one-hot编码，尤其当类别个数很多的情况下，会存在以下问题：

为了解决one-hot编码处理类别特征的不足，LightGBM优化了对类别特征的支持，可以直接输入类别特征，不需要额外的$0/1$展开。LightGBM采用many-vs-many的切分方式把类别特征分为两个子集，实现类别特征的最优切分。假设某维特征有$k$个类别，则共有$2^{k-1}-1$种切分方式，时间复杂度为$O(2^k)$，LightGBM进一步优化为$O(k \log k)$的时间复杂度。

LightGBM切分类别特征的方法如下。在枚举分割点之前，先把直方图按照每个类别对应的标签均值$avg(y)=\frac{sum(y)}{count(y)}$进行排序；然后按照排序的结果依次枚举最优分割点。

6. 支持高效并行

⚪ 特征并行 Feature Parallelization

特征并行的主要思想是不同机器在不同特征集合上分别寻找最优的分割点，然后在机器间同步最优的分割点。特征并行方法的缺点是需对数据进行垂直划分，每台机器所存储的数据不同，使用不同机器找到不同特征的最优分裂点后，划分结果需要通过机器之间的通信进行同步，增加了额外的复杂度。

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

⚪ 数据并行 Data Parallelization

数据并行的主要思想是水平划分数据，让不同的机器先在本地构造直方图，然后进行全局的合并，最后在合并的直方图上寻找最优分割点。这种数据并行的主要缺点是机器间的通信开销过大。

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

⚪ 投票并行 Voting-based Parallelization

基于投票的数据并行进一步优化数据并行中的通信代价，使通信代价变成常数级别。在数据量很大的时候，使用投票并行的方式只合并部分特征的直方图从而达到降低通信量的目的，可以得到非常好的加速效果。大致步骤为两步：

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

7. 缓存命中率优化 cache

LightGBM所使用的直方图算法对缓存天生友好：

8. LightGBM的代码实现

pip install lightgbm

(1) LightGBM的主要参数

下面介绍lightgbm库中定义的LightGBM模型的主要参数：

⚪ 核心参数 Core Parameters

⚪ 学习控制参数 Learning Control Parameters

⚪ 数据集参数 Dataset Parameters

(2) 使用LightGBM原生接口进行多分类

下面以IRIS鸢尾花分类数据集为例，介绍使用LightGBM原生接口进行多分类任务的例子：

import lightgbm as lgb
# 设置LightGBM的参数
params = {
    'objective': 'multiclass',
    'num_class': 3,
    'learning_rate': 0.1,
    'lambda_l1': 0.1,
    'lambda_l2': 0.2,
    'max_depth': 4,
}

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
# 准备数据集
iris = load_iris()
X = iris.data
y = iris.target
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)

# 转换为Dataset数据格式
train_data = lgb.Dataset(X_train, label=y_train)
validation_data = lgb.Dataset(X_test, label=y_test)

# 训练LightGBM
gbm = lgb.train(params, train_data, valid_sets=[validation_data])

from sklearn.metrics import accuracy_score
# 对测试集进行预测
y_pred = gbm.predict(X_test)
y_pred = [list(x).index(max(x)) for x in y_pred]
print(accuracy_score(y_test, y_pred))

(3) 使用基于Scikit-learn接口的LightGBM进行回归

本节以kaggle竞赛中的House Prices回归问题为例，介绍使用基于Scikit-learn接口的LightGBM进行回归的方法。

该数据集一共有81列，第一列是id，最后一列是标签，中间79列是特征。这79列特征中，有43列是分类型变量，33列是整数变量，3列是浮点型变量。训练数据集中存在缺失值。

import pandas as pd
# 1.读文件
data = pd.read_csv('./dataset/train.csv')
data.dropna(axis=0, subset=['SalePrice'], inplace=True)

# 2.切分数据 (输入：特征) (输出：预测目标变量)
y = data.SalePrice
X = data.drop(['SalePrice'], axis=1).select_dtypes(exclude=['object'])

from sklearn.model_selection import train_test_split
# 3.切分训练集、测试集, 切分比例75 : 25
train_X, test_X, train_y, test_y = train_test_split(X.values, y.values, test_size=0.25)

from sklearn.impute import SimpleImputer
# 4.空值处理，默认方法：使用特征列的平均值进行填充
my_imputer = SimpleImputer()
train_X = my_imputer.fit_transform(train_X)
test_X = my_imputer.transform(test_X)

import lightgbm as lgb
# 5.调用LightGBM模型，使用训练集数据进行训练
my_model = lgb.LGBMRegressor(
    objective='regression', num_leaves=31,
    learning_rate=0.05, n_estimators=20,
    verbosity=2)
# 对应的lgb.LGBClassifier()为分类模型
my_model.fit(train_X, train_y, verbose=False)

# 6.使用模型对测试集数据进行预测
predictions = my_model.predict(test_X)

from sklearn.metrics import mean_absolute_error
# 7.对模型的预测结果进行评判（平均绝对误差）
print("Mean Absolute Error : " + str(mean_absolute_error(predictions, test_y)))
print('Feature importances:', list(my_model.feature_importances_))

from sklearn.externals import joblib
# 8.模型存储和加载
joblib.dump(my_model, 'load_model.pkl')
my_model = joblib.load('load_model.pkl')

from sklearn.model_selection import GridSearchCV
# 9.超参数的网格搜索
estimator = lgb.LGBMRegressor(num_leaves=31)
param_grid = {
    'learning_rate': [0.01, 0.1, 1],
    'num_iterations': [20, 40]
}
lgbm = GridSearchCV(estimator, param_grid)
lgbm.fit(X_train, y_train)
print('Best parameters found by grid search are:', lgbm.best_params_)