提升方法AdaBoost算法

1、提升方法

提升方法就是從弱學習算法出發，反複學習，得到一系列弱分類器(又稱為基本分類器)，然後組合弱分類器，構成一個強分類器。大多數提升的方法都是改變訓練資料的的機率分布(訓練資料的權值分布)。

2、提升方法相關問題

（1）在每一輪如何改變訓練資料的權值或者機率分布？

Adaboost的做法就是，提高那些前一輪弱分類器錯誤分類樣本的權值，而降低那些被正确分類樣本的權值。

（2）如何将弱分類器組合成一個強分類器？

Adaboost采取權重多數表決的方法。加大分類誤差率小的弱分類器的權值，使其在表決中起較大的作用，減小弱分類器誤差率大的弱分類器的權值，使其在表決中起較小的作用。

3、AdaBoost算法

訓練資料

序号	1	2	3	4	5	6	7	8	9	10
x x	1	2	3	4	5	6	7	8	9
yy	1	1	1	-1	-1	-1	1	1	1	-1

步驟：

(1)初始化資料的權值 D1={w1,...,wN} D 1 = { w 1 , . . . , w N }

一共10個樣本，是以

w1=w2=...=w10=1N=0.1 w 1 = w 2 = . . . = w 10 = 1 N = 0.1

(2)在權值分布為 D1 D 1 上建構基本分類器 G1(x) G 1 ( x ) 如下

G1(x)=⎧⎩⎨⎪⎪1,x<2.5−1,x>2.5(1) (1) G 1 ( x ) = { 1 , x < 2.5 − 1 , x > 2.5

因為2.5作為分界線使得分類的誤差最低。

注意，基本分類器 Gm(x) G m ( x ) 的分類誤差的計算如下。即基本分類器對整個資料劃分，劃分不正确的樣本的權值之和。

em=P(Gm(xi)≠yi)=∑Gm(xi)≠yiwmi(2) (2) e m = P ( G m ( x i ) ≠ y i ) = ∑ G m ( x i ) ≠ y i w m i

(3)計算 G1(x) G 1 ( x ) 在資料集上的誤差

因為 G1(x) G 1 ( x ) 分類器的劃分界限是5.5，即序号為 {7,8,9} { 7 , 8 , 9 } 的3個樣本被錯誤分類，他們的權值都是0.1，是以 e1=0.3 e 1 = 0.3

(3)計算 G1(x) G 1 ( x ) 的系數，公式如下

αm=12log1−emem(3) (3) α m = 1 2 l o g 1 − e m e m

注意：公式(3)是個遞減函數，意味着分類器的誤差越大，其權重系數越小，在表決中作用越小。

是以， α1=12log1−e1e1=0.4236 α 1 = 1 2 l o g 1 − e 1 e 1 = 0.4236

(4)更新訓練資料的權值分布，公式如下

wi=wie−αmyiGm(xi)∑Ni=1wie−αmyiGm(xi)(4) (4) w i = w i e − α m y i G m ( x i ) ∑ i = 1 N w i e − α m y i G m ( x i )

注意：公式(4)的 −αmyiGm(xi) − α m y i G m ( x i ) 項表明，在分類器正确分類的情況下，該項值<0,而錯誤分類時候，該項值>0，又 ex e x 是個遞增函數，意味着錯誤的樣本的權值被加大。

經過公式(4)變換，得到新的權值分布 D2 D 2

D2=(0.07143，0.07143，0.07143，0.07143，0.07143，0.07143，0.16667，0.16667，0.16667，0.07143) D 2 = ( 0.07143 ， 0.07143 ， 0.07143 ， 0.07143 ， 0.07143 ， 0.07143 ， 0.16667 ， 0.16667 ， 0.16667 ， 0.07143 )

從中可以看到原來被錯誤分類序号為 {4,5,6} { 4 , 5 , 6 } 的3個樣本的權值得到加強。

(5)建構基本分類器的線性組合 fm(x) f m ( x ) ，公式如下:

fm(x)=∑m=1MαmGm(x) f m ( x ) = ∑ m = 1 M α m G m ( x )

目前的線性組合為

是以 f1(x)=α1G1(x)=0.4236∗G1(x) f 1 ( x ) = α 1 G 1 ( x ) = 0.4236 ∗ G 1 ( x )

分類器 sign[f1(x)] s i g n [ f 1 ( x ) ] 在訓練集上有3個錯分樣本。

其中，sign(x)或者Sign(x)叫做符号函數，在數學和計算機運算中，其功能是取某個數的符号（正或負）：當x>0，sign(x)=1;當x=0，sign(x)=0;當x<0， sign(x)=-1。

由于線性組合分類器還有錯誤樣本。是以，繼續上面的步驟(2)-(5).

(6)在權值分布為 D2 D 2 上建構基本分類器 G2(x) G 2 ( x ) 如下

G2(x)=⎧⎩⎨⎪⎪1,x<8.5−1,x>8.5(5) (5) G 2 ( x ) = { 1 , x < 8.5 − 1 , x > 8.5

因為新的權值分布如下，取分界限8.5時候序号為 {4,5,6} { 4 , 5 , 6 } 的3個樣本被錯誤分類，他們的權值都是0.07143，使得誤差最小，為 e2=0.07143∗3=0.21429 e 2 = 0.07143 ∗ 3 = 0.21429 。(注意，前一輪錯誤分類的序号為 {7,8,9} { 7 , 8 , 9 } ，在本輪中被正确分類了，因為其權值變大，使得不能再錯誤分類他們，如果繼續錯誤分類他們，根據誤差的計算原理，計算得出的誤差将比較大)

D2=(0.07143，0.07143，0.07143，0.07143，0.07143，0.07143，0.16667，0.16667，0.16667，0.07143) D 2 = ( 0.07143 ， 0.07143 ， 0.07143 ， 0.07143 ， 0.07143 ， 0.07143 ， 0.16667 ， 0.16667 ， 0.16667 ， 0.07143 )

(7)計算 α2,D3等 α 2 , D 3 等

得到 f2=α1G1(x)+α2G2(x) f 2 = α 1 G 1 ( x ) + α 2 G 2 ( x )

判斷 sign[f2(x)] s i g n [ f 2 ( x ) ] 是否還有錯誤分類的點

。。。

最終得到分類器

G(x)=sign[fm(x)] G ( x ) = s i g n [ f m ( x ) ]