浅尝AdaBoost算法

作者: RossH | 来源:发表于2019-11-03 23:28 被阅读0次

浅尝AdaBoost算法
提升方法
第8章 Adaboost算法
集成算法整理
Adaboost算法简介
4. AdaBoost 自适应推进
GBDT集成算法（梯度提升树）
04 集成学习 - Boosting - AdaBoost算法构
adaboost和xgboost的区别和联系
AdaBoost 算法

元算法是对其他算法进行组合的一种方式。

使用集成方法时，会有多种形式：可以是不同算法的集成；也可以是同一算法在不同设置下的集成；还可以是数据集不同部分分配给不同分类器之后的集成。

bagging，自举汇聚法（bootstrap aggregating），其算法过程如下：

从原始样本集中抽取训练集。每轮从原始样本集中使用Bootstraping的方法抽取n个训练样本（在训练集中，有些样本可能被多次抽取到，而有些样本可能一次都没有被抽中）。共进行k轮抽取，得到k个训练集。（k个训练集之间是相互独立的）
每次使用一个训练集得到一个模型，k个训练集共得到k个模型。（注：这里并没有具体的分类算法或回归方法，我们可以根据具体问题采用不同的分类或回归方法，如决策树、感知器等）
对分类问题：将上步得到的k个模型采用投票的方式得到分类结果；对回归问题，计算上述模型的均值作为最后的结果。（所有模型的重要性相同）。

boosting（提升）是通过集中关注被已有分类器错分的那些数据来获得新的分类器。bagging中的分类器权重是相等的，而boosting中的分类器权重并不相等，每个权重代表的是其对应分类器在上一轮迭代中的成功度。

AdaBoost

AdaBoost是adaptive boosting（自适应boosting）的缩写。其运行过程如下：

为每个训练数据赋予相等的初始权重，这些权重构成向量D
训练出一个弱分类器并计算该分类器的错误率
重新调整每个样本的权重，上一次分对的样本的权重降低，分错的样本的权重提高，然后在同一数据集上再次训练弱分类器

为了从所有弱分类器中得到最终的分类结果，AdaBoost为每个分类器分配一个权重值alpha，这些alpha值是基于弱分类器的错误率进行计算的。其中，错误率 $\varepsilon$ 的定义为：
$\varepsilon = \frac{未正确分类的样本数}{所有样本数}$
而alpha的计算公式如下：
$\alpha = \frac{1}{2}ln\lgroup\frac{1 - \varepsilon}{\varepsilon}\rgroup$

计算出alpha值之后，对权重向量D进行更新。
如果某个样本被正确分类，那么该样本的权重更改为：
$D^{(t+1)}_i = \frac{D^{(t)}_ie^{-\alpha}}{Sum(D)}$
如果某个样本被错分，那么该样本的权重更改为：
$D^{(t+1)}_i = \frac{D^{(t)}_ie^{\alpha}}{Sum(D)}$

AdaBoost算法会不断重复训练和调整权重的过程，直到训练错误率为0或者弱分类器数目达到指定值。

上图为Adaboost算法示意图。最左边为数据集，不同宽度表示权重不同。各个弱分类器预测出的结果通过三角形中的alpha值进行加权，最后汇总求和，通过sign函数输出结果。

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

单层决策树(decision stump)，仅基于单个特征做决策，只有一次分裂过程，实际上就是个树桩。

# 创建简单数据集
def loadSimpData():
    datMat = np.matrix([[ 1. ,  2.1],
        [ 1.5 ,  1.5],
        [ 1.3,  1. ],
        [ 1. ,  1. ],
        [ 2. ,  1. ]])
    classLabels = [1.0, 1.0, -1.0, -1.0, 1.0]
    return datMat,classLabels

# 数据可视化
datMat, classLabels = loadSimpData()

xcord0 = []
ycord0 = []
xcord1 = []
ycord1 = []
markers =[]
colors =[]

for i in range(len(classLabels)):
    if classLabels[i]==1.0:
        xcord1.append(datMat[i,0]), ycord1.append(datMat[i,1])
    else:
        xcord0.append(datMat[i,0]), ycord0.append(datMat[i,1])
fig = plt.figure()
ax = fig.add_subplot(111)       
ax.scatter(xcord0,ycord0, marker='s', s=90)
ax.scatter(xcord1,ycord1, marker='o', s=50, c='red')
plt.title('decision stump test data')
plt.show()

