Kaggle神器LightGBM的最全解讀

1. LightGBM簡介

GBDT (Gradient Boosting Decision Tree) 是機(jī)器學(xué)習(xí)中一個(gè)長盛不衰的模型，其主要思想是利用弱分類器（決策樹）迭代訓(xùn)練以得到最優(yōu)模型，該模型具有訓(xùn)練效果好、不易過擬合等優(yōu)點(diǎn)。GBDT不僅在工業(yè)界應(yīng)用廣泛，通常被用于多分類、點(diǎn)擊率預(yù)測(cè)、搜索排序等任務(wù)；在各種數(shù)據(jù)挖掘競(jìng)賽中也是致命武器，據(jù)統(tǒng)計(jì)Kaggle上的比賽有一半以上的冠軍方案都是基于GBDT。而LightGBM（Light Gradient Boosting Machine）是一個(gè)實(shí)現(xiàn)GBDT算法的框架，支持高效率的并行訓(xùn)練，并且具有更快的訓(xùn)練速度、更低的內(nèi)存消耗、更好的準(zhǔn)確率、支持分布式可以快速處理海量數(shù)據(jù)等優(yōu)點(diǎn)。

1.1 LightGBM提出的動(dòng)機(jī)

常用的機(jī)器學(xué)習(xí)算法，例如神經(jīng)網(wǎng)絡(luò)等算法，都可以以mini-batch的方式訓(xùn)練，訓(xùn)練數(shù)據(jù)的大小不會(huì)受到內(nèi)存限制。而GBDT在每一次迭代的時(shí)候，都需要遍歷整個(gè)訓(xùn)練數(shù)據(jù)多次。如果把整個(gè)訓(xùn)練數(shù)據(jù)裝進(jìn)內(nèi)存則會(huì)限制訓(xùn)練數(shù)據(jù)的大?。蝗绻谎b進(jìn)內(nèi)存，反復(fù)地讀寫訓(xùn)練數(shù)據(jù)又會(huì)消耗非常大的時(shí)間。尤其面對(duì)工業(yè)級(jí)海量的數(shù)據(jù)，普通的GBDT算法是不能滿足其需求的。

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

1.2 XGBoost的缺點(diǎn)及LightGBM的優(yōu)化

（1）XGBoost的缺點(diǎn)

在LightGBM提出之前，最有名的GBDT工具就是XGBoost了，它是基于預(yù)排序方法的決策樹算法。這種構(gòu)建決策樹的算法基本思想是：首先，對(duì)所有特征都按照特征的數(shù)值進(jìn)行預(yù)排序。其次，在遍歷分割點(diǎn)的時(shí)候用的代價(jià)找到一個(gè)特征上的最好分割點(diǎn)。最后，在找到一個(gè)特征的最好分割點(diǎn)后，將數(shù)據(jù)分裂成左右子節(jié)點(diǎn)。

這樣的預(yù)排序算法的優(yōu)點(diǎn)是能精確地找到分割點(diǎn)。但是缺點(diǎn)也很明顯：首先，空間消耗大。這樣的算法需要保存數(shù)據(jù)的特征值，還保存了特征排序的結(jié)果（例如，為了后續(xù)快速的計(jì)算分割點(diǎn)，保存了排序后的索引），這就需要消耗訓(xùn)練數(shù)據(jù)兩倍的內(nèi)存。其次，時(shí)間上也有較大的開銷，在遍歷每一個(gè)分割點(diǎn)的時(shí)候，都需要進(jìn)行分裂增益的計(jì)算，消耗的代價(jià)大。最后，對(duì)cache優(yōu)化不友好。在預(yù)排序后，特征對(duì)梯度的訪問是一種隨機(jī)訪問，并且不同的特征訪問的順序不一樣，無法對(duì)cache進(jìn)行優(yōu)化。同時(shí)，在每一層長樹的時(shí)候，需要隨機(jī)訪問一個(gè)行索引到葉子索引的數(shù)組，并且不同特征訪問的順序也不一樣，也會(huì)造成較大的cache miss。

（2）LightGBM的優(yōu)化

為了避免上述XGBoost的缺陷，并且能夠在不損害準(zhǔn)確率的條件下加快GBDT模型的訓(xùn)練速度，lightGBM在傳統(tǒng)的GBDT算法上進(jìn)行了如下優(yōu)化：

基于Histogram的決策樹算法。

單邊梯度采樣 Gradient-based One-Side Sampling(GOSS)：使用GOSS可以減少大量只具有小梯度的數(shù)據(jù)實(shí)例，這樣在計(jì)算信息增益的時(shí)候只利用剩下的具有高梯度的數(shù)據(jù)就可以了，相比XGBoost遍歷所有特征值節(jié)省了不少時(shí)間和空間上的開銷。

互斥特征捆綁 Exclusive Feature Bundling(EFB)：使用EFB可以將許多互斥的特征綁定為一個(gè)特征，這樣達(dá)到了降維的目的。

帶深度限制的Leaf-wise的葉子生長策略：大多數(shù)GBDT工具使用低效的按層生長 (level-wise) 的決策樹生長策略，因?yàn)樗患訁^(qū)分的對(duì)待同一層的葉子，帶來了很多沒必要的開銷。實(shí)際上很多葉子的分裂增益較低，沒必要進(jìn)行搜索和分裂。LightGBM使用了帶有深度限制的按葉子生長 (leaf-wise) 算法。

