標籤：

GBDT演算法

07-15
GBDT演算法

來自專欄機器學習，深度學習，複雜網路，演算法2 人贊了文章

覺得這篇文章不錯，推薦給大家！！！！！！！！！！

GBDT相對於經典的決策樹，算是一種比較成熟而且可以實際應用的決策樹演算法了。我們想要理解GBDT這種決策樹，得先從感性上理解這棵樹的工作方式。

我們知道，分類樹在每一次分支的時候，窮舉每一個特徵的每一個閾值，然後按照大於或者小於閾值的方式將其相互分開。這就是分類樹的演算法。

而回歸樹也十分類似，但是在每個節點都會得到一個預測值。

以年齡為例，該預測值等於屬於這個節點的所有人年齡的平均值。分枝時窮舉每一個feature的每個閾值找最好的分割點，但衡量最好的標準不再是最大熵，而是最小化均方差--即（每個人的年齡-預測年齡）^2 的總和 / N，或者說是每個人的預測誤差平方和 除以 N。這很好理解，被預測出錯的人數越多，錯的越離譜，均方差就越大，通過最小化均方差能夠找到最靠譜的分枝依據。分枝直到每個葉子節點上人的年齡都唯一（這太難了）或者達到預設的終止條件（如葉子個數上限），若最終葉子節點上人的年齡不唯一，則以該節點上所有人的平均年齡做為該葉子節點的預測年齡。

BDT(Boosting Decision Tree 提升決策樹)

這其實是一個很好的思維方式。

Boosting，提升。這涉及到機器學習中的集成學習。原理就是通過多個特徵生成多個樹，來決策一件事情。也就是「三個臭皮匠，頂一個諸葛亮」的原理。這是如何實現的呢？我們舉一個簡單的例子。BDT的核心就在於，每一棵樹學的是之前所有樹結論和的殘差，這個殘差就是一個加預測值後能得真實值的累加量。比如A的真實年齡是18歲，我們訓練的時候，第一棵樹的擬合過後預測年齡是12歲，我們與真實數據比對差了6歲，即殘差為6歲。那麼在第二棵樹里我們把A的年齡設為6歲去擬合學習，如果第二棵樹真的能把A分到6歲的葉子節點，那累加兩棵樹的結論就是A的真實年齡；如果第二棵樹的結論是5歲，則A仍然存在1歲的殘差，第三棵樹里A的年齡就變成1歲，繼續學。

如果還有疑問，請看下面這個例子：

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

這是一棵普通的回歸樹，我們可以看到，我們通過年齡平均值將少年和青年分開

，再用上網時長將每個分支繼續細分到不能分割或者達到要求為止。

接下來看BDT實現：

在第一棵樹分枝和圖1一樣，由於A,B年齡較為相近，C,D年齡較為相近，他們被分為兩撥，每撥用平均年齡作為預測值。此時計算殘差（殘差的意思就是： A的預測值 + A的殘差 = A的實際值），所以A的殘差就是16-15=1（注意，A的預測值是指前面所有樹累加的和，這裡前面只有一棵樹所以直接是15，如果還有樹則需要都累加起來作為A的預測值）。進而得到A,B,C,D的殘差分別為-1,1，-1,1。然後我們拿殘差替代A,B,C,D的原值，到第二棵樹去學習，如果我們的預測值和它們的殘差相等，則只需把第二棵樹的結論累加到第一棵樹上就能得到真實年齡了。這裡的數據顯然是我可以做的，第二棵樹只有兩個值1和-1，直接分成兩個節點。此時所有人的殘差都是0，即每個人都得到了真實的預測值。

換句話說，現在A,B,C,D的預測值都和真實年齡一致了:

  1. 14歲高一學生，購物較少，經常問學長問題；預測年齡A = 15 – 1 = 14
  2. 16歲高三學生；購物較少，經常被學弟問問題；預測年齡B = 15 + 1 = 16
  3. 24歲應屆畢業生；購物較多，經常問師兄問題；預測年齡C = 25 – 1 = 24
  4. 26歲工作兩年員工；購物較多，經常被師弟問問題；預測年齡D = 25 + 1 = 26

GBDT核心思想就是這樣，但是既然普通的樹和GBDT結果一樣，那為什麼還需要GBDT呢？

原因就是過擬合。過擬合就是模型在訓練數據集上表現的過於好，分的過於細。以致於容錯能力很低，也可以稱作」泛化能力「低。這就會導致在實際測試數據中表現明顯差很多。我們發現圖1為了達到100%精度使用了3個feature（上網時長、時段、網購金額），其中分枝「上網時長>1.1h」 很顯然已經過擬合了，這個數據集上A,B也許恰好A每天上網1.09h, B上網1.05小時，但用上網時間是不是>1.1小時來判斷所有人的年齡很顯然是有悖常識的；

相對來說圖2的boosting雖然用了兩棵樹 ，但其實只用了2個feature就搞定了，後一個feature是問答比例，顯然圖2的依據更靠譜（這是杜撰的數據，為了顯示效果誇張的一下，實際有實驗證明以上論點）。

GB(Gradient Boosting 梯度提升)

我們前面一直都在討論GBDT的基本原理，是從宏觀上對於這種演算法有個感性的認識。但是我們要想進一步理解GBDT，就得知道負梯度擬合，或者我們也叫梯度提升。

我們都知道，在機器學習演算法中，為了降低誤差函數，我們會有一個方法叫做梯度下降法。其做法是誤差函數中，每一步都走當前的梯度方向，也就是下降最快的方向進行下降，這樣多次迭代步長之後，誤差函數就會降到一個局部最低點（凸函數中也是全局最低點），也就得到了最小的誤差函數。

我們嘗試使用這種方法去訓練一棵回歸樹，或者更精確的說，是一棵CART，如有朋友不太熟悉CART，請看我之前的文章《CART》。正如前面所提到，我們GBDT每次訓練的時候都是擬合上一棵樹的殘差，那麼我們使用損失函數來擬合這棵樹:

使用損失函數的負梯度來擬合它的殘差：

這樣將所有的負梯度加起來之後就會得到一個整體的梯度下降。使得整個系統的誤差函數最小。

我貼出梯度提升演算法以輔助理解，內容來自李航的《統計學習方法》：

我們來看看這梯度提升演算法的流程：

  1. 我們先初始化第一棵回歸樹，使這個分界點讓整體誤差最小。具體細節上為什麼初始化成這種形式，請看我之前寫過的文章《CART》;
  2. 我們每生成一棵樹之後，就將這棵樹的每一條數據的損失函數的梯度求出來；損失函數我們一般寫作是均方誤差，每個數據與切分點之間的均方差就是損失函數；
  3. 求出每個數據的負梯度之後，我們依據已有數據和每個數據的負梯度，生成一個新樹出來，我們先將每個數據的負梯度當作新的數據的yi，這樣就得到了一組新數據，也確定了新數據的空間劃分。然後再計算每一條數據的誤差函數，取誤差函數最小的那個點做為下一個分支切分點，這也就生成了一顆新樹；
  4. 我們將新樹加到原來那棵樹上；
  5. 最後總和得到一棵樹；

推薦閱讀：

TAG:機器學習 | 深度學習DeepLearning | 數據挖掘 |