机器学习8：集成学习--LightGBM

目录：

一、LightGBM算法原理

1，Gradient-based One-Side Sampling(GOSS)

2，ExclusiveFeature Bundling (EFB)

3，XGboost与LightGBM比较：

3.1，Histogram VS pre-sorted

3.2，Histogram算法与pre-sorted算法对比

4，leaf-wise VS level-wise

5，特征并行和数据并行：

5.1，特征并行

5.1.1，Lightgbm中的特征并行

5,2，数据并行

5.2.1，Lightbgm中的数据并行

6，CatBoost

二、python代码实现

LightGBM相关知识模块：Histogram VS pre-sorted，leaf-wiseVS level-wise，特征并行和数据并行，顺序访问梯度，支持类别特征， CatBoost(了解)。

一、LightGBM算法原理

Lightgbm是GBDT的另一种实现方法, 在GBDT的基础之上, 采用了两种新的策略。

LightGBM是一个梯度Boosting框架，使用基于决策树的学习算法。它可以说是分布式的，高效的，有以下优势：

1）更快的训练效率

2）低内存使用

3）更高的准确率

4）支持并行化学习

5）可以处理大规模数据

与常见的机器学习算法对比，速度是非常快。

Lightgbm是GBDT的另一种实现方法, 在GBDT的基础之上, 采用了两种新的策略。

1，Gradient-based One-Side Sampling(GOSS)：

在Adaboost中, 权重是一个很好的指标来标识样本重要程度；在GBDT中, 可以用样本的梯度来衡量重要性, Lightgbm并依此进行采样, 梯度小的数据说明其已经得到了充分的训练了, 所以再训练时可以丢弃掉这些样本, 这样带来的负面效果则是改变了数据的分布, 而GOSS就是用来避免这个问题.

GOSS在保持大梯度样本的同时, 随机采样小梯度样本, 为补偿对数据分布的影响, 在计算信息增益的时候, 给小梯度样本引入了一个常量乘子,

GOSS伪代码如下：

输入: I:训练数据, d: 迭代轮数, a/b, 对 大/小 梯度数据的采样率, loss: 损失, L:弱学习器
models <- {}, fact <- (1-a)/b
topN <- a x len(I), randN <- b x len(I)
for i in range(0, d):
    preds <- models.predict(I)
    g <- loss(I,preds), w <- {1,1,...}
    sorted <- GetSortedIndices(abs(g))
    topSet <- sorted[1:topN]
    randSet <- RandomPick(sorted[topN: len(I)], randN)
    usedSet <-topSet + randSet
    w[randSet] *= fact ▷ Assign weight fact to the small gradient data
    newModel <- L(I[usedSet], -g[usedSet], w[usedSet])
    models.append(newModel)

2，ExclusiveFeature Bundling (EFB)：

合并高维数据中互斥特征至bundle,

