快捷導(dǎo)航

一篇文章帶你了解XGBoost算法

更新時間：2021年08月11日 10:41:24 作者：mantch

XGBoost全名叫（eXtreme Gradient Boosting）極端梯度提升，經(jīng)常被用在一些比賽中，其效果顯著。它是大規(guī)模并行boosted tree的工具，它是目前最快最好的開源boosted tree工具包

1. 什么是XGBoost

XGBoost是陳天奇等人開發(fā)的一個開源機器學(xué)習(xí)項目，高效地實現(xiàn)了GBDT算法并進行了算法和工程上的許多改進，被廣泛應(yīng)用在Kaggle競賽及其他許多機器學(xué)習(xí)競賽中并取得了不錯的成績。

說到XGBoost，不得不提GBDT(Gradient Boosting Decision Tree)。因為XGBoost本質(zhì)上還是一個GBDT，但是力爭把速度和效率發(fā)揮到極致，所以叫X (Extreme) GBoosted。包括前面說過，兩者都是boosting方法。

關(guān)于GBDT，這里不再提，可以查看我前一篇的介紹，點此跳轉(zhuǎn)。

1.1 XGBoost樹的定義

先來舉個例子，我們要預(yù)測一家人對電子游戲的喜好程度，考慮到年輕和年老相比，年輕更可能喜歡電子游戲，以及男性和女性相比，男性更喜歡電子游戲，故先根據(jù)年齡大小區(qū)分小孩和大人，然后再通過性別區(qū)分開是男是女，逐一給各人在電子游戲喜好程度上打分，如下圖所示。

就這樣，訓(xùn)練出了2棵樹tree1和tree2，類似之前gbdt的原理，兩棵樹的結(jié)論累加起來便是最終的結(jié)論，所以小孩的預(yù)測分?jǐn)?shù)就是兩棵樹中小孩所落到的結(jié)點的分?jǐn)?shù)相加：2 + 0.9 = 2.9。爺爺?shù)念A(yù)測分?jǐn)?shù)同理：-1 + （-0.9）= -1.9。具體如下圖所示：

恩，你可能要拍案而起了，驚呼，這不是跟上文介紹的GBDT乃異曲同工么？

事實上，如果不考慮工程實現(xiàn)、解決問題上的一些差異，XGBoost與GBDT比較大的不同就是目標(biāo)函數(shù)的定義。XGBoost的目標(biāo)函數(shù)如下圖所示：

其中：

紅色箭頭所指向的L 即為損失函數(shù)（比如平方損失函數(shù)：\(l(y_i,y^i)=(y_i-y^i)^2\))紅色方框所框起來的是正則項（包括L1正則、L2正則）紅色圓圈所圈起來的為常數(shù)項對于f(x)，XGBoost利用泰勒展開三項，做一個近似。f(x)表示的是其中一顆回歸樹。

看到這里可能有些讀者會頭暈了，這么多公式，我在這里只做一個簡要式的講解，具體的算法細節(jié)和公式求解請查看這篇博文，講得很仔細：通俗理解kaggle比賽大殺器xgboost

XGBoost的核心算法思想不難，基本就是：

不斷地添加樹，不斷地進行特征分裂來生長一棵樹，每次添加一個樹，其實是學(xué)習(xí)一個新函數(shù)f(x)，去擬合上次預(yù)測的殘差。當(dāng)我們訓(xùn)練完成得到k棵樹，我們要預(yù)測一個樣本的分?jǐn)?shù)，其實就是根據(jù)這個樣本的特征，在每棵樹中會落到對應(yīng)的一個葉子節(jié)點，每個葉子節(jié)點就對應(yīng)一個分?jǐn)?shù)最后只需要將每棵樹對應(yīng)的分?jǐn)?shù)加起來就是該樣本的預(yù)測值。

