机器学习之AdaBoost元算法

亦凉 2022-08-27 03:20 245阅读 0赞

# 一、Adaboost算法及分析 #

参考：

[http://stblog.baidu-tech.com/?p=19][http_stblog.baidu-tech.com_p_19]

[http://blog.csdn.net/haidao2009/article/details/7514787][http_blog.csdn.net_haidao2009_article_details_7514787]

# 二、程序实现 （代码来自于机器学习实战 李锐等译） #

## 2.1基于单层决策手构建弱分类器 ##

单层决策树(decision stump，也称为决策树桩)是一种简单的决策树。它仅根据单个特征来做决策。

buildStump函数的伪代码：

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

代码：

from numpy import *
    import matplotlib.pyplot as plt
    
    def loadSimpData():
        datMat = 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
    
    
    def loadDataSet(fileName):      #general function to parse tab -delimited floats
        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
    '''
    功能：通过阈值比较对数据进行分类
    '''
    def stumpClassify(dataMatrix,dimen,threshVal,threshIneq):#just classify the data
        retArray = ones((shape(dataMatrix)[0],1))
        if threshIneq == 'lt':
            retArray[dataMatrix[:,dimen] <= threshVal] = -1.0
        else:
            retArray[dataMatrix[:,dimen] > threshVal] = -1.0
        return retArray
        
    '''
    功能：单层决策树生成函数（弱分类器）
    输入函数：
    dataArr:数据集
    classLabels:类别标签
    D：数据点的权重
    输出函数：
    bestStump:具有最小错误率的单层决策树
    minError:最小错误率
    bestClasEst:估计的类别向量
    '''
    def buildStump(dataArr,classLabels,D):
        dataMatrix = mat(dataArr); labelMat = mat(classLabels).T
        m,n = shape(dataMatrix)
        numSteps = 10.0
        bestStump = {} #定义一个空字典，用于存储给定权重向量D时所得到的最佳单层决策树的相关信息
        bestClasEst = mat(zeros((m,1)))
        minError = inf #init error sum, to +infinity；最小错误率初始化为无穷大
        for i in range(n):#loop over all dimensions；在所有数据集的所有特征上遍历
            rangeMin = dataMatrix[:,i].min(); rangeMax = dataMatrix[:,i].max();
            stepSize = (rangeMax-rangeMin)/numSteps #通过计算特征的最小值和最大值来计算步长，numSteps越大，步长越小
            for j in range(-1,int(numSteps)+1):#loop over all range in current dimension按分的步长总数进行循环
                for inequal in ['lt', 'gt']: #go over less than and greater than
                    threshVal = (rangeMin + float(j) * stepSize)
                    predictedVals = stumpClassify(dataMatrix,i,threshVal,inequal)#call stump classify with i, j, lessThan
                    errArr = mat(ones((m,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: #如果当前的错误率较小，则保存该单层决策树到bestStump字典中
                        minError = weightedError
                        bestClasEst = predictedVals.copy()
                        bestStump['dim'] = i
                        bestStump['thresh'] = threshVal
                        bestStump['ineq'] = inequal
        return bestStump,minError,bestClasEst

运行命令：

dataMat,classLabels = loadSimpData()
    D = mat(ones((5,1))/5)
    bestStump,minError,bestClassEst = buildStump(dataMat,classLabels,D)

结果：

>>> bestStump
    {'dim': 0, 'ineq': 'lt', 'thresh': 1.3}
    >>> minError
    matrix([[ 0.2]])
    >>> bestClassEst
    array([[-1.],
           [ 1.],
           [-1.],
           [-1.],
           [ 1.]])

## 2.2 完整AdaBoost算法的实现 ##

实现的伪代码：

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

代码：

'''
    功能：完整的AdaBoost算法
    输入参数:
    dataArr:数据集
    classLabels:类别标签
    numIt:迭代次数（唯一需要用户指定的参数）
    输出参数：
    weakClassArr：多个弱分类器组成的数组
    '''
    def adaBoostTrainDS(dataArr,classLabels,numIt=40): #adaBoostTrainDS中DS代表单层决策树（decision stump）
        weakClassArr = [] #建立一个单层决策树数组
        m = shape(dataArr)[0] #得到数据点的数目
        D = mat(ones((m,1))/m)   #init D to all equal；D表示每个数据点的权重，初始化为1/m
        aggClassEst = mat(zeros((m,1)))
        for i in range(numIt):
            bestStump,error,classEst = buildStump(dataArr,classLabels,D)#build Stump；单层决策树
    ##        plot_Fig(dataArr,classEst,bestStump)
            print "D:",D.T
            alpha = float(0.5*log((1.0-error)/max(error,1e-16)))#calc alpha, throw in max(error,eps) to account for error=0
                                                                #max(error,1e-16)用于确保错误为0时不会发生除0溢出
            bestStump['alpha'] = alpha  
            weakClassArr.append(bestStump)  #store Stump Params in Array,将alpha值添加到字典中
            print "classEst: ",classEst.T
            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/D.sum()
            #calc training error of all classifiers, if this is 0 quit for loop early (use break)
            aggClassEst += alpha*classEst
            print "aggClassEst: ",aggClassEst.T
            aggErrors = multiply(sign(aggClassEst) != mat(classLabels).T,ones((m,1))) #计算数据点哪个是错误
            print 'aggErrors: ',sign(aggClassEst) != mat(classLabels).T
            print 'aggErrors: ',aggErrors
            errorRate = aggErrors.sum()/m #计算错误率
            print "total error: ",errorRate
            if errorRate == 0.0: break
        return weakClassArr

加入画图函数：

'''
    功能：画决策树的图
    '''
    def plot_Fig(xMat,yMat,weakClassArr):
        xMat = mat(xMat)
        fig = plt.figure()
        ax = fig.add_subplot(111)
        for i in range(len(yMat)):
            if yMat[i] == -1.0: #如果标签为-1，则将数据点标为蓝色方块
                ax.scatter(xMat[i,0],xMat[i,1],color='b',marker='s') #注意flatten的用法
            else:  #如果标签为1，则将数据点标为红色圆形
                ax.scatter(xMat[i,0],xMat[i,1],color='r',marker='o')
        for i in range(len(weakClassArr)): #根据弱分类器数组画出决策树图形
            if weakClassArr[i].get("dim") == 0: 
                y = arange(0.0,3.0,0.1)
                x = weakClassArr[i].get("thresh") #得到阈值
                x = repeat(x,len(y))
                ax.plot(x,y)
            if weakClassArr[i].get("dim") == 1:
                x = arange(0.0,3.0,0.1)
                y = weakClassArr[i].get("thresh")
                y = repeat(y,len(x))
                ax.plot(x,y) 
        plt.show()

运行命令：

dataMat,classLabels = loadSimpData()
    weakClassArr = adaBoostTrainDS(dataMat,classLabels,9) 
    plot_Fig(dataMat,classLabels,weakClassArr)

运行结果：

D: [[ 0.2  0.2  0.2  0.2  0.2]]
    classEst:  [[-1.  1. -1. -1.  1.]]
    aggClassEst:  [[-0.69314718  0.69314718 -0.69314718 -0.69314718  0.69314718]]
    aggErrors:  [[ True]
     [False]
     [False]
     [False]
     [False]]
    aggErrors:  [[ 1.]
     [ 0.]
     [ 0.]
     [ 0.]
     [ 0.]]
    total error:  0.2
    D: [[ 0.5    0.125  0.125  0.125  0.125]]
    classEst:  [[ 1.  1. -1. -1. -1.]]
    aggClassEst:  [[ 0.27980789  1.66610226 -1.66610226 -1.66610226 -0.27980789]]
    aggErrors:  [[False]
     [False]
     [False]
     [False]
     [ True]]
    aggErrors:  [[ 0.]
     [ 0.]
     [ 0.]
     [ 0.]
     [ 1.]]
    total error:  0.2
    D: [[ 0.28571429  0.07142857  0.07142857  0.07142857  0.5       ]]
    classEst:  [[ 1.  1.  1.  1.  1.]]
    aggClassEst:  [[ 1.17568763  2.56198199 -0.77022252 -0.77022252  0.61607184]]
    aggErrors:  [[False]
     [False]
     [False]
     [False]
     [False]]
    aggErrors:  [[ 0.]
     [ 0.]
     [ 0.]
     [ 0.]
     [ 0.]]
    total error:  0.0

图形为：

![20140430113215765][]

# 三、ROC曲线 #

参考文献：

1、[http://blog.csdn.net/mytestmy/article/details/24270513][http_blog.csdn.net_mytestmy_article_details_24270513]

2、[http://blog.csdn.net/abcjennifer/article/details/7359370][http_blog.csdn.net_abcjennifer_article_details_7359370]

3、机器学习实战 李锐等译

从中得出：为什么用曲线下的面积（AUC）代表分类器的平均性能值。

加入绘制ROC曲线及计算AUC函数：

def plotROC(predStrengths, classLabels): import matplotlib.pyplot as plt cur = (1.0,1.0) #cursor绘制光标的位置 ySum = 0.0 #variable to calculate AUC；用于计算AUC的值 numPosClas = sum(array(classLabels)==1.0) #计算正例的数目 yStep = 1/float(numPosClas); #确定y坐标轴上的步长，因为当y为1时，对应的正例个数为numPosClas xStep = 1/float(len(classLabels)-numPosClas) #计算x坐标轴上的步长，因为当x为1时，对应的负例个数为总数减去numPosClas sortedIndicies = predStrengths.argsort()#get sorted index, it's reverse fig = plt.figure() fig.clf() ax = plt.subplot(111) #loop through all the values, drawing a line segment at each point for index in sortedIndicies.tolist()[0]: #利用tolist()转化为列表， if classLabels[index] == 1.0: #每得到一个标签为1.0的类，沿着y轴的方向下降一个步长，即不断降低真阳率（好好体会为什么这样做） delX = 0; delY = yStep; else: delX = xStep; delY = 0; #类似 ySum += cur[1] #先对所有矩形的高度进行累加（当y值下降时不累加），最后再乘以xStep就是其总面积。 #draw line from cur to (cur[0]-delX,cur[1]-delY) 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]) print "the Area Under the Curve is: ",ySum*xStep plt.show()

加入命令：

dataMat,classLabels = loadDataSet('horseColicTraining2.txt')
    weakClassArr,aggClassEst = adaBoostTrainDS(dataMat,classLabels,5)
    plotROC(aggClassEst.T, classLabels)

结果：

![20140507175911265][]

the Area Under the Curve is:  0.827282013186

\#也就是说分对的概率为0.827282013186

[http_stblog.baidu-tech.com_p_19]: http://stblog.baidu-tech.com/?p=19
[http_blog.csdn.net_haidao2009_article_details_7514787]: http://blog.csdn.net/haidao2009/article/details/7514787
[20140430113215765]: /images/20220824/ad347668b3e14347bf23fb6d20e4f861.png
[http_blog.csdn.net_mytestmy_article_details_24270513]: http://blog.csdn.net/mytestmy/article/details/24270513
[http_blog.csdn.net_abcjennifer_article_details_7359370]: http://blog.csdn.net/abcjennifer/article/details/7359370
[20140507175911265]: /images/20220824/8d750effee9047918e11bf9cf66b3135.png