Adaboost算法概述.pdf

发布时间：2022-05-29 发布人：admin 分类：说明书资料大小：0.24M 资料格式：pdf 举报版权申诉

sz590-5021266-4744302543290245935.pdf-第1页.png

第1页 / 共6页

sz590-5021266-4744302543290245935.pdf-第2页.png

第2页 / 共6页

sz590-5021266-4744302543290245935.pdf-第3页.png

第3页 / 共6页

sz590-5021266-4744302543290245935.pdf-第4页.png

第4页 / 共6页

sz590-5021266-4744302543290245935.pdf-第5页.png

第5页 / 共6页

sz590-5021266-4744302543290245935.pdf-第6页.png

第6页 / 共6页

文本预览

AdaBoost分分分类类类算算算法法法赵兴丽 ( 西南大学计算机与信息科学学院重庆 400715;) 摘要: 本文主要讲述了数据挖掘中十大分类算法之一AdaBoost学习算法的起源、发展和应用，然后介绍了该算法的主要训练过程，性能改进，最后对该算法进行了展望。关键词: AdaBoost算法；发展背景；训练过程；性能改进；分类算法 AdaBoost classiﬁcation algorithm ZHAO xingli ( Southwest University, Beibei District, Chongqing Institute of Computer and Information Science, Chongqing 400715) Abstract: This article is designed to the classiﬁcation algorithm -AdaBoost which is one of the ten learning algorithms in data mining .Firstly it introduces the origin, development and application, then introduces the main training process of the algorithm, performance improvements, and ﬁnally discusses the algorithm. Key words:AdaBoost algorithm; development background; training process ; performance improvement;classiﬁcation algorithm 1 AdaBoost算算算法法法的的的提提提出出出背背背景景景及及及其其其应应应用用用范范范围围围 Adaboost算法是机器学习中一种比较重要的特征分类算法，已被广泛应用人脸表情识别、图像检索等应用中。就目前而言，对Adaboost算法的研究以及应用大多集中于分类问题，在一些回归问题上也有所应用。Adaboost主要解决的问题有: 两类问题、多类单标签问题、多类多标签问题、回归问题。现已有人将Adaboost算法应用到交通管理信息系统中,利用弱学习器来训练道路交通数据,预测道路交通流量情况并且取得良好的效果。Lin将Real Adaboost算法应用到基于内容的图像检索系统中,达到降低噪声的效果,比KNN分类算法准确性有所提高[4]。也有人讲AdaBoost算法应用到区域图像检索中,通过反复训练若分类器而得到了错分率较小的强分类器，可以进行精确地查询。为了解决不同的特征融合分类问题,有人提出了对AdaBoost 算法的改进,改进后的算法在手写数字识别中取得了较好的效果。李闯等人把改进后的AdaBoost 算法应用于目标检测问题等方面。在机器学习领域，Boosting算法是一种通用的学习算法，这一算法可以提升任意给定的学习算法的性能其思想源于1984年Valiant提出的”可能近似正确”-PAC(Probably Approximately Correct)学习模型，在PAC模型中定义了两个概念-强学习算法和弱学习算法。其概念是: 如果一个学习算法通过学习一组样本，识别率很高，则称其为强学习算法;如果识别率仅比随机猜测略高，其猜测准确率大于50 1989年Kearns and Valiant研究了PAC学习模型中弱学习算法和强学习算法两者间的等价问题，即任意给定仅仅比随机猜测稍好(准确率大于0.5)的弱学习算法，是否可以被提升为强学习算法？若两者等价，则我们只需寻找一个比随机猜测稍好的若学习算法，然后将其提升为强学习算法，从而不必费很大力气去直接寻找强学习算法。就此问题，Schapire于1990年首次给出了肯定的答案。他主持这样一个观点：任一弱学习算法可以通过加强提升到一个任意正确率的强学习算法，并通过构造一种多项式级的算法来实现这一加强过程，这就是最初的Boosting算法的原型。Freund于1991年提出了另外一种效率更高的Boosting算法。但此算法需要要提前知道弱学习算法正确率的下限，因而应用范围十分有限。 Freund and Schapire于1995年改进了Boosting算法，取名为Adaboost算法，该算法不需要提前知道所有关于弱学习算法的先验知识，同时运算

