xgboost分類_XGBoost (eXtreme Gradient Boosting)可擴充的提升樹系統

Xgboost (eXtreme Gradient Boosting)是大規模并行boosted tree的工具。Xgboost演算法是經曆以下的演算法演化而來，後續文章将逐一介紹個演算法

• Bagging演化至Boosting
• Boosting演化至Gradient boosting(GB)
• Gradient boosting(GB)和Decision Tree(DT)演化至Gradient Boosting Decision Tree(GBDT)
• Gradient Boosting Decision Tree(GBDT)演化至eXtreme Gradient Boosting(Xgboost)

Bagging原理

Bagging的概念就是從訓練資料中随機抽取(抽後放回，稱為bootstrap)，建立多組訓練樣本，訓練多組分類器(可自己設定要多少個分類器)，每個分類器的權重一緻最後透過投票方式(Majority vote)得到最終結果。

＊Bagging的優點在於原始訓練樣本中有噪聲資料(不好的資料)，透過Bagging抽樣就有機會不讓有噪聲資料被訓練到，是以可以降低模型的不穩定性

Boosting原理

Boosting概念是，對一份資料，建立M個模型（比如分類），一般選擇的模型比較簡單，稱為弱分類器(weak learner)

每次分類都将上一次分錯的資料權重提高一點再進行分類

，這樣最終得到的分類器在測試資料與訓練資料上都可以得到比較好的成績。

Boosting的公式如下：

Boosting的公式，每次都提高分類錯誤的權重

＊Boosting将注意力集中在分類錯誤的資料上，是以Boosting對訓練資料的噪聲非常敏感，如果一筆訓練資料噪聲資料很多，那後面分類器都會集中在進行噪聲資料上分類，反而會影響最終的分類性能。

GB(Gradient boosting)原理

Gradient Boosting是一種Boosting的方法，主要的概念是讓每次建立模型是能夠逐漸讓損失函數(loss function)持續下降，代表模型不斷在改進，而最好的方式就是讓損失函數在其梯度（Gradient)的方向上下降。

舉例:

1. Input為ｘ、Output為y
2. 建立一個簡單一層的回歸樹預測模型F(x)，Ｆ(x)預測出來的值與真實值y的差額為Residual
3. 為了提升F(X)的預測能力，再透過Input為ｘ、output為Residual建立一個h(x)
4. 是以得到了新的模型為Ｈ(x) = F(x) + h(x)，并祈望預測能力比Ｆ(x)好
5. 重複2-4的方法......
6. 可以得到F(x) + h(x) + n(x) + g(x).....的預測模型

Gradient Descent 是一個在最佳化領域相當常見的疊代方法，用于尋找「可微分函數」的局部最小值，它的做法是這樣的：

1. 假設我們要最佳化的目标函數是 L(x)，例如要找 L(x) 的最小值
2. 随機選取一個起始點，例如從 a 出發
3. 從 a 沿着 −∇L(a)走一小步，即 a−γ∇L(a)，此處的 ∇L(a) 代表的是 L 在 a 上的 Gradient，那麼對于一個夠小的 γ，此處的函數值将小于等于 L(a)
4. 當有一個夠小的 γ，我們将有L(a)≥L(a−γ∇L(a))
5. 令 a−γ∇L(a) 為新的出發點，重複 3–4
6. 根據這樣的方法，從 a 開始一步一步走（疊代），在 γ 選取适當的情況下，我們可以找到 L(x) 的局部最小值

GB稱為Gradient的原因在于對于每次的Residual進行計算時加入了控制步伐大小的 γ 稱作 Learning Rate，數學原理如下：

1. y和F(x))的MSE為L(y, F(x))= (y−F(x))²
2. 偷改造一下MSE為L(y, F(x))= (y−F(x))² / 2
3. 對F(x)偏微分∂L/∂F = −(y−F)，在使用 MSE Loss 的情況下，Residual 正是 Loss 對 F 的 Gradient 取負号（在 x 處取值）
4. 兩邊同乘負号為y−F=−∂L/∂F
5. 如果把H(x)=F(x)+h(x) 視作對F(x) 的 更新
6. 那麼根據h(x)≈y−F(x)=−∂L/∂F，其實正如上述Gradient Descent 中的第三步，∂L/∂F為一個朝局部最小值移動的一個變動
7. 是以H(x)=F(x)−γ∂L/∂F, 而γ為Learning Rate

