簡介

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

提出的動機

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

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

XGBoost的缺點

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

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

LightGBM的優(yōu)化

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

• 基于Histogram(直方圖)的決策樹算法。
• 單邊梯度采樣 Gradient-based One-Side Sampling(GOSS)：使用GOSS可以減少大量只具有小梯度的數(shù)據(jù)實例，這樣在計算信息增益的時候只利用剩下的具有高梯度的數(shù)據(jù)就可以了，相比XGBoost遍歷所有特征值節(jié)省了不少時間和空間上的開銷。
• 互斥特征捆綁 Exclusive Feature Bundling(EFB)：使用EFB可以將許多互斥的特征綁定為一個特征，這樣達到了降維的目的。
• 帶深度限制的Leaf-wise的葉子生長策略：大多數(shù)GBDT工具使用低效的按層生長 (level-wise) 的決策樹生長策略，因為它不加區(qū)分的對待同一層的葉子，帶來了很多沒必要的開銷。實際上很多葉子的分裂增益較低，沒必要進行搜索和分裂。LightGBM使用了帶有深度限制的按葉子生長 (leaf-wise) 算法。
• 直接支持類別特征(Categorical Feature)
• 支持高效并行
• Cache命中率優(yōu)化

LGBM原理：

1、基于Histogram的決策樹算法

? ? ? ? （1）直方圖算法

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

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