效率与Freund在1991年提出的Boosting算法几乎相同。Adaboost即Adaptive Boosting，它能自适应的调整弱学习算法的错误率，经过若干次迭代后错误率能达到预期的效果。另一方面，它不需要精确知道样本空间分布，在每次弱学习后调整样本空间分布，更新所有训练样本的权重，把样本空间中被正确分类的样本权重降低，被错误分类的样本权重将会提高，这样下次弱学习时就更能更关注这些被错误分类的样本。该算法可以很容易地应用到实际问题中，因此，已成为目前最流行的Boosting算法。 2 AdaBoost算算算法法法的的的基基基本本本原原原理理理（（（主主主要要要的的的训训训练练练过过过程程程））） AdaBoost算法的核心思想是针对同一个训练集训练出不同的分类器（弱分类器），然后把这些弱分类器集合起来，构成一个性能更加强大的分类器（强分类器）。 2.1 弱弱弱分分分类类类器器器的的的构构构造造造构造弱分类器算法如下: 矩形特征值：Value[i][j], 1≤i≤n代表所有的Haar特征，1≤j≤m代表所有的样本 FAULT=(curlerror+currerror)表示当前分类器的错误率的最小值，初始设置：curlerror=currerror=m(m是个暴力大的数值就可以) For i=1:n(对每个特征) Found=0 For j=1:m eval[j]=Value[i][j](存放所有样本具有特征i时的特征值) wl = wk,wr = wk, wk是第k个样本权 j j k=1 对eval数组进行从小到大排序 For j=1:m(对排好序的样本) m m 值 wyl = k=j+1 wk · yk, wyr = 本是人脸时yk = 1 否则yk = −1 k=1 k=j+1 curleft = wyl/wl,curright = wyr/wr wk · yk,第k个样 j m k=1 curlerror = currerror = wk · [yk − curlef t]2 wk · [yk − curright]2 k=j+1 if(curlerror + currerror) < F AU LT then ∧F AU LT = (curlerror + currerror) ∧θ = eval[j] (分类器的阈值) ∧α1 = curlef t, α2 = curright ∧f ound = 1 if found = 1 then selection = 1 2 得到一个弱分类器，其对应句型特征号为selection. 以上就是训练一个弱分类器的具体过程。 2.2 Boosting与与与AdaBoost算算算法法法的的的训训训练练练 Boosting是一种将弱分类器通过某种方式结合起来得到一个分类性能大大提高的强分类器的分类方法。该方法可以把一些粗略的经验规则转变为高度准确的预测法则。强分类器对数据进行分类，是通过弱分类器的多数投票机制进行的。该算法是一个简单的弱分类算法提升过程，这个过程通过不断的训练，以提高对数据的分类能力。其过程如下所示：先通过对N个训练数据的学习得到第一个弱分类器h1；将h1分错的数据和其他的新数据一起构成一个新的有N个训练数据的样本，通过对这个样本的学习得到第二个弱分类器h2；将h1和h2都分错了的数据加上其他的新数据构成另一个新的有N个训练数据的样本，通过对这个样本的学习得到第三个弱分类器h3；最终经过提升的强分类器hﬁnal=Majority Vote(h1,h2,h3)。即某个数据被分为哪一类要通过h1,h2,h3的多数表决。[4] 对于上述Boosting算法，存在两个问题： ①如何调整训练集，使得在训练集上训练弱分类器得以进行。 ②如何将训练得到的各个弱分类器联合起来形成强分类器。针对以上两个问题，AdaBoost算法进行了调整： ①使用加权后选取的训练数据代替随机选取的训练数据，这样将训练的焦点集中在比较难分的训练数据上。 ②将弱分类器联合起来时，使用加权的投票机制代替平均投票机制。让分类效果好的弱分类器具有较大的权重，而分类效果差的分类器具有较小的权重。 AdaBoost算法的具体描述如下： Adaboost算法有很多推广形式，目前应用比较广泛由Schapireetal[6,7](1998a)提出，具体流程如下： 1．给定一个训练样本集(x1 ,y1)( x2 ,y2)......(xn ,yn) xi∈X,yi∈1,-1.yi是分类类别的标志，当yi=-1,表示负样本，当yi=1时，表示该样本是正样本；xi是输入训练样本向量,且xi∈X，X是训练样本集； 2.初始化每个样本权重：D1（xi）= ，i=1,2...N。

