作者 |梁云1991

一、XGBoost和GBDT

xgboost是一種集成學習算法，屬于3類常用的集成方法(bagging,boosting,stacking)中的boosting算法類別。它是一個加法模型，基模型一般選擇樹模型，但也可以選擇其它類型的模型如邏輯回歸等。

xgboost屬于梯度提升樹(GBDT)模型這個范疇，GBDT的基本想法是讓新的基模型（GBDT以CART分類回歸樹為基模型）去擬合前面模型的偏差，從而不斷將加法模型的偏差降低。相比于經典的GBDT，xgboost做了一些改進，從而在效果和性能上有明顯的提升（劃重點面試常考）。第一，GBDT將目標函數泰勒展開到一階，而xgboost將目標函數泰勒展開到了二階。保留了更多有關目標函數的信息，對提升效果有幫助。第二，GBDT是給新的基模型尋找新的擬合標簽（前面加法模型的負梯度），而xgboost是給新的基模型尋找新的目標函數（目標函數關于新的基模型的二階泰勒展開）。第三，xgboost加入了和葉子權重的L2正則化項，因而有利于模型獲得更低的方差。第四，xgboost增加了自動處理缺失值特征的策略。通過把帶缺失值樣本分別劃分到左子樹或者右子樹，比較兩種方案下目標函數的優劣，從而自動對有缺失值的樣本進行劃分，無需對缺失特征進行填充預處理。

此外，xgboost還支持候選分位點切割，特征并行等，可以提升性能。

二、XGBoost原理概述

下面從假設空間，目標函數，優化算法3個角度對xgboost的原理進行概括性的介紹。

1，假設空間

2，目標函數

3，優化算法

基本思想：貪心法，逐棵樹進行學習，每棵樹擬合之前模型的偏差。

三、第t棵樹學什么？

要完成構建xgboost模型，我們需要確定以下一些事情。

1，如何boost? 如果已經得到了前面t-1棵樹構成的加法模型，如何確定第t棵樹的學習目標？

2，如何生成樹？已知第t棵樹的學習目標的前提下，如何學習這棵樹？具體又包括是否進行分裂？選擇哪個特征進行分裂？選擇什么分裂點位？分裂的葉子節點如何取值？

我們首先考慮如何boost的問題，順便解決分裂的葉子節點如何取值的問題。

四、如何生成第t棵樹？

xgboost采用二叉樹，開始的時候，全部樣本都在一個葉子節點上。然后葉子節點不斷通過二分裂，逐漸生成一棵樹。

xgboost使用levelwise的生成策略，即每次對同一層級的全部葉子節點嘗試進行分裂。對葉子節點分裂生成樹的過程有幾個基本的問題：是否要進行分裂？選擇哪個特征進行分裂？在特征的什么點位進行分裂？以及分裂后新的葉子上取什么值？葉子節點的取值問題前面已經解決了。我們重點討論幾個剩下的問題。

1，是否要進行分裂？

根據樹的剪枝策略的不同，這個問題有兩種不同的處理。如果是預剪枝策略，那么只有當存在某種分裂方式使得分裂后目標函數發生下降，才會進行分裂。但如果是后剪枝策略，則會無條件進行分裂，等樹生成完成后，再從上而下檢查樹的各個分枝是否對目標函數下降產生正向貢獻從而進行剪枝。xgboost采用預剪枝策略，只有分裂后的增益大于0才會進行分裂。

2，選擇什么特征進行分裂？

xgboost采用特征并行的方法進行計算選擇要分裂的特征，即用多個線程，嘗試把各個特征都作為分裂的特征，找到各個特征的最優分割點，計算根據它們分裂后產生的增益，選擇增益最大的那個特征作為分裂的特征。

3，選擇什么分裂點位？

xgboost選擇某個特征的分裂點位的方法有兩種，一種是全局掃描法，另一種是候選分位點法。

全局掃描法將所有樣本該特征的取值按從小到大排列，將所有可能的分裂位置都試一遍，找到其中增益最大的那個分裂點，其計算復雜度和葉子節點上的樣本特征不同的取值個數成正比。

而候選分位點法是一種近似算法，僅選擇常數個（如256個）候選分裂位置，然后從候選分裂位置中找出最優的那個。