adaboost算法原理

聚类和分类的区别是什么？一般对已知物体类别总数的识别方式我们称之为分类，并且训练的数据是有标签的，比如已经明确指定了是人脸还是非人脸，这是一种有监督学习。也存在可以处理类别总数不确定的方法或者训练的数据是没有标签的，这就是聚类，不需要学习阶段中关于物体类别的信息，是一种无监督学习。

Haar分类器实际上是Boosting算法的一个应用，Haar分类器用到了Boosting算法中的AdaBoost算法，只是把AdaBoost算法训练出的强分类器进行了级联，并且在底层的特征提取中采用了高效率的矩形特征和积分图方法。

在2001年，Viola和Jones两位大牛发表了经典的《Rapid Object Detection using a Boosted Cascade of Simple Features》【1】和《Robust Real-Time Face Detection》【2】，在AdaBoost 算法的基础上，使用Haar-like小波特征和积分图方法进行人脸检测，他俩不是最早使用提出小波特征的，但是他们设计了针对人脸检测更有效的特征，并对AdaBoost训练出的强分类器进行级联。这可以说是人脸检测史上里程碑式的一笔了，也因此当时提出的这个算法被称为Viola-Jones检测器。又过了一段时间，Rainer Lienhart和Jochen Maydt两位大牛将这个检测器进行了扩展《An Extended Set of Haar-like Features for Rapid Object Detection》【3】，最终形成了OpenCV现在的Haar分类器。

Haar分类器= Haar-like特征+ 积分图方法+ AdaBoost + 级联；

Haar分类器算法的要点如下：

①使用Haar-like特征做检测。

②使用积分图（Integral Image）对Haar-like特征求值进行加速。

③使用AdaBoost算法训练区分人脸和非人脸的强分类器。

④使用筛选式级联把强分类器级联到一起，提高准确率。

1.Haar-like特征你是何方神圣

Haar-like特征，那么我先说下什么是特征，我把它放在下面的情景中来描述，假设在人脸检测时我们需要有这么一个子窗口在待检测的图片窗口中不断的移位滑动，子窗口每到一个位置，就会计算出该区域的特征，然后用我们训练好的级联分类器对该特征进行筛选，一旦该特征通过了所有强分类器的筛选，则判定该区域为人脸。

所谓的特征不就是一堆堆带条纹的矩形么，到底是干什么用的？我这样给出解释，将上面的任意一个矩形放到人脸区域上，然后，将白色区域的像素和减去黑色区域的像素和，得到的值我们暂且称之为人脸特征值，如果你把这个矩形放到一个非人脸区域，那么计算出的特征值应该和人脸特征值是不一样的，而且越不一样越好，所以这些方块的目的就是把人脸特征量化，以区分人脸和非人脸。

为了增加区分度，可以对多个矩形特征计算得到一个区分度更大的特征值，那么什么样的矩形特征怎么样的组合到一块可以更好的区分出人脸和非人脸呢，这就是AdaBoost算法要做的事了。这里我们先放下积分图这个概念不管，为了让我们的思路连贯，我直接开始介绍AdaBoost算法。

2 AdaBoost你给我如实道来！

Boosting算法的核心思想，是将弱学习方法提升成强学习算法，也就是“三个臭皮匠顶一个诸葛亮”，它的理论基础来自于Kearns和Valiant牛《Crytographic Limitations on Learning Boolean Formulae and Finite Automata》的相关证明【4】，在此不深究了。（AdaBoost在Haar分类器中的应用，所以只是描述了它在Haar分类器中的特性，而实际上AdaBoost是一种具有一般性的分类器提升算法，它使用的分类器并不局限某一特定算法。）

上面说到利用AdaBoost算法可以帮助我们选择更好的矩阵特征组合，其实这里提到的矩阵特征组合就是我们之前提到的分类器，分类器将矩阵组合以二叉决策树的形式存储起来。

我现在脑子里浮现了很多问题，总结起来大概有这么些个：

v 弱分类器和强分类器是什么？

v 弱分类器是怎么得到的？

v 强分类器是怎么得到的？

v 二叉决策树是什么？

2.1 AdaBoost的身世之谜

Valiant牛《A Theory of the Learnable》提出了Boosting算法，Boosting算法涉及到两个重要的概念就是弱学习和强学习，所谓的弱学习，就是指一个学习算法对一组概念的识别率只比随机识别好一点，所谓强学习，就是指一个学习算法对一组概率的识别率很高。现在我们知道所谓的弱分类器和强分类器就是弱学习算法和强学习算法。弱学习算法是比较容易获得的，获得过程需要数量巨大的假设集合，这个假设集合是基于某些简单规则的组合和对样本集的性能评估而生成的，而强学习算法是不容易获得的，然而，Kearns 和Valiant 两头牛提出了弱学习和强学习等价的问题【6】并证明了只要有足够的数据，弱学习算法就能通过集成的方式生成任意高精度的强学习方法。这一证明使得Boosting有了可靠的理论基础，Boosting算法成为了一个提升分类器精确性的一般性方法。

