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 lightgbm LightGBM提供了分類和回歸兩大類接口，下面以分類問題和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