元算法是对其他算法进行组合的一种方式。其背后的思路就像当做重要决定时，大家可能都会考虑吸取多个专家而不只是一个人的意见。利用元算法处理机器学习问题时就是采用
这种思路。

将不同的分类器进行组合，这种组合结果被称为集成方法或者元算法。

使用集成方法时有多种形式：

• 不同算法的集成；
• 同一算法在不同设置下的集成；
• 数据集不同部分分配给不同分类器之后的集成。

AdaBoost优缺点：

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

自汇聚法，也称为bagging方法，是从原始数据集选择S次后得到S个新数据集的一种技术。在S个数据集建好之后，将某个学习算法分别作用于每个数据集就得到了S个分类器。当
我们要对新数据进行分类时，就可以应用这S个分类器进行分类。与此同时，选择分类器投票结果最多的类别作为最后的分类结果。

boosting是通过集中关注被已有分类器错分的那些数据来获得新的分类器，boosting中的分类器权重并不相等，每个权重代表的是其对应分类器在上一轮迭代中的成功度。AdaBoost
是boosting中最流行的一个版本。

• 收集数据：可以使用任意方法
• 准备数据：依赖于所使用的弱分类器类型。作为弱分类器，简单分类器效果更好
• 分析数据：可以使用任意方法
• 训练算法：AdaBoost的大部分时间都用在训练上，分类器将多次在同一数据集上训练弱分类器
• 测试算法：计算分类的错误率
• 使用算法：同SVM一样，同AdaBoost预测二分类问题，如果想把它应用到多个类别，需对AdaBoost进行修改

AdaBoost是adaptive boosting(自适应boosting)的缩写，其运行过程如下：

• 训练数据中的每个样本，并赋予其一个权重，这些权重构成了向量D。一开始，这些权重都初始化成相等值。
• 首先在训练数据上训练出一个弱分类并计算该分类器的错误率，然后在同一数据集上再次训练弱分类器。
• 在分类器的第二次训练当中，将会重新调整每个样本的权重，其中第一次分对的样本的权重将会降低，而第一次分错的样本的权重将会提高。
• 为了从所有弱分类器中得到最终的分类结果，AdaBoost为每个分类器都分配了一个权重值alpha，这些alpha值是基于每个弱分类器的错误率进行计算的。
  ++ 其中，错误率$\varepsilon 的 定 义 为 ： 的定义为： 的定义为：\varepsilon = \frac{未正确分类的数目}{所有样本数目}$
  ++ 而alpha的计算公式如下： α = 1 2 l n ( 1 − ε ε ) \alpha = \frac{1}{2}ln(\frac{1-\varepsilon }{\varepsilon }) α=21​ln(ε1−ε​)
• 计算出alpha值之后，可以对权重向量D进行更新，以使得那些正确分类的样本权重降低而错分样本的权重升高。D的计算方法如下：
  ++ 如果某个样本被正确分类，那么该样本的权重更改为： D i t + 1 = D i t e − α S u m ( D ) D_{i}^{t+1} = \frac{D_{i}^{t}e^{-\alpha }}{Sum(D)} Dit+1​=Sum(D)Dit​e−α​
  ++ 如果某个样本被错误分类，那么该样本的权重更改为： D i t + 1 = D i t e α S u m ( D ) D_{i}^{t+1} = \frac{D_{i}^{t}e^{\alpha }}{Sum(D)} Dit+1​=Sum(D)Dit​eα​
• 在计算出D之后，AdaBoost又开始进入下一轮迭代。AdaBoost算法会不断地重复训练和调整权重的过程，知道训练错误率为0或者弱分类器的数目达到用户的指定值为止。

伪代码大致如下：

• 将最小错误率minError设为正无穷大
• 对数据集中的每一个特征（第一层循环）：
  • 对每个步长（第二层循环）：
    • 对每个不等号（第三层循环）：
      • 建立一颗单层决策树并利用加权数据集对它进行测试
      • 如果错误率低于minError，则将单层决策树设为最佳单层决策树
• 返回最佳单层决策树

import numpy as np

#########单层决策树生成函数，基于加权输入值进行决策的分类器##########
#dataSet
def loadSimpData():
    dataMat = np.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 dataMat, classLabels