Boosting算法还是存在着几个主要的问题，其一Boosting算法需要预先知道弱学习算法学习正确率的下限即弱分类器的误差，其二Boosting算法可能导致后来的训练过分集中于少数特别难区分的样本，导致不稳定。针对Boosting的若干缺陷，Freund和Schapire牛于1996年前后提出了一个实际可用的自适应Boosting算法AdaBoost《A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting》。

2.2弱分类器的孵化

最初的弱分类器可能只是一个最基本的Haar-like特征，计算输入图像的Haar-like特征值，和最初的弱分类器的特征值比较，以此来判断输入图像是不是人脸，然而这个弱分类器太简陋了，可能并不比随机判断的效果好，对弱分类器的孵化就是训练弱分类器成为最优弱分类器，注意这里的最优不是指强分类器，只是一个误差相对稍低的弱分类器，训练弱分类器实际上是为分类器进行设置的过程。至于如何设置分类器，设置什么，我们首先分别看下弱分类器的数学结构和代码结构。

??数学结构

??代码结构

[cpp]view plain copy print?

1.typedef struct CvCARTHaarClassifier

2.{

3. CV_INT_HAAR_CLASSIFIER_FIELDS()

4.int count; //包含弱分类器的个数

5.int* compidx; //这个弱分类器对应的特征编号。即这个弱分类器是第compidx特征产生的

6.CvTHaarFeature* feature; //弱分类器对应的特征的特征坐标

7. CvFastHaarFeature* fastfeature;//弱分类器对应的特征的特征坐标

8.float* threshold; //该弱分类器的阈值

9.int* left; //同上

10.int* right;

11.float* val;

12.} CvCARTHaarClassifier;

代码结构中的threshold即代表数学结构中的 阈值。

这个阈值究竟是干什么的？我们先了解下CvCARTHaarClassifier这个结构，注意CART这个词，它是一种二叉决策树，它的提出者Leo Breiman等牛称其为“分类和回归树（CART）”。什么是决策树？

“机器学习中，决策树是一个预测模型；他代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，而每个分叉路径则代表的某个可能的属性值，而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。决策树仅有单一输出，若欲有复数输出，可以建立独立的决策树以处理不同输出。从数据产生决策树的机器学习技术叫做决策树学习, 通俗说就是决策树。”

决策树包含：分类树，回归树，分类和回归树（CART），CHAID。

分类和回归的区别是，分类是当预计结果可能为两种类型(例如男女，输赢等)使用的概念。回归是当局域结果可能为实数(例如房价，患者住院时间等)使用的概念。

决策树用途很广可以分析因素对事件结果的影响（详见维基百科），同时也是很常用的分类方法，我举个最简单的决策树例子，假设我们使用三个Haar-like特征f1，f2，f3来判断输入数据是否为人脸，可以建立如下决策树：

可以看出，在分类的应用中，每个非叶子节点都表示一种判断，每个路径代表一种判断的输出，每个叶子节点代表一种类别，并作为最终判断的结果。

一个弱分类器就是一个基本和上图类似的决策树，最基本的弱分类器只包含一个

Haar-like特征，也就是它的决策树只有一层，被称为树桩（stump）。

最重要的就是如何决定每个结点判断的输出，要比较输入图片的特征值和弱分类器中特征，一定需要一个阈值，当输入图片的特征值大于该阈值时才判定其为人脸。训练最优弱分类器的过程实际上就是在寻找合适的分类器阈值，使该分类器对所有样本的判读误差最低。

在此元素之前的非人脸样本的权重的和s0；

2）最终求得每个元素的分类误差

1/* internal stage classifier */

2 typedef struct CvStageHaarClassifier

3 {

4 CV_INT_HAAR_CLASSIFIER_FIELDS()

5int count;

6float threshold;

7 CvIntHaarClassifier** classifier;

8 }CvStageHaarClassifier;

/* internal weak classifier*/

typedef struct CvIntHaarClassifier

{

CV_INT_HAAR_CLASSIFIER_FIELDS()

} CvIntHaarClassifier;

这里要提到的是CvIntHaarClassifier结构：它就相当于一个接口类，当然是用C语言模拟的面向对象思想，利用CV_INT_HAAR_CLASSIFIER_FIELDS()这个宏让弱分类CvCARTHaarClassifier和强分类器CvStageHaarClassifier继承于CvIntHaarClassifier。

强分类器的诞生需要T轮的迭代，具体操作如下：

1. 给定训练样本集S，共N个样本，其中X和Y分别对应于正样本和负样本； T为训练的最大循环次数；

2. 初始化样本权重为1/N，即为训练样本的初始概率分布；

3. 第一次迭代训练N个样本，得到第一个最优弱分类器，步骤见2.2节

4. 提高上一轮中被误判的样本的权重；

5. 将新的样本和上次本分错的样本放在一起进行新一轮的训练。

6. 循环执行4-5步骤，T轮后得到T个最优弱分类器。

7.组合T个最优弱分类器得到强分类器，组合方式如下：

相当于让所有弱分类器投票，再对投票结果按照弱分类器的错误率加权求和，将投票加权求

