AdaBoost

一、AdaBoost简介

AdaBoost采用的是boosting算法，通过集中关注被已有分类器错分的 那些数据更新样本权重从而更新每个弱分类器的权重（$\alpha$α）来获得新的分类器，$\alpha$α代表其对应分类器在上一轮迭代中的成功度。

二、工作原理

对训练数据中的每 个样本赋予一个权重，这些权重构成了向量$w$w。一开始，这些权重都初始化成相等值。首先，在训练数据上训练出一个弱分类器并计算该分类器的错误率$e_m$em​和权重$\alpha$α，然后,在同一数据集上再次训练弱分类器。在分类器的第二次训练当中，将会重新调整每个样本的权重，其中第一次分对的样本的权重将会降低，而第一次分错的样本的权重将会提高。

1.错误率：

可以理解为：$w$w*$(未正确分类的权重$(未正确分类的权重/$所有的样本数)

2.弱分类器权重值：

3.权重更新：

$y_i$yi​：真实的分类标签。
$G_m(x_i)$Gm​(xi​)：每个弱分类器得到的分类标签。


$Z_m$Zm​：规范因子，使更新后的样本权重值总和为1。

4.最终分类器

a.弱分类器的线性组合

b.最终分类器

三、核心代码

1.基于单层决策树构建弱分类器

伪代码：

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

def stumpClassify(dataMatrix,dimen,threshVal,threshIneq):
    '''
    Desc:通过阈值比较对数据进行分类
    Method:数组过滤
    dimen：特征列
    threshVal：阀值
    threshIneq：阀值判断条件
    '''
    retArray = np.ones((dataMatrix.shape[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):
    '''
    Desc:计算最优阀值，找到最佳的单层决策树
    '''
    dataMatrix = np.mat(dataArr)
    labelMat = np.mat(classLabels).T
    m,n = dataMatrix.shape #(5,2) 
    # 用于在特征的所有可能值上进行遍历？？？？
    numSteps = 10.0
    bestStump = {}
    bestClasEst = np.mat(np.zeros((m,1)))
    minError = np.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)#call stump classify with i, j, lessThan
                # 初始化预测标签矩阵
                errArr = np.mat(np.ones((m,1)))
                # 以阀值为标准的分类与真实分类作对比，分类错误样本记为1
                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

3.基于单层决策树的AdaBoost训练

伪代码：

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

def adaBoostTrainDS(dataArr,classLabels,numIt=40):
    
    '''
    Desc:单层决策树的训练过程
    dataArr:训练数据集
    classLabels：分类标签
    numIt：训练迭代次数
    '''
    
    weakClassArr = []
    m = dataArr.shape[0]
    D = np.mat(np.ones((m,1))/m)
    aggClassEst = np.mat(np.zeros((m,1)))
    for i in range(numIt):
        bestStump,error,classEst = buildStump(dataArr,classLabels,D)#build Stump
        alpha = float(0.5*np.log((1.0-error)/max(error,1e-16))) 
        bestStump['alpha'] = alpha
        # 将最佳单层决策树加入到单层决策树数组
        weakClassArr.append(bestStump)
        # -ayG, a:弱分类器权重值，y:分类标签，G:弱分类器预测标签
        expon=np.multiply(-1*alpha*np.mat(classLabels).T,classEst)
        # 更新权重矩阵
        D = np.multiply(D,np.exp(expon))
        # 规范化
        D = D/D.sum()
        aggClassEst += alpha*classEst
        aggErrors = np.multiply(np.sign(aggClassEst) != np.mat(classLabels).T,np.ones((m,1)))
        errorRate = aggErrors.sum()/m
        print("total error: ",errorRate)
        if errorRate == 0.0: break
    return weakClassArr,aggClassEst

4.测试算法：基于 AdaBoost的分类

def adaClassify(datToClass,classifierArr):
    '''
    Desc:基于AdaBoost的分类
    datToClass:待分类样本
    classifierArr：经过训练的所有弱分类器
    '''
    dataMatrix = np.mat(datToClass)
    m = dataMatrix.shape[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)

import numpy as np
def loadSimpData():
    datMat = 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 datMat,classLabels

datMat,classLabels=loadSimpData()
weakClassArr,aggClassEst=adaBoostTrainDS(datMat,classLabels,9)
weakClassArr,aggClassEst

([{‘alpha’: 0.693147180559945, ‘dim’: 0, ‘ineq’: ‘lt’, ‘thresh’: 1.3},
{‘alpha’: 0.9729550745276565, ‘dim’: 1, ‘ineq’: ‘lt’, ‘thresh’: 1.0},
{‘alpha’: 0.8958797346140273, ‘dim’: 0, ‘ineq’: ‘lt’, ‘thresh’: 0.9}],
matrix([[ 1.17568763],
[ 2.56198199],
[-0.77022252],
[-0.77022252],
[ 0.61607184]]))

adaClassify([[5,5],[0,0]],weakClassArr)

[[-0.69314718]]
[[-1.66610226]]
[[-2.56198199]]
matrix([[-1.]])

四、示例

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

def loadDataSet(fileName):
    '''
    Desc:加载文件数据，预处理
    '''
    # 每行的数据量
    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

# 训练
datArr,labelArr = loadDataSet('horseColicTraining2.txt')
# 迭代60次误差较小
classifierAarry,aggClassEst= adaBoostTrainDS(np.mat(datArr),labelArr,10)

# 测试
testArr,testLabelArr = loadDataSet('horseColicTest2.txt')
pred = adaClassify(np.mat(testArr),classifierAarry)

import matplotlib.pyplot as plt
def plotROC(predStrengths, classLabels):
    '''
    
    '''
    cur = (1.0,1.0)
    ySum = 0.0
    numPosClas = sum(np.array(classLabels)==1.0)
    yStep = 1/float(numPosClas); xStep = 1/float(len(classLabels)-numPosClas)
    sortedIndicies = predStrengths.argsort()
    fig = plt.figure()
    fig.clf()
    ax = plt.subplot(111)
    for index in sortedIndicies.tolist()[0]:
        if classLabels[index] == 1.0:
            delX = 0; delY = yStep;
        else:
            delX = xStep; delY = 0;
            ySum += cur[1]
        ax.plot([cur[0],cur[0]-delX],[cur[1],cur[1]-delY], c='b')
        cur = (cur[0]-delX,cur[1]-delY)
    ax.plot([0,1],[0,1],'b--')
    plt.xlabel('False positive rate'); plt.ylabel('True positive rate')
    plt.title('ROC curve for AdaBoost horse colic detection system')
    ax.axis([0,1,0,1])
    plt.show()
    print("the Area Under the Curve is: ",ySum*xStep)

plotROC(aggClassEst.T,labelArr)