直接支持類別特征(Categorical Feature)

支持高效并行

Cache命中率優(yōu)化

下面我們就詳細(xì)介紹以上提到的lightGBM優(yōu)化算法。

2. LightGBM的基本原理

2.1 基于Histogram的決策樹算法

（1）直方圖算法

Histogram algorithm應(yīng)該翻譯為直方圖算法，直方圖算法的基本思想是：先把連續(xù)的浮點(diǎn)特征值離散化成個(gè)整數(shù)，同時(shí)構(gòu)造一個(gè)寬度為的直方圖。在遍歷數(shù)據(jù)的時(shí)候，根據(jù)離散化后的值作為索引在直方圖中累積統(tǒng)計(jì)量，當(dāng)遍歷一次數(shù)據(jù)后，直方圖累積了需要的統(tǒng)計(jì)量，然后根據(jù)直方圖的離散值，遍歷尋找最優(yōu)的分割點(diǎn)。

圖：直方圖算法

直方圖算法簡單理解為：首先確定對(duì)于每一個(gè)特征需要多少個(gè)箱子（bin）并為每一個(gè)箱子分配一個(gè)整數(shù)；然后將浮點(diǎn)數(shù)的范圍均分成若干區(qū)間，區(qū)間個(gè)數(shù)與箱子個(gè)數(shù)相等，將屬于該箱子的樣本數(shù)據(jù)更新為箱子的值；最后用直方圖（#bins）表示?？雌饋砗芨叽笊?，其實(shí)就是直方圖統(tǒng)計(jì)，將大規(guī)模的數(shù)據(jù)放在了直方圖中。

我們知道特征離散化具有很多優(yōu)點(diǎn)，如存儲(chǔ)方便、運(yùn)算更快、魯棒性強(qiáng)、模型更加穩(wěn)定等。對(duì)于直方圖算法來說最直接的有以下兩個(gè)優(yōu)點(diǎn)：

內(nèi)存占用更?。褐狈綀D算法不僅不需要額外存儲(chǔ)預(yù)排序的結(jié)果，而且可以只保存特征離散化后的值，而這個(gè)值一般用位整型存儲(chǔ)就足夠了，內(nèi)存消耗可以降低為原來的。也就是說XGBoost需要用位的浮點(diǎn)數(shù)去存儲(chǔ)特征值，并用位的整形去存儲(chǔ)索引，而 LightGBM只需要用 位去存儲(chǔ)直方圖，內(nèi)存相當(dāng)于減少為；

圖：內(nèi)存占用優(yōu)化為預(yù)排序算法的1/8

計(jì)算代價(jià)更小：預(yù)排序算法XGBoost每遍歷一個(gè)特征值就需要計(jì)算一次分裂的增益，而直方圖算法LightGBM只需要計(jì)算次（可以認(rèn)為是常數(shù)），直接將時(shí)間復(fù)雜度從降低到，而我們知道。

當(dāng)然，Histogram算法并不是完美的。由于特征被離散化后，找到的并不是很精確的分割點(diǎn)，所以會(huì)對(duì)結(jié)果產(chǎn)生影響。但在不同的數(shù)據(jù)集上的結(jié)果表明，離散化的分割點(diǎn)對(duì)最終的精度影響并不是很大，甚至有時(shí)候會(huì)更好一點(diǎn)。原因是決策樹本來就是弱模型，分割點(diǎn)是不是精確并不是太重要；較粗的分割點(diǎn)也有正則化的效果，可以有效地防止過擬合；即使單棵樹的訓(xùn)練誤差比精確分割的算法稍大，但在梯度提升（Gradient Boosting）的框架下沒有太大的影響。

（2）直方圖做差加速

LightGBM另一個(gè)優(yōu)化是Histogram（直方圖）做差加速。一個(gè)葉子的直方圖可以由它的父親節(jié)點(diǎn)的直方圖與它兄弟的直方圖做差得到，在速度上可以提升一倍。通常構(gòu)造直方圖時(shí)，需要遍歷該葉子上的所有數(shù)據(jù)，但直方圖做差僅需遍歷直方圖的k個(gè)桶。在實(shí)際構(gòu)建樹的過程中，LightGBM還可以先計(jì)算直方圖小的葉子節(jié)點(diǎn)，然后利用直方圖做差來獲得直方圖大的葉子節(jié)點(diǎn)，這樣就可以用非常微小的代價(jià)得到它兄弟葉子的直方圖。

圖：直方圖做差

注意：XGBoost 在進(jìn)行預(yù)排序時(shí)只考慮非零值進(jìn)行加速，而 LightGBM 也采用類似策略：只用非零特征構(gòu)建直方圖。

2.2 帶深度限制的 Leaf-wise 算法

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

XGBoost 采用 Level-wise 的增長策略，該策略遍歷一次數(shù)據(jù)可以同時(shí)分裂同一層的葉子，容易進(jìn)行多線程優(yōu)化，也好控制模型復(fù)雜度，不容易過擬合。但實(shí)際上Level-wise是一種低效的算法，因?yàn)樗患訁^(qū)分的對(duì)待同一層的葉子，實(shí)際上很多葉子的分裂增益較低，沒必要進(jìn)行搜索和分裂，因此帶來了很多沒必要的計(jì)算開銷。

