机器学习(4)—— Adaboost学习

《机器学习实战》第七章


    总结:Adaboost是一个2分类器

Adaboost其中的弱分类器可以是任意一种分类器,但是常用的是单层决策树

每一层弱分类器包括:特征维度Index;

       阈值(在这一特征维度上的);

       哪边是正lt or gt;

       弱分类器的权重αi

每一层弱分类器的确定包含三个循环:特征维度上(eg二维特征,阈值是选在横轴上,还是纵轴上);

    阈值(按照一定的步长,在某一轴上遍历选阈值);

        阈值哪边为正lt or gt;

               Adaboost的核心是根据弱分类器的判断结果,更新样本权重。分错的样本对应的权重增加,正确的样本权重减小。

               预测新样本∑(弱分类器的权重αi * 弱分类器的预测结果)




定义:说到boosting算法,就不得提一提bagging算法,他们两个都是把一些弱分类器组合起来来进行分类的方法,统称为集成方法(ensemble method)。类似于投资,“不把鸡蛋放在一个篮子”,虽然每个弱分类器分类的不那么准确,但是如果把多个弱分类器组合起来可以得到相当不错的结果,另外要说的是集成方法还可以组合不同的分类器,而Adaboost和boosting算法的每个弱分类器的类型都一样的。他们两个不同的地方是:boosting的每个弱分类器组合起来的权重不一样,本节的Adaboost就是一个例子,而bagging的每个弱分类器的组合权重是相等,代表的例子就是random forest。Random forest的每个弱分类器是决策树,输出的类别有多个决策树分类的类别的众数决定。

简单的说,Adaboost就是不断的对同样的数据使用同一个分类器进行分类,直到所有的数据都分类完毕,或是达到迭代的次数为止。这是一个串行训练的过程,在每个迭代过程中,分类器和数值的权重都不一样,下次的权重会依赖于当前分类器的分类结果。


具体算法:

(1)分类器的系数(权重)和分类器的错误率相关,具体如下:

机器学习(4)—— Adaboost学习


(2)数据的权值:对于分类器分类正确的数据减小它的权值,相反对于分类器分错的数据增大它的权值,这样使得我们在下次的分类过程中更加关注那些被分错的数据,具体的公式如下:

机器学习(4)—— Adaboost学习


以上我们就概括了Adaboost的整个算法,接下来我们就要选择一个分类器,进行Adaboost的实现。


弱分类器:单层决策树

其实就是一个单节点的决策树。构造单层决策树,这部分的构造的思路和前面的决策树是一样的,只是这里的评价体系不是熵而是加权的错误率,这里的加权是通过数据的权重D来实现的,每一次build权重都会因上一次分类结果不同而不同。

单层决策树的伪代码:

将minError设置为无穷大

对数据集中的每一个属性

    对每个步长(第二层循环):

        对每个不等号:

            建立一棵单层决策树并利用加权数据集对其进行测试

            如果错误率低于minError,则将当前的决策树设为最佳单层决策树

返回最佳单层决策树

下面进行代码的实现,首先建立adaboost.py文件。同样,我们需要一个简单的数据集用来测试我们的算法。编辑代码如下:

[python] view plain copy
 print?
  1. #加载一个简单的数据集合,该集合很难用一条平行于坐标轴的直线进行分类  
  2. def loadSimpData():  
  3.     datMat=matrix([[1.,2.1],  
  4.                    [2.,1.1],  
  5.                    [1.3,1.],  
  6.                    [1.,1.];  
  7.                    [2.,1.]])  
  8.     classLabels=[1.0,1.0,-1.0,-1.0,1.0]  
  9. return datMat,classLabels  
接下来按照伪代码实现单层决策树:

