做重要决定时，大家可能都会考虑吸取多个专家而不只是一个人的意见。机器学习处理问题时又何尝不是如此？这就是元算法（meta-algorithm ) 背后的思路。元算法是对其他算法进行组合的一种方式

7.1 基于数据集多重抽样的分类器
  我们自然可以将不同的分类器组合起来，而这种组合结果则被称为集成方法（ensemblemethod)或者元算法（meta-algorithm)。使用集成方法时会有多种形式：可以是不同算法的集成，也可以是同一算法在不同设置下的集成，还可以是数据集不同部分分配给不同分类器之后的集成。

AdaBoost
  优点：泛化错误率低，易编码，可以应用在大部分分类器上，无参数调整。
  缺点：对离群点敏感。
  适用数据类型：数值型和标称型数据。

  7.1.1 bagging：基于数据随机重抽样的分类器构建方法
    自举汇聚法（bootstrap aggregating），也称为bagging方法，是在从原始数据集选择S次后得到S个新数据集的一种技术。新数据集和原数据集的大小相等。每个数据集都是通过在原始数据集中随机选择一个样本来进行替换而得到的®。这里的替换就意味着可以多次地选择同一样本。这一性质就允许新数据集中可以有重复的值，而原始数据集的某些值在新集合中则不再出现。
在S个数据集建好之后，将某个学习算法分别作用于每个数据集就得到了S个分类器。当我们要对新数据进行分类时，就可以应用这S个分类器进行分类。与此同时，选择分类器投票结果中最多的类别作为最后的分类结果。

  7.1.2 boosting
    boosting是一种与bagging很类似的技术。不论是在boosting还是bagging当中，所使用的多个分类器的类型都是一致的。但是在前者当中，不同的分类器是通过串行训练而获得的，每个新分类器都根据已训练出的分类器的性能来进行训练。boosting是通过集中关注被已有分类器错分的那些数据来获得新的分类器。
由于boosting分类的结果是基于所有分类器的加权求和结果的，因此boosting与bagging不太一样。bagging中的分类器权重是相等的，而boosting中的分类器权重并不相等，每个权重代表的是其对应分类器在上一轮迭代中的成功度。

AdaBoost的一般流程
  (1)收集数据：可以使用任意方法。
  (2)准备数据：依赖于所使用的弱分类器类型，本章使用的是单层决策树，这种分类器可以处理任何数据类型。当然也可以使用任意分类器作为弱分类器，第2章到第6章中的任一分类器都可以充当弱分类器。作为弱分类器，简单分类器的效果更好。
  (3)分析数据：可以使用任意方法。
  (4)训练算法：AdaBoost的大部分时间都用在训絲上，分类器将多次在同一数据集上训练弱分类器。
  (5)测试算法：计算分类的错误率。
  (6)使用算法：同SVM — 样，AdaBoost预测两个类别中的一个。如果想把它应用到多个类别的场合，那么就要像多类SVM中的做法一样对AdaBoost进行修改

7.2 训练算法：基于错误提升分类器的性能
  AdaBoost是adaptive（自适应boosting)的缩写，其运行过程如下：训练数据中的每个样本，并赋予其一个权重，这些权重构成了向量D。一开始，这些权重都初始化成相等值。首先在训练数据上训练出一个弱分类器并计算该分类器的错误率，然后在同一数据集上再次训练弱分类器。在分类器的第二次训练当中，将会重新调整每个样本的权重，其中第一次分对的样本的权重将会降低，而第一次分错的样本的权重将会提高。为了从所有弱分类器中得到最终的分类结果，AdaBoost为每个分类器都分配了一个权重值alpha，这些alpha值是基于每个弱分类器的错误率进行计算的。其中，错误率ε的定义为：

目

alpha的计算公式如下：

)

AdaBoost算法的流程如图7-1所示
。
  计算出alpha之后，可以对权重向量乃进行更新，以使得那些正确分类的样本的权重降低而错分样本的权重升高
如果某个样本被正确分类，那么该样本的权重更改为：

)

而如果某个样本被错分，那么该样本的权重更改为

)

在计算出D之后，AdaBoost又开始进入下一轮迭代。AdaBoost算法会不断地重复训练和调整权重的过程，直到训练错误率为0或者弱分类器的数目达到用户的指定值为止。

7.3 基于单层决策树构建弱分类器
  单层决策树（decision stump, 也称决策树桩）是一种简单的决策树。前面我们已经介绍了决策树的工作原理，接下来将构建一个单层决策树，而它仅基于单个特征来做决策。由于这棵树只有一次分裂过程，因此它实际上就是一个树桩。