圖：按層生長的決策樹

LightGBM采用Leaf-wise的增長策略，該策略每次從當(dāng)前所有葉子中，找到分裂增益最大的一個(gè)葉子，然后分裂，如此循環(huán)。因此同Level-wise相比，Leaf-wise的優(yōu)點(diǎn)是：在分裂次數(shù)相同的情況下，Leaf-wise可以降低更多的誤差，得到更好的精度；Leaf-wise的缺點(diǎn)是：可能會(huì)長出比較深的決策樹，產(chǎn)生過擬合。因此LightGBM會(huì)在Leaf-wise之上增加了一個(gè)最大深度的限制，在保證高效率的同時(shí)防止過擬合。

圖：按葉子生長的決策樹

2.3 單邊梯度采樣算法

Gradient-based One-Side Sampling 應(yīng)該被翻譯為單邊梯度采樣（GOSS）。GOSS算法從減少樣本的角度出發(fā)，排除大部分小梯度的樣本，僅用剩下的樣本計(jì)算信息增益，它是一種在減少數(shù)據(jù)量和保證精度上平衡的算法。

AdaBoost中，樣本權(quán)重是數(shù)據(jù)重要性的指標(biāo)。然而在GBDT中沒有原始樣本權(quán)重，不能應(yīng)用權(quán)重采樣。幸運(yùn)的是，我們觀察到GBDT中每個(gè)數(shù)據(jù)都有不同的梯度值，對(duì)采樣十分有用。即梯度小的樣本，訓(xùn)練誤差也比較小，說明數(shù)據(jù)已經(jīng)被模型學(xué)習(xí)得很好了，直接想法就是丟掉這部分梯度小的數(shù)據(jù)。然而這樣做會(huì)改變數(shù)據(jù)的分布，將會(huì)影響訓(xùn)練模型的精確度，為了避免此問題，提出了GOSS算法。

GOSS是一個(gè)樣本的采樣算法，目的是丟棄一些對(duì)計(jì)算信息增益沒有幫助的樣本留下有幫助的。根據(jù)計(jì)算信息增益的定義，梯度大的樣本對(duì)信息增益有更大的影響。因此，GOSS在進(jìn)行數(shù)據(jù)采樣的時(shí)候只保留了梯度較大的數(shù)據(jù)，但是如果直接將所有梯度較小的數(shù)據(jù)都丟棄掉勢(shì)必會(huì)影響數(shù)據(jù)的總體分布。所以，GOSS首先將要進(jìn)行分裂的特征的所有取值按照絕對(duì)值大小降序排序（XGBoost一樣也進(jìn)行了排序，但是LightGBM不用保存排序后的結(jié)果），選取絕對(duì)值最大的個(gè)數(shù)據(jù)。然后在剩下的較小梯度數(shù)據(jù)中隨機(jī)選擇個(gè)數(shù)據(jù)。接著將這個(gè)數(shù)據(jù)乘以一個(gè)常數(shù)，這樣算法就會(huì)更關(guān)注訓(xùn)練不足的樣本，而不會(huì)過多改變?cè)瓟?shù)據(jù)集的分布。最后使用這個(gè)數(shù)據(jù)來計(jì)算信息增益。下圖是GOSS的具體算法。

圖：單邊梯度采樣算法

2.4 互斥特征捆綁算法

高維度的數(shù)據(jù)往往是稀疏的，這種稀疏性啟發(fā)我們?cè)O(shè)計(jì)一種無損的方法來減少特征的維度。通常被捆綁的特征都是互斥的（即特征不會(huì)同時(shí)為非零值，像one-hot），這樣兩個(gè)特征捆綁起來才不會(huì)丟失信息。如果兩個(gè)特征并不是完全互斥（部分情況下兩個(gè)特征都是非零值），可以用一個(gè)指標(biāo)對(duì)特征不互斥程度進(jìn)行衡量，稱之為沖突比率，當(dāng)這個(gè)值較小時(shí)，我們可以選擇把不完全互斥的兩個(gè)特征捆綁，而不影響最后的精度?；コ馓卣骼壦惴ǎ‥xclusive Feature Bundling, EFB）指出如果將一些特征進(jìn)行融合綁定，則可以降低特征數(shù)量。這樣在構(gòu)建直方圖時(shí)的時(shí)間復(fù)雜度從變?yōu)?，這里指特征融合綁定后特征包的個(gè)數(shù)，且遠(yuǎn)小于。

針對(duì)這種想法，我們會(huì)遇到兩個(gè)問題：

怎么判定哪些特征應(yīng)該綁在一起（build bundled）？

怎么把特征綁為一個(gè)（merge feature）？

（1）解決哪些特征應(yīng)該綁在一起

