前面介紹了幾種不同的分類器，若把不同的分類器組合起來就是集成方法(ensemble method)或者元算法(meta-algorithm)
集成方法通過組合多個基分類器(base classifier)來完成學(xué)習(xí)任務(wù)，基分類器一般采用的是弱可學(xué)習(xí)(weakly learnable)分類器通過集成方法組合成一個強可學(xué)習(xí)(strongly learnable)分類求待牵。弱可學(xué)習(xí)是指學(xué)習(xí)的正確率僅略優(yōu)于隨機猜測的多項式學(xué)習(xí)算法拜隧；強可學(xué)習(xí)指正確率較高的多項式學(xué)習(xí)算法
- 集成方法包括Bagging和Boosting
Bagging和Boosting都是將已有的分類或回歸算法通過一定方式組合起來惑灵，形成一個性能更加強大的分類器盅藻，下面介紹二者的不同
Bagging
自舉匯聚法(bootstrap aggregating)，也稱為bagging方法。Bagging對訓(xùn)練數(shù)據(jù)采用自舉采樣辕羽，即有放回地采樣數(shù)據(jù)，主要思想:
- 從原始樣本集中抽取訓(xùn)練集。每輪從原始樣本集中使用Booststraping的方法抽取n個訓(xùn)練樣本(在訓(xùn)練集中熟妓，有些樣本可能被多次抽取到，而有些樣本可能一次都沒有被抽到)栏尚。共進行k輪抽取起愈，得到k個訓(xùn)練集
- 每次使用一個訓(xùn)練集得到一個模型，k個訓(xùn)練集共得到k個模型译仗。
- 對分類問題:將上步得到的k個模型采用投票的方式得到分類結(jié)果抬虽；對回歸問題，計算上述的均值作為最后的結(jié)果
Boosting
Boosting是一種與Bagging很類似的技術(shù)纵菌。Boosting的思路是采用重賦權(quán)重法迭代地訓(xùn)練基分類器阐污，主要思想:
- 每一輪的訓(xùn)練數(shù)據(jù)樣本賦予一個權(quán)重，并且每一輪樣本的權(quán)值分布依賴上一輪的分類結(jié)果
- 基分類器之間采用序列式的線性加權(quán)方式進行組合
Bagging咱圆，Boosting二者之間的區(qū)別
Bagging：訓(xùn)練集是在原始集中有放回選取的笛辟，從原始集中選出的各輪訓(xùn)練集之間是獨立的；使用均勻取樣序苏，每個樣例的權(quán)重相等手幢；所有預(yù)測函數(shù)的權(quán)重相等；各個預(yù)測函數(shù)可以并行生成
Boosting：每一輪的訓(xùn)練集不變杠览，只是訓(xùn)練集中每個樣例在分類器中的權(quán)重發(fā)生變化弯菊。而權(quán)值是根據(jù)上一輪的分類結(jié)果進行調(diào)整。根據(jù)錯誤率不斷調(diào)整樣例的權(quán)值踱阿，錯誤率越大則權(quán)重越大管钳；每個弱分類器都有相應(yīng)的權(quán)重，對于分類誤差小的分類器會有更大的權(quán)重软舌；各個預(yù)測函數(shù)只能順序生成才漆，因為后一個模型參數(shù)需要前一輪模型的結(jié)果。
訓(xùn)練算法:基于錯誤提升分類器的性能
AdaBoost是adaptive boosting(自適應(yīng)boosting)的縮寫佛点，其運行過程如下:訓(xùn)練數(shù)據(jù)中的每個樣本醇滥，并賦予其一個權(quán)重黎比，這些權(quán)重構(gòu)成向量D。一開始鸳玩，這些權(quán)重都初始化成相等值阅虫。首先在訓(xùn)練數(shù)據(jù)上訓(xùn)練出一個弱分類器并計算該分類器的錯誤率(ps:所謂弱分類器中的"弱"意味著分類器的性能比隨機猜測要略好，但是也不會好太多不跟。這就是說颓帝，在二分類情況下弱分類器的錯誤率會高于50%，而"強"分類器的錯誤率將會低很多)窝革，然后在同一數(shù)據(jù)集上再次訓(xùn)練弱分類器购城。在分類器的第二次訓(xùn)練中，將會重新調(diào)整每個樣本的權(quán)重虐译，其中第一次分對的樣本的權(quán)重將會降低瘪板，而第一次分錯的樣本的權(quán)重將會提高。為了從所有弱分類器中得到最終的分類結(jié)果漆诽，AdaBoost為每個分類器都分配一個權(quán)重值alpha侮攀，這些alpha值是基于每個弱分類器的錯誤率進行計算的。其中錯誤率的定義:
alpha的計算公式:
AdaBoost算法的流程圖:
左邊是數(shù)據(jù)集拴泌，其中直方圖的不同寬度表示每個樣例上的不同權(quán)重魏身。在經(jīng)過一個分類器之后，加權(quán)的預(yù)測結(jié)果會通過三角形中的alpha值進行加權(quán)蚪腐。每個三角形中輸出的加權(quán)結(jié)果在圓形中求和，從而得到最終的輸出結(jié)果
計算出alpha值之后税朴，可以對權(quán)重向量D進行更新回季，以使得那些正確分類的樣本的權(quán)重降低而錯分樣本的權(quán)重升高。
D的計算方法如下:
如果某個樣本被正確分類正林，那么該樣本的權(quán)重更改為:
如果某個樣本被錯分泡一，那么該樣本的權(quán)重更改為:
在計算出D之后，AdaBoost又開始進入下一輪迭代觅廓。AdaBoost算法會不斷地重復(fù)訓(xùn)練和調(diào)整權(quán)重的過程鼻忠，直到訓(xùn)練錯誤率為0或者弱分類器的數(shù)目達到用戶的指定值為止
基于單層決策樹構(gòu)建弱分類器
單層決策樹是一種簡單的決策樹，由于它僅基于單個特征來做決策杈绸，并且只有一次分裂過程帖蔓，因此它實際上就是一個樹樁。
準(zhǔn)備數(shù)據(jù)集
def loadSimpData():
"""
創(chuàng)建單層決策樹的數(shù)據(jù)集
Parameters:
無
Returns:
dataMat - 數(shù)據(jù)矩陣
classLabels - 數(shù)據(jù)標(biāo)簽
"""
datMat = np.matrix([[ 1. , 2.1],
[ 1.5, 1.6],
[ 1.3, 1. ],
[ 1. , 1. ],
[ 2. , 1. ]])
classLabels = [1.0, 1.0, -1.0, -1.0, 1.0]
return datMat,classLabels
數(shù)據(jù)可視化
def showDataSet(dataMat, labelMat):
"""
數(shù)據(jù)可視化
Parameters:
dataMat - 數(shù)據(jù)矩陣
labelMat - 數(shù)據(jù)標(biāo)簽
Returns:
無
"""
data_plus = [] #正樣本
data_minus = [] #負樣本
for i in range(len(dataMat)):
if labelMat[i] > 0:
data_plus.append(dataMat[i])
else:
data_minus.append(dataMat[i])
data_plus_np = np.array(data_plus) #轉(zhuǎn)換為numpy矩陣
data_minus_np = np.array(data_minus) #轉(zhuǎn)換為numpy矩陣
plt.scatter(np.transpose(data_plus_np)[0], np.transpose(data_plus_np)[1]) #正樣本散點圖
plt.scatter(np.transpose(data_minus_np)[0], np.transpose(data_minus_np)[1]) #負樣本散點圖
plt.show()
測試
dataArr,classLabels = loadSimpData()
showDataSet(dataArr,classLabels)
輸出
如果想要試著從某個坐標(biāo)軸選擇一個值(即選擇一條與坐標(biāo)軸平行的直線)來將所有的圓形點和方形點分開瞳脓，顯然是不可能的塑娇。這就是單層決策樹難以處理的有名問題。通過使用多顆單層數(shù)劫侧，就可以構(gòu)建一個能夠?qū)υ摂?shù)據(jù)集完全正確分類的分類器
通過兩個函數(shù)建立單層決策樹
第一個函數(shù)將用于測試是否有某個值小于或者大于我們正在測試的閾值
def stumpClassify(dataMatrix,dimen,threshVal,threshIneq):
"""
單層決策樹分類函數(shù)
Parameters:
dataMatrix - 數(shù)據(jù)矩陣
dimen - 第dimen列埋酬，也就是第幾個特征
threshVal - 閾值
threshIneq - 標(biāo)志
Returns:
retArray - 分類結(jié)果
"""
retArray = np.ones((np.shape(dataMatrix)[0],1)) #初始化retArray為1
if threshIneq == 'lt':
retArray[dataMatrix[:,dimen] <= threshVal] = -1.0 #如果小于閾值,則賦值為-1
else:
retArray[dataMatrix[:,dimen] > threshVal] = -1.0 #如果大于閾值,則賦值為-1
return retArray
第二個函數(shù)找到具有最低錯誤率的單層決策樹
def buildStump(dataArr,classLabels,D):
"""
找到數(shù)據(jù)集上最佳的單層決策樹
Parameters:
dataArr - 數(shù)據(jù)矩陣
classLabels - 數(shù)據(jù)標(biāo)簽
D - 樣本權(quán)重
Returns:
bestStump - 最佳單層決策樹信息
minError - 最小誤差
bestClasEst - 最佳的分類結(jié)果
"""
dataMatrix = np.mat(dataArr); labelMat = np.mat(classLabels).T
m,n = np.shape(dataMatrix)
numSteps = 10.0; bestStump = {}; bestClasEst = np.mat(np.zeros((m,1)))
minError = float('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']:#大于和小于的情況哨啃，均遍歷。lt:less than写妥，gt:greater than
threshVal = (rangeMin + float(j) * stepSize) #計算閾值
predictedVals = stumpClassify(dataMatrix, i, threshVal, inequal)#計算分類結(jié)果
errArr = np.mat(np.ones((m,1))) #初始化誤差矩陣為全一
errArr[predictedVals == labelMat] = 0 #分類正確的,賦值為0
weightedError = D.T * errArr #計算誤差
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
測試
if __name__ == '__main__':
dataArr,classLabels = loadSimpData()
D = np.mat(np.ones((5, 1)) / 5)
bestStump,minError,bestClasEst = buildStump(dataArr,classLabels,D)
print('bestStump:\n', bestStump)
print('minError:\n', minError)
print('bestClasEst:\n', bestClasEst)
輸出
split: dim 0, thresh 0.90, thresh ineqal: lt, the weighted error is 0.400
split: dim 0, thresh 0.90, thresh ineqal: gt, the weighted error is 0.600
split: dim 0, thresh 1.00, thresh ineqal: lt, the weighted error is 0.400
split: dim 0, thresh 1.00, thresh ineqal: gt, the weighted error is 0.600
split: dim 0, thresh 1.10, thresh ineqal: lt, the weighted error is 0.400
split: dim 0, thresh 1.10, thresh ineqal: gt, the weighted error is 0.600
split: dim 0, thresh 1.20, thresh ineqal: lt, the weighted error is 0.400
split: dim 0, thresh 1.20, thresh ineqal: gt, the weighted error is 0.600
split: dim 0, thresh 1.30, thresh ineqal: lt, the weighted error is 0.200
split: dim 0, thresh 1.30, thresh ineqal: gt, the weighted error is 0.800
split: dim 0, thresh 1.40, thresh ineqal: lt, the weighted error is 0.200
....
.....
.....
bestStump:
{'dim': 0, 'thresh': 1.3, 'ineq': 'lt'}
minError:
[[ 0.2]]
bestClasEst:
[[-1.]
[ 1.]
[-1.]
[-1.]
[ 1.]]
完整AdaBoost算法的實現(xiàn)
def adaBoostTrainDS(dataArr, classLabels, numIt = 40):
weakClassArr = []
m = np.shape(dataArr)[0]
D = np.mat(np.ones((m, 1)) / m) #初始化權(quán)重
aggClassEst = np.mat(np.zeros((m,1)))
for i in range(numIt):
bestStump, error, classEst = buildStump(dataArr, classLabels, D) #構(gòu)建單層決策樹
print("D:",D.T)
alpha = float(0.5 * np.log((1.0 - error) / max(error, 1e-16))) #計算弱學(xué)習(xí)算法權(quán)重alpha,使error不等于0,因為分母不能為0
bestStump['alpha'] = alpha #存儲弱學(xué)習(xí)算法權(quán)重
weakClassArr.append(bestStump) #存儲單層決策樹
print("classEst: ", classEst.T)
expon = np.multiply(-1 * alpha * np.mat(classLabels).T, classEst) #計算e的指數(shù)項
D = np.multiply(D, np.exp(expon))
D = D / D.sum() #根據(jù)樣本權(quán)重公式拳球，更新樣本權(quán)重
#計算AdaBoost誤差，當(dāng)誤差為0的時候珍特，退出循環(huán)
aggClassEst += alpha * classEst
print("aggClassEst: ", aggClassEst.T)
aggErrors = np.multiply(np.sign(aggClassEst) != np.mat(classLabels).T, np.ones((m,1))) #計算誤差
errorRate = aggErrors.sum() / m
print("total error: ", errorRate)
if errorRate == 0.0: break #誤差為0醇坝，退出循環(huán)
return weakClassArr, aggClassEst
AdaBoost算法的輸入?yún)?shù)包括數(shù)據(jù)集，類別標(biāo)簽以及迭代次數(shù)numIt次坡，其中numIt是在整個AdaBoost算法中唯一需要用戶指定的參數(shù)
列向量D包含每個數(shù)據(jù)點的權(quán)重呼猪，一開始這些權(quán)重都賦予相等的值。在后續(xù)的迭代中砸琅，AdaBoost算法會在增加錯分?jǐn)?shù)據(jù)的權(quán)重的同時宋距，降低正確分類數(shù)據(jù)的權(quán)重。D是一個概率分布向量症脂，因此其所有的元素之和為1.0谚赎。程序中的列向量aggClassEst記錄每個數(shù)據(jù)點的類別估計累計值
該算法的核心在于for循環(huán)，該循環(huán)運行numIt次或者直到訓(xùn)練錯誤率為0為止诱篷。該循環(huán)首先利用buildStump()建立單層決策樹壶唤，該函數(shù)的輸入為權(quán)重向量D，返回的是利用D而得到的具有最小錯誤率的單層決策樹棕所，同時返回最小的錯誤率以及估計的類別向量闸盔。
alpha值告訴總分類器本次單層決策樹輸出結(jié)果的權(quán)重。然后計算下一次迭代中的新權(quán)重向量D,
測試
if __name__ == '__main__':
dataArr,classLabels = loadSimpData()
weakClassArr, aggClassEst = adaBoostTrainDS(dataArr, classLabels)
print(weakClassArr)
print(aggClassEst)
輸出
split: dim 0, thresh 0.90, thresh ineqal: lt, the weighted error is 0.400
split: dim 0, thresh 0.90, thresh ineqal: gt, the weighted error is 0.600
split: dim 0, thresh 1.00, thresh ineqal: lt, the weighted error is 0.400
split: dim 0, thresh 1.00, thresh ineqal: gt, the weighted error is 0.600
split: dim 0, thresh 1.10, thresh ineqal: lt, the weighted error is 0.400
split: dim 0, thresh 1.10, thresh ineqal: gt, the weighted error is 0.600
split: dim 0, thresh 1.20, thresh ineqal: lt, the weighted error is 0.400
split: dim 0, thresh 1.20, thresh ineqal: gt, the weighted error is 0.600
.............
...............
............
split: dim 1, thresh 1.99, thresh ineqal: gt, the weighted error is 0.429
split: dim 1, thresh 2.10, thresh ineqal: lt, the weighted error is 0.857
split: dim 1, thresh 2.10, thresh ineqal: gt, the weighted error is 0.143
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
[{'dim': 0, 'thresh': 1.3, 'ineq': 'lt', 'alpha': 0.6931471805599453}, {'dim': 1, 'thresh': 1.0, 'ineq': 'lt', 'alpha': 0.9729550745276565}, {'dim': 0, 'thresh': 0.90000000000000002, 'ineq': 'lt', 'alpha': 0.8958797346140273}]
[[ 1.17568763]
[ 2.56198199]
[-0.77022252]
[-0.77022252]
[ 0.61607184]]
通過中間運行的結(jié)果琳省，可以發(fā)現(xiàn)在第一輪迭代中迎吵，D中的所有值都相等。于是针贬，只有第一個數(shù)據(jù)點被錯分击费，因此在第二次迭代中，D向量給第一個數(shù)據(jù)點0.5的權(quán)重桦他。這就可以通過變量aggClassEst的符號來了解總的類別蔫巩，第二次迭代之后，發(fā)現(xiàn)第一個數(shù)據(jù)點已經(jīng)正確分類快压，但此時最后一個數(shù)據(jù)點錯分了圆仔。D向量中的最后一個元素編程0.5，而D向量中的其他值都變的非常小嗓节。最后第三次迭代后aggClassEst所有值的符號和真是類別標(biāo)簽都完全吻合荧缘，那么訓(xùn)練誤差率為0
測試算法:基于AdaBoost的分類
def adaClassify(datToClass,classifierArr):
"""
AdaBoost分類函數(shù)
Parameters:
datToClass - 待分類樣例
classifierArr - 訓(xùn)練好的分類器
Returns:
分類結(jié)果
"""
dataMatrix = np.mat(datToClass)
m = np.shape(dataMatrix)[0]
aggClassEst = np.mat(np.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 np.sign(aggClassEst)
測試
if __name__ == '__main__':
dataArr,classLabels = loadSimpData()
weakClassArr, aggClassEst = adaBoostTrainDS(dataArr, classLabels)
print(adaClassify([[0,0],[5,5]], weakClassArr))
輸出
......
.....
.....split: dim 1, thresh 2.10, thresh ineqal: lt, the weighted error is 0.857
split: dim 1, thresh 2.10, thresh ineqal: gt, the weighted error is 0.143
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
[[-0.69314718]
[ 0.69314718]]
[[-1.66610226]
[ 1.66610226]]
[[-2.56198199]
[ 2.56198199]]
[[-1.]
[ 1.]]
(5,5)屬于正類拦宣，(0,0)屬于負類
在一個難數(shù)據(jù)集上應(yīng)用AdaBoost
利用第四章給出的馬疝病數(shù)據(jù)集上應(yīng)用AdaBoost分類器截粗，主要是利用多個單層決策樹和AdaBoost能不能預(yù)測得更準(zhǔn)
if __name__ == '__main__':
dataArr, LabelArr = loadDataSet(r'horseColicTraining2.txt')
weakClassArr, aggClassEst = adaBoostTrainDS(dataArr, LabelArr)
testArr, testLabelArr = loadDataSet(r'horseColicTest2.txt')
#print(weakClassArr)
predictions = adaClassify(dataArr, weakClassArr)
errArr = np.mat(np.ones((len(dataArr), 1)))
print('訓(xùn)練集的錯誤率:%.3f%%' % float(errArr[predictions != np.mat(LabelArr).T].sum() / len(dataArr) * 100))
predictions = adaClassify(testArr, weakClassArr)
errArr = np.mat(np.ones((len(testArr), 1)))
print('測試集的錯誤率:%.3f%%' % float(errArr[predictions != np.mat(testLabelArr).T].sum() / len(testArr) * 100))
輸出
訓(xùn)練集的錯誤率:19.732%
測試集的錯誤率:19.403%
對比第四章的錯誤率信姓，會發(fā)現(xiàn)該方法下錯誤率大大下降
使用AdaBoostClassifier運行代碼
import numpy as np
from sklearn.ensemble import AdaBoostClassifier
from sklearn.tree import DecisionTreeClassifier
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')
for i in range(numFeat - 1):
lineArr.append(float(curLine[i]))
dataMat.append(lineArr)
labelMat.append(float(curLine[-1]))
return dataMat, labelMat
if __name__ == '__main__':
dataArr, classLabels = loadDataSet(r'horseColicTraining2.txt')
testArr, testLabelArr = loadDataSet(r'horseColicTest2.txt')
bdt = AdaBoostClassifier(DecisionTreeClassifier(max_depth = 2), algorithm = "SAMME", n_estimators = 10)
bdt.fit(dataArr, classLabels)
predictions = bdt.predict(dataArr)
errArr = np.mat(np.ones((len(dataArr), 1)))
print('訓(xùn)練集的錯誤率:%.3f%%' % float(errArr[predictions != classLabels].sum() / len(dataArr) * 100))
predictions = bdt.predict(testArr)
errArr = np.mat(np.ones((len(testArr), 1)))
print('測試集的錯誤率:%.3f%%' % float(errArr[predictions != testLabelArr].sum() / len(testArr) * 100))
輸出
訓(xùn)練集的錯誤率:16.054%
測試集的錯誤率:17.910%
源碼
Python3《機器學(xué)習(xí)實戰(zhàn)》學(xué)習(xí)筆記（十）：提升分類器性能利器-AdaBoost
