AdaBoost,是英文"Adaptive Boosting"(自适应增强)的缩写,是一种机器学习方法,由Yoav Freund和Robert
Schapire提出。AdaBoost方法的自适应在于:前一个分类器分错的样本会被用来训练下一个分类器。AdaBoost方法对于噪声数据和异常数据很敏感。但在一些问题中,AdaBoost方法相对于大多数其它学习算法而言,不会很容易出现过拟合现象。AdaBoost方法中使用的分类器可能很弱(比如出现很大错误率),但只要它的分类效果比随机好一点(比如两类问题分类错误率略小于0.5),就能够改善最终得到的模型。而错误率高于随机分类器的弱分类器也是有用的,因为在最终得到的多个分类器的线性组合中,可以给它们赋予负系数,同样也能提升分类效果。
AdaBoost把多个不同的决策树用一种非随机的方式组合起来,表现出惊人的性能!第一,把决策树的准确率大大提高,可以与SVM媲美。第二,速度快,且基本不用调参数。第三,几乎不Overfitting。我估计当时Breiman和Friedman肯定高兴坏了,因为眼看着他们提出的CART正在被SVM比下去的时候,AdaBoost让决策树起死回生!Breiman情不自禁地在他的论文里赞扬AdaBoost是最好的现货方法(off-the-shelf,即“拿下了就可以用”的意思)。(这段话摘自统计学习那些事)
AdaBoost方法是一种迭代算法,在每一轮中加入一个新的弱分类器,直到达到某个预定的足够小的错误率。每一个训练样本都被赋予一个权重,表明它被某个分类器选入训练集的概率。如果某个样本点已经被准确地分类,那么在构造下一个训练集中,它被选中的概率就被降低;相反,如果某个样本点没有被准确地分类,那么它的权重就得到提高。通过这样的方式,AdaBoost方法能“聚焦于”那些较难分(更富信息)的样本上。在具体实现上,最初令每个样本的权重都相等,对于第k次迭代操作,我们就根据这些权重来选取样本点,进而训练分类器Ck。然后就根据这个分类器,来提高被它分错的的样本的权重,并降低被正确分类的样本权重。然后,权重更新过的样本集被用于训练下一个分类器Ck。整个训练过程如此迭代地进行下去。
梦游一发,bagging方法和boosting方法是非常相像的两种算法,不论在bagging还是在boost中,说使用的多个分类器的类型都是一致的。但是boosting当中,不同的分类器是通过串行训练而获得的,每个新分类器都根据已训练处的分类器的性能来进行训练。即通过关注那些上一个分类器分错的那些数据来获得新的分类器。
而bagging方法中,训练数据都是在原始数据集中随机选择一个样本来替换得到的。这里的替换就以为这可以多次地选择同一个样本。这一性质就允许新数据集中可以有重复的值,而原数据集的某些值在新集合中则不再出现。在S个数据集建好之后,将某个学习算法分别作用于每个数据集就得到了S个分类器。当我们要对新数据进行分类时,就可以应用这S个分类器进行分类。与此同时,选择分类器投票结果中最多的类别作为最后的分类结果。
............梦游结束....................
初始化,给每个样本一个相等的权重
每次迭代的时候,建立一个弱分类器。算出其分类error,根据error算这个弱分类器的权值alpha(用于最终多个弱分类器的结果加权平均得到最终的分类器的结果,意义在于,error较小的弱分类器的结果多重视一点,反之轻视一点),然后根据这个alpha算样本的权重向量D,其原则为:分错的样本下一次迭代更加重视,权重++,分对样本的轻视一点,权重--;
再接着迭代,在新得到的D基础上找当前最佳的弱分类器。算出其分类error,根据error算这个弱分类器的权值alpha。。。以此往复。
贴个《机器学习实战上》的代码:
from numpy import * import operator def loadSimpData(): datMat = matrix([[1.0, 2.1], [2.0, 1.1], [1.3, 1.0], [1.0, 1.0], [2.0, 1.0]]) classlabels = [1.0, 1.0, -1.0, -1.0, 1.0] return datMat, classlabels 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 def buildStump(dataArr, classLabels, D): dataMatrix = mat(dataArr) labelMat = mat(classLabels).T print "classlabels:", classLabels 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 print "min:", rangeMin, "max:", rangeMax, "stepSize", stepSize for j in range(-1, int(numSteps) + 1): for inequal in ['lt', 'gt']: threshVal = (rangeMin + float(j) * stepSize) predictedVals = stumpClassify(dataMatrix, i, threshVal, inequal) errArr = mat(ones((m, 1))) errArr[predictedVals == labelMat] = 0 weightedError = D.T * errArr print "split: dim %d, thresh %.2f, thresh inequal: %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 def adaBoostTrainDS(dataArr, classLabels, numIt = 40): weakClassArr = [] m = shape(dataArr)[0] D = mat(ones((m, 1)) / m) aggClassEst = mat(ones((m, 1))) for i in range(numIt): bestStump, error, classEst = buildStump(dataArr, classLabels, D) print "D:", D.T alpha = float(0.5 * log((1 - 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() print "aggClassEst:", aggClassEst.T aggClassEst += alpha * classEst print "alpha:", alpha print "alpha * classEst :", alpha * classEst 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: break return weakClassArr