AdaBoost算法

• 簡(jiǎn)介
  • 當(dāng)一個(gè)分類器正確率不那么高時(shí)，稱其為“弱分類器”，或者說(shuō)該分類器的學(xué)習(xí)方法為“弱學(xué)習(xí)方法”。與之對(duì)應(yīng)的，存在“強(qiáng)分類器”和“強(qiáng)學(xué)習(xí)方法”。強(qiáng)學(xué)習(xí)方法的正確率很高。
  • AdaBoost是一種迭代算法，其核心思想是針對(duì)同一個(gè)訓(xùn)練集訓(xùn)練不同的分類器（弱分類器），然后把這些弱分類器集合起來(lái)，構(gòu)成一個(gè)更強(qiáng)的最終分類器（強(qiáng)分類器）。
  • AdaBoost是Adaptive Boosting（自適應(yīng))的縮寫，它的自適應(yīng)在于：前一個(gè)基本分類器分錯(cuò)的樣本會(huì)得到加強(qiáng)，加權(quán)后的樣本再次被用來(lái)訓(xùn)練下一個(gè)基本分類器。同時(shí)，在每一輪中加入一個(gè)新的弱分類器，知道達(dá)到某個(gè)預(yù)定的足夠小的錯(cuò)誤率，或者達(dá)到預(yù)先設(shè)定的最大迭代次數(shù)。
  • 常見(jiàn)的機(jī)器學(xué)習(xí)算法都可以建立弱分類器，不過(guò)最經(jīng)常使用的弱分類器是單層決策樹，又叫決策樹樁（Decision Stump），即層數(shù)為1的決策樹。
• 原理
  • 這里使用單層決策樹作為弱分類器。每一個(gè)訓(xùn)練數(shù)據(jù)都有一個(gè)權(quán)值系數(shù)，注意不是弱分類器的系數(shù)。建立最佳單層決策樹的依據(jù)就是：每個(gè)訓(xùn)練數(shù)據(jù)在單層決策樹中的分類結(jié)果乘以自己的權(quán)值系數(shù)后相加的“和”最小，即分類誤差最小化。
  • 整體說(shuō)來(lái)，AdaBoost迭代算法分為三步。
    • 初始化訓(xùn)練數(shù)據(jù)的權(quán)值分布。如果有N個(gè)樣本，則每一個(gè)訓(xùn)練樣本最開(kāi)始時(shí)都被賦予相同的權(quán)重：$1/N$。
    • 訓(xùn)練弱分類器。具體訓(xùn)練過(guò)程中，如果某個(gè)樣本點(diǎn)已經(jīng)被準(zhǔn)確分類，那么在構(gòu)造下一個(gè)訓(xùn)練集中，它的權(quán)重就被降低；相反，如果某個(gè)樣本點(diǎn)沒(méi)有被準(zhǔn)確分類，那么它的權(quán)重就得到提高。然后，權(quán)重更新過(guò)的樣本集被用于訓(xùn)練下一個(gè)分類器，整個(gè)訓(xùn)練過(guò)程如此迭代進(jìn)行下去。
    • 將各個(gè)訓(xùn)練得到的弱分類器組合成強(qiáng)分類器。各個(gè)弱分類器的訓(xùn)練過(guò)程結(jié)束后，加大分類誤差率小的弱分類器權(quán)重，使其在最終的分類函數(shù)中起著較大的決定作用，而降低分類誤差率大的弱分類器的權(quán)重，使其在最終的分類函數(shù)中起著較小的決定作用。換言之，誤差率低的弱分類器在最終分類器中占的權(quán)重較大，否則較小。
  • 運(yùn)行過(guò)程
    • 訓(xùn)練數(shù)據(jù)中的每一個(gè)樣本，并賦予一開(kāi)始相等的權(quán)重，這些權(quán)重構(gòu)成了向量D。首先在訓(xùn)練數(shù)據(jù)上訓(xùn)練一個(gè)弱分類器并計(jì)算分類器的錯(cuò)誤率，然后在同一數(shù)據(jù)集上再次訓(xùn)練弱分類器。在第二次訓(xùn)練分類器中，會(huì)再次重新調(diào)整每個(gè)樣本的權(quán)重，其中第一次分類錯(cuò)誤的權(quán)重會(huì)提高，第一次分類正確的權(quán)重會(huì)降低。AdaBoost根據(jù)每個(gè)弱分類器的錯(cuò)誤率進(jìn)行計(jì)算，為每個(gè)分類器都配了一個(gè)權(quán)重$\alpha$。
    • 錯(cuò)誤率的定義為：$$\epsilon =\frac{未正確分類的樣本數(shù)目}{所有樣本數(shù)目}$$
    • 而$\alpha$的計(jì)算公式為$$\alpha =\frac{1}{2}\left(\frac{1?\epsilon }{\epsilon }\right)$$
    • 計(jì)算出$\alpha$之后，可以對(duì)權(quán)重向量D進(jìn)行更新，D的計(jì)算方法如下。
    • 如果某個(gè)樣本被錯(cuò)誤分類，那么該樣本的權(quán)重更改為：$$D_i^{(t+1)}=\frac{D_i^{(t)}{e}^{\alpha }}{sum(D)}$$
    • 如果某個(gè)樣本被正確分類，那么該樣本的權(quán)重修改為:$$D_i^{(t+1)}=\frac{D_i^{(t)}{e}^{?\alpha }}{sum(D)}$$
    • 計(jì)算出D后，AdaBoost又開(kāi)始下一輪迭代。AdaBoost算法會(huì)不斷地重復(fù)訓(xùn)練和調(diào)整權(quán)重，直到訓(xùn)練錯(cuò)誤率為0，或者弱分類器的數(shù)目達(dá)到用戶的指定值。
