整合學習——Boosting之提升樹(Boosting tree)、梯度提升樹(GBDT)

整合學習——Boosting之提升樹(Boosting tree)、梯度提升樹(GBDT)

提升樹是以迴歸樹為基本分類器的提升方法。以決策樹為基函式的提升方法稱為提升樹(boosting tree)。對分類問題決策樹是分類樹,對迴歸問題決策樹為迴歸樹。首先定義決策樹用公式表示。

提升樹演算法:

1.首先確定初始提升樹

2.第二個提升樹

第三個提升樹

……推出:

3.回憶一下CART迴歸樹,它是採用平方誤差損失函式最小來決定最佳分類點,,CART的優化模型為,就是這個最佳分類點分為兩類後殘差最小;提升樹的模型為:當前樹的引數,換句話就是用上次決策樹分類完的殘差,繼續計算當前樹的殘差。(CART是分類完後再在子類中用原始資料計算最小殘差分類)。如果想對上述式子化簡:

4.更新,得到迴歸問題提升樹:

如果不理解,可以看下面例子:

這個例子與CART迴歸樹用的是同一個例子,可以幫助理解對比。(例子來源李航:統計學習方法)。

X

1

2

3

4

5

6

7

8

9

10

Y

5.56

5.7

5.91

6.4

6.8

7.05

8.9

8.7

9

9.05

步驟一:,求即迴歸樹

通過以下優化問題找到最初分割點s:

取s=1.5,此時 R1={1},R2={2,3,4,5,6,7,8,9,10},這兩個區域的輸出值分別為:c1=5.56,c2=1/9(5.7 5.91 6.4 6.8 7.05 8.9 8.7 9 9.05)=7.50。

取s=2.5,c1=5.63,s2=7.73,等等,計算m(1.5)=0 15.72=15.72等等,得到下表:

s

1.5

2.5

3.5

4.5

5.5

6.5

7.5

8.5

9.5

m(s)

15.72

12.07

8.36

5.78

3.91

1.93

8.01

11.73

15.74

顯然s=6.5時,m(s)最小。因此,第一個劃分變數s=6.5

對這個選定劃分後的兩個區域為R1={1,2,3,4,5,6},R2={7,8,9,10}輸出值c1=6.24,c2=8.91。

所以迴歸樹

到此為止與CART迴歸樹演算法一樣,CART接下來就是在分完的子樹中繼續利用平方損失函式分類,但提升樹演算法如下:

計算殘差,,見下表:

1

2

3

4

5

6

7

8

9

10

-0.68

-0.54

-0.33

0.16

0.56

0.81

-0.01

-0.21

0.09

0.14

 

計算的訓練資料的平方損失誤差:

步驟二:求。方法與求一樣,只不過用的資料是上次計算的殘差。即取s=1.5時算出c1=-0.68,c2=0.08,再算m(1.5)……等等,不再計算,得到x=3.5時m(3.5)最小,則:

算出的平方損失誤差為:

繼續求得:

算出的平方損失誤差為:,假設我們設定的誤差閾值大於0.17,那麼到此為止生成樹結束,就是所求的提升樹。

梯度提升樹(GBDT)

Gradient Boosting(提升樹):每一次的計算是為了減少上一次的殘差(residual),而為了消除殘差,我們可以在殘差減少的梯度(Gradient)方向上建立一個新的模型。所以說,在Gradient Boost中,每個新的模型的建立是為了使得之前模型的殘差往梯度方向減少(當然也可以變向理解成每個新建的模型都給予上一模型的誤差給了更多的關注),與傳統Boost對正確、錯誤的樣本進行直接加權還是有區別的。

所以,有的文章把上一節介紹的基於殘差的提升樹方法叫做GBDT(梯度提升樹),他們認為GBDT分為兩個版本,一個就是這個殘差的提升樹,另一個版本就是即將介紹的基於負梯度的提升樹;具體讀者怎麼分類,各自保留意見,只要自己不蒙圈就行。

首先我們先把李航描述的GBDT演算法寫出來,再做分析:

提升樹的損失函式是平方損失,每一步優化是簡單,但對一般損失函式而言,往往每一步優化並不簡單,梯度提升就是利用最速下降法的近似方法,利用損失函式的負梯度在當前模型的值作為迴歸問題提升樹演算法中的殘差的近似值,擬合一個迴歸樹。

梯度提升演算法:

(1) 初始化:

(2) 對m=1,2,……M

a 對i=1,2,……N計算

b 對擬合一個迴歸樹,得到第m顆樹的葉節點區域

c 對,計算

d 更新

(3) 得到迴歸樹

第1步:初始化,估計使損失函式最小化的常數值,它是隻有一個根節點的樹;

第2(a)步:計算損失函式的負梯度在當前模型的值,將它作為殘差的估計。對於平方損失函式,它就是通常所說的殘差;對於一般損失函式,它就是殘差的近似值;

第2(b)步:估計迴歸樹葉節點區域,以擬合殘差的近似值;

第2(c)步:利用線性搜尋估計葉節點區域的值,使損失函式極小化;

第2(d)步:更新迴歸樹;