#用于测试是否有某个值小于或者大于我们正在测试的阈值，进行分类
def stumpClassify(dataMatrix, dimen, threshVal, threshIneq):
    retArray = np.ones((np.shape(dataMatrix)[0], 1))
    if threshIneq == 'lt':  #当满足条件：比阈值小划分为-1
        retArray[dataMatrix[:, dimen] <= threshVal] = -1.0
    else:   #当满足条件：比阈值大划分为-1
        retArray[dataMatrix[:, dimen] > threshVal] = -1.0
    return retArray

def buildStump(dataArr, classLabels, D):
    dataMatrix = np.mat(dataArr)
    labelMat = np.mat(classLabels).T
    m, n = np.shape(dataMatrix)
    numSteps = 10.0 #设置第二层的迭代次数
    bestStump = {}  #存放最优解的相关信息
    bestClassEst = np.mat(np.zeros((m, 1))) #最优分类预测结果
    minError = np.inf
    for i in range(n):  #对dataMatrix的每一列
        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)    #设置阈值，通过stepSize进行逐步更新阈值
                predictedVals = stumpClassify(dataMatrix, i, threshVal, inequal)    #调用stumpClassify返回分类预测结果
                errArr = np.mat(np.ones((m, 1)))    #设置错误值变量
                errArr[predictedVals == labelMat] = 0
                weightedError = D.T*errArr  #计算每一次预测分类后的错误值
                #print ("split: dim %d, thresh: %.2f, thresh ineqal: %s, the weightes 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

#运行测试
#dataMat, classLabels = loadSimpData()
#D = np.mat(np.ones((5,1))/5)
#buildStump(dataMat, classLabels, D)

完整AdaBoost算法实现的伪代码如下：

• 对每次迭代：
  • 利用buildStump()函数找到最佳的单层决策树
  • 将最佳单层决策树加入到单层决策树数组
  • 计算alpha
  • 计算新的权重向量D
  • 更新累计类别估计值
  • 如果错误率低于0.0，则退出循环

#基于单层决策树的AdaBoost训练过程
def adaBoostTrainDS(dataArr, classLabels, numIt=40):
    weakClassArr = []
    m = np.shape(dataArr)[0]
    D = np.mat(np.ones((m,1))/m)    #D是一个概率分布向量，因此其所有的元素之和为1.0。为满足此要求，一开始所有的元素都会被初始化为1/m
    aggClassEst = np.mat(np.zeros((m,1)))   #记录每个数据点的类别估计累计值
    for i in range(numIt):
        bestStump, error, classEst = buildStump(dataArr, classLabels, D)
        print("D:", D.T)
        # alpha值告诉分类器本次单层决策树输出结果的权重
        alpha = float(0.5*np.log((1.0-error)/max(error, 1e-16)))    #1e-16，确保除数不为0
        bestStump['alpha'] = alpha
        weakClassArr.append(bestStump)
        print("classEst:", classEst.T)
        expon = np.multiply(-1*alpha*np.mat(classLabels).T, classEst)
        D = np.multiply(D, np.exp(expon))
        D = D/D.sum()   #下一次迭代的新权重向量
        aggClassEst += alpha*classEst  #错误率累加计算
        print("aggClassEst:", aggClassEst.T)
        aggErrors = np.multiply(np.sign(aggClassEst) != np.mat(classLabels).T, np.ones((m,1)))
        errorRate = aggErrors.sum()/m
        print("total Error:", errorRate, "\n")
        if errorRate == 0.0:
            break
    return weakClassArr

#运行算法
#classifierArr = adaBoostTrainDS(dataMat, classLabels, 9)

#AdaBoost分类函数
def adaClassify(dataToClass, classifierArr):
    dataMatrix = np.mat(dataToClass)
    m = np.shape(dataMatrix)[0]
    aggClassEst = np.mat(np.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 np.sign(aggClassEst)

#分类算法测试
#adaClassify([[5,5],[0, 0]], classifierArr)
    

##########示例：在一个难数据集上应用AdaBoost#############
#自适应数据加载函数
def loadDataSet(fileName):
    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

fileDir = r'E:\book\MLiA\MLiA_SourceCode\Ch07'
datArr, labelArr = loadDataSet(fileDir + r'\horseColicTraining2.txt')
classifierArray = adaBoostTrainDS(datArr, labelArr, 10)
testArr, testLabelArr = loadDataSet(fileDir + r'\horseColicTest2.txt')
prediction10 = adaClassify(testArr, classifierArray)
#67个测试样本的错误率
errArr = np.mat(np.ones((67,1)))
print(errArr[prediction10 != np.mat(testLabelArr).T].sum() / len(errArr))