LightGBM

（Light Gradient Boosting Machine）是一款基于決策樹算法的分布式梯度提升框架。為了滿足工業界縮短模型計算時間的需求，LightGBM的設計思路主要是兩點：
減小數據對內存的使用，保證單個機器在不犧牲速度的情況下，盡可能地用上更多的數據；
減小通信的代價，提升多機并行時的效率，實現在計算上的線性加速。
由此可見，LightGBM的設計初衷就是提供一個快速高效、低內存占用、高準確度、支持并行和大規模數據處理的數據科學工具。
LightGBM是微軟旗下的Distributed Machine Learning Toolkit （DMKT）的一個項目，由2014年首屆阿里巴巴大數據競賽獲勝者之一柯國霖主持開發。雖然其開源時間才僅僅2個月，但是其快速高效的特點已經在數據科學競賽中嶄露頭角。Allstate Claims Severity競賽中的冠軍解決方案里就使用了LightGBM，并對其大嘉贊賞。

特性

優化速度與內存使用。
稀疏優化。
優化準確率。使用leaf-wise生長方式，可以處理分類變量。
優化網絡通訊。
支持三種模式并行。
（1）特征并行：
a. Workers find local best split point {feature, threshold} on the local feature set.
b. Communicate local best splits with each other and get the best one.
c. Perform the best split.
（2）數據并行：
a. Instead of “Merge global histograms from all local histograms”, LightGBM use “Reduce Scatter” to merge histograms of different (non-overlapping) features for different workers. Then workers find the local best split on local merged histograms and sync up the global best split.
b. As aforementioned, LightGBM uses histogram subtraction to speed up training. Based on this, we can communicate histograms only for one leaf, and get its neighbor’s histograms by subtraction as well.
（3）投票并行：
Voting parallel further reduces the communication cost in data-parallel to constant cost. It uses two-stage voting to reduce the communication cost of feature histograms.

常見問題

LightGBM和XGBoost有什么區別？他們的loss一樣么？ 算法層面有什么區別？
答：LightGBM：基于Histogram的決策樹算法；Leaf-wise的葉子生長策略；Cache命中率優化；直接支持類別特征（categorical Feature）；XGBoost：預排序；Level-wise的層級生長策略；特征對梯度的訪問是一種隨機訪問。

LightGBM有哪些實現，各有什么區別？
答：gbdt:梯度提升決策樹，串行速度慢，容易過擬合；rf：隨機森林，并行速度快；dart：訓練較慢；goss：容易過擬合。

LigthGBM是boosting集合模型中的新進成員，由微軟提供，它和XGBoost一樣是對GBDT的高效實現，原理上它和GBDT及XGBoost類似，都采用損失函數的負梯度作為當前決策樹的殘差近似值，去擬合新的決策樹。

LightGBM樹的生長方式是垂直方向的，其他的算法都是水平方向的，也就是說Light GBM生長的是樹的葉子，其他的算法生長的是樹的層次。
LightGBM選擇具有最大誤差的樹葉進行生長，當生長同樣的樹葉，生長葉子的算法可以比基于層的算法減少更多的loss。

不建議在小數據集上使用LightGBM。LightGBM對過擬合很敏感，對于小數據集非常容易過擬合。對于多小屬于小數據集，并沒有什么閾值，但是從我的經驗，我建議對于10000+以上的數據的時候，再使用LightGBM。

LightGBM在很多方面會比XGBoost表現的更為優秀。它有以下優勢：
更快的訓練效率
低內存使用
更高的準確率
支持并行化學習
可處理大規模數據
支持直接使用category特征
從下圖實驗數據可以看出， LightGBM比XGBoost快將近10倍，內存占用率大約為XGBoost的1/6，并且準確率也有提升。
至于LGB為什么比XGB的精度高這一點，我的理解是選擇梯度大(殘差大)樣本來進行特征分裂生成的樹，借鑒了Adaboost的更改樣本權重的思想。每棵樹針對某些特定訓練樣本有著較好的劃分能力，導致每棵樹之間的異質性較大，對于效果近似但異質性大的模型加權往往會帶來更大的提升。

通俗解釋：LGB的優化方法是，在保留大梯度樣本的同時，隨機地保留一些小梯度樣本，同時放大了小梯度樣本帶來的信息增益。

