AdaBoost算法分析及简单应用

机器学习课程结课论文学号、专业：姓名：yan**论文题目：Adaboost算法分析及简单应用指导教师：杨**所属学院：电子工程与自动化学院成绩评定教师签名桂林电子科技大学研究生院年月日Adaboost算法分析及简单应用Yan**(桂林电子科技大学电子工程与自动化学院广西桂林541004)摘要:本文主要阐述了在数据挖掘领域中十个主要的分类算法之一——Adaboost的来源、发展，以及开发应用，然后介绍了在该算法的训练过程中一个简单的应用，最后对该算法进行了简单评价。关键词:Adaboost算法；发展背景；训练过程；性能改进；分类算法AnalysisofthealgorithmanditssimpleapplicationYan**SchoolofelectronicengineeringandautomationofGuilinUniversityofElectronicTechnology,Guilin541004,ChinaAbstract:Thispapermainlydescribesoneofthetenmainclassificationalgorithmindateamining——Adaboost.Firstly,itintroducestheorigin,developmentandapplication,thenintroducesthemaintrainingprocessofthealgorithm,simpleapplicationandfinallydiscussesthealgorithmsimply.Keywords:Adaboostalgorithm;developmentbackground;trainingprocess;performanceimprovement;classificationalgorithm1引言在1990年，Schapire提出了Boosting算法，次年Freund改进Boosting算法，这两种算法存在共同的实践上的缺陷，那就是都要求事先知道弱学习算法学习正确率的下限。1995年，Freund和Schapire共同改进了Boosting算法，提出了Adaboost(AdaptiveBoosting)算法，该算法效率和Freund于1991年提出的Boosting算法几乎相同，但不需要任何关于弱学习器的先验知识，因而更容易应用到实际问题当中。Adaboost即AdaptiveBoosting，它通过自适应学习算法来降低误差率，多次迭代后达到预期的效果。在另一方面，它并不需要知道样本空间的精确分布，每个样品经过弱学习调节后，通过权重的高低更新空间分布。该算法可以很容易地应用到实际问题，因此，已成为最流行的Boosting算法。在机器学习的算法中，Adaboost算法是一种比较重要且通用的用于特征分类的算法，在图像检索和人脸表情识别等问题中都有普遍应用。从现状看，人们对Adaboost算法的研究及应用主要集中用于分类问题上，另外在某些回归问题上也有所涉及，比如两类问题、多类单标签问题、多类多标签问题和回归问题。该学习算法可以提高其他算法的性能，其思想来自于1984年Valiant提出的PAC(ProbablyApproximatelyCorrect)（可能近似正确）学习模型，在这个PAC模型中，提出了两个概念-弱学习算法和强学习算法。其概念是:如果一个学习算法通过学习一组样本，识别率很高，则称其为强学习算法;如果识别正确率只有50%左右，仅略高于随机猜测，则称其为弱学习算法。强分类器是指一种算法通过一些训练集的学习，来达到所需的正确识别率。如果一个学习算法的识别率仅好于随机的猜测，则称其为弱分类器。通常，针对一个具体的识别问题，我们很难找到一个理想的强分类器，但是弱分类器一般都会有很多，基于这种现象，Adaboost算法被提出，它指出：通过一定的算法可以将一组弱分类器提升为一个强分类器。Adaboost在机器学习领域中十分重要，它是一种提高任意给定学习算法准确度的方法。也就是说，Adaboost算法为其他算法提供了一种框架结构，而其他算法只在其中作为子分类器，因此Adaboost算法可以运用在许多方面的实践上。如今通过Adaboost算法，我们实现了手写体字符识别，运用到了许多输入设备上，如流行的触屏手机上的手写输入、笔记本电脑的手写输入、扫描仪扫面文字转化为电子文档。我们实现了图像识别，如人脸识别、google上的图片检索功能（很方便地找到我想要的清晰度更高的图片）。我们实现了语音识别，现在的WIN7上都有了一个语音识别的功能，我们能够让计算机知道我们说了什么话，并通过机器自动学习提高语音识别的精度，声音输入和声控很可能在未来普及。当然Adaboost算法还能做文本分类和医疗诊断等等。2算法描述Adaboost的是一种迭代算法，其主要思想是针对相同的训练集用不同的分类器（弱分类器）去学习，然后把这些弱分类器结合起来，以形成更强的最终分类器（强分类器）。算法本身是通过改变数据分布，根据每个训练的样本的分类是否正确，以及整体分类的精度来确定每个样本的权重来实现的。每次都是将样本加权后得到一组新的数据并将其分给下一层的分类器进行训练，直至达到一定的正确率，然后将这些分类器融合在一起形成一个最终分类器，作为一个最后的决定分类。Adaboost算法的基本步骤是：首先，给出一个弱学习算法和训练集（X1，Y1），（X2，Y2），...，（XM，YM），其中，XM∈X，X代表分类问题或类域实例空间，YM∈Y={+1，-1}。初始化时，Adaboost算法将训练集指定分配1/M，即每个训练样本的权重都是1/M。然后，用弱学习算法进行T次迭代，每次迭代都根据训练结果来更新训练集的分布情况，并为训练失败的训练实例给予更大的权重，这样的训练实例将在下一次迭代得到更多的关注。这样经T次循环后将会得到T个弱分类器，最终按更新的权重叠加到一起得到强分类器，这个最终的强分类器是这些弱分类器的加权平均。虽然单个弱学习器的准确率不高，但采用Adaboost算法后，将会使得结果更为准确。Adaboost算法与Boosting算法不同，它不需要预先知道弱分类器分错的概率，并且最后它是通过所有弱分类器的分类精度来得到这个强分类器的分类精度，这样可以提高分类能力。简单地说，Adaboost算法的训练是通过调整每个样品相应的权重来实现的。首先，将各样品的权重比设成一样，其中M是一个弱学习的样本分布的训练次数。对于错误分类的样本，增加相应的权重，而对于正确分类的样本，降低其权重，这样错的样本就受到重视以便下次“对症下药”。在新的样本分布中，又一次进行弱学习算法地训练。这样经T周期的循环得到T个弱分类器，再把这些弱分类器加权起来，最终得到一个合适的的强分类器。下面我们举一个简单的例子来看看Adaboost的实现过程：图中，“+”和“-”分别表示两种类别，在这个过程中，我们使用水平或者垂直的直线作为分类器，来进行分类。根据分类的正确率，得到一个新的样本分布D2，一个子分类器h1。其中划圈的样本表示被分错的。在右边的图中，比较大的“+”表示对该样本做了加权。算法最开始给了一个均匀分布D。所以h1里的每个点的值是0.1。当划分后，有三个点划分错了，根据算法误差表达式~Pr[()]ttiDtiihxy得到误差为分错了的三个点的值之和，所以ɛ1=(0.1+0.1+0.1)=0.3，而ɑ1根据表达式11ln()2ttt可以算出来为0.42.然后就根据算法把分错的点权值变大。如此迭代，最终完成Adaboost算法。根据分类的正确率，得到一个新的样本分布D3，一个子分类器h2。得到一个子分类器h3整合所有子分类器：此例的阈值是1，即加权平均后对于蓝色中大于1的区域就划分为蓝色种类，其他部分为红色种类。因此，从综合的效果来看，即使是一个简单的分类器组合，也可以得到较好的分类结果。3本文的方法Adaboost算法的完整步骤如下：如今，Adaboost算法有了很大的发展，并且还出现了许多其他boost算法，比如Gentleboost和Logitboost算法等。从上图中我们可以看到Adaboost算法的一个详细过程。Adaboost是一种较有特点的算法，现总结如下：1）每次迭代改变的是样本的分布，而不是重复采样。2）样本分布的改变取决于样本是否被正确分类。总是分类正确的样本权值低，而分类错误的样本权值高。3）最终的结果是弱分类器的加权组合。权值表示该弱分类器的性能。下面我们看看Adaboost是如何进行训练的：4实验（1）实验程序这是用Java语言在Eclipse环境中写的一个小程序。下面的代码：Adaboost类的代码：publicclassAdaboost{int[][]matrix=newint[8][8];//矩阵，行代表基分类器，列代表测试点Point[]point;BaseClassifiers[]bc;VectorIntegerh=newVectorInteger();VectorDoublea=newVectorDouble();//预测点的labelpublicintjudge(Pointp){doubleresult=0.0;for(inti=0;ih.size();i++){doubletemp=a.get(i)*bc[h.get(i)].classify(p);result+=temp;}returnresult0?1:-1;}//这个函数在对象生成后就应该被调用，但是参数由用户输入，所以没有把它放到生成函数中publicvoidAdaboost(intT,doubledelt){//传过来T=10，delt=0.01；intlen=this.point.length;//长度为8，即len=8double[]D=newdouble[len];//每个点的权重//初始时每个点权重应满足均匀分布for(inti=0;ilen;i++){D[i]=1.0/len;}for(intt=1;tT;t++){doubleerror=chooseHypothese(D);if(Math.abs(error-0.5)delt){break;}doubleat=0.5*Math.log((1-error)/error);a.add(at);doublez=2*Math.sqrt(error*(1-error));for(inti=0;ilen;i++){D[i]=D[i]*Math.exp(-1*at*point[i].label*matrix[h.get(h.size()-1)][i])/z;}}DecimalFormatdf=newDecimalFormat(0.00);for(Integeri:h){System.out.print(i+\t\t);}System.out.println();for(Doubled:a){Strings=df.format(d);System.out.print(s+\t\t);}}//选择最小错误的分类器，返回错误值publicdoublechooseHypothese(double[]D){intmin=Integer.MAX_VALUE;doubleerror=1.1;for(inti=0;ibc.length;i++){doubletemp=0.0;for(intj=0;jpoint.length;j++){if(bc[i].classify(point[j])!=point[j].label){temp+=D[j];}}if(temperror){error=temp;min=i;}}h.add(min);returnerror;}publicAdaboost(Point[]point,BaseClassifiers[]bc){this.point=point;this.bc=bc;//计算矩阵，行代表基分类器，列代