3．对于T轮训练，for t=1,…,T：（1）将弱学习算法在权值Dt下训练，得到弱分类器：ht: X→[1,-1]。区域面积相等; C型矩形特征要求白色区域面积是黑色区域面积的两倍。把选取的Harr-like 特征作为弱分类器(特征) 。 N i=1 Dt(xi)[ht(xi) = yi] （2）计算该弱分类器在权值Dt下的错误率： εt = (3) βt = εt 1−εt 令：αt = 1 根据上述错误率更新权值： 2 ln(βt) Dt+1(xi) = Dt(xi) Zt × e−at if ht(xi) = yi,then ht(xi)yi = 1 eat if ht(xi) = yi,then ht(xi)yi = −1 = Dt(xi) exp(atyiht(xi)) 其中，Zt 是使 Zt N i=1 T Dt+1(xi) = 1 的归一化因子。 4．T轮训练完毕，最终的强分类器为： H(x) = sign αtht(x) i=1 这个算法定义的弱学习算法，对所有的t都有 εt≤1/2，而这个错误率的上限并不需要事先知道，实际上εt∈[0，1/2]。βt是εt的参数，在每一次迭代中，βt将根据εt来变化，βt被用来对权重向量进行更新。更新的规则是：减小弱分类器预测分类效果较好的数据的概率，增大弱分类器预测分类效果较差的数据的概率。最终的强分类器是T个弱分类器的加权平均. 3 AdaBoost 算算算法法法在在在实实实例例例中中中的的的应应应用用用下面通过一个简单的例子进一步理解AdaBoost算法，该例子主要是利用AdaBoost算法来识别喷码图像。 3.1 弱弱弱分分分类类类特特特征征征的的的选选选取取取如图1观察喷码图像，单号码图像之间其实有一些典型的区分区域(见图2 ) 例图中标出6 和8 的一个典型区分区域，由此考虑通过一组典型区分区域识别喷码图像。2001 年，Violat提出基于Harr 型的AdaBoost 算法[3] ，并应用于人脸检测领域取得了成功。借鉴其成功经验,我们选用简单矩形特征,Harr-like 特征(见图3)作为待识别喷码图像特征。Harr-like特征用五元组表示(x,y,w,h,style )，记录矩形位置，长宽和类型。特征值为矩形中白色区域灰度值和与黑色区域灰度值灰度值和的差值，反映图像局部灰度变化。用快速积分图方法[3] 计算特征值。预选取Harr - like 特征时对矩形面积进行限制: A , B , D型矩形特征要求白色区域面积和黑色图1 ：喷码图像图2 ：典型区分区域图3 ：Harr-Like特征 3.2 分分分类类类器器器的的的构构构造造造 AdaBoost 算法针对的是二分类问题，可以把多个二分类问题组合和一个多分类问题。数字0至9是一个多分类问题，通过决策树可以把这个多分类问题细化为9个二分类问题，这样AdaBoost 算法就可应用于此。对已拍摄到的喷码图像进行预处理和号码分割，得到大小相等的单号码图像，作为训练样本。利用预取的弱分类器( 特征) 对每个二分类问题中的正反样本进行AdaBoost学习，其中训练轮数T根据实际需要选择。在此AdaBoost算法应用中，弱分类器： hj(xi) = 1, pjfj < pjθj 0, others θ 为弱学习寻找出的域值,ﬁ表示特征值，即Harr-like特征值;Pi为不等 3