数据集加载代码如下:

def loadSimpData():
    datMat = matrix([[ 1. ,  2.1],
        [ 2. ,  1.1],
        [ 1.3,  1. ],
        [ 1. ,  1. ],
        [ 2. ,  1. ]])
    classLabels = [1.0, 1.0, -1.0, -1.0, 1.0]
    return datMat,classLabels

绘制数据集代码如下:

def draw(dataSet,labelSet):
    dataSet = dataSet.A
    x1 = [];x2 = []
    y1 = [];y2 = []
    for i in range(len(labelSet)):
      if labelSet[i] == 1.0:
          x1.append(dataSet[i][0])
          y1.append(dataSet[i][1])
      else:
          x2.append(dataSet[i][0])
          y2.append(dataSet[i][1])
    axes = plt.figure().add_subplot(111)
    #正类数据集
    first = axes.scatter(x1,y1,c='red')
    #负类数据集
    second = axes.scatter(x2, y2,c='green')
    #防止出现中文乱码
    zhfont1 = matplotlib.font_manager.FontProperties(fname='C:\Windows\Fonts\simsun.ttc')
    plt.title('单层决策树测试数据',fontproperties=zhfont1)
    plt.show()

数据集如图所示:

有了数据，接下来就岢以通过构建多个函数来建立单层决策树。
第一个函数将用于测试是否有某个值小于或者大于我们正在测试的阈值。第二个函数则更加复杂一些，它会在一个加权数据集中循环，并找到具有最低错误率的单层决策树。
这个程序的伪代码看起来大致如下：
将最小错误率minError设为+00
对数据集中的每一个特征（第一层循环）：
  对每个步长（第二层循环）：
    对每个不等号（第三层循环）：
      建立一棵单层决策树并利用加权数据集对它进行测试
      如果错误率低于m in Err0r，则将当前单层决策树设为最佳单层决策树返回最佳单雇决策树

单层决策树生成函数,代码如下：

def stumpClassify(dataMatrix,dimen,threshVal,threshIneq):#just classify the data
    #构建(m,1)单位数组
    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 = {}; bestClasEst = mat(zeros((m,1)))
    minError = inf #init error sum, to +infinity
    for i in range(n):#loop over all dimensions
        #求第i个特征的最小值，最大值
        rangeMin = dataMatrix[:,i].min(); rangeMax = dataMatrix[:,i].max();
        #特征由最小值增加到最大值的步长
        stepSize = (rangeMax-rangeMin)/numSteps
        for j in range(-1,int(numSteps)+1):#loop over all range in current dimension
            for inequal in ['lt', 'gt']: #go over less than and greater than
                #分割数据集的特征值
                threshVal = (rangeMin + float(j) * stepSize)
                #得出分类数组
                predictedVals = stumpClassify(dataMatrix,i,threshVal,inequal)#call stump classify with i, j, lessThan
                #存放分类错误的数组，初始化为(m,1)单位数组
                errArr = mat(ones((m,1)))
                #通过数组过滤，将分类正确的设置为0
                errArr[predictedVals == labelMat] = 0
                #计算加权错误值
                weightedError = D.T*errArr  #calc total error multiplied by D
                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

测试截图如下:

上述单层决策树的生成函数是决策树的一个简化版本。它就是所谓的弱学习器，即弱分类算法。到现在为止，我们已经构建了单层决策树，并生成了程序，做好了过渡到完整AdaBoost算法的准备。

完整AdaBoost算法的实现

整个实现的伪代码如下：
对每次迭代：
  利用buildStump函数找到最佳的单层决策树
  将最佳单层决策树加入到单层决策树数组
  计算alpha
  计算新的权重向量D
  更新累计类别估计值
  如果错误率等于0.0,则退出循环

基于单层决策树的AdaBoost训练过程，代码如下:

def adaBoostTrainDS(dataArr,classLabels,numIt=40):
    #最佳决策树桩字典数组
    weakClassArr = []
    #获取数据集行数
    m = shape(dataArr)[0]
    D = mat(ones((m,1))/m)   #init D to all equal
    #存放预测分类数组，初始化为(m,1)维矩阵
    aggClassEst = mat(zeros((m,1)))
    for i in range(numIt):
        #获取最佳决策树桩，加权错误值，以及预测分类数组
        bestStump,error,classEst = buildStump(dataArr,classLabels,D)#build Stump
        print("D:",D.T)
        alpha = float(0.5*log((1.0-error)/max(error,1e-16)))#calc alpha, throw in max(error,eps) to account for error=0
        bestStump['alpha'] = alpha  
        weakClassArr.append(bestStump)                  #store Stump Params in Array
        print("classEst: ",classEst.T)
        expon = multiply(-1*alpha*mat(classLabels).T,classEst) #exponent for D calc, getting messy
        D = multiply(D,exp(expon))                              #Calc New D for next iteration
        D = D/D.sum()
        #calc training error of all classifiers, if this is 0 quit for loop early (use break)
        aggClassEst += alpha*classEst
        #print "aggClassEst: ",aggClassEst.T
        #sign(x)函数表示x>0,返回0;x=0,返回0;x<0;返回-1
        #sign(aggClassEst) != mat(classLabels) 返回bool矩阵,对应元素相等则为True,不等则为False
        #multiply(),False相当于0，True相当于1，表示累加分类错误个数
        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

