利用AdaBoost元算法提高分类器性能

bagging与boosting

bagging(bootstrap aggregating)自举汇聚法，从原始数据集中选择S次后得到S个新数据集的一种技术。，新数据集和原始数据集大小相等。每个数据集都是在原始数据集中随机选择一个样本来进行替换而得到（允许有重复值），将某个学习算法分别作用于每个数据集就得到S个分类器，对新数据进行分类时，选择分类器投票结果中最多的类别作为最后的分类结果！

boosting，与bagging类似，只不过boosting不同的分类器是通过串行训练而获得的，每个新分类器都根据已训练出的分类器性能来进行训练，通过集中关注被已有分类器错分的那些数据来获得新的分类器。

不同：bagging中的分类器权重是相等的，而boosting中的分类器权重并不相等，每个权重代表的是其对应分类器在上一轮迭代中的成功度。

下面讲的是最流行的版本AdaBoost（adptive boosting）自适应boosting.

训练算法

赋予训练集数据中的每个样本一个权重，这些权重构成向量D,开始将权重都初始化为相等值。首先在分类器上训练出一个弱分类器并计算该分类器的错误率，然后在同一数据集上再次训练弱分类器。在分类器的第二次训练当中，调整每个样本的权重，第一次分对的的样本的权重降低，错分样本的权重提高。为了从所有弱分类中得到最终的分类结果，AdaBoost为每个分类器都分配了权重值alpha,其是基于每个分类器的错误率进行的。错误率定义为：ε=未成功分类的样本数目/所有样本数目

alpha的计算公式如下：α=1/2(ln((1-ε)/ε))

计算alpha后可以对向量D更新以使正确分类的样本权重降低，错分样本的权重升高。对于正确分类的样本，权重更新为：D_i=(D_ie^-α)/sum(D);错分的样本权重更新为：D_i=(D_ieα)/sum(D)--------ps:在这里编辑公式要命呀！--------计算出D之后进行下一轮迭代，知道训练错误率为0或弱分类器的数目达到用户指定值为止。

基于单层决策树构建弱分类器

（还记得决策树么？见http://www.cnblogs.com/woshikafeidouha/p/3573730.html）

单层决策树，仅基于单个特征来做决策，只有一次分裂过程，实际上就是一个树桩！

兵马未动，粮草先行。准备数据集：

 1 from numpy import *
 2 
 3 def loadSimpData():
 4     dataMat=matrix([[1.,2.1],
 5         [2.,1.1],
 6         [1.3,1.],
 7         [1.,1.]
 8         [2.,1.]
 9         ])
10     classLabels=[1.0,1.0,-1.0,-1.0,1.0]
11     return dataMat,classLabels

构建单层决策树：

将最小错误率minError设为+∞

对数据集中的每一个特征（第一层循环）：

　　对每个步长（第二层循环）：

　　　　对每个不等号（第三层循环）：

　　　　　　建立一颗单层决策树并利用并利用加权数据集对它进行测试

　　　　　　如果错误率小于minError，则将当前单层决策树设为最佳单层决策树

返回最佳单层决策树

看代码：

def stumpClassify(dataMatrix,dimen,threshVal,threshIneq):#预测类别函数
　　retArry=ones((shape(dataMatrix)[0],1))
　　if(threshIneq==‘lt‘):
　　　　retArry[dataMatrix[:,dimen]<=threshVal]=-1.0
　　else:
　　　　retArry[dataMatrix[:,dimen]>threshVal]=-1.0
　　return retArry

完整的AdaBoost算法实现

对每次迭代：

　　利用bulidStump（）函数找到最佳决策树

　　将最佳单层决策树加入到单层决策树组

　　计算alpha

　　j计算新的权重D

　　更新累计类别估计值

　　如果错误率为0.0，则推出循环。

def adaBoostTrainDS(dataArr,classLabels,numIt=40):
　　weakClassArr=[]
　　m=shape(dataArr)[0]
　　D=mat(ones((m,1))/m)
　　aggClassEst=mat(zeros((m,1)))
　　for i in range(numIt):
　　　　bestStump,error,classEst=buildStump(dataArr,classLabels,D)
　　　　print "D:",D.T
　　　　alpha=float(0.5*log((1.0-error)/max(error,1e-16)))
　　　　bestStump[‘alpha‘]=alpha
　　　　weakClassArr.append(bestStump)
　　　　print "classEst:",classEst.T
　　　　expon=multiply(-1*alpha*mat(classLabels).T,classEst)
　　　　D=multiply(D,exp(expon))
　　　　D=D/D.sum()
　　　　aggClassEst+=alpha*classEst
　　　　print ‘aggClassEst‘,aggClassEst
　　　　aggError=multiply(sign(aggClassEst)!=mat(classLabels).T,ones((m,1)))
　　　　errorRate=aggError.sum()/m
　　　　print "total error:",errorRate,"\n"
　　　　if errorRate==0.0:
　　　　break
　　return weakClassArr

在这里疑惑有二：其一，对D的处理貌似不是公式所给的那样，反正公式书上解释的也不太清晰，各个字母的含义都没有；其二，对于维持aggClassEst这么一个变量的意义搞不太明白，什么叫运行时类别估计值，难道classEst不是么？没想明白。

先忽略这些细节继续往下看。

测试算法：基于AdaBoost的分类

def adaClassify(datToClass,classifierArr):
　　dataMatrix = mat(datToClass)#do stuff similar to last aggClassEst in adaBoostTrainDS
　　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
　　print aggClassEst
　　return sign(aggClassEst)

利用AdaBoost元算法提高分类器性能,布布扣,bubuko.com

利用AdaBoost元算法提高分类器性能

原文：http://www.cnblogs.com/woshikafeidouha/p/3583275.html