号方向，根据实际需要设定;x为Harr-like特征。通过AdaBoost算法学习，得到9个强的二分类器，其中每个强二分类器由训练选择出的T个强特征组合而成. 喷码图像通过这9个二分类器的分级分类判定，快速准确地识别出号码。由于喷码常出现错点，断点，重点和漏点，所以故意在训练样本中加人错码样本，以提高分类器对错喷码情况的识别能力。选取分辨率为78x40的4号码喷码图像为实验素材。对现有喷码图像进行预处理和图像分割，得到10类各约100张分辨率为19x40的单号码喷码图像。选取约6000个Harr-like特征作为弱分类器(特征)，AdaBoost学习轮数选择为30，利用上述应用方法构造分类器。[5]通过训练得到9个强分类器，每个强分类器由30个强特征组合而成。从而可以对喷码进行识别。 4 AdaBoost算算算法法法的的的一一一些些些改改改进进进 AdaBoost算法给我们提供方便的同时，也存在着很多不足，研究人员从不同角度对此算法进行了改进，以下是对AdaBoost算法的不足和改进进行了分析：（1）我们已经知道，AdaBoost学习算法在每轮训练中，如果分类器对某些样本正确分类，则相应地减少这些样本的权值；如果分类器错误分类，则相应地增加这些样本的权值，学习算法在以后的学习训练中能够”集中力量”对比较难的训练样本进行学习。AdaBoost学习算法的这种权值更新规则是该算法的较为突出的优点，它可以保证学习算法专注于训练比较难的训练样本。但是，与此同时这也是一个缺点当训练样本集中包含了像噪音样本和一些少见的独特样本（也就是困难样本）时，AdaBoost学习算法将会给这些样本分配一个较高的权值从而最终有可能导致过学习现象的发生，使得泛化误差很大，降低了算法的性能。1999年，R.E.Schapire和Y.Singer提出的使用置信度预测（conﬁdence-rated Edic- tions）[8]的Adaboost学习算法，他们对给出了一个新定义，这样虽然能够改训练误差，但是当样本库规模较小，并有噪音样本存在时，这种改进的Adaboost学习法也有可能导致过学习，从而产生更糟的训练误差。其改进方法，令 T t=1 Masayuki Nakamura[9]等人针对过学习这个问题在R.E.Schapire和Y.Singer[7,8]的基础上提出了一种 f(x) = αtht(x) 训练误差满足： 1 N |{i : H(xi) = yi}| T Zt t=1 新的权值更新规则。他们的试验表明，采用这种新的权值更新规则的Adaboost学习算法的误差小于原始的Adaboost学习算法的误差。而且这种新算法能更有效的防止过学习现象的发生。但是，与此同时他们提出的这种新的权值更新规则也存在两个缺陷：1).虽然这种新方法相比原始Adaboost学习算法而言，误差更低，也能更有效地防止过学习的发生，但是这种新的权值更新规则相比原始的Adaboost学习算法的权值更新规则要更耗时。2).这种新方法只能应用于两类区分问题，如人脸检测等。对多类区分问题不能分类。（2）Aadboost系统检测速度很高，但是Adaboost算法本身训练比较耗时，就整个系统的训练时间也是非常长。根据文献[7] ，其系统要花费数周的时间进行训练。由于Adaboost算法训练时间过长这一缺点，因而大大地限制了该算法的应用。因此，有必要对原训练算法进行并行化。在Viola[1,7,16]的训练方法中，每训练一个简单分类器一般要用上万个训练样本，每个样本有数万个特征，因此从大量特征中训练一个具有最小误差的弱分类器计算量是相当大，例如表1中，m=10000个负样本，l=5000个正样本，数目n共15000个，一个24×24像素大小的图像子窗口就有45396个矩形特征，训练一个简单分类器要在45396×15000=680940000个特征中求解最小误差，这个过程非常耗费时间；而且在完成一次最优弱分类器提取后，每个样本所对应的权重wt,j迭代更新，相当于训练样本概率分布完全变化了，而再次求最优弱分类器时最小误差εj与当前权重wt,j相关，因此简单分类器必须完全重新训练。针对上述问题AdaBoost算法的训练过程可以采用并行化处理，如图4通过分析强分类器的生成过程，可以发现Adaboost算法的训练过程中有两部分可以并行化处理，第一部分是在计算完大量的特征值后，将其排序插入链表[1,16]时；第二部分则是循环训练寻找每轮的最佳弱分类器时。 4

