xgboost是Boost（提升）算法家族中的壹員，Boost根本思想在於通過多個簡單的弱分類器，構建出準確率很高的強分類器。簡單地來說，Boost（提升）就是指每壹步我都產生壹個弱預測模型，然後加權累加到總模型中，可以用於回歸和分類問題。如果每壹步的弱預測模型生成都是依據損失函數的梯度方向，則稱之為梯度提升(Gradient boosting)，這樣若幹步以後就可以達到逼近損失函數局部最小值的目標。
boosting集成學習，由多個相關聯的決策樹聯合決策，什麽叫相關聯，舉個例子，有壹個樣本[數據->標簽]是[(2，4，5)-> 4]，第壹棵決策樹用這個樣本訓練得預測為3.3，那麽第二棵決策樹訓練時的輸入，這個樣本就變成了[(2，4，5)-> 0.7]，也就是說，下壹棵決策樹輸入樣本會與前面決策樹的訓練和預測相關。其中，0.7是模型預測和樣本標記的差，稱為殘差。我們每次要學習的目標是上次學習的殘差，直到殘差小到滿足我們的要求或其他終止條件。這個殘差就是壹個加預測值後能得真實值的累加量。
上面的例子，如果第二次直接預測得到0.7，並不壹定好，因為每次走壹小步逐漸逼近結果的效果，要比每次邁壹大步很快逼近結果的方式更容易避免過擬合。換句話說我們思想不完全信任每壹個棵殘差樹，我們認為每棵樹只學到了真理的壹小部分，累加的時候只累加壹小部分，只有通過多學幾棵樹才能彌補不足。
與之對比的是random forest（隨機森林）算法，各個決策樹是獨立的、每個決策樹在樣本堆裏隨機選壹批樣本，隨機選壹批特征進行獨立訓練，各個決策樹之間沒有啥毛線關系。
xgboost本質上就是k個CART樹，k是壹個正整數。
CART樹也叫分類與回歸樹，是壹種決策樹，既能做分類任務也能做回歸任務。分類樹的輸出是樣本的類別， 回歸樹的輸出是壹個實數（連續型變量）。
回歸樹的運行流程與分類樹基本類似，但有以下兩點不同之處：
對於回歸問題，我們常用的損失函數是MSE（均方誤差），即：
對於分類問題，我們常用的損失函數是對數損失函數：
前面提到，xgboost是具有k個CART樹的集成學習算法，那麽問題來了，我們應該怎麽得到這k個樹，k又是多少呢？（註意：不是隨機得到k個樹，是壹個壹個來，後壹個依賴於前壹個）
在我們壹顆接著壹顆樹的構建過程中，我們的目標是：預測誤差盡量小，葉子節點盡量少，節點數值盡量不極端。第壹個目標很清晰，而第二個目標的原因是因為樹的復雜度越低，泛化能力越強，在後面我們會知道葉子節點數量是樹的復雜度計算中的壹個考量，葉子節點數越多，樹越復雜。節點數值盡量不極端指的是某棵樹對壹個樣本的預測值相對於其它樹對這個樣本的預測值相差比較大，比如某個樣本label數值為4，那麽第壹個回歸樹預測3，第二個預測為1；另外壹組回歸樹，壹個預測2，壹個預測2，那麽傾向後壹種，為什麽呢？前壹種情況，第壹棵樹學的太多，太接近4，也就意味著有較大的過擬合的風險。
生成決策樹：決策樹算法相信大家都比較熟悉了，還不清楚的讀者請先了解壹下決策樹算法。在xgboost中，生成決策樹時，劃分屬性的方式如下：
為了更好的解釋xgboost算法，我們必須定義壹些公式了。
首先是模型的預測：
模型的目標函數：
綜上，我們可以將損失函數用以下函數表示：
但是，損失函數壹定是二次函數嗎？如果不是，就泰勒展開成二次，簡單粗暴。
它背後的思路就是在損失函數上執行梯度下降，然後用基學習器對其進行擬合。當梯度為負時，我們稱它為偽殘差，因為它們依然能間接幫助我們最小化目標函數。
建樹的過程中，在以下情況下完成這棵樹的創建：
（1）當引入的分裂帶來的增益小於壹個閥值的時候，我們可以剪掉這個分裂，所以並不是每壹次分裂loss function整體都會增加的，有點預剪枝的意思。
（2）當樹達到最大深度時則停止建立決策樹，設置壹個超參數max_depth，樹太深很容易出現的情況學習局部樣本，過擬合。
（3）當樣本權重和小於設定閾值時則停止建樹。
1）將樹模型的復雜度加入到正則項中，來避免過擬合，因此泛化性能會好於GBDT。XGBoost的正則項會懲罰具有多個葉子節點的樹結構。
2）損失函數是用泰勒展開式展開的，同時用到了壹階導和二階導，可以加快優化速度。
3）和GBDT只支持CART作為基分類器之外，還支持線性分類器，在使用線性分類器的時候可以使用L1，L2正則化。
4）引進了特征子采樣，像RandomForest那樣，這種方法既能降低過擬合，還能減少計算。
5）在尋找最佳分割點時，考慮到傳統的貪心算法效率較低，實現了壹種近似貪心算法，用來加速和減小內存消耗，除此之外還考慮了稀疏數據集和缺失值的處理，對於特征的值有缺失的樣本，XGBoost依然能自動找到其要分裂的方向。
6）XGBoost支持並行處理，XGBoost的並行不是在模型上的並行，而是在特征上的並行，將特征列排序後以block的形式存儲在內存中，在後面的叠代中重復使用這個結構。這個block也使得並行化成為了可能，其次在進行節點分裂時，計算每個特征的增益，最終選擇增益最大的那個特征去做分割，那麽各個特征的增益計算就可以開多線程進行。