將相互獨(dú)立的特征進(jìn)行綁定是一個(gè) NP-Hard 問題，LightGBM的EFB算法將這個(gè)問題轉(zhuǎn)化為圖著色的問題來求解，將所有的特征視為圖的各個(gè)頂點(diǎn)，將不是相互獨(dú)立的特征用一條邊連接起來，邊的權(quán)重就是兩個(gè)相連接的特征的總沖突值，這樣需要綁定的特征就是在圖著色問題中要涂上同一種顏色的那些點(diǎn)（特征）。此外，我們注意到通常有很多特征，盡管不是％相互排斥，但也很少同時(shí)取非零值。如果我們的算法可以允許一小部分的沖突，我們可以得到更少的特征包，進(jìn)一步提高計(jì)算效率。經(jīng)過簡單的計(jì)算，隨機(jī)污染小部分特征值將影響精度最多，是每個(gè)綁定中的最大沖突比率，當(dāng)其相對(duì)較小時(shí)，能夠完成精度和效率之間的平衡。具體步驟可以總結(jié)如下：

構(gòu)造一個(gè)加權(quán)無向圖，頂點(diǎn)是特征，邊有權(quán)重，其權(quán)重與兩個(gè)特征間沖突相關(guān)；

根據(jù)節(jié)點(diǎn)的度進(jìn)行降序排序，度越大，與其它特征的沖突越大；

遍歷每個(gè)特征，將它分配給現(xiàn)有特征包，或者新建一個(gè)特征包，使得總體沖突最小。

算法允許兩兩特征并不完全互斥來增加特征捆綁的數(shù)量，通過設(shè)置最大沖突比率來平衡算法的精度和效率。EFB 算法的偽代碼如下所示：

圖：貪心綁定算法

算法3的時(shí)間復(fù)雜度是，訓(xùn)練之前只處理一次，其時(shí)間復(fù)雜度在特征不是特別多的情況下是可以接受的，但難以應(yīng)對(duì)百萬維度的特征。為了繼續(xù)提高效率，LightGBM提出了一種更加高效的無圖的排序策略：將特征按照非零值個(gè)數(shù)排序，這和使用圖節(jié)點(diǎn)的度排序相似，因?yàn)楦嗟姆橇阒低ǔ?huì)導(dǎo)致沖突，新算法在算法3基礎(chǔ)上改變了排序策略。

（2）解決怎么把特征綁為一捆

特征合并算法，其關(guān)鍵在于原始特征能從合并的特征中分離出來。綁定幾個(gè)特征在同一個(gè)bundle里需要保證綁定前的原始特征的值可以在bundle中識(shí)別，考慮到histogram-based算法將連續(xù)的值保存為離散的bins，我們可以使得不同特征的值分到bundle中的不同bin（箱子）中，這可以通過在特征值中加一個(gè)偏置常量來解決。比如，我們?cè)赽undle中綁定了兩個(gè)特征A和B，A特征的原始取值為區(qū)間，B特征的原始取值為區(qū)間，我們可以在B特征的取值上加一個(gè)偏置常量，將其取值范圍變?yōu)?，綁定后的特征取值范圍為，這樣就可以放心的融合特征A和B了。具體的特征合并算法如下所示：

圖：特征合并算法

3. LightGBM的工程優(yōu)化

我們將論文《Lightgbm: A highly efficient gradient boosting decision tree》中沒有提到的優(yōu)化方案，而在其相關(guān)論文《A communication-efficient parallel algorithm for decision tree》中提到的優(yōu)化方案，放到本節(jié)作為LightGBM的工程優(yōu)化來向大家介紹。

3.1 直接支持類別特征

實(shí)際上大多數(shù)機(jī)器學(xué)習(xí)工具都無法直接支持類別特征，一般需要把類別特征，通過 one-hot 編碼，轉(zhuǎn)化到多維的特征，降低了空間和時(shí)間的效率。但我們知道對(duì)于決策樹來說并不推薦使用 one-hot 編碼，尤其當(dāng)類別特征中類別個(gè)數(shù)很多的情況下，會(huì)存在以下問題：

會(huì)產(chǎn)生樣本切分不平衡問題，導(dǎo)致切分增益非常?。蠢速M(fèi)了這個(gè)特征）。使用 one-hot編碼，意味著在每一個(gè)決策節(jié)點(diǎn)上只能使用one vs rest（例如是不是狗，是不是貓等）的切分方式。例如，動(dòng)物類別切分后，會(huì)產(chǎn)生是否狗，是否貓等一系列特征，這一系列特征上只有少量樣本為，大量樣本為，這時(shí)候切分樣本會(huì)產(chǎn)生不平衡，這意味著切分增益也會(huì)很小。較小的那個(gè)切分樣本集，它占總樣本的比例太小，無論增益多大，乘以該比例之后幾乎可以忽略；較大的那個(gè)拆分樣本集，它幾乎就是原始的樣本集，增益幾乎為零。比較直觀的理解就是不平衡的切分和不切分沒有區(qū)別。

會(huì)影響決策樹的學(xué)習(xí)。因?yàn)榫退憧梢詫?duì)這個(gè)類別特征進(jìn)行切分，獨(dú)熱編碼也會(huì)把數(shù)據(jù)切分到很多零散的小空間上，如下圖左邊所示。而決策樹學(xué)習(xí)時(shí)利用的是統(tǒng)計(jì)信息，在這些數(shù)據(jù)量小的空間上，統(tǒng)計(jì)信息不準(zhǔn)確，學(xué)習(xí)效果會(huì)變差。但如果使用下圖右邊的切分方法，數(shù)據(jù)會(huì)被切分到兩個(gè)比較大的空間，進(jìn)一步的學(xué)習(xí)也會(huì)更好。下圖右邊葉子節(jié)點(diǎn)的含義是或者放到左孩子，其余放到右孩子。

