機器學習boosting算法—Adaboost之示例解析

boosting方法是一種常用的統計學習方法，應用廣泛且有效，在分類問題中，它通過改變訓練樣本的權重，學習多個分類器，并将這些分類器進行線性組合，提高分類的性能，這裡我們通過Adaboost算法的示例分析來了解boosting方法的基本思路。

Adaboost算法

1 Adaboost算法流程圖

左邊是訓練資料集，其中直方圖的不同長度表示每個樣例的權重。在經過一個分類器之後，權重的預測結果會通過三角形中的alpha值進行權重。每個三角形中輸出的權重結果在圓形中求和，進而得到最終的輸出結果。

2 Adaboost算法詳細流程

輸入：訓練資料集 T={(x1,y1),(x2,y2),...,(xN,yN)} ， xi 為一個n維的特征點， yi∈{−1,+1}

輸出：分類器G(x)

步驟1. 初始化訓練資料權值分布

D1={w11,...,w1i,...w1N},w1i=1N,i=1,2,...N

步驟2. for T=1 to M

    (1) 對于權值分布為 Dm 的訓練資料集學習，得到弱分類器

Gm:xi→{−1，+1}

    (2) 計算 Gm(x) 在訓練資料集上的分類誤差

em=P(Gm(xi)≠yi)=∑i=1NwmiI(Gm(xi)≠yi)

    (3) 計算分類器 Gm(x) 的權重

αm=12ln1−emem

    （4）更新訓練資料集的分布

Dm+1={wm+1,1,...,wm+1,i,...wm+1,N}

wm+1,i=wmiZme−αmyiGmxi,i=1,2,...N

Zm=∑i=1Nwmie−αmyiGmxi

     Zm 是一個規範化因子

步驟3.分類器線性組合得到最終分類器

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

3 算法示例

給定如下樣例資料，假設弱分類器由 x<v 或 x>v 産生，其門檻值v使得分類器在訓練資料集上分類誤差最低，用Adaboost算法學習一個強分類器。

Index	1	2	3	4	5	6	7	8	9	10
x	1	2	3	4	5	6	7	8	9
y	1	1	1	-1	-1	-1	1	1	1	-1

步驟1. 初始化樣本權重

D1=(0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1)

樣本個數為10，是以均勻分布每個樣本的權重就為0.1

步驟2.疊代更新

第一輪疊代:

(a) 對于權值分布為 D1 的資料集，當分界點取為2.5時分類誤差率最低，是以得到基分類器

x<0.5(y=1)x>0.5(y=−1)error=510=0.5

x>0.5(y=1)x<0.5(y=−1)error=510=0.5

x<1.5(y=1)x>1.5(y=−1)error=410=0.5

x>1.5(y=1)x<1.5(y=−1)error=610=0.5

x<2.5(y=1)x>2.5(y=−1)error=310=0.4

x>2.5(y=1)x<2.5(y=−1)error=710=0.6

x<3.5(y=1)x>3.5(y=−1)error=410=0.3

x>3.5(y=1)x<3.5(y=−1)error=610=0.7

x<4.5(y=1)x>4.5(y=−1)error=510=0.4

x>4.5(y=1)x<4.5(y=−1)error=510=0.6

...

G1(x)={1,x<2.5−1,x>2.5

(b)分類器誤差: e1=310=0.3

(c)分類器權重： α1=12ln1−0.30.3=0.4236

(d)更新樣本權重：

w2,i=w1iZ1e−α1yiG1xi,i=1,2,...N

D2=(0.07143,0.07143,0.07143,0.07143,0.07143,0.07143,0.16667,0.16667,0.16667,0.07143)

(e)最終分類器: G(x)=sign(0.4236G1(x)) ,分類錯誤的樣本數為3

從疊代結果可以看出因為分類器取2.5為分界點，是以索引為6,7,8 的樣本分類錯誤，對應的樣本權重更新後從0.1上調為了0.16667，而其他的樣本都分類正确，樣本權重下調為了0.07143。

第二輪疊代：

(a)對于權值分布為 D2 的資料集，分界點為8.5時誤差率最低,基分類器為：

G2(x)={1,x<8.5−1,x>8.5

(b)分類器誤差: e2=0.2143

(c) 分類器權重： α2=0.6496

(d)更新樣本權重：

D3=(0.0455,0.0455,0.0455,0.16667,0.16667,0.16667,0.1060,0.1060,0.1060,0.0455)

(e)最終分類器： G(x)=sign(0.4236G1(x)+0.6496G2(x)) ，分類錯誤樣本數為3

從第二輪疊代的結果來看，基分類器對3，4，5的分類錯誤，而在第一輪疊代中分類錯誤的6，7，8分類正确了，是以3，4，5的樣本權重上調為了0.1667,而6，7，8的樣本權重下調為了0.1060，其它在第一輪和第二輪疊代中都分類正确的樣本權重就變得更低。

第三輪疊代：

(a)在權值分布為 D3 的資料集上，分界點為5.5時分類誤差率最低，基分類器為：

G3(x)={1,x>5.5−1,x<5.5

(b)分類器誤差： e3=0.1820

(c)分類器權重： α3=0.7514

(d)更新資料權值分布：

D4=(0.125,0.125,0.125,0.102,0.102,0.102,0.065,0.065,0.065,0.125)

(e)最終分類器 G(x)=sign(0.4236G1(x)+0.6496G2(x)+0.7514G3(x)) ,誤分點個數為0