集成学习②——Adaboost算法原理及python实现

一、AdaBoost算法原理

上一偏博客总结过，集成学习基于弱学习器之间是否依赖分为Boosting和Bagging两类, Adaboost就是Boosting中的典型代表。 其核心思想是针对同一个训练集训练不同的学习器，然后将这些弱学习器集合起来，构造一个更强的最终学习算法

AdaBoost是英文"Adaptive Boosting"（自适应增强）的缩写，它的自适应在于： 基于每一个分类器的误差率，来更新所有样本的权重，前一个分类器被错误分类的样本的权值会增大，而正确分类的样本的权值会减小，并再次用来训练下一个基本分类器。

Adaboost算法分为三步：
（1）初始化权值：每一个训练样本最开始权重相同
（2）训练弱分类器：先训练一个弱分类器，计算其误差率（被错误分类的样本权值和），基于误差率降低分类正确的样本权重，提升分类错误的样本权重。权值更新过的样本集被用于训练下一个分类器，整个训练过程如此迭代地进行下去。
（3）组合分类器：各个弱分类器的训练过程结束后，依据各分类器的误差率计算各自在最终分类器中的权重，误差率越大，权重越低，就是你说的越对，那么就越听你的，你满嘴跑火车，那就没人听你的了

Adaboost有几个要注意的指标：
① 初始权重：1/训练样本数D
② 误差率： 被分类错误的样本的权重和
③ 弱学习器的权重：

③ 更新训练样本权重：


④最终的分类器

二、Adaboost的python实现

① 构造训练样本

            
              import numpy as np
import matplotlib.pyplot as plt

# 输出样本和类别
def loadsimple():
    datMat = np.matrix([[1., 2.1],
                        [1.5, 1.6],
                        [1.3, 1.],
                        [1., 1.],
                        [2., 1.]])
    classlablels = [1.0, 1.0, -1.0, -1.0, 1.0]
    return datMat, classlablels

            
          

② 训练弱分类器（简单二分类决策树）

            
              # 输出按某特征的某个阈值分类后的类别向量
def stumpClassify(dataMatrix, dimen, threshVal, threshIneq):
    retArray = np.ones((np.shape(dataMatrix)[0], 1))
    if threshIneq == 'lt':
        retArray[dataMatrix[:, dimen] <=threshVal] = -1.0
    else:                                                # threshIneq == 'gt'大于为-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
    bestClassEst = np.mat(np.zeros((m, 1)))
    minError = float('inf')
    bestStump = {}
    for i in range(n):
        rangMin = dataMatrix[:, i].min()
        rangMax = dataMatrix[:, i].max()
        stepSize = (rangMax-rangMin)/numsteps
        for j in range(-1, int(numsteps)+1):
            for inequal in ['lt', 'gt']:
                threshVal = (rangMin + float(j)*stepSize)
                predictedVals = stumpClassify(dataMatrix, i, threshVal, inequal)
                errArr = np.mat(np.ones((m, 1)))
                errArr[predictedVals == labelMat] = 0
                weightedError = D.T * errArr  # 点乘法，为一个值
                if weightedError < minError:
                    minError = weightedError
                    bestClassEst = predictedVals.copy()
                    bestStump['dim'] = i  # 最佳分类特征
                    bestStump['thresh'] = threshVal  # 最佳分类阈值
                    bestStump['ineq'] = inequal # 最佳分类标准，是大于还是小于
    return bestStump, minError, bestClassEst

            
          

③ 构造Adaboost分类器

            
               # 构造Adaboost分类器
def adaBoostTrainDS(dataArr, classlabels, numIt = 40):
    weakClassArr = []
    m = np.shape(dataArr)[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)
        # 计算分类器的权重
        alpha = float(0.5 * np.log((1.0 - error)/max(error, 1e-16))) #计算弱学习算法权重alpha,使error不等于0,因为分母不能为0
        bestStump['alpha'] = alpha  # 一个弱分类器是一个词典，包含了分类的特征、阈值，分类结果，及弱分类器的权重
        weakClassArr.append(bestStump)
        # 重新计算每个样本的权重D
        expon = np.multiply(-1 * alpha * np.mat(classlabels).T, classEst) # #数组对应元素位置相乘
        D = np.multiply(D, np.exp(expon))
        D = D/D.sum()
        # 计算AdaBoost误差，当误差为0的时候，退出循环
        aggClassEst += alpha * classEst
        aggErrors = np.multiply(np.sign(aggClassEst) != np.mat(classEst).T, np.ones((m, 1)))
        errorRate = aggErrors.sum()/m
        print('totol error:', errorRate)
        if errorRate == 0.0:
            break
    return weakClassArr, aggClassEst

            
          

