xgboost分類_解讀論文 《XGBoost: A Scalable Tree Boosting System》

前言

本文是對 <<XGBoost：A Scalable Tree Boosting System>> 的算法解讀。本着最近養成的寫此類文章的習慣，我會延續先介紹 Paper 中涉及到的一些掃盲概念，然後逐漸切入 XGBoost 主要設計思想，以及對公式的詳細解讀，使讀者能對 Paper 中的抽象部分有更深度的了解。

此 Paper 是華人學術明星來自華盛頓大學的 XGBoost 作者本人：陳天奇，在SIGKDD 2016 大會上發表過的論文。在深度學習大火之前的年代 XGBoost 幾乎橫掃了 Kaggle 競賽裡面的大部分的獎項，XGBoost 出于它天生的樹結構設計優勢，也在工業界的分布式計算中得到廣泛應用。在我個人經曆的項目中，樹類模型出于出色的可解釋性，經常被用于 Baseline 模型（比如 feature importance 的存在）。

由于原始論文中涉及到了大量的決策樹（Decision Tree），提升樹（Boosting Tree）等算法的相關的知識，本文第一章會先從一些容易混淆的概念，數學公式和抽象的算法思路入手，使讀者對該論文涉及到的“樹”知識體系有一個大體的認識。然後在第二章、第三章以與論文的相同順序詳細解釋作者提到的三個 Tree Boosting 算法和分裂算法（Split Finding Algorithms）。由于本文除了數學算法上的優化外還涉及到計算機系統方向的優化，這部分内容會在後面做簡單的總結。由于論文後幾章的内容不涉及到抽象的數學和計算機系統優化，考慮到篇幅的關系，不在此贅述，有興趣的朋友可以直接閱讀原文。

1. 基礎概念 1.1 決策樹 & CART