DT(Decision Tree)原理

Decision Tree是采用CART (Classification and Regression Trees)算法來進行，執行的步驟為以下兩大步驟：

1. 決策樹生成： 遞歸地建構二叉決策樹的過程，基于訓 練資料集 生成決策樹，生成的決策樹要盡量大。 分類問題 可采用GINI，雙化或有序雙化； 回歸問題 可采用最小二乘偏差（LSD）或最小絕對偏差（LAD）。
2. 決策樹剪枝： 用 驗證資料集 對已生成的樹進行剪枝并選擇最優子樹，這時損失函數最小作為剪枝的标準。

GBDT(Gradient Boosting Decision Tree)原理

GBDT為GB+DT兩大核心組合而成(不論是分類或是回歸問題皆可處裡)。

GBDT的核心就在于，每一棵樹學的是之前所有樹結論和的殘差

，這個

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

。比如A的真實年齡是18歲，但第一棵樹的預測年齡是12歲，差了6歲，即殘差為6歲。那麼在第二棵樹裡我們把A的年齡設為6歲去學習，如果第二棵樹真的能把A分到6歲的葉子節點，那累加兩棵樹的結論就是A的真實年齡；如果第二棵樹的結論是5歲，則A仍然存在1歲的殘差，第三棵樹裡A的年齡就變成1歲，繼續學。這就是Gradient Boosting在GBDT中的意義。

簡單的訓練集隻有4個人，A,B,C,D，他們的年齡分别是14,16,24,26。其中A、B分别是高一和高三學生；C,D分别是應屆畢業生和工作兩年的員工。如果是用一棵傳統的回歸決策樹來訓練，會得到如下圖1所示結果：

現在我們使用GBDT來做這件事，由于資料太少，我們限定葉子節點做多有兩個，即每棵樹都隻有一個分枝，并且限定隻學兩棵樹。我們會得到如下圖2所示結果：

上圖說明如下:

1. 圖左：以20歲為中心建立預測為15歲和25歲的二叉樹，由于A,B年齡較為相近，C,D年齡較為相近，他們被分為兩撥。并計算A,B對15歲的殘差，Ｃ,Ｄ對25歲的殘差，進而得到A,B,C,D的殘差分别為-1,1，-1,1。
2. 圖右：将A,B,C,D的殘差拿至第二棵樹去學習，進行預測在拿到了得到A,B,C,D的殘差為０，即每個人都得到了真實的預測值。

Xgboost(eXtreme Gradient Boosting)原理

Xgboost也是屬于GBDT之中的其中一種，同樣可以應用于分類與回歸問題，gradient boosting 的實作是比較慢的，因為每次都要先構造出一個樹并添加到整個模型序列中。

XGBoost 的特點就是計算速度快，模型表現好，依照

XGBoost: A Scalable Tree Boosting Systemr

說明主要的原因有以下四個原因：

1. Parallelization：訓練時可以用所有的 CPU 核心來并行化建樹。
2. Distributed Computing ：用分布式計算來訓練非常大的模型。
3. Out-of-Core Computing：對于非常大的資料集還可以進行 Out-of-Core Computing。
4. Cache Optimization of data structures and algorithms：更好地利用硬體。

透過以下範例說明Xgboost：

(1) Regression Tree Ensemble 回歸樹內建

建立兩顆樹分别進行預測，并且把兩個樹的誤內插補點加總。接下來分别說明進行GB和DT

(2)GB

*透過公式的推導可以發現Xgboost與GBDT的差異在于Xgboost透過泰勒式二階近似

第t輪的模型預測等于前t-1輪的模型預測y(t-1)加上ft，是以誤差函式項記為l(yi,y(t-1) ft),後面一項為正則化項。在目前步，yi以及y(t-1)都是已知值，模型學習的是ft。

