第十章 集成算法

机器学习的算法好多种,大部分的算法都是用来做分类。在生活中,我们也会经常碰到对一件事情进行评分,比如唱歌比赛对各个选择进行评分,而通常一场比赛中,为了分数的公平性,通常评审不止一个人,通过不同评审的评分后加权求平均值来作为选手最后的得分,也就是对选手进行分类。

在机器学习中能否也加入这种机制,通过已知的数据,学习不同的分类器,在预测时使用这些分类器的组合,对未知的数据进行分类。这种分类的方式叫做集成学习算法。

当然不能拿同样训练方法的几个分类器,这样并没有作用,如何建立分类器是集成学习算法的关键。现在有较多的方法,这里介绍Adaboost算法和bagging算法。

Adaboost算法

在训练分类器的过程中,在一些较为复杂的数据中,一个分类器并不可能把所有的数据都正确的分类,通过某一种算法建立了第一个分类器后,能够知道哪些数据是被分错类的,这样可以认为这个分类器对这种数据是无能为力的,对于这些点不能寄希望在这个分类器上,在建立另一个分类器,但这时候可以利用前面这个分类器的经验,怎么使用这些经验,经验到底是什么?既然这些点难以找到正确的分类,是不是说明这些点在这个分类器中的误差是被忽略掉的,因为在训练分类器的时候是使用误差进行分类的,在接下来的分类器中人为的放大这些点的误差,优化分类器的决策,那之前的得到正确的数据会不会有乱了呢?这是个问题,但有一个考核的目标就是总分类器的总误差是下降的,因此在考虑如何确定放大倍数是有现成的方法的。

通用Adaboost算法的过程如下:

为了方便说明,这里的分类器为0-1分类器。其中训练数据集,

$$T=\begin{Bmatrix} (x_1,y_1),(x_2,y_2),...,(x_N,y_N)\ \end{Bmatrix},其中x_i \in \chi \subseteq R^n,y_i \in \begin{Bmatrix} -1,1\ \end{Bmatrix}$$

最终要确定需要几个分类器,各个分类器的参数是怎么样的情况。

  • 一开始并不知道那些数据分不出来,因此所有数据点的权重都是一样的用来表示:

$$D1=(w<>{11},w{1i},..,w<>{1n}),w{1i}=\frac{1}{N},i=1,2,..,N$$

下面确定

  • 对$m=1,2,...,M$,通过算法(比如决策树)训练分类器为$G_m(x)= \chi \rightarrow \begin{Bmatrix} -1,1\ \end{Bmatrix}$:,计算$G_m(x)$上产生的分类误差,分类误差为权重和分错的乘积。$e_m=P(G_m(x_i) \not= y<>i)=\sum{i=1}^Nw_{mi}I(G_m(x_i) \not= y_i)$

  • 更新训练数据的权重:$D<>{m+1}=(w{m+1,1},...,w<>{m+1,i},...,w{m+1,N})$,计算各个权重$w<>{m+1,i},w{m+1,i}=\frac{w_{m,i}}{Z_m}exp(-\alpha_my_iG_m(x_i))$,其中两参数是未知的$Z_m,\alpha_m$,计算方法为$\alpha_m=\frac{1}{2}log\frac{1-e_m}{e},Z<>m=\sum{i=1}^Nexp(-\alpha_my_iG_m(x_i))$,简化$Z_m,Z<>m=\sum{i=1}^Nw_{mi}$,。不断的更新这个过程直到误差满足一定的条件。就能求得各个分类器$G_m(x)$和各个$G_m(x)$权重$\alpha_m$。

  • 分类器为0-1分类器,最终的分类器为:$G(x)=sign(\sum_{m=1}^M\alpha_mG_m(x))$。

使用决策树算法实现Adaboost算法

在训练的过程中,不管采用哪种分类器方法,关键的一点是在计算总误差的时候需要注意权重参数。在机器学习实战中采用的是决策树,单个决策树代码如下:

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

在训练决策树的时候,误差的算法需要加入权重$D_m$,使用的是加权的误差对决策树进行分类:

def buildStump(dataArr,classLabels,D):
    dataMatrix = mat(dataArr); labelMat = mat(classLabels).T
    m,n = shape(dataMatrix)
    numSteps = 10.0; bestStump = {}; 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
        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:
                    minError = weightedError
                    bestClasEst = predictedVals.copy()
                    bestStump['dim'] = i
                    bestStump['thresh'] = threshVal
                    bestStump['ineq'] = inequal
    return bestStump,minError,bestClasEst

不断的产生决策树,计算$\alpha_m=\frac{1}{2}log\frac{1-e_m}{e<>m}$,算出下一个决策树的$D{m+1}$,即:

$$w<>{m+1,i}=\frac{w{m,j}}{\sum<>{i=1}^Nw{mi}}exp(-\alpha_my_iG_m(x<>i))=\frac{w{m,i}}{sum(G_m)}exp(-\alpha_my_iG_m(x_i))$$

def adaBoostTrainDS(dataArr,classLabels,numIt=40):
    weakClassArr = []
    m = shape(dataArr)[0]
    D = mat(ones((m,1))/m)   #init D to all equal
    aggClassEst = mat(zeros((m,1)))
    for i in range(numIt):
        bestStump,error,classEst = buildStump(dataArr,classLabels,D)#build Stump
        #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
        bestStump['alpha'] = alpha  
        weakClassArr.append(bestStump)                  #store Stump Params in Array
        #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.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)))
        errorRate = aggErrors.sum()/m
        print "total error: ",errorRate
        if errorRate == 0.0: break
    return weakClassArr,aggClassEst

训练完成以后,构建分类器:

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[i]['dim'],\
                                 classifierArr[i]['thresh'],\
                                 classifierArr[i]['ineq'])#call stump classify
        aggClassEst += classifierArr[i]['alpha']*classEst
        print aggClassEst
    return sign(aggClassEst)

Adaboost的算法过程就是如上的一个计算过程,之前还有一个问题,总分类器的总误差为何能下降,这可以对Adaboost的算法过的误差进行分析,具体的分析过程不再这里整理。

Bagging算法

Bagging算法是最符合评分系统的算法,在Bagging算法中,包原始的数据集分为S份,在S个数据集建好之后,用某个学习算法对数据集进行训练,得出S个分类器。最具有代表性的是随机森林算法(random forest),这种算法较容易用各种语言实现。

PS: 如本文对您有帮助,不妨通过一下方式支持一下博主噢 ^_^

官方
微信
官方微信
Q Q
咨询
意见
反馈
返回
顶部