图4 ：训练强分类器的流程这样，可以把特征值排序和弱分类器的训练两部分计算放在并行机上进行。其他部分，例如计算样本特征值，使用强分类器进行检测等等，却仍在串行机器上运行。并行化后的整个流程如图5所示。图5 ：训练强分类器后的流程训练过程中，寻找每轮的最佳弱分类器可以分给p个处理器去完成，因此，训练强分类器的算法并行化[17,18]后如下：对每一个t=1…N(其中N为训练的次数): (1)处理器P0归一化权重W，T0和T1，并广播到所有处理器中；(2)每个处理器计算本地最优弱分类器，并把结果发送给处理器P0；(3)处理器同步,保证处理器P0接收到所有处理器的计算结果；(4)处理器P0通过比较所有的计算结果得到本轮最佳弱分类器；(5)处理器P0调整样本权重。图6显示了这部分并行算法的流程： 5 图6 ：并行训练每轮最佳弱分类器流程 5 小小小结结结 (1)用AdaBoost训练得到的分类器一般都用于灰度图像的检测，这是因为Haar特征构造出来的弱分类器就是基于灰度图像的。如果给定一幅彩色图像，我们先要将它转换为灰度图像，然后才能运用级联分类器进行检测。是否可以运用色度学的知识，构造出基于彩色图像的分类器，将AdaBoost方法直接应用于彩色图像的检测。 (2) 本文用到的弱分类器是比较简单的二值分类器，还有其他分类器，例如神经网络、支持向量机[3,15]等，若弱分类器采用他们是否能取得更好的效果。 (3)在24x24的窗口中就要包含117941个矩形特征，这个数量是很大的，但是其中有很多特征包含人脸的可能性是很小的，例如lx24、24x2的窗口中包含人脸的可能性就很小，在训练弱分类器时这些特征将会占用大量的时间，如何在训练弱分类器之前排除这些包含人脸的可能性很小的特征是一个值得研究的问题。[13] (4)其他：人脸随年龄变化特征主要有：先是外眼角、额头皱纹增多，逐渐蔓延到脸颊上部、眼圈下部；到了中年多数开始出现眼袋；到了老年以后上眼皮逐渐耷拉，眼睛显得小了；同样一个人从小到老，多数眼神由幼稚有光泽到深沉、再到混浊；多数人眉毛会部分更长，甚至出现树根”超长”的，眉毛、男性胡子出现灰、白色的。嘴唇的颜色逐渐灰暗，没有光泽，干燥没有弹性。Adaboost算法能够对人脸的一些特征进行提取,已有人在思考是否可以通过该算法识别人的某些特征，进而估算出人的年龄，年龄的估计做到十分精确恐怕很难，是否

可以先估算出处于某个年龄段，通过对算法一步一步的改进，从而进一步缩小估计的年龄范围，尽可能地接近人的实际年龄。 Reference(References): [1] 左登宇基于Adaboost算法的人脸检测研究[J ] 2009 37- 45 [2] 柴梅平,朱明.基于彩色分割的人脸检测算法的研究闭,计算机测量与控制,2006,14(l):11 13. [3] VIOLA P.Rapid object detection using a Boosted cascade of sim- ple featur [J]. Prc IEEE Confernce on Computer Vision and Pater n Recogition , 2001 . 511一518 . [4] 金王倩，陈斌，黄文杰AdaBoost算法在喷码图像识别的应用[J]计算机应用2006.26 (9) . [5] 黄文杰，陈斌一种快速图像处理的积分图方法[J] .计算机应用2005 , 25 (Z1) , 266一268 . [6] 陈茂林，戚飞虎.自组织隐马尔可夫模型的人脸检测研究[J].计算机学报，2002，25(II):1165 1169. [8] 梁路宏，艾海舟，何克忠，张拔.基于多关联模板匹配的人脸检测[J]软件学报，2001，12(l):94 102. [9] 梁路宏，艾海舟，何克忠，张拔.基于仿射模板匹配的多角度单人脸定位[J].计算机学报，23(6):641 646. [10] 梁路宏，艾海舟，徐光佑，张拔.人脸检测研究综述[J].计算机学报，2002，25(5):44 [11] 田欣.基于不同色彩空间的肤色模型[J].西安科技学院学报，2O01，21(4):369 371. [12] 梁路宏，艾海舟，何克忠，张拔.基于仿射模板匹配的多角度单人脸定位[J].计算机学报，23(6):641 646. [13] 王洪群，彭嘉雄，强赞霞.基于边缘和纹理特征相结合的快速人脸精确定位方法[J].计算程与应用，2004，40(7):27 32 [14] 王倩，陈斌，黄文杰.Adaboost算法在喷码图像识别的应用[J]计算机应用，2O06，26 (9):2100 2101 [15] Freund Y.Boosting a Weak Learning Algorithm By major- ity[J]．Information and Computation,1995，121(2)：256 285 [16] Bernd Heisele,Thomas Serreb,Sam Prenticeb,Tomaso Pog- giob,Hierarchical classi?cation and feature reduction for fast face detection with support vector machines[J].Pattern Recognition 2003,36(9):201 202. [17] 赵丽红，刘纪红，徐心和.人脸检测方法综述[J].计算机应用研 [7] 孔凡之,张兴周,谢耀菊.基于Adaboost的人脸检测技术[J].应用科究，2004，21(9):1 4 学,2O05,32(6):7 10 [18] 赵楠.基于Adaboost算法的人脸检测[D].北京:北京大学,2005. 6

分享到：

赞收藏

资料库

Adaboost算法概述.pdf

相关推荐

开发技术

热门标签

最新资料