決策樹(Decision Tree）是在已知各種情況發生機率的基礎上，通過構成決策樹來求取淨現值的期望值大于等于零的機率，評價項目風險，判斷其可行性的決策分析方法，是直覺運用機率分析的一種圖解法。由于這種決策分支畫成圖形很像一棵樹的枝幹，故稱決策樹[1]。

決策樹是一種十分常用的分類方法，需要監督學習（Supervised Learning），就是給出一堆樣本，每個樣本都有一組屬性和一個分類結果，通過學習，優化這些樣本得到決策樹，能夠對新的資料給出正确的分類。

在樹分裂（某節點分出新節點）時，使用資訊論中的熵來衡量随機事件的“混亂程度”。随機變量的資訊熵越大，則它的值（内容）能給你補充的資訊量越大。數學上被記為：

。 其中 p(x) 為 X 的機率函數。決策樹本着熵越大分類結果越好的原則，使用資料的次元生成樹。

常見的熵計算有[2]：

• ID3 算法中根據特征選擇和資訊增益評估，每次選擇 資訊增益最大 的特征作為分支标準。
• C4.5 使用“ 增益率 ”（gain ratio）來選擇最優的分支标準
• CART 的分支标準建立在 GINI 指數 上，GINI 值越大表明樣本集合的類别越雜亂

決策樹可宏觀上分為：

分類樹

和

回歸樹

兩類。基本流程都是根據樣本的特征找出門檻值，但是這兩類樹的門檻值衡量 / 計算标準有所不同，是以相對應的損失函數也不同。分類樹選擇門檻值的标準是實作每個分枝都盡可能隻有一個分類，即男性分枝上盡可能多的是男性，女性盡可能少；女性分枝上盡可能多的是女性，男性盡可能少；回歸樹選擇門檻值的标準則是：實作預測值和真實值的最小化均方差。回歸和分類從實作上，分别用不同的方法實作了"動态确定樣本權值"這一目标。

總結：回歸樹是用拟合殘差，分類樹是用錯誤率來調整樣本權值。

1.2 提升樹 1.2.1 基本思想

梯度提升（Gradient Boost）其實隻是一個架構或者設計理念，裡面可以套用不同的算法。其核心思想是，用多個弱分類器（比如生成的子樹）來建構一個強分類器（最終內建出來的樹）。大體流程是首先建立多棵決策樹做內建，再将所有樹的輸出結果（學出的最佳參數）累加起來。或者可以這樣說，每一棵樹（以回歸樹為例）學習的是之前所有樹結論和的

殘差，

這個殘差就是一個加預測值後能得真實值的累加量。

其數學表達式可寫為：

,

其中

為第 k 個棵樹（弱分類器），

為第 k 個決策樹的參數， K 為決策樹的數量。

算法具體步驟如下：

1. 初始化提升樹

   

   = 0
2. 其中 殘差

   

   為目前模型拟合資料的殘差
3. 第 k 步的模型為：

   

   , 其中

   

   為目前的待求的由殘差訓練得出第

   k 棵樹

4. 通過經驗風險極小化确定第 k 個決策樹的參數

   

   ：

   

   其中：對于回歸類的損失函數為

   

   ； 對分類類的損失函數為

   

   ;

   

   為真實值，

   

   為預測值

   

   的另一種寫法。利用這兩種損失函數的性質在求導過程中會給我們帶來很多友善。
5. 最後整理後得出分類樹的損失函數（此處為推導過程，不包括損失函數）：

将損失函數帶入

變成求目标函數最小值問題。疊代方法見圖1。

見到網上很多文章裡把 Gradient Boost 了解成 Gradient Boosting Decision Tree（GBDT），這其實是錯誤的認識，後者嚴格上來講是指疊代梯度決策樹，是 Gradient Boosting Tree 中的一個分類算法。另外與 Boosting 同類的內建模型架構中還有一個叫做 Bagging ，在機器學習訓練過程中和 Boosting 有一定的差別。具體見Bagging vs Boosting。

本文所涉及到的 XGBoost 看名字就知道，是講的 Boosting 的算法。下面小節中我會介紹兩種常見的 Boosting 算法，其中 Paper 中第二章讨論的基礎就是 Gradient Boosting Regression Tree（GBRT），且使用了 CART 作為樹分裂算法，是以後面所涉及到的優化算法例子也是基于它的。

圖1：Boosting Tree 計算過程

1.2.1 提升樹的優化（Gradient Boosting Tree）

上文中的例子，損失函數可以是

平方損失函數

或

指數損失函數

，在此基礎上

Freidman

提出了

梯度提升樹算法(GBT)

。梯度提升樹(GBT)的一個核心思想是

利用損失函數的負梯度在目前模型的值作為殘差的近似值

，本質上是對損失函數進行一階泰勒展開，進而拟合一個回歸樹。

回憶

泰勒展開公式（稍後 XGBoost 會用）：

在

GBT

中損失函數使用

一階泰勒展開公式（

相當于這裡的

）

：

則有：

意思為：要使得損失函數降低，則根據梯度下降的思想讓損失函數對

進行求導，按照負梯度更新改損失函數值，是以才有：

其中對于平方或指數損失函數，就是通常意義上的殘差。對于其他普通函數，殘差是導數的近似值。用于回歸模型時，是

梯度提升回歸樹GBRT；

梯度提升樹用于分類模型時，是

梯度提升決策樹

GBDT

；二者的差別主要是損失函數不同。此處借鑒了GBT、GBDT、GBRT與Xgboost 文章。

1.2.1 疊代梯度回歸樹 (GBRT)

疊代決策樹算法，由多棵決策樹組成，并将所有樹的輸出結果累加起來。且每一棵樹是從之前所有樹的

殘差

中來學習的。GBRT 幾乎可用于所有的回歸問題（線性/非線性），相對logistic regression僅能用于線性回歸，GBRT的适用面非常廣。亦可用于二分類問題（設定門檻值，大于門檻值為正例，反之為負例）。損失函數數學表達式見 1.2 。

1.2.2 疊代梯度決策樹 (GBDT)

GBDT 分類算法在思想上和回歸算法沒有差別，但是由于樣本輸出不是連續的值，而是離散的類别，導緻我們無法直接從輸出類别去拟合類别輸出的誤差。為解決此問題，我們嘗試用類似于邏輯回歸的對數似然損失函數的方法,也就是說我們用的是類别的預測機率值和真實機率值來拟合損失函數。對于對數似然損失函數，我們有二進制分類和多元分類的差別。[3]

2. 從 GDBT 更新到 XGBoost

在第一章節，我用了大量的篇幅介紹了 GBT 的數學推導和工作原理，正是因為在這些理論上才有了 XGBoost ， 在原始論文中作者本着讀者已經了解 GBT 和 Freidman 提出的優化觀點直接切入 XGBoost 話題，導緻了很多初學者一時間無法領悟這麼多容易混淆的概念。

在有了良好的基礎後，我們下面回到論文的主題，對 XGBoost 進行更深度的剖析。原文作者在現有的 GDBT 思路上做了些小改動。注：下文中關于 XGBoost 的講解基于 GBRT 和 CART 算法。

2.1 目标函數添加正則化

由此章節前一部分和我們講得基本吻合，是以此處隻會對提到的數學符号做一下解釋。

給定 XGBoost 的目标函數：

； 其中

• 公式中

  

  是 1.2.1 章節中提到的損失函數，限制為可微、且為凸函數

• 

  表示對模型複雜度的懲罰項（正則項）
• 在懲罰項中

  

  、

  

  表示懲罰系數

• 

  表示給定一顆樹的葉節點數
• 決策樹定義為

  

  ，

  

  為某一樣本，這裡的

  

  表示該樣本所在的葉子結點，

  

  為葉子結點權重

  

  ，是以得出

  

  為每個樣本的取值

  

  （即預測值）。是以

  

  表示每顆樹葉節點上的輸出分數的平方(相當于L2正則)

從目标函數的定義可以看出 XGBoost 的懲罰項對模型複雜度考慮了每顆樹的葉節點個數，以及每顆樹葉節點輸出得分值得平方和。作者強調與 Regularized greedy forest[4] 相比，這個懲罰項更便于做并行化計算的優化。

2.2 梯度提升樹

在通常的模型中針對這類目标函數可以使用梯度下降的方式進行優化，但注意到

表示的是一顆樹，而非一個數值型的向量，是以不能使用梯度下降的方式去優化該目标函數。在此作者提出了使用

前向分步算法

（additive manner）。

目标函數為：

其中第 i 個樣本在第 t 顆樹的預測值 (

)等于樣本 i 在前 t-1 棵樹的預測值(

) 加目前第 t 顆樹預測值(

) 公式表達為：

對于該函數的優化，在 XGBoost 中使用了我們前面提到的泰勒展開式，與 GDBT 不同的是 XGBoost 使用了泰勒二次展開式。

使

則有：

這裡是針對

的求導，是以可以将

部分看成常數去掉。

得出簡化後的損失函數：

定義集合

為樹的第 j 個葉節點上的所有樣本點的集合，即給定一顆樹，所有按照決策規則被劃分到第 j 個葉節點的樣本集合。根據模型複雜度懲罰項的定義有：

第二步推導第三步過程請回顧 2.1 章節公式，

代表每個樣本的損失函數，但這些值最終都會被歸為某個葉子節點，且有

；

表示該樣本所在的葉子結點；

表示第

個葉子節點取。是以也可以把葉子節點上所有損失累加起來，效果和 2.1 的損失函數效果是一樣的。這裡有可能會思考起來有點抽象，建議把整個 GBDT 計算過程走一遍會更容易了解，推薦閱讀 GDBT 執行個體了解。

如果确定了樹的結構，為了使目标函數最小，可以令其導數為0，解得每個葉節點的最優預測分數為：

将

代入簡化後的目标函數得到最小損失為：

替換：

則有：

用做為得分值評價一顆樹的好壞。這和決策樹中的剪枝是一樣原理，給定一個損失函數，判斷剪枝後,根據損失函數是否減小來決定是否執行剪枝如圖2。

圖2 Structure score calcuation

這裡作者也提出了，通常是不會把所有可能出現的排列組合樹形都枚舉出來。他解決此問題用了

貪心算法

。假設在某節點分裂了左

，右節點

且滿足 如果确定了樹的結構（即q(x)确定），為了使目标函數最小，可以令其導數為0，解得每個葉節點的最有預測分數為：

,

那麼分裂後的 L 可以表示為：

該值越大，說明分裂後能使目标函數減少越多，就越好。此方法被用于 XGBoost 判斷最優特征以及最優切分點（此處借鑒了xgboost的了解），換句話說這個目标函數的值诠釋了

樹結構的好壞

。

2.3 Shrinkage & 列降采樣

作為 Gradient Boosting 算法，作者提出可以使用

• Shrinkage 政策（權重衰減，類似 LSTM）。比如把整個訓練過程看作一個時間序列，離目前樹時間點越靠前的權重對目前權重的累加影響越小，這個衰減就是論文裡的參數

  

  控制的
• 特征降采樣的方法來避免過拟合，隻是這裡的降采樣使用的是 列降采樣 （與随機森林做法一樣），它的另外一個好處是可以友善加速并行化

3. 分裂查找算法

在此作者點出了樹類算法與其他算法（比如求距離，機率）比較頭疼的地方在于：樹的生成/分裂過程。因為每個樹生成的問題都要考慮到兩個問題是：1）按照哪個次元 / 順序組合切 2）如何判斷

最佳切分點

。

圍繞着這兩個問題引出了如下兩個解決方案。

3.1 精确貪心算法

從樹的根節點開始，對每個葉節點枚舉所有的可用特征。此處文中指出：對該節下的資料需令其按特征值進行排序，這樣做可以使計算分裂收益值更加高效，

分裂收益值

計算如下：

然後選擇該輪最大收益值作為

最佳分裂點

，使在該節點行分裂出左右兩個新的葉節點，并重新配置設定新節點上的樣本。至此一個循環結束，繼續按同樣流程遞歸疊代直至滿足條件停止。相應實作步驟在論文中給出了僞代碼，見 3.1 章節 Algorithm 1：Exact Greedy Algorithm for Split Finding。

由于該方法需要窮舉所有分裂可能，可以在特征量大的情況下記憶體是肯定不夠的。對此作者給出了下一個近似值計算方法。

3.2 求近似值算法

為了減少計算作者使用了将連續特征變量按照特征值分布進行分桶操作的方法，這樣隻需要計算每個桶中的統計資訊就可以求出最佳分裂點的最佳分裂收益值。

在确定分裂點時作者提出了兩種方法：

Global、Local

。

Global

表示在生成樹

之前

進行候選切分點（candidate splits）的計算，且在整個計算過程中隻做

一次

操作。在以後的節點劃分時都使用已經提前計算好的候選切分點；

Local

則是在每次節點劃分時才進行候選切分點的計算。經作者實戰經驗，如果想使兩種方法達到逼近

精确貪婪算法

的準确性，需要對 Global 取更多的候選切分點來提高精度。由于 Local 在每次節點劃分時都要計算，是以他們在有些情況下計算量很接近。

這裡作者給出的總結是：Global 适合在取大量切分點下使用； Local 更适用于深度較大的樹結構。具體需要在實際中根據訓練資料自由調整。

3.3 權重分位數略圖（Weighted Quantile Sketch）

為了避免簡單統計名額對定義候選切分點不合理的問題，作者引出了權重分位數略圖的概念。

設資料集

表示每個樣本的第 k 個特征值(

)和二階導數(

)的集合。

定義排名函數

；表示資料集中第 k 個特征值小于 z 的樣本所在比例。

然後根據

,

進行侯選點的選取。

這裡有一個也許讓正常人都覺得很抽象的概念，

為什麼會用二階導數？ 它是怎麼影響樣本權重劃分的？

由于作者隻用一個公式帶過，讓這件事看起來更難以了解。我本人也是借鑒了其他人的推導過程[5]。

具體如下：

反正我自己是想不出來，但看過程無非就是湊個平方差公式。最後在标簽為

的情況下，權重為

。

最後給我這類數學分析基礎較差的愛好者們總結下：綜上所述證明了在求解對樣本點合理切割的問題上，可以用樣本的特征值和其二階導數的關系更好地劃分資料分布範圍！

3.4 稀疏值處理（Sparsity-aware Split Finding）

對于缺失資料作者讓模型自動學習預設的劃分方向。采用的是在每次的切分中，讓缺失值分别被切分到左節點以及右節點，通過計算得分值比較兩種切分方法哪一個更優，則會對每個特征的缺失值都會學習到一個最優的預設切分方向。

4. 總結

以上隻是總結了該論文在數學算法上的分析，另外作者也從計算機系統方向做了大量優化，使模型在訓練中的速度大大提升，同時也可以利用硬碟 IO 處理超大規模資料，甚至優化了緩存。由于這部分和計算機系統更加相關，在此就不做贅述。

對比傳統的 GBDT，XGBoost 在目标函數上加入了懲罰項，使模型的泛化能力大大增強，且對行列支援降采樣，優化了計算速度。

本人不太确定的是：對于特征工程處理缺失值使用讓模型自動學習的方法，也許會造成模型在生産環境中的穩定性造成一定影響，文中作者的隻提到了它在計算速度上的效率，但并未給出模型處理這類稀疏問題的準确性。我從個人之前資料挖掘經驗來看，這種插值方法在真正的生産環境中對模型的穩定性也許會存在一定隐患（比如模型準确率不到一個月就會大打折扣）。不知具體實戰效果如何？不知可否使用傳統的中位數代替？

iris 資料集測試代碼

：

#importing library and segregation of data as train and test using DMatrix 
# Data structure
from sklearn import datasets
from sklearn import metrics
from sklearn.model_selection import train_test_split
import xgboost as xgb

iris = datasets.load_iris() #dataset loading
X = iris.data               #Features stored in X 
y = iris.target             #Class variable

#Splitting dataset into Training (80%) and testing data (20%) using train_test_split
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

# 這裡提前定義了特征名稱，以便之後 feature_importance 能直接顯示特征名，而不是 f{n}
feature_names = ['sepal_len', 'sepal_width', 'petal_len', 'petal_width']

dtrain = xgb.DMatrix(data = X_train, 
                     label = y_train, 
                     feature_names = feature_names)

dtest = xgb.DMatrix(data = X_test, 
                    label = y_test)

param = {
    'max_depth': 3,  # the maximum depth of each tree
    'eta': 0.3,  # the training step for each iteration
    'silent': 1,  # logging mode - quiet
    'objective': 'multi:softprob',  # error evaluation for multiclass training
    'num_class': 3}  # the number of classes that exist in this datset

num_round = 5  # the number of training iterations

bst = xgb.train(param, dtrain, num_round)
y_predict = bst.predict(dtest)
print(metrics.accuracy_score(y_test, y_pred))

bst.dump_model('dump.raw.txt')
           

這個檔案會生成 xgboost 庫在建立樹結構時的具體資訊，包括：

• ID: 每個節點的ID
• Feature: 使用樹分裂的特征，分裂停止于葉子節點
• Split: 分裂時計算出的特征值
• Yes: 分支中下一個節點滿足分裂條件的特征ID
• No: 分支中下一個節點不滿足分裂條件的特征ID
• Missing: 分支中下一個節點用于分裂條件的特征ID，且該特征有缺失值

booster[0]:
0:[petal_len<2.45000005] yes=1,no=2,missing=1
	1:leaf=0.426035523
	2:leaf=-0.218845025
booster[1]:
0:[petal_len<2.45000005] yes=1,no=2,missing=1
	1:leaf=-0.213017777
	2:[petal_width<1.75] yes=3,no=4,missing=3
		3:leaf=0.357142866
		4:leaf=-0.193288609
booster[2]:
0:[petal_len<4.75] yes=1,no=2,missing=1
	1:[petal_width<1.45000005] yes=3,no=4,missing=3
		3:leaf=-0.217894763
		4:leaf=-0.109756112
	2:[petal_width<1.75] yes=5,no=6,missing=5
		5:leaf=0.0878048688
		6:leaf=0.404698014
booster[3]:
0:[petal_len<2.45000005] yes=1,no=2,missing=1
	1:leaf=0.293278694
	2:leaf=-0.195857152
booster[4]:
0:[petal_len<2.45000005] yes=1,no=2,missing=1
	1:leaf=-0.189503655
	2:[petal_len<4.94999981] yes=3,no=4,missing=3
		3:leaf=0.262102395
		4:leaf=-0.163355067
booster[5]:
0:[petal_len<4.75] yes=1,no=2,missing=1
	1:[petal_width<1.45000005] yes=3,no=4,missing=3
		3:leaf=-0.19525367
		4:leaf=-0.0907141864
	2:[petal_len<4.94999981] yes=5,no=6,missing=5
		5:leaf=0.0648387149
		6:leaf=0.284316152
booster[6]:
0:[petal_len<2.45000005] yes=1,no=2,missing=1
	1:leaf=0.234882191
	2:leaf=-0.180683166
booster[7]:
0:[petal_len<2.45000005] yes=1,no=2,missing=1
	1:leaf=-0.173286781
	2:[petal_width<1.6500001] yes=3,no=4,missing=3
		3:leaf=0.210330531
		4:leaf=-0.145057067
booster[8]:
0:[petal_len<4.75] yes=1,no=2,missing=1
	1:[petal_width<1.45000005] yes=3,no=4,missing=3
		3:leaf=-0.179621071
		4:leaf=-0.0728611574
	2:[petal_width<1.75] yes=5,no=6,missing=5
		5:leaf=0.046688173
		6:leaf=0.23004286
booster[9]:
0:[petal_len<2.45000005] yes=1,no=2,missing=1
	1:leaf=0.202377468
	2:leaf=-0.169775575
booster[10]:
0:[petal_len<2.45000005] yes=1,no=2,missing=1
	1:leaf=-0.161111236
	2:[petal_len<4.94999981] yes=3,no=4,missing=3
		3:leaf=0.176073477
		4:leaf=-0.133052737
booster[11]:
0:[petal_len<4.75] yes=1,no=2,missing=1
	1:[petal_width<1.45000005] yes=3,no=4,missing=3
		3:leaf=-0.168202192
		4:leaf=-0.059584748
	2:[petal_len<5.05000019] yes=5,no=6,missing=5
		5:leaf=0.0603878833
		6:leaf=0.202011034
booster[12]:
0:[petal_len<2.45000005] yes=1,no=2,missing=1
	1:leaf=0.18176958
	2:leaf=-0.161522761
booster[13]:
0:[petal_len<2.45000005] yes=1,no=2,missing=1
	1:leaf=-0.151254103
	2:[petal_width<1.75] yes=3,no=4,missing=3
		3:leaf=0.149364129
		4:leaf=-0.133772731
booster[14]:
0:[petal_len<4.75] yes=1,no=2,missing=1
	1:[sepal_width<2.54999995] yes=3,no=4,missing=3
		3:leaf=-0.0491230562
		4:leaf=-0.160760283
	2:[petal_width<1.75] yes=5,no=6,missing=5
		5:leaf=0.0225836635
		6:leaf=0.175175846
           

樹結構可視化：

# visualization
import matplotlib.pyplot as plt

xgb.plot_tree(bst, num_trees=1)
fig = plt.gcf()
fig.set_size_inches(150, 100)
fig.savefig('treeIris.png')

fig.show()
           

特征重要性展示：

from xgboost import plot_importance
from matplotlib import pyplot
plot_importance(bst)
pyplot.show()
           

如圖所示，在樣本量大的情況下我們可以用分布式的方式訓練，在得到結果後通過特征貢獻程度來輔助選擇特征（類似 PCA 的降維操作，不過 XGBoost 是可監督的模型，準确度會更高）。由此可見用此類模型做 Baseline 模型還是有諸多益處的。

如果一定要抱怨，那恐怕隻有超參數過多吧。代碼例子中隻展示了部分超參數，具體見 API。

備注：

這篇文章寫得不是太滿意，因為樹本身不像其他算法那樣隻涉及到算距離，機率的問題，而是用數學表達了一個抽象的樹結構，以及葉子節點資訊等概念。。。 剛剛看會比較難了解其真正的數學意義。以後會慢慢改進對這部分的描述。

推薦閱讀：

阿澤：【機器學習】決策樹（下）——XGBoost、LightGBM（非常詳細）​zhuanlan.zhihu.com

金貴濤：對xgboost的了解​zhuanlan.zhihu.com

XGboost: A Scalable Tree Boosting System論文及源碼導讀​mlnote.com

yyHaker：GBT、GBDT、GBRT與Xgboost​zhuanlan.zhihu.com

參考

1. ^決策樹 https://baike.baidu.com/item/%E5%86%B3%E7%AD%96%E6%A0%91
2. ^決策樹熵計算： https://blog.csdn.net/u010089444/article/details/53241218
3. ^GDBT 詳解 https://zhuanlan.zhihu.com/p/36339161
4. ^RGF https://arxiv.org/pdf/1109.0887.pdf
5. ^權重分位數略圖 https://zhuanlan.zhihu.com/p/75217528