至今为止我们好像一直在讲分类器的训练，实际上Haar分类器是有两个体系的，训练的体系，和检测的体系。训练的部分大致都提到了，还剩下最后一部分就是对筛选式级联分类器的训练。我们看到了通过AdaBoost算法辛苦的训练出了强分类器，然而在现实的人脸检测中，只靠一个强分类器还是难以保证检测的正确率，这个时候，需要一个豪华的阵容，训练出多个强分类器将它们强强联手，最终形成正确率很高的级联分类器这就是我们最终的目标Haar分类器。

那么训练级联分类器的目的就是为了检测的时候，更加准确，这涉及到Haar分类器的另一个体系，检测体系，检测体系是以现实中的一幅大图片作为输入，然后对图片中进行多区域，多尺度的检测，所谓多区域，是要对图片划分多块，对每个块进行检测，由于训练的时候用的照片一般都是20*20左右的小图片，所以对于大的人脸，还需要进行多尺度的检测，多尺度检测机制一般有两种策略，一种是不改变搜索窗口的大小，而不断缩放图片，这种方法显然需要对每个缩放后的图片进行区域特征值的运算，效率不高，而另一种方法，是不断初始化搜索窗口size为训练时的图片大小，不断扩大搜索窗口，进行搜索，解决了第一种方法的弱势。在区域放大的过程中会出现同一个人脸被多次检测，这需要进行区域的合并，这里不作探讨。

无论哪一种搜索方法，都会为输入图片输出大量的子窗口图像，这些子窗口图像经过筛选式级联分类器会不断地被每一个节点筛选，抛弃或通过。

它的结构如图所示。

我想你一定觉得很熟悉，这个结构不是很像一个简单的决策树么。

在代码中，它的结构如下：

1/* internal tree cascade classifier node */

2 typedef struct CvTreeCascadeNode

3 {

4 CvStageHaarClassifier* stage;

5struct CvTreeCascadeNode* next;

6struct CvTreeCascadeNode* child;

7struct CvTreeCascadeNode* parent;

8struct CvTreeCascadeNode* next_same_level;

9struct CvTreeCascadeNode* child_eval;

10int idx;

11int leaf;

12 } CvTreeCascadeNode;

13/* internal tree cascade classifier */

14 typedef struct CvTreeCascadeClassifier

15 {

16 CV_INT_HAAR_CLASSIFIER_FIELDS()

17 CvTreeCascadeNode* root; /* root of the tree */

18 CvTreeCascadeNode* root_eval; /* root node for the filtering */ 19int next_idx;

20 } CvTreeCascadeClassifier;

级联强分类器的策略是，将若干个强分类器由简单到复杂排列，希望经过训练使每个强分类器都有较高检测率，而误识率可以放低，比如几乎99%的人脸可以通过，但50%的非人脸也可以通过，这样如果有20个强分类器级联，那么他们的总识别率为0.99^20=98%，错误接受率也仅为0.5^20=0.0001%。这样的效果就可以满足现实的需要了，但是如何使每个强分类器都具有较高检测率呢，为什么单个的强分类器不可以同时具有较高检测率和较低误识率呢？

下面我们讲讲级联分类器的训练。（主要参考了论文《基于Adaboost的人脸检测方法及眼睛定位算法研究》）

设K是一个级联检测器的层数，D是该级联分类器的检测率，F是该级联分类器的误识率，d i是第i层强分类器的检测率，f i是第i层强分类器的误识率。如果要训练一个级联分类器达到给定的F值和D值，只需要训练出每层的d值和f值，这样：

d^K = D,f^K = F

级联分类器的要点就是如何训练每层强分类器的d值和f值达到指定要求。

AdaBoost训练出来的强分类器一般具有较小的误识率，但检测率并不很高，一般情况下，高检测率会导致高误识率，这是强分类阈值的划分导致的，要提高强分类器的检测率既要降低阈值，要降低强分类器的误识率就要提高阈值，这是个矛盾的事情。据参考论文的实验结果，增加分类器个数可以在提高强分类器检测率的同时降低误识率，所以级联分类器在训练时要考虑如下平衡，一是弱分类器的个数和计算时间的平衡，二是强分类器检测率和误识率之间的平衡。具体训练方法如下,我用伪码的形式给出：

1）设定每层最小要达到的检测率d，最大误识率f，最终级联分类器的误识率Ft；

2）P=人脸训练样本，N=非人脸训练样本，D0=1.0，F0=1.0；

3）i=0；

4）for : F i>Ft

●?++i;

●?n i=0;F i=F i-1;

●?for : F i>f*F i-1

??++n i;

??利用AdaBoost算法在P和N上训练具有n i个弱分类器的强分类器;

??衡量当前级联分类器的检测率D i和误识率F i;

??for : d i

?降低第i层的强分类器阈值;

?衡量当前级联分类器的检测率D i和误识率F i;

??N = Φ;

??利用当前的级联分类器检测非人脸图像，将误识的图像放入N;

的值ii(i,j)是原图像(i,j)左上角方向所有像素的和：示。

AdaBoost算法的训练过程

