时隔两年，再次复盘之前写的lightgbm的这篇文章，发现当时主要是为了实践使用，并没有写很多的理论背景，这次在文章的前面部分，添加理论部分，后面依旧是简单的使用和参数的含义。希望迎接更好的2020年~
——————————————————————————
在第二部分原理中，结合了原始作者的论文，还有网络上比较好的几篇的讲解
lightGBM的论文
一、简介——机器学习竞赛的好工具
lightGBM是一个很好用的机器学习竞赛算法实现，他的本质是GDBT算法的一种优化实现，重点在于light这个单词上。作者在论文中提到，lightgbm可以比xgboost快6倍，同时使用更加小的内存，并且保持算法的高准确率。那么是如何实现light的呢？
主要是通过下面这些方式实现的：
- GOSS(Gradient-based One-Side Sampling)：减少样本数
- EFB (Exclusive Feature Bundling ):减少特征数
- 直方图差加速
- 自动处理缺省值，包括是否将0视为缺省值。
- 处理类别特征
- Leaf-wise生长策略
其中第一第二点，是在作者论文中就提到的，极大优化的时间和空间开销的方法，第三点是在分裂特征的时候使用的，第5点是最让人感动的，可以在拿到数据之后，快速的进行训练，不需要对离散特征进行one-hot encoding.第6点可以在相同的分裂次数时，获得更高的精度和更低的误差。下面将分别介绍这些优化方法。
二、lightgbm的优势们
0. 直方图算法
这个不是lightgbm首先提出的，但却是是light的一个基石。在训练树的时候，需要找到最佳划分节点，为此其中需要遍历特征下的每一个value，这里通常有两种做法：pre-sorted algorithm(预排序算法)和histogram-based algorithm（直方图算法）。
许多提升工具对于决策树的学习使用基于 pre-sorted 的算法。这是一个简单的解决方案，但是不易于优化。
LightGBM 利用基于 histogram 的算法 [3, 4, 5]，通过将连续特征（属性）值分段为 discrete bins 来加快训练的速度并减少内存的使用。
1. GOSS
我们知道传统的Adaboost其实数据集都是有一个权值的，用来衡量其重要程度，没有被好好训练的样本其权值就大，以便下一个基学习器对其多加训练，于是就可以依据该权值对其采用，这样就做到采用利用部分数据集。
但是在GBDT中，数据没有权重这个概念，那我们应该怎么做呢？虽然我们没有权重，但是我们每次使用决策树训练的是之前所有模型的残差（平方损失的情况下），或者说是负梯度方向。那么我们可以将每个样本的一阶导数看做权重，一阶导数大的说明离最优解还远，这部分样本带来的增益大，或者说这部分样本还没有被好好训练，下一步我们应该重点训练他们。
我们计算所有样本的梯度，然后排序，取前top a%作为大梯度样本，然后对剩下的（1-a）x n的样本取b%作为小梯度样本训练。但是这样会导致数据的分布发生变化，所以还有给小样本一个补偿，那就是乘以一个常数即（1-a）/b，可以看到当a=0时就变成了随机采用啦，这样抽的结果还是能保持准确率的。
这样训练的样本就只有原始样本的an + (1-a) x n x b了。在论文的实验中，a = 0.1, b=0.1(乃至更小）都没有影响最终的结果，还是和xgboost的结果那么精确。
2. EFB优化
通常，在GBDT和其最优的实现xgboost中，我们需要将类别型的特征预处理为onehot编码，否则就会认为是潜在有大小关系的。但是转为one hot之后，类别数大，gbdt这种树模型对高维稀疏特征的处理效果差。简直就是两难的问题啊。
我们先来理解一下为什么会效果差，GBDT是二叉树，使用one-hot编码的话，意味着在每一个决策节点上只能使用one vs rest（例如是不是狗，是不是猫等）的切分方式。当类别值很多时，每个类别上的数据可能会比较少，这时候切分会产生不平衡，这意味着切分增益也会很小（比较直观的理解是，不平衡的切分和不切分没有区别）。其次，可能因为训练数据的问题（噪声或者数据量太少），产生错的分支，导致过拟合。最后，一个直观的感觉是即使树很深了，但是使用的特征可能也不多。
lightgbm反其道行之，在训练的时候有意的将看起来像是one hot的好几类稀疏高维的特征结合在意思。咋么做到的呢？直观的就会问两个问题：
1）到底那些特征需要合并到一起
2）怎么合并到一起
2.1
论文定义了一个概念叫Exclusive Feature，意思是很少同时取到非零值的特征列。回想一下one-hot编码的特征，是不是当某一列特征为1时，其余的特征都是0，这些one-hot特征就是Exclusive Feature,还有其他一些潜在有关系的特征，也会有这种现象。EFB就是希望将这些特征合并起来。同时注意到有些特征并不是100%的互相排斥，但是呢？其也很少同时取非0值，如果我们允许一部分冲突，那么这部分特征就可以进一步进行合并，使得bundle进一步减少。
在实际算法中，作者首先计算每个特征和其他特征的冲突数量（同时取到非0的样本数），然后将特征按照总冲突数排序，依次遍历这些特征，检查该特征和其他特征的冲突数是否少于阈值T，如果少于阈值，那么就合并成一个bundle，如果无法和其他特征结合，就新建一个bundle.
作者为了优化速度，其不再建立图了，而是统计非零的个数，非零个数越多就说明冲突越大，互相排斥越小，越不能捆绑到一起。
2.2
EFB直觉上可以理解为one-hot的反向操作。那么对于已经bundle到一起的特征，怎么在取值上区分出所有特征？方法也很简单（一般人都能想到）假如A特征的范围是[0,10),B特征的范围是[0,20),那么就给B特征加一个偏值，比如10，那么B的范围就变为[10,30)，所以捆绑为一个特征后范围就是[0,30]
3. 直方图加速
在GBDT中，在找到分裂点之后，需要统计左右树上的样本分布情况。在lightgbm中，因为我们使用了直方图对样本的特征进行预处理，那么只要知道父节点上的直方图，然后得到左子树上的直方图分布，就可以做差得到右子图上的直方图，不需要再重复计算。
说到这个直方图加速的概念，我们在脑中来模拟一下lightgbm划分最优分裂点的过程。
- 先看该特征下划分出的bin容器的个数，如果bin容器的数量小于4，直接使用one vs other方式, 逐个扫描每一个bin容器，找出最佳分裂点
- 对于bin容器较多的情况, 先进行过滤，只让子集合较大的bin容器参加划分阈值计算, 对每一个符合条件的bin容器进行公式计算(公式如下: 该bin容器下所有样本的一阶梯度之和/ 该bin容器下所有样本的二阶梯度之和 + 正则项(参数cat_smooth)，可以联想到在xgboost中，寻找最佳分裂点的时候，也是使用了类似的一个公式，只是分母是一阶导数的平方。得到一个值，根据该值对bin容器从小到大进行排序，然后分从左到右、从右到左进行搜索，得到最优分裂阈值。但是有一点，没有搜索所有的bin容器，而是设定了一个搜索bin容器数量的上限值，程序中设定是32，即参数max_num_cat。
LightGBM中对离散特征实行的是many vs many 策略，这32个bin中最优划分的阈值的左边或者右边所有的bin容器就是一个many集合，而其他的bin容器就是另一个many集合。 - 对于连续特征，划分阈值只有一个，对于离散值可能会有多个划分阈值，每一个划分阈值对应着一个bin容器编号，当使用离散特征进行分裂时，只要数据样本对应的bin容器编号在这些阈值对应的bin集合之中，这条数据就加入分裂后的左子树，否则加入分裂后的右子树。
这里有两个问题需要注意：
- 为什么按照一阶导数/二阶导数的值作为bin排序的顺序？其实可以看成前面说的熵（更简单的可以理解对当前特征分的好坏），这样做的目的就是熵大的在一边，熵小的在一边，假设排序后是a,b,c,d这样进行many vs many的组合时尽可能的保持了分的好的放一边，否则如果混乱的分的话，已经分的好的特征就又会和没有分的好的特征混在一起，那么其实后面的分就效率不高。
- 为什么需要左边遍历一次，右边遍历一次？其意义就在于缺省值到底是在哪里？其实这类问题叫做Sparsity-aware Split Finding稀疏感知算法，当从左到右，对于缺省值就规划到了右面，当方向相反时，缺省值都规划到了左面。还有一个用处，就是sorted_idx中的bin数和最大bin数可能不一样，前面有讲，bin中数据量大于一个阈值的才放进sorted_idx，后面是遍历sorted_idx，所以左右遍历的时候，分出某一边树的时候，剩下的bin分到另一边，这个剩下的bin是包括空值和没有在sorted_idx中的bin的，所以即使没有空值，而有bin是不在sorted_idx中的时候，左右遍历得到的结果也是不一样。
4. 自动处理缺省值
在2中，我们提到在最优分割点的选择的时候，需要左右遍历一次，遍历的意义就是为了将缺省值放置在合适的位置。从左到右，对于缺省值就规划到了右面，当方向相反时，缺省值都规划到了左面。当从左到右时，我们记录不论是当前一阶导数和也好二阶导数也罢，都是针对有值的（缺省值就没有一阶导数和二阶导数），那么我们用差加速得到右子树，既然左子树没有包括缺省值，那么总的减去左子树自然就将缺省值归到右子树了
5. 处理类别特征
lightgbm相对于其他GBDT实现的优点之一，就是不需要对类别特征做one-hot预处理。
为了解决one-hot编码处理类别特征的不足。LGBM采用了Many vs many的切分方式，实现了类别特征的最优切分。用Lightgbm可以直接输入类别特征。
在上面的3中，在将lightgbm划分最优分裂点的过程的时候，已经提到了针对bins较少的情况是怎么做的，对于类别较多的bins是按照数值来进行操作的。
6.Leaf-wise生长策略
大部分决策树的学习算法通过 level(depth)-wise 策略生长树，而lightgbm使用Leaf-wise (Best-first) 的决策树生长策略。它将选取具有最大 delta loss 的叶节点来生长。 当生长相同的 #leaf，leaf-wise 算法可以比 level-wise 算法减少更多的损失。
当 #data 较小的时候，leaf-wise 可能会造成过拟合。 所以，LightGBM 可以利用额外的参数 max_depth 来限制树的深度并避免过拟合（树的生长仍然通过 leaf-wise 策略）。
我们通常将类别特征转化为 one-hot coding。 然而，对于学习树来说这不是个好的解决方案。 原因是，对于一个基数较大的类别特征，学习树会生长的非常不平衡，并且需要非常深的深度才能来达到较好的准确率。
事实上，最好的解决方案是将类别特征划分为两个子集，总共有 2^(k-1) - 1 种可能的划分 但是对于回归树 [7] 有个有效的解决方案。为了寻找最优的划分需要大约k * log(k) .
三、 lightgbm的使用
lightgbm的使用起来也很简单。大致步骤可以分为下面几个
- 首先用lgb包的DataSet类包装一下需要测试的数据；
- 将lightgbm的参数构成一个dict字典格式的变量
- 将参数字典，训练样本，测试样本，评价指标一股脑的塞进lgb.train()方法的参数中去
- 上一步的方法会自觉地得到最佳参数和最佳的模型，保存模型
- 使用模型进行测试集的预测
其中比较重要的是第二步也就是设置参数。有很多很重要的参数，在下面的第二部分（参数字典）中，我大概介绍一下使用的比较多的比较有意义的参数。
1. 安装
在已经安装了anaconda的windows 7环境下，在cmd控制面板中输入pip install lightgbm即实现了安装。在此之前需要已经下载了依赖包如setuptools, wheel, numpy 和 scipy。pip install setuptools wheel numpy scipy scikit-learn -U. 过程中没有碰到问题。
2. 训练数据包装
lightgbm的一些特点：
- LightGBM 支持 CSV, TSV 和 LibSVM 格式的输入数据文件。
- LightGBM 可以直接使用 categorical feature（类别特征）（不需要单独编码）。 Expo data 实验显示，与 one-hot 编码相比，其速度提高了 8 倍。可以在包装数据的时候指定哪些属性是类别特征。
- LightGBM 也支持加权训练，可以在包装数据的时候指定每条记录的权重
LightGBM 中的 Dataset 对象由于只需要保存 discrete bins（离散的数据块）, 因此它具有很好的内存效率. 然而, Numpy/Array/Pandas 对象的内存开销较大. 如果你关心你的内存消耗. 您可以根据以下方式来节省内存:
- 在构造 Dataset 时设置 free_raw_data=True （默认为 True）
- 在 Dataset 被构造完之后手动设置 raw_data=None
- 调用 gc
LightGBM Python 模块能够使用以下几种方式来加载数据:
- libsvm/tsv/csv txt format file（libsvm/tsv/csv 文本文件格式）
- Numpy 2D array, pandas object（Numpy 2维数组, pandas 对象）
- LightGBM binary file（LightGBM 二进制文件）
加载后的数据存在 Dataset 对象中.
要加载 numpy 数组到 Dataset 中:
data = np.random.rand(500, 10) # 500 个样本, 每一个包含 10 个特征
label = np.random.randint(2, size=500) # 二元目标变量, 0 和 1
train_data = lgb.Dataset(data, label=label)
在现实情况下，我们可能之前使用的是pandas的dataFrame格式在训练数据，那也没有关系，可以先使用sklearn包对训练集和测试集进行划分，然后再使用DataSet类包装。DataSet第一个参数是训练特征，第二个参数是标签
from sklearn.model_selection import train_test_split
X_train,X_val,y_train,y_val = train_test_split(X,Y,test_size=0.2)
xgtrain = lgb.Dataset(X_train, y_train)
xgvalid = lgb.Dataset(X_val, y_val)
在 LightGBM 中, 验证数据应该与训练数据一致（格式一致）.
保存 Dataset 到 LightGBM 二进制文件将会使得加载更快速:
train_data = lgb.Dataset('train.svm.txt')
train_data.save_binary('train.bin')
指定 feature names（特征名称）和 categorical features（分类特征）,注意在你构造 Dataset 之前, 你应该将分类特征转换为 int 类型的值。还可以指定每条数据的权重（比如在样本规模不均衡的时候希望少样本的标签对应的记录可以拥有较大的权重）
w = np.random.rand(500, )
train_data = lgb.Dataset(data, label=label, feature_name=['c1', 'c2', 'c3'],
categorical_feature=['c3'],weight=w)
或者
train_data = lgb.Dataset(data, label=label)
w = np.random.rand(500, )
train_data.set_weight(w)
3. 设置参数
- 参数字典
每个参数的含义后面介绍
lgb_params = {
'boosting_type': 'gbdt',
'objective': 'binary', #xentlambda
'metric': 'auc',
'silent':0,
'learning_rate': 0.05,
'is_unbalance': 'true', #当训练数据是不平衡的，正负样本相差悬殊的时候，可以将这个属性设为true,此时会自动给少的样本赋予更高的权重
'num_leaves': 64, # 一般设为少于2^(max_depth)
'max_depth': -1, #最大的树深，设为-1时表示不限制树的深度
'min_child_samples': 15, # 每个叶子结点最少包含的样本数量，用于正则化，避免过拟合
'max_bin': 200, # 设置连续特征或大量类型的离散特征的bins的数量
'subsample': 0.8, # Subsample ratio of the training instance.
'subsample_freq': 1, # frequence of subsample, <=0 means no enable
'colsample_bytree': 0.5, # Subsample ratio of columns when constructing each tree.
'min_child_weight': 0, # Minimum sum of instance weight(hessian) needed in a child(leaf)
#'scale_pos_weight':100,
'subsample_for_bin': 200000, # Number of samples for constructing bin
'min_split_gain': 0, # lambda_l1, lambda_l2 and min_gain_to_split to regularization
'reg_alpha': 2.99, # L1 regularization term on weights
'reg_lambda': 1.9, # L2 regularization term on weights
'nthread': 10,
'verbose': 0,
}
- 评价函数
评价函数可以是自定义的，也可以是sklearn中使用的。这里是一个自定义的评价函数写法：
def feval_spec(preds, train_data):
from sklearn.metrics import roc_curve
fpr, tpr, threshold = roc_curve(train_data.get_label(), preds)
tpr0001 = tpr[fpr <= 0.0005].max()
tpr001 = tpr[fpr <= 0.001].max()
tpr005 = tpr[fpr <= 0.005].max()
#tpr01 = tpr[fpr.values <= 0.01].max()
tprcal = 0.4 * tpr0001 + 0.3 * tpr001 + 0.3 * tpr005
return 'spec_cal',tprcal,True
如果是自定义的评价函数，那么需要函数的输入是预测值、输入数据。返回参数有三个，第一个是评价指标名称、第二个是评价值、第三个是True表示成功。
4. 训练
4.1基础版
训练一个模型时, 需要一个 parameter list（参数列表、字典）和 data set（数据集）这里使用上面定义的param参数字典和上面提到的训练数据:
num_round = 10
bst = lgb.train(param, train_data, num_round, valid_sets=[test_data])
4.2 交叉验证
时间充足的时候，应该使用交叉验证来选择最好的训练模型，使用 5-折 方式的交叉验证来进行训练（4 个训练集, 1 个测试集）:
num_round = 10
lgb.cv(param, train_data, num_round, nfold=5)
4.3 提前停止
如果您有一个验证集, 你可以使用提前停止找到最佳数量的 boosting rounds（梯度次数）. 提前停止需要在 valid_sets 中至少有一个集合. 如果有多个，它们都会被使用:
bst = lgb.train(param, train_data, num_round, valid_sets=valid_sets,
early_stopping_rounds=10)
bst.save_model('model.txt', num_iteration=bst.best_iteration)
该模型将开始训练, 直到验证得分停止提高为止. 验证错误需要至少每个 early_stopping_rounds 减少以继续训练.
如果提前停止, 模型将有 1 个额外的字段: bst.best_iteration. 请注意 train() 将从最后一次迭代中返回一个模型, 而不是最好的一个.. 请注意, 如果您指定多个评估指标, 则它们都会用于提前停止.
提前停止可以节约训练的时间。
5. 保存模型
在训练完成后, 可以使用如下方式来存储模型:
bst.save_model('model.txt')
已经训练或加载的模型都可以对数据集进行预测:
6. 预测
7 个样本, 每一个包含 10 个特征
data = np.random.rand(7, 10)
ypred = bst.predict(data)
如果在训练过程中启用了提前停止, 可以用 bst.best_iteration 从最佳迭代中获得预测结果:
ypred = bst.predict(data, num_iteration=bst.best_iteration)
