Machine Learning in Action -- AdaBoost

初始的想法就是，结合不同的分类算法来给出综合的结果，会比较准确一些  称为ensemble methods or meta-algorithms，集成方法或元算法

集成方法有很多种，可以是不同算法之间的，也可以是同一个算法但不同参数设置之间的，也可以是将数据集分成多分给不同的分类器之间的  总的来说，有3个维度可以进行集成，算法，算法参数和数据集

下面简单介绍两种比较流行的元算法思路，

1. Building classifiers from randomly resampled data: bagging

bagging又称为bootstrap aggregating  想法比较简单，对大小为n的训练集做n次放回随机抽样，形成新的大小仍然为n的训练集  因为是放回随机抽样，新的训练集中可能有重复，某些训练集中的样本中新的训练集中也会没有  用这个方法，产生s个新的训练集，对同一个分类算法可以产生s个不同参数的分类器  使用时，让s个分类器，多数投票表决来决定最终的分类结果

比较典型的bagging算法，如随机森林（random forest）  首先采用bootstrap取样，用产生新的训练集生成决策树，并且用在新训练集中没有抽样到样本作为测试集  如果有S个新的训练集，就会产生S个决策树，所以称为森林  所谓随机，首先新训练集是随机抽样产生的  再者，在训练决策树的时候，每个树节点会随机选择m个特征（m<<M总特征数）  参考，http://zh.wikipedia.org/wiki/随机森林

2. Boosting

下面主要介绍Boosting中最流行的AdaBoost算法，这里主要介绍实现，理论参考前一篇

我们使用单层决策树，即decision stump 决策树桩作为弱分类器  所谓decision stump，就是只对一个特征做一次划分的单节点的决策树

这个弱分类器足够简单，但是如果直接使用，基本没用，  比如对于底下这个很简单的训练集，用一个decision stump都无法完全正确分类，试着在x轴或y轴上做一次划分

虽然无法完全正确分类，但是我们需要找到误差最小的那个decision stump  方法很简单，在x和y的取值范围内，以一定的步长，遍历比较误差

先实现stump分类，  dataMatrix，一行表示一个训练样本，每列表示一个特征  dimen，表示哪个特征  threshVal，阀值  threshIneq，对于decision stump，只存在less than或greater than

def stumpClassify(dataMatrix,dimen,threshVal,threshIneq): retArray = ones((shape(dataMatrix)[0],1)) if threshIneq == 'lt': #lt,less than retArray[dataMatrix[:,dimen] <= threshVal] = -1.0 #boolean indexing else: retArray[dataMatrix[:,dimen] > threshVal] = -1.0 return retArray

所以给定上面的参数，就是可以判断每个样本的分类是1或-1

下面给出求解最优stump分类器的算法，  参数中有个D向量，表示样本weight  因为这里是要找到加权样本误差最小的stump分类器

def buildStump(dataArr,classLabels,D): dataMatrix = mat(dataArr); labelMat = mat(classLabels).T m,n = shape(dataMatrix) numSteps = 10.0; bestStump = {}; bestClasEst = mat(zeros((m,1))) minError = inf #inf，python中表示无穷大 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']: #尝试划分的方向，less than或greater than threshVal = (rangeMin + float(j) * stepSize) predictedVals = stumpClassify(dataMatrix,i,threshVal,inequal) #进行stump分类 errArr = mat(ones((m,1))) #初始化误差为1 errArr[predictedVals == labelMat] = 0 #计算误差，将分对的误差设为0 weightedError = D.T*errArr #计算加权误差 if weightedError < minError: #如果小于minError，说明我们找到更优的stump分类器 minError = weightedError bestClasEst = predictedVals.copy() bestStump['dim'] = i bestStump['thresh'] = threshVal bestStump['ineq'] = inequal return bestStump,minError,bestClasEst

好，现在可以给出AdaBoost算法的源码，

def adaBoostTrainDS(dataArr,classLabels,numIt=40): weakClassArr = [] m = shape(dataArr)[0] #样本数 D = mat(ones((m,1))/m) #初始化样本weight，所有样本权值相等为1/m aggClassEst = mat(zeros((m,1))) #累积分类结果 for i in range(numIt): #生成多少个弱分类器 bestStump,error,classEst = buildStump(dataArr,classLabels,D) #计算最优的stump分类器 print "D:",D.T alpha = float(0.5*log((1.0-error)/max(error,1e-16))) #1.计算该分类器的权值 bestStump['alpha'] = alpha weakClassArr.append(bestStump) print "classEst: ",classEst.T expon = multiply(-1*alpha*mat(classLabels).T,classEst) D = multiply(D,exp(expon)) #2.更新样本权值 D = D/D.sum() aggClassEst += alpha*classEst #3.更新累积分类结果 print "aggClassEst: ",aggClassEst.T aggErrors = multiply(sign(aggClassEst) != #计算累积分类误差 mat(classLabels).T,ones((m,1))) errorRate = aggErrors.sum()/m print "total error: ",errorRate,"\n" if errorRate == 0.0: break #4.误差为0，算法结束 return weakClassArr

其中，

1. 计算分类器权值的公式为，

max(error,1e-16)，这个是为了防止error为0

2. 更新样本权值的公式为，

即判断正确时，减小权值，而错误时，增大权值

expon = multiply(-1*alpha*mat(classLabels).T,classEst)  -alpha×classLabel×classEst，即如果分类正确，classLable=classEst，仍然得到-alpha，否则得到alpha

3. aggClassEst

因为我们最终在分类时，是用多个弱分类器的综合结果 所以这里每生成一个弱分类器，我们就把它的分类结果加到aggClassEst上，aggClassEst += alpha*classEst

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

用于aggClassEst是float类型，所以先使用sign转换成1，-1，0  然后!= mat(classLabels).T，会产生一个boolean的向量  小技巧，这里为何要乘上一个全1的向量，因为需要把boolean类型转换为int

可以在python试下，

>>> (1 == 1) *1  1

4.最终当所有弱分类器综合误差为0时，就不需要继续迭代了

下面看看，如何用AdaBoost算法进行分类

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 print aggClassEst return sign(aggClassEst) 2014-08-28 相关资源：机器学习实战 源代码（Machine Learning in Action）