本文是決策樹的第三篇，主要介紹基于 Boosting 框架的主流集成算法，包括 XGBoost 和 LightGBM。

XGBoost

XGBoost 是大規(guī)模并行 boosting tree 的工具，它是目前最快最好的開源 boosting tree 工具包，比常見的工具包快 10 倍以上。Xgboost 和 GBDT 兩者都是 boosting 方法，除了工程實現(xiàn)、解決問題上的一些差異外，最大的不同就是目標(biāo)函數(shù)的定義。故本文將從數(shù)學(xué)原理和工程實現(xiàn)上進(jìn)行介紹，并在最后介紹下 Xgboost 的優(yōu)點。

1.1 數(shù)學(xué)原理

1.1.1 目標(biāo)函數(shù)

我們知道 XGBoost 是由 k 個基模型組成的一個加法運算式：

其中 為第 k 個基模型， 為第 i 個樣本的預(yù)測值。

損失函數(shù)可由預(yù)測值 與真實值 進(jìn)行表示：

其中 n 為樣本數(shù)量。

我們知道模型的預(yù)測精度由模型的偏差和方差共同決定，損失函數(shù)代表了模型的偏差，想要方差小則需要簡單的模型，所以目標(biāo)函數(shù)由模型的損失函數(shù) L 與抑制模型復(fù)雜度的正則項 組成，所以我們有：

為模型的正則項，由于 XGBoost 支持決策樹也支持線性模型，所以這里不再展開描述。

我們知道 boosting 模型是前向加法，以第 t 步的模型為例，模型對第 i 個樣本 的預(yù)測為：

其中 由第 t-1 步的模型給出的預(yù)測值，是已知常數(shù)， 是我們這次需要加入的新模型的預(yù)測值，此時，目標(biāo)函數(shù)就可以寫成：

求此時最優(yōu)化目標(biāo)函數(shù)，就相當(dāng)于求解 。

泰勒公式是將一個在 處具有 n 階導(dǎo)數(shù)的函數(shù) f(x) 利用關(guān)于 的 n 次多項式來逼近函數(shù)的方法，若函數(shù) f(x) 在包含 的某個閉區(qū)間 上具有 n 階導(dǎo)數(shù)，且在開區(qū)間 (a,b) 上具有 n+1 階導(dǎo)數(shù)，則對閉區(qū)間 上任意一點 x 有 其中的多項式稱為函數(shù)在 處的泰勒展開式， 是泰勒公式的余項且是 的高階無窮小。

根據(jù)泰勒公式我們把函數(shù) 在點 x 處進(jìn)行泰勒的二階展開，可得到如下等式：

我們把 視為 視為 ，故可以將目標(biāo)函數(shù)寫為：

其中 為損失函數(shù)的一階導(dǎo)， 為損失函數(shù)的二階導(dǎo)，注意這里的求導(dǎo)是對 求導(dǎo)。

我們以平方損失函數(shù)為例：

則：

由于在第 t 步時 其實是一個已知的值，所以 是一個常數(shù)，其對函數(shù)的優(yōu)化不會產(chǎn)生影響，因此目標(biāo)函數(shù)可以寫成：

所以我們只需要求出每一步損失函數(shù)的一階導(dǎo)和二階導(dǎo)的值（由于前一步的 是已知的，所以這兩個值就是常數(shù)），然后最優(yōu)化目標(biāo)函數(shù)，就可以得到每一步的 f(x) ，最后根據(jù)加法模型得到一個整體模型。

1.1.2 基于決策樹的目標(biāo)函數(shù)

我們知道 Xgboost 的基模型不僅支持決策樹，還支持線性模型，這里我們主要介紹基于決策樹的目標(biāo)函數(shù)。

我們可以將決策樹定義為 ，x 為某一樣本，這里的 q(x) 代表了該樣本在哪個葉子結(jié)點上，而 w_q 則代表了葉子結(jié)點取值 w ，所以 就代表了每個樣本的取值 w （即預(yù)測值）。

決策樹的復(fù)雜度可由葉子數(shù) T 組成，葉子節(jié)點越少模型越簡單，此外葉子節(jié)點也不應(yīng)該含有過高的權(quán)重 w （類比 LR 的每個變量的權(quán)重），所以目標(biāo)函數(shù)的正則項可以定義為：

即決策樹模型的復(fù)雜度由生成的所有決策樹的葉子節(jié)點數(shù)量，和所有節(jié)點權(quán)重所組成的向量的 范式共同決定。

這張圖給出了基于決策樹的 XGBoost 的正則項的求解方式。

我們設(shè) 為第 j 個葉子節(jié)點的樣本集合，故我們的目標(biāo)函數(shù)可以寫成：

第二步到第三步可能看的不是特別明白，這邊做些解釋：第二步是遍歷所有的樣本后求每個樣本的損失函數(shù)，但樣本最終會落在葉子節(jié)點上，所以我們也可以遍歷葉子節(jié)點，然后獲取葉子節(jié)點上的樣本集合，最后在求損失函數(shù)。即我們之前樣本的集合，現(xiàn)在都改寫成葉子結(jié)點的集合，由于一個葉子結(jié)點有多個樣本存在，因此才有了 和 這兩項， 為第 j 個葉子節(jié)點取值。

