摘要
1。 AdaBoost元演算法
2。 AdaBoost元演算法誤差分析
3。 程式碼實現與解釋
AdaBoost演算法
AdaBoost演算法是整合學習的一種。
整合學習就是構建多個“基學習器”,之後再將它們結合來完成學習任務的方法。整合學習透過將多個學習器進行綜合,其效能通常比單個學習器要好。我們之前提過的隨機森林就是整合學習的一種。
Adaboost演算法:先從初始訓練集合中訓練出一個基學習器,再根據基學習器的表現對訓練樣本的權重進行調整,使得先前基學習器做錯的樣本在後續得到更多的關注,然後基於調整後的樣本權重來訓練下一個基學習器,直到基學習器的數目達到事先指定的數目M,最終將這M個學習器進行加權組合。
首先我們假設給定一個二分類的訓練資料集:
其中
,
。
初始化樣本的權重為:
第m個基分類器的樣本權重為:
我們構建M個基學習器,最終的學習器即為基學習器的線性組合:
其中
為第i個基學習器的係數,
為第i個基學習器。
接下來我們定義
在訓練集合中的分類誤差率為:
也就是說
在加權訓練資料集中的分類誤差率為被誤分類的樣本權值之和。注意一下,我們定義的基學習器,其
。。
接著我們定義損失函式為指數損失函式:
其中y是樣本的實際類別,f(x)是預測的類別,樣本x的權重服從D分佈。E代表求期望。
損失函式為什麼這樣定義?下面一起證明一下:
若f(x)能使損失函式最小化,那我們考慮上式對f(x)的偏導為零:
令上式為零,得:
因此,有
當P(y=1|x)>P(y=-1|x)時,sign(f(x))=1
當P(y=1|x)>P(y=-1|x)時,sign(f(x))=-1
這樣的分類規則正是我們所需要的,若指數函式最小化,則分類錯誤率也最小,它們倆是一致的。所以我們的損失函式可以這樣定義。
定義完了損失函式,我們看怎麼來進行基分類器
和係數
的求取。
第一個分類器G1(x)是直接將基學習演算法用於初始資料分佈求得,之後不斷迭代,生成
和
。當第m個基分類器產生後,我們應該使得其在資料集第m輪樣本權重基礎上的指數損失最小,即
首先,我們求解
,對任意的
,最優的
應為:
其中
是第m輪訓練樣本的權重。
就是在第m輪中使得加權訓練樣本誤差率最小的分類器。
在得到
後,我們來求
。
應該使得損失函式最小,所以令下式對
求導等於零:
得到
的表示式:
由於
,所以
,且
隨著
的減小而增大。
這時候我們就可以得到Adaboost的迭代公式:
這時候就只剩下最後一個問題,之前說,我們會根據基學習器的表現對訓練樣本的權重進行調整,使得先前基學習器做錯的樣本在後續得到更多的關注。那訓練樣本的權重分佈
應該怎麼變化呢?
這一部分在周志華老師《機器學習》P175有詳細的推導,感興趣的讀者可以自行查閱。我這裡直接給出
的迭代公式,並證明其可行性。
其中
,是一個常數。
上面就是樣本權重
的迭代公式。我們發現:
當
時:
當
時:
由於
,從上面的式子可以看到,當樣本i上一次被誤分類時,其下一次的權重
會變大;而當樣本i上一次被分類正確時,其下一次的權重
會變小。因此,誤分類樣本在下一輪學習中起到的作用更大,這也是Adaboost的一個特點。
以上就是Adaboost演算法原理部分的全部內容,從基學習器到其係數,再到資料集合的權重迭代,我們都給出了較為詳細的公式推導。希望給大家一些幫助。
Adaboost演算法的誤差
先給大家結論:隨著整合學習中個體分類器數目的增加,其整合的錯誤率將成指數級下降,最終趨向於零。
當然,如果分類器數目過多也會發生過擬合現象,導致分類器的泛化能力不強,所以我們應該在其中尋求一種平衡。
關於演算法誤差這個點,李航老師《統計學習方法》P142和周志華老師《機器學習》P172頁都有解釋。李航老師的證明更為詳細。周志華老師的證明用到了Hoeffding不等式。
最終得到的不等式:
我們發現,隨著個體分類器數目的增加,其整合的錯誤率將成指數級下降。當然前提條件是每個基分類器的分類正確率要高於50%,即
。
程式碼實現與註釋
在下面的程式中,基分類器選用的是決策樹,但是基分類器可以選取我們所知道的任意一個分類器都可以,比如神經網路等。
1。單層決策樹生成函式
程式清單:
from
numpy
import
*
# 載入資料
def
loadsimpData
():
dataMat
=
matrix
([[
1
,
2。1
],
[
2
,
1。1
],
[
1。3
,
1
],
[
1
,
1
],
[
2
,
1
]])
classLabels
=
[
1
,
1
,
-
1
,
-
1
,
1
]
return
dataMat
,
classLabels
# 單層決策樹生成函式
# dimen是哪一個特徵;threshVal是特徵閾值;threshIneq是大於還是小於
def
stumpClassify
(
dataMatrix
,
dimen
,
threshVal
,
threshIneq
):
# 初始化一個全1列表
retArray
=
ones
((
shape
(
dataMatrix
)[
0
],
1
))
if
(
threshIneq
==
‘lt’
):
# 以閾值劃分後,小於等於閾值的,類別定為-1
retArray
[
dataMatrix
[:,
dimen
]
<=
threshVal
]
=-
1。0
else
:
retArray
[
dataMatrix
[:,
dimen
]
>
threshVal
]
=-
1。0
return
retArray
# D是權重向量
def
buildStump
(
dataArr
,
classLabels
,
D
):
dataMatrix
=
mat
(
dataArr
);
labelMat
=
mat
(
classLabels
)
。
T
m
,
n
=
shape
(
dataMatrix
)
numSteps
=
10。0
;
bestStump
=
{};
bestClassEst
=
mat
(
zeros
((
m
,
1
)))
# 最小值初始化為無窮大
minError
=
inf
# 對每一個特徵
for
i
in
range
(
n
):
# 找到最大值和最小值
rangeMin
=
dataMatrix
[:,
i
]
。
min
()
rangeMax
=
dataMatrix
[:,
i
]
。
max
()
# 確定步長
stepSize
=
(
rangeMax
-
rangeMin
)
/
numSteps
for
j
in
range
(
-
1
,
int
(
numSteps
)
+
1
):
for
inequal
in
[
‘lt’
,
‘gt’
]:
# 得到閾值
threshVal
=
(
rangeMin
+
float
(
j
)
*
stepSize
)
# 呼叫函式,並得到分類列表
predictedVals
=
stumpClassify
(
dataMatrix
,
i
,
threshVal
,
inequal
)
# 初始化errArr
errArr
=
mat
(
ones
((
m
,
1
)))
# 將errArr中分類正確的置為0
errArr
[
predictedVals
==
labelMat
]
=
0
# 計算加權錯誤率
weightedError
=
D
。
T
*
errArr
# print(“split:dim %d,thresh %。2f,thresh inequal:”
# “%s,the weighted error is %。3f”%(i,threshVal,
inequal
,
weightedError
))
# 如果錯誤率比之前的小
if
(
weightedError
<
minError
):
minError
=
weightedError
# bestClassEst中是錯誤最小的分類類別
bestClassEst
=
predictedVals
。
copy
()
bestStump
[
‘dim’
]
=
i
bestStump
[
‘thresh’
]
=
threshVal
bestStump
[
‘ineq’
]
=
inequal
return
bestStump
,
minError
,
bestClassEst
2。基於單層決策樹的Adaboost訓練過程
程式清單:
# 基於單層決策樹的Adaboost訓練過程
# numIt表示最多迭代的次數
def
adaBoostTrainDS
(
dataArr
,
classLabels
,
numIt
=
40
):
weakClassArr
=
[]
m
=
shape
(
dataArr
)[
0
]
# 初始化權重矩陣D,1/m
D
=
mat
(
ones
((
m
,
1
))
/
m
)
# 初始化,aggClassEst裡面存放的是類別估計的累計值
aggClassEst
=
mat
(
zeros
((
m
,
1
)))
for
i
in
range
(
numIt
):
bestStump
,
error
,
classEst
=
buildStump
(
dataArr
,
classLabels
,
D
)
(
“D:”
,
D
。
T
)
# 計算分類器的係數;max()的作用是防止error=0
alpha
=
float
(
0。5
*
log
((
1。0
-
error
)
/
max
(
error
,
1e-16
)))
bestStump
[
‘alpha’
]
=
alpha
weakClassArr
。
append
(
bestStump
)
(
“classEst:”
,
classEst
。
T
)
# 下面三行是對權重向量進行更新,具體公式推導見正文
expon
=
multiply
(
-
1
*
alpha
*
mat
(
classLabels
)
。
T
,
classEst
)
D
=
multiply
(
D
,
exp
(
expon
))
D
=
D
/
D
。
sum
()
# 計算類別估計的累加值
aggClassEst
+=
alpha
*
classEst
(
‘aggClassEst:’
,
aggClassEst
。
T
)
# 計算分類錯誤的個數
aggErrors
=
multiply
(
sign
(
aggClassEst
)
!=
mat
(
classLabels
)
。
T
,
ones
((
m
,
1
)))
# 計算分類錯誤率
errorRate
=
aggErrors
。
sum
()
/
m
(
“total error:”
,
errorRate
,
“
\n
”
)
# 如果分類錯誤率為0,則結束
if
(
errorRate
==
0
):
break
# 返回建立的分類器列表
return
weakClassArr
3。Adaboost分類函式
程式清單:
# adaBoost分類函式
# datToClass是待分類資料;classifierArr是建立好的分類器列表
def
adaClassify
(
datToClass
,
classifierArr
):
dataMatrix
=
mat
(
datToClass
)
m
=
shape
(
dataMatrix
)[
0
]
aggClassEst
=
mat
(
zeros
((
m
,
1
)))
# 對每一個弱分類器
for
i
in
range
(
len
(
classifierArr
)):
# 得到分類類別
classEst
=
stumpClassify
(
dataMatrix
,
classifierArr
[
i
][
‘dim’
],
classifierArr
[
i
][
‘thresh’
],
classifierArr
[
i
][
‘ineq’
])
# 計算類別估計累加值
aggClassEst
+=
classifierArr
[
i
][
‘alpha’
]
*
classEst
(
aggClassEst
)
# 返回類別;sign(x)函式:x>0返回1;x<0返回-1;x=0返回0
return
sign
(
aggClassEst
)
# 自適應資料載入函式
def
loadDataSet
(
fileName
):
# 得到特徵數目
numFeat
=
len
(
open
(
fileName
)
。
readline
()
。
split
(
‘
\t
’
))
dataMat
=
[];
labelMat
=
[]
fr
=
open
(
fileName
)
for
line
in
fr
。
readlines
():
lineArr
=
[]
curLine
=
line
。
strip
()
。
split
(
‘
\t
’
)
# 對每一個特徵
for
i
in
range
(
numFeat
-
1
):
lineArr
。
append
(
float
(
curLine
[
i
]))
dataMat
。
append
(
lineArr
)
labelMat
。
append
(
float
(
curLine
[
-
1
]))
# 返回特徵矩陣和類別矩陣
return
dataMat
,
labelMat
以上就是Adaboost演算法的全部內容,下一節我們一起學習線性迴歸、區域性加權線性迴歸和收縮方法。
宣告
最後,所有資料均本人自學整理所得,如有錯誤,歡迎指正,有什麼建議也歡迎交流,讓我們共同進步!轉載請註明作者與出處。
以上原理部分主要來自於《機器學習》—周志華,《統計學習方法》—李航,《機器學習實戰》—Peter Harrington。程式碼部分主要來自於《機器學習實戰》,程式碼用Python3實現,這是機器學習主流語言,本人也會盡力對程式碼做出較為詳盡的註釋。