观察上图，可以发现如果要找一条与坐标轴平行的直线来分开两类数据是不可能的。这就是单层决策树难以处理的一个问题。

def stumpClassify(dataMatrix,dimen,threshVal,threshIneq):
    '''
    dataMatrix：数据集
    dimen：用于决策的特征
    threshVal：阈值
    threshIneq：比较符号（小于等于或大于）
    '''
    retArray = np.ones((np.shape(dataMatrix)[0],1))
    if threshIneq == 'le':
        retArray[dataMatrix[:,dimen] <= threshVal] = -1.0
    else:
        retArray[dataMatrix[:,dimen] > threshVal] = -1.0
    return retArray

def buildStump(dataArr,classLabels,D):
    '''
    dataArr：特征矩阵
    classLabels：标签矩阵
    D：样本权重
    返回：最佳树桩信息，最小误差，最佳分类结果
    '''
    dataMatrix = np.mat(dataArr)
    labelMat = np.mat(classLabels).T
    m,n = dataMatrix.shape
    numSteps = 10.0
    bestStump = {}                              # 用于存储最佳树桩信息的字典
    bestClasEst = np.mat(np.zeros((m,1)))       # 初始化分类结果为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 ['le', 'gt']:        # 第三层：循环切换不等式
                threshVal = (rangeMin + 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
                    bestClasEst = predictedVals.copy()
                    bestStump['dim'] = I
                    bestStump['thresh'] = threshVal
                    bestStump['ineq'] = inequal
    return bestStump,minError,bestClasEst

试一下，观察结果。

D = np.mat(np.ones((5,1))/5)
buildStump(datMat, classLabels, D)

output:
({'dim': 0, 'thresh': 1.3, 'ineq': 'le'}, matrix([[0.2]]), array([[-1.],
        [ 1.],
        [-1.],
        [-1.],
        [ 1.]]))

上面生成的单层决策树就是一个弱分类器。接下来将使用多个弱分类器来构建AdaBoost。

完整AdaBoost算法

伪代码：

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

python代码实现：

def adaBoostTrainDS(dataArr, classLabels, maxIter=40):
    '''
    dataArr：特征矩阵
    classLabels：标签矩阵
    maxIter=40：最大迭代次数，默认值为40
    返回：弱分类器数组，类别估计累计值
    '''
    weakClassArr = []
    m = dataArr.shape[0]
    D = np.mat(np.ones((m,1))/m)                                       # 初始化权重值
    aggClassEst = np.mat(np.zeros((m,1)))
    for i in range(maxIter):
        bestStump,error,classEst = buildStump(dataArr,classLabels,D)   # 构建单层决策树
        alpha = float(0.5*np.log((1.0-error)/max(error,1e-16)))        # 计算alpha
        bestStump['alpha'] = alpha  
        weakClassArr.append(bestStump)                                 # 存储单层决策树
        expon = np.multiply(-1*alpha*np.mat(classLabels).T,classEst)   # 计算e的指数项
        D = np.multiply(D,np.exp(expon))
        D = D/D.sum()
        # 计算全部分类器的累计误差，如果为0则终止循环
        aggClassEst += alpha*classEst
        aggErrors = np.multiply(np.sign(aggClassEst) != np.mat(classLabels).T,np.ones((m,1)))
        errorRate = aggErrors.sum()/m
        if errorRate == 0.0: break
    return weakClassArr,aggClassEst

执行函数，观察结果。

DSArr, aggClass = adaBoostTrainDS(datMat, classLabels)

output:
D: [[0.2 0.2 0.2 0.2 0.2]]
D: [[0.5   0.125 0.125 0.125 0.125]]
D: [[0.28571429 0.07142857 0.07142857 0.07142857 0.5       ]]

可以观察到在迭代过程中，被错分的样本权重会增加，正确分类的样本权重会降低。
观察分类器数组：

DSArr

ooutput:
[{'dim': 0, 'thresh': 1.3, 'ineq': 'le', 'alpha': 0.6931471805599453},
 {'dim': 1, 'thresh': 1.0, 'ineq': 'le', 'alpha': 0.9729550745276565},
 {'dim': 0, 'thresh': 0.9, 'ineq': 'le', 'alpha': 0.8958797346140273}]

只有三个弱分类器，也就是说迭代三次就停止了。
接下来测试下算法。

基于AdaBoost的分类

# AdaBoost分类函数
def adaClassify(inX, classifierArr):
    '''
    inX：待分类数据
    classifierArr：训练好的弱分类器数组
    '''
    dataMatrix = np.mat(inX)
    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
    return np.sign(aggClassEst)

观察实际运行效果。

print(adaClassify([0,0], DSArr))
print(adaClassify([2,2], DSArr))

output:
[[-1.]]
[[1.]]

示例：在病马数据集上应用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 np.matrix(dataMat), np.matrix(labelMat)

def calErrRate(maxC = 40):
    trainMat, trainLabelMat = loadDataSet('horseColicTraining2.txt')
    weakClassArr,aggClassEst = adaBoostTrainDS(trainMat, trainLabelMat, maxC)
    trainPred = adaClassify(trainMat, weakClassArr)
    errArr = np.mat(np.ones((trainMat.shape[0], 1)))
    trainErrRate = errArr[trainPred != trainLabelMat.T].sum() / trainMat.shape[0]

    testMat, testLabelMat = loadDataSet('horseColicTest2.txt')
    testPred = adaClassify(testMat, weakClassArr)
    errArr = np.mat(np.ones((testMat.shape[0], 1)))
    testErrRate = errArr[testPred != testLabelMat.T].sum() / testMat.shape[0]
    return trainErrRate, testErrRate

loadDataSet()函数加载数据集，并以矩阵形式返回。calErrRate()计算训练错误率和测试错误率。
直接执行calErrRate()函数会得到如下结果。

(0.19732441471571907, 0.19402985074626866)

也就是说弱分类器在40个的情况下，训练错误率在0.20左右，测试错误率在0.19左右。
接下来看一下不同分类器数目的情况。

import pandas as pd

Cycles = [1, 10, 50, 100, 500, 1000, 10000]
trainErrRate = []
testErrRate = []
for maxC in Cycles:
    a, b = calErrRate(maxC)
    trainErrRate.append(round(a, 2))
    testErrRate.append(round(b, 2))

df = pd.DataFrame({'分类器数目':Cycles, '训练错误率':trainErrRate, '测试错误率':testErrRate})
df

分类器数目	训练错误率	测试错误率
1	0.28	0.27
10	0.23	0.24
50	0.19	0.21
100	0.19	0.22
500	0.16	0.25
1000	0.14	0.31
10000	0.11	0.33

观察发现，测试错误率在达到一个最小值后又开始上升。这种现象称之为过拟合。

小结

集成方法通过组合多个分类器的分类结果，获得了比简单的单分类器更好的分类结果。

多个分类器组合可能会进一步凸显出单分类器的不足，比如过拟合问题。如果分类器之间差别显著，那么可能会缓解这一问题。分类器之间的差别可以是算法本身或者应用于算法上的数据不同。

bagging是通过随机抽样的替换方式，得到了与原始数据集规模一样的数据集。boosting在数据集上顺序应用了多个不同的分类器。

本文以单层决策树作为弱学习器构建AdaBoost分类器。实际上，AdaBoost可以应用于任意分类器，只要该分类器能够处理加权数据即可。

浅尝AdaBoost算法
元算法是对其他算法进行组合的一种方式。使用集成方法时，会有多种形式：可以是不同算法的集成；也可以是同一算法在不同...
提升方法
提升方法提升方法 AdaBoost 算法 AdaBoost算法的训练误差分析 AdaBoost算法的解释提升树...
第8章 Adaboost算法
内容一、Adaboost简介二、Adaboost算法过程三、Adaboost算法的训练误差分析四、Adab...
集成算法整理
一.AdaBoost的算法在学习adaboost算法前先要弄清楚前向分布算法，因为AdaBoost是前向分布加法...
Adaboost算法简介
Adaboost算法 Adaboost算法是一种有监督的学习方法，是基于Adaboost算法的分类器把若干个分类器...
4. AdaBoost 自适应推进
1.名词解释 Boost(推进)，adaboost（adapt boost）自适应推进算法：Adaboost算法是...
GBDT集成算法（梯度提升树）
一、算法思想 GBDT是集成学习Boosting算法中的一种，它与Adaboost相比，Adaboost算法利用...
04 集成学习 - Boosting - AdaBoost算法构
03 集成学习 - Boosting - AdaBoost算法原理十、AdaBoost算法构建上一章最后说明了...
adaboost和xgboost的区别和联系
机器学习算法中GBDT与Adaboost的区别与联系是什么？ Adaboost Adaboost是模型为加法模型，...
AdaBoost 算法
参考Blog： adaBoost算法参考书籍：《机器学习实战》参考书籍： Adaboost是一种迭代算法，其...