• 實(shí)戰(zhàn)
  • 基于單層決策樹構(gòu)建分類算法
  • 說(shuō)明
    • 構(gòu)造了一個(gè)簡(jiǎn)單數(shù)據(jù)集。
    • 單層決策樹的一個(gè)著名問(wèn)題就是難以通過(guò)一個(gè)分類器直接區(qū)分?jǐn)?shù)據(jù)集。所以使用多個(gè)單層決策樹，就可以構(gòu)建一個(gè)能夠解決分類的分類器。
  • 流程
    • 利用buildStump函數(shù)找到最佳的單層決策樹
    • 將最佳單層決策樹加入單層決策樹數(shù)組
    • 計(jì)算$\alpha$
    • 計(jì)算新的權(quán)重向量D
    • 更新累計(jì)類別估計(jì)值
    • 如果錯(cuò)誤率等于0.0，則退出循環(huán)
  • 代碼實(shí)現(xiàn)
  • # -*- coding:utf-8 -*-from numpy import *import matplotlib.pyplot as pltdef loadSimpData():'''創(chuàng)建一個(gè)簡(jiǎn)單數(shù)據(jù)集:return:'''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, classLabelsdef stumpClassify(dataMatrix, dimen, threshVal, threshIneq):'''對(duì)數(shù)據(jù)進(jìn)行分類通過(guò)閾值比對(duì)將數(shù)據(jù)分類，所有在閾值一邊的會(huì)分到類別1中，而在另一邊的會(huì)分到類別-1中:param dataMatrix::param dimen::param threshVal::param threshIneq::return:'''retArray = ones((shape(dataMatrix)[0], 1))if threshIneq == 'lt':retArray[dataMatrix[:, dimen] <= threshVal] = -1.0else:retArray[dataMatrix[:, dimen] > threshVal] = -1.0return retArraydef buildStump(dataArr,classLabels,D):'''找到最佳決策樹遍歷stumpClassify()函數(shù)所有可能的輸入值，并找到基于數(shù)據(jù)權(quán)重向量D的單層決策樹。:param dataArr::param classLabels::param D::return:'''dataMatrix = mat(dataArr)labelMat = mat(classLabels).Tm, n = shape(dataMatrix)# 用于在特征空間的所有可能值上進(jìn)行遍歷numSteps = 10.0# 存儲(chǔ)給定權(quán)重向量D時(shí)所得到的單層決策樹信息bestStump = {}bestClasEst = mat(zeros((m, 1)))# 記錄可能的最小錯(cuò)誤率minError = inffor i in range(n):rangeMin = dataMatrix[:, i].min()rangeMax = dataMatrix[:, i].max()stepSize = (rangeMax-rangeMin)/numStepsfor j in range(-1, int(numSteps) + 1):for inequal in ['lt', 'gt']:threshVal = (rangeMin + float(j) * stepSize)predictedVals = stumpClassify(dataMatrix, i, threshVal, inequal)errArr = mat(ones((m, 1)))errArr[predictedVals == labelMat] = 0weightedError = D.T * errArrprint('split：dim %d,thresh %.2f,thresh ineqal:%s,the weighted error is %.3f' % (i, threshVal, inequal, weightedError))if weightedError < minError:minError = weightedErrorbestClasEst = predictedVals.copy()bestStump['dim'] = ibestStump['thresh'] = threshValbestStump['ineq'] = inequalreturn bestStump, minError, bestClasEstdef adaBoostTrainDS(dataArr,classLabels,numIt=40):'''完整的訓(xùn)練算法:param dataArr::param classLabels::param numIt::return:'''weakClassArr = []m = shape(dataArr)[0]D = mat(ones((m, 1))/m)aggClassEst = mat(zeros((m, 1)))for i in range(numIt):bestStump, error, classEst = buildStump(dataArr, classLabels, D)print("D:", D.T)alpha = float(0.5*log((1.0-error)/max(error, 1e-16)))bestStump['alpha'] = alphaweakClassArr.append(bestStump)print("classEst: ", classEst.T)# 計(jì)算下次迭代的新權(quán)重Dexpon = multiply(-1*alpha*mat(classLabels).T, classEst)D = multiply(D, exp(expon))D = D/D.sum()# 計(jì)算累加錯(cuò)誤率aggClassEst += alpha*classEstprint("aggClassEst: ", aggClassEst.T)aggErrors = multiply(sign(aggClassEst) != mat(classLabels).T, ones((m, 1)))errorRate = aggErrors.sum()/mprint("total error: ", errorRate)if errorRate == 0.0:breakreturn weakClassArr, aggClassEstdef adaClassify(datToClass,classifierArr):'''實(shí)現(xiàn)分類函數(shù)，測(cè)試算法:param datToClass::param classifierArr::return:'''dataMatrix = mat(datToClass)m = shape(dataMatrix)[0]aggClassEst = mat(zeros((m, 1)))for i in range(len(classifierArr)):classEst = stumpClassify(dataMatrix, classifierArr[0][i]['dim'], classifierArr[0][i]['thresh'], classifierArr[0][i]['ineq'])aggClassEst += classifierArr[0][i]['alpha']*classEstprint(aggClassEst)return sign(aggClassEst)def loadDataSet(fileName):'''在難數(shù)據(jù)集上應(yīng)用自適應(yīng)數(shù)據(jù)加載函數(shù):param fileName::return:'''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 dataMat, labelMatdef plotROC(predStrengths, classLabels):'''繪制ROC曲線:param predStrengths::param classLabels::return:'''cur = (1.0, 1.0)ySum = 0.0numPosClas = sum(array(classLabels) == 1.0)yStep = 1/float(numPosClas)xStep = 1/float(len(classLabels)-numPosClas)sortedIndicies = predStrengths.argsort()fig = plt.figure()fig.clf()ax = plt.subplot(111)for index in sortedIndicies.tolist()[0]:if classLabels[index] == 1.0:delX = 0delY = yStepelse:delX = xStepdelY = 0ySum += cur[1]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])plt.show()print("the Area Under the Curve is: ", ySum*xStep)if __name__ == '__main__':dataMat, classLabels = loadSimpData()classifierArr = adaBoostTrainDS(dataMat, classLabels, 30)adaClassify([[5, 5], [0, 0]], classifierArr)
• 補(bǔ)充說(shuō)明
  • 考書《Python3數(shù)據(jù)分析與機(jī)器學(xué)習(xí)實(shí)戰(zhàn)》
  • 具體數(shù)據(jù)集和代碼可以查看我的GitHub，歡迎star或者fork

總結(jié)

以上是生活随笔為你收集整理的机器学习-分类之AdaBoost原理及实战的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。