AdaBoost算法的训练过程 每个Haar特征对应看一个弱分类器，但并不是任何一个Haar特征都能较好的描述人脸灰度分布的某一特点，如何从大量的Haar特征中挑选出最优的Haar特征并制作成分类器用于人脸检测，这是AdaBoost算法训练过程所要解决的关键问题。 Paul Viola和Michael Jones于2001年将Adaboost算法应用于人脸检测中,其基本思想是针对不同的训练集训练同一个分类器（弱分类器），然后把这些不同训练集上的得到的分类器联合起来，构成一个最终的强分类器。Adaboost 算法中不同的训练集是通过调整每个样本对应的权重来实现的。开始时，每个样本对应的权重是相同的，对于h1 分类错误的样本，加大其对应的权重；而对于分类正确的样本，降低其权重，这样分错的样本就被突出出来，从而得到一个新的样本分布U2 。在新的样本分布下，再次对弱分类器进行训练，得到弱分类器h2 。依次类推，经过T 次循环，得到T 个弱分类器，把这T 个弱分类器按一定的权重叠加（boost）起来，得到最终想要的强分类器。 训练系统总体框架，由“ 训练部分”和“ 补充部分”构成。依据系统框架，本文的训练系统可分为以下几个模块: (1)以样本集为输入，在给定的矩形特征原型下，计算并获得矩形特征集; (2)以特征集为输入，根据给定的弱学习算法，确定闽值，将特征与弱分类器一一对应，获得弱分类器集; (3)以弱分类器集为输入，在训练检出率和误判率限制下，使用A d a B o o s t 算法 挑选最优的弱分类器构成强分类器; (4)以强分类器集为输入，将其组合为级联分类器; (5)以非人脸图片集为输入，组合强分类器为临时的级联分类器，筛选并补充非人脸样本。

AdaBoost人脸检测原理

AdaBoost人脸检测原理 对人脸检测的研究最初可以追溯到 20 世纪 70 年代，早期的研究主要致力于模板匹配、子空间方法，变形模板匹配等。近期人脸检测的研究主要集中在基于数据驱动的学习方法，如统计模型方法，神经网络学习方法，统计知识理论和支持向量机方法，基于马尔可夫随机域的方法，以及基于肤色的人脸检测。目前在实际中应用的人脸检测方法多为基于 Adaboost 学习算法的方法。 Viola人脸检测方法是一种基于积分图、级联检测器和AdaBoost 算法的方法，方法框架可以分为以下三大部分: 第一部分，使用Harr-like特征表示人脸，使用“积分图”实现特征数值的快速计算; 第二部分，使用Adaboost算法挑选出一些最能代表人脸的矩形特征( 弱分类器)，按照加权投票的方式将弱分类器构造为一个强分类器; 第三部分，将训练得到的若干强分类器串联组成一个级联结构的层叠分类器，级联结构能有效地提高分类器的检测速度。 Adaboost 算法是一种用来分类的方法，它的基本原理就是“三个臭皮匠，顶个诸葛亮”。它把一些比较弱的分类方法合在一起，组合出新的很强的分类方法。例如下图中, 需要用一些线段把红色的球与深蓝色的球分开，然而如果仅仅画一条线的话，是分不开的。 a b c d 使用Adaboost算法来进行划分的话，先画出一条错误率最小的线段如图 1 ，但是左下脚的深蓝色球被错误划分到红色区域，因此加重被错误球的权重，再下一次划分时，将更加考虑那些权重大的球，如 c 所示，最终得到了一个准确的划分，如下图所示。

人脸检测的目的就是从图片中找出所有包含人脸的子窗口，将人脸的子窗口与非人脸的子窗口分开。大致步骤如下： (1)在一个 20*20 的图片提取一些简单的特征（称为Harr特征），如下图所示。 它的计算方法就是将白色区域内的像素和减去黑色区域，因此在人脸与非人脸图片的相同位置上，值的大小是不一样的，这些特征可以用来区分人脸和分人脸。 (2)目前的方法是使用数千张切割好的人脸图片，和上万张背景图片作为训练样本。训练图片一般归一化到 20*20 的大小。在这样大小的图片中，可供使用的haar特征数在1万个左右，然后通过机器学习算法-adaboost算法挑选数千个有效的haar特征来组成人脸检测器。 (3)学习算法训练出一个人脸检测器后，便可以在各个场合使用了。使用时，将图像按比例依次缩放，然后在缩放后的图片的 20*20 的子窗口依次判别是人脸还是非人脸。

adaboost算法原理