這樣說起來比較抽象，我們過一遍流程： 首先把樣本按照梯度排序，選出梯度最大的a%個樣本，然后在剩下小梯度數據中隨機選取b%個樣本，在計算信息增益的時候，將選出來b%個小梯度樣本的信息增益擴大 1 - a / b 倍。這樣就會避免對于數據分布的改變。

這給我的感覺就是一個公寓里本來住了十個人，感覺太擠了，趕走了六個人，但剩下的四個人要分攤他們六個人的房租。
舉個例子，對于一列特征[1,nan,1,nan,1]和一列特征[nan,1,nan,1,nan]，他們正好可以合并成一列特征[1,2,1,2,1]。LGB的目標就是在于找到這樣的特征并且將他們合并在一起。

如果把特征抽象成圖中的點，特征之間的沖突看作是圖中的邊，那么問題就轉換為找出圖中的社團并使圖中的社團數量最少。LGB里提出了一個貪心的策略，按照有權度來為圖中所有的點排序，然后把特征合并到度小于某個閾值的社團中或單獨創建一個社團。

對于特征如何合并，一個重要的原則就是使合并的兩個特征可以被順利區分出來，LGB采取了一個更改閾值的方法。例如對于特征x∈(0, 10)， 特征y∈(0, 20)，就可以把特征y轉換為y∈(10,30)，然后再去合并x與y。
看完這些驚人的實驗結果以后，對下面兩個問題產生了疑惑：XGBoost已經十分完美了，為什么還要追求速度更快、內存使用更小的模型？對GBDT算法進行改進和提升的技術細節是什么？

提出LightGBM的動機

常用的機器學習算法，例如神經網絡等算法，都可以以mini-batch的方式訓練，訓練數據的大小不會受到內存限制。而GBDT在每一次迭代的時候，都需要遍歷整個訓練數據多次。如果把整個訓練數據裝進內存則會限制訓練數據的大小；如果不裝進內存，反復地讀寫訓練數據又會消耗非常大的時間。尤其面對工業級海量的數據，普通的GBDT算法是不能滿足其需求的。

LightGBM提出的主要原因就是為了解決GBDT在海量數據遇到的問題，讓GBDT可以更好更快地用于工業實踐。

XGBoost的優缺點

精確貪心算法

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

優點：

可以找到精確的劃分條件
缺點：

計算量巨大
內存占用巨大
易產生過擬合
Level-wise迭代方式

預排序方法（pre-sorted）：首先，空間消耗大。這樣的算法需要保存數據的特征值，還保存了特征排序的結果（例如排序后的索引，為了后續快速的計算分割點，在這里XGBoost采用了特征粒度的并行化），這里需要消耗訓練數據兩倍的內存。其次時間上也有較大的開銷，在遍歷每一個分割點的時候，都需要進行分裂增益的計算，消耗的代價大。

優點：

可以使用多線程
可以加速精確貪心算法
缺點：

效率低下，可能產生不必要的葉結點
對cache優化不友好
在預排序后，特征對梯度的訪問是一種隨機訪問，并且不同的特征訪問的順序不一樣，無法對cache進行優化。同時，在每一層長樹的時候，需要隨機訪問一個行索引到葉子索引的數組，并且不同特征訪問的順序也不一樣，也會造成較大的cache miss。

LightGBM在哪些地方進行了優化？

概括來說，lightGBM主要有以下特點：
基于Histogram的決策樹算法
帶深度限制的Leaf-wise的葉子生長策略
直方圖做差加速
直接支持類別特征(Categorical Feature)
Cache命中率優化
基于直方圖的稀疏特征優化
多線程優化

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

