AdaBoost是Boosting算法的一種,比較出名,它可以將多個弱分類器線性組合成一個強分類器,通俗的說就是“三個臭皮匠,頂個諸葛亮”。其要求弱分類器好而不同,每個分類器的准確率要在50%以上。
AdaBoos先初始化樣本權值分布,並從初始訓練集訓練出一個基學習器,再根據這個基學習器的分類結果對訓練樣本的權值分布進行調整,再生成新的基學習器,依次進行下去,直到滿足要求。其流程如下:
(1)初始化樣本權值分布
(2)生成基本分類器G1
(3)計算分類器系數 α \alpha α
(4)更新訓練數據的權值分布
(5)生成新的分類器G2
(6)循環(2-5)
(7)將所有的分類器線性相加。
這個過程看起來比較難理解,同時書上公式太多,看得頭大,所以咱們還是舉個簡單的例子吧,這個例子是李航《統計學習方法》裡的。假設我們有這樣一些數據:
x x x表示樣本值, y y y是這些樣本的標簽,我們現在要做的就是根據x的值建立一個模型來預測y的值。本質上是一個二分類問題,建立一個分類器將這些樣本進行分類,1表示正例,-1表示反例。在正式開始之前,我們先假定這些樣本的權值 w w w都是一樣的,都為0.1(總共10個樣本,權值的和為1),如下表所示:
權值初始化代碼如下:
def func_w_1(x):
w_1=[]
for i in range(len(x)):
w_1.append(0.1)
return w_1
假設我們最初的分類器可以將前n個樣本識別為正例,剩下的樣本為反例,可以用下面的公式表達: G i ( x ) = { 1 x<u − 1 x>u (1) Gi(x)= \begin{cases} 1& \text{x<u}\\ -1& \text{x>u} \end{cases}\tag{1} Gi(x)={ 1−1x<ux>u(1)
其中 u u u為阈值, i i i是下標(不會編輯,哭了),為了方便討論我們將u的值設置為:
阈值生成的代碼如下:
def func_threshs(x):
threshs =[i-0.5 for i in x]
threshs.append(x[len(x)-1]+0.5)
return threshs
對於每一個分類器 G i ( x ) Gi(x) Gi(x),其誤差率 e e e可用其出錯(即 G i ( x i ) ≠ y i Gi(xi)\neq yi Gi(xi)=yi)的權值和來表示,比如當阈值為2.5時,該分類器為 G i ( x ) = { 1 x<2.5 − 1 x>2.5 (2) Gi(x)= \begin{cases} 1& \text{x<2.5}\\ -1& \text{x>2.5} \end{cases}\tag{2} Gi(x)={ 1−1x<2.5x>2.5(2)
或者
G i ( x ) = { − 1 x<2.5 1 x>2.5 (3) Gi(x)= \begin{cases} -1& \text{x<2.5}\\ 1& \text{x>2.5} \end{cases}\tag{3} Gi(x)={ −11x<2.5x>2.5(3)
這樣每一個阈值都可以生成2種分類器,因此共有22個分類器。對於分類器 ( 2 ) (2) (2)給定輸入 x x x,其輸出 G G G如下
分類器實現的代碼如下:
def func_cut(threshs): y_pres_all={
}#定義正向分類器,形如公式2 y_last_all={
}#定義正向分類器,形如公式3
for thresh in threshs:
y_pres=[]
y_last=[]
for i in range(len(x)):
if x[i]<thresh:
y_pres.append(1)
y_last.append(-1)
else:
y_pres.append(-1)
y_last.append(1)
y_pres_all[thresh]=y_pres
y_last_all[thresh]=y_last
return y_pres_all,y_last_all
從表中可以看出,樣本7、8、9分錯了,故其誤差率e=w7+w8+w9=0.3。我們用同樣的方法求這22個分類器的誤差率,選擇誤差率最小的作為基分類器。計算誤差率的代碼如下:
def sub_func_e(y,w_n,y_pres_all,thresh):
e=0
for i in range(len(y)):
if y_pres_all[thresh][i]!=y[i]:
e+=w_n[i];
return e
def sub_func_e_s(y,w_n,y_pres_all,threshs): e_s={
}
e_min=1
n=0
for thresh in threshs:
e=sub_func_e(y,w_n,y_pres_all,thresh)
e_s[thresh]=round(e,6)
if e<e_min:
e_min=round(e,6)
n=thresh
return e_s,e_min,n
def sub_func_e_all(y,w_n,y_pres_all,y_last_all,threshs):
e_s1,e_min1,n1=sub_func_e_s(y,w_n,y_pres_all,threshs)
e_s2,e_min2,n2=sub_func_e_s(y,w_n,y_last_all,threshs)
if e_min1<=e_min2:
return e_s1,e_min1,n1,y_pres_all
else:
return e_s2,e_min2,n2,y_last_all
在我們的例子中,通過計算所有的誤差率得到基分類器為公式2所示。下面開始計算分類器的系數 α \alpha α,其計算公式如下:
α = 1 2 l n 1 − e e (4) \alpha=\frac{1}{2}ln\frac{1-e}{e}\tag{4} α=21lne1−e(4) 由此可見誤差率e不能大於0.5,否則會使得 α \alpha α<0。本例中 α = 1 2 l n 1 − 0.3 0.3 = 0.4236 \alpha=\frac{1}{2}ln\frac{1-0.3}{0.3}=0.4236 α=21ln0.31−0.3=0.4236,計算分類器系數的代碼如下:
def func_a_n(e_min):
a_n=round(0.5*math.log((1-e_min)/e_min),6)
return a_n
最後再根據以上計算的結果更新權值分布w2,更新的公式如下:
w 2 i = w 1 ( i ) Z ∗ e − α i ∗ y i ∗ G 1 ( x i ) (5) w2i=\frac{w1(i)}{Z}*e^{-\alpha{i}*yi*G1(xi)}\tag{5} w2i=Zw1(i)∗e−αi∗yi∗G1(xi)(5)其中 Z = ∑ i = 1 m w 1 ( i ) ∗ e − α i ∗ y i ∗ G 1 ( x i ) (6) Z=\sum_{i=1}^m w1(i)*e^{-\alpha{i}*yi*G1(xi)}\tag{6} Z=i=1∑mw1(i)∗e−αi∗yi∗G1(xi)(6)
m是樣本的個數,不難看出 Z Z Z的作用是讓新生成的樣本權值的和為1,通過該公式計算可以得到新的權值分布:
舉個例子,第一個樣本的權值更新成了0.07143,這個是怎麼來的呢,是這樣算的: w 1 ( 1 ) Z ∗ e − α 1 ∗ y 1 ∗ G 1 ( x 1 ) = 0.1 5.50011 ∗ e − 0.4236 ∗ 1 ∗ 1 = 0.07143 , 其 中 Z = 0.07143 ∗ 7 + 0.16667 ∗ 3 = 5.50011 \frac{w1(1)}{Z}*e^{-\alpha{1}*y1*G1(x1)}=\frac{0.1}{5.50011}*e^{-0.4236*1*1}=0.07143,其中Z=0.07143*7+0.16667*3=5.50011 Zw1(1)∗e−α1∗y1∗G1(x1)=5.500110.1∗e−0.4236∗1∗1=0.07143,其中Z=0.07143∗7+0.16667∗3=5.50011,其實就是w2的和。從表裡可以看出,之前分錯的樣本7,8,9的權值提高了,其余的則下降了。樣本分布權值的更新代碼如下:
def func_w_n_tmp(x,pre_n,w_n,a_n):
w_n_tmp=[]
for i in range(len(x)):
w_new=round(w_n[i]*math.exp(-1*a_n*y[i]*pre_n[i]),6)
w_n_tmp.append(w_new)
return w_n_tmp
def func_z_n(w_n_tmp):
z_n=sum(w_n_tmp)
return z_n
def func_w_n(w_n_tmp,z_n):
w_n=[round(i/z_n,5) for i in w_n_tmp]
return w_n
我們用同樣的流程可以得到多個分類器及多個分類器權值分布,共同組成了新的分類器,即
G ( X ) = s i g n [ f ( x ) ] G(X)=sign[f(x)] G(X)=sign[f(x)]其中
f ( x ) = α 1 ∗ G 1 ( x ) + α 2 ∗ G 2 ( x ) + ⋅ ⋅ ⋅ α n ∗ G n ( x ) f(x)=\alpha1*G1(x)+\alpha2*G2(x)+\cdot\cdot\cdot\alpha n*Gn(x) f(x)=α1∗G1(x)+α2∗G2(x)+⋅⋅⋅αn∗Gn(x)
s i g n [ f ( x ) ] sign[f(x)] sign[f(x)]表示當 f ( x ) f(x) f(x)大於0時取1,小於0時取-1,書上給出的3個分類器的集成,結果為 f ( x ) = 0.4236 ∗ G 1 ( x ) + 0.6496 ∗ G 2 ( x ) + 0.7514 ∗ G 3 ( x ) f(x)=0.4236*G1(x)+0.6496*G2(x)+0.7514*G3(x) f(x)=0.4236∗G1(x)+0.6496∗G2(x)+0.7514∗G3(x),其中: G 1 ( x ) = { 1 x<2.5 − 1 x>2.5 G1(x)= \begin{cases} 1& \text{x<2.5}\\ -1& \text{x>2.5} \end{cases} G1(x)={ 1−1x<2.5x>2.5 G 2 ( x ) = { 1 x<8.5 − 1 x>8.5 G2(x)= \begin{cases} 1& \text{x<8.5}\\ -1& \text{x>8.5} \end{cases} G2(x)={ 1−1x<8.5x>8.5 G 3 ( x ) = { − 1 x<5.5 1 x>5.5 G3(x)= \begin{cases} -1& \text{x<5.5}\\ 1& \text{x>5.5} \end{cases} G3(x)={ −11x<5.5x>5.5
則 f ( x ) f(x) f(x)為 f ( x ) = { 0.4236 + 0.6496 − 0.7514 = 0.3218 x<2.5 − 0.4236 + 0.6496 − 0.7514 = − 0.5254 2.5<x<5.5 − 0.4236 + 0.6496 + 0.7514 = 0.9774 5.5<x<8.5 − 0.4236 − 0.6496 + 0.7514 = − 0.3218 x>8.5 f(x)= \begin{cases} 0.4236+0.6496-0.7514=0.3218& \text{x<2.5}\\ -0.4236+0.6496-0.7514=-0.5254& \text{2.5<x<5.5}\\ -0.4236+0.6496+0.7514=0.9774& \text{5.5<x<8.5}\\ -0.4236-0.6496+0.7514=-0.3218& \text{x>8.5} \end{cases} f(x)=⎩⎪⎪⎪⎨⎪⎪⎪⎧0.4236+0.6496−0.7514=0.3218−0.4236+0.6496−0.7514=−0.5254−0.4236+0.6496+0.7514=0.9774−0.4236−0.6496+0.7514=−0.3218x<2.52.5<x<5.55.5<x<8.5x>8.5
最終的分類器
G ( x ) = { 1 x<2.5 − 1 2.5<x<5.5 1 5.5<x<8.5 − 1 x>8.5 G(x)= \begin{cases} 1& \text{x<2.5}\\ -1& \text{2.5<x<5.5}\\ 1& \text{5.5<x<8.5}\\ -1& \text{x>8.5}\end{cases} G(x)=⎩⎪⎪⎪⎨⎪⎪⎪⎧1−11−1x<2.52.5<x<5.55.5<x<8.5x>8.5
模型的輸出如下:
正確率為100%!是不是很神奇?
最後我們用python實現上述例子中的結果,我們像書上那樣,設置3個分類器,具體的實現代碼如下:
#導入相關的庫 import math import pandas as pd import numpy as np #輸入原始數據 x=[0,1,2,3,4,5,6,7,8,9] y=[1,1,1,-1,-1,-1,1,1,1,-1] T=3 #設置分類器個數 #初始化樣本權值分布函數 def func_w_1(x): w_1=[] for i in range(len(x)): w_1.append(0.1) return w_1 #生成阈值函數 def func_threshs(x): threshs =[i-0.5 for i in x] threshs.append(x[len(x)-1]+0.5) return threshs #根據阈值生成22種分類器的輸出 def func_cut(threshs): y_pres_all={
}
y_last_all={
}
for thresh in threshs:
y_pres=[]
y_last=[]
for i in range(len(x)):
if x[i]<thresh:
y_pres.append(1)
y_last.append(-1)
else:
y_pres.append(-1)
y_last.append(1)
y_pres_all[thresh]=y_pres #前向分類器
y_last_all[thresh]=y_last #後向分類器
return y_pres_all,y_last_all
#求一個分類器誤差率e
def sub_func_e(y,w_n,y_pres_all,thresh):
e=0
for i in range(len(y)):
if y_pres_all[thresh][i]!=y[i]:
e+=w_n[i];
return e #求一類分類器誤差率 def sub_func_e_s(y,w_n,y_pres_all,threshs): e_s={
}
e_min=1 n=0 for thresh in threshs: e=sub_func_e(y,w_n,y_pres_all,thresh) e_s[thresh]=round(e,6) if e<e_min: e_min=round(e,6) n=thresh return e_s,e_min,n #求兩類分類器誤差率 def sub_func_e_all(y,w_n,y_pres_all,y_last_all,threshs): e_s1,e_min1,n1=sub_func_e_s(y,w_n,y_pres_all,threshs) e_s2,e_min2,n2=sub_func_e_s(y,w_n,y_last_all,threshs) if e_min1<=e_min2: return e_s1,e_min1,n1,y_pres_all else: return e_s2,e_min2,n2,y_last_all #輸出最佳分類器 def func_pre_n(y_all,n): pre_n=y_all[n] return pre_n #求最佳分類器的誤差率 def func_a_n(e_min): a_n=round(0.5*math.log((1-e_min)/e_min),6) return a_n #求臨時分布權值 def func_w_n_tmp(x,pre_n,w_n,a_n): w_n_tmp=[] for i in range(len(x)): w_new=round(w_n[i]*math.exp(-1*a_n*y[i]*pre_n[i]),6) w_n_tmp.append(w_new) return w_n_tmp #求Z def func_z_n(w_n_tmp): z_n=sum(w_n_tmp) return z_n #求更新後的樣本分布權值 def func_w_n(w_n_tmp,z_n): w_n=[round(i/z_n,5) for i in w_n_tmp] return w_n #求f(x) def func_g_n(x,pre_n,a_n): g_n=[] for i in range(len(x)): g_n_single=a_n*pre_n[i] g_n.append(g_n_single) return g_n #各子函數封裝 def func_AdaBoost(x,y,T): a_n_s=[] #保存分類器系數 w_n_s=[] #保存樣本分布權值 pre_n_s=[] #保存各個基分類器的輸出 e_n_s=[] #保存誤差率 g_n_s=[] #保存子分類器 n_s=[] #保存阈值 w_1=func_w_1(x) #初始化權值,都為0.1 w_n_s.append(w_1) threshs=func_threshs(x) for i in range(T): w_n=w_n_s[i] y_pres_all,y_last_all=func_cut(threshs) e_s,e_min,n,y_all=sub_func_e_all(y,w_n,y_pres_all,y_last_all,threshs) pre_n=func_pre_n(y_all,n) a_n=func_a_n(e_min) w_n_tmp=func_w_n_tmp(x,pre_n,w_n,a_n) z_n=func_z_n(w_n_tmp) w_n=func_w_n(w_n_tmp,z_n) g_n=func_g_n(x,pre_n,a_n) a_n_s.append(a_n) w_n_s.append(w_n) pre_n_s.append(pre_n) g_n_s.append(g_n) n_s.append(n) e_n_s.append(e_min) return a_n_s,w_n_s,pre_n_s,g_n_s,n_s,e_n_s #主程序 a_n_s,w_n_s,pre_n_s,g_n_s,n_s,e_n_s=func_AdaBoost(x,y,T) #列表、顯示結果 data={
'x':x,'y':y,'w_1':w_n_s[0],'pre_1':pre_n_s[0],'g_1':g_n_s[0],
'w_2':w_n_s[1],'pre_2':pre_n_s[1],'g_2':g_n_s[1],
'w_3':w_n_s[2],'pre_3':pre_n_s[2],'g_3':g_n_s[2]}
df=pd.DataFrame(data)
df['sum']=df['g_1']+df['g_2']+df['g_3']
#輸出預測值
df['G(x)']=np.sign(df['sum'])
df.T
程序的輸出結果如下:
備注:以上代碼參考b站up主“致敬大神”,大家都去點波關注啊,哈哈哈,溜了溜了,有問題可以留言。