聚类和分类的区别是什么？一般对已知物体类别总数的识别方式我们称之为分类，并且训练的数据是有标签的，比如已经明确指定了是人脸还是非人脸，这是一种有监督学习。也存在可以处理类别总数不确定的方法或者训练的数据是没有标签的，这就是聚类，不需要学习阶段中关于物体类别的信息，是一种无监督学习。 Haar分类器实际上是Boosting算法的一个应用，Haar分类器用到了Boosting算法中的AdaBoost算法，只是把AdaBoost算法训练出的强分类器进行了级联，并且在底层的特征提取中采用了高效率的矩形特征和积分图方法。 在2001年，Viola和Jones两位大牛发表了经典的《Rapid Object Detection using a Boosted Cascade of Simple Features》【1】和《Robust Real-Time Face Detection》【2】，在AdaBoost 算法的基础上，使用Haar-like小波特征和积分图方法进行人脸检测，他俩不是最早使用提出小波特征的，但是他们设计了针对人脸检测更有效的特征，并对AdaBoost训练出的强分类器进行级联。这可以说是人脸检测史上里程碑式的一笔了，也因此当时提出的这个算法被称为Viola-Jones检测器。又过了一段时间，Rainer Lienhart和Jochen Maydt两位大牛将这个检测器进行了扩展《An Extended Set of Haar-like Features for Rapid Object Detection》【3】，最终形成了OpenCV现在的Haar分类器。 Haar分类器= Haar-like特征+ 积分图方法+ AdaBoost + 级联； Haar分类器算法的要点如下： ①使用Haar-like特征做检测。 ②使用积分图（Integral Image）对Haar-like特征求值进行加速。 ③使用AdaBoost算法训练区分人脸和非人脸的强分类器。 ④使用筛选式级联把强分类器级联到一起，提高准确率。 1.Haar-like特征你是何方神圣 Haar-like特征，那么我先说下什么是特征，我把它放在下面的情景中来描述，假设在人脸检测时我们需要有这么一个子窗口在待检测的图片窗口中不断的移位滑动，子窗口每到一个位置，就会计算出该区域的特征，然后用我们训练好的级联分类器对该特征进行筛选，一旦该特征通过了所有强分类器的筛选，则判定该区域为人脸。 所谓的特征不就是一堆堆带条纹的矩形么，到底是干什么用的？我这样给出解释，将上面的任意一个矩形放到人脸区域上，然后，将白色区域的像素和减去黑色区域的像素和，得到的值我们暂且称之为人脸特征值，如果你把这个矩形放到一个非人脸区域，那么计算出的特征值应该和人脸特征值是不一样的，而且越不一样越好，所以这些方块的目的就是把人脸特征量化，以区分人脸和非人脸。 为了增加区分度，可以对多个矩形特征计算得到一个区分度更大的特征值，那么什么样的矩形特征怎么样的组合到一块可以更好的区分出人脸和非人脸呢，这就是AdaBoost算法要做的事了。这里我们先放下积分图这个概念不管，为了让我们的思路连贯，我直接开始介绍AdaBoost算法。

Adaboost算法流程和证明

Adaboost算法 1、Adaboost算法简介 Adaboost算法是Freund和Schapire根据在线分配算法提出的，他们详细分析了Adaboost算法错误率的上界，以及为了使强分类器达到错误率，算法所需要的最多迭代次数等相关问题。与Boosting算法不同的是，Adaboost算法不需要预先知道弱学习算法学习正确率的下限即弱分类器的误差，并且最后得到的强分类器的分类精度依赖于所有弱分类器的分类精度，这样可以深入挖掘弱分类器算法的能力。 2、Adaboost 算法基本原理 Adaboost是一种迭代算法，其核心思想是针对同一个训练集训练不同的分类器(弱分类器)，然后把这些弱分类器集合起来，构成一个更强的最终分类器(强分类器)。其算法本身是通过改变数据分布来实现的，它根据每次训练集之中每个样本的分类是否正确，以及上次的总体分类的准确率，来确定每个样本的权值。将修改过权值的新数据集送给下层分类器进行训练，最后将每次训练得到的分类器最后融合起来，作为最后的决策分类器。使用Adaboost分类器可以排除一些不必要的训练数据特征，并将关键放在关键的训练数据上面。 Adaboost算法中不同的训练集是通过调整每个样本对应的权重来实现的。开始时，每个样本对应的权重是相同的，即其中n为样本个数，在此样本分布下训练出一弱分类器。对于分类错误的样本，加大

其对应的权重；而对于分类正确的样本，降低其权重，这样分错的样本就被突出出来，从而得到一个新的样本分布。在新的样本分布下，再次对弱分类器进行训练，得到弱分类器。依次类推，经过T 次循环，得到T 个弱分类器，把这T 个弱分类器按一定的权重叠加(boost)起来，得到最终想要的强分类器。 Adaboost 算法的具体步骤如下： 设输入的n 个训练样本为：1122{(,),(,),,(,)}n n x y x y x y L ,其中i x 是输入的训练样本，{0,1}i y ∈分别表示正样本和负样本，其中正样本数为l ，负样本数m 。n l m =+，具体步骤如下： ⑴初始化每个样本的权重,()i w i D i ∈； ⑵对每个1,,t T =L (T 为弱分类器的个数)： ①把权重归一化为一个概率分布 ,,,1 t i t i n t j j w w w == ∑ ②对每个特征f ，训练一个弱分类器j h 计算对应所有特征的弱分类器的加权错误率 1()()n j t i j i i i w x h x y ε==≠∑ ③选取最佳的弱分类器t h (拥有最小错误率)：t ε ④按照这个最佳弱分类器，调整权重 11,,i t i t i t w w εβ-+= 其中0i ε=表示被正确地分类，1i ε=，表示被错误地分类

