1：简单概念描述

       Adaboost是一种弱学习算法到强学习算法，这里的弱和强学习算法，指的当然都是分类器，首先我们需要简单介绍几个概念。

1：弱学习器：在二分情况下弱分类器的错误率会高于50%。其实任意的分类器都可以做为弱分类器，比如之前介绍的KNN、决策树、Na?ve Bayes、logiostic回归和SVM都可以。这里我们采用的弱分类器是单层决策树，它是一个单节点的决策树。它是adaboost中最流行的弱分类器，当然并非唯一可用的弱分类器。即从特征中选择一个特征来进行分类，该特征能是错误率达到最低，注意这里的错误率是加权错误率，为错分样本(1)与该样本的权重的乘积之和(不明白看后面代码)。

2：强学习器：识别准确率很高并能在多项式时间内完成的学习算法

3：集成方法：就是将不同的分类器组合在一起，这种组合的结果就是集成方法或者称为元算法。它可以是不同算法的集成，也可以是同一算法在不同设置下的集成，还可以是数据集的不同部分分配给不同分类器后的集成。

4：通常的集成方法有bagging方法和boosting方法，adaboost是boosting的代表算法，他们的区别在于：bagging方法(bootstrapaggregating)，中文为自举汇聚法，是从原始数据集选择得到S个新数据集的一种技术，S个新数据集样本总和与原数据集数目相等，这样就可以得到S个分类器，再对这S个分类器进行叠加，他们的权重都相等，这样就可以得到一个强学习器。而boosting方法是通过集中关注被已有分类器错分的那些数据来获得新的分类器，boosting算法中分类的权重并不相等，每个权重代表的是其对应分类器在上一轮迭代中的成功度。这里不是太明白的话，看完后面adaboost算法就会明白这句话的含义。

5：adaboost算法：机器学习实战这本书上的描述和论文中的描述是一致的，见下面(前两幅是书中描述，后一副是论文中描述)。

2:python代码的实现

(1)   基于单层决策树构建分类器

def loadSimDat():
    dataMat = matrix([[1, 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 dataMat, classLabels

# 单层决策树生成函数
def stumpClassify(dataMatrix,dimen,threshVal,threshIneq):#just classify the data
    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
    m,n = shape(dataMatrix)
    numSteps = 10.0; bestStump = {}; bestClassEst = 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']:
                threshVal = (rangeMin + float(j)*stepSize)
                predictedVals = stumpClassify(dataMatrix, i, threshVal, inequal)
                errArr = mat(ones((m,1)))
                errArr[predictedVals == labelMat] = 0
                weightedError = D.T * errArr           #这里的error是错误向量errArr和权重向量D的相应元素相乘得到的即加权错误率
                #print "split: dim %d, thresh %.2f, thresh inequal: %s, the weighted error is %.3f" %(i, threshVal, inequal, weightedError)
                if weightedError < minError:
                    minError = weightedError
                    bestClassEst = predictedVals.copy()
                    bestStump['dim'] = i
                    bestStump['thresh'] = threshVal
                    bestStump['ineq'] = inequal
    return bestStump, minError, bestClassEst

注意这里有三层循环构建了单层决策树，最外层循环为遍历特征，次外层循环为遍历的步长，最内层为是否大于或小于阀值。构建的最小错误率为加权错误率。

(2)   完整adaboost算法

# 基于单层决策树的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.sum()            # 归一化用的
        aggClassEst += alpha * classEst    #累加变成强分类器
        aggErrors = multiply(sign(aggClassEst) != mat(classLabels).T, ones((m,1)))
        errorRate = aggErrors.sum()/m
        print "total error: ", errorRate, "\n"
        if errorRate == 0.0: break
    return weakClassArr, aggClassEst

注意代码中的一个技巧max(error,le-16)用于确保在没有错误时不会发生除零溢出。

(3)   测试算法：基于adaboost的分类

#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)

3:案例—从疝气病症预测病马的死亡率

# 案例-通过马疝病预测马的死亡率
def loadDataSet(fileName):      #general function to parse tab -delimited floats
    numFeat = len(open(fileName).readline().split('\t')) #自动检测特征的数目
    dataMat = []; labelMat = []
    fr = open(fileName)
    for line in fr.readlines():
        lineArr =[]
        curLine = line.strip().split('\t')
        for i in range(numFeat-1):
            lineArr.append(float(curLine[i]))
        dataMat.append(lineArr)
        labelMat.append(float(curLine[-1]))
    return dataMat,labelMat

注意上图中会发现在错误率达到了一个最小值之后又开始上升，这种现象称之为过拟合现象。

注明：1：本笔记来源于书籍<机器学习实战>

2：参考blog：http://blog.csdn.net/haidao2009/article/details/7514787

作者：小村长  出处：http://blog.csdn.net/lu597203933 欢迎转载或分享，但请务必声明文章出处。 （新浪微博：小村长zack, 欢迎交流！）