AdaBoost演算法的原理与实现

导语

AdaBoost演算法与SVM演算法通常被认为是有监督学习中最强大的两种演算法。上一节讲义中对SVM演算法进行了深入讲解，本节对AdaBoost演算法进行讲解，重点在于理解该演算法的原理，并用python对其进行实现。

1 AdaBoost演算法

AdaBoost的全称是Adaptive Boosting，是「自适应增强」的意思。AdaBoost演算法的本质，是用来提升分类器的分类性能。它用什么方法来提升呢？有两个途径：

（1）集成的方法。一个分类器性能不好，就通过组合多个分类器来完成，也就是俗语「三个臭皮匠顶一个诸葛亮」的意思。每个基分类器都是弱分类器，通过集成的方法，加权组合成一个强分类器。这就是Boosting的内涵。

（2）自适应的方法。在训练各个基分类器时，采用顺序生成的方法。前一轮训练中被基分类器错分的样本，会在训练下一个基分类器中得到增强，即在每一轮训练中加大上一轮中错分样本的权重，这就是Adaptive的内涵。

注释1：:弱分类器的「弱」的意思，即分类器的分类性能比随机猜测略好，也好不了多少，在二分类的情况下，错误率可能会高于50%。而强分类器的错误率会低很多。

了解AdaBoost演算法内涵之后，可以发现它主要包括以下几部分：

（1）设计基分类器。你可以根据所处理数据的特点选择弱分类器，决策树、kNN、logistic回归方法等等都可以作为弱分类器。一般来说，作为弱分类器，简单的分类器效果会更好一些。

（2）训练基分类器。一开始，训练数据集中的样本权重初始化为相等值。训练过程中，某个样本分类如果被分错了，则它在下一个训练数据集中的权重增加，反之，分对了，它的权值就降低。权值更新后，样本集用于下一个基分类器的训练，如此迭代，直至达到某个预定的足够小的错误率或达到预先指定的最大迭代次数。（注意：训练数据集的样本值在每一轮中都是不变的，变的是这些样本的权重。）

（3）组合基分类器。训练结束后，将各个弱分类器组合成强分类器。组合的方法是，根据每个弱分类器的误差率，加权相加。即误差率小的弱分类器分配个较大权重，误差率大的弱分类器分配个较小的权重。

2 AdaBoost演算法步骤

假设有一个训练数据集有个样本点，即 $left{ (x_{1},y_{1}),(x_{2},y_{2}) ,...,(x_{n},y_{n}) ight}$ 。代表数据特征，代表对应的标签， $y_{i}inleft{+1,-1 ight}$ 。AdaBoost演算法的步骤如下：

<1> 初始化样本权重。每个样本最开始被赋予相等值，即，样本权重用向量表示，则

$egin{cases} D_{1}=(omega_{11},omega_{12},...,omega_{1n})\ omega_{1i}=frac{1}{n},quad i=1,2,...,n\ end{cases}$

其中， $D_{1}$ 代表第一轮训练的样本权重。

<2> 构建弱分类器。可以用决策树、kNN等等方法来设计弱分类器。例如，在决策树方法中，可以把最低误差率的单层决策树作为基分类器 $G_{m}(x)$ ，代表第轮迭代。

<3> 计算在第轮训练中 $G_{m}(x)$ 的误差率 $e_{m}$ 。

$e_{m}=P(G_{m}(x_{i}) e y_{i})\ quadquadquadquad=sum_{i=1}^{n}{omega_{mi}I(G_{m}(x_{i}) e y_{i})}$

可以看出， $G_{m}(x)$ 在训练数据集上的误差率 $e_{m}$ 就是被 $G_{m}(x)$ 误分类样本的权值之和。

<4> 计算 $G_{m}(x)$ 在最终分类器中的权重 $alpha_{m}$ 。

$alpha_{m}=frac{1}{2}lnfrac{1-e_{m}}{e_{m}}$

分析这个公式，当 $e_{m}leqfrac{1}{2}$ 时， $alpha_{m}geq0$ ，且 $alpha_{m}$ 随著 $e_{m}$ 的减小而增大，意味著分类误差率越小的基分类器在最终分类器中的作用越大。

<5> 更新样本权重 $D_{m+1}$ ，用于下一轮迭代。

$egin{cases} D_{m+1}=(omega_{m+1,1},omega_{m+1,2},...,omega_{m+1,n})quadquad quad \ omega_{m+1,i}=frac{omega_{m,i}cdot e^{-alpha_{m}y_{i}G_{m}(x_{i})}}{Z_{m}},quad i=1,2,...,n\ Z_{m}=sum_{i=1}^{n}{omega_{m,i}cdot e^{-alpha_{m}y_{i}G_{m}(x_{i})}}quad quad quad quad quad quad end{cases}$

