關於Adaboost算法

Adaboost是一種迭代算法，其核心思想是針對同一個訓練集訓練不同的分類器(弱分類器)，然後把這些弱分類器集合起來，構成一個更強的最終分類器（強分類器）。

一.引入

對於Adaboost，可以說是久聞大名，據說在Deep Learning出來之前，SVM和Adaboost是效果最好的 兩個算法，而Adaboost是提升樹(boosting tree)，所謂「提升樹」就是把「弱學習算法」提升(boost)為「強學習算法」(語自《統計學習方法》)，而其中最具代表性的也就是Adaboost了，貌似Adaboost的結構還和Neural Network有幾分神似，我倒沒有深究過，不知道是不是有什麼乾貨

二.過程

（from PRML）

這就是Adaboost的結構，最後的分類器YM是由數個弱分類器（weak classifier）組合而成的,相當於最後m個弱分類器來投票決定分類，而且每個弱分類器的「話語權」α不一樣。

這裡闡述下算法的具體過程：

1. 初始化所有訓練樣例的權重為1 / N,其中N是樣例數

2. for m=1,……M:

a).訓練弱分類器ym()，使其最小化權重誤差函數（weighted error function）：

b)接下來計算該弱分類器的話語權α：

c)更新權重：

其中Zm：

是規範化因子，使所有w的和為1。(這裡公式稍微有點亂)

可以看到整個過程就是和最上面那張圖一樣，前一個分類器改變權重w，同時組成最後的分類器

如果一個訓練樣例 在前一個分類其中被誤分，那麼它的權重會被加重，相應地，被正確分類的樣例的權重會降低

使得下一個分類器 會更在意被誤分的樣例，那麼其中那些α和w的更新是怎麼來的呢？

下面我們從前項分步算法模型的角度來看看Adaboost：

直接將前項分步加法模型具體到adaboost上：

其中 fm是前m個分類器的結合

此時我們要最小化E，同時要考慮α和yl，

但現在我們假設前m-1個α和y都已經fixed了：那麼

其中，可以被看做一個常量，因為它裡面沒有αm和ym：

接下來：

其中Tm表示正分類的集合，Mm表示誤分類的集合，這一步其實就是把上面那個式子拆開，沒什麼複雜的東西。

然後就是找ym了，就是最小化下式的過程，其實就是我們訓練弱分類器

有了ym，α也就可以找了，然後繼續就可以找到更新w的公式了(注意這裡得到的w公式是沒有加規範化因子Z的公式，為了計算方便我們加了個Z進去)。因為這裡算出來直接就是上面過程裡的公式，就不再贅述了，有興趣你可以自己算一算。

   

終於到實現了，本次實現代碼基本基於《統計學習方法》，比如有些符號(弱分類器是G(x),訓練樣例的目標是y而不是上文所述的t)差異

所有的代碼你可以在我寫的toy toolkit裡面找到：DML (你都看到這了，給個star好不好)

              

# coding: UTF-8

from __future__ import division

import numpy as np

import scipy as sp

from weakclassify import WEAKC

from dml.tool import sign

class ADABC:

def __init__(self,X,y,Weaker=WEAKC):

'''

Weaker is a class of weak classifier

It should have a train(self.W) method pass the weight parameter to train

pred(test_set) method which return y formed by 1 or -1

see detail in <統計學習方法>

'''

self.X=np.array(X)

self.y=np.array(y)

self.Weaker=Weaker

self.sums=np.zeros(self.y.shape)

self.W=np.ones((self.X.shape[1],1)).flatten(1)/self.X.shape[1]

self.Q=0

#print self.W

def train(self,M=4):

'''

M is the maximal Weaker classification

'''

self.G={}

self.alpha={}

for i in range(M):

self.G.setdefault(i)

self.alpha.setdefault(i)

for i in range(M):

self.G[i]=self.Weaker(self.X,self.y)

e=self.G[i].train(self.W)

#print self.G[i].t_val,self.G[i].t_b,e

self.alpha[i]=1/2*np.log((1-e)/e)

#print self.alpha[i]

sg=self.G[i].pred(self.X)

Z=self.W*np.exp(-self.alpha[i]*self.y*sg.transpose())

self.W=(Z/Z.sum()).flatten(1)

self.Q=i

#print self.finalclassifer(i),'==========='

if self.finalclassifer(i)==0:

 

print i+1," weak classifier is enough to  make the error to 0"

break

def finalclassifer(self,t):

'''

the 1 to t weak classifer come together

'''

self.sums=self.sums+self.G[t].pred(self.X).flatten(1)*self.alpha[t]

#print self.sums

pre_y=sign(self.sums)

#sums=np.zeros(self.y.shape)

#for i in range(t+1):

# sums=sums+self.G[i].pred(self.X).flatten(1)*self.alpha[i]

# print sums

#pre_y=sign(sums)

t=(pre_y!=self.y).sum()

return t

def pred(self,test_set):

sums=np.zeros(self.y.shape)

for i in range(self.Q+1):

sums=sums+self.G[i].pred(self.X).flatten(1)*self.alpha[i]

#print sums

pre_y=sign(sums)

return pre_y

看train裡面的過程和上文 闡述的一模一樣，finalclassifier()函數是用來判斷是否已經無誤分類的點 的。

當然這裡用的Weak Classifier是比較基礎的Decision Stump，是根據x>v和x<v來分類的，這個代碼稍微煩一點，就不貼到這裡了，在DML裡也有，先試驗下《統計學習方法》裡面那個最簡單的例子：

可以看到也是三個分類器就沒有誤分點了，權值的選擇也是差不多的。

其中後面那個-1 表示大於threshold分為負類，小於分為正類。1則相反。

加一些其它數據試試：

結果：

  

我們把圖畫出來就是：

基本還是正確的，這是四個子分類器的圖，不是最後總分類器的圖啊~~~

（實驗的代碼你也可以在DML裡面找到，你都看到這了，給個star好不好~~~~~）

Reference：

      【1】 《Pattern Recognition And Machine Learning》

      【2】 《統計學習方法》

- 

版權聲明：本文為CSDN博主「Dark_Scope」的原創文章，遵循CC 4.0 by-sa版權協議，轉載請附上原文出處連結及本聲明。

原文連結：https://blog.csdn.net/Dark_Scope/article/details/14103983