[python] view plain copy
 print?
  1. def buildStump(dataArr,classLables,D):  
  2.        dataMatrix=mat(dataArr)  
  3.        #.T表示转置  
  4.        labelMat=classLables.T  
  5.        #m表示数据集个数,n表示属性个数  
  6.        m,n=shape(dataMatrix)  
  7.        #步长  
  8.        numSteps=10.0  
  9.        #用来存放最佳单层决策树  
  10.        bestStump={};bestClassEst=mat(zeros((m,1)))  
  11.        #按照伪代码实现  
  12.        minError=inf  
  13.        for i in range(n):  
  14.            rangeMin=dataMatrix[:,i].min()  
  15.            rangeMax=dataMatrix[:,i].max()  
  16.            stepSize=(rangeMax-rangeMin)/numSteps;  
  17.            for j in range(-1,int(numSteps)+1):  
  18.                 for inequal in ['lt','gt']:  
  19.                    threshValue=(rangeMin+float(j)*stepSize)  
  20.                    predictVals=stumpClassify(dataMatrix,i,threshValue,inequal)  
  21.                    #计算误差,初始化错误矩阵为1,如果判断正确则设置为0  
  22.                    errArr=mat(ones((m,1)))  
  23.                   # print predictVals==labelMat  
  24.                    errArr[predictVals==labelMat]=0  
  25.                    weightedError=D.T*errArr  
  26.                    print "split: dim %d, thresh %.2f, thresh inequal: %s, the weighted error: %.3f" \  
  27.                          %(i, threshValue, inequal, weightedError)    
  28.                    if weightedError < minError:    
  29.                       minError = weightedError    
  30.                       bestClassEst = predictVals.copy()    
  31.                       bestStump['dim']=i    
  32.                       bestStump['thresh']=threshValue    
  33.                       bestStump['ineq']=inequal  
  34.        return bestStump,minError,bestClassEst;  
测试代码:


机器学习(4)—— Adaboost学习

...................

机器学习(4)—— Adaboost学习

这样我们就找到了一个弱分类器,有了这个弱分类器,接下来我们只需要根据公式构建Adaboost即可。

伪代码如下:

对每次迭代:

    利用buildStump找到最佳的单层决策树

    将最佳单层决策树加入数组

    计算分类器系数alpha

    计算新的权重D

    更新累计类别估计值

    如果错误率为0.0,跳出循环


继续编辑代码如下:

[python] view plain copy
 print?
  1. #numIt表示循环次数  
  2. def adaBoostTrainDS(dataArr, classLabels, numIt = 40):  
  3.     #用于存放弱分类器的数组  
  4.     weakClassArr = []  
  5.     #数据个数  
  6.     m = shape(dataArr)[0]  
  7.     #权重初始化为相等值1/m  
  8.     D = mat(ones((m,1))/m)    
  9.     aggClassEst = mat(zeros((m,1)))    
  10.     for i in range(numIt):    
  11.         bestStump, error, classEst = buildStump(dataArr, classLabels, D)    
  12.         print "D:", D.T  
  13.         #计算alpha  
  14.         alpha = float(0.5*log((1.0-error)/max(error,1e-16)))    
  15.         bestStump['alpha']=alpha    
  16.         weakClassArr.append(bestStump)    
  17.         print "classEst: ", classEst.T  
  18.         #这里需要说明一下,对于classLabels表示数据应该属于哪一类,classEst表示预测的分类结果,两者都为-1,1的list  
  19.         #如果分对了,两者相乘结果为1,相反为-1.正好符合提到的公式  
  20.         expon = multiply(-1*alpha*mat(classLabels).T, classEst)    
  21.         D = multiply(D, exp(expon))    
  22.         D = D/D.sum()    
  23.         aggClassEst += alpha*classEst    
  24.         print "aggClassEst: ", aggClassEst.T    
  25.         aggErrors = multiply(sign(aggClassEst) != mat(classLabels).T, ones((m,1)))    
  26.         errorRate = aggErrors.sum()/m    
  27.         print "total error: ", errorRate    
  28.         if errorRate == 0.0:break    
  29.     return weakClassArr    
  30.                      
测试程序得到如下结果:

机器学习(4)—— Adaboost学习
从上面的结果可以看出,如果对某个数据分错了,adaboost在下一次分类中会增加分错数据的权重,直到所有的数据都分类正确为止。

下面我们看一下完整的分类器:

机器学习(4)—— Adaboost学习

这样我们就完成了整个算法的实现。