元算法是對其他算法進(jìn)行組合的一種方式闸拿。本章首先討論不同分類器的集成方法，然后主要關(guān)注boosting方法及其代表分類器Adaboost峻凫。
Adaboost
優(yōu)點(diǎn)：泛化錯(cuò)誤率低矮湘，易編碼，可以應(yīng)用在大部分分類器上醋寝，無參數(shù)調(diào)整
缺點(diǎn)：對離群點(diǎn)敏感
適用數(shù)據(jù)類型：數(shù)值型和標(biāo)稱型數(shù)據(jù)
bagging：自舉匯聚法（bootstrap aggregating）搞挣，也成為bagging方法，是從原始數(shù)據(jù)集選擇S次吼得到S個(gè)新數(shù)據(jù)集的一種技術(shù)音羞。新數(shù)據(jù)集大小和原始數(shù)據(jù)集的大小相等囱桨。
boosting：通過集中關(guān)注被已有分類器錯(cuò)分的那些數(shù)據(jù)來獲得新的分類器。
單層決策樹（decision stump嗅绰，也稱決策樹樁）舍肠，是一種簡單的決策樹搀继。
#adaboost.py
from numpy import *
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
并加入
import adaboost
datMat,classLabels = adaboost.loadSimpData()
接下來可以通過構(gòu)建多個(gè)函數(shù)來建立單層決策樹，偽代碼如下
將最小錯(cuò)誤率minError設(shè)為正無窮
對數(shù)據(jù)集中的每一個(gè)特征（每一層循環(huán)）：
對每一個(gè)步長（第二層循環(huán)）：
對每一個(gè)不等號（第三層循環(huán)）：
建立一顆單層決策樹并利用加權(quán)數(shù)據(jù)集對它進(jìn)行測試
如果錯(cuò)誤率低于minError貌夕，則將當(dāng)前單層決策樹設(shè)為最佳單層決策樹
返回最佳單層決策樹
接下來開始構(gòu)造這個(gè)函數(shù)
#7-1 單層決策樹生成函數(shù)
def stumpClassify(dataMatrix,dimen,threshVal,threshIneq):#閾值比較分類
retArray = ones((shape(dataMatrix)[0],1))
if threshIneq == "lt":
retArray[dataMatrix[:,dimen] <= threshVal] = -1.0
else:
retArray[dataMatrix[:,dimen] > threshVal] = -1.0
return retArray
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#無窮大
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"]:
threshVal = (rangeMin + float(j)*stepSize)
predictedVals = stumpClassify(dataMatrix,i,threshVal,inequal)
errArr = mat(ones((m,1)))
errArr[predictedVals == labelMat] = 0
weightedError = D.T*errArr
print "split: dim %d, thresh %.2f, thresh ineqal: %s, the weighted error is %.3f" % (i, threshVal, inequal, weightedError)
#將當(dāng)前錯(cuò)誤率與已有的最小錯(cuò)誤率進(jìn)行對比民镜，如果當(dāng)前的值比較小啡专，那么就在詞典bestStump中保存該單層決策樹
if weightedError < minError:
minError = weightedError
bestClasEst = predictedVals.copy()
bestStump["dim"] = i
bestStump["thresh"] = threshVal
bestStump['ineq'] = inequal
return bestStump,minError,bestClasEst
#開始運(yùn)行
D = mat(ones((5,1))/5)
adaboost.buildStump(datMat, classLabels,D)
#省略部分
split: dim 1, thresh 1.88, thresh ineqal: gt, the weighted error is 0.600
split: dim 1, thresh 1.99, thresh ineqal: lt, the weighted error is 0.600
split: dim 1, thresh 1.99, thresh ineqal: gt, the weighted error is 0.600
split: dim 1, thresh 2.10, thresh ineqal: lt, the weighted error is 0.400
split: dim 1, thresh 2.10, thresh ineqal: gt, the weighted error is 0.400
Out[26]:
({'dim': 0, 'ineq': 'lt', 'thresh': 2.0}, matrix([[ 0.4]]), array([[ 1.],
[ 1.],
[ 1.],
[ 1.],
[ 1.]]))
上述單層決策樹的生成函數(shù)時(shí)決策樹的簡化版本，也是所謂的弱學(xué)習(xí)器制圈。
下面實(shí)現(xiàn)一個(gè)完整AdaBoost算法所需要的所有信息们童，偽代碼如下：
對每次迭代:
利用buildStump()函數(shù)找到最佳的單詞決策樹
將最佳單層決策樹加入到單層決策樹數(shù)組
計(jì)算alpha
計(jì)算新的權(quán)重向量D
更新累計(jì)類別估計(jì)值
如果錯(cuò)誤率等于0.0，則退出循環(huán)
繼續(xù)補(bǔ)充adaboost.py
#7-2 基于單層決策樹的AdaBoost訓(xùn)練過程
def adaBoostTrainDS(dataArr,classLabels,numIt=40):#數(shù)據(jù)集鲸鹦，類別標(biāo)簽慧库，迭代次數(shù)
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)))#確保沒有除0溢出
bestStump["alpha"] = alpha
weakClassArr.append(bestStump)
print "classEst:",classEst.T
expon = multiply(-1*alpha*mat(classLabels).T,classEst)
D = multiply(D,exp(expon))
D = D/D.sum()
aggClassEst += alpha*classEst#更新累計(jì)估計(jì)值
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
并使用該函數(shù)
In [48]: runfile('E:/上學(xué)/機(jī)器學(xué)習(xí)實(shí)戰(zhàn)/7.利用AdaBoost元算法提高分類性能/adaboost.py', wdir='E:/上學(xué)/機(jī)器學(xué)習(xí)實(shí)戰(zhàn)/7.利用AdaBoost元算法提高分類性能')
Reloaded modules: adaboost
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]]
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]]
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]]
total error: 0.0
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]]
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]]
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]]
total error: 0.0
#觀察classifierArray的值
In [62]: classifierArray
Out[62]:
([{'alpha': 0.6931471805599453, 'dim': 0, 'ineq': 'lt', 'thresh': 1.3},
{'alpha': 0.9729550745276565, 'dim': 1, 'ineq': 'lt', 'thresh': 1.0},
{'alpha': 0.8958797346140273,
'dim': 0,
'ineq': 'lt',
'thresh': 0.90000000000000002}],
matrix([[ 1.17568763],
[ 2.56198199],
[-0.77022252],
[-0.77022252],
[ 0.61607184]]))
我們已經(jīng)實(shí)際寫完了大部分的代碼，現(xiàn)在需要將弱分類器的訓(xùn)練過程從程序中抽出來馋嗜，然后應(yīng)用到某個(gè)具體的實(shí)例上去齐板。
def adaClassify(datToClass,classifierArr):#待分類樣本，多個(gè)弱分類器組成的數(shù)組
dataMatrix = mat(datToClass)
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'])
aggClassEst += classifierArr[i]['alpha']*classEst
print aggClassEst
return sign(aggClassEst)#返回符號
datArr,labelArr = adaboost.loadSimpData()
classifierArr = adaboost.adaBoostTrainDS(datArr,labelArr,30)
In [75]: adaboost.adaClassify([0,0],classifierArr)
[[-0.69314718]]
[[-1.66610226]]
[[-2.56198199]]
Out[75]: matrix([[-1.]])
In [76]: adaboost.adaClassify([[5,5],[0,0]],classifierArr)
[[ 0.69314718]
[-0.69314718]]
[[ 1.66610226]
[-1.66610226]]
[[ 2.56198199]
[-2.56198199]]
Out[76]:
matrix([[ 1.],
[-1.]])
我們可以看到葛菇，數(shù)據(jù)點(diǎn)的分類結(jié)果也會(huì)隨著迭代的進(jìn)行而越來越強(qiáng)甘磨，接下來我們將會(huì)將該分類器應(yīng)用到一個(gè)規(guī)模更大，難度也更大的真實(shí)數(shù)據(jù)集中眯停。
首先我們向文件加載數(shù)據(jù)
#自適應(yīng)加載函數(shù)
def loadDataSet(fileName):
numFeat = len(open(fileName).readline().split('\t'))
dataMat = []; labelMat = []
fr = open(fileName)
for line in fr.readlines():
lineArr = []
curLine = line.strip().split('\t')#\t是tab鍵
for i in range(numFeat-1):
lineArr.append(float(curLine[i]))
dataMat.append(lineArr)
labelMat.append(float(curLine[-1]))
return dataMat,labelMat
并且測試該函數(shù)
In [18]: import adaboost
...: datArr, labelArr = loadDataSet("horseColicTraining2.txt")
...: classifierArray = adaBoostTrainDS(datArr, labelArr, 10)
...:
total error: 0.284280936455
total error: 0.284280936455
total error: 0.247491638796
total error: 0.247491638796
total error: 0.254180602007
total error: 0.240802675585
total error: 0.240802675585
total error: 0.220735785953
total error: 0.247491638796
total error: 0.230769230769
In [19]: testArr,testLabelArr = adaboost.loadDataSet('horseColicTest2.txt')
In [20]: prediction10 = adaboost.adaClassify(testArr,classifierArray)
[[ 0.46166238]
[ 0.46166238]
[-0.46166238]
...,
#省略部分
...,
[ 0.80958618]
[ 0.54030781]
[ 0.5273375 ]]
In [21]: errArr = mat(ones((67,1)))
In [22]: errArr[prediction10!=mat(testLabelArr).T].sum()
Out[22]: 16.0
如圖7-1所示济舆，使用50個(gè)分類器就可以獲得較高的性能。但是錯(cuò)誤率在達(dá)到一個(gè)最小值以后又開始上升莺债，這類現(xiàn)象稱為過擬合滋觉。
表7-1
很多人認(rèn)為AdaBoost和SVM是監(jiān)督機(jī)器學(xué)習(xí)中最強(qiáng)大的兩種方法。實(shí)際上齐邦，這兩者之間有不少相似之處椎侠。我們可以吧弱分類器想象成SVM中的一個(gè)核函數(shù)，也可以按照最大化某個(gè)最小間隔的方式重寫AdaBoost算法措拇。而他們的不同就在于其所定義的間隔計(jì)算方式有所不同肺蔚，因此導(dǎo)致的結(jié)果也不同。
ROC曲線代表接受者特征儡羔。在最佳的分類器下宣羊，點(diǎn)應(yīng)該盡可能在左上角，不同的ROC曲線進(jìn)行比較的一個(gè)參數(shù)是曲線下面積汰蜘。一個(gè)完美的分類器的AUC為1.0仇冯，而隨機(jī)猜測的未0.5。
def plotROC(predStrengths, classLabels):#分類器的預(yù)測強(qiáng)度
import matplotlib.pyplot as plt
cur = (1.0,1.0)#繪制光標(biāo)的位置
ySum = 0.0#計(jì)算AUC的值
numPosClas = 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 = 0; delY =yStep;
else:
delX = xStep; delY = 0;
ySum += 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
datArr, labelArr = loadDataSet("horseColicTraining2.txt")
classifierArray,aggClassEst = adaboost.adaBoostTrainDS(datArr,labelArr,10)
plotROC(aggClassEst.T,labelArr)
ROC圖
the Area Under the Curve is: 0.858296963506
