基于单层决策树的AdaBoost算法
基于单层决策树的AdaBoost算法
用户6021899
发布于 2019-09-02 18:00:08
发布于 2019-09-02 18:00:08
Boosting，也称为增强学习或提升法，是一种重要的集成学习技术，能够将预测精度仅比随机猜度略高的弱学习器增强为预测精度高的强学习器，这在直接构造强学习器非常困难的情况下，为学习算法的设计提供了一种有效的新思路和新方法。作为一种元算法框架，Boosting几乎可以应用于所有目前流行的机器学习算法以进一步加强原算法的预测精度，应用十分广泛，产生了极大的影响。而AdaBoost正是其中最成功的代表，被评为数据挖掘十大算法之一。
Adaboost（adaptive boosting）是一种迭代算法，其核心思想是针对同一个训练集训练不同的分类器(弱分类器)，然后把这些弱分类器集合起来，组成一个更强的最终分类器（强分类器）。可以用一句谚语来形容----“三个臭皮匠，顶个诸葛亮”。过程较民主，投票再加权。如下图所示：
其中，弱分类器的“弱”意味着分类器的性能比随机猜测要略好，但也不必好太多。
Adaboost算法的主要流程如下：
- 先赋予训练集中每个样本一个权重（一开始初始化为相等的值），这些权重构成权重向量D。
- 在训练数据集上训练出一个弱分类器并计算该分类器的错误率，然后再同一数据集上再训练弱分类器。
- 在弱分类器的第二次训练当中，会更新样本权重向量D，其中上次分对的样本的权重会降低，分错的样本的权重会提高。
- 为了从弱分类器中组合得到强分类器，需要为每个弱分类器分配一个权重值 α。这些 α 值是根据每个弱分类器的错误率 ε 进行计算。
附上绘图的代码：
from matplotlib import pyplot as plt
import numpy as np
from math import log
def cal_alpha(epsilon):
return 0.5* log((1- epsilon)/ epsilon)
cal_a = np.frompyfunc(cal_alpha, 1, 1)
E = np.arange(0.0001,1.0, 0.0001)
a = cal_a(E).astype(np.double)
plt.plot(E, a)
plt.xlabel(r"$\epsilon$")
plt.ylabel(r"$\alpha$")
plt.title(r"$\alpha$ 曲线")
plt.grid()
plt.show()- 在计算出了α之后，可以对权重向量D进行更新，以使得那些正确分类的样本的权重降低而错误样本的权重升高。 对于某个样本被正确分类，则该样本的权重更新为：
反之，如果某个样本被错分，则该样本的权重更新为：
- 在算出D后，AdaBoost又开始进入下一次迭代，直至错误率为0，或者达到最大迭代次数为止。
本篇使用的弱分类器为单层决策树（decision stump,也称决策树桩）。它仅根据样本的单个特征值进行分类，实在是够弱（当然，弱不是优点）。
如下图的简单数据集，要想从某个坐标轴上选择一个值（即根据一条平行于某坐标轴的直线）来将所有的圆点和方形点分开，显然是不可能的。但是通过多棵单层决策树投票加权，我们就可以构建出一个能对该数据集完全正确分类的强分类器。
加载数据集，创建单层决策树，投票加权组合成强分类器的完整代码如下：
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
def loadDataSet(fileName): #general function to parse tab -delimited floats
numFeat = len(open(fileName).readline().split('\t')) #get number of fields
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
def stumpClassify(dataMatrix,dimen,threshVal,threshIneq):
#基于单层决策树构建弱分类器
retArray = ones((shape(dataMatrix)[0],1))
if threshIneq == 'lt': # "less than"
retArray[dataMatrix[:,dimen] <= threshVal] = -1.0
else: # "gt" , "grater than"
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 #init error sum, to +infinity
for i in range(n):#loop over all dimensions
rangeMin = dataMatrix[:,i].min(); rangeMax = dataMatrix[:,i].max();
stepSize = (rangeMax-rangeMin)/numSteps
for j in range(-1,int(numSteps)+1):#loop over all range in current dimension
for inequal in ['lt', 'gt']: #go over less than and greater than
threshVal = (rangeMin + float(j) * stepSize)
predictedVals = stumpClassify(dataMatrix,i,threshVal,inequal)#call stump classify with i, j, lessThan
errArr = mat(ones((m,1)))
errArr[predictedVals == labelMat] = 0
weightedError = D.T*errArr #calc total error multiplied by D
#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 #取决于D
def adaBoostTrainDS(dataArr,classLabels,numIt=40):
weakClassArr = []
m = shape(dataArr)[0]
D = mat(ones((m,1))/m) #init D to all equal
aggClassEst = mat(zeros((m,1)))
for i in range(numIt): # 循环（不超过最大迭代次数）
print("第%d次迭代："%(i+1))
bestStump,error,classEst = buildStump(dataArr,classLabels,D)#build Stump
print ("样本系数 D:",D.T)
#计算alpha ， max(error,1e-16) 是为了防止0做分母
alpha = float(0.5*log((1.0-error)/max(error,1e-16)))#calc alpha, throw in max(error,eps) to account for error=0
bestStump['alpha'] = alpha
weakClassArr.append(bestStump) #添加一个弱分类器/投票者 #store Stump Params in Array
print("当前最好分类预测 classEst: ",classEst.T)
#指数矩阵（正确分类 -alpha，错分 +alpha）。因为正确分类 则 1*1 =1 或者 (-1)*(-1) =1 , 错分则 1*(-1) = -1
expon = multiply(-1*alpha*mat(classLabels).T,classEst) #exponent for D calc, getting messy
#更新D
D = multiply(D,exp(expon))
D = D/D.sum()
#calc training error of all classifiers, if this is 0 quit for loop early (use break)
aggClassEst += alpha*classEst # 投票 加权 结果，为浮点数
print ("投票 加权 结果aggClassEst （为浮点数）：\n ",aggClassEst.T)
print("投票后的分类结果：\n",sign(aggClassEst).T)
#sign(aggClassEst) 将 投票结果（浮点数）转化为 分类标签 1或-1
#aggErrors = multiply(sign(aggClassEst) != mat(classLabels).T,ones((m,1)))
aggErrors = sign(aggClassEst) != mat(classLabels).T # 简化，源代码太啰嗦
errorRate = aggErrors.sum()/m #错误率
print ("错误率(total error): ",errorRate)
print("\n")
if errorRate == 0.0: break
return weakClassArr, aggClassEst #返回弱分类器（投票者)列表，以及投票总加权结果（浮点数）
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)
datMat,classLabels = loadSimpData()
dataMat = mat(datMat); labelMat = mat(classLabels).T #转为矩阵
m,n = shape(dataMat)
D= mat(ones((m, 1)) /m) # 个样本初始权重相等,权重之和恒为1
bestStump, minError, bestClasEst = buildStump(dataMat, classLabels, D)
#第一步的结果
print("bestStump:", bestStump)
print("minError:", minError)
print("bestClasEst:\n", bestClasEst,"\n")
classifierArray = adaBoostTrainDS(dataMat, classLabels, 40)程序输出的结果：
可以看到，对于上述简单的数据集，三次迭代之后错误率已经降为0。
当然，我们可以选择其它弱分类器，只需对代码稍作修改。
另外请注意，同SVM一样，AdaBoost只能预测两个类别中的一个。如果想要把它应用到多个类别的场合，那么就要像多类SVM中的做法一样对AdaBoost进行修改。
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-08-31，如有侵权请联系 cloudcommunity@tencent.com 删除
本文分享自 Python可视化编程机器学习OpenCV 微信公众号，前往查看
如有侵权，请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体分享计划 ，欢迎热爱写作的你一起参与！
评论
登录后参与评论
推荐阅读