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)

五、参考信息:

《机器学习实战》

《统计学习方法》

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

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180707G1A3HB00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码关注腾讯云开发者

领取腾讯云代金券