圖解機器學習算法(11) | LightGBM模型詳解（機器學習通關指南·完結）

Clay*more 2022-06-20 發(fā)布于北京

展開全文

引言

https://blog.csdn.net/ShowMeAI/article/details/123406621

之前ShowMeAI對強大的boosting模型工具XGBoost做了介紹（詳見ShowMeAI文章圖解機器學習 | XGBoost模型詳解）。本篇我們來學習一下GBDT模型（詳見ShowMeAI文章圖解機器學習 | GBDT模型詳解）的另一個進化版本：LightGBM。

LightGBM是微軟開發(fā)的boosting集成模型，和XGBoost一樣是對GBDT的優(yōu)化和高效實現，原理有一些相似之處，但它很多方面比XGBoost有著更為優(yōu)秀的表現。官方給出的這個工具庫模型的優(yōu)勢如下：

更快的訓練效率
低內存使用
更高的準確率
支持并行化學習
可處理大規(guī)模數據
支持直接使用category特征

下圖是一組實驗數據，在這份實驗中，LightGBM比XGBoost快將近10倍，內存占用率大約為XGBoost的1/6，準確率也略有提升。

1.LightGBM動機

互聯(lián)網領域的算法應用，通常背后都有海量的大數據。深度學習中一系列神經網絡算法，都是以mini-batch的方式喂數據迭代訓練的，總訓練數據量不受內存限制。

但我們用到的機器學習算法，比如GBDT（參考ShowMeAI文章 GBDT詳解）在每一次迭代的時候，都需要遍歷整個訓練數據多次。

如果把整個訓練數據一次性裝進內存，會明顯限制訓練數據的大小。
如果不裝進內存，反復地讀寫訓練數據又會消耗非常大的時間。

面對工業(yè)級海量的數據，普通的GBDT算法無法滿足需求。LightGBM提出的主要原因之一，就是為了解決上述大數據量級下的GBDT訓練問題，以便工業(yè)實踐中能支撐大數據量并保證效率。

2.XGBoost優(yōu)缺點

我們之前介紹過強大的XGBoost（詳見ShowMeAI文章圖解機器學習 | XGBoost模型詳解），但XGBoost也依舊存在一些缺點，LightGBM針對其中的一部分進行了調整優(yōu)化。XGB優(yōu)缺點歸納如下：

1）精確貪心算法

輪迭代時，都需要遍歷整個訓練數據多次。如果把整個訓練數據裝進內存則會限制訓練數據的大??；如果不裝進內存，反復地讀寫訓練數據又會消耗非常大的時間。

G a i n = 1 2 [ G L 2 H L + λ + G R 2 H R + λ ? ( G L + G R ) 2 H L + H R + λ ? γ ] Gain=\frac{1}{2}\left [ \frac{G_{L}^{2}}{H_{L}+\lambda} + \frac{G_{R}^{2}}{H_{R}+\lambda} - \frac{\left(G_{L}+G_{R}\right)^{2}}{H_{L}+H_{R}+\lambda} - \gamma \right ] Gain=21[HL+λGL2+HR+λGR2?HL+HR+λ(GL+GR)2?γ]

優(yōu)點：可以找到精確的劃分條件。
缺點：計算量巨大、內存占用巨大、易產生過擬合。

2）Level-wise生長方式

XGBoost采用Level-wise的增長策略：基于層進行生長，直到達到停止條件。這種增長策略方便并行計算每一層的分裂節(jié)點，提高了訓練速度，但同時也因為節(jié)點增益過小增加了很多不必要的分裂，增加了計算量。

優(yōu)點：可以使用多線程、可以加速精確貪心算法。
缺點：效率低下，可能產生不必要的葉結點。

3）對cache優(yōu)化不友好

在預排序后，特征對梯度的訪問是一種隨機訪問，并且不同的特征訪問的順序不一樣，無法對cache進行優(yōu)化。同時，在每一層長樹的時候，需要隨機訪問一個行索引到葉子索引的數組，并且不同特征訪問的順序也不一樣，也會造成較大的cache miss。

3.LightGBM優(yōu)化點

上個部分其實也是LightGBM作者們，構建新算法時著重優(yōu)化的點。概括來說，LightGBM主要有以下特點：

基于Histogram的決策樹算法
帶深度限制的Leaf-wise的葉子生長策略
直方圖做差加速
直接支持類別特征（Categorical Feature）
Cache命中率優(yōu)化
基于直方圖的稀疏特征優(yōu)化
多線程優(yōu)化

4.決策樹算法

1）XGBoost：Pre-sorted算法

XGBoost使用的是Pre-sorted算法，能夠更精確的找到數據分隔點。