AdaBoost算法简介

Adaboost 算法 1、AdaBoost算法简介 AdaBoost算法是Freund和Schapire根据在线分配算法提出的，他们详细分析了AdaBoost算法错误率的上界，以及为了使强分类器达到错误率，算法所需要的最多迭代次数等相关问题。与Boosting算法不同的是，adaBoost算法不需要预先知道弱学习算法学习正确率的下限即弱分类器的误差，并且最后得到的强分类器的分类精度依赖于所有弱分类器的分类精度，这样可以深入挖掘弱分类器算法的能力。 2、Adaboost 算法基本原理 Adaboost是一种迭代算法，其核心思想是针对同一个训练集训练不同的分类器(弱分类器)，然后把这些弱分类器集合起来，构成一个更强的最终分类器(强分类器)。其算法本身是通过改变数据分布来实现的，它根据每次训练集之中每个样本的分类是否正确，以及上次的总体分类的准确率，来确定每个样本的权值。将修改过权值的新数据集送给下层分类器进行训练，最后将每次训练得到的分类器最后融合起来，作为最后的决策分类器。使用Adaboost 分类器可以排除一些不必要的训练数据特征，并将关键放在关键的训练数据上面。 AdaBoost算法中不同的训练集是通过调整每个样本对应的权重来实现的。开始时，每个样本对应的权重是相同的，即其中n 为样本个数，在此样本分布下训练出一弱分类器。对于分类错误的样本，加大其对应的权重；而对于分类正确的样本，降低其权重，这样分错的样本就被突出出来，从而得到一个新的样本分布。在新的样本分布下，再次对弱分类器进行训练，得到弱分类器。依次类推，经过T 次循环，得到T 个弱分类器，把这T 个弱分类器按一定的权重叠加（boost）起来，得到最终想要的强分类器。 AdaBoost算法的具体步骤如下： 设输入的n个训练样本为:{(x1,y1)，(x2,y2)，......(xn,yn)}，其中xi是输入的训练样本，yi∈{0,1}分别表示正样本和负样本，其中正样本数为l，负样本数m。n=l+m，具体步骤如下： （1）初始化每个样本的权重w i,i∈D(i); (2)对每个t=1,..., T(T为弱分类器的个数) ①把权重归一化为一个概率分布 ②对每个特征f，训练一个弱分类器h j计算对应所有特征的弱分类器的加权错误率 ③选取最佳的弱分类器h t(拥有最小错误率)：εt ④按照这个最佳弱分类器，调整权重 其中εi =0表示被正确地分类，εi=1，表示被错误地分类

Adaboost算法多类问题Matlab实现

一种adaboost多类分类算法Matlab实现 一、adaboost算法简介 Adaboost算法的主要思想是给定一个训练集(x1,y1),…,(xm,ym),其中xi属于某个域或者实例空间X，yi=-1或者+1。初始化时Adaboost指定训练集上的分布为1/m,并按照该分布调用弱学习器对训练集上的分布，并按照该分布调用弱学习器对训练集进行训练，每次训练后，根据训练结果更新训练集上的分布，并按照新的样本分布进行训练。反复迭代T轮，最终得到一个估计序列h1,..,hT,每个估计都具有一定的权重，最终的估计H是采用权重投票方式获得。Adaboost算法的伪代码如图1所示。 图1、Adaboost算法 二、多类问题 从上面的流程可以看出，Adaboost算法是针对二类问题的。但是我们面对的问题很多都是不是简单的非0即1，而是多类问题。常见的就是解决方法，就是把多类问题转换成二类问题。用的比较多就是两种组合方法，OAA和OAO，我这里就是采用对这种方法的结合，实现adaboost算法对多类问题的分类。 目前需要对7类问题进行分类，依次编号：0、1、2、3、4、5、6。 特征向量28个。 样本总数840个； OAA分类器的个数7 个 OAO分类器的个数7（7-1）/2 = 21个。 弱分类器的个数K= 10； 弱分类用BP神经网络 算法的思路： Step1、把数据分成训练集和测试集 Step 2、训练OAA、OAO分类器； Step3、保存相应的分类器和投票权重； Step4、测试样本，预测所以OAA分类器的权重； Step5、选择OAA预测值中最大的两个 Step6、选用OAO分类器对选取预测权重最大的两个类进行预测； Step7、输出测试结果；

基于AdaBoost算法的人脸检测——赵楠 北京大学

北京大学 本科生毕业论文 基于AdaBoost 算法的人脸检测Face Detection Based on AdaBoost 姓名：赵楠 学号：00105029 院系：物理学院物理学系 指导老师：查红彬教授 导师单位：视觉与听觉信息处理国家重点实验室 信息科学技术学院智能科学系

