大数据/分布式系统

机器学习笔记（Chapter 07 - AdaBoost元算法）

元算法是对其他算法进行组合的一种方式。在做决定时，大家通常考虑吸取多个专家（分类算法）而不是一个专家的意见。当我们试图对样例数目不均衡的数据进行分类时，会遇到非均衡分类问题。

基于数据集多重抽样的分类器

  • 前面已经介绍了五种不同的分类算法，各有优缺点。我们可以将不同的分类器组合起来，这种组合结果被称为集成方法或者元算法。使用集成方法时会有许多形式，可以是不同算法的集合，也可以是同一算法在不同设置下的集成，还可以是数据集不同部分分配给不同分类器之后的集成。
  • 自举汇聚法 （bootstrap aggregating，bagging）是从原始数据集选择S次后得到S个新数据集的技术。新数据集和原数据集大小相等，每个数据集都是通过在原始数据集中随机选择一个样本来进行替换得到的，因此有可能出现多次选择同一样本，所以这一行只允许新数据集中有重复的值，而原始数据集的某些值在新集合中则不再出现。当这S个数据集建好，将某个学习算法应用到每个数据集就得到了S个分类器，之后用这S个分类器分类，投票选择最终类别。其它先进的bagging方法有随机森林等，讨论材料见http://www.stat.berkeley.edu/~breiman/RandomForests/cc_home.htm。
  • boosting是一种与bagging类似的技术，无论在bo哦sting还是bagging中，分类器的类型都是一致的。但在前者中，不同的分类器是通过串行训练获得的，每个新分类器都根据已训练出的分类器的性能来训练。 boosting是通过集中关注被已有分类器错分的数据来获得新的分类器 。bagging中各个分类器的权重相等，而boosting中的分类器权重不等，代表其对应分类器在上一轮迭代中的成功度。
  • AdaBoost流程
    • 准备数据：依赖于使用的弱分类器类型，本章使用单层决策树，也可以使用任意分类器充当弱分类器。简单分类器作为弱分类器效果更好。
    • 分析数据：任意方法。
    • 训练算法：占据大部分时间，分类器将多次在同一数据集上训练弱分类器。
    • 测试算法：计算分类错误率。
    • 使用算法：二类分类器。

基于错误提升分类器性能

  • 可以通过弱分类器和多个实例来构造一个强分类器，这里的“弱”意味着分类器的性能比随即猜测要略好，但不会好太多。AdaBoost是adaptive boosting（自适应boosting），过程如下。
  • 训练数据集中的每个样本，并赋予其一个权重，这些权重构成了向量D。一开始这些权重都初始化为相等值。首先在训练数据上训练出一个弱分类器并计算该分类器的错误率，然后在同一数据集上再一次训练弱分类器。在分类器的第二次训练中，会重新调整每个样本的权重，其中上一次训练中分对的样本所占权重会降低，分错的样本所占样本权重升高。
  • AdaBoost为每个弱分类器设置一个权重α，这些α值根据每个弱分类器的错误率计算，错误率ε=未正确分类的样本数/所有的样本数目。α计算公式为α=0.5*ln((1-ε)/ε)。可见错误率下降，α上升。计算出α后，对权重向量D更新，如果某个样本被正确地分类，那么D' = D*e^(-α)/sum(D)，如果某个样本被错分，那么D' = D*e^α/sum(D)。
  • 更新D后，AdaBoost进入下一轮迭代。其会不断重复训练和调整权重的过程，直到某次训练错误率为0，或者弱分类器达到用户指定的数量。

基于单层决策树构建弱分类器

  • 单层决策树（决策树桩）是一种简单的决策树，仅基于单个特征来做决策，只有一次分裂过程，因此是一个树桩。

  • 简单数据集加载 - adaboost.py

1
2
3
4
5
6
7
8
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

  • 建立最佳单层决策树

    • 将最小错误率minError设为+∞
    • 对数据集中的每一个特征（一层循环）：
    •     对每个步长（二层循环）：
    •         对每个不等号（三层循环）：
    •               建立一棵单层决策树并利用加权数据集对他测试，如果错误率低于minError，就将当前的单层决策树设为最佳单层决策树
    • 返回最佳单层决策树

  • 最佳单层决策树生成函数 - adaboost.py。下面包含两个函数，stumpClassify是通过阈值threshVal来确定类别，在阈值一边的数据分到类别-1，另一边分到类别+1。第二个函数buildStump遍历stumpClassify所有可能输入值，第一层循环遍历数据集所有特征，第二层遍历所有阈值，第三层遍历不等号。并找到数据集上最佳的单层决策树。之后返回一个bestStump字典，存乎了最优单层决策树的信息。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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 inequal: %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

