【机器学习基础】数学推导+纯Python实现机器学习算法24：LightGBM
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 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回歸模型五折交叉驗證訓練的代碼模板，僅供大家參考。
? ? 以上就是本篇文章的主要內容。下一篇我們將關注另一種高效的Boosting框架——CatBoost。
參考資料：
LightGBM: A Highly Efficient Gradient Boosting Decision Tree
https://lightgbm.readthedocs.io/en/latest/
往期精彩：
數學推導+純Python實現機器學習算法23：kmeans聚類
數學推導+純Python實現機器學習算法22：最大熵模型
數學推導+純Python實現機器學習算法21：馬爾科夫鏈蒙特卡洛
數學推導+純Python實現機器學習算法20：LDA線性判別分析
數學推導+純Python實現機器學習算法19：PCA降維
數學推導+純Python實現機器學習算法18：奇異值分解SVD
數學推導+純Python實現機器學習算法17：XGBoost
數學推導+純Python實現機器學習算法16：Adaboost
數學推導+純Python實現機器學習算法15：GBDT
數學推導+純Python實現機器學習算法14：Ridge嶺回歸
數學推導+純Python實現機器學習算法13：Lasso回歸
數學推導+純Python實現機器學習算法12：貝葉斯網絡
數學推導+純Python實現機器學習算法11：樸素貝葉斯
數學推導+純Python實現機器學習算法10：線性不可分支持向量機
數學推導+純Python實現機器學習算法8-9：線性可分支持向量機和線性支持向量機
數學推導+純Python實現機器學習算法7：神經網絡
數學推導+純Python實現機器學習算法6：感知機
數學推導+純Python實現機器學習算法5：決策樹之CART算法
數學推導+純Python實現機器學習算法4：決策樹之ID3算法
數學推導+純Python實現機器學習算法3：k近鄰
數學推導+純Python實現機器學習算法2：邏輯回歸
數學推導+純Python實現機器學習算法1：線性回歸
往期精彩回顧適合初學者入門人工智能的路線及資料下載機器學習及深度學習筆記等資料打印機器學習在線手冊深度學習筆記專輯《統計學習方法》的代碼復現專輯 AI基礎下載機器學習的數學基礎專輯獲取一折本站知識星球優惠券，復制鏈接直接打開：https://t.zsxq.com/yFQV7am本站qq群1003271085。加入微信群請掃碼進群：總結
以上是生活随笔為你收集整理的【机器学习基础】数学推导+纯Python实现机器学习算法24：LightGBM的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 【机器学习基础】一文说透正则项与模型复杂
- 下一篇： 【NLP】6种用于文本分类的开源预训练模