北京大学本科生毕业论文 二○○五年六月 摘要 Abstract 人脸检测是人脸分析的首要环节，其处理的问题是确认图像（或影像）中是否存在人脸，如果存在则对人脸进行定位。人脸检测的应用领域相当广泛，是实现机器智能化的重要步骤之一。 AdaBoost 算法是1995 年提出的一种快速人脸检测算法，是人脸检测领域里程碑式的进步，这种算法根据弱学习的反馈，适应性地调整假设的错误率，使在效率不降低的情况下，检测正确率得到了很大的提高。 本论文第一章和第二章简述了人脸检测的一般情况，第三章对一些人脸检测的经典方法进行了说明。 第四章讲述了AdaBoost 算法的发展历史。从PCA 学习模型到弱学习和强学习相互关系的论证，再到Boosting 算法的最终提出，阐述了Ada ptive Boost ing 算法的发展脉络。 第五章对影响AdaBoost 人脸检测训练算法速度的至关重要的两方面：矩形特征和积分图的概念和理论进行了仔细的阐明。 第六章给出了AdaBoost 的算法，并深入探讨了其中的一些关键问题——弱学习器的构造、选取等问题。

最后一章，用编写的实现了AdaBoost 算法的FáDèt程序，给出了相应的人脸检测实验结果，并和Viola 等人的结果做了比较。 关键词Keywords AdaBoost 方法、人脸检测、Boosting 方法、PCA 学习模型、弱学习

Adaboost算法的MATLAB实现

Adaboost算法的MATLAB实现： clear all clc tr_n=200; %the population of the train set te_n=200; %the population of the test set weak_learner_n=20; %the population of the weak_learner tr_set=[1,5;2,3;3,2;4,6;4,7;5,9;6,5;6,7;8,5;8,8]; te_se=[1,5;2,3;3,2;4,6;4,7;5,9;6,5;6,7;8,5;8,8]; tr_labels=[2,2,1,1,2,2,1,2,1,1]; te_labels=[2,2,1,1,2,2,1,2,1,1]; figure; subplot(2,2,1); hold on;axis square; indices=tr_labels==1; plot(tr_set(indices,1),tr_set(indices,2),'b*'); indices=~indices; plot(tr_set(indices,1),tr_set(indices,2),'r*'); title('Training set'); subplot(2,2,2); hold on; axis square; indices=te_labels==1; plot(te_set(indices,1),te_set(indices,2),'b*')3 ; indices=~indices; plot(te_set(indices,1),te_set(indices,2),'r*'); title('Training set'); % Training and testing error rates tr_error=zeros(1,weak_learner_n); te_error=zeros(1,weak_learner_n); for i=1:weak_learner_n adaboost_model=adaboost_tr(@threshold_tr,@threshold_te,tr_set,tr_labels,i); [L_tr,hits_tr]=adaboost_te(adaboost_model,@threshold_te,te_set,te_labels); tr_error(i)=(tr_n-hits_tr)/tr_n; [L_te,hits_te]=adaboost_te(adaboost_model,@threshold_te,te_set,te_labels); te_error(i)=(te_n-hits_te)/te_n; end subplot(2,2,3); plot(1:weak_learner_n,tr_error); axis([1,weak_learner_n,0,1]); title('Training Error');

Adaboost算法多类问题Matlab实现知识讲解

A d a b o o s t算法多类问题M a t l a b实现

一种adaboost多类分类算法Matlab实现 一、adaboost算法简介 Adaboost算法的主要思想是给定一个训练集(x1,y1),…,(xm,ym),其中xi属于某个域或者实例空间X，yi=-1或者+1。初始化时Adaboost指定训练集上的分布为1/m,并按照该分布调用弱学习器对训练集上的分布，并按照该分布调用弱学习器对训练集进行训练，每次训练后，根据训练结果更新训练集上的分布，并按照新的样本分布进行训练。反复迭代T轮，最终得到一个估计序列 h1,..,hT,每个估计都具有一定的权重，最终的估计H是采用权重投票方式获得。Adaboost算法的伪代码如图1所示。 图1、Adaboost算法 二、多类问题 从上面的流程可以看出，Adaboost算法是针对二类问题的。但是我们面对的问题很多都是不是简单的非0即1，而是多类问题。常见的就是解决方法，就是把多类问题转换成二类问题。用的比较多就是两种组合方法，OAA和OAO，我这里就是采用对这种方法的结合，实现adaboost算法对多类问题的分类。 目前需要对7类问题进行分类，依次编号：0、1、2、3、4、5、6。 特征向量 28个。 样本总数 840个； OAA分类器的个数 7 个 OAO分类器的个数 7（7-1）/2 = 21个。 弱分类器的个数 K= 10； 弱分类用BP神经网络 算法的思路： Step1、把数据分成训练集和测试集 Step 2、训练OAA、OAO分类器； Step3、保存相应的分类器和投票权重； Step4、测试样本，预测所以OAA分类器的权重； Step5、选择OAA预测值中最大的两个

Adaboost算法的前世今生

