机器学习之Adaboost元算法

发表于 | 分类于 | 浏览 次

《机器学习实战》第7章 利用AdaBoost元算法提高分类性能

最近的机器学习课程要求博客分享学习报告，因此借助博客进行分享，希望大家提出宝贵意见。此外由于还没有搞清楚hexo如何分栏目，所以暂未进行分栏，接下来熟悉后会对文章进行分栏等处理，保持博客的“清爽”。

7.1 基于数据集多重抽样的分类器

集成方法(ensemble method)又称为元算法(meta-algorithm)是对其他算法进行组合的一种方式，组合的方式主要有：

①不同的分类算法集成（KNN、决策树、朴素贝叶斯、Logistics、SVM等分类算法进行集成）
②同一算法在不同设置下集成（算法参数不同）
③数据集不同部分分配给不同分类器之后的集成

通常来讲一个集成分类器的分类性能将优于单个的分类器，单个分类器如果是一个决策者，集成学习的方法则为多决策者共同决策一个问题。

7.1.1 bagging 基于数据随机重抽样的分类器构建方法

bagging方法是在从原始数据集选择S次后得到S个新数据集的一种技术。每个数据集都是通过在原始数据集中随机选择一个样本来进行替换得到的。新数据集中可能有重复的值，也原始数据集中有新集合中没有的值。bagging又叫做bootstrap aggregating，是一种根据均匀概率分布从数据中重复抽样即有放回的技术。

bagging方法的过程：

某个学习算法至每个数据集至S个分类器至投票结果的最多类别
先进的bagging方法：随机森林
因此：
Bagging方法的性能依赖于及分类器的稳定性，若基分类器稳定，该方法误差主要源于基分类器的偏差，若该方法不稳定，则该方法有助于降低训练数据随机波动造成的误差。此外由于基于均匀分布，每个样本被选中的概率相同，因此该方法不侧重于某一实例。

7.1.2 boosting

boosting通过集中关注被已有分类器错分的那些数据来获得新的分类器，是一个迭代的过程。由于boosting分类结果是基于所有分类器的加权求和结果的，因此boosting中分类器权重不相等，每个权重代表的是其对应分类器上一轮迭代中的成功度（每一轮结束后都加大错误值的权重，减少正确值的权重）。其中adaboosting较有代表性。

7.2 训练算法：基于错误提升分类器的性能

Adaboosting算法运行过程：

step1初始化：在训练数据中的每个样本赋予权重，权重构成向量D，初始状态下将各个权重初始化为相等值。

step2训练+错误率计算：在训练数据上训练处一个弱分类器并计算错误率。多个分类器之间由alpha权重协调，alpha基于每个弱分类器错误率进行计算，得到的alpha加权结果求和输出。

step3权重调整：更新权重向量D，调整每个样本权重，分对的权重降低，分错的权重提高。

step4结束条件：若训练错误率为0或弱分类器的数目达到用户的指定值，循环停止，否则进入step2开始下一循环。

以上过程中，错误率$\epsilon$的定义为：

alpha的计算为：

权重调整过程，样本正确分类，权重修改：

样本错误分类，权重修改：

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

此步骤中主要构建了stumpClassify与buildStump两个函数用于弱分类器的构建。stumpClassify函数可以用于测试是否有某个值小于或大于我们正在测试的阈值。buildStump函数调用了stumpClassify函数，用于找到具有最低错误率的单层决策树。

该步骤相当于完成了adaboosting算法中的一次迭代过程。

stumpClassify的伪代码过程为：

1
2
3
4
5
6
7
设置最小错误率minerror为$+\infty$
对数据集中的每个特征：
	对每个步长：
		对每个不等号可能：
			建立一颗单层决策树并利用加权数据集对其进行测试
			如果错误率低于minerror，则将单签决策树设置为最佳单层决策树
返回最佳决策树的相关参数

本部分具体代码及自行添加的详细注释将在最后的代码部分附加~

7.4 完整AdaBoost算法的实现

接下来将利用7.3中的一次迭代过程来实现7.2中所涉及到的Adaboost算法。

该过程的伪代码如下：

1
2
3
4
5
6
7
每次迭代：
	利用buildStump()函数找到最佳的单层决策树
	将最佳单层决策树加入到单层决策树组
	依据公式计算alpha
	计算新的权重向量D
	更新累计类别估计值
	如果错误率等于0.0，则退出循环

此循环通过编写adaBoostTrainDS()函数实现，函数及具体步骤的解释同样在最后的代码部分阐述。

7.5 测试算法：基于AdaBoost的分类

基于adaboos的分类在adaBoostTrainDS中已经基本完成，此处需要将弱分类器的训练过程抽出并应用于具体实例，每个弱分类器的结果以其对应的alpha值作为权重，所有弱分类器的分类结果加权求和得到最后的结果。

此步骤中构建AdaClassify()函数，其是利用训练处的多个弱分类器进行分类的函数。

该过程伪代码：

1
2
3
4
5
6
输入待分类样例、多个弱分类器组成的数组
转换待分类样例为numpy矩阵，获取待分类样例个数m，构建0列向量aggClassEst
遍历多个弱分类器组成的数组的全部弱分类器：
	调用StumpClassify对每个分类器得到一个类别估计值
	累加aggClassEst，累加值为输出的类别估计值*该单层决策树的alpha权重
返回aggClassEst的符号，大于0，则返回+1，小于0返回-1.

此前各函数代码：

