GBDT

概述

GBDT 是梯度提升樹(shù)（Gradient Boosting Decison Tree）的簡(jiǎn)稱(chēng)，GBDT 也是集成學(xué)習(xí) Boosting 家族的成員，但是卻和傳統(tǒng)的 Adaboost 有很大的不同?；仡櫹?Adaboost，我們是利用前一輪迭代弱學(xué)習(xí)器的誤差率來(lái)更新訓(xùn)練集的權(quán)重，這樣一輪輪的迭代下去。GBDT 也是迭代，使用了前向分布算法，同時(shí)迭代思路和 Adaboost 也有所不同。

GBDT 通過(guò)多輪迭代，每輪迭代產(chǎn)生一個(gè)弱分類(lèi)器，每個(gè)分類(lèi)器在上一輪分類(lèi)器的殘差基礎(chǔ)上進(jìn)行訓(xùn)練。對(duì)弱分類(lèi)器的要求一般是足夠簡(jiǎn)單，并且是低方差和高偏差的。因?yàn)橛?xùn)練的過(guò)程是通過(guò)降低偏差來(lái)不斷提高最終分類(lèi)器的精度。

弱分類(lèi)器一般會(huì)選擇為 CART（也就是分類(lèi)回歸樹(shù)）。由于上述高偏差和簡(jiǎn)單的要求，每個(gè)分類(lèi)回歸樹(shù)的深度不會(huì)很深。最終的總分類(lèi)器是將每輪訓(xùn)練得到的弱分類(lèi)器加權(quán)求和得到的（也就是加法模型）。

讓損失函數(shù)沿著梯度方向的下降就是 GBDT 的核心了。利用損失函數(shù)的負(fù)梯度在當(dāng)前模型的值作為回歸問(wèn)題提升樹(shù)算法中的殘差的近似值去擬合一個(gè)回歸樹(shù)。GBDT 每輪迭代的時(shí)候，都去擬合損失函數(shù)在當(dāng)前模型下的負(fù)梯度。

算法如下（截圖來(lái)自《The Elements of Statistical Learning》）：

GBDT 算法

算法步驟解釋?zhuān)?/p>

1. 初始化，估計(jì)使損失函數(shù)極小化的常數(shù)值，它是只有一個(gè)根節(jié)點(diǎn)的樹(shù)，即 ganma 是一個(gè)常數(shù)值。

2. 迭代

   a. 計(jì)算損失函數(shù)的負(fù)梯度在當(dāng)前模型的值，將它作為殘差的估計(jì)

   b. 估計(jì)回歸樹(shù)葉節(jié)點(diǎn)區(qū)域，以擬合殘差的近似值

   c. 利用線性搜索估計(jì)葉節(jié)點(diǎn)區(qū)域的值，使損失函數(shù)極小化

   d. 更新回歸樹(shù)

3. 得到輸出的最終模型 f(x)

下面我們具體來(lái)說(shuō) CART (是一種二叉樹(shù)) 如何生成。CART 生成的過(guò)程其實(shí)就是一個(gè)選擇特征的過(guò)程。假設(shè)我們目前總共有 M 個(gè)特征。第一步我們需要從中選擇出一個(gè)特征 j，做為二叉樹(shù)的第一個(gè)節(jié)點(diǎn)。然后對(duì)特征 j 的值選擇一個(gè)切分點(diǎn) m。一個(gè) 樣本的特征 j 的值 如果小于 m，則分為一類(lèi)，如果大于 m，則分為另外一類(lèi)。如此便構(gòu)建了 CART 樹(shù)的一個(gè)節(jié)點(diǎn)。其他節(jié)點(diǎn)的生成過(guò)程和這個(gè)是一樣的。

參數(shù)說(shuō)明（sklearn）

• n_estimators：控制弱學(xué)習(xí)器的數(shù)量

• max_depth：設(shè)置樹(shù)深度，深度越大可能過(guò)擬合

• max_leaf_nodes：最大葉子節(jié)點(diǎn)數(shù)

• learning_rate：更新過(guò)程中用到的收縮步長(zhǎng)，(0, 1]

• max_features：劃分時(shí)考慮的最大特征數(shù)，如果特征數(shù)非常多，我們可以靈活使用其他取值來(lái)控制劃分時(shí)考慮的最大特征數(shù)，以控制決策樹(shù)的生成時(shí)間。

• min_samples_split：內(nèi)部節(jié)點(diǎn)再劃分所需最小樣本數(shù)，這個(gè)值限制了子樹(shù)繼續(xù)劃分的條件，如果某節(jié)點(diǎn)的樣本數(shù)少于min_samples_split，則不會(huì)繼續(xù)再?lài)L試選擇最優(yōu)特征來(lái)進(jìn)行劃分。