Adaboost算法的前世今生 转载▼ 标签： it Adaboost算法的前世今生 引言 众所周知，模式识别的方法可以按照参与识别特征的属性来区分，可以分为两大类：一、使用定量特征（可度量）如物体长度、宽度等，来描述的各种模式，这一类主要是指决策理论，有匹配、统计、神经网络等方法；二、使用定性特征如特征结构、排列顺序等，来描绘的各种模式，这一类主要是指结构判别，主要有串和树的匹配等方法。 模式识别的完整的流程顺序是：传感器——分割组织——特征提取——分类器——后处理。其中分类器的设计部分，可以使用的理论有很多，目前主要包括：基于统计理论的方法（贝叶斯理论）、线性判别函数、神经网络的方法、随机方法（对于复杂的问题）、非度量方法（定性结构特征） 分类器得到的模型不仅要很好拟合输入数据，还要能够正确地预测未知样本的类标号。因此，训练算法的主要目标就是要建立具有很好的泛化能力模型，即建立能够准确地预测未知样本类标号的模型。 通常我们用“方差”和“偏差”来测量学习算法与给定分类问题的“匹配”和“校准”程度。“偏差”度量的是匹配的“准确性”和“质量”：一个高的偏差意味着一个坏的匹配，“方差”度量的是匹配的“精确性”和“特定性”：一个高的方差意味着一个弱的匹配。 研究表明，使用重采样技术可以提高分类器的准确率，而boosting算法就是涉及分类器设计中的重采样技术。其思想内涵在于：从给定的数据集中抽取多个数据子集，使得有可能计算任意统计量的值及其范围。 说道boosting，不得不说Arcing（adaptive reweighting and combining）自适应的权值重置和组合：重新使用和选择数据，以期达到改善分类器性能的目的。最简单的arcing版本就是bagging算法。 Bagging一个多分类器系统 bagging算法的基本思想: 给定一个弱学习算法，和一个训练集；单个弱学习算法准确率不高；将该学习算法使用多次，得出预测函数序列，进行投票，最后结果准确率将得到提高。 步骤1：从大小为n的原始数据集D中，分别独立随机的抽取n’个数据（n’

机器学习十大算法：AdaBoost

Chapter7 AdaBoost Zhi-Hua Zhou and Yang Yu Contents 7.1Introduction (127) 7.2The Algorithm (128) 7.2.1Notations (128) 7.2.2A General Boosting Procedure (129) 7.2.3The AdaBoost Algorithm (130) 7.3Illustrative Examples (133) 7.3.1Solving XOR Problem (133) 7.3.2Performance on Real Data (134) 7.4Real Application (136) 7.5Advanced Topics (138) 7.5.1Theoretical Issues (138) 7.5.2Multiclass AdaBoost (142) 7.5.3Other Advanced Topics (145) 7.6Software Implementations (145) 7.7Exercises (146) References (147) 7.1Introduction Generalization ability,which characterizes how well the result learned from a given training data set can be applied to unseen new data,is the most central concept in machine learning.Researchers have devoted tremendous efforts to the pursuit of tech-niques that could lead to a learning system with strong generalization ability.One of the most successful paradigms is ensemble learning[32].In contrast to ordinary machine learning approaches which try to generate one learner from training data, ensemble methods try to construct a set of base learners and combine them.Base learners are usually generated from training data by a base learning algorithm which can be a decision tree,a neural network,or other kinds of machine learning algorithms. Just like“many hands make light work,”the generalization ability of an ensemble is usually signi?cantly better than that of a single learner.Actually,ensemble meth-ods are appealing mainly because they are able to boost weak learners,which are 127

adaboost算法matlab实现.doc

clear all clc tr_n=200; %the population of the train set te_n=200; %the population of the test set weak_learner_n=20; %the population of the weak_learner tr_set=[1,5;2,3;3,2;4,6;4,7;5,9;6,5;6,7;8,5;8,8]; te_se=[1,5;2,3;3,2;4,6;4,7;5,9;6,5;6,7;8,5;8,8]; tr_labels=[2,2,1,1,2,2,1,2,1,1]; te_labels=[2,2,1,1,2,2,1,2,1,1]; figure; subplot(2,2,1); hold on;axis square; indices=tr_labels==1; plot(tr_set(indices,1),tr_set(indices,2),'b*'); indices=~indices; plot(tr_set(indices,1),tr_set(indices,2),'r*'); title('Training set'); subplot(2,2,2); hold on;axis square; indices=te_labels==1; plot(te_set(indices,1),te_set(indices,2),'b*')3 ; indices=~indices; plot(te_set(indices,1),te_set(indices,2),'r*'); title('Training set'); % Training and testing error rates tr_error=zeros(1,weak_learner_n); te_error=zeros(1,weak_learner_n); for i=1:weak_learner_n adaboost_model=adaboost_tr(@threshold_tr,@threshold_te,tr_set,tr_l abels,i); 第 1 页 无标题 [L_tr,hits_tr]=adaboost_te(adaboost_model,@threshold_te,te_set,te_ labels); tr_error(i)=(tr_n-hits_tr)/tr_n; [L_te,hits_te]=adaboost_te(adaboost_model,@threshold_te,te_set,te_ labels); te_error(i)=(te_n-hits_te)/te_n; end subplot(2,2,3); plot(1:weak_learner_n,tr_error); axis([1,weak_learner_n,0,1]); title('Training Error');