1
2
3
4
5
6
7
def stumpClassify(dataMatrix,dimen,threshVal,threshIneq): #通过阈值比较对数据进行分类
    retArray = ones((shape(dataMatrix)[0],1))#先全部设置为1
    if threshIneq == 'lt':#ifelse条件用于不等号的切换
        retArray[dataMatrix[:,dimen] <= threshVal] = -1.0#不满足不等式要求设置为-1
    else:
        retArray[dataMatrix[:,dimen] > threshVal] = -1.0#不满足不等式要求设置为-1
    return retArray
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def buildStump(dataArr,classLabels,D):#用于遍历stumpClassify函数所有可能的输入值，并找到该数据集上的最佳单层决策树
    dataMatrix = mat(dataArr); labelMat = mat(classLabels).T#转换为符合条件的格式
    m,n = shape(dataMatrix) #m是样本数，n是特征数
    numSteps = 10.0; bestStump = {}; bestClasEst = mat(zeros((m,1)))#建立空字典，存储给定权重向量D是的最佳单层决策树
    minError = 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']: #在小于(less than)与大于(greater than)之间切换
                threshVal = (rangeMin + float(j) * stepSize) #得到每个步子的划分阈值
                predictedVals = stumpClassify(dataMatrix,i,threshVal,inequal) #调用stumpClassify
                errArr = mat(ones((m,1))) #初始化错误对照矩阵为全1
                errArr[predictedVals == labelMat] = 0 #预测结果与标签一致则改为0
                weightedError = D.T*errArr  #计算总错误，用权重向量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 #返回存储最佳单层决策树的字典、错误两次和类别估计值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def adaBoostTrainDS(dataArr,classLabels,numIt=40):#用于构建完整的adaboost过程，调用buildStump函数；numIt为迭代次数，需要用户指定
    weakClassArr = []
    m = shape(dataArr)[0] #m为数据集数据点数数
    D = mat(ones((m,1))/m)   #D为概率分布向量，包含了每个数据点的权重，将权重矩阵D初始化为相等值1/m
    aggClassEst = mat(zeros((m,1)))  #列向量，用于记录每个数据点的类别估计累计值
    for i in range(numIt): #主循环段，停止条件为次数到达numIt或错误率为0.0
        bestStump,error,classEst = buildStump(dataArr,classLabels,D)#建立单层决策树
        #print ("D:",D.T)
        alpha = float(0.5*log((1.0-error)/max(error,1e-16)))#计算alpha，用于告诉总分类器本次单层决策树输出结果的权重，max函数防止除0溢出
        bestStump['alpha'] = alpha  #将alpha值加入bestStump字典
        weakClassArr.append(bestStump)  #保存信息
        #print ("classEst: ",classEst.T)
        #用于下一次迭代权重矩阵D的计算
        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()
        #aggClassEst保持运行时的类别估计值。如果总错误率为0，则提前结束循环
        aggClassEst += alpha*classEst
        #print ("aggClassEst: ",aggClassEst.T)
        #错误率累加计算
        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
2
3
4
5
6
7
8
9
10
11
def adaClassify(datToClass,classifierArr):
    dataMatrix = mat(datToClass)#do stuff similar to last aggClassEst in adaBoostTrainDS
    m = shape(dataMatrix)[0]
    aggClassEst = mat(zeros((m,1)))
    for i in range(len(classifierArr)):
        classEst = stumpClassify(dataMatrix,classifierArr[0][i]['dim'],\ #注意[i]前面需添加[0]
                                 classifierArr[0][i]['thresh'],\
                                 classifierArr[0][i]['ineq'])   #call stump classify
        aggClassEst += classifierArr[0][i]['alpha']*classEst
        print (aggClassEst)
    return sign(aggClassEst)

7.6 在其他数据集上应用Adaboost

在应用adaboost算法是，我们需要经过以下步骤，且本次讨论的程序仅用于二分类问题，若希望处理多分类问题，则需要对程序进行改写：

step1：收集数据，划分训练集与测试集

step2：准备数据：确保类别标签是+1与-1而非1和0

step3：分析数据：手工检查数据，查看数据缺失状况

step4：训练算法：在数据上利用AdaBoostTrainDS()函数训练一系列分类器

step5：测试算法：使用adaClassify()函数测试算法的错误率

step6：使用算法

此步骤中包含数据文件加载的过程：

1
2
3
4
5
6
7
8
9
10
11
12
def loadDataSet(fileName):   #用于读入txt文件数据，并划分为特征和标签
    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

之后，可利用如下程序应用Adaboost算法：

1
2
3
4
5
6
7
8
>>> datArr, labelArr = boadDataSet('训练集文件名.txt')
>>> classifierArray = adaBoostTrainDS(datArr, labelArr, 指定的分类器数目)
将输出训练错误率
>>> testArr, testLabelArr = loadDataSet('测试集文件名.txt')
>>> prediction分类器数目 = adaClassify(testArr, classifierArray)
>>> errArr = mat(ones((测试集样本数,1)))
>>> errArr[prediction分类器数目 != mat(testLabelArr).T].sum()
>>> errorrate = (errArr[prediction分类器数目 != mat(testLabelArr).T].sum())/测试集样本数

通过指定不同的分类器数目，可以看到训练错误率与测试错误率的变化，在这一过程中可能会出现，随着分类器数目的增加，训练错误率逐渐降低，但测试错误率先降低后升高的现象，这类现象称为过拟合。

12:00ddl到了，不得不先deploy此篇文章了，接下来的非均衡分类问题待我一会儿补全~