④使用生成的Adaboost分类器进行分类

            
              # 使用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
    return np.sign(aggClassEst)

            
          

⑤ 主函数调用

            
              if __name__ == '__main__':
    dataArr, classlabels = loadsimple()
    weakClassArr,aggClassEst = adaBoostTrainDS(dataArr, classlabels)
    print(weakClassArr)
    print(aggClassEst)
    print(adaClassify([[0, 0, 6, 10],[1, 5, 6,-3]], weakClassArr))

            
          

Adaboost分类器如下：

所有代码如下：

            
              import numpy as np
import matplotlib.pyplot as plt
    
# 输出样本和类别
def loadsimple():
    datMat = np.matrix([[1., 2.1],
                        [1.5, 1.6],
                        [1.3, 1.],
                        [1., 1.],
                        [2., 1.]])
    classlablels = [1.0, 1.0, -1.0, -1.0, 1.0]
    return datMat, classlablels    

# 输出按某特征的某个阈值分类后的类别向量
def stumpClassify(dataMatrix, dimen, threshVal, threshIneq):
    retArray = np.ones((np.shape(dataMatrix)[0], 1))
    if threshIneq == 'lt':
        retArray[dataMatrix[:, dimen] <=threshVal] = -1.0
    else:                                                # threshIneq == 'gt'大于为-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
    bestClassEst = np.mat(np.zeros((m, 1)))
    minError = float('inf')
    bestStump = {}
    for i in range(n):
        rangMin = dataMatrix[:, i].min()
        rangMax = dataMatrix[:, i].max()
        stepSize = (rangMax-rangMin)/numsteps
        for j in range(-1, int(numsteps)+1):
            for inequal in ['lt', 'gt']:
                threshVal = (rangMin + float(j)*stepSize)
                predictedVals = stumpClassify(dataMatrix, i, threshVal, inequal)
                errArr = np.mat(np.ones((m, 1)))
                errArr[predictedVals == labelMat] = 0
                weightedError = D.T * errArr  # 点乘法，为一个值
                if weightedError < minError:
                    minError = weightedError
                    bestClassEst = predictedVals.copy()
                    bestStump['dim'] = i  # 最佳分类特征
                    bestStump['thresh'] = threshVal  # 最佳分类阈值
                    bestStump['ineq'] = inequal # 最佳分类标准，是大于还是小于
    return bestStump, minError, bestClassEst

# 构造Adaboost分类器
def adaBoostTrainDS(dataArr, classlabels, numIt = 40):
    weakClassArr = []
    m = np.shape(dataArr)[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)
        # 计算分类器的权重
        alpha = float(0.5 * np.log((1.0 - error)/max(error, 1e-16))) #计算弱学习算法权重alpha,使error不等于0,因为分母不能为0
        bestStump['alpha'] = alpha  # 一个弱分类器是一个词典，包含了分类的特征、阈值，分类结果，及弱分类器的权重
        weakClassArr.append(bestStump)
        # 重新计算每个样本的权重D
        expon = np.multiply(-1 * alpha * np.mat(classlabels).T, classEst) # #数组对应元素位置相乘
        D = np.multiply(D, np.exp(expon))
        D = D/D.sum()
        # 计算AdaBoost误差，当误差为0的时候，退出循环
        aggClassEst += alpha * classEst
        aggErrors = np.multiply(np.sign(aggClassEst) != np.mat(classEst).T, np.ones((m, 1)))
        errorRate = aggErrors.sum()/m
        print('totol error:', errorRate)
        if errorRate == 0.0:
            break
    return weakClassArr, aggClassEst

# 使用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
    return np.sign(aggClassEst)

if __name__ == '__main__':
    dataArr, classlabels = loadsimple()
    weakClassArr,aggClassEst = adaBoostTrainDS(dataArr, classlabels)
    print(weakClassArr)
    print(aggClassEst)
    print(adaClassify([[0, 0, 6, 10],[1, 5, 6,-3]], weakClassArr))