首先，對所有特征按數值進行預排序。
其次，在每次的樣本分割時，用O(# data)的代價找到每個特征的最優分割點。
最后，找到最后的特征以及分割點，將數據分裂成左右兩個子節點。
這種pre-sorting算法能夠準確找到分裂點，但是在空間和時間上有很大的開銷。

由于需要對特征進行預排序并且需要保存排序后的索引值（為了后續快速的計算分裂點），因此內存需要訓練數據的兩倍。
在遍歷每一個分割點的時候，都需要進行分裂增益的計算，消耗的代價大。
LightGBM使用的是histogram算法，占用的內存更低，數據分隔的復雜度更低。其思想是將連續的浮點特征離散成k個離散值，并構造寬度為k的Histogram。然后遍歷訓練數據，統計每個離散值在直方圖中的累計統計量。在進行特征選擇時，只需要根據直方圖的離散值，遍歷尋找最優的分割點。

使用直方圖算法有很多優點。首先最明顯就是內存消耗的降低，直方圖算法不僅不需要額外存儲預排序的結果，而且可以只保存特征離散化后的值，而這個值一般用8位整型存儲就足夠了，內存消耗可以降低為原來的1/8。

Histogram algorithm

Histogram algorithm應該翻譯為直方圖算法，直方圖算法的思想也很簡單，首先將連續的浮點數據轉換為bin數據，具體過程是首先確定對于每一個特征需要多少的桶bin，然后均分，將屬于該桶的樣本數據更新為bin的值，最后用直方圖表示。（看起來很高大上，其實就是直方圖統計，最后我們將大規模的數據放在了直方圖中）

直方圖算法有幾個需要注意的地方：

使用bin替代原始數據相當于增加了正則化；
使用bin意味著很多數據的細節特征被放棄了，相似的數據可能被劃分到相同的桶中，這樣的數據之間的差異就消失了；
bin數量選擇決定了正則化的程度，bin越少懲罰越嚴重，欠擬合風險越高。
直方圖算法需要注意的地方：

構建直方圖時不需要對數據進行排序（比XGBoost快），因為預先設定了bin的范圍；
直方圖除了保存劃分閾值和當前bin內樣本數以外還保存了當前bin內所有樣本的一階梯度和（一階梯度和的平方的均值等價于均方損失）；
閾值的選取是按照直方圖從小到大遍歷，使用了上面的一階梯度和，目的是得到劃分之后△loss最大的特征及閾值。

Histogram 算法的優缺點：

Histogram算法并不是完美的。由于特征被離散化后，找到的并不是很精確的分割點，所以會對結果產生影響。但在實際的數據集上表明，離散化的分裂點對最終的精度影響并不大，甚至會好一些。原因在于decision tree本身就是一個弱學習器，采用Histogram算法會起到正則化的效果，有效地防止模型的過擬合。
時間上的開銷由原來的O(#data * #features)降到O(k * #features)。由于離散化，#bin遠小于#data，因此時間上有很大的提升。
Histogram算法還可以進一步加速。一個葉子節點的Histogram可以直接由父節點的Histogram和兄弟節點的Histogram做差得到。一般情況下，構造Histogram需要遍歷該葉子上的所有數據，通過該方法，只需要遍歷Histogram的k個捅。速度提升了一倍。

決策樹生長策略

在Histogram算法之上，LightGBM進行進一步的優化。首先它拋棄了大多數GBDT工具使用的按層生長 (level-wise)的決策樹生長策略，而使用了帶有深度限制的按葉子生長 (leaf-wise)算法。

XGBoost采用的是按層生長level（depth）-wise生長策略，能夠同時分裂同一層的葉子，從而進行多線程優化，不容易過擬合；但不加區分的對待同一層的葉子，帶來了很多沒必要的開銷。因為實際上很多葉子的分裂增益較低，沒必要進行搜索和分裂。

LightGBM采用leaf-wise生長策略，每次從當前所有葉子中找到分裂增益最大（一般也是數據量最大）的一個葉子，然后分裂，如此循環。因此同Level-wise相比，在分裂次數相同的情況下，Leaf-wise可以降低更多的誤差，得到更好的精度。Leaf-wise的缺點是可能會長出比較深的決策樹，產生過擬合。因此LightGBM在Leaf-wise之上增加了一個最大深度的限制，在保證高效率的同時防止過擬合。

直方圖差加速

LightGBM另一個優化是Histogram（直方圖）做差加速。一個容易觀察到的現象：一個葉子的直方圖可以由它的父親節點的直方圖與它兄弟的直方圖做差得到。通常構造直方圖，需要遍歷該葉子上的所有數據，但直方圖做差僅需遍歷直方圖的k個桶。利用這個方法，LightGBM可以在構造一個葉子的直方圖后，可以用非常微小的代價得到它兄弟葉子的直方圖，在速度上可以提升一倍。

直接支持類別特征

實際上大多數機器學習工具都無法直接支持類別特征，一般需要把類別特征，轉化one-hotting特征，降低了空間和時間的效率。而類別特征的使用是在實踐中很常用的。基于這個考慮，LightGBM優化了對類別特征的支持，可以直接輸入類別特征，不需要額外的0/1展開。并在決策樹算法上增加了類別特征的決策規則。

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

可能無法在這個類別特征上進行切分（即浪費了這個特征）。使用one-hot編碼的話，意味著在每一個決策節點上只能使用one vs rest（例如是不是狗，是不是貓等）的切分方式。當類別值很多時，每個類別上的數據可能會比較少，這時候切分會產生不平衡，這意味著切分增益也會很小（比較直觀的理解是，不平衡的切分和不切分沒有區別）。
會影響決策樹的學習。因為就算可以在這個類別特征進行切分，也會把數據切分到很多零碎的小空間上，如圖1左邊所示。而決策樹學習時利用的是統計信息，在這些數據量小的空間上，統計信息不準確，學習會變差。但如果使用下圖右邊的分裂方式，數據會被切分到兩個比較大的空間，進一步的學習也會更好。
下圖右邊葉子節點的含義是X=A或者X=C放到左孩子，其余放到右孩子。

LightGBM處理分類特征大致流程

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

算法流程下圖所示：在枚舉分割點之前，先把直方圖按每個類別的均值進行排序；然后按照均值的結果依次枚舉最優分割點。從下圖可以看到，Sum(y)/Count(y)為類別的均值。當然，這個方法很容易過擬合，所以在LGBM中加入了很多對這個方法的約束和正則化。
下圖是一個簡單的對比實驗，可以看到該最優方法在AUC上提升了1.5個點，并且時間只多了20%。
下面具體來講下在代碼中如何求解類別特征的最優切分的流程：

離散特征建立直方圖的過程：統計該特征下每一種離散值出現的次數，并從高到低排序，并過濾掉出現次數較少的特征值, 然后為每一個特征值，建立一個bin容器, 對于在bin容器內出現次數較少的特征值直接過濾掉，不建立bin容器。
計算分裂閾值的過程：
先看該特征下劃分出的bin容器的個數，如果bin容器的數量小于4，直接使用one vs other方式, 逐個掃描每一個bin容器，找出最佳分裂點;
對于bin容器較多的情況, 先進行過濾，只讓子集合較大的bin容器參加劃分閾值計算, 對每一個符合條件的bin容器進行公式計算:

公式如下: 該bin容器下所有樣本的一階梯度之和/該bin容器下所有樣本的二階梯度之和 + 正則項(參數cat_smooth)

這里為什么不是label的均值呢？其實上例中只是為了便于理解，只針對了學習一棵樹且是回歸問題的情況， 這時候一階導數是Y, 二階導數是1)，得到一個值，根據該值對bin容器從小到大進行排序，然后分從左到右、從右到左進行搜索，得到最優分裂閾值。但是有一點，沒有搜索所有的bin容器，而是設定了一個搜索bin容器數量的上限值，程序中設定是32，即參數max_num_cat。LightGBM中對離散特征實行的是many vs many 策略，這32個bin中最優劃分的閾值的左邊或者右邊所有的bin容器就是一個many集合，而其他的bin容器就是另一個many集合。
對于連續特征，劃分閾值只有一個，對于離散值可能會有多個劃分閾值，每一個劃分閾值對應著一個bin容器編號，當使用離散特征進行分裂時，只要數據樣本對應的bin容器編號在這些閾值對應的bin集合之中，這條數據就加入分裂后的左子樹，否則加入分裂后的右子樹。

直接支持高效并行

LightGBM原生支持并行學習，目前支持特征并行和數據并行的兩種。特征并行的主要思想是在不同機器在不同的特征集合上分別尋找最優的分割點，然后在機器間同步最優的分割點。數據并行則是讓不同的機器先在本地構造直方圖，然后進行全局的合并，最后在合并的直方圖上面尋找最優分割點。
LightGBM針對這兩種并行方法都做了優化，在特征并行算法中，通過在本地保存全部數據避免對數據切分結果的通信；在數據并行中使用分散規約(Reduce scatter)把直方圖合并的任務分攤到不同的機器，降低通信和計算，并利用直方圖做差，進一步減少了一半的通信量。
基于投票的數據并行則進一步優化數據并行中的通信代價，使通信代價變成常數級別。在數據量很大的時候，使用投票并行可以得到非常好的加速效果。

網絡通信優化

XGBoost由于采用pre-sorted算法，通信代價非常大，所以在并行的時候也是采用histogram算法；LightGBM采用的histogram算法通信代價小，通過使用集合通信算法，能夠實現并行計算的線性加速。

LightGBM原理

提升樹是利用加模型與前向分布算法實現學習的優化過程，它有一些高效實現，如XGBoost, pGBRT，GBDT(Gradient Boosting Decision Tree)等。其中GBDT采用負梯度作為劃分的指標（信息增益），XGBoost則利用到二階導數。他們共同的不足是，計算信息增益需要掃描所有樣本，從而找到最優劃分點。在面對大量數據或者特征維度很高時，它們的效率和擴展性很難使人滿意。解決這個問題的直接方法就是減少特征量和數據量而且不影響精確度，有部分工作根據數據權重采樣來加速booisting的過程，但由于GBDT沒有樣本權重不能應用。

結合使用 GOSS 和 EFB 的 GBDT 算法就是 LightGBM。微軟開源的LightGBM（基于GBDT的）則很好的解決這些問題，它主要包含兩個算法：

單邊梯度采樣，Gradient-based One-Side Sampling（GOSS）

GOSS（從減少樣本角度）：排除大部分小梯度的樣本，僅用剩下的樣本計算信息增益。GBDT雖然沒有數據權重，但每個數據實例有不同的梯度，根據計算信息增益的定義，梯度大的實例對信息增益有更大的影響，因此在下采樣時，我們應該盡量保留梯度大的樣本（預先設定閾值，或者最高百分位間），隨機去掉梯度小的樣本。我們證明此措施在相同的采樣率下比隨機采樣獲得更準確的結果，尤其是在信息增益范圍較大時。

GBDT使用決策樹，來學習獲得一個將輸入空間映射到梯度空間的函數。假設訓練集有n個實例x1,…,xn，特征維度為s。每次梯度迭時，模型數據變量的損失函數的負梯度方向表示為g1,…,gn，決策樹通過最優切分點（最大信息增益點）將數據分到各個節點。GBDT通過分割后的方差衡量信息增益。

GOSS是一種在減少數據量和保證精度上平衡的算法。GOSS是通過區分不同梯度的實例，保留較大梯度實例同時對較小梯度隨機采樣的方式減少計算量，從而達到提升效率的目的。

EFB是通過特征捆綁的方式減少特征維度（其實是降維技術）的方式，來提升計算效率。通常被捆綁的特征都是互斥的（一個特征值為零,一個特征值不為零），這樣兩個特征捆綁起來才不會丟失信息。如果兩個特征并不是完全互斥（部分情況下兩個特征都是非零值），可以用一個指標對特征不互斥程度進行衡量，稱之為沖突比率，當這個值較小時，我們可以選擇把不完全互斥的兩個特征捆綁，而不影響最后的精度。

AdaBoost中，樣本權重是數據實例重要性的指標。然而在GBDT中沒有原始樣本權重，不能應用權重采樣。幸運的事，我們觀察到GBDT中每個數據都有不同的梯度值，對采樣十分有用，即實例的梯度小，實例訓練誤差也就較小，已經被學習得很好了，直接想法就是丟掉這部分梯度小的數據。然而這樣做會改變數據的分布，將會影響訓練的模型的精確度，為了避免此問題，我們提出了GOSS。

GOSS保留所有的梯度較大的實例，在梯度小的實例上使用隨機采樣。為了抵消對數據分布的影響，計算信息增益的時候，GOSS對小梯度的數據引入常量乘數。GOSS首先根據數據的梯度絕對值排序，選取top a個實例。然后在剩余的數據中隨機采樣b個實例。接著計算信息增益時為采樣出的小梯度數據乘以(1-a)/b，這樣算法就會更關注訓練不足的實例，而不會過多改變原數據集的分布。

定義：O表示某個固定節點的訓練集，分割特征j的分割點d定義為：

其中，

在GOSS中，
首先根據數據的梯度將訓練降序排序。
保留top a個數據實例，作為數據子集A。
對于剩下的數據的實例，隨機采樣獲得大小為b的數據子集B。
最后我們通過以下方程估計信息增益:

此處GOSS通過較小的數據集估計信息增益V~j(d)將大大地減小計算量。更重要的，我們接下來理論表明GOSS不會丟失許多訓練精度，勝過隨機采樣，理論的證明在附加材料。

我們定義GOSS近似誤差為：
根據上述理論，我們得出以下結論：

GOSS流程

輸入：訓練數據，迭代步數d，大梯度數據的采樣率a，小梯度數據的采樣率b，損失函數和若學習器的類型（一般為決策樹）；

輸出：訓練好的強學習器；

（1）根據樣本點的梯度的絕對值對它們進行降序排序；

（2）對排序后的結果選取前a*100%的樣本生成一個大梯度樣本點的子集；

（3）對剩下的樣本集合（1-a）100%的樣本，隨機的選取b（1-a）*100%個樣本點，生成一個小梯度樣本點的集合；

（4）將大梯度樣本和采樣的小梯度樣本合并；

（5）將小梯度樣本乘上一個權重系數；

（6）使用上述的采樣的樣本，學習一個新的弱學習器；

（7）不斷地重復（1）~（6）步驟直到達到規定的迭代次數或者收斂為止。

通過上面的算法可以在不改變數據分布的前提下不損失學習器精度的同時大大的減少模型學習的速率。

從上面的描述可知，當a=0時，GOSS算法退化為隨機采樣算法；當a=1時，GOSS算法變為采取整個樣本的算法。在許多情況下，GOSS算法訓練出的模型精確度要高于隨機采樣算法。另一方面，采樣也將會增加若學習器的多樣性，從而潛在的提升了訓練出的模型泛化能力。

互斥特征綁定，Exclusive Feature Bundling（EFB）

EFB（從減少特征角度）：捆綁互斥特征，也就是他們很少同時取非零值（也就是用一個合成特征代替）。通常真是應用中，雖然特征量比較多，但是由于特征空間十分稀疏，是否可以設計一種無損的方法來減少有效特征呢？特別在稀疏特征空間上，許多特征幾乎是互斥的（例如許多特征不會同時為非零值，像one-hot），我們可以捆綁互斥的特征。最后，我們將捆綁問題歸約到圖著色問題，通過貪心算法求得近似解。
結合使用 GOSS 和 EFB 的 GBDT 算法就是 LightGBM。

EBF的算法步驟如下：

將特征按照非零值的個數進行排序
計算不同特征之間的沖突比率
遍歷每個特征并嘗試合并特征，使沖突比率最小化
高位的數據通常是稀疏的，這種稀疏性啟發我們設計一種無損地方法來減少特征的維度。特別的，稀疏特征空間中，許多特征是互斥的，例如他們從不同時為非零值。我們可以綁定互斥的特征為單一特征，通過仔細設計特征臊面算法，我們從特征捆綁中構建了與單個特征相同的特征直方圖。這種方式的間直方圖時間復雜度從O(#data * #feature)降到O(#data * #bundle)，由于#bundle << # feature，我們能夠極大地加速GBDT的訓練過程而且損失精度。

有兩個問題：

怎么判定那些特征應該綁在一起（build bundled）？
怎么把特征綁為一個（merge feature）？
bundle（什么樣的特征被綁定）？

**理論1：**將特征分割為較小量的互斥特征群是NP難的。

證明：將圖著色問題歸約為此問題，而圖著色是NP難的，所以此問題就是NP難的。

給定圖著色實例G=(V, E)。以G的關聯矩陣的每一行為特征，得到我們問題的一個實例有|V|個特征。 很容易看到，在我們的問題中，一個獨特的特征包與一組具有相同顏色的頂點相對應，反之亦然。

理論1說明多項式時間中求解這個NP難問題不可行。為了尋找好的近似算法，我們將最優捆綁問題歸結為圖著色問題，如果兩個特征之間不是相互排斥，那么我們用一個邊將他們連接，然后用合理的貪婪算法（具有恒定的近似比）用于圖著色來做特征捆綁。 此外，我們注意到通常有很多特征，盡管不是100％相互排斥的，也很少同時取非零值。 如果我們的算法可以允許一小部分的沖突，我們可以得到更少的特征包，進一步提高計算效率。經過簡單的計算，隨機污染小部分特征值將影響精度最多O([(1–γ)n]?2/3)，γ是每個綁定中的最大沖突比率，當其相對較小時，能夠完成精度和效率之間的平衡。

基于上面的討論，我們設計了算法3，偽代碼見下圖，具體算法：

建立一個圖，每個點代表特征，每個邊有權重，其權重和特征之間總體沖突相關。
按照降序排列圖中的度數來排序特征。
檢查排序之后的每個特征，對他進行特征綁定或者建立新的綁定使得操作之后的總體沖突最小。
算法3的時間復雜度是O(feature2)，訓練之前只處理一次，其時間復雜度在特征不是特別多的情況下是可以接受的，但難以應對百萬維的特征。為了繼續提高效率，我們提出了一個更加高效的無圖的排序策略：將特征按照非零值個數排序，這和使用圖節點的度排序相似，因為更多的非零值通常會導致沖突，新算法在算法3基礎上改變了排序策略。

merging features(特征合并)

如何合并同一個bundle的特征來降低訓練時間復雜度。關鍵在于原始特征值可以從bundle中區分出來。鑒于直方圖算法存儲離散值而不是連續特征值，我們通過將互斥特征放在不同的箱中來構建bundle。這可以通過將偏移量添加到特征原始值中實現，例如，假設bundle中有兩個特征，原始特征A取值[0, 10]，B取值[0, 20]。我們添加偏移量10到B中，因此B取值[10, 30]。通過這種做法，就可以安全地將A、B特征合并，使用一個取值[0, 30]的特征取代AB。算法見算法4，

EFB算法能夠將許多互斥的特征變為低維稠密的特征，就能夠有效的避免不必要0值特征的計算。實際，通過用表記錄數據中的非零值，來忽略零值特征，達到優化基礎的直方圖算法。通過掃描表中的數據，建直方圖的時間復雜度將從O(#data)降到O(#non_zero_data)。當然，這種方法在構建樹過程中需要而額外的內存和計算開銷來維持預特征表。我們在lightGBM中將此優化作為基本函數，因為當bundles是稀疏的時候，這個優化與EFB不沖突（可以用于EFB）。
參考鏈接：https://blog.csdn.net/shine19930820/article/details/79123216

針對 Leaf-wise（Best-first）樹的參數優化

（1）num_leaves這是控制樹模型復雜度的主要參數。理論上, 借鑒 depth-wise 樹, 我們可以設置 num_leaves= 但是, 這種簡單的轉化在實際應用中表現不佳. 這是因為, 當葉子數目相同時, leaf-wise 樹要比 depth-wise 樹深得多, 這就有可能導致過擬合. 因此, 當我們試著調整 num_leaves 的取值時, 應該讓其小于 . 舉個例子, 當 max_depth=7時，depth-wise 樹可以達到較高的準確率.但是如果設置 num_leaves 為 128 時, 有可能會導致過擬合, 而將其設置為 70 或 80 時可能會得到比 depth-wise 樹更高的準確率. 其實, depth 的概念在 leaf-wise 樹中并沒有多大作用, 因為并不存在一個從 leaves 到 depth 的合理映射。

（2）min_data_in_leaf. 這是處理 leaf-wise 樹的過擬合問題中一個非常重要的參數. 它的值取決于訓練數據的樣本個樹和 num_leaves. 將其設置的較大可以避免生成一個過深的樹, 但有可能導致欠擬合. 實際應用中, 對于大數據集, 設置其為幾百或幾千就足夠了。

（3）max_depth（默認不限制，一般設置該值為5—10即可） 你也可以利用 max_depth 來顯式地限制樹的深度。

5.2 針對更快的訓練速度

（1）通過設置 bagging_fraction 和 bagging_freq 參數來使用 bagging 方法；（2）通過設置 feature_fraction 參數來使用特征的子抽樣；（3）使用較小的 max_bin；（4）使用 save_binary 在以后的學習過程對數據進行加速加載。

5.3 針對更好的準確率

（1）使用較大的 max_bin （學習速度可能變慢）；（2）使用較小的 learning_rate 和較大的 num_iterations；（3）使用較大的 num_leaves （可能導致過擬合）；（4）使用更大的訓練數據；（5）嘗試 dart（一種在多元Additive回歸樹種使用dropouts的算法）.

5.4 處理過擬合

（1）使用較小的 max_bin（默認為255）（2）使用較小的 num_leaves（默認為31）（3）使用 min_data_in_leaf（默認為20） 和 min_sum_hessian_in_leaf（默認為）（4）通過設置 bagging_fraction （默認為1.0）和 bagging_freq （默認為0，意味著禁用bagging，k表示每k次迭代執行一個bagging）來使用 bagging（5）通過設置 feature_fraction（默認為1.0） 來使用特征子抽樣（6）使用更大的訓練數據（7）使用 lambda_l1（默認為0）, lambda_l2 （默認為0）和 min_split_gain（默認為0，表示執行切分的最小增益） 來使用正則（8）嘗試 max_depth 來避免生成過深的樹

具體想要了解更多內容請參考：
https://blog.csdn.net/qq_24519677/article/details/82811215

附上python3代碼

#數據預處理 import numpy as np import matplotlib.pyplot as plt import pandas as pd # Importing the dataset dataset = pd.read_csv('...input\\Social_Network_Ads.csv') X = dataset.iloc[:, [2, 3]].values y = dataset.iloc[:, 4].values # Splitting the dataset into the Training set and Test set from sklearn.cross_validation import train_test_split x_train, x_test, y_train, y_test = train_test_split(X, y, test_size = 0.25, random_state = 0) # Feature Scaling from sklearn.preprocessing import StandardScaler sc = StandardScaler() x_train = sc.fit_transform(x_train) x_test = sc.transform(x_test) #模型構建和訓練 import lightgbm as lgb d_train = lgb.Dataset(x_train, label=y_train) params = {} params['learning_rate'] = 0.003 params['boosting_type'] = 'gbdt' params['objective'] = 'binary' params['metric'] = 'binary_logloss' params['sub_feature'] = 0.5 params['num_leaves'] = 10 params['min_data'] = 50 params['max_depth'] = 10 clf = lgb.train(params, d_train, 100) #模型預測 #Prediction y_pred=clf.predict(x_test) #convert into binary values for i in range(0,99): if y_pred[i]>=.5: # setting threshold to .5 y_pred[i]=1 else: y_pred[i]=0 #準確率計算 #Confusion matrix from sklearn.metrics import confusion_matrix cm = confusion_matrix(y_test, y_pred) #Accuracy from sklearn.metrics import accuracy_score accuracy=accuracy_score(y_pred,y_test)

結果：

調參:

數據科學家在使用參數的時候，總是很掙扎。理想的參數應該長什么樣呢？下面的一組練習可以用來提升你的模型效率。

num_leaves: 這個是控制樹的復雜度的主要的參數。理想情況下，葉子的數量的值應該小于等于 $2^{max_depth}$，大于這個值會導致過擬合。 mindatain_leaf: 設置成一個比較大的值可以避免樹生長太深，但是可能會導致過擬合。實際使用中，對于大數據集設置成幾百到幾千就足夠了。maxdepth: 你可以使用maxdepth來顯式的限制深度。

追求速度:

通過設置 bagging_fraction 和 bagging_freq來使用bagging通過設置 feature_fraction來使用特征下采樣使用小的 max_bin使用 save_binary 來加速加載數據使用并行學習，參考parallel learning guide

追求更高的準確率:

使用大的 max_bin (可能速度會慢)使用小 learning_rate 大的 num_iterations使用大的 num_leaves(可能會過擬合)使用大訓練數據集試試 dart嘗試直接使用類別特征處理過擬合:使用小的 max_bin使用小的 num_leaves使用 min_data_in_leaf 和 min_sum_hessian_in_leaf通過設置 bagging_fraction 和 bagging_freq來使用bagging通過設置 feature_fraction來使用特征下采樣`使用大訓練數據集嘗試使用 lambda_l1, lambda_l2 和 min_gain_to_split 來進行正則化嘗試使用 max_depth 來避免生成的樹太深

總結

以上是生活随笔為你收集整理的LightGBM算法详解(教你一文掌握LightGBM所有知识点)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。