作者 | Ray
XGBoost是boosting算法的其中一種。Boosting算法的思想是將許多弱分類器集成在一起形成一個強分類器。因為XGBoost是一種提升樹模型，所以它是將許多樹模型集成在一起，形成一個很強的分類器。而所用到的樹模型則是CART迴歸樹模型。講解其原理前，先講解一下CART迴歸樹。
一、CART迴歸樹
CART迴歸樹是假設樹為二叉樹，通過不斷將特徵進行分裂。比如當前樹結點是基於第j個特徵值進行分裂的，設該特徵值小於s的樣本劃分為左子樹，大於s的樣本劃分為右子樹。
而CART迴歸樹實質上就是在該特徵維度對樣本空間進行劃分，而這種空間劃分的優化是一種NP難問題，因此，在決策樹模型中是使用啟發式方法解決。典型CART迴歸樹產生的目標函數為：
因此，當我們為了求解最優的切分特徵j和最優的切分點s，就轉化為求解這麼一個目標函數：
所以我們只要遍歷所有特徵的的所有切分點，就能找到最優的切分特徵和切分點。最終得到一棵迴歸樹。
二、XGBoost算法思想
該算法思想就是不斷地添加樹，不斷地進行特徵分裂來生長一棵樹，每次添加一個樹，其實是學習一個新函數，去擬合上次預測的殘差。當我們訓練完成得到k棵樹，我們要預測一個樣本的分數，其實就是根據這個樣本的特徵，在每棵樹中會落到對應的一個葉子節點，每個葉子節點就對應一個分數，最後只需要將每棵樹對應的分數加起來就是該樣本的預測值。
注：w_q(x)為葉子節點q的分數，f(x)為其中一棵迴歸樹
如下圖例子，訓練出了2棵決策樹，小孩的預測分數就是兩棵樹中小孩所落到的結點的分數相加。爺爺的預測分數同理。
三、XGBoost原理
XGBoost目標函數定義為：
目標函數由兩部分構成，第一部分用來衡量預測分數和真實分數的差距，另一部分則是正則化項。正則化項同樣包含兩部分，T表示葉子結點的個數，w表示葉子節點的分數。γ可以控制葉子結點的個數，λ可以控制葉子節點的分數不會過大，防止過擬合。
正如上文所說，新生成的樹是要擬合上次預測的殘差的，即當生成t棵樹後，預測分數可以寫成：
同時，可以將目標函數改寫成：
很明顯，我們接下來就是要去找到一個f_t能夠最小化目標函數。XGBoost的想法是利用其在f_t=0處的泰勒二階展開近似它。所以，目標函數近似為：
其中g_i為一階導數，h_i為二階導數：
由於前t-1棵樹的預測分數與y的殘差對目標函數優化不影響，可以直接去掉。簡化目標函數為：
上式是將每個樣本的損失函數值加起來，我們知道，每個樣本都最終會落到一個葉子結點中，所以我們可以將所以同一個葉子結點的樣本重組起來，過程如下圖：
因此通過上式的改寫，我們可以將目標函數改寫成關於葉子結點分數w的一個一元二次函數，求解最優的w和目標函數值就變得很簡單了，直接使用頂點公式即可。因此，最優的w和目標函數公式為
四、分裂結點算法
在上面的推導中，我們知道了如果我們一棵樹的結構確定了，如何求得每個葉子結點的分數。但我們還沒介紹如何確定樹結構，即每次特徵分裂怎麼尋找最佳特徵，怎麼尋找最佳分裂點。
正如上文說到，基於空間切分去構造一顆決策樹是一個NP難問題，我們不可能去遍歷所有樹結構，因此，XGBoost使用了和CART迴歸樹一樣的想法，利用貪婪算法，遍歷所有特徵的所有特徵劃分點，不同的是使用上式目標函數值作為評價函數。具體做法就是分裂後的目標函數值比單子葉子節點的目標函數的增益，同時為了限制樹生長過深，還加了個閾值，只有當增益大於該閾值才進行分裂。
同時可以設置樹的最大深度、當樣本權重和小於設定閾值時停止生長去防止過擬合。
五、Shrinkage and Column Subsampling
XGBoost還提出了兩種防止過擬合的方法：Shrinkage and Column Subsampling。Shrinkage方法就是在每次迭代中對樹的每個葉子結點的分數乘上一個縮減權重η，這可以使得每一棵樹的影響力不會太大，留下更大的空間給後面生成的樹去優化模型。Column Subsampling類似於隨機森林中的選取部分特徵進行建樹。其可分為兩種，一種是按層隨機採樣，在對同一層內每個結點分裂之前，先隨機選擇一部分特徵，然後只需要遍歷這部分的特徵，來確定最優的分割點。另一種是隨機選擇特徵，則建樹前隨機選擇一部分特徵然後分裂就只遍歷這些特徵。一般情況下前者效果更好。
六、近似算法
對於連續型特徵值，當樣本數量非常大，該特徵取值過多時，遍歷所有取值會花費很多時間，且容易過擬合。因此XGBoost思想是對特徵進行分桶，即找到l個劃分點，將位於相鄰分位點之間的樣本分在一個桶中。在遍歷該特徵的時候，只需要遍歷各個分位點，從而計算最優劃分。從算法偽代碼中該流程還可以分為兩種，全局的近似是在新生成一棵樹之前就對各個特徵計算分位點並劃分樣本，之後在每次分裂過程中都採用近似劃分，而局部近似就是在具體的某一次分裂節點的過程中採用近似算法。
七、針對稀疏數據的算法（缺失值處理）
當樣本的第i個特徵值缺失時，無法利用該特徵進行劃分時，XGBoost的想法是將該樣本分別劃分到左結點和右結點，然後計算其增益，哪個大就劃分到哪邊。
八、XGBoost的優點
之所以XGBoost可以成為機器學習的大殺器，廣泛用於數據科學競賽和工業界，是因為它有許多優點：
1.使用許多策略去防止過擬合，如：正則化項、Shrinkage and Column Subsampling等。
2. 目標函數優化利用了損失函數關於待求函數的二階導數
3.支持並行化，這是XGBoost的閃光點，雖然樹與樹之間是串行關係，但是同層級節點可並行。具體的對於某個節點，節點內選擇最佳分裂點，候選分裂點計算增益用多線程並行。訓練速度快。
4.添加了對稀疏數據的處理。
5.交叉驗證，early stop，當預測結果已經很好的時候可以提前停止建樹，加快訓練速度。
6.支持設置樣本權重，該權重體現在一階導數g和二階導數h，通過調整權重可以去更加關注一些樣本。
參考文獻：
[1] https://arxiv.org/pdf/1603.02754v1.pdf
[2] https://zhuanlan.zhihu.com/p/26214650
[3] http://matafight.github.io/2017/03/14/XGBoost-%E7%AE%80%E4%BB%8B/
閱讀更多 人工智能遇見磐創 的文章