测试截图如下:

接下来我们观察一下中间的运行结果。还记得吗，数据的类别标签为[1.0，1.0,-1.0,-1.0,
1.0]。在第一轮迭代中，D中的所有值都相等。.于是，只有第一个数据点被错分了。因此在第二轮迭代中，D向量给第一个数据点0.5的权重。这就可以通过变量aggClassEst的符号来了解总的类别。第二次迭代之后，我们就会发现第一个数据点巳经正确分类了，但此时最后一个数据点却是错分了。D向量中的最后一个元素变成0.5，而乃向量中的其他值都变得非常小。最后，第三次迭代之后aggClassEst所有值的符号和真实类别标签都完全吻合，那么训练错误率为0,程序就此退出。

7.5 测试算法：基于AdaBoost的分类
AdaBoost分类函数,代码如下:

def adaClassify(datToClass,classifierArr):
    dataMatrix = mat(datToClass)#do stuff similar to last aggClassEst in adaBoostTrainDS
    #获取待分类数据集行数
    m = shape(dataMatrix)[0]
    #预测分类数组,初始化为(m,1)维零矩阵
    aggClassEst = mat(zeros((m,1)))
    #分别通过classifierArr中存储的最佳决策树桩对数据集进行stumpClassify()分类,将分类结果与alpha累加
    for i in range(len(classifierArr)):
        classEst = stumpClassify(dataMatrix,classifierArr[i]['dim'],\
                                 classifierArr[i]['thresh'],\
                                 classifierArr[i]['ineq'])#call stump classify
        aggClassEst += classifierArr[i]['alpha']*classEst
        print(aggClassEst)
    #sign(x)函数表示x>0,返回0;x=0,返回0;x<0;返回-1
    #返回预测结果
    return sign(aggClassEst)

测试截图如下:

可以发现，随着迭代的进行，数据点[0，0]的分类结果越来越强。

7.6 示例：在一个难数据集上应用AdaBoost
  示例：在一个难数据集上的AdaBoost应用
    (1)收集数据：提供的文本文件。
    (2)准备数据：确保类别标签是+1和-1而非1和0。
    (3)分析数据：手工检查数据。
    (4)训练算法：在数据上，利用adaBoostTrainDS()函数训练出一系列的分类器。
    (5)测试算法：我们拥有两个数据集。在不釆用随机抽样的方法下，我们就会对AdaBoost和Logistic回归的结果进行完全对等的比较。
    (6)使用算法：观察该例子上的错误率。不过，也可以构建一个Web网站，让驯马师输入马的症状然后预测马是否会死去。

自适应数据加载函数,代码如下:

#与之前的loadData的不同之处在于我们不必指定特征数目，在第一行已经读取的数目-1即为特征数目
#需要注意的是，需要打开文件两次

def loadDataSet(fileName):      #general function to parse tab -delimited floats
    numFeat = len(open(fileName).readline().split('\t')) #get number of fields 
    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

当最佳决策树桩为10时，测试截图如下:

训练错误率:

测试错误率:

当最佳决策树桩为50时，测试截图如下:
训练错误率:

测试错误率:

在第5章中，我们在同一数据集上采用Logistic回归得到的平均错误率为0.35。而采用AdaBoost得到的错误率就永远不会那么高了。从表中可以看出，我们仅仅使用50个弱分类器，就达到了较高的性能。

(注意，图中单位不是百分比，而是小数)

观察表7-1中的测试错误率一栏，就会发现测试错误率在达到了一个最小值之后又开始上升了。这类现象称之为过拟合（overfitting
,也称过学习）。有文献声称，对于表现好的数据集，AdaBoost的测试错误率就会达到一个稳定值，并不会随着分类器的增多而上升。或许在本例子中的数据集也称不上“表现好”。该数据集一开始有30%的缺失值，对于Logistic回归而言，这些缺失值的假设就是有效的，而对于决策树却可能并不合适。