圖：左圖為基于 one-hot 編碼進(jìn)行分裂，右圖為 LightGBM 基于 many-vs-many 進(jìn)行分裂

而類別特征的使用在實(shí)踐中是很常見的。且為了解決one-hot編碼處理類別特征的不足，LightGBM優(yōu)化了對(duì)類別特征的支持，可以直接輸入類別特征，不需要額外的展開。LightGBM采用 many-vs-many 的切分方式將類別特征分為兩個(gè)子集，實(shí)現(xiàn)類別特征的最優(yōu)切分。假設(shè)某維特征有個(gè)類別，則有種可能，時(shí)間復(fù)雜度為，LightGBM 基于 Fisher的《On Grouping For Maximum Homogeneity》論文實(shí)現(xiàn)了的時(shí)間復(fù)雜度。

算法流程如下圖所示，在枚舉分割點(diǎn)之前，先把直方圖按照每個(gè)類別對(duì)應(yīng)的label均值進(jìn)行排序；然后按照排序的結(jié)果依次枚舉最優(yōu)分割點(diǎn)。從下圖可以看到，為類別的均值。當(dāng)然，這個(gè)方法很容易過擬合，所以LightGBM里面還增加了很多對(duì)于這個(gè)方法的約束和正則化。

圖：LightGBM求解類別特征的最優(yōu)切分算法

在Expo數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，相比展開的方法，使用LightGBM支持的類別特征可以使訓(xùn)練速度加速倍，并且精度一致。更重要的是，LightGBM是第一個(gè)直接支持類別特征的GBDT工具。

3.2 支持高效并行

（1）特征并行

特征并行的主要思想是不同機(jī)器在不同的特征集合上分別尋找最優(yōu)的分割點(diǎn)，然后在機(jī)器間同步最優(yōu)的分割點(diǎn)。XGBoost使用的就是這種特征并行方法。這種特征并行方法有個(gè)很大的缺點(diǎn)：就是對(duì)數(shù)據(jù)進(jìn)行垂直劃分，每臺(tái)機(jī)器所含數(shù)據(jù)不同，然后使用不同機(jī)器找到不同特征的最優(yōu)分裂點(diǎn)，劃分結(jié)果需要通過通信告知每臺(tái)機(jī)器，增加了額外的復(fù)雜度。

LightGBM 則不進(jìn)行數(shù)據(jù)垂直劃分，而是在每臺(tái)機(jī)器上保存全部訓(xùn)練數(shù)據(jù)，在得到最佳劃分方案后可在本地執(zhí)行劃分而減少了不必要的通信。具體過程如下圖所示。

圖：特征并行

（2）數(shù)據(jù)并行

傳統(tǒng)的數(shù)據(jù)并行策略主要為水平劃分?jǐn)?shù)據(jù)，讓不同的機(jī)器先在本地構(gòu)造直方圖，然后進(jìn)行全局的合并，最后在合并的直方圖上面尋找最優(yōu)分割點(diǎn)。這種數(shù)據(jù)劃分有一個(gè)很大的缺點(diǎn)：通訊開銷過大。如果使用點(diǎn)對(duì)點(diǎn)通信，一臺(tái)機(jī)器的通訊開銷大約為；如果使用集成的通信，則通訊開銷為。

LightGBM在數(shù)據(jù)并行中使用分散規(guī)約 (Reduce scatter) 把直方圖合并的任務(wù)分?jǐn)偟讲煌臋C(jī)器，降低通信和計(jì)算，并利用直方圖做差，進(jìn)一步減少了一半的通信量。具體過程如下圖所示。

圖：數(shù)據(jù)并行

（3）投票并行

基于投票的數(shù)據(jù)并行則進(jìn)一步優(yōu)化數(shù)據(jù)并行中的通信代價(jià)，使通信代價(jià)變成常數(shù)級(jí)別。在數(shù)據(jù)量很大的時(shí)候，使用投票并行的方式只合并部分特征的直方圖從而達(dá)到降低通信量的目的，可以得到非常好的加速效果。具體過程如下圖所示。

大致步驟為兩步：

本地找出 Top K 特征，并基于投票篩選出可能是最優(yōu)分割點(diǎn)的特征；

合并時(shí)只合并每個(gè)機(jī)器選出來的特征。

圖：投票并行

3.3 Cache命中率優(yōu)化

XGBoost對(duì)cache優(yōu)化不友好，如下圖所示。在預(yù)排序后，特征對(duì)梯度的訪問是一種隨機(jī)訪問，并且不同的特征訪問的順序不一樣，無法對(duì)cache進(jìn)行優(yōu)化。同時(shí)，在每一層長樹的時(shí)候，需要隨機(jī)訪問一個(gè)行索引到葉子索引的數(shù)組，并且不同特征訪問的順序也不一樣，也會(huì)造成較大的cache miss。為了解決緩存命中率低的問題，XGBoost 提出了緩存訪問算法進(jìn)行改進(jìn)。

圖：隨機(jī)訪問會(huì)造成cache miss

而 LightGBM 所使用直方圖算法對(duì) Cache 天生友好：

