元算法是对其他算法进行组合的一种方式。
使用集成方法时，会有多种形式：可以是不同算法的集成；也可以是同一算法在不同设置下的集成；还可以是数据集不同部分分配给不同分类器之后的集成。
bagging，自举汇聚法（bootstrap aggregating），其算法过程如下：
从原始样本集中抽取训练集。每轮从原始样本集中使用Bootstraping的方法抽取n个训练样本（在训练集中，有些样本可能被多次抽取到，而有些样本可能一次都没有被抽中）。共进行k轮抽取，得到k个训练集。（k个训练集之间是相互独立的）
每次使用一个训练集得到一个模型，k个训练集共得到k个模型。（注：这里并没有具体的分类算法或回归方法，我们可以根据具体问题采用不同的分类或回归方法，如决策树、感知器等）
对分类问题：将上步得到的k个模型采用投票的方式得到分类结果；对回归问题，计算上述模型的均值作为最后的结果。（所有模型的重要性相同）。
boosting（提升）是通过集中关注被已有分类器错分的那些数据来获得新的分类器。bagging中的分类器权重是相等的，而boosting中的分类器权重并不相等，每个权重代表的是其对应分类器在上一轮迭代中的成功度。
AdaBoost
AdaBoost是adaptive boosting（自适应boosting）的缩写。其运行过程如下：
- 为每个训练数据赋予相等的初始权重，这些权重构成向量D
- 训练出一个弱分类器并计算该分类器的错误率
- 重新调整每个样本的权重，上一次分对的样本的权重降低，分错的样本的权重提高，然后在同一数据集上再次训练弱分类器
为了从所有弱分类器中得到最终的分类结果，AdaBoost为每个分类器分配一个权重值alpha，这些alpha值是基于弱分类器的错误率进行计算的。其中，错误率的定义为：
而alpha的计算公式如下：
计算出alpha值之后，对权重向量D进行更新。
如果某个样本被正确分类，那么该样本的权重更改为：
如果某个样本被错分，那么该样本的权重更改为：
AdaBoost算法会不断重复训练和调整权重的过程，直到训练错误率为0或者弱分类器数目达到指定值。
上图为Adaboost算法示意图。最左边为数据集，不同宽度表示权重不同。各个弱分类器预测出的结果通过三角形中的alpha值进行加权，最后汇总求和，通过sign函数输出结果。
基于单层决策树构建分类器
单层决策树(decision stump)，仅基于单个特征做决策，只有一次分裂过程，实际上就是个树桩。
# 创建简单数据集
def loadSimpData():
datMat = np.matrix([[ 1. , 2.1],
[ 1.5 , 1.5],
[ 1.3, 1. ],
[ 1. , 1. ],
[ 2. , 1. ]])
classLabels = [1.0, 1.0, -1.0, -1.0, 1.0]
return datMat,classLabels
# 数据可视化
datMat, classLabels = loadSimpData()
xcord0 = []
ycord0 = []
xcord1 = []
ycord1 = []
markers =[]
colors =[]
for i in range(len(classLabels)):
if classLabels[i]==1.0:
xcord1.append(datMat[i,0]), ycord1.append(datMat[i,1])
else:
xcord0.append(datMat[i,0]), ycord0.append(datMat[i,1])
fig = plt.figure()
ax = fig.add_subplot(111)
ax.scatter(xcord0,ycord0, marker='s', s=90)
ax.scatter(xcord1,ycord1, marker='o', s=50, c='red')
plt.title('decision stump test data')
plt.show()
观察上图，可以发现如果要找一条与坐标轴平行的直线来分开两类数据是不可能的。这就是单层决策树难以处理的一个问题。
def stumpClassify(dataMatrix,dimen,threshVal,threshIneq):
'''
dataMatrix：数据集
dimen：用于决策的特征
threshVal：阈值
threshIneq：比较符号（小于等于或大于）
'''
retArray = np.ones((np.shape(dataMatrix)[0],1))
if threshIneq == 'le':
retArray[dataMatrix[:,dimen] <= threshVal] = -1.0
else:
retArray[dataMatrix[:,dimen] > threshVal] = -1.0
return retArray
def buildStump(dataArr,classLabels,D):
'''
dataArr：特征矩阵
classLabels：标签矩阵
D：样本权重
返回：最佳树桩信息，最小误差，最佳分类结果
'''
dataMatrix = np.mat(dataArr)
labelMat = np.mat(classLabels).T
m,n = dataMatrix.shape
numSteps = 10.0
bestStump = {} # 用于存储最佳树桩信息的字典
bestClasEst = np.mat(np.zeros((m,1))) # 初始化分类结果为1
minError = np.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 ['le', 'gt']: # 第三层：循环切换不等式
threshVal = (rangeMin + float(j) * stepSize)
predictedVals = stumpClassify(dataMatrix,i,threshVal,inequal)
errArr = np.mat(np.ones((m,1)))
errArr[predictedVals == labelMat] = 0
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
试一下，观察结果。
D = np.mat(np.ones((5,1))/5)
buildStump(datMat, classLabels, D)
output:
({'dim': 0, 'thresh': 1.3, 'ineq': 'le'}, matrix([[0.2]]), array([[-1.],
[ 1.],
[-1.],
[-1.],
[ 1.]]))
上面生成的单层决策树就是一个弱分类器。接下来将使用多个弱分类器来构建AdaBoost。
完整AdaBoost算法
伪代码：
对每次迭代：
利用buildStump()函数找到最佳的单层决策树
将最佳单层决策树加入到单层决策树数组
计算alpha
计算新的权重向量D
更新累计类别估计值
如果错误率等于0，则退出循环
python代码实现：
def adaBoostTrainDS(dataArr, classLabels, maxIter=40):
'''
dataArr：特征矩阵
classLabels：标签矩阵
maxIter=40：最大迭代次数，默认值为40
返回：弱分类器数组，类别估计累计值
'''
weakClassArr = []
m = dataArr.shape[0]
D = np.mat(np.ones((m,1))/m) # 初始化权重值
aggClassEst = np.mat(np.zeros((m,1)))
for i in range(maxIter):
bestStump,error,classEst = buildStump(dataArr,classLabels,D) # 构建单层决策树
alpha = float(0.5*np.log((1.0-error)/max(error,1e-16))) # 计算alpha
bestStump['alpha'] = alpha
weakClassArr.append(bestStump) # 存储单层决策树
expon = np.multiply(-1*alpha*np.mat(classLabels).T,classEst) # 计算e的指数项
D = np.multiply(D,np.exp(expon))
D = D/D.sum()
# 计算全部分类器的累计误差，如果为0则终止循环
aggClassEst += alpha*classEst
aggErrors = np.multiply(np.sign(aggClassEst) != np.mat(classLabels).T,np.ones((m,1)))
errorRate = aggErrors.sum()/m
if errorRate == 0.0: break
return weakClassArr,aggClassEst
执行函数，观察结果。
DSArr, aggClass = adaBoostTrainDS(datMat, classLabels)
output:
D: [[0.2 0.2 0.2 0.2 0.2]]
D: [[0.5 0.125 0.125 0.125 0.125]]
D: [[0.28571429 0.07142857 0.07142857 0.07142857 0.5 ]]
可以观察到在迭代过程中，被错分的样本权重会增加，正确分类的样本权重会降低。
观察分类器数组：
DSArr
ooutput:
[{'dim': 0, 'thresh': 1.3, 'ineq': 'le', 'alpha': 0.6931471805599453},
{'dim': 1, 'thresh': 1.0, 'ineq': 'le', 'alpha': 0.9729550745276565},
{'dim': 0, 'thresh': 0.9, 'ineq': 'le', 'alpha': 0.8958797346140273}]
只有三个弱分类器，也就是说迭代三次就停止了。
接下来测试下算法。
基于AdaBoost的分类
# AdaBoost分类函数
def adaClassify(inX, classifierArr):
'''
inX：待分类数据
classifierArr：训练好的弱分类器数组
'''
dataMatrix = np.mat(inX)
m = dataMatrix.shape[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
return np.sign(aggClassEst)
观察实际运行效果。
print(adaClassify([0,0], DSArr))
print(adaClassify([2,2], DSArr))
output:
[[-1.]]
[[1.]]
示例：在病马数据集上应用AdaBoost
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 np.matrix(dataMat), np.matrix(labelMat)
def calErrRate(maxC = 40):
trainMat, trainLabelMat = loadDataSet('horseColicTraining2.txt')
weakClassArr,aggClassEst = adaBoostTrainDS(trainMat, trainLabelMat, maxC)
trainPred = adaClassify(trainMat, weakClassArr)
errArr = np.mat(np.ones((trainMat.shape[0], 1)))
trainErrRate = errArr[trainPred != trainLabelMat.T].sum() / trainMat.shape[0]
testMat, testLabelMat = loadDataSet('horseColicTest2.txt')
testPred = adaClassify(testMat, weakClassArr)
errArr = np.mat(np.ones((testMat.shape[0], 1)))
testErrRate = errArr[testPred != testLabelMat.T].sum() / testMat.shape[0]
return trainErrRate, testErrRate
loadDataSet()函数加载数据集，并以矩阵形式返回。calErrRate()计算训练错误率和测试错误率。
直接执行calErrRate()函数会得到如下结果。
(0.19732441471571907, 0.19402985074626866)
也就是说弱分类器在40个的情况下，训练错误率在0.20左右，测试错误率在0.19左右。
接下来看一下不同分类器数目的情况。
import pandas as pd
Cycles = [1, 10, 50, 100, 500, 1000, 10000]
trainErrRate = []
testErrRate = []
for maxC in Cycles:
a, b = calErrRate(maxC)
trainErrRate.append(round(a, 2))
testErrRate.append(round(b, 2))
df = pd.DataFrame({'分类器数目':Cycles, '训练错误率':trainErrRate, '测试错误率':testErrRate})
df
| 分类器数目 | 训练错误率 | 测试错误率 |
|---|---|---|
| 1 | 0.28 | 0.27 |
| 10 | 0.23 | 0.24 |
| 50 | 0.19 | 0.21 |
| 100 | 0.19 | 0.22 |
| 500 | 0.16 | 0.25 |
| 1000 | 0.14 | 0.31 |
| 10000 | 0.11 | 0.33 |
观察发现，测试错误率在达到一个最小值后又开始上升。这种现象称之为过拟合。
小结
集成方法通过组合多个分类器的分类结果，获得了比简单的单分类器更好的分类结果。
多个分类器组合可能会进一步凸显出单分类器的不足，比如过拟合问题。如果分类器之间差别显著，那么可能会缓解这一问题。分类器之间的差别可以是算法本身或者应用于算法上的数据不同。
bagging是通过随机抽样的替换方式，得到了与原始数据集规模一样的数据集。boosting在数据集上顺序应用了多个不同的分类器。
本文以单层决策树作为弱学习器构建AdaBoost分类器。实际上，AdaBoost可以应用于任意分类器，只要该分类器能够处理加权数据即可。
