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直接安裝即可：
LightGBM提供了分類和回歸兩大類接口，下面以分類問題和iris數據集為例給出原生LightGBM接口的一個使用示例：
import pandas as pdimport lightgbm as lgbfrom sklearn.metrics import mean_squared_errorfrom sklearn.datasets import load_irisfrom sklearn.model_selection import train_test_splitfrom sklearn.datasets import make_classification
iris = load_iris()data = iris.datatarget = iris.targetX_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 timeimport numpy as npimport pandas as pdimport lightgbm as lgbfrom sklearn.model_selection import KFoldfrom sklearn.metrics import mean_squared_error
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 BoostingDecision Tree
https://lightgbm.readthedocs.io/en/latest/
往期精彩：
數學推導+純Python實現機器學習算法27：LDA線性判別分析
一個算法工程師的成長之路
長按二維碼.關注機器學習實驗室