把平方損失函式的一二次項帶入原目标函式，你會發現與之前的損失函式是一緻的 。至于為什麼要這樣展開呢,這裡就是xgboost的特殊，通過這種近似，你可以自定義一些損失函式（隻要保證二階可導），樹分裂的打分函式是基于gi,hi（Gj，Hj ）計算的。

目标函式保留了泰勒展開的二次項

。

(3)DT

從圖中可以看出，xgboost算法中對樹的複雜度項增加了一個L2正則化項，針對每個葉結點的得分增加L2平滑，目的也是為了避免過拟合

經過範例的計算隻需要總結每個葉子上的梯度和二階梯度統計量，然後應用得分公式來獲得品質得分。

xgboost特點（與gbdt對比）

1.傳統GBDT以CART作為基分類器，xgboost還支援線性分類器，這個時候xgboost相當于帶

L1和L2正則化項的邏輯斯蒂回歸（分類問題）或者線性回歸（回歸問題）

2.傳統GBDT在優化時隻用到一階導數資訊，

xgboost則對損失函式進行了二階泰勒展開

，同時用到了一階和二階導數，對損失函數進行了改進。

3.xgboost在損失函式裡加入了正則項，用于控制模型的複雜度。正則項裡包含了樹的葉子節點個數、每個葉子節點上輸出的score的L2的平方和。從Bias-variance tradeoff角度，正則項降低了模型variance，使學習出來的模型更加簡單，防止過拟合，這也是xgboost優于傳統GBDT的一個特性

4.shrinkage and column subsampling

（1）shrinkage縮減類似于學習速率，在每一步tree boosting之後增加了一個引數n（權重），通過這種方式來

減小每棵樹的影響力

，給後面的樹提供空間去優化模型。

（2）column subsampling列(特征)抽樣，

防止過拟合

的效果比傳統的行抽樣還好，并且有利于

并行化處理演算法

。

5.split finding algorithms(劃分點查詢演算法)

（1）exact greedy algorithm—貪心演算法擷取最優切分點

（2）approximate algorithm—近似演算法，提出了候選分割點概念，先通過直方圖演算法獲得候選分割點的分布情況，然後根據候選分割點将連續的特征資訊對映到不同的buckets中，并統計彙總資訊。

（3）Weighted Quantile Sketch—分散式權重直方圖演算法

*這裡的演算法(2)、(3)是為了解決資料無法一次載入記憶體或者在分散式情況下演算法(1)效率低的問題，說明如下：

可并行的近似直方圖演算法。樹節點在進行分裂時，我們需要計算每個特征的每個分割點對應的增益，即用貪心法列舉所有可能的分割點。當資料無法一次載入記憶體或者在分散式情況下，貪心演算法效率就會變得很低，是以xgboost還提出了一種可并行的近似直方圖演算法，用于高效地生成候選的分割點。

6.對缺失值的處理。對于特征的值有缺失的樣本，xgboost可以自動學習出它的分裂方向(稀疏感覺演算法)

7.Built-in Cross-Validation（内建交叉驗證)

8.continue on Existing Model（接着已有模型學習）

9.High Flexibility（高靈活性）

10.并行化處理—系統設計模組,塊結構設計等

xgboost還設計了快取記憶體壓縮感覺演算法，這是系統設計模組的效率提升。當梯度統計不适合于處理器快取記憶體和快取記憶體丢失時，會大大減慢切分點查詢演算法的速度。

（1）針對 exact greedy algorithm采用快取感覺預取演算法

（2）針對 approximate algorithms選擇合适的塊大小

參考資料:

機器學習中的數學(3)-模型組合(Model Combining)之Boosting與Gradient Boosting

CART 分類與回歸樹

https://www.zhihu.com/question/41354392/answer/98658997

A Kaggle Master Explains Gradient Boosting

https://blog.csdn.net/w28971023/article/details/8240756

https://www.kdd.org/kdd2016/papers/files/rfp0697-chenAemb.pdf

https://medium.com/@chih.sheng.huang821/%E6%A9%9F%E5%99%A8%E5%AD%B8%E7%BF%92-ensemble-learning%E4%B9%8Bbagging-boosting%E5%92%8Cadaboost-af031229ebc3

https://codertw.com/%E7%A8%8B%E5%BC%8F%E8%AA%9E%E8%A8%80/635146/