為簡化表達(dá)式，我們定義 ，則目標(biāo)函數(shù)為：

這里我們要注意 和 是前 t-1 步得到的結(jié)果，其值已知可視為常數(shù)，只有最后一棵樹的葉子節(jié)點 不確定，那么將目標(biāo)函數(shù)對 求一階導(dǎo)，并令其等于 0 ，則可以求得葉子結(jié)點 j 對應(yīng)的權(quán)值：

所以目標(biāo)函數(shù)可以化簡為：

上圖給出目標(biāo)函數(shù)計算的例子，求每個節(jié)點每個樣本的一階導(dǎo)數(shù) 和二階導(dǎo)數(shù) ，然后針對每個節(jié)點對所含樣本求和得到的 和 ，最后遍歷決策樹的節(jié)點即可得到目標(biāo)函數(shù)。

1.1.3 最優(yōu)切分點劃分算法

在決策樹的生長過程中，一個非常關(guān)鍵的問題是如何找到葉子的節(jié)點的最優(yōu)切分點，Xgboost 支持兩種分裂節(jié)點的方法——貪心算法和近似算法。

1）貪心算法

1. 從深度為 0 的樹開始，對每個葉節(jié)點枚舉所有的可用特征；
2. 針對每個特征，把屬于該節(jié)點的訓(xùn)練樣本根據(jù)該特征值進(jìn)行升序排列，通過線性掃描的方式來決定該特征的最佳分裂點，并記錄該特征的分裂收益；
3. 選擇收益最大的特征作為分裂特征，用該特征的最佳分裂點作為分裂位置，在該節(jié)點上分裂出左右兩個新的葉節(jié)點，并為每個新節(jié)點關(guān)聯(lián)對應(yīng)的樣本集
4. 回到第 1 步，遞歸執(zhí)行到滿足特定條件為止

那么如何計算每個特征的分裂收益呢？

假設(shè)我們在某一節(jié)點完成特征分裂，則分列前的目標(biāo)函數(shù)可以寫為：

分裂后的目標(biāo)函數(shù)為：

則對于目標(biāo)函數(shù)來說，分裂后的收益為：

注意該特征收益也可作為特征重要性輸出的重要依據(jù)。

對于每次分裂，我們都需要枚舉所有特征可能的分割方案，如何高效地枚舉所有的分割呢？

我假設(shè)我們要枚舉所有 x < a 這樣的條件，對于某個特定的分割點 a 我們要計算 a 左邊和右邊的導(dǎo)數(shù)和。

我們可以發(fā)現(xiàn)對于所有的分裂點 a，我們只要做一遍從左到右的掃描就可以枚舉出所有分割的梯度和 和 。然后用上面的公式計算每個分割方案的分?jǐn)?shù)就可以了。

2）近似算法

貪婪算法可以的到最優(yōu)解，但當(dāng)數(shù)據(jù)量太大時則無法讀入內(nèi)存進(jìn)行計算，近似算法主要針對貪婪算法這一缺點給出了近似最優(yōu)解。

對于每個特征，只考察分位點可以減少計算復(fù)雜度。

該算法會首先根據(jù)特征分布的分位數(shù)提出候選劃分點，然后將連續(xù)型特征映射到由這些候選點劃分的桶中，然后聚合統(tǒng)計信息找到所有區(qū)間的最佳分裂點。

在提出候選切分點時有兩種策略：

• Global：學(xué)習(xí)每棵樹前就提出候選切分點，并在每次分裂時都采用這種分割；
• Local：每次分裂前將重新提出候選切分點。

直觀上來看，Local 策略需要更多的計算步驟，而 Global 策略因為節(jié)點沒有劃分所以需要更多的候選點。

下圖給出不同種分裂策略的 AUC 變換曲線，橫坐標(biāo)為迭代次數(shù)，縱坐標(biāo)為測試集 AUC，eps 為近似算法的精度，其倒數(shù)為桶的數(shù)量。

我們可以看到 Global 策略在候選點數(shù)多時（eps 小）可以和 Local 策略在候選點少時（eps 大）具有相似的精度。此外我們還發(fā)現(xiàn)，在 eps 取值合理的情況下，分位數(shù)策略可以獲得與貪婪算法相同的精度。

• 第一個 for 循環(huán)：對特征 k 根據(jù)該特征分布的分位數(shù)找到切割點的候選集合 。XGBoost 支持 Global 策略和 Local 策略。
• 第二個 for 循環(huán)：針對每個特征的候選集合，將樣本映射到由該特征對應(yīng)的候選點集構(gòu)成的分桶區(qū)間中，即 ，對每個桶統(tǒng)計 G,H 值，最后在這些統(tǒng)計量上尋找最佳分裂點。

下圖給出近似算法的具體例子，以三分位為例：

根據(jù)樣本特征進(jìn)行排序，然后基于分位數(shù)進(jìn)行劃分，并統(tǒng)計三個桶內(nèi)的 G,H 值，最終求解節(jié)點劃分的增益。