第3步:得到輸出的最終模型

GBDT常用的損失函式:

對於分類演算法,其損失函式一般有對數損失函式和指數損失函式兩種:

a) 如果是指數損失函式,則損失函式表示式為

其負梯度計算和葉子節點的最佳殘差擬合參見Adaboost原理篇。

b) 如果是對數損失函式,分為二元分類和多元分類兩種,

二元GBDT:

多元GBDT:

對於迴歸演算法,常用損失函式有如下4種:

a)均方差,這個是最常見的迴歸損失函式了

b)絕對損失,這個損失函式也很常見

對應負梯度誤差為:

c)Huber損失,它是均方差和絕對損失的折衷產物,對於遠離中心的異常點,採用絕對損失,而中心附近的點採用均方差。這個界限一般用分位數點度量。損失函式如下:

對應的負梯度誤差為:

d) 分位數損失。它對應的是分位數迴歸的損失函式,表示式為

其中θ為分位數,需要我們在迴歸前指定。對應的負梯度誤差為:

對於Huber損失和分位數損失,主要用於健壯迴歸,也就是減少異常點對損失函式的影響。

先說迴歸演算法,我們依然採用簡單的平方損失函式。是的,跟提升樹採用的損失函式一樣,但是演算法不一樣!那麼第m輪的第i個樣本的損失函式的負梯度為:,把平方損失函式帶入得到:,這就是要去擬合的,這不就是提升樹時用的殘差嗎,是的,它特麼就是殘差!