顯然，我們的目標(biāo)是要使得樹群的預(yù)測值\(y_i^{'}\)盡量接近真實值\(y_i\)，而且有盡量大的泛化能力。類似之前GBDT的套路，XGBoost也是需要將多棵樹的得分累加得到最終的預(yù)測得分（每一次迭代，都在現(xiàn)有樹的基礎(chǔ)上，增加一棵樹去擬合前面樹的預(yù)測結(jié)果與真實值之間的殘差）。

那接下來，我們?nèi)绾芜x擇每一輪加入什么 f 呢？答案是非常直接的，選取一個 f 來使得我們的目標(biāo)函數(shù)盡量最大地降低。這里 f 可以使用泰勒展開公式近似。

實質(zhì)是把樣本分配到葉子結(jié)點會對應(yīng)一個obj，優(yōu)化過程就是obj優(yōu)化。也就是分裂節(jié)點到葉子不同的組合，不同的組合對應(yīng)不同obj，所有的優(yōu)化圍繞這個思想展開。到目前為止我們討論了目標(biāo)函數(shù)中的第一個部分：訓(xùn)練誤差。接下來我們討論目標(biāo)函數(shù)的第二個部分：正則項，即如何定義樹的復(fù)雜度。

1.2 正則項：樹的復(fù)雜度

XGBoost對樹的復(fù)雜度包含了兩個部分：

一個是樹里面葉子節(jié)點的個數(shù)T一個是樹上葉子節(jié)點的得分w的L2模平方（對w進行L2正則化，相當(dāng)于針對每個葉結(jié)點的得分增加L2平滑，目的是為了避免過擬合）

我們再來看一下XGBoost的目標(biāo)函數(shù)（損失函數(shù)揭示訓(xùn)練誤差 + 正則化定義復(fù)雜度）：

\[L(\phi)=\sum_{i}l(y_i^{'}-y_i)+\sum_k\Omega(f_t)\]

正則化公式也就是目標(biāo)函數(shù)的后半部分，對于上式而言，\(y_i^{'}\)是整個累加模型的輸出，正則化項∑kΩ(ft)是則表示樹的復(fù)雜度的函數(shù)，值越小復(fù)雜度越低，泛化能力越強。

1.3 樹該怎么長

很有意思的一個事是，我們從頭到尾了解了xgboost如何優(yōu)化、如何計算，但樹到底長啥樣，我們卻一直沒看到。很顯然，一棵樹的生成是由一個節(jié)點一分為二，然后不斷分裂最終形成為整棵樹。那么樹怎么分裂的就成為了接下來我們要探討的關(guān)鍵。對于一個葉子節(jié)點如何進行分裂，XGBoost作者在其原始論文中給出了一種分裂節(jié)點的方法：枚舉所有不同樹結(jié)構(gòu)的貪心法

不斷地枚舉不同樹的結(jié)構(gòu)，然后利用打分函數(shù)來尋找出一個最優(yōu)結(jié)構(gòu)的樹，接著加入到模型中，不斷重復(fù)這樣的操作。這個尋找的過程使用的就是貪心算法。選擇一個feature分裂，計算loss function最小值，然后再選一個feature分裂，又得到一個loss function最小值，你枚舉完，找一個效果最好的，把樹給分裂，就得到了小樹苗。

總而言之，XGBoost使用了和CART回歸樹一樣的想法，利用貪婪算法，遍歷所有特征的所有特征劃分點，不同的是使用的目標(biāo)函數(shù)不一樣。具體做法就是分裂后的目標(biāo)函數(shù)值比單子葉子節(jié)點的目標(biāo)函數(shù)的增益，同時為了限制樹生長過深，還加了個閾值，只有當(dāng)增益大于該閾值才進行分裂。從而繼續(xù)分裂，形成一棵樹，再形成一棵樹，每次在上一次的預(yù)測基礎(chǔ)上取最優(yōu)進一步分裂/建樹。

1.4 如何停止樹的循環(huán)生成

凡是這種循環(huán)迭代的方式必定有停止條件，什么時候停止呢？簡言之，設(shè)置樹的最大深度、當(dāng)樣本權(quán)重和小于設(shè)定閾值時停止生長以防止過擬合。具體而言，則

當(dāng)引入的分裂帶來的增益小于設(shè)定閥值的時候，我們可以忽略掉這個分裂，所以并不是每一次分裂loss function整體都會增加的，有點預(yù)剪枝的意思，閾值參數(shù)為（即正則項里葉子節(jié)點數(shù)T的系數(shù)）；當(dāng)樹達到最大深度時則停止建立決策樹，設(shè)置一個超參數(shù)max_depth，避免樹太深導(dǎo)致學(xué)習(xí)局部樣本，從而過擬合；樣本權(quán)重和小于設(shè)定閾值時則停止建樹。什么意思呢，即涉及到一個超參數(shù)-最小的樣本權(quán)重和min_child_weight，和GBM的 min_child_leaf 參數(shù)類似，但不完全一樣。大意就是一個葉子節(jié)點樣本太少了，也終止同樣是防止過擬合；

2. XGBoost與GBDT有什么不同

除了算法上與傳統(tǒng)的GBDT有一些不同外，XGBoost還在工程實現(xiàn)上做了大量的優(yōu)化。總的來說，兩者之間的區(qū)別和聯(lián)系可以總結(jié)成以下幾個方面。

GBDT是機器學(xué)習(xí)算法，XGBoost是該算法的工程實現(xiàn)。在使用CART作為基分類器時，XGBoost顯式地加入了正則項來控制模型的復(fù)雜度，有利于防止過擬合，從而提高模型的泛化能力。GBDT在模型訓(xùn)練時只使用了代價函數(shù)的一階導(dǎo)數(shù)信息，XGBoost對代價函數(shù)進行二階泰勒展開，可以同時使用一階和二階導(dǎo)數(shù)。傳統(tǒng)的GBDT采用CART作為基分類器，XGBoost支持多種類型的基分類器，比如線性分類器。傳統(tǒng)的GBDT在每輪迭代時使用全部的數(shù)據(jù)，XGBoost則采用了與隨機森林相似的策略，支持對數(shù)據(jù)進行采樣。傳統(tǒng)的GBDT沒有設(shè)計對缺失值進行處理，XGBoost能夠自動學(xué)習(xí)出缺失值的處理策略。

3. 為什么XGBoost要用泰勒展開，優(yōu)勢在哪里？

XGBoost使用了一階和二階偏導(dǎo), 二階導(dǎo)數(shù)有利于梯度下降的更快更準(zhǔn). 使用泰勒展開取得函數(shù)做自變量的二階導(dǎo)數(shù)形式, 可以在不選定損失函數(shù)具體形式的情況下, 僅僅依靠輸入數(shù)據(jù)的值就可以進行葉子分裂優(yōu)化計算, 本質(zhì)上也就把損失函數(shù)的選取和模型算法優(yōu)化/參數(shù)選擇分開了. 這種去耦合增加了XGBoost的適用性, 使得它按需選取損失函數(shù), 可以用于分類, 也可以用于回歸。