首先，所有的特征都采用相同的方式獲得梯度（區(qū)別于XGBoost的不同特征通過不同的索引獲得梯度），只需要對(duì)梯度進(jìn)行排序并可實(shí)現(xiàn)連續(xù)訪問，大大提高了緩存命中率；

其次，因?yàn)椴恍枰鎯?chǔ)行索引到葉子索引的數(shù)組，降低了存儲(chǔ)消耗，而且也不存在 Cache Miss的問題。

圖：LightGBM增加緩存命中率

4. LightGBM的優(yōu)缺點(diǎn)

4.1 優(yōu)點(diǎn)

這部分主要總結(jié)下 LightGBM 相對(duì)于 XGBoost 的優(yōu)點(diǎn)，從內(nèi)存和速度兩方面進(jìn)行介紹。

（1）速度更快

LightGBM 采用了直方圖算法將遍歷樣本轉(zhuǎn)變?yōu)楸闅v直方圖，極大的降低了時(shí)間復(fù)雜度；

LightGBM 在訓(xùn)練過程中采用單邊梯度算法過濾掉梯度小的樣本，減少了大量的計(jì)算；

LightGBM 采用了基于 Leaf-wise 算法的增長策略構(gòu)建樹，減少了很多不必要的計(jì)算量；

LightGBM 采用優(yōu)化后的特征并行、數(shù)據(jù)并行方法加速計(jì)算，當(dāng)數(shù)據(jù)量非常大的時(shí)候還可以采用投票并行的策略；

LightGBM 對(duì)緩存也進(jìn)行了優(yōu)化，增加了緩存命中率；

（2）內(nèi)存更小

XGBoost使用預(yù)排序后需要記錄特征值及其對(duì)應(yīng)樣本的統(tǒng)計(jì)值的索引，而 LightGBM 使用了直方圖算法將特征值轉(zhuǎn)變?yōu)?bin 值，且不需要記錄特征到樣本的索引，將空間復(fù)雜度從降低為，極大的減少了內(nèi)存消耗；

LightGBM 采用了直方圖算法將存儲(chǔ)特征值轉(zhuǎn)變?yōu)榇鎯?chǔ) bin 值，降低了內(nèi)存消耗；

LightGBM 在訓(xùn)練過程中采用互斥特征捆綁算法減少了特征數(shù)量，降低了內(nèi)存消耗。

4.2 缺點(diǎn)

可能會(huì)長出比較深的決策樹，產(chǎn)生過擬合。因此LightGBM在Leaf-wise之上增加了一個(gè)最大深度限制，在保證高效率的同時(shí)防止過擬合；

Boosting族是迭代算法，每一次迭代都根據(jù)上一次迭代的預(yù)測(cè)結(jié)果對(duì)樣本進(jìn)行權(quán)重調(diào)整，所以隨著迭代不斷進(jìn)行，誤差會(huì)越來越小，模型的偏差（bias）會(huì)不斷降低。由于LightGBM是基于偏差的算法，所以會(huì)對(duì)噪點(diǎn)較為敏感；

在尋找最優(yōu)解時(shí)，依據(jù)的是最優(yōu)切分變量，沒有將最優(yōu)解是全部特征的綜合這一理念考慮進(jìn)去；

5. LightGBM實(shí)例

本篇文章所有數(shù)據(jù)集和代碼均在我的GitHub中，地址：https://github.com/Microstrong0305/WeChat-zhihu-csdnblog-code/tree/master/Ensemble%20Learning/LightGBM

5.1 安裝LightGBM依賴包

pipinstalllightgbm

5.2 LightGBM分類和回歸

LightGBM有兩大類接口：LightGBM原生接口 和 scikit-learn接口 ，并且LightGBM能夠?qū)崿F(xiàn)分類和回歸兩種任務(wù)。

（1）基于LightGBM原生接口的分類

importlightgbmaslgb
fromsklearnimportdatasets
fromsklearn.model_selectionimporttrain_test_split
importnumpyasnp
fromsklearn.metricsimportroc_auc_score,accuracy_score

#加載數(shù)據(jù)
iris=datasets.load_iris()

#劃分訓(xùn)練集和測(cè)試集
X_train,X_test,y_train,y_test=train_test_split(iris.data,iris.target,test_size=0.3)

#轉(zhuǎn)換為Dataset數(shù)據(jù)格式
train_data=lgb.Dataset(X_train,label=y_train)
validation_data=lgb.Dataset(X_test,label=y_test)

#參數(shù)
params={
learning_rate:0.1,
lambda_l1:0.1,
lambda_l2:0.2,
max_depth:4,
objective:multiclass,#目標(biāo)函數(shù)
num_class:3,
}

#模型訓(xùn)練
gbm=lgb.train(params,train_data,valid_sets=[validation_data])

#模型預(yù)測(cè)
y_pred=gbm.predict(X_test)
y_pred=[list(x).index(max(x))forxiny_pred]
print(y_pred)

#模型評(píng)估
print(accuracy_score(y_test,y_pred))

（2）基于Scikit-learn接口的分類

fromlightgbmimportLGBMClassifier
fromsklearn.metricsimportaccuracy_score
fromsklearn.model_selectionimportGridSearchCV
fromsklearn.datasetsimportload_iris
fromsklearn.model_selectionimporttrain_test_split
fromsklearn.externalsimportjoblib

