|
不同的分類算法各有優(yōu)缺點，可以將不同的分類器組合起來
這種組合被稱為集成方法（ensemble method）或者元算法（meta-algorithm）
使用集成方法有多種形式
?○?可以是不同算法的集成
?○?可以是同一算法在不同設置下的集成
?○?可以是數(shù)據(jù)集不同部分分配給不同分類器之后的集成
bagging （Bootstrap aggregating，引導聚集算法，又稱裝袋算法）
- 隨機采樣：在一個有 m 個樣本的數(shù)據(jù)集中，每次采集一個樣本，然后將該樣本放回，共采集 m 個樣本形成新的數(shù)據(jù)集，這樣原始數(shù)據(jù)集中有些樣本會被重復采集，有些樣本則不會被采集，形成的新的數(shù)據(jù)集和原數(shù)據(jù)集大小相等，理論上 m 足夠大的情況下平均會有約 36% 的樣本不會被采集
- 重復 S 次得到 S 個新數(shù)據(jù)集
- 將某個學習算法分別作用于每個數(shù)據(jù)集就得到了 S 個分類器
- 對新數(shù)據(jù)進行分類時，應用這 S 個分類器進行分類，選擇分類器投票結果中最多的類別作為最后的分類結果
隨機森林（random forest, RF）
和普通的 bagging 差不多，在其基礎上做了一點改進
?○?使用 S 個 CART 決策樹作為弱學習器
?○?假設樣本特征數(shù)為 a，則每次生成 CART 樹都是隨機選擇 a 中的 k 個特征
boosting（提升算法）
- 與 bagging 類似，不同的是 bagging 的各個分類器是獨立訓練出來的，而 boosting 的每個分類器是根據(jù)已訓練出的分類器的性能來進行訓練
- boosting 是通過集中關注被已有分類器錯分的那些數(shù)據(jù)來獲得新的分類器
- boosting 分類的結果是基于所有分類器的加權求和，而 bagging 中的分類器權重是相等的
- boosting 公式
??
??\(\large f(x)= \sum_{i=1}^{n}(a_{i}f_{i}(x))\)
??
- boosting 是串行過程，不好并行化，這是它的一個缺點
- boosting 有多種算法比如 adaboost、GBDT、xgboost
adaboost（adaptive boosting - 自適應 boosting）
adaboost 可以應用于任意分類器，只要將該分類器改造成能夠處理加權數(shù)據(jù)即可
其運行過程如下
- 對每個樣本賦予一個權重，這些權重構成向量 D，一開始 D 初始化成相等值： \(\Large \frac{1}{樣本數(shù)}\)
- 先在訓練數(shù)據(jù)上訓練出一個弱分類器 \(\large f(x)\) 并按照樣本權值 D 計算該分類器的錯誤率
??\(\large e = \sum D_{i}\)????其中 \(\large i\) 為分類錯誤的數(shù)據(jù)
- 每個分類器也有一個權重值，該值基于每個弱分類器的錯誤率進行計算的，公式為
??\(\large \alpha = \frac{1}{2} ln(\frac{1-e}{e})\)
- 這里要有 \(\large e<0.5\) 以保證 \(\large \alpha>0\)，分類器也不應該出現(xiàn)錯誤大于一半的情況，否則應忽略
- 然后在同一數(shù)據(jù)集上再次訓練弱分類器，這次會調(diào)整每個樣本的權重，上一次分對的樣本的權重將會降低，分錯的樣本的權重將會提高，同時基于上個分類器權值 \(\small \alpha\) 計算
??正確分類則
????\(\Large D_{i-new} = \frac{D_{i-old}\ e^{(-\alpha)}}{\sum_{j=1}^{n}D_{j-old}\ e^{(-\alpha)}}\)
?
??錯誤分類則
????\(\Large D_{i-new} =\frac{D_{i-old}\ e^{(\alpha)}}{\sum_{j=1}^{n}D_{j-old}\ e^{(\alpha)}}\)
??
??將分類結果標記為 1 和 -1，這樣統(tǒng)一寫為
?
????\(\Large D_{i-new} = \frac{D_{i-old}\ e^{(-\alpha y_{i}f(x_{i}))}}{\sum_{j=1}^{n}D_{j-old}\ e^{(-\alpha y_{j}f(x_{j})))}}\)
- 累加分類結果為
??\(\Large y = sign(\sum_{i=1}^{n}(\alpha_{i}f_{i}(x)))\)
- 不斷迭代直到總錯誤率為 0 或者弱分類器的數(shù)目達到用戶的指定值為止
??\(\Large 總錯誤率 = \frac{累加分類結果錯誤數(shù)}{總樣本數(shù)}\)
adaboost 代碼
# coding=utf-8
import numpy as np
def stumpClassify(dataMatrix, dimen, threshVal, threshIneq):
"""
單層決策樹 (decision stump，也稱決策樹樁)
它僅基于單個特征來做決策，由于只有一次分裂過程，實際上就是一個樹樁
單層決策樹的分類能力比較弱，是一種弱分類器，通過 adaboost 使用多個單層決策樹可以構建強分類器
dataMatrix - 要分類的數(shù)據(jù)集 (n, m) 矩陣
dimen - 用于分類的特征
threshVal - 判斷分類的閥值
threshIneq - 操作符 ('lt', 'gt') 決定是特征值大于閥值返回分類 -1，還是小于閥值返回分類 -1
"""
# 初始化分類矩陣，默認為分類 1
retArray = np.ones((np.shape(dataMatrix)[0], 1))
if threshIneq == 'lt':
# 當 dataMatrix[x, dimen] <= threshVal 時，將 retArray[x] 改為 -1
retArray[dataMatrix[:, dimen] <= threshVal] = -1.0
else:
retArray[dataMatrix[:, dimen] > threshVal] = -1.0
return retArray
def buildStump(dataArr, classLabels, D):
"""
按照樣本權值，尋找最佳的單層決策樹，即尋找最佳的分類特征和分類閥值，以及操作符
dataArr - 樣本數(shù)據(jù)
classLabels - 標簽數(shù)據(jù)
D - 樣本權值
"""
# 初始化矩陣并獲取矩陣大小
dataMatrix = np.mat(dataArr)
labelMat = np.mat(classLabels).T
n, m = np.shape(dataMatrix)
# 閥值數(shù)
# 將特征值從最大值到最小值之間，取 10 個間隔分出 11 個閥值，在這些閥值中選取最佳值
numSteps = 10.0
# 用于存儲最佳決策樹的配置，包括（特征，閥值，操作符）
bestStump = {}
# 用于保存最佳決策樹的分類結果
bestClasEst = np.mat(np.zeros((n, 1)))
# 用于保存最佳決策樹的錯誤率
minError = np.inf
# 遍歷每一個特征
for i in range(m):
# 取該特征的最大最小值以及步長
rangeMin = dataMatrix[:, i].min()
rangeMax = dataMatrix[:, i].max()
stepSize = (rangeMax - rangeMin)/numSteps
# 遍歷所有閥值
for j in range(0, int(numSteps) 1):
# 遍歷操作符
for inequal in ['lt', 'gt']:
# 取閥值
threshVal = (rangeMin float(j) * stepSize)
# 以 (特征，閥值，操作符) 作為決策樹，對所有數(shù)據(jù)分類
predictedVals = stumpClassify(dataMatrix, i, threshVal, inequal)
# 評估分類結果，正確分類為 1，錯誤分類為 0
errArr = np.mat(np.ones((n, 1)))
errArr[predictedVals == labelMat] = 0
# 計算錯誤率, D 的初始值是 1/(樣本總數(shù))
weightedError = D.T*errArr
if weightedError < minError:
# 找到更好的決策樹，保存結果
minError = weightedError
bestClasEst = predictedVals.copy()
bestStump['dim'] = i
bestStump['thresh'] = threshVal
bestStump['ineq'] = inequal
# 返回最佳決策樹配置(特征，閥值，操作符), 最佳決策樹的錯誤率, 最佳決策樹的分類結果
return bestStump, minError, bestClasEst
def adaBoostTrainDS(dataArr, classLabels, numIt = 40):
"""
基于單層決策樹的 adaboost 訓練
dataArr - 樣本數(shù)據(jù)
classLabels - 樣本標簽
numIt - 最大迭代次數(shù)
"""
# 用于保存決策樹列表
# 每次迭代會產(chǎn)生一個決策樹, 直到達到最大迭代次數(shù), 或是最終錯誤率為 0
weakClassArr = []
# 樣本數(shù)
n = np.shape(dataArr)[0]
# 初始化樣本權值 D，每個數(shù)據(jù)的權重為 1/(樣本數(shù))
D = np.mat(np.ones((n, 1))/n)
# 保存累加分類結果
aggClassEst = np.mat(np.zeros((n, 1)))
for i in range(numIt):
# 按樣本和權值尋找最佳決策樹
# 返回決策樹配置(特征，閥值，操作符), 錯誤率, 分類結果
bestStump, error, classEst = buildStump(dataArr, classLabels, D)
# 計算決策樹權值 alpha = 0.5 * ln((1-err)/err)
# 1e-16 是防止 err 為 0 的情況, ln(1/1e-16) 的結果為 36.8
# 這里沒處理 err > 0.5 導致 alpha < 0 的情況, 照理說也不應該出現(xiàn)這種情況
alpha = float(0.5 * np.log((1.0 - error)/max(error, 1e-16)))
# 將決策樹權值加入到?jīng)Q策樹配置
bestStump['alpha'] = alpha
# 將決策樹配置加入決策樹列表
weakClassArr.append(bestStump)
# 計算新的樣本權值
# D(i_new) = (D(i_old) * exp(-alpha * yi * f(xi))) / SUM_j_1_n (D(j_old) * exp(-alpha * yj * f(xj)))
expon = np.multiply(-1 * alpha * np.mat(classLabels).T, classEst)
D = np.multiply(D, np.exp(expon))
D = D/D.sum()
# 該決策樹的分類結果, 按權值算入累加分類結果
aggClassEst = alpha*classEst
# 計算累加分類結果的錯誤率, 如果錯誤率為 0 則退出迭代
aggErrors = np.multiply(np.sign(aggClassEst) != np.mat(classLabels).T, np.ones((n, 1)))
errorRate = aggErrors.sum()/n
if errorRate == 0.0:
break
# 返回決策樹配置列表, 累加分類結果
return weakClassArr, aggClassEst
def adaClassify(datToClass, classifierArr):
"""
使用決策樹列表進行分類
weakClassArr - 要分類的數(shù)據(jù)
classifierArr - 決策樹配置列表
"""
dataMatrix = np.mat(datToClass)
n = np.shape(dataMatrix)[0]
aggClassEst = np.mat(np.zeros((n, 1)))
# 遍歷決策樹
for i in range(len(classifierArr)):
# 分類
classEst = stumpClassify(dataMatrix,
classifierArr[i]['dim'],
classifierArr[i]['thresh'],
classifierArr[i]['ineq'])
# 按權值累加分類結果
aggClassEst = classifierArr[i]['alpha']*classEst
# sign 函數(shù)：大于 0 返回 1，小于 0 返回 -1，等于 0 返回 0
return np.sign(aggClassEst)
????
????
來源：https://www./content-1-645001.html
|