其中， $Z_{m}$ 是归一化因子。可以看出，如果 $x_{i}$ 分类正确，则 $y_{i}G_{m}(x_{i})=1$ ， $omega_{m+1,i}=frac{omega_{m,i}cdot e^{-alpha_{m}}}{Z_{m}}$ ，权值变小。如果 $x_{i}$ 分类错误，则 $y_{i}G_{m}(x_{i})=-1$ ， $omega_{m+1,i}=frac{omega_{m,i}cdot e^{alpha_{m}}}{Z_{m}}$ ，权值变大。这样，在接下来的训练中，重点关注这些错分样本。

<6> 组合各个基分类器，从而得到最终分类器。

$f(x)=sum_{m=1}^{M}{alpha_{m}G_{m}(x)}$

最终分类器为

$G(x)=sign(f(x))=sign(sum_{m=1}^{M}{alpha_{m}G_{m}(x)})$

至此，AdaBoost演算法结束。

3 AdaBoost演算法的实现

下面，我们用python对AdaBoost演算法进行实现。数据导入的函数就不再罗嗦了，在上一节中有，大同小异。重点聚焦构建弱分类器和用AdaBoost提升分类器性能，这是AdaBoost演算法的核心。

（1）构建弱分类器。可以根据需要构建任意类型的弱分类器，单层决策树（decision stump）是AdaBoost比较流行的弱分类器，我们以此为例，直接上代码。

def stumpClassify(dataMatrix,dimen,threshVal,threshIneq): """ 单层决策树分类函数 """ retArray = ones((shape(dataMatrix)[0],1)) if threshIneq == lt: retArray[dataMatrix[:,dimen] <= threshVal] = -1.0 else: retArray[dataMatrix[:,dimen] > threshVal] = -1.0 return retArray

在单层决策树函数中，参数dataMatrix表示输入的数据矩阵；dimen表示第dimen列，也就是第几个特征；threshVal表示阈值，在这个阈值两侧，取不同的分类；threshIneq是定义的一个标志位，当它为lt（less than）时，则小于阈值的是-1类，大于阈值的是+1类，当它取其它值时，则大于阈值的取-1类，小于阈值的是+1类。

def buildStump(dataArr,classLabels,D): """ 根据给定的权值向量D,寻找数据集上的最佳单层决策树,作为弱分类器 """ dataMatrix = mat(dataArr); labelMat = mat(classLabels).T m,n = shape(dataMatrix) numSteps = 10.0; bestStump = {}; bestClasEst = 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]: #lt(less than),gt(greater than) 都考虑到 threshVal = (rangeMin + float(j) * stepSize) #计算阈值 predictedVals = stumpClassify(dataMatrix,i,threshVal,inequal) errArr = mat(ones((m,1))) #初始化误差矩阵为单位矩阵 errArr[predictedVals == labelMat] = 0 #分类正确,误差矩阵对应值为0 weightedError = D.T*errArr #计算误差 #print "split: dim %d, thresh %.2f, thresh ineqal: %s, the weighted error is %.3f" % (i, threshVal, inequal, weightedError) if weightedError < minError: #找到最小误差分类方式 minError = weightedError bestClasEst = predictedVals.copy() bestStump[dim] = i bestStump[thresh] = threshVal bestStump[ineq] = inequal return bestStump,minError,bestClasEst

该函数的输入参数dataArr表示数据矩阵，classLabels表示对应的标签，D为权值向量。返回参数bestStump为一个字典，保存了最佳单层决策树信息，minError代表最小误差，bestClasEst表示最佳分类结果。

（2）AdaBoost演算法训练弱分类器。

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/D.sum() #计算训练误差, 当误差为0时, 跳出循环 aggClassEst += alpha*classEst print "aggClassEst: ",aggClassEst.T aggErrors = multiply(sign(aggClassEst) != mat(classLabels).T,ones((m,1))) errorRate = aggErrors.sum()/m print "total error: ",errorRate if errorRate == 0.0: break return weakClassArr,aggClassEst

AdaBoost演算法的输入参数为训练样本数据，对应的类标签，以及最大迭代次数numIt。返回参数weakClassArr为保存的所有弱分类器信息，aggClassEst为每次迭代后输出的类别值乘以该决策树的权重，然后累加。根据它的符号可以判断最终类别，即如果大于0则为+1类，小于0则为-1类。

这样，我们就得到了多个分类器，以及对应的权重。将这些分类器加权求和，就可得到最终的分类器。此时如果用新的测试样本，对该分类器性能进行测试，就非常容易了。

def adaClassify(datToClass,classifierArr): """ 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)

至此，AdaBoost演算法就介绍完了。回顾一下，它的作用是提升分类器的性能。基本思想就是在训练基分类器的过程中，不断自适应调整样本权重，将分类重点放在难分类的数据上，最后根据所有基分类器的误差率加权组合成最终的分类器。