#加載數(shù)據(jù)
iris=load_iris()
data=iris.data
target=iris.target

#劃分訓(xùn)練數(shù)據(jù)和測(cè)試數(shù)據(jù)
X_train,X_test,y_train,y_test=train_test_split(data,target,test_size=0.2)

#模型訓(xùn)練
gbm=LGBMClassifier(num_leaves=31,learning_rate=0.05,n_estimators=20)
gbm.fit(X_train,y_train,eval_set=[(X_test,y_test)],early_stopping_rounds=5)

#模型存儲(chǔ)
joblib.dump(gbm,loan_model.pkl)
#模型加載
gbm=joblib.load(loan_model.pkl)

#模型預(yù)測(cè)
y_pred=gbm.predict(X_test,num_iteration=gbm.best_iteration_)

#模型評(píng)估
print(Theaccuracyofpredictionis:,accuracy_score(y_test,y_pred))

#特征重要度
print(Featureimportances:,list(gbm.feature_importances_))

#網(wǎng)格搜索，參數(shù)優(yōu)化
estimator=LGBMClassifier(num_leaves=31)
param_grid={
learning_rate:[0.01,0.1,1],
n_estimators:[20,40]
}
gbm=GridSearchCV(estimator,param_grid)
gbm.fit(X_train,y_train)
print(Bestparametersfoundbygridsearchare:,gbm.best_params_)

（3）基于LightGBM原生接口的回歸

對(duì)于LightGBM解決回歸問題，我們用Kaggle比賽中回歸問題：House Prices: Advanced Regression Techniques，地址：https://www.kaggle.com/c/house-prices-advanced-regression-techniques 來進(jìn)行實(shí)例講解。

該房價(jià)預(yù)測(cè)的訓(xùn)練數(shù)據(jù)集中一共有列，第一列是Id，最后一列是label，中間列是特征。這列特征中，有列是分類型變量，列是整數(shù)變量，列是浮點(diǎn)型變量。訓(xùn)練數(shù)據(jù)集中存在缺失值。

importpandasaspd
fromsklearn.model_selectionimporttrain_test_split
importlightgbmaslgb
fromsklearn.metricsimportmean_absolute_error
fromsklearn.preprocessingimportImputer

#1.讀文件
data=pd.read_csv(./dataset/train.csv)

#2.切分?jǐn)?shù)據(jù)輸入：特征輸出：預(yù)測(cè)目標(biāo)變量
y=data.SalePrice
X=data.drop([SalePrice],axis=1).select_dtypes(exclude=[object])

#3.切分訓(xùn)練集、測(cè)試集,切分比例7.5:2.5
train_X,test_X,train_y,test_y=train_test_split(X.values,y.values,test_size=0.25)

#4.空值處理，默認(rèn)方法：使用特征列的平均值進(jìn)行填充
my_imputer=Imputer()
train_X=my_imputer.fit_transform(train_X)
test_X=my_imputer.transform(test_X)
#5.轉(zhuǎn)換為Dataset數(shù)據(jù)格式
lgb_train=lgb.Dataset(train_X,train_y)
lgb_eval=lgb.Dataset(test_X,test_y,reference=lgb_train)

#6.參數(shù)
params={
task:train,
boosting_type:gbdt,#設(shè)置提升類型
objective:regression,#目標(biāo)函數(shù)
metric:{l2,auc},#評(píng)估函數(shù)
num_leaves:31,#葉子節(jié)點(diǎn)數(shù)
learning_rate:0.05,#學(xué)習(xí)速率
feature_fraction:0.9,#建樹的特征選擇比例
bagging_fraction:0.8,#建樹的樣本采樣比例
bagging_freq:5,#k意味著每k次迭代執(zhí)行bagging
verbose:1#<0?顯示致命的,?=0?顯示錯(cuò)誤?(警告),?>0顯示信息
}
#7.調(diào)用LightGBM模型，使用訓(xùn)練集數(shù)據(jù)進(jìn)行訓(xùn)練（擬合）
#Addverbosity=2toprintmessageswhilerunningboosting
my_model=lgb.train(params,lgb_train,num_boost_round=20,valid_sets=lgb_eval,early_stopping_rounds=5)

#8.使用模型對(duì)測(cè)試集數(shù)據(jù)進(jìn)行預(yù)測(cè)
predictions=my_model.predict(test_X,num_iteration=my_model.best_iteration)

#9.對(duì)模型的預(yù)測(cè)結(jié)果進(jìn)行評(píng)判（平均絕對(duì)誤差）
print("MeanAbsoluteError:"+str(mean_absolute_error(predictions,test_y)))

（4）基于Scikit-learn接口的回歸

importpandasaspd
fromsklearn.model_selectionimporttrain_test_split
importlightgbmaslgb
fromsklearn.metricsimportmean_absolute_error
fromsklearn.preprocessingimportImputer

#1.讀文件
data=pd.read_csv(./dataset/train.csv)

#2.切分?jǐn)?shù)據(jù)輸入：特征輸出：預(yù)測(cè)目標(biāo)變量
y=data.SalePrice
X=data.drop([SalePrice],axis=1).select_dtypes(exclude=[object])

