关键词:
前言
有人认为 AdaBoost 是最好的监督学习的方式。
某种程度上因为它是元算法,也就是说它会是几种分类器的组合。这就好比对于一个问题能够咨询多个 "专家" 的意见了。
组合的方式有多种,可能是不同分类算法的分类器,可能是同一算法在不同设置下的集成,还可以是数据集在不同部分分配给不同分类器之后的集成等等。
本文将给出的 AdaBoost 分类器实现基于第二种 (另外几种实现在此基础上稍作改动即可)。
一种原始的元算法 - bagging (自举汇聚法)
这个算法的意思有点像投票系统,其思路步骤大致如下:
1. 将数据按照一定的规则划分成 N 份,每份的大小和原数据集一样大 (因此里面肯定是有重复数据的)。
2. 将这 N 份数据集分发到多个分类器中。
3. 按照 "少数服从多数" 原则,从这 N 个分类器的分类结果中总结出最优结果。
boost (提高任意给定学习算法精确度算法) vs bagging (自举汇聚法)
boost 和 bagging 一个很大的不同是它会给那些分错的样本更高关注度(权重)。AdaBoost 是一种最为典型的 boost 元算法。
因此理论上它能在相对较少的迭代次数下得到更为精确的分类结果。
AdaBoost 元算法的基本原理
AdaBoost 的强大之处,在于它能够集成多个弱分类器,形成一个强分类器。
所谓弱分类器就是分类错误率大于五成的分类器,比随机分类还渣。(但是它的分类算法是确定的,这点和随机分类器不同。显然你无法通过集成随机分类器得到什么有价值的东西)
其具体步骤大致如下:
1. 对每个样本给定一个权重 d。
2. 基于权重向量 D 调用一次弱分类器并得出这次统计的分类器权重值 alpha (注意是分类器权重值,区别于上一步的权重d)
3. 基于分类器权重值 alpha 更新各个样本的权重向量
4. 循环 2 - 3 直到错误率为 0 或者循环到了指定的次数
5. 1-4 为训练部分算法,训练好了之后,便可带入样本进行分类。分类的方法是依次带入训练集中的各个分类器中求出分类结果,然后各部分结果乘以其对应的分类器权重值 alpha 再累加求和。
下图可用来帮助理解 (直方图中的矩形长度表示样本权重,三角形中的值表示分类器权重值 alpha):
基于单层决策树的 AdaBoost 元算法分类器实现
首先,准备好单层决策树的数据结构。
在本文的 AdaBoost 实现中,元算法中的分类器组合模式是 "同一算法在不同设置下的集成",那么不同设置不同在哪里?
不同就不同在每次构建单层决策树都是选择划分正确率最高的划分方式。
因此在构建单层决策树函数中,必须有一个择优过程,具体可以参考下面的实现代码。
函数的功能应当是返回一个单层决策树信息结构(仅仅是划分信息就可以了不用数据)。
同时,函数应该返回一个错误信息值,这个错误值是和权重向量D相关的,用于计算分类器权重值 alpha。(当然也可以在该函数内部实现该字段)
最后,分类结果自然也要返回。
单层决策树代码实现如下:
1 #========================================== 2 # 输入: 3 # dataMatrix: 输入数据 4 # dimen: 划分特征下标 5 # threshVal: 划分阈值 6 # threshIneq: 划分方向(是左1右0分类还是左0右1分类) 7 # 输出: 8 # retArray: 分类结果 9 #========================================== 10 def stumpClassify(dataMatrix,dimen,threshVal,threshIneq): 11 '按照指定方式分类并返回结果' 12 13 retArray = numpy.ones((numpy.shape(dataMatrix)[0],1)) 14 if threshIneq == 'lt': 15 retArray[dataMatrix[:,dimen] <= threshVal] = -1.0 16 else: 17 retArray[dataMatrix[:,dimen] > threshVal] = -1.0 18 19 return retArray 20 21 22 #========================================== 23 # 输入: 24 # dataArr: 输入数据 25 # classLabels: 分类标签集 26 # D: 权重向量 27 # 输出: 28 # bestStump: 决策树信息 29 # minError: 带权错误(用于生成分类器权重值 alpha) 30 # bestClasEst: 分类结果 31 #========================================== 32 def buildStump(dataArr,classLabels,D): 33 '创建单层最佳决策树' 34 35 dataMatrix = numpy.mat(dataArr); 36 labelMat = numpy.mat(classLabels).T 37 m,n = numpy.shape(dataMatrix) 38 39 # 特征值阈值步长 40 numSteps = 10.0; 41 # 当前最佳决策树信息集 42 bestStump = {}; 43 # 分类结果 44 bestClasEst = numpy.mat(numpy.zeros((m,1))) 45 # 最小带权错误初始化为无穷大 46 minError = numpy.inf 47 48 for i in range(n): # 遍历所有的特征选取最佳划分特征 49 rangeMin = dataMatrix[:,i].min(); 50 rangeMax = dataMatrix[:,i].max(); 51 stepSize = (rangeMax-rangeMin)/numSteps 52 53 for j in range(-1,int(numSteps)+1): # 遍历所有的特征值选取最佳划分特征值 stepSize为探测步长 54 55 for inequal in ['lt', 'gt']: # 对于 左1右0 和 左0右1 两种分类方式 56 57 # 当前划分阈值 58 threshVal = (rangeMin + float(j) * stepSize) 59 # 分类 60 predictedVals = stumpClassify(dataMatrix,i,threshVal,inequal) 61 # 统计分类错误信息 62 errArr = numpy.mat(numpy.ones((m,1))) 63 errArr[predictedVals == labelMat] = 0 64 weightedError = D.T*errArr 65 66 # 更新最佳决策树的信息 67 if weightedError < minError: 68 minError = weightedError 69 bestClasEst = predictedVals.copy() 70 bestStump['dim'] = i 71 bestStump['thresh'] = threshVal 72 bestStump['ineq'] = inequal 73 74 return bestStump,minError,bestClasEst
在单层决策树之上,便是 AdaBoost 分类器的实现,下面先给出伪代码:
1 对每次迭代: 2 找到最佳单层决策树 3 将该树加入到最佳决策树数组 4 计算分类器权重 alpha 5 更新权重向量 D 6 更新累计类别估计值 7 PS: 如果错误率等于0.0,则立马退出循环。
Python 代码实现如下:
1 #========================================== 2 # 输入: 3 # dataArr: 输入数据 4 # classLabels: 分类标签集 5 # numIt: 最大迭代次数 6 # 输出: 7 # bestStump: 决策树信息 8 # minError: 带权错误(用于生成分类器权重值 alpha) 9 # bestClasEst: 分类结果 10 #========================================== 11 def adaBoostTrainDS(dataArr,classLabels,numIt=40): 12 'AdaBoost 分类器' 13 14 # 最佳决策树集合 15 weakClassArr = [] 16 # 样本个数 17 m = numpy.shape(dataArr)[0] 18 # 权重向量 19 D = numpy.mat(numpy.ones((m,1))/m) 20 # 各个类别的估计累积值 21 aggClassEst = numpy.mat(numpy.zeros((m,1))) 22 23 for i in range(numIt): # 迭代 numIt 次 24 # 构建最佳决策树 25 bestStump,error,classEst = buildStump(dataArr,classLabels,D) 26 # 计算该决策树的分类器权重值 alpha 27 alpha = float(0.5*numpy.log((1.0-error)/max(error,1e-16))) 28 bestStump['alpha'] = alpha 29 # 将该决策树加入到决策树数组中去 30 weakClassArr.append(bestStump) 31 32 # 更新权重向量 33 expon = numpy.multiply(-1*alpha*numpy.mat(classLabels).T,classEst) 34 D = numpy.multiply(D,numpy.exp(expon)) 35 D = D/D.sum() 36 37 # 计算当前的总错误率。如果错误率为0则退出循环。 38 aggClassEst += alpha*classEst 39 aggErrors = numpy.multiply(numpy.sign(aggClassEst) != numpy.mat(classLabels).T,numpy.ones((m,1))) 40 errorRate = aggErrors.sum()/m 41 print "错误率: ",errorRate 42 if errorRate == 0.0: break 43 44 return weakClassArr
至此,就可以用 AdaBoost 进行分类了。
首先训练出一个训练集,然后将训练集带入分类函数,如下:
1 # 获取训练集 2 classifierArr = adaBoostTrainDS(daaArr, labelArr, 30) 3 # 分类并打印结果 4 print adaClassify([0,0], classifierArr)
测试结果:
显然,可以看出 AdaBoost 分类器由三个决策树构成。样本最终分类结果为 -1。
小结
本文介绍了分类器中的元算法思想。通过这样的思想,能够将多种分类器组合起来,大大地加强了分类性能。
另外据可靠数据分析,较之逻辑回归,AdaBoost 分类器没有过度拟合(overfitting)现象。
Boost算法还有很多种,AdaBoost 只是其中最为经典的实现之一,还有更多高级实习需要在日后学习工作中进行研究。
机器学习实战笔记-利用adaboost元算法提高分类性能
做重要决定时,大家可能都会考虑吸取多个专家而不只是一个人的意见。机器学习处理问题时又何尝不是如此?这就是元算法(meta-algorithm)背后的思路。元算法是对其他算法进行组合的一种方式7.1基于数据集多重抽样的分类器??... 查看详情
机器学习实战第7章——利用adaboost元算法提高分类性能(代码片段)
将不同的分类器组合起来,这种组合结果被称为集成方法或元算法(meta-algorithm)。使用集成方法时会有多种形式:(1)可以是不同算法的集成(2)可以是同一种算法在不同设置下的集成(3)数据集不同部分分配给不同分类器... 查看详情
机器学习算法-adaboost
本章内容组合类似的分类器来提高分类性能应用AdaBoost算法处理非均衡分类问题主题:利用AdaBoost元算法提高分类性能1.基于数据集多重抽样的分类器-AdaBoost长处泛化错误率低,易编码,能够应用在大部分分类器上,无需參数调整... 查看详情
利用adaboost提高分类性能
Adaboost为一种集成算法,是对其他算法进行组合的一种方式。本文将通过单层决策树分类器建立一个Adaboost优化算法,即利用多个弱分类器构建一个强分类器。弱分类器:分类器性能比随机猜测要略好,但是也不会好太多。强分... 查看详情
机器学习(利用adaboost元算法提高分类性能)(代码片段)
元算法背后的思路是对其他算法进行组合的一种方式,Afromnumpyimport*defloadSimpData():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]returndatMat,classLabelsdefloadDataSet(fileName 查看详情
《机器学习实战第7章:利用adaboost元算法提高分类性能》(代码片段)
importnumpyasnpimportmatplotlib.pyplotaspltdefloadSimpData():dataMat=np.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]returndataMat,classLabelsdefshowDataSet(d 查看详情
第九篇:随机森林(randomforest)
... 随机森林非常像《机器学习实践》里面提到过的那个AdaBoost算法,但区别在于它没有迭代,还有就是森林里的树长度不限制。 因为它是没有迭代过程的,不像AdaBoost那样需要迭代,不断更新每个样本以及子... 查看详情
adaboost元算法(代码片段)
boosting:不同的分类器是通过串行训练而获得的,每个新分类器都根据已经训练出的分类器的性能来进行训练。通过集中关注被已有分类器错分的那些样本来获得新的分类器。权重alpha:弱分类器的线性组合系数,用来构成完整... 查看详情
提升算法——adaboost
思路:通过改变训练样本权重,学习多个分类器,并将这些分类器进行线性组合,提高分类器性能。大多数提升方法都是改变训练数据的概率分布(数据的权值)强可学习:存在一个多项式的学习算法能够学习他,并且正确率很... 查看详情
图像算法研究---adaboost算法具体解释
本篇文章先介绍了提升放法和AdaBoost算法。已经了解的可以直接跳过。后面给出了AdaBoost算法的两个样例。附有详细计算过程。1、提升方法(来源于统计学习方法) 提升方法是一种经常使用的统计学习方法,应用十分广... 查看详情
adaboost理解
AdaBoost是一种准确性很高的分类算法,它的原理是把K个弱分类器(弱分类器的意思是该分类器的准确性较低),通过一定的组合(一般是线性加权进行组合),组合成一个强的分类器,提高分类的准确性。因此,要想使用AdaBoost,需要... 查看详情
adaboost算法
...考技术A链接:1.线性回归总结2.正则化3.逻辑回归4.Boosting5.Adaboost算法转自:原地址提升方法(boosting)是一种常用的统计学习方法,应用广泛且有效。在分类问题中,它通过改变训练样本的权重,学习多个分类器,并将这些分类器... 查看详情
class-提升方法boosting
1AdaBoost算法2AdaBoost训练误差分析3AdaBoostalgorithm另外的解释3.1前向分步算法3.2前向分步算法与AdaBoost4提升树4.1提升树模型4.2梯度提升Boosting在分类问题中,通过改变训练样本的权重,学习多个分类器,并将这些分类器进行线性组合... 查看详情
人脸检测——基于机器学习3adaboost算法
简介主要工作AdaBoost算法的人脸检测算法包含的主要工作:(1)通过积分图快速求得Haar特征;(2)利用AdaBoost算法从大量的特征中选择出判别能力较强的少数特征用于人脸检测分类;(3)提出一个级联结构模型,将若干个弱分... 查看详情
adaboost(自适应增强算法)
AdaBoost(自适应增强算法)AdaBoost的目标是通过一个弱分类器构建一个强分类器,AdaBoost的大致运行过程:训练数据中的每一个样本,并赋予其一个权重,形成对应的权重向量DD,一开始所有训练样本具有相同权值,然... 查看详情
机器学习---算法---adaboost
...自:https://blog.csdn.net/px_528/article/details/72963977写在前面说到Adaboost,公式与代码网上到处都有,《统计学习方法》里面有详细的公式原理,Github上面有很多实例,那么为什么还要写这篇文章呢?希望从一种更容易理解的角度,来为... 查看详情
adaboost提升算法从原理到实践
...可学习算法的算法。如何地这些弱算法进行提升是关键!AdaBoost算法是其中的一个代表。2.分类算法提升的思路: 1.找到一个弱分类器,分类器简单,快捷,易操作(如果它本身就很复杂, 查看详情
adaboost
...成。代表算法是boosting系列算法。在boosting系列算法中,Adaboost是最著名的算法之一。第二类是个体学习器之间不存在强依赖关系,一系列个体学习器可以并行生成,代表算法是bagging和随机森林(RandomForest)系列算法。。Adaboost既... 查看详情