機器學習算法總結(四)--GBDT與XGBOOST - 微笑sun - 部落格園
Boosting方法實際上是采用加法模型與前向分布算法。在上一篇提到的Adaboost算法也可以用加法模型和前向分布算法來表示。以決策樹為基學習器的提升方法稱為提升樹（Boosting Tree）。對分類問題決策樹是CART分類樹，對回歸問題決策樹是CART回歸樹。
1、前向分布算法引入加法模型
在給定了訓練資料和損失函數L(y,f(x)) 的條件下，可以通過損失函數最小化來學習加法模型
然而對于這個問題是個很複雜的優化問題，而且要訓練的參數非常的多，前向分布算法的提出就是為了解決模型的優化問題，其核心思想是因為加法模型是由多各模型相加在一起的，而且在Boosting中模型之間又是有先後順序的，是以可以在執行每一步加法的時候對模型進行優化，那麼每一步隻需要學習一個模型和一個參數，通過這種方式來逐漸逼近全局最優，每一步優化的損失函數：
具體算法流程如下：
1）初始化f0(x)=0；
2）第m次疊代時，極小化損失函數
3）更新模型，則$f_m (x)$：
4）得到最終的加法模型
GBDT是梯度提升決策樹（Gradient Boosting Decision Tree）的簡稱，GBDT可以說是最好的機器學習算法之一。
GBDT分類和回歸時的基學習器都是CART回歸樹，因為是拟合殘差的。GBDT和Adaboost一樣可以用前向分布算法來描述，不同之處在于Adaboost算法每次拟合基學習器時，輸入的樣本資料是不一樣的（每一輪疊代時的樣本權重不一緻），因為Adaboost旨在重點關注上一輪分類錯誤的樣本，GBDT算法在每一步疊代時是輸出的值不一樣，本輪要拟合的輸出值是之前的加法模型的預測值和真實值的內插補點（模型的殘差，也稱為損失）。用于一個簡單的例子來說明GBDT，假如某人的年齡為30歲，第一次用20歲去拟合，發現損失還有10歲，第二次用6歲去拟合10歲，發現損失還有4歲，第三次用3歲去拟合4歲，依次下去直到損失在我們可接受範圍内。
以平方誤差損失函數的回歸問題為例，來看看以損失來拟合是個什麼樣子，采用前向分布算法：
在第m次疊代時，我們要優化的損失函數：
此時我們采用平方誤差損失函數為例：
則上面損失函數變為：
問題就成了對殘差r的拟合了
然而對于大多數損失函數，卻沒那麼容易直接獲得模型的殘差，針對該問題，大神Freidman提出了用損失函數的負梯度來拟合本輪損失的近似值，拟合一個回歸樹
關于GBDT一般損失函數的具體算法流程如下：
1）初始化f0(x)：
2）第m次疊代時，計算目前要拟合的殘差rmi：
以rmi為輸出值，對rmi拟合一個回歸樹（
此時隻是确定了樹的結構，但是還未确定葉子節點中的輸出值），然後通過最小化目前的損失函數，并求得每個葉子節點中的輸出值cmj，j表示第j個葉子節點
更新目前的模型fm(x)為：
3）依次疊代到我們設定的基學習器的個數M，得到最終的模型，其中M表示基學習器的個數，J表示葉子節點的個數
GBDT算法提供了衆多的可選擇的損失函數，通過選擇不同的損失函數可以用來處理分類、回歸問題，比如用對數似然損失函數就可以處理分類問題。大概的總結下常用的損失函數：
1）對于分類問題可以選用指數損失函數、對數損失函數。
2）對于回歸問題可以選用均方差損失函數、絕對損失函數。
3）另外還有huber損失函數和分位數損失函數，也是用于回歸問題，可以增加回歸問題的健壯性，可以減少異常點對損失函數的影響。
3、GBDT的正則化在Adaboost中我們會對每個模型乘上一個弱化系數（正則化系數），減小每個模型對提升的貢獻（
注意：這個系數和模型的權重不一樣，是在權重上又乘以一個0,1之間的小數），在GBDT中我們采用同樣的政策，對于每個模型乘以一個系數λ (0 < λ ≤ 1)，降低每個模型對拟合損失的貢獻，這種方法也意味着我們需要更多的基學習器。
第二種是每次通過按比例（推薦[0.5, 0.8] 之間）随機抽取部分樣本來訓練模型，這種方法有點類似Bagging，可以減小方差，但同樣會增加模型的偏差，可采用交叉驗證選取，這種方式稱為子采樣。采用子采樣的GBDT有時也稱為随機梯度提升樹（SGBT）。
第三種就是控制基學習器CART樹的複雜度，可以采用剪枝正則化。
4、GBDT的優缺點GBDT的主要優點：
1）可以靈活的處理各種類型的資料
2）預測的準确率高
3）使用了一些健壯的損失函數，如huber，可以很好的處理異常值
GBDT的缺點：
1）由于基學習器之間的依賴關系，難以并行化處理，不過可以通過子采樣的SGBT來實作部分并行。
5、XGBoost算法 事實上對于樹模型為基學習器的內建方法在模組化過程中可以分為兩個步驟：一是确定樹模型的結構，二是确定樹模型的葉子節點中的輸出值。 5.1 定義樹的複雜度首先把樹拆分成結構部分q和葉子節點輸出值w，在這裡w是一個向量，表示各葉子節點中的輸出值。在這裡就囊括了上面提到的兩點，确定樹結構q和葉子結點的輸出值w。從下圖中可以看出，q(x)實際上是确定輸入值最終會落到哪個葉子節點上，而w将會給出相應的輸出值。
具體表現示例如下，引入正則化項 Ω(ft)來控制樹的複雜度，進而實作有效的控制模型的過拟合，
這是xgboost中的第一個重要點。式子中的T
為葉子節點數 和GBDT方法一樣，XGBoost的提升模型也是采用殘差，不同的是分裂結點選取的時候不一定是最小平方損失，其損失函數如下，較GBDT其根據樹模型的複雜度加入了一項正則化項：
上面的式子是通過泰勒展開式将損失函數展開為具有二階導的平方函數。
在GBDT中我們通過求損失函數的負梯度（一階導數），利用負梯度替代殘差來拟合樹模型。在XGBoost中直接用泰勒展開式将損失函數展開成二項式函數（
前提是損失函數一階、二階都連續可導，而且在這裡計算一階導和二階導時可以并行計算），假設此時我們定義好了樹的結構（在後面介紹，和GBDT中直接用殘差拟合不同），假設我們的葉節點區域為：
上面式子中i代表樣本i，j代表葉子節點j。
則我們的目标優化函數可以轉換成（因為l(yi,yt−1i)是個已經确定的常數，可以舍去）：
上面式子把樣本都合并到葉子節點中了。
此時我們對wj求導并令導數為0，可得：
其中 Gj=∑i∈Ijgi,Hj=∑i∈Tjhj。
5.4 樹結構的打分函數上面的Obj值代表當指定一個樹結構時，在目标上面最多減少多少，我們可以把它稱為結構分數。可以認為這是一個類似與基尼指數一樣更一般的對樹結構進行打分的函數。如下面的例子所示
對于求得Obj分數最小的樹結構，我們可以枚舉所有的可能性，然後對比結構分數來獲得最優的樹結構，然而這種方法計算消耗太大，更常用的是貪心法（事實上絕大多數樹模型都是這樣的，隻考慮目前節點的劃分最優），每次嘗試對已經存在的葉節點（最開始的葉節點是根節點）進行分割，然後獲得分割後的增益為：
在這裡以Gain作為判斷是否分割的條件，這裡的Gain可以看作是未分割前的Obj減去分割後的左右Obj，是以如果Gain<0，則此葉節點不做分割，然而這樣對于每次分割還是需要列出所有的分割方案（
對于特征的值的個數為n時，總共有2^n - 2 種劃分）。而實際中是采用近似貪心方法，我們先将所有樣本按照gi從小到大排序，然後進行周遊，檢視每個節點是否需要分割（
對于特征的值的個數為n
時，總共有n−1
種劃分），具體示例如下：
最簡單的樹結構就是一個節點的樹。我們可以算出這棵單節點的樹的好壞程度obj*。假設我們現在想按照年齡将這棵單節點樹進行分叉，我們需要知道：
1）按照年齡分是否有效，也就是是否減少了obj的值
2）如果可分，那麼以哪個年齡值來分。
此時我們就是先将年齡特征從小到大排好序，然後再從左到右周遊分割
這樣的分割方式，我們就隻要對樣本掃描一遍，就可以分割出GL，GR，然後根據Gain的分數進行分割，極大地節省了時間。是以從這裡看，XGBoost中從新定義了一個劃分屬性，也就是這裡的Gain，而這個劃分屬性的計算是由其目标損失決定obj的。
5.5 XGBoost中其他的正則化方法1）像Adaboost和GBDT中一樣，對每一個模型乘以一個系數λ（0<λ≤1），用來降低每個模型對結果的貢獻。
2）采用特征子采樣方法，和RandomForest中的特征子采樣一樣，可以降低模型的方差
6、XGBoost和GBDT的差別1）将樹模型的複雜度加入到正則項中，來避免過拟合，是以泛化性能會由于GBDT。
2）損失函數是用泰勒展開式展開的，同時用到了一階導和二階導，可以加快優化速度。
3）和GBDT隻支援CART作為基分類器之外，還支援線性分類器，在使用線性分類器的時候可以使用L1，L2正則化。
4）引進了特征子采樣，像RandomForest那樣，這種方法既能降低過拟合，還能減少計算。
5）在尋找最佳分割點時，考慮到傳統的貪心算法效率較低，實作了一種近似貪心算法，用來加速和減小記憶體消耗，除此之外還考慮了稀疏資料集和缺失值的處理，對于特征的值有缺失的樣本，XGBoost依然能自動找到其要分裂的方向。
6）XGBoost支援并行處理，XGBoost的并行不是在模型上的并行，而是在特征上的并行，将特征列排序後以block的形式存儲在記憶體中，在後面的疊代中重複使用這個結構。這個block也使得并行化成為了可能，其次在進行節點分裂時，計算每個特征的增益，最終選擇增益最大的那個特征去做分割，那麼各個特征的增益計算就可以開多線程進行。