完整AdaBoost算法

  • 伪代码：对每次迭代

    • 利用buildStump找到最佳的单层决策树
    • 将最佳单层决策树加入单层决策树数组
    • 计算α
    • 计算新的权重向量D
    • 更新累计类别估计值
    • 如果错误率为0.0则退出循环。

  • 下面是训练过程代码，输入参数为数据集、类别标签和迭代次数。D是概率分布向量，因此所有元素之和为1，因此初始全部为1/m。同时程序建立列向量aggClassEst记录每个数据点的类别估计累计值。程序中max(error, 1e-16)防止出现除零溢出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def adaBoostTrainDS(dataArr, classLabels, numIt = 40):
	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'] = 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
		print "aggClassEst: ", aggClassEst.T
		aggErrors = multiply(sign(aggClassEst) != mat(classLabels).T, ones((m,1)))
		errorRate = aggErrors.sum() / m
		print "total error: ", errorRate, "\n"
		if errorRate == 0.0 : break
	return weakClassArr, aggClassEst
  • 分类：输入参数是待分类数据和分类器。遍历强分类器中的每个弱分类器，并通过stumpClassify得到每个分类器对某个类别的估计值。
1
2
3
4
5
6
7
8
9
10
def adaClassify(datToClass, classifierArr):
	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)
  • 在疝气病马数据集上应用AdaBoost算法，通过loadDataSet读入数据，并进行分类。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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

>>> datArr, labelArr = adaboost.loadDataSet('horseColicTraining2.txt')
>>> classifierArray = adaboost.adaBoostTrainDS(datArr, labelArr, 10)
>>> testArr, testLabelArr = adaboost.loadDataSet('horseColicTest2.txt')
>>> prediction10 = adaboost.adaClassify(testArr, classifierArray)
>>> errArr = mat(ones((67,1)))
>>> errArr[prediction10!=mat(testLabelArr).T].sum()
  • 错误率分析：当分类器数目从1到10000变化时，总测试错误率先达到一个 最小值，之后又上升。该现象称为过拟合。有文献表明，对于表现好的数据集（horseColicTest有30%数据缺失），AdaBoost的测试错误率会达到一个稳定之，并不会随着分类器增加而上升。

非均衡类问题和其他分类性能度量指标

之前的分类都假设所有分类代价一样，但实际上将马归类为死或者活的代价不同，假如分类器只有80%正确率，将一匹本能存活的马判定为安乐死，损失会更大。

  • 混淆矩阵：列方向为预测结果，行方向为实际结果，如果除了对角线，其他元素都是0，那么将是一个完美的分类器。
  • 对于二类问题：如果将正例判为正例则产生真阳例（TP），将反例正确判为反例则产生真阴例（TN），将正例错判为反例，则产生假阴例（FN），将反例错判为正例称为假阳例（FP）。正确率=TP/(TP+FP)，召回率=TP/(TP+FN)。在高召回率的分类器重，真正判错的正例数目并不多。我们可以很容易构造一个高准确率或者高召回率的分类器，但很难保证两者同时成立。
  • ROC曲线：横轴为假阳率=FP/(FP+TN)，纵轴是真阳率=TP/(TP+FN)。ROC曲线给出的是当阈值变化时假阳率和真阳率变化的情况。左下角点对应所有样例判为反例，右上角对应所有样例判为正例。理想情况下，最佳分类器应尽可能处于左上角。另一个指标是ROC曲线下的面积AUC，代表了分类器的平均性能值。完美分类器的AUC=1.0，随即猜测的AUC=0.5。
  • 创建ROC曲线。首先将分类样例按照预测强度排序，强度高的分为正例，低的判为反例。下面为创建ROC曲线的代码。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def plotROC(predStrengths, classLabels):
	import matplotlib.pyplot as plt
	cur = (1.0, 1.0)
	ySum = 0.0
	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

  • 生成图像如下

  • 代价敏感的学习：选择具有最小期望代价而不是最大概率的类别作为最后的结果。

  • 数据抽样方法：欠抽样和过抽样。欠抽样指删除部分样例，过抽样指复制部分样例。对于罕见类别，要尽量保留更多信息，通常选择离决策边界较远的样例删除。另一种策略是使用反例类别的欠抽样和正例类别的过抽样结合。

AdaBoost元算法总结

元算法过多个分类器组合，可以减轻单分类器的不足。AdaBoost函数可以应用于任何分类器，只要该分类器可以处理加权数据。非均衡分类问题指在分类器训练时正例数目和反例数目不等或者相差很大，或者错分正例和反例代价不同时产生。

参考文献： 《机器学习实战 - 美Peter Harrington》

原创作品，允许转载，转载时无需告知，但请务必以超链接形式标明文章原始出处(https://forec.github.io/2016/02/14/machinelearning7/) 、作者信息（Forec）和本声明。

分享到