舉個栗子(來自部落格https://blog.csdn.net/zpalyq110/article/details/79527653):

如下表所示:一組資料,特徵為年齡、體重,身高為標籤值。共有5條資料,前四條為訓練樣本,最後一條為要預測的樣本。

編號

年齡

體重(kg)

身高(m)

1

5

20

1.1

2

7

30

1.3

3

21

70

1.7

4

30

60

1.8

5(要預測的)

25

65

?

步驟一:初始化弱學習器,;這個函式就是要找到使得平方損失函式最小的引數。對平方損失函式求導,令導數等於0:

,令,得到

所以初始化時,取所有樣本標籤的均值,=(1.1 1.3 1.7 1.8)/4=1.475,那麼

步驟二:迭代第一輪m=1:

計算負梯度,當採用損失函式是平方損失函式時負梯度就是殘差:,見下表,殘差表:

編號

真實值

殘差

1

1.1

1.475

-0.375

2

1.3

1.475

-0.175

3

1.7

1.475

0.225

4

1.8

1.475

0.325

把上表算出的殘差作為樣本標籤,訓練,即把原始資料變為:

編號

年齡

體重(kg)

身高(m)

1

5

20

-0.375

2

7

30

-0.175

3

21

70

0.225

4

30

60

0.325

然後找最佳劃分點,提升樹時使用,即找到最小的m(s),GBDT是找到最小的方差,見小表:

採用年齡劃分:

劃分點

小於劃分點的樣本

大於劃分點的樣本

總方差

5歲

/

1,2,3,4

0.082

7歲

1

2,3,4

0.047

21歲

1,2

3,4

0.0125

30歲

1,2,3

4

0.062

採用體重劃分:

劃分點

小於劃分點的樣本

大於劃分點的樣本

總方差

20kg

/

1,2,3,4

0.082

30kg

1

2,3,4

0.047

60kg

1,2

3,4

0.0125

70kg

1,2,4

3

0.0867

 

遍歷所有樣本點後,發現方差最小0.0125的劃分:年齡21歲或者體重60kg,採用哪種劃分都行,我們採用年齡21歲劃分。

在演算法2(c)步,接著給這兩個葉子節點計算,擬合殘差,計算,求解方法與步驟一初始化一樣,求導令導數為0得到最小值,其實就是把殘差表劃分為兩個子類後每個子類的均值。那麼根據上述年齡21劃分後:

樣本1,2為左葉子節點,,所以

樣本3,4為右葉子節點,,所以

演算法2(d)更新強學習器,

步驟三:繼續m次迭代,重複以上演算法,m可以認為控制,生成m顆樹;

假設我們只迭代1次,那麼得到最終的強學習器,最終的樹為:

GBDT樹:

 

步驟四:預測,對原始資料有個樣本5,年齡為25歲,預測其身高,根據最終強分類器,,及GBDT樹得知,樣本5被分到右子樹,那麼;這就是樣本5的最終預測值,身高1.75(m)。用於迴歸的GBDT介紹完畢,下面介紹用於分類的GBDT。

用於分類的GBDT(參考部落格:https://www.cnblogs.com/pinard/p/6140514.html):

GBDT 無論用於分類還是迴歸一直都是使用的CART 迴歸樹,GBDT的分類演算法從思想上和GBDT的迴歸演算法沒有區別,但是由於樣本輸出不是連續的值,而是離散的類別,導致我們無法直接從輸出類別去擬合類別輸出的誤差。

為了解決這個問題,主要有兩個方法,一個是用指數損失函式,此時GBDT退化為Adaboost演算法。另一種方法是用類似於邏輯迴歸的對數似然損失函式的方法。也就是說,我們用的是類別的預測概率值和真實概率值的差來擬合損失。本文僅討論用對數似然損失函式的GBDT分類。而對於對數似然損失函式,我們又有二元分類和多元分類的區別。

二元GBDT分類演算法:

對於二元GBDT,如果用類似於邏輯迴歸的對數似然損失函式,則損失函式為:

其中。則此時的負梯度誤差為

對於生成的決策樹,我們各個葉子節點的最佳殘差擬合值為

由於上式比較難優化,我們一般使用近似值代替

除了負梯度計算和葉子節點的最佳殘差擬合的線性搜尋,二元GBDT分類和GBDT迴歸演算法過程相同。

多元GBDT分類演算法:

多元GBDT要比二元GBDT複雜一些,對應的是多元邏輯迴歸和二元邏輯迴歸的複雜度差別。假設類別數為K,則此時我們的對數似然損失函式為:

其中如果樣本輸出類別為k,則。第k類的概率的表示式為:

集合上兩式,我們可以計算出第輪的第個樣本對應類別的負梯度誤差為

觀察上式可以看出,其實這裡的誤差就是樣本對應類別的真實概率和輪預測概率的差值。

對於生成的決策樹,我們各個葉子節點的最佳殘差擬合值為

由於上式比較難優化,我們一般使用近似值代替

除了負梯度計算和葉子節點的最佳殘差擬合的線性搜尋,多元GBDT分類和二元GBDT分類以及GBDT迴歸演算法過程相同。

先介紹一下演算法流程:

樣本總共有K個分類,新來一個樣本求這個樣本屬於哪一類;

反正我是看不懂,這都是啥,由例子來解析演算法吧

(參考部落格https://blog.csdn.net/qq_22238533/article/details/79199605):

一組簡單的資料,也就是隻有一個特徵值:

6

12

14

18

20

65

31

40

1

2

100

101

65

54

A

A

A

A

A

B

B

B

B

B

C

C

C

C

由於我們要轉化為3個二分類問題,所以需要先one-hot:

6

12

14

18

20

65

31

40

1

2

100

101

65

54

A

A

A

A

A

B

B

B

B

B

C

C

C

C

1

1

1

1

1

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

1

1

1

1

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

1

1

1

對於K各分類問題,我們即要訓練K個數,類別標籤為A的樹CART Tree1,如果樣本屬於類別A那麼它的類別標籤輸出即為[1,0,0],其他兩棵樹同理;

為了方便說明只進行一輪迭代,學習率為1;

首先初始化,即

對第一棵樹CART Tree1即類別=A,擬合第一棵樹,只迭代一次:

6

12

14

18

20

65

31

40

1

2

100

101

65

54

1

1

1

1

1

0

0

0

0

0

0

0

0

0

 

利用,得到:

6

12

14

18

20

65

31

40

1

2

100

101

65

54

計算負梯度值,比如求

=1-1/3=2/3,得到下表:

6

12

14

18

20

65

31

40

1

2

100

101

65

54

2/3

2/3

2/3

2/3

2/3

就以上面這個表利用殘差找到一個最佳分類點,比如我們選s=31為分類點,則小於31的子樹的均值為,大於等於31的子樹的均值,則殘差等於屬於左子樹樣本的加上屬於右子樹樣本的,怎麼計算殘差說了好多遍了這裡就不再多說,最後得到31為最佳分類點,m(31)=1.42857。

再計算:同理,計算得到:

根據公式更新:,得到下表:

6

12

14

18

20

65

31

40

1

2

100

101

65

54

1.1428

1.1428

1.1428

1.1428

1.1428

-0.999

-0.999

-0.999

1.1428

1.1428

-0.999

-0.999

-0.999

-0.999

至此,迭代一次的情況下,類別A的第一棵樹就擬合完畢,下面擬合類別B的迭代一次的樹;

迭代一次,類別B的第一棵樹:

6

12

14

18

20

65

31

40

1

2

100

101

65

54

0

0

0

0

0

1

1

1

1

1

0

0

0

0

利用,得到:

6

12

14

18

20

65

31

40

1

2

100

101

65

54

 

計算負梯度值,比如求

=0-1/3=-1/3,得到下表:

6

12

14

18

20

65

31

40

1

2

100

101

65

54

擬合一顆迴歸樹,(以6為分裂點),可計算得到葉子節點:

,更新,得到下表:

6

12

14

18

20

65

31

40

1

2

100

101

65

54

-0.2499

-0.2499

-0.2499

-0.2499

-0.2499

-0.2499

-0.999

-0.2499

2

2

-0.2499

-0.2499

-0.2499

-0.2499

同理,再擬合第一輪中的第三棵樹CART Tree3,不再重複,假如說我們只迭代一輪,如果新來一個樣本X=50,那麼它屬於哪個類別呢,根據公式,樣本X屬於類別A的概率為,利用CART Tree1分類方法得到,利用CART Tree2得到,等等,帶入上式分別得到樣本X屬於類別A的概率,屬於類別B的概率,等等,如果我們設定閾值為0.5,那麼誰大於0.5樣本X就屬於哪個類別。