AdaBoost 自适应增强学习算法原理

论坛从7月份开始正式关闭，

论坛成立至今刚好三年，三年时间说长不长，说短也不短，

关闭是为了下一次更好的相见，

最后在这里感谢曾经为此付出过的朋友；

一、AdaBoost算法介绍

AdaBoost是adaptive boosting的缩写，全称为自适应增强学习，属于集成学习中的一种，其主要思想是弱分类器等价于强分类器；

计算方式主要是通过不断迭代两组权重，最终使得若干弱分类器组成的强分类器误差达到最小，

两组权重分别是：

a、样本权重，每个样本点给予一个权重，初始化权重为1/n (n为样本量数量);

b、弱分类器权重a(m)，每个弱分类器同样给予一个权重；

先来看一下两组权重的更新公式

a、样本权重更新公式 (其中Z是归一化因子，Gm(x)为弱分类器)

b、弱分类器权重更新公式

e^x的图像

从样本点的更新公式及结合e^x的图像可知：

当弱分类器分类正确时，样本点权重会越来越小，当弱分类器分类错误时，该样本点权重会越来越大；

二、AdaBoost的推导过程

1、损失函数

损失函数即需使得分类错误的样本数量达到最少，

从样本权重更新公式中可以看到当分类器分类错误时，刚有G(x)*y(i)

进一步得到

即只需要使得每一轮的归一化因子Zm最小，因此损失函数如下所示

2、求解损失函数的系数a

因为Zm是归一化因子，其更新公式为：

从上式以及当y=G(x)、不相等以及样本权重和为1，正确分类权重为(1-em),错误分类的样本权重为em可得Zm如下结果，简化后直接对Zm关于am求导等于0即可得到am的值；

转化一下可得

3、Zm的求解

将am的结果代入Zm中即可得出如下结果

4、样本点的权重更新

当样本正确分类时有y*G(x)=1,即有样本更新公式

当样本错误分类时有y*G(x)=1,即有样本更新公式

三、实例计算

以《机器学习实战》实例为例

总共5个样本，其中3个为正样本，2个为负样本

样本集分布

3.1 初始化每个样本权重

D1初始化权重

3.2 寻找单决策树最佳分类器

3.2.1 首先从x1上找最佳分类器

本案例上从样本分布图可以看到，当在x1上处于1.3-2.0之间的分类器都可以作为单决策树最佳分类器

那么只需要随机选择其中一个弱分类器就可以，那么通过计算的执行顺序可以选择1.3作为x1上的最佳分类器

当我们选择小于1.3的样本为负样本时，可以看到只有左上角的样本分类错误，即em=0.2

则a1=In((1-em)/em)=0.6931

得到D2的权重如下所示：

3.2.2 从x2上找最佳分类器

从x2上寻找最佳分类器，从下图可以看出，x2在1.0-1.1之间任选一个分类器均可，那么同样，选择大于1.0作为x2的最佳分类器

从图中可以看到第5个样本点是误分类点；

计算a2=1/2*ln((1-em)/em)=1/2*ln((1-0.125)/0.125)=0.9729

D3相应的样本权重如下所示：

可以得到最终的模型为

G(x1) 如果x1小于1.3，则为-1，否则为1

G(x2) 如果x2小于1，则为-1，否则为1

最终模型,其中sign为指示函数

将5个样本点代入检验可得

可以明显看到，5个样本点已经相应分开，如果将sign定义为1的为正类，那么最终分类结果的误差为0~

四、Python实现

importnumpyasnp

defloadSimpData():

dataMat=np.matrix([[1,2.1],[2,1.1],[1.3,1],[1,1],[2,1]])

classLabels=[1,1,-1,-1,1]

returndataMat,classLabels

defstumpClassify(dataMatrix,dimen,threshVal,threshIneq):

retArray=np.ones((dataMatrix.shape[],1))

ifthreshIneq=='lt':

retArray[dataMatrix[:,dimen]

else:

retArray[dataMatrix[:,dimen]>threshVal]=-1

returnretArray

defbuildStump(dataArr,classLable,D):

dataMatrix=np.mat(dataArr)

labelMat=np.mat(classLable).T

m,n=np.shape(dataMatrix)

numSteps=10

bestStump={}

bestClasEst=np.mat(np.zeros((m,1)))

minError=np.inf

foriinrange(n):

rangeMin=dataMatrix[:,i].min()

rangeMax=dataMatrix[:,i].max()

stepsize=(rangeMax-rangeMin)/numSteps

forjinrange(-1,int(numSteps)+1):

forinequalin['lt','gt']:

threshVal=(rangeMin+float(j)*stepsize)

predictedVals=stumpClassify(dataMatrix,i,threshVal,inequal)

errArr=np.mat(np.ones((m,1)))

errArr[predictedVals==labelMat]=

weightedError=D.T*errArr

ifweightedError

minError=weightedError

bestClasEst=predictedVals.copy()

bestStump['dim']=i

bestStump['thresh']=threshVal

bestStump['ineq']=inequal

returnbestStump,minError,bestClasEst

defadaBoostTrainDS(dataArr,classLabels,numIt=40):

weakClassArr=[]

m=dataArr.shape[]

D=np.mat(np.ones((m,1))/m)

aggClassEst=np.mat(np.zeros((m,1)))

foriinrange(numIt):

bestStump,error,classEst=buildStump(dataArr,classLabels,D)

alpha=float(0.5*np.log((1-error)/error))

bestStump['alpha']=alpha

weakClassArr.append(bestStump)

expon=np.multiply(-1*alpha*np.mat(classLabels).T,classEst)

D=np.multiply(D,np.exp(expon))

print(D/D.sum())

D=D/D.sum()

aggClassEst+=alpha*classEst

aggErrors=np.multiply(np.sign(aggClassEst)!=np.mat(classLabels).T,np.ones((m,1)))

errorRate=aggErrors.sum()/m

print("total error:",errorRate)

iferrorRate==0.0:break

returnweakClassArr,aggClassEst

dataMat,classLabels=loadSimpData()

classifierArr=adaBoostTrainDS(dataMat,classLabels)

print(classifierArr)

五、参考信息：

《机器学习实战》

《统计学习方法》

由于水平有限，请参照指正