集成学习-Boosting集成学习算法LightGBM
?
在2017年年1月微軟在GitHub的上開源了一個新的升壓工具LightGBM（Light Gradient Boosting Machine ）。它是一種優秀的機器學習算法框架，與XGBoost算法相比，在不降低準確率的前提下，速度提升了10倍左右，占用內存下降了3倍左右。
目錄
性能對比
GBDT和XGBoost算法的缺點和不足
LightGBM優化
優化策略：直方圖算法（Histogram算法）
優化策略：GOSS（單邊梯度采樣算法）
優化策略：EFB（獨立特征合并）
優化策略：葉子生長（leaf-wise)的算法
優化策略：支持類別特征（即不需要做one-hot編碼）
優化策略：支持高效并行
XGBoost與LightGBM對比
其他
性能對比
下圖是LightGBM在GitHub主頁上展示的在五個不同數據集上得到的性能實驗數據，比起XGBoost算法，LightGBM算法在準確度一樣，但在速度和內存的消耗上有更明顯的優勢。
耗時比較：
準確率比較：
內存消耗：
GBDT和XGBoost算法的缺點和不足
梯度提升決策樹算法的實現原理，它是基于決策樹的提升算法，采用前向分布算法，在每次迭代中，通過負梯度擬合殘差，從而學習到一顆決策樹。在生成決策樹的過程中，進行特征選擇節點分裂時，需要對特征值進行排序，遍歷所有可能的劃分點，然后計算信息增益，從而選擇出最優的分裂點。每輪迭代都會對整個訓練集進行遍歷，這樣既耗費內存，也非常的耗時。
在這部分比較常用的優化算法有預排序，就是對所有特征值優先排序，計算每個劃分點的增益值，并且保存在內存中。在迭代的過程中通過查表的方式進行選擇最優分裂點。XGBoost算法已經提供了這種方式的優化，然而它在面對海量數據和特征維度很高的數據集時，算法的效率和擴展性很難讓人滿意。
如果要對GBDT進行優化，有兩個方面：
- ?降低訓練集的規模，這樣可以減少計算量，提高算法的計算效率。
- ?降低特征維度，這樣的話，可以在選擇分裂點的時候減少計算量，提高算法的性能。但是直接減少訓練集規模或者降低特征維度，很明顯會犧牲模型的精確度。
然而，LightGBM算法正是通過對模型訓練時樣本點的采樣優化和選擇分裂點時的特征維度的優化，在不犧牲精度的條件下，提高了訓練速度。LightGBM算法是一種改進則是直方圖算法，他把連續特征值劃分到k個桶中去（連續值分箱），劃分點則在這k個點中選取。k<<d，所以在內存消耗和訓練速度都更佳。并且在實際的數據集上表明，離散化的分裂點對最終的精度影響并不大，甚至會好一些。原因在于決策樹本身就是一個弱學習器，采用Histogram算法會起到正則化的效果，有效地防止模型的過擬合。LightGBM也是基于直方圖的。
?
LightGBM優化
優化策略：直方圖算法（Histogram算法）
LightGBM采用了基于直方圖的算法將連續的特征值離散化成了K個整數，構造寬度為K的直方圖，遍歷訓練數據，統計每個離散值在直方圖中的累積統計量。在選取特征的分裂點的時候，只需要遍歷排序直方圖的離散值。使用直方圖算法降低了算法的計算代價，XGBoost采用的預排序需要遍歷每一個特征值，計算分裂增益，而直方圖算法只需要計算K次，提高了尋找分裂點的效率；降低了算法的內存消耗，不需要存儲預排序結果，只需要保存特征離散化后的值。
但是特征值被離散化后，找到的并不是精確的分割點，會不會對學習的精度上造成影響呢？在實際的數據集上表明，離散化的分裂點對最終學習的精度影響并不大，甚至會更好一些。因為這里的決策樹本身就是弱學習器，采用直方圖離散化特征值反而會起到正則化的效果，提高算法的泛化能力。
XGBoost預排序算法每遍歷一個特征值就需要計算一次分裂的增益，而直方圖算法只需要計算k次（k可以認為是常數），時間復雜度從O(#data * #feature) 優化到O(k* #features)。
LightGBM的直方圖做差加速
一個容易觀察到的現象：一個葉子的直方圖可以由它的父親節點的直方圖與它兄弟的直方圖做差得到。通常構造直方圖，需要遍歷該葉子上的所有數據，但直方圖做差僅需遍歷直方圖的k個桶。利用這個方法，LightGBM可以在構造一個葉子的直方圖后（父節點在上一輪就已經計算出來了），可以用非常微小的代價得到它兄弟葉子的直方圖，在速度上可以提升一倍。
優化策略：GOSS（單邊梯度采樣算法）
單邊梯度采樣算法（Grandient-based One-Side Sampling，GOSS），大致的意思是根據樣本某一特征上的單梯度作為樣本的權值進行訓練。
LightGBM使用GOSS算法進行訓練樣本采樣的優化。在AdaBoost算法中，采用了增加被錯誤分類的樣本的權重來優化下一次迭代時對哪些樣本進行重點訓練。然而GBDT算法中沒有樣本的權重，但是LightGBM采用了基于每個樣本的梯度進行訓練樣本的優化，具有較大梯度的數據對計算信息增益的貢獻比較大。當一個樣本點的梯度很小，說明該樣本的訓練誤差很小，即該樣本已經被充分訓練。然而在計算過程中，僅僅保留梯度較大的樣本（例如：預設置一個閾值，或者保留最高若干百分位的梯度樣本），拋棄梯度較小樣本，會改變樣本的分布并且降低學習的精度。GOSS算法的提出很好的解決了這個問題。
GOSS算法的基本思想是首先對訓練集數據根據梯度排序，預設一個比例，保留在所有樣本中梯度高于的數據樣本；梯度低于該比例的數據樣本不會直接丟棄，而是設置一個采樣比例，從梯度較小的樣本中按比例抽取樣本。為了彌補對樣本分布造成的影響，GOSS算法在計算信息增益時，會對較小梯度的數據集乘以一個系數，用來放大。這樣，在計算信息增益時，算法可以更加關注“未被充分訓練”的樣本數據。
其采樣的方式有點巧妙：
總的來說就是a% * #samples + b% * (1 - a%) * #samples個樣本作為訓練樣本。 而這樣的構造是為了盡可能保持與總的數據分布一致，并且保證小梯度值的樣本得到訓練。
此時，已經得到了通過GOSS算法篩選出來的樣本和這些樣本對應的梯度(殘差)。此時的樣本數量比沒有GOSS處理之前少了很多。并且該方法是根據樣本誤差當權重做采樣的，這樣做出來的準確率優于隨機采樣。，精度更高。
優化策略：EFB（獨立特征合并）
EFB（Exclusive Feature Bundling）中文名叫獨立特征合并，顧名思義它就是將若干個特征合并在一起。使用這個算法的原因是因為我們要解決數據稀疏的問題。在很多時候，數據通常都是幾千萬維的稀疏數據。因此我們對不同維度的數據合并一齊使得一個稀疏矩陣變成一個稠密矩陣。這里就有兩個問題：1. 如何確定哪些特征用于融合且效果為較好。2. 如何將這些特征合并到一齊。
高維數據一般是稀疏的，可以設計一種損失最小的特征減少方法。并且，在稀疏特征空間中，許多特征都是互斥的，也就是它們幾乎不同時取非0值。因此，我們可以安全的把這些互斥特征綁到一起形成一個特征，然后基于這些特征束構建直方圖，這樣又可以加速了。
有兩個問題待解決，如何判斷哪些特征該綁到一起，如何構建綁定。這是NP難的。
首先，轉換到圖著色問題。G=(V, E)，把關聯矩陣G的每一行看成特征，從而得到|V|個特征，互斥束就圖中顏色相同的頂點。圖中點就是特征，邊代表兩個特征不互斥，也就是特征之間的沖突。如果算法允許小的沖突，可以得到更小的特征束數量，計算效率會更高。證明發現隨機污染一小部分特征值，最多影響訓練精度 ，是所有束中沖突最大的。通過選取合適的，我們可以很好的在效率和精度之間尋找平衡。
最后，排序就按照束的度來進行。當然，更一步優化是不夠造圖，直接根據非零值的數量排序，這個根據度排序很像，因為更多非0值意味著更高概率的沖突。更改了排序策略，可以避免重復。
第二個問題，合并特征，從而降低訓練復雜度，關鍵是我們可以確保原先特征值可以從特征束中識別出來。因為直方圖存儲的是特征的離散桶，而不是連續值，我們可以通過把互斥特征放到不同桶，從而構造一個特征束。這可以通過添加偏移實現。如，假設我們有2個特征在一個特征束中，原先特征A的范圍為[0,10)，特征B的范圍為[0,20)，我們給特征B加上一個偏移10，它就變成[10,30)，這樣我們就可以執行安全的合并了，用特征束[0,30)代替特征A和B。具體算法如下。
EFB算法可以把很多特征綁到一起，形成更少的稠密特征束，這樣可以避免對0特征值的無用的計算。加速計算直方圖還可以用一個表記錄數據的非0值。
擬合該輪殘差樹前，用EFB算法減少特征量
為什么要用EFB？
在處理高維特征數據的時候，容易出現數據稀疏問題，存在有些特征之間是互斥的，這樣造成了沒有必要的計算開銷。EFB方法能夠把互斥的特征綁定成一個特征，又不影響數據質量，減少不必要的計算開銷。
EFB的實現原理和過程是什么？
關注兩個問題：
（1）如何發現互斥特征對；
（2）如何把互斥特征對捆綁。
解決這兩個問題，EFB方法的原理也就明白。
（1）如何發現互斥特征對
遍歷每一條樣本，當兩個特征沒有同時為非零取值的情況，這樣的兩個特征為互斥特征；當然，也可以給一個沖突閾值，兩個特征同時為非零的個數占總的樣本的比例，如果這個比例小于閾值，則也考慮為互斥特征。
例如，以下表格中特征1和特征2就是互斥特征。
發現了互斥特征后，下一步就是對互斥特征對進行”捆綁”。
（2）如何把互斥特征對捆綁
特征1的取值在[0,3]，讓特征2的每個取值都加一個偏置3.1，這樣就把特征1和特征2分開了，這兩個特征放入同一個直方圖中就不會有交叉的地方了。把這兩個特放入同一個直方圖中做統計，這個直方圖的取值在[0,3.2+3.1]–>[0,6.3]。(實質就是減少了一個直方圖，減少了計算內存開銷)
優化策略：葉子生長（leaf-wise)的算法
大多數的決策樹學習算法的樹生成方式都是采用按層生長（level-wise)的策略。如下圖所示：
Level-wise過一次數據可以同時分裂同一層的葉子，容易進行多線程優化，也好控制模型復雜度，不容易過擬合。但實際上Level-wise是一種低效的算法，因為它不加區分的對待同一層的葉子，帶來了很多沒必要的開銷，因為實際上很多葉子的分裂增益較低，沒必要進行搜索和分裂。
不同的是，LightGBM采用了一種更為高效的按葉子生長（leaf-wise）的策略。該策略每次從當前決策樹所有的葉子節點中，找到分裂增益最大的一個葉子節點，然后分裂，如此循環往復。這樣的機制，減少了對增益較低的葉子節點的分裂計算，減少了很多沒必要的開銷。與leve-wise的策略相比，在分裂次數相同的情況下，leaf-wise可以降低誤差，得到更好的精度。Leaf-wise算法的缺點是可能會生成較深的決策樹。因此，LightGBM在Leaf-wise上增加了限制最大深度的參數，在保證算法高效的同時，防止過擬合。
優化策略：支持類別特征（即不需要做one-hot編碼）
實際上大多數機器學習工具都無法直接支持類別特征，一般需要把類別特征，轉化到多維的one-hot編碼特征，降低了空間和時間的效率。而類別特征的使用是在實踐中很常用的。基于這個考慮，LightGBM優化了對類別特征的支持，可以直接輸入類別特征，不需要額外的one-hot編碼展開。并在決策樹算法上增加了類別特征的決策規則。在Expo數據集上的實驗，相比0/1展開的方法，訓練速度可以加速8倍，并且精度一致。
優化策略：支持高效并行
LightGBM還具有支持高效并行的優點。LightGBM原生支持并行學習，目前支持特征并行和數據并行的兩種。
- 特征并行的主要思想是在不同機器在不同的特征集合上分別尋找最優的分割點，然后在機器間同步最優的分割點（和XGboost一樣）。
- 數據并行則是讓不同的機器先在本地構造直方圖，然后進行全局的合并，最后再合并的直方圖上面尋找最優分割點。
LightGBM針對這兩種并行方法都做了優化，在特征并行算法中，通過在本地保存全部數據避免對數據切分結果的通信；在數據并行中使用分散規約 (Reduce scatter) 把直方圖合并的任務分攤到不同的機器，降低通信和計算，并利用直方圖做差，進一步減少了一半的通信量。
LightGBM 的單機版本還有很多其他細節上的優化，比如 cache 訪問優化，多線程優化，稀疏特征優化等等，更多的細節可以查閱 https://github.com/Microsoft/LightGBM/wiki)上的文檔說明。優化匯總對比表:?
全部的優化步驟為：
（1）在擬合殘差樹之前，引入GOSS算法剔除權重較小的樣本，減少數據量；
（2）在擬合殘差樹之前，在引入EFB算法，在高維(高維一般也稀疏)的數據情況捆綁互斥(或接近互斥)的特征(捆綁的方法是采用直方圖的方法)，達到減少特征量；
（3）在擬合殘差樹之前，對離散值(如輸入是”A”, “B”,”C”等取值的特征輸入)的處理，讓輸入的這些離散值直接被模型支持(這一點也是和xgboost的區別，xgboost不能直接支持類似”A”,”B”,”C”的特征輸入)；
（4）擬合殘差樹的過程中，采樣leaf-wise方法，減少節點的分裂個數，進而減少計算量(主要體現在與xgboost的level-wise的區別)；
（5）擬合殘差樹的過程中，采用直方圖方法(以及直方圖做差加速)提高求最優分割點的速度(主要體現在與xgboost的預排序的區別)。
XGBoost與LightGBM對比
其他
直方圖方法有什么優點？
通過以上講解，
<1> 最后求增益做分裂的過程，僅需存儲每個特征的直方圖，計算內存消耗很小；
<2> 采用直方圖方法求增益，因為離散化取值，與預排序算法相比對于每個特征遍歷求增益的次數減少了很多，這樣就加快了優分割點的求解速度；
<2> 因為是以某一取值范圍為取值，而不是具體的原始數據，實際上可能決策樹對于分割點的精確程度并不太敏感，而且較“粗”的分割點也自帶正則化的效果。
Lightgbm如何節省時間和空間？
節省時間：
<1> GOSS減少樣本數量，在做每個特征直方圖(統計樣本個數、梯度之和)的時候因為樣本數量變少了，可以減少計算量;
<2> EFB減少特征量，特征數量減少了，直方圖的個數也就減少了，即省時間也省計算內存。
節省空間：
<1> 直方圖算法，僅需存儲每個特征的直方圖，計算內存消耗很小；
<2> EFB減少特征量，特征數量減少了，直方圖的個數也就減少了，即省時間也省計算內存.
Leaf-wise生長方式有什么優缺點？
優點：
1 更高效。因為以前計算過的葉子節點的最大增益是不變的，無需重復計算。
2 與level-wise相比，在分裂次數相同的情況，因為每次分裂都是求所有葉子節點中增益最大的那個最為最優分割點，leaf-wise能達到更好的精度。
缺點：
容易過擬合，因此增加了一個最大樹深的限制條件。
Xgboost中的預排序算法？
對于遍歷到某一個特征，把樣本按該特征的取值排序。這樣在遍歷分割點的時候就能夠很快地將樣本分成兩批。
?
?
?
《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀總結
以上是生活随笔為你收集整理的集成学习-Boosting集成学习算法LightGBM的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 集成学习-Boosting集成学习算法X
- 下一篇： 逻辑回归模型详解(Logistic Re