#3.切分訓(xùn)練集、測(cè)試集,切分比例7.5:2.5
train_X,test_X,train_y,test_y=train_test_split(X.values,y.values,test_size=0.25)

#4.空值處理，默認(rèn)方法：使用特征列的平均值進(jìn)行填充
my_imputer=Imputer()
train_X=my_imputer.fit_transform(train_X)
test_X=my_imputer.transform(test_X)
#5.調(diào)用LightGBM模型，使用訓(xùn)練集數(shù)據(jù)進(jìn)行訓(xùn)練（擬合）
#Addverbosity=2toprintmessageswhilerunningboosting
my_model=lgb.LGBMRegressor(objective=regression,num_leaves=31,learning_rate=0.05,n_estimators=20,
verbosity=2)
my_model.fit(train_X,train_y,verbose=False)

#6.使用模型對(duì)測(cè)試集數(shù)據(jù)進(jìn)行預(yù)測(cè)
predictions=my_model.predict(test_X)

#7.對(duì)模型的預(yù)測(cè)結(jié)果進(jìn)行評(píng)判（平均絕對(duì)誤差）
print("MeanAbsoluteError:"+str(mean_absolute_error(predictions,test_y)))

5.3 LightGBM調(diào)參

在上一部分中，LightGBM模型的參數(shù)有一部分進(jìn)行了簡單的設(shè)置，但大都使用了模型的默認(rèn)參數(shù)，但默認(rèn)參數(shù)并不是最好的。要想讓LightGBM表現(xiàn)的更好，需要對(duì)LightGBM模型進(jìn)行參數(shù)微調(diào)。下圖展示的是回歸模型需要調(diào)節(jié)的參數(shù)，分類模型需要調(diào)節(jié)的參數(shù)與此類似。

圖：LightGBM回歸模型調(diào)參

6. 關(guān)于LightGBM若干問題的思考

6.1 LightGBM與XGBoost的聯(lián)系和區(qū)別有哪些？

（1）LightGBM使用了基于histogram的決策樹算法，這一點(diǎn)不同于XGBoost中的貪心算法和近似算法，histogram算法在內(nèi)存和計(jì)算代價(jià)上都有不小優(yōu)勢(shì)。1）內(nèi)存上優(yōu)勢(shì)：很明顯，直方圖算法的內(nèi)存消耗為(因?yàn)閷?duì)特征分桶后只需保存特征離散化之后的值)，而XGBoost的貪心算法內(nèi)存消耗為：，因?yàn)閄GBoost既要保存原始feature的值，也要保存這個(gè)值的順序索引，這些值需要位的浮點(diǎn)數(shù)來保存。2）計(jì)算上的優(yōu)勢(shì)：預(yù)排序算法在選擇好分裂特征計(jì)算分裂收益時(shí)需要遍歷所有樣本的特征值，時(shí)間為，而直方圖算法只需要遍歷桶就行了，時(shí)間為。

（2）XGBoost采用的是level-wise的分裂策略，而LightGBM采用了leaf-wise的策略，區(qū)別是XGBoost對(duì)每一層所有節(jié)點(diǎn)做無差別分裂，可能有些節(jié)點(diǎn)的增益非常小，對(duì)結(jié)果影響不大，但是XGBoost也進(jìn)行了分裂，帶來了不必要的開銷。leaft-wise的做法是在當(dāng)前所有葉子節(jié)點(diǎn)中選擇分裂收益最大的節(jié)點(diǎn)進(jìn)行分裂，如此遞歸進(jìn)行，很明顯leaf-wise這種做法容易過擬合，因?yàn)槿菀紫萑氡容^高的深度中，因此需要對(duì)最大深度做限制，從而避免過擬合。

（3）XGBoost在每一層都動(dòng)態(tài)構(gòu)建直方圖，因?yàn)閄GBoost的直方圖算法不是針對(duì)某個(gè)特定的特征，而是所有特征共享一個(gè)直方圖(每個(gè)樣本的權(quán)重是二階導(dǎo))，所以每一層都要重新構(gòu)建直方圖，而LightGBM中對(duì)每個(gè)特征都有一個(gè)直方圖，所以構(gòu)建一次直方圖就夠了。

（4）LightGBM使用直方圖做差加速，一個(gè)子節(jié)點(diǎn)的直方圖可以通過父節(jié)點(diǎn)的直方圖減去兄弟節(jié)點(diǎn)的直方圖得到，從而加速計(jì)算。

（5）LightGBM支持類別特征，不需要進(jìn)行獨(dú)熱編碼處理。

（6）LightGBM優(yōu)化了特征并行和數(shù)據(jù)并行算法，除此之外還添加了投票并行方案。

（7）LightGBM采用基于梯度的單邊采樣來減少訓(xùn)練樣本并保持?jǐn)?shù)據(jù)分布不變，減少模型因數(shù)據(jù)分布發(fā)生變化而造成的模型精度下降。

（8）特征捆綁轉(zhuǎn)化為圖著色問題，減少特征數(shù)量。

原文標(biāo)題：Kaggle神器LightGBM最全解讀！

文章出處：【微信公眾號(hào)：通信信號(hào)處理研究所】歡迎添加關(guān)注！文章轉(zhuǎn)載請(qǐng)注明出處。

責(zé)任編輯：haq