首先，對所有特征按數值進行預排序。
其次，在每次的樣本分割時，用O(#data)的代價找到每個特征的最優(yōu)分割點。
最后，找到最后的特征以及分割點，將數據分裂成左右兩個子節(jié)點。

這種pre-sorting算法能夠準確找到分裂點，但是在空間和時間上有很大的開銷。

由于需要對特征進行預排序并且需要保存排序后的索引值（為了后續(xù)快速的計算分裂點），因此內存需要訓練數據的兩倍。
在遍歷每一個分割點的時候，都需要進行分裂增益的計算，消耗的代價大。

2）LightGBM：直方圖算法

LightGBM使用的是直方圖算法（histogram algorithm），占用的內存更低，數據分割的復雜度更低。直方圖算法思想是：

將連續(xù)的浮點特征離散成k個離散值，并構造寬度為k的Histogram。
遍歷訓練數據，統(tǒng)計每個離散值在直方圖中的累計統(tǒng)計量。
在進行特征選擇時，只需要根據直方圖的離散值，遍歷尋找最優(yōu)的分割點。

（1）內存優(yōu)化

直方圖算法可以很大程度降低內存消耗，它不僅不需要額外存儲預排序的結果，還可以只保存特征離散化后的值（一般用8位整型存儲就足夠了）。

如圖所示，用8位整型存儲，內存消耗可以降低為原來的1/8。

（2）計算量優(yōu)化

應用直方圖算法，計算代價也大幅降低，預排序算法每遍歷一個特征值就需要計算一次分裂的增益，而直方圖算法只需要計算k次（k可以認為是常數），時間復雜度從O(#data*#feature)直接優(yōu)化到 O(k#*features)。

（3）注意點

直方圖算法的理解和注意點如下：

使用分桶bin替代原始數據相當于增加了正則化。
使用分桶bin意味著很多數據的細節(jié)特征丟失，相似的數據如果劃分到相同的桶中，數據之間的差異就無法捕獲了。
分桶bin數量決定了正則化的程度，bin越少懲罰越嚴重，欠擬合風險越高。
因為預先設定了bin的范圍，構建直方圖時不需要對數據進行排序。
直方圖保存「劃分閾值」、「當前bin內樣本數」、「當前bin內所有樣本的一階梯度和」。
閾值的選取是按照直方圖從小到大遍歷，使用了上面的一階梯度和，目的是得到劃分之后△loss最大的特征及閾值。

（4）直方圖算法優(yōu)缺點

Histogram算法并不是完美的。由于特征被離散化后，找到的并不是很精確的分割點，所以會對結果產生影響。但在實際的數據集上表明，離散化的分裂點對最終的精度影響并不大，甚至會好一些。原因在于decision tree本身就是一個弱學習器，采用Histogram算法會起到正則化的效果，有效地防止模型的過擬合。
時間上的開銷由原來的O(#data*#features)降到O(k*#features)。由于離散化，#bin遠小于#data，因此時間上有很大的提升。

Histogram算法還可以進一步加速。一個葉子節(jié)點的Histogram可以直接由父節(jié)點的Histogram和兄弟節(jié)點的Histogram做差得到。一般情況下，構造Histogram需要遍歷該葉子上的所有數據，通過該方法，只需要遍歷Histogram的k個捅。速度提升了一倍。

5.決策樹生長策略

1）樹生長策略調整

直方圖算法之上，LightGBM進行進一步的優(yōu)化。它沒有使用大多數GBDT工具使用的按層生長（Level-wise）的決策樹生長策略，而使用了帶有深度限制的按葉子生長（Leaf-wise）算法。

( p m , f m , v m ) = arg ? min ? ( p , f , v ) L ( T m ? 1 ( X ) . split ? ( p , f , v ) , Y ) \left(p_{m}, f_{m}, v_{m}\right)=\arg \min _{(p, f, v)} L\left(T_{m-1}(X) . \operatorname{split}(p, f, v), Y\right) (pm,fm,vm)=arg(p,f,v)minL(Tm?1(X).split(p,f,v),Y)

T m ( X ) = T m ? 1 ( X ) . split ? ( p m , f m , v m ) T_{m}(X)=T_{m-1}(X) . \operatorname{split}\left(p_{m}, f_{m}, v_{m}\right) Tm(X)=Tm?1(X).split(pm,fm,vm)

2）XGBoost：Level-wise

XGBoost采用的是Level-wise（按層生長）策略生長的，能夠同時分裂同一層的葉子，從而進行多線程優(yōu)化，不容易過擬合。

但不加區(qū)分的對待同一層的葉子，帶來了很多沒必要的開銷。因為實際上很多葉子的分裂增益較低，沒必要進行搜索和分裂。

3）LightGBM：Leaf-wise

LightGBM采用Leaf-wise（按葉子生長）生長策略，每次從當前所有葉子中找到分裂增益最大（一般也是數據量最大）的一個葉子，然后分裂，如此循環(huán)。

同Level-wise相比，在分裂次數相同的情況下，Leaf-wise可以降低更多的誤差，得到更好的精度。Leaf-wise的缺點是可能會長出比較深的決策樹，產生過擬合。因此LightGBM在Leaf-wise之上增加了一個最大深度的限制，在保證高效率的同時防止過擬合。

6.直方圖差加速

LightGBM另一個優(yōu)化是Histogram（直方圖）做差加速。整個構建過程中可以觀察到：一個葉子的直方圖可以由它的父親節(jié)點的直方圖與它兄弟的直方圖做差得到。

一般來說構造直方圖，需要遍歷該葉子上的所有數據，但直方圖做差僅需遍歷直方圖的k個桶。利用上述特征，LightGBM可以在構造一個葉子的直方圖后，可以用非常微小的代價得到它兄弟葉子的直方圖，在速度上可以提升一倍。

7.類別型特征支持

大多數機器學習工具都無法直接支持類別型特征，我們會先將其編碼再做后續(xù)建模，如果使用one-hot這種編碼方式還會降低空間和時間效率。

LightGBM優(yōu)化了對類別型特征的支持，可以直接輸入類別特征，不需要額外的編碼或one-hot 0/1展開。并在決策樹算法上增加了類別型特征的決策規(guī)則。

1）樹模型與one-hot編碼

one-hot編碼是處理類別特征的一個通用方法，然而在樹模型中，這可能并不一定是一個好的方法，尤其當類別特征中類別個數很多的情況下，主要的問題是：

問題1：可能無法在這個類別特征上進行切分。

使用one-hot編碼的話，意味著在每一個決策節(jié)點上只能使用one vs rest（例如是不是男性，是不是一線城市等）的切分方式。當類別值很多時，每個類別上的數據可能會比較少，這時候切分會產生不平衡，這意味著切分增益也會很小。

問題2：影響決策樹的學習。

就算可以在這個類別特征進行切分，也會把數據切分到很多零碎的小空間上，如下左圖所示。而決策樹學習時利用的是統(tǒng)計信息，在這些數據量小的空間上，統(tǒng)計信息不準確，學習會變差。但如果使用下右圖的分裂方式，數據會被切分到兩個比較大的空間，進一步的學習也會更好。

圈中的數值表示該結點內的數據。右圖中葉子節(jié)點 X=A || X=C 的含義是 X=A 或者 X=C 放到左孩子，其余放到右孩子。

2）LightGBM類別型特征處理方式

LightGBM采用了Many vs Many的切分方式解決one-hot編碼帶來的問題，實現了類別特征的最優(yōu)切分。用LightGBM可以直接輸入類別特征，并產生上右圖的效果。
在1個k維的類別特征中尋找最優(yōu)切分，樸素的枚舉算法的復雜度是 O ( 2 k ) O(2^k) O(2k)，而LightGBM采用了如 On Grouping For Maximum Homogeneity的方法實現了 O ( k log ? k ) O(k\log k) O(klogk) 的算法。

算法流程如圖所示：

①在枚舉分割點之前，先把直方圖按每個類別的均值進行排序。
②接著按照均值的結果依次枚舉最優(yōu)分割點。

從下圖可以看到，Sum(y)/Count(y)為類別的均值。當然，這個方法很容易過擬合，所以在LightGBM中加入了很多對這個方法的約束和正則化。

求解類別型特征的最優(yōu)切分的具體流程如下：

① 離散特征建立直方圖的過程

統(tǒng)計該特征下每一種離散值出現的次數，并從高到低排序，并過濾掉出現次數較少的特征值。然后為每一個特征值，建立一個bin容器，對于在bin容器內出現次數較少的特征值直接過濾掉，不建立bin容器。

② 計算分裂閾值的過程

先看該特征下劃分出的bin容器的個數，如果bin容器的數量小于4，直接使用one vs other方式，逐個掃描每一個bin容器，找出最佳分裂點。
對于bin容器較多的情況，先進行過濾，只讓子集合較大的bin容器參加劃分閾值計算，對每一個符合條件的bin容器進行公式計算，得到一個值，根據該值對bin容器從小到大進行排序，然后分從左到右、從右到左進行搜索，得到最優(yōu)分裂閾值。公式如下：

該 b i n 容器下所有樣本的一階梯度之和該 b i n 容器下所有樣本的二階梯度之和 + 正則項（參數 c a t - s m o o t h ） \frac{該bin容器下所有樣本的一階梯度之和}{該bin容器下所有樣本的二階梯度之和} + 正則項（參數 {cat \text{-} smooth}）該bin容器下所有樣本的二階梯度之和該bin容器下所有樣本的一階梯度之和+正則項（參數cat-smooth）

這里為什么不是label的均值呢？其實上例中只是為了便于理解，只針對了學習一棵樹且是回歸問題的情況。這時候一階導數是Y，二階導數是1），

沒有搜索所有的bin容器，而是設定了一個搜索bin容器數量的上限值，程序中設定是32，即參數max_num_cat。
LightGBM中對離散特征實行的是many vs many 策略，這32個bin中最優(yōu)劃分的閾值的左邊或者右邊所有的bin容器就是一個many集合，而其他的bin容器就是另一個many集合。

③ 對于連續(xù)特征，劃分閾值只有一個。對于離散值可能會有多個劃分閾值，每一個劃分閾值對應著一個bin容器編號。

當使用離散特征進行分裂時，只要數據樣本對應的bin容器編號在這些閾值對應的bin集合之中，這條數據就加入分裂后的左子樹，否則加入分裂后的右子樹。