复杂度O(#featuresx #data) -> O(#bundle x #data)。

EFB伪代码如下：

输入: numData: 数据大小, F: 互斥特征的bundle
binRanges <- {0}, totalBin <- 0
for f in F:
    totalBin += f.numBin
    binRanges.append(totalBin)
newBin <- new Bin(numData)

for i in range(0, numData):
    newBin[i] <- 0

    for j in range(0, len(F)):
        if F[j].bin[i] != 0:
            newBin[i] <- F[j].bin[i] + binRanges[j]

输出: newBin, bingRanges

3，XGboost与LightGBM比较：

· 关于XGboost的不足之处:

§ 1）每轮迭代时，都需要遍历整个训练数据多次。如果把整个训练数据装进内存则会限制训练数据的大小；如果不装进内存，反复地读写训练数据又会消耗非常大的时间。

§ 2）预排序方法的时间和空间的消耗都很大

· 总的来说Lightgbm具有以下优势:

§ 1）更快的训练效率

§ 2）低内存使用

§ 3）在数据并行的时候，数据间通信代价更低

和xgboost一样,Lightgbm可以直接支持category特征的处理，在用pandas结构使用LGB时可以指定哪一列是类别型数据，省去one-hot的步骤。如果类别过多，如商品ID，在one-hot处理后数据会变得过于稀疏，大大增加了训练集的大小，浪费计算资源。而LGB则会采用一种直方图式的方法去处理，max bin的默认值是256，对于category类型的feature，则是每一种取值放入一个bin，且当取值的个数大于max bin数时，会忽略那些很少出现的category值。在求split时，对于category类型的feature，算的是"按是否属于某个category值划分"的gain，它的实际效果就是类似one-hot的编码方法。

3.1，Histogram VS pre-sorted：

xgboost采用了预排序的方法来处理节点分裂。

这样计算的分裂点比较精确。但是，也造成了很大的时间开销。为了解决这个问题，Lightgbm 选择了基于Histogram 的决策树算法。相比于 pre-sorted算法，Histogram在内存消耗和计算代价上都有不少优势。

LightGBM采用了Histogram-based Algorithm

Histogram-based Algorithm伪代码如下：

for node in nodeSet:
      usedRows <- rowSet[node]

      for k in range(0, m):
          更新并建立Histgram

          for j in usedRows:
              bin = I.f[k][j].bin  #对特征k在第i层node结点索引为j的值取bin
              H[bin].y += I.y[j]
              H[bin].n += 1 

  根据最佳划分点更新rowSet和nodeSet

FindBestSplitByHistogram Algorithm伪代码如下：

输入: 训练数据X, 当前子树T, 一阶梯度G, 二阶梯度H
for leaf in T:

    for f in X.features:
        # 对于每个特征，首先为其创建一个直方图，这个直方图存储了两类信息 
        H = Histogram()

        遍历所有样本，累积上述的两类统计值到样本所属的bin中
        for i in range(0, rowSet):
            # 每个bin中样本的梯度之和H[f.bins[i]].g
            H[f.bins[i]].g += gi
            # 每个bin中样本数量
            H[f.bins[i]].n += 1

        遍历所有bin，分别以当前bin作为分割点, 计算其增益与当前的最大增益进行比较
        for i in range(0, len(H)):
            SL += H[i].g
            nL += H[i].n

            gain = SL**2/nL + SR**2/nR - SP**2/nP

            if 此bin 中gain大于最大的增益点:
                更新

直方图优化算法需要在训练前预先把特征值转化为bin，将对每个特征的取值转换成分段函数，将所有样本在该特征上的取值划分到某一段（bin）中,最终把特征取值从连续值转化成了离散值

如[0,0.3)—>0，[0.3,0.7)—->1等。在Lightgbm中默认的#bins为256（1个字节的能表示的长度，可以设置）。对于分类特征来说，则是每一种取值放入一个bin，且当取值的个数大于max bin数时，会忽略那些很少出现的category值。在节点分裂的时候，不需要按照预排序算法那样计算每个特征，只需要计算#bins，这样大大加快了训练速度

直方图差加速

一个叶子的直方图可以由它的父亲节点的直方图与它兄弟的直方图做差得到,利用这个方法，Lightgbm可以在构造一个叶子（含有较少数据）的直方图后，可以用非常微小的代价得到它兄弟叶子（含有较多数据）的直方图

原来构造直方图，需要遍历该叶子上的所有数据，但直方图做差仅需遍历直方图的#bin个桶。使用这个方法，构建完一个叶子的直方图后，可以用非常微小的代价得到它兄弟的直方图，相当于速度提升了一倍。

3.2，Histogram算法与pre-sorted算法对比：

优势

·

1. Pre-sorted算法需要的内存约是训练数据的两倍，它需要用32位浮点(4Bytes)来保存feature value，并且对每一列特征，都需要一个额外的排好序的索引，这也需要32位(4Bytes)的存储空间。因此是(2 #data #features 4Bytes)。而对于 Histogram 算法，则只需要(#data #features * 1Bytes)的内存消耗，仅为pre-sorted算法的1/8。因为 Histogram 算法仅需要存储feature bin value (离散化后的数值)，不需要原始的 feature value，也不用排序，而bin value 用 1Bytes(256 bins) 的大小一般也就足够了。

·

1. 计算上的优势则是大幅减少了计算分割点增益的次数。对每一个特征，pre-sorted 需要对每一个不同特征值都计算一次分割增益，代价是O(#feature#distinct_values_of_the_feature)；而 Histogram 只需要计算#bins次，代价是(#feature#bins)。

·

1. 事实上，cache-miss对速度的影响是特别大的。预排序中有2个操作频繁的地方会造成cache miss，

§ a. 对梯度的访问，在计算gain的时候需要利用梯度，不同特征访问梯度的顺序都是不一样的，且是随机的，因此这部分会造成严重的cache-miss

§ b. 二是对于索引表的访问，预排序使用了一个行号到叶子节点号的索引表（row_idx_to_tree_node_idx ），来防止数据切分时对所有的数据进行切分，即只对该叶子节点上的样本切分。在与level-wise进行结合的时候，每一个叶子节点都要切分数据，这也是随机的访问。这样会带来严重的系统性能下降。而直方图算法则是天然的cache friendly。在直方图算法的第3个for循环的时候，就已经统计好了每个bin的梯度，因此，在计算gain的时候，只需要对bin进行访问，造成的cache-miss问题会小很多。

·

1. 在数据并行的时候，用 histgoram 可以大幅降低通信代价。用 pre-sorted 算法的话，通信代价是非常大的（几乎是没办法用的）。所以 xgoobst 在并行的时候也使用Histogram 进行通信。

劣势

Histogram 算法不能找到很精确的分割点，训练误差没有 pre-sorted 好。但从实验结果来看， Histogram 算法在测试集的误差和 pre-sorted 算法差异并不是很大，甚至有时候效果更好。实际上可能决策树对于分割点的精确程度并不太敏感，而且较“粗”的分割点也自带正则化的效果，再加上boosting算法本身就是弱分类器的集成。

4，leaf-wise VS level-wise：

level-wise：

Level-wise过一次数据可以同时分裂同一层的叶子，容易进行多线程优化，也好控制模型复杂度，不容易过拟合。但实际上Level-wise是一种低效的算法，因为它不加区分的对待同一层的叶子，带来了很多没必要的开销，因为实际上很多叶子的分裂增益较低，没必要进行搜索和分裂。

leaf-wise：

Leaf-wise则是一种更为高效的策略，每次从当前所有叶子中，找到分裂增益最大的一个叶子，然后分裂，如此循环。因此同Level-wise相比，在分裂次数相同的情况下，Leaf-wise可以降低更多的误差，得到更好的精度。Leaf-wise的缺点是可能会长出比较深的决策树，产生过拟合。因此LightGBM在Leaf-wise之上增加了一个最大深度的限制，在保证高效率的同时防止过拟合。

5，特征并行和数据并行：

5.1，特征并行：

特征并行主要是并行化决策树中寻找最优划分点(“Find Best Split”)的过程，这部分最为耗时。

传统算法：

1），垂直划分数据（对特征划分），不同的worker有不同的特征集

2），每个workers找到局部最佳的切分点{feature,threshold}

3），workers使用点对点通信，找到全局最佳切分点

4），具有全局最佳切分点的worker进行节点分裂，然后广播切分后的结果（左右子树的instanceindices）

5），其它worker根据收到的instanceindices也进行划分。

传统算法的缺点是：

1），无法加速split的过程，该过程复杂度为O(#data)，当数据量大的时候效率不高

2），需要广播划分的结果（左右子树的instance indices），1条数据1bit的话，大约需要花费O(#data/8)。

5.1.1，Lightgbm中的特征并行：

每个worker保存所有的数据集，这样找到全局最佳切分点后各个worker都可以自行划分，就不用进行广播划分结果，减小了网络通信量。过程如下：

1），每个workers找到局部最佳的切分点{feature,threshold}

2），workers使用点对点通信，找到全局最佳切分点

3），每个worker根据全局全局最佳切分点进行节点分裂。

缺点：

1），split过程的复杂度仍是O(#data)，当数据量大的时候效率不高

2），每个worker保存所有数据，存储代价高。

5,2，数据并行：

传统算法：

1），水平切分数据，不同的worker拥有部分数据

2），每个worker根据本地数据构建局部直方图

3），合并所有的局部直方图得到全部直方图

3.1），采用点对点方式(point-to-pointcommunication algorithm)进行通讯，每个worker通讯量为O(#machine∗#feature∗#bin)

3.2），采用collective communicationalgorithm(如“All Reduce”)进行通讯（相当于有一个中心节点，通讯后在返回结果），每个worker的通讯量为O(2∗#feature∗#bin)

4），根据全局直方图找到最优切分点并进行分裂。

5.2.1，Lightbgm中的数据并行：

1），使用“Reduce Scatter”将不同worker的不同特征的直方图合并，然后workers在局部合并的直方图中找到局部最优划分，最后同步全局最优划分。

2），前面提到过，可以通过直方图作差法得到兄弟节点的直方图，因此只需要通信一个节点的直方图。

通信开销降为O(0.5∗#feature∗#bin)

6，CatBoost：

CatBoost在两方面尤其强大

· 它产生了最先进的结果，而且不需要进行广泛的数据训练

· 为更多的描述性数据格式提供了强大的“开箱即用”支持

· 性能:

CatBoost提供了一种先进效果，它在性能方面与任何领先的机器学习算法都可以抗衡。

· 自动处理分类特性:

不需要任何显式的预处理来将类别转换为数字。CatBoost使用在各种统计上的分类特征和数值特征的组合将分类值转换成数字。你可以在这里读到更多相关信息。

· 鲁棒性:

它减少了对广泛的超参数调优的需求，并降低了过度拟合的机会，这也导致了模型变得更加具有通用性。虽然CatBoost有多个参数可以调优，但它还包含一些参数，比如树的数量、学习速率、正则化、树的深度等等。

CatBoost不需要像XGBoost和LightGBM那样将数据集转换为任何特定格式

二、python代码实现：

使用达观杯文本竞赛数据实现一个简单的LightGBM模型，如下：

# 第五部分：lightGBM模型
import numpy as np
import pandas as pd
from sklearn.model_selection import train_test_split
from sklearn.metrics import f1_score
import time
import pickle
import lightgbm as LGB
from sklearn.externals import joblib

t_start = time.time()
data_path = 'Datasets/DaGuan/'
feature_path = 'Datasets/DaGuan/feature_file/'
proba_path = 'Datasets/DaGuan/proba_file/'
model_path = 'Datasets/DaGuan/model_file/'
result_path ="Datasets/DaGuan/result/"


# 0 自定义验证集的评价函数
print("0 自定义验证集的评价函数")
def f1_score_vali(preds, data_vali):
    labels = data_vali.get_label()
    preds = np.argmax(preds.reshape(19, -1), axis=0)
    score_vali = f1_score(y_true=labels, y_pred=preds, average='macro')
    return 'f1_score', score_vali, True


#1 读取数据,并转换到LGB的标准数据格式
print("1 读取数据,并转换到LGB的标准数据格式")
data_fp = open(feature_path + 'data_w_tfidf.pkl' , 'rb')
x_train, y_train, x_test = pickle.load(data_fp)
data_fp.close()

#2 划分训练集和验证集，验证集比例为test_size

print("划分训练集和验证集，验证集比例为test_size")
x_train, x_vali, y_train, y_vali = train_test_split(x_train, y_train, test_size=0.1, random_state=0)
d_train = LGB.Dataset(data=x_train, label=y_train)
d_vali = LGB.Dataset(data=x_vali, label=y_vali)


#3 训练LGB分类器
print("3 训练LGB分类器")
params = {
    'boosting': 'gbdt',
    'application': 'multiclassova',
    'num_class': 19,
    'learning_rate': 0.1,
    'num_leaves': 31,
    'max_depth': -1,
    'lambda_l1': 0,
    'lambda_l2': 0.5,
    'bagging_fraction': 1.0,

}

bst = LGB.train(params, d_train, num_boost_round=800, valid_sets=d_vali, feval=f1_score_vali,
                early_stopping_rounds=None,
                verbose_eval=True)

joblib.dump(bst, model_path + "LGB_data_w_tfidf.m")


#4 对测试集进行预测;将预测结果转换为官方标准格式；并将结果保存至本地
print("4 对测试集进行预测;将预测结果转换为官方标准格式；并将结果保存至本地")
y_proba = bst.predict(x_test)
y_test = np.argmax(y_proba, axis=1) + 1

df_result = pd.DataFrame(data={'id': range(5000), 'class': y_test.tolist()})
df_proba = pd.DataFrame(data={'id': range(5000), 'proba': y_proba.tolist()})

df_result.to_csv(result_path  + 'LGB_data_w_tfidf_result.csv', index=False)
df_proba.to_csv(result_path + 'LGB_data_w_tfidf_proba.csv', index=False)
t_end = time.time()
print("训练结束，耗时:{}min".format((t_end - t_start) / 60))

Reference：

LightGBM中文文档：https://lightgbm.apachecn.org/#/

https://zhuanlan.zhihu.com/p/25308051

https://blog.csdn.net/anshuai_aw1/article/details/83040541

https://www.hrwhisper.me/machine-learning-lightgbm/