• min_samples_leaf：葉子節(jié)點(diǎn)最少樣本數(shù)，這個(gè)值限制了葉子節(jié)點(diǎn)最少的樣本數(shù)，如果某葉子節(jié)點(diǎn)數(shù)目小于樣本數(shù)，則會(huì)和兄弟節(jié)點(diǎn)一起被剪枝。

• min_weight_fraction_leaf：葉子節(jié)點(diǎn)最小的樣本權(quán)重和，這個(gè)值限制了葉子節(jié)點(diǎn)所有樣本權(quán)重和的最小值，如果小于這個(gè)值，則會(huì)和兄弟節(jié)點(diǎn)一起被剪枝。

• min_impurity_split：節(jié)點(diǎn)劃分最小不純度，使用 min_impurity_decrease 替代。

• min_impurity_decrease：如果節(jié)點(diǎn)的純度下降大于了這個(gè)閾值，則進(jìn)行分裂。

• subsample：采樣比例，取值為(0, 1]，注意這里的子采樣和隨機(jī)森林不一樣，隨機(jī)森林使用的是放回抽樣，而這里是不放回抽樣。如果取值為1，則全部樣本都使用，等于沒(méi)有使用子采樣。如果取值小于1，則只有一部分樣本會(huì)去做 GBDT 的決策樹(shù)擬合。選擇小于1的比例可以減少方差，即防止過(guò)擬合，但是會(huì)增加樣本擬合的偏差，因此取值不能太低，一般在[0.5, 0.8]之間。

回歸樹(shù)基學(xué)習(xí)器的大小定義了可以被梯度提升模型捕捉到的變量（即特征）相互作用（即多個(gè)特征共同對(duì)預(yù)測(cè)產(chǎn)生影響）的程度。 通常一棵深度為 h 的樹(shù)能捕獲到秩為 h 的相互作用。這里有兩種控制單棵回歸樹(shù)大小的方法。

如果你指定 max_depth = h ，那么將會(huì)產(chǎn)生一個(gè)深度為 h 的完全二叉樹(shù)。這棵樹(shù)將會(huì)有（至多） 2h 個(gè)葉子節(jié)點(diǎn)和 2h - 1 個(gè)切分節(jié)點(diǎn)。

另外，你能通過(guò)參數(shù) max_leaf_nodes 指定葉子節(jié)點(diǎn)的數(shù)量來(lái)控制樹(shù)的大小。在這種情況下，樹(shù)將會(huì)使用最優(yōu)優(yōu)先搜索來(lái)生成，這種搜索方式是通過(guò)每次選取對(duì)不純度提升最大的節(jié)點(diǎn)來(lái)展開(kāi)。一棵 max_leaf_nodes = k 的樹(shù)擁有 k - 1 個(gè)切分節(jié)點(diǎn)，因此可以模擬秩最高達(dá)到 max_leaf_nodes - 1 的相互作用（即 max_leaf_nodes - 1 個(gè)特征共同決定預(yù)測(cè)值）。

常見(jiàn)問(wèn)題

隨機(jī)森林（random forest）和 GBDT 都是屬于集成學(xué)習(xí)（ensemble learning）的范疇，有什么不同

集成學(xué)習(xí)下有兩個(gè)重要的策略 Bagging 和 Boosting，Bagging算法是這樣，每個(gè)分類(lèi)器都隨機(jī)從原樣本中做有放回的采樣，然后分別在這些采樣后的樣本上訓(xùn)練分類(lèi)器，然后再把這些分類(lèi)器組合起來(lái)。簡(jiǎn)單的多數(shù)投票一般就可以。其代表算法是隨機(jī)森林。Boosting 的算法是這樣，它通過(guò)迭代地訓(xùn)練一系列的分類(lèi)器，每個(gè)分類(lèi)器采用的樣本分布都和上一輪的學(xué)習(xí)結(jié)果有關(guān)。其代表算法是 AdaBoost，GBDT。

為什么隨機(jī)森林的樹(shù)深度往往大于 GBDT 的樹(shù)深度

其實(shí)就機(jī)器學(xué)習(xí)算法來(lái)說(shuō)，其泛化誤差可以分解為兩部分，偏差（bias）和方差（variance）。偏差指的是算法的期望預(yù)測(cè)與真實(shí)預(yù)測(cè)之間的偏差程度，反應(yīng)了模型本身的擬合能力；方差度量了同等大小的訓(xùn)練集的變動(dòng)導(dǎo)致學(xué)習(xí)性能的變化，刻畫(huà)了數(shù)據(jù)擾動(dòng)所導(dǎo)致的影響。

如下圖所示，當(dāng)模型越復(fù)雜時(shí)，擬合的程度就越高，模型的訓(xùn)練偏差就越小。但此時(shí)如果換一組數(shù)據(jù)可能模型的變化就會(huì)很大，即模型的方差很大。所以模型過(guò)于復(fù)雜的時(shí)候會(huì)導(dǎo)致過(guò)擬合。

當(dāng)模型越簡(jiǎn)單時(shí)，即使我們?cè)贀Q一組數(shù)據(jù)，最后得出的學(xué)習(xí)器和之前的學(xué)習(xí)器的差別就不那么大，模型的方差很小。還是因?yàn)槟Ｐ秃?jiǎn)單，所以偏差會(huì)很大。

模型比較

也就是說(shuō)，當(dāng)我們訓(xùn)練一個(gè)模型時(shí)，偏差和方差都得照顧到，漏掉一個(gè)都不行。

對(duì)于 Bagging 算法來(lái)說(shuō)，由于我們會(huì)并行地訓(xùn)練很多不同的分類(lèi)器的目的就是降低這個(gè)方差（variance），因?yàn)椴捎昧讼嗷オ?dú)立的基分類(lèi)器多了以后，h 的值自然就會(huì)靠近。所以對(duì)于每個(gè)基分類(lèi)器來(lái)說(shuō)，目標(biāo)就是如何降低這個(gè)偏差（bias），所以我們會(huì)采用深度很深甚至不剪枝的決策樹(shù)。

對(duì)于 Boosting 來(lái)說(shuō)，每一步我們都會(huì)在上一輪的基礎(chǔ)上更加擬合原數(shù)據(jù)，所以可以保證偏差（bias），所以對(duì)于每個(gè)基分類(lèi)器來(lái)說(shuō)，問(wèn)題就在于如何選擇 variance 更小的分類(lèi)器，即更簡(jiǎn)單的分類(lèi)器，所以我們選擇了深度很淺的決策樹(shù)。

GBDT 如何用于分類(lèi)

GBDT 無(wú)論用于分類(lèi)還是回歸一直都是使用的 CART 回歸樹(shù)。不會(huì)因?yàn)槲覀兯x擇的任務(wù)是分類(lèi)任務(wù)就選用分類(lèi)樹(shù)，這里面的核心是因?yàn)?GBDT 每輪的訓(xùn)練是在上一輪的訓(xùn)練的殘差基礎(chǔ)之上進(jìn)行訓(xùn)練的。這里的殘差就是當(dāng)前模型的負(fù)梯度值 。這個(gè)要求每輪迭代的時(shí)候，弱分類(lèi)器的輸出的結(jié)果相減是有意義的。殘差相減是有意義的。

在分類(lèi)訓(xùn)練的時(shí)候，是針對(duì)樣本 X 每個(gè)可能的類(lèi)都訓(xùn)練一個(gè)分類(lèi)回歸樹(shù)。針對(duì)樣本有三類(lèi)的情況，我們實(shí)質(zhì)上是在每輪的訓(xùn)練的時(shí)候是同時(shí)訓(xùn)練三顆樹(shù)。第一棵樹(shù)針對(duì)樣本 x 的第一類(lèi)，輸入為（x, 0）。第二棵樹(shù)輸入針對(duì)樣本 x 的第二類(lèi)，假設(shè) x 屬于第二類(lèi)，輸入為（x, 1）。第三棵樹(shù)針對(duì)樣本 x 的第三類(lèi)，輸入為（x, 0）。在這里每棵樹(shù)的訓(xùn)練過(guò)程其實(shí)就是就是我們之前已經(jīng)提到過(guò)的 CART 的生成過(guò)程。在此處我們參照之前的生成樹(shù)的程序即可以就解出三棵樹(shù)，以及三棵樹(shù)對(duì) x 類(lèi)別的預(yù)測(cè)值 f1(x), f2(x), f3(x)。那么在此類(lèi)訓(xùn)練中，我們仿照多分類(lèi)的邏輯回歸，使用 softmax 來(lái)產(chǎn)生概率。并且我們我們可以針對(duì)類(lèi)別 1 求出殘差 f11(x) = 0 ? f1(x)；類(lèi)別 2 求出殘差 f22(x) = 1 ? f2(x)；類(lèi)別 3 求出殘差 f33(x) = 0 ? f3(x)。然后開(kāi)始第二輪訓(xùn)練，針對(duì)第一類(lèi)輸入為(x, f11(x))，針對(duì)第二類(lèi)輸入為(x, f22(x))，針對(duì)第三類(lèi)輸入為(x, f33(x))。繼續(xù)訓(xùn)練出三棵樹(shù)，一直迭代 M 輪，每輪構(gòu)建 3 棵樹(shù)。當(dāng)訓(xùn)練完畢以后，新來(lái)一個(gè)樣本 x1，我們需要預(yù)測(cè)該樣本的類(lèi)別的時(shí)候，便可使用 softmax 計(jì)算每個(gè)類(lèi)別的概率。

XGBoost

概述

XGBoost 是 “Extreme Gradient Boosting” 的縮寫(xiě)，XGBoost 算法的步驟和 GBDT 基本相同，都是首先初始化為一個(gè)常數(shù)，GBDT 是根據(jù)一階導(dǎo)數(shù)，XGBoost 是根據(jù)一階導(dǎo)數(shù) gi 和二階導(dǎo)數(shù) hi，迭代生成基學(xué)習(xí)器，相加更新學(xué)習(xí)器。

泰勒公式是一個(gè)用函數(shù)在某點(diǎn)的信息描述其附近取值的公式?；拘问绞牵?/p>

泰勒公式

一階泰勒展開(kāi)

二階泰勒展開(kāi)

XGBoost 的損失函數(shù)不僅使用到了一階導(dǎo)數(shù)，還使用二階導(dǎo)數(shù)。

損失函數(shù)

對(duì)上述損失函數(shù)做二階泰勒展開(kāi)，其中 g 為 一階導(dǎo)數(shù)，h 為二階導(dǎo)數(shù)，最后一項(xiàng)為正則項(xiàng)，

損失函數(shù)展開(kāi)

XGBoost 對(duì)分類(lèi)前后的增益計(jì)算采用了如下方式（ID3 采用信息增益，C4.5 采用信息增益比，CART 采用 Gini 系數(shù)），

增益公式

這個(gè)公式形式上跟 ID3 算法、CART 算法是一致的，都是用分裂后的某種值減去分裂前的某種值，從而得到增益。為了限制樹(shù)的生長(zhǎng)，我們可以加入閾值，當(dāng)增益大于閾值時(shí)才讓節(jié)點(diǎn)分裂，上式中的 gamma 即閾值，它是正則項(xiàng)里葉子節(jié)點(diǎn)數(shù)T的系數(shù)，所以 XGBoost 在優(yōu)化目標(biāo)函數(shù)的同時(shí)相當(dāng)于做了預(yù)剪枝。另外，上式中還有一個(gè)系數(shù) lambda，是正則項(xiàng)里 leaf score 的 L2 模平方的系數(shù)，對(duì) leaf score 做了平滑，也起到了防止過(guò)擬合的作用，這個(gè)是傳統(tǒng) GBDT 里不具備的特性。

優(yōu)勢(shì)

1. 在尋找最佳分割點(diǎn)時(shí)，考慮傳統(tǒng)的枚舉每個(gè)特征的所有可能分割點(diǎn)的貪心法效率太低，XGBoost 實(shí)現(xiàn)了一種近似的算法。大致的思想是根據(jù)百分位法列舉幾個(gè)可能成為分割點(diǎn)的候選者，然后從候選者中根據(jù)上面求分割點(diǎn)的公式計(jì)算找出最佳的分割點(diǎn)。同時(shí)當(dāng)分裂時(shí)遇到一個(gè)負(fù)損失時(shí)，GBM 會(huì)停止分裂。XGBoost 會(huì)一直分裂到指定的最大深度(max_depth)，然后回過(guò)頭來(lái)剪枝。如果某個(gè)節(jié)點(diǎn)之后不再有正值，它會(huì)去除這個(gè)分裂。這種做法的優(yōu)點(diǎn)，當(dāng)一個(gè)負(fù)損失（如-2）后面有個(gè)正損失（如+10）的時(shí)候，就顯現(xiàn)出來(lái)了。GBM 會(huì)在-2處停下來(lái)，因?yàn)樗龅搅艘粋€(gè)負(fù)值。但是 XGBoost 會(huì)繼續(xù)分裂，然后發(fā)現(xiàn)這兩個(gè)分裂綜合起來(lái)會(huì)得到+8，因此會(huì)保留這兩個(gè)分裂。

2. 標(biāo)準(zhǔn) GBM 的實(shí)現(xiàn)沒(méi)有像 XGBoost 這樣的正則化步驟。正則化對(duì)減少過(guò)擬合也是有幫助的。

3. XGBoost 考慮了訓(xùn)練數(shù)據(jù)為稀疏值的情況，可以為缺失值或者指定的值指定分支的默認(rèn)方向，這能大大提升算法的效率。

4. 列抽樣，XGboost 借鑒了隨機(jī)森林的做法，支持列抽樣，不僅能降低過(guò)擬合，還能減少計(jì)算。

5. 特征列排序后以塊的形式存儲(chǔ)在內(nèi)存中，在迭代中可以重復(fù)使用；雖然 boosting 算法迭代必須串行，但是在處理每個(gè)特征列時(shí)可以做到并行。

6. 按照特征列方式存儲(chǔ)能優(yōu)化尋找最佳的分割點(diǎn)，但是當(dāng)以行計(jì)算梯度數(shù)據(jù)時(shí)會(huì)導(dǎo)致內(nèi)存的不連續(xù)訪問(wèn)，嚴(yán)重時(shí)會(huì)導(dǎo)致 cache miss，降低算法效率。paper 中提到，可先將數(shù)據(jù)收集到線程內(nèi)部的 buffer，然后再計(jì)算，提高算法的效率。

7. XGBoost 還考慮了當(dāng)數(shù)據(jù)量比較大，內(nèi)存不夠時(shí)怎么有效的使用磁盤(pán)，主要是結(jié)合多線程、數(shù)據(jù)壓縮、分片的方法，盡可能的提高算法的效率。

參數(shù)說(shuō)明

括號(hào)內(nèi)為 sklearn 參數(shù)。

通用參數(shù)

• booster：基學(xué)習(xí)器類(lèi)型，gbtree，gblinear 或 dart（增加了 Dropout） ，gbtree 和 dart 使用基于樹(shù)的模型，而 gblinear 使用線性模型

• silent：使用 0 會(huì)打印更多信息

• nthread：運(yùn)行時(shí)線程數(shù)

Booster 參數(shù)

樹(shù)模型

• eta（learning_rate）：更新過(guò)程中用到的收縮步長(zhǎng)，(0, 1]

• gamma：在節(jié)點(diǎn)分裂時(shí)，只有在分裂后損失函數(shù)的值下降了，才會(huì)分裂這個(gè)節(jié)點(diǎn)。Gamma 指定了節(jié)點(diǎn)分裂所需的最小損失函數(shù)下降值。這個(gè)參數(shù)值越大，算法越保守。

• max_depth：樹(shù)的最大深度，這個(gè)值也是用來(lái)避免過(guò)擬合的

• min_child_weight：決定最小葉子節(jié)點(diǎn)樣本權(quán)重和。當(dāng)它的值較大時(shí)，可以避免模型學(xué)習(xí)到局部的特殊樣本。但如果這個(gè)值過(guò)高，會(huì)導(dǎo)致欠擬合。

• max_delta_step：這參數(shù)限制每顆樹(shù)權(quán)重改變的最大步長(zhǎng)。如果是0意味著沒(méi)有約束。如果是正值那么這個(gè)算法會(huì)更保守，通常不需要設(shè)置。

• subsample：這個(gè)參數(shù)控制對(duì)于每棵樹(shù)，隨機(jī)采樣的比例。減小這個(gè)參數(shù)的值算法會(huì)更加保守，避免過(guò)擬合。但是這個(gè)值設(shè)置的過(guò)小，它可能會(huì)導(dǎo)致欠擬合。

• colsample_bytree：用來(lái)控制每顆樹(shù)隨機(jī)采樣的列數(shù)的占比。

• colsample_bylevel：用來(lái)控制的每一級(jí)的每一次分裂，對(duì)列數(shù)的采樣的占比。

• lambda（reg_lambda）：L2 正則化項(xiàng)的權(quán)重系數(shù)，越大模型越保守。

• alpha（reg_alpha）：L1 正則化項(xiàng)的權(quán)重系數(shù)，越大模型越保守。

• tree_method：樹(shù)生成算法，auto, exact, approx, hist, gpu_exact, gpu_hist

• scale_pos_weight：各類(lèi)樣本十分不平衡時(shí)，把這個(gè)參數(shù)設(shè)置為一個(gè)正數(shù)，可以使算法更快收斂。典型值是 sum(negative cases) / sum(positive cases)

Dart 額外參數(shù)

• sample_type：采樣算法

• normalize_type：標(biāo)準(zhǔn)化算法

• rate_drop：前置樹(shù)的丟棄率，有多少比率的樹(shù)不進(jìn)入下一個(gè)迭代，[0, 1]

• one_drop：設(shè)置為 1 的話每次至少有一棵樹(shù)被丟棄。

• skip_drop：跳過(guò)丟棄階段的概率，[0, 1]，非零的 skip_drop 比 rate_drop 和 one_drop 有更高的優(yōu)先級(jí)。

線性模型

• lambda（reg_lambda）：L2 正則化項(xiàng)的權(quán)重系數(shù)，越大模型越保守。

• alpha（reg_alpha）：L1 正則化項(xiàng)的權(quán)重系數(shù)，越大模型越保守。

• lambda_bias（reg_lambda_bias）：L2 正則化項(xiàng)的偏置

學(xué)習(xí)任務(wù)參數(shù)

• objective：這個(gè)參數(shù)定義需要被最小化的損失函數(shù)。

• base_score：初始化預(yù)測(cè)分?jǐn)?shù)，全局偏置。

• eval_metric：對(duì)于有效數(shù)據(jù)的度量方法，取值范圍取決于 objective。

• seed：隨機(jī)數(shù)種子，相同的種子可以復(fù)現(xiàn)隨機(jī)結(jié)果，用于調(diào)參。

LightGBM

概述

LightGBM 是微軟開(kāi)發(fā)的一款快速、分布式、高性能的基于決策樹(shù)的梯度 Boosting 框架。主要有以下優(yōu)勢(shì)：

• 更快的訓(xùn)練效率
• 低內(nèi)存使用
• 更好的準(zhǔn)確率（我對(duì)比 XGBoost 沒(méi)太大差別）
• 支持并行學(xué)習(xí)
• 可處理大規(guī)模數(shù)據(jù)

改進(jìn)

基于 Histogram 的決策樹(shù)算法

把連續(xù)的浮點(diǎn)特征值離散化成 k 個(gè)整數(shù)，同時(shí)構(gòu)造一個(gè)寬度為 k 的直方圖。在遍歷數(shù)據(jù)的時(shí)候，根據(jù)離散化后的值作為索引在直方圖中累積統(tǒng)計(jì)量，當(dāng)遍歷一次數(shù)據(jù)后，直方圖累積了需要的統(tǒng)計(jì)量，然后根據(jù)直方圖的離散值，遍歷尋找最優(yōu)的分割點(diǎn)。
當(dāng)然， histogram 算法也有缺點(diǎn)，它不能找到很精確的分割點(diǎn)，訓(xùn)練誤差沒(méi)有 pre-sorted 好。但從實(shí)驗(yàn)結(jié)果來(lái)看， histogram 算法在測(cè)試集的誤差和 pre-sorted 算法差異并不是很大，甚至有時(shí)候效果更好。實(shí)際上可能決策樹(shù)對(duì)于分割點(diǎn)的精確程度并不太敏感，而且較“粗”的分割點(diǎn)也自帶正則化的效果。

直方圖做差加速

一個(gè)葉子的直方圖可以由它的父親節(jié)點(diǎn)的直方圖與它兄弟節(jié)點(diǎn)的直方圖做差得到，提升一倍速度。

帶深度限制的 Leaf-wise 的葉子生長(zhǎng)策略

Level-wise 過(guò)一次數(shù)據(jù)可以同時(shí)分裂同一層的葉子，容易進(jìn)行多線程優(yōu)化，也好控制模型復(fù)雜度，不容易過(guò)擬合。但實(shí)際上 Level-wise 是一種低效的算法，因?yàn)樗患訁^(qū)分的對(duì)待同一層的葉子，帶來(lái)了很多沒(méi)必要的開(kāi)銷(xiāo)，因?yàn)閷?shí)際上很多葉子的分裂增益較低，沒(méi)必要進(jìn)行搜索和分裂。
Leaf-wise 則是一種更為高效的策略，每次從當(dāng)前所有葉子中，找到分裂增益最大的一個(gè)葉子，然后分裂，如此循環(huán)。因此同 Level-wise 相比，在分裂次數(shù)相同的情況下，Leaf-wise 可以降低更多的誤差，得到更好的精度。Leaf-wise 的缺點(diǎn)是可能會(huì)長(zhǎng)出比較深的決策樹(shù)，產(chǎn)生過(guò)擬合。因此 LightGBM 在 Leaf-wise 之上增加了一個(gè)最大深度的限制，在保證高效率的同時(shí)防止過(guò)擬合。

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

LightGBM 優(yōu)化了對(duì)類(lèi)別特征的支持，可以直接輸入類(lèi)別特征，不需要額外的 0/1 展開(kāi)，并在決策樹(shù)算法上增加了類(lèi)別特征的決策規(guī)則。

基于直方圖的稀疏特征優(yōu)化

對(duì)于稀疏特征，只需要 O(2 * #non_zero_data) 來(lái)構(gòu)建直方圖。

多線程優(yōu)化

在特征并行算法中，通過(guò)在本地保存全部數(shù)據(jù)避免對(duì)數(shù)據(jù)切分結(jié)果的通信。在數(shù)據(jù)并行中使用分散規(guī)約(Reduce scatter)把直方圖合并的任務(wù)分?jǐn)偟讲煌臋C(jī)器，降低通信和計(jì)算，并利用直方圖做差，進(jìn)一步減少了一半的通信量?；谕镀钡臄?shù)據(jù)并行(Parallel Voting)則進(jìn)一步優(yōu)化數(shù)據(jù)并行中的通信代價(jià)，使通信代價(jià)變成常數(shù)級(jí)別。特征并行的主要思想是在不同機(jī)器在不同的特征集合上分別尋找最優(yōu)的分割點(diǎn)，然后在機(jī)器間同步最優(yōu)的分割點(diǎn)。數(shù)據(jù)并行則是讓不同的機(jī)器先在本地構(gòu)造直方圖，然后進(jìn)行全局的合并，最后在合并的直方圖上面尋找最優(yōu)分割點(diǎn)。

參數(shù)說(shuō)明

XGBoost 和 LightGBM 參數(shù)對(duì)比

括號(hào)內(nèi)為 sklearn 參數(shù)。

• application（objective）：學(xué)習(xí)目標(biāo)和損失函數(shù)。
• boosting（boosting_type）：‘gbdt’, traditional Gradient Boosting Decision Tree；‘dart’, Dropouts meet Multiple Additive Regression Trees；‘goss’, Gradient-based One-Side Sampling；‘rf’, Random Forest
• num_leaves：因?yàn)?LightGBM 使用的是 leaf-wise 的算法，因此在調(diào)節(jié)樹(shù)的復(fù)雜程度時(shí)，使用的是 num_leaves 而不是 max_depth。大致?lián)Q算關(guān)系：num_leaves = 2^(max_depth)。它的值的設(shè)置應(yīng)該小于 2^(max_depth)，否則可能會(huì)導(dǎo)致過(guò)擬合。
• max_depth：限制樹(shù)的深度，和 num_leaves 只需要設(shè)置一個(gè)。
• min_data_in_leaf（min_child_samples ）：葉子節(jié)點(diǎn)中最小的數(shù)據(jù)量，調(diào)大可以防止過(guò)擬合。
• min_sum_hessian_in_leaf（min_child_weight）：葉子節(jié)點(diǎn)的最小權(quán)重和，調(diào)大可以防止過(guò)擬合。
• bagging_fraction（subsample ）：樣本采樣比例，同 XGBoost ，調(diào)小可以防止過(guò)擬合，加快運(yùn)算速度。
• feature_fraction（colsample_bytree）：列采樣比例，同 XGBoost，調(diào)小可以防止過(guò)擬合，加快運(yùn)算速度。
• bagging_freq（subsample_freq）：bagging 的頻率，0 表示禁止 bagging，正整數(shù)表示每隔多少個(gè)迭代進(jìn)行 bagging。
• lambda_l1（reg_alpha）：L1 正則化項(xiàng)，同 XGBoost。
• lambda_l2（reg_lambda）：L2 正則化項(xiàng)，同 XGBoost。
• min_gain_to_split（min_split_gain）：分裂的最小增益閾值。
• drop_rate：Dart 的丟棄率。
• skip_drop：Dart 的跳過(guò)丟棄步驟的概率。
• max_drop：Dart 每次迭代最大丟棄數(shù)量。

參數(shù)調(diào)優(yōu)

以 XGBoost 為例，演示一下參數(shù)調(diào)優(yōu)的方法。

XGBoost 提供了 cv 函數(shù)進(jìn)行自動(dòng)化參數(shù)選擇，首先定義一個(gè)函數(shù)。

def model_cv(model, X, y, cv_folds=5, early_stopping_rounds=50, seed=0):
    xgb_param = model.get_xgb_params()
    xgtrain = xgb.DMatrix(X, label=y)
    cvresult = xgb.cv(xgb_param, xgtrain, num_boost_round=model.get_params()['n_estimators'], nfold=cv_folds,
                      metrics='auc', seed=seed, callbacks=[
            xgb.callback.print_evaluation(show_stdv=False),
            xgb.callback.early_stop(early_stopping_rounds)
        ])
    num_round_best = cvresult.shape[0] - 1
    print('Best round num: ', num_round_best)
    return num_round_best

cv_folds 是交叉驗(yàn)證的份數(shù)，early_stopping_rounds 是在多少次迭代 metrics 沒(méi)有變好的情況下提前結(jié)束，這個(gè)函數(shù)可以找到此參數(shù)組下最佳的迭代次數(shù)（n_estimators）。

num_round = 5000
seed = 0
max_depth = 3
min_child_weight = 7
gamma = 0
subsample = 0.8
colsample_bytree = 0.8
scale_pos_weight = 1
reg_alpha = 1
reg_lambda = 1e-5
learning_rate = 0.1
model = XGBClassifier(learning_rate=learning_rate, n_estimators=num_round, max_depth=max_depth,
                      min_child_weight=min_child_weight, gamma=gamma, subsample=subsample, reg_alpha=reg_alpha,
                      reg_lambda=reg_lambda, colsample_bytree=colsample_bytree, objective='binary:logistic',
                      nthread=4, scale_pos_weight=scale_pos_weight, seed=seed)
num_round = model_cv(model, x, y)

在開(kāi)始的時(shí)候，可以選擇較大一點(diǎn)的 learning_rate，這樣可以更快地收斂，計(jì)算出最佳的迭代次數(shù)。
然后，使用 Sklearn 的 GridSearchCV 自動(dòng)測(cè)試參數(shù)。

def gridsearch_cv(model, test_param, X, y, cv=5): 
    gsearch = GridSearchCV(estimator=model, param_grid=test_param, scoring='roc_auc', n_jobs=4, iid=False, cv=cv) 
    gsearch.fit(X, y) 
    print('CV Results: ', gsearch.cv_results_) 
    print('Best Params: ', gsearch.best_params_) 
    print('Best Score: ', gsearch.best_score_) 
    return gsearch.best_params_ 

提供模型及候選參數(shù)的列表，GridSearchCV 能自動(dòng)窮舉所有組合的參數(shù)，計(jì)算最佳的參數(shù)組合。
首先調(diào)試 max_depth 和 min_child_weight 參數(shù)組合

# tune max_depth & min_child_weight 
param_test1 = { 
    'max_depth': range(3, 10, 2), 
    'min_child_weight': range(1, 10, 2) 
} 
gridsearch_cv(model, param_test1, x, y) 

函數(shù)能從所有的候選組合中選出誤差最小的組合，注意開(kāi)始的時(shí)候不要給太多組合，不然計(jì)算會(huì)非常慢?？梢韵冉o出一個(gè)大范圍，然后在慢慢縮小范圍。
例如，如果 max_depth = 6，min_child_weight = 4 時(shí)最佳，則縮小范圍再試一次。

param_test1 = {
    'max_depth': range(5, 8, 1),
    'min_child_weight': range(3, 6, 1)
}
gridsearch_cv(model, param_test1, x, y)

然后調(diào)整 gamma。

# tune gamma
param_test2 = {
    'gamma': [i / 10.0 for i in range(0, 5)]
}
gridsearch_cv(model, param_test2, x, y)

接著類(lèi)似調(diào)整其他參數(shù)，先從大范圍開(kāi)始，慢慢縮小范圍。

# tune subsample & colsample_bytree
param_test3 = {
    'subsample': [i / 10.0 for i in range(6, 10)],
    'colsample_bytree': [i / 10.0 for i in range(6, 10)]
}
gridsearch_cv(model, param_test3, x, y)
# tune scale_pos_weight
param_test4 = {
    'scale_pos_weight': [i for i in range(1, 10, 2)]
}
gridsearch_cv(model, param_test4, x, y)
# tune reg_alpha
param_test5 = {
    'reg_alpha': [1e-5, 1e-2, 0.1, 1, 100, 1000]
}
gridsearch_cv(model, param_test5, x, y)
# tune reg_lambda
param_test6 = {
    'reg_lambda': [1e-5, 1e-2, 0.1, 1, 100, 1000]
}
gridsearch_cv(model, param_test6, x, y)

在所有的參數(shù)的調(diào)整完成后，可以降低學(xué)習(xí)速率，再用 cv 測(cè)試一下。當(dāng)然每次調(diào)整之后，都可以用 cv 校正一下。

最后說(shuō)一下，

1. 僅僅靠參數(shù)的調(diào)整和模型的小幅優(yōu)化，想要讓模型的表現(xiàn)有個(gè)大幅度提升是不可能的。確實(shí)是有一定的提升，但是沒(méi)有達(dá)到質(zhì)的飛躍。
2. 要想讓模型的表現(xiàn)有一個(gè)質(zhì)的飛躍，需要依靠其他的手段，例如特征工程（feature egineering），模型組合（ensemble of model），以及堆疊（stacking）等。

以上內(nèi)容是我自己的學(xué)習(xí)心得，部分內(nèi)容摘自其他文章，詳見(jiàn)參考文獻(xiàn)，大家有什么問(wèn)題，歡迎與我交流。

實(shí)戰(zhàn)示例

Kaggle 實(shí)戰(zhàn)，使用 XGBoost 進(jìn)行 Titanic 生存預(yù)測(cè)、房?jī)r(jià)預(yù)測(cè)請(qǐng)參見(jiàn) https://github.com/wwtg99/kaggle_getting_started

參考文獻(xiàn)

• Sklearn 官網(wǎng)
• Sklearn 中文文檔
• XGBoost 源碼
• XGBoost 文檔
• XGBoost 中文文檔
• LightGBM 源碼
• LightGBM 文檔](https://lightgbm.readthedocs.io/en/latest/index.html))
• LightGBM 中文文檔
• http://www.itdecent.cn/p/48e82dbb142b
• 知乎問(wèn)答1[](https://www.zhihu.com/question/45487317[https://www.zhihu.com/question/45487317]))
• 知乎問(wèn)答2](https://www.zhihu.com/question/41354392/answer/98658997))
• 知乎問(wèn)答3](https://www.zhihu.com/question/51644470))
• https://www.analyticsvidhya.com/blog/2016/03/complete-guide-parameter-tuning-xgboost-with-codes-python/