好贷网好贷款

adaboost学习(二)

发布时间:2016-12-3 8:23:17 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"adaboost学习(二)",主要涉及到adaboost学习(二)方面的内容,对于adaboost学习(二)感兴趣的同学可以参考一下。

引言 众所周知,模式识别的方法可以按照参与识别特征的属性来区分,可以分为两大类:一、使用定量特征(可度量)如物体长度、宽度等,来描述的各种模式,这一类主要是指决策理论,有匹配、统计、神经网络等方法;二、使用定性特征如特征结构、排列顺序等,来描绘的各种模式,这一类主要是指结构判别,主要有串和树的匹配等方法。 模式识别的完整的流程顺序是:传感器——分割组织——特征提取——分类器——后处理。其中分类器的设计部分,可以使用的理论有很多,目前主要包括:基于统计理论的方法(贝叶斯理论)、线性判别函数、神经网络的方法、随机方法(对于复杂的问题)、非度量方法(定性结构特征) 分类器得到的模型不仅要很好拟合输入数据,还要能够正确地预测未知样本的类标号。因此,训练算法的主要目标就是要建立具有很好的泛化能力模型,即建立能够准确地预测未知样本类标号的模型。 通常我们用“方差”和“偏差”来测量学习算法与给定分类问题的“匹配”和“校准”程度。“偏差”度量的是匹配的“准确性”和“质量”:一个高的偏差意味着一个坏的匹配,“方差”度量的是匹配的“精确性”和“特定性”:一个高的方差意味着一个弱的匹配。 研究表明,使用重采样技术可以提高分类器的准确率,而boosting算法就是涉及分类器设计中的重采样技术。其思想内涵在于:从给定的数据集中抽取多个数据子集,使得有可能计算任意统计量的值及其范围。 说道boosting,不得不说Arcing(adaptive reweighting and combining)自适应的权值重置和组合:重新使用和选择数据,以期达到改善分类器性能的目的。最简单的arcing版本就是bagging算法。 Bagging一个多分类器系统 bagging算法的基本思想: 给定一个弱学习算法,和一个训练集;单个弱学习算法准确率不高;将该学习算法使用多次,得出预测函数序列,进行投票,最后结果准确率将得到提高。 步骤1:从大小为n的原始数据集D中,分别独立随机的抽取n’个数据(n’),形成自助数据集,将这个过程独立重复多次,直到产生很多独立的自助数据集。 步骤2:每一个自助数据集都被独立的用于训练一个“分量分类器”。 步骤3、最终的分类判决由这些“分量分类器”各自的判决结果投票决定。 Bagging算法是第一个多分类器系统,后面还有(组合分类器系统)。 算法: For t = 1, 2, …, T Do 从数据集S中取样(放回选样) 训练得到模型Ht 对未知样本X分类时,每个模型Ht都得出一个分类,得票最高的即为未知样本X的分类,也 可通过得票的平均值用于连续值的预测 。   Bagging和boosting的区别   训练集: 预测函数 准确性 使用要求 Bagging 随机选择,各轮训练集相互独立 没有权重;可以并行生成 在有些数据集中,boosting会引起退化 要求“不稳定”的分类方法 Boosting 各轮训练集并不独立,它的选择与前轮的学习结果有关 有权重;只能顺序生成 在大多数数据集中,boosting的准确性比bagging高 要求“不稳定”的分类方法 训练集的小变动能够使得分类模型显著变动 Bagging是一个纯粹的降低相关度的方法,如果树的节点具有很高的相关性,bagging就会有好的结果。早期的AdaBoost在第二步的时候采用重采样方法,即使某些样本权重增加。这种方法与bagging存在某种关联。它也是Boost的成功之处中降低相关度方面的重要部分。 AdaBoost在第二步中如果使用加权的tree-growing算法,而不是重采样算法,效果会更好。可以使用stumps作为弱分类器 最初的boosting算法 1989年Kearns and Valiant研究了PAC学习模型中弱学习算法和强学习算法两者间的等价问题,即任意给定仅仅比随机猜测稍好(准确率大于0.5)的弱学习算法,是否可以被提升为强学习算法?若两者等价,则我们只需寻找一个比随机猜测稍好的弱学习算法,然后将其提升为强学习算法,从而不必费很大力气去直接寻找强学习算法。就此问题,Schapire于1990年首次给出了肯定的答案。他主持这样一个观点:任一弱学习算法可以通过加强提升到一个任意正确率的强学习算法,并通过构造一种多项式级的算法来实现这一加强过程,这就是最初的Boosting算法的原型。 主要思想是,根据已有的训练样本集设计一个分类器,要求其准确率要比平均性能好,然后依次顺序加入多个分量分类器系统,最后形成一个总体分类器。 以一个二类问题举例。 步骤1:从大小为n的原始样本集D中随机选取n1个样本点(不放回),组成样本集D1。根据D1训练出第一个分类器C1。 步骤2:构造第二个样本集D2,它是根据C1最富信息的那些样本点组成的。在最后产生的D2集合中将有一半的样本被C1正确分类,而另一半的样本被C1错误分类。 步骤3:继续构造第三个样本集D3,方法:在D中剩余的样本中选取样本点,并且用C1和C2进行分类,如果C1和C2判决结果不同,那么就把样本加入D3,否则就忽略这个样本。然后用D3训练新分类器C3。 步骤4:用这3个分类器对新样本x进行分类,如果C1和C2的判决结果相同,则表为一类,不同则表为另一类。 Boosting方法有许多不同的变形,其中最流行的一种就是adaboost。这个名词是“adaptive boosting”的缩写。这个方法允许设计者不断的加入新的“弱分类器”,直到达到某个预定的最小错误率。 1995年Freund and Schapire提出AdaBoost算法。 1996年Yoav Freund在Experiments with a New Boosting Algorithm中提出了AdaBoost.M1和AdaBoost.M2两种算法。其中,AdaBoost.M1是我们通常所说的Discrete AdaBoost:而AdaBoost.M2是M1的泛化形式。该文的一个结论是:当弱分类器算法使用简单的分类方法时,boosting的效果明显地统一地比bagging要好。当弱分类器算法使用C4.5时,boosting比bagging较好,但是没有前者的比较来得明显。 AdaBoost.M1 Discrete AdaBoost: 初始版本 1.获得一组样本(X)和它的分类(Y)和一个分类器(weaklearn). 2.赋予平均的权值分布D(i) 进入循环:T次 1. 赋予弱分类器权值D(i),使用弱分类器获得样本(X)到分类(Y)上的一个映射.(就是把某个X归到某个Y类中去) 2. 计算这个映射的误差e,e=各个归类错误的样本权值之和.如果e>1/2那么弱分类器训练失败,跳出循环, 训练结束(这在二值检测中是不会发生的,而多值的情况就要看分类器够不够强健了) 3. 设beta B = e / ( 1 - e ).用于调整权值.因为e<1/2.因此0 4. 如果某样本分类正确,该样本的权值就乘以B让权值变小;如果分类错误,就让该样本的权值乘以B^-1或者不变,这样就让分类正确的样本权值降低,分类错误的样本权值升高,加强了对较难分类样本的分类能力 5. 权值均衡化 循环结束 1. 最终的分类器是,当一个X进入时,遍历所有Y,寻找使(h(x)=y的情况下,log(1/B)之和)最大者即是输出分类y   书上版本 具体算法: 每个样本都赋予一个权重,T次迭代,每次迭代后,对分类错误的样本加大权重,使得下一次的迭代更加关注这些样本。 输入:(X1,Y1), (X2,Y2),…(Xn,Yn) Xi∈X, Yi∈Y={+1,-1} 初始化权值:D1(i)=1/n For t=1,…,T 在Dt下训练, 得到弱的假设ht: X->{-1,+1}, 错误率:Εt=ΣDt(i) [ht(Xi)≠Yi] 选择αt=1/2 ln ( (1- Εt)/ Εt ), 更改权值: if ht(Xi)≠Yi , Dt+1(i)=Dt(i)* eαt /Zt if ht(Xi)=Yi , Dt+1(i)=Dt(i)* e -αt /Zt 输出:H(X)=sign( ∑ αtht(X) )   带图版本(程序版本): 初始赋予每个样本相等的权重1/N ; For t = 1, 2, …, T Do 学习得到分类法Ct; 计算该分类法的错误率Et Et=所有被错误分类的样本的权重和; βt= Et/(1 - Et) 根据错误率更新样本的权重; 正确分类的样本: Wnew= Wold* βt 错误分类的样本: Wnew= Wold 调整使得权重和为1; 每个分类法Ct的投票价值为log [ 1 / βt ] 转自: http://210.43.24.222/chy/3sbase/news/?538.html

上一篇:MINA2.0用户手册中文版--第三章 第三节 服务端接口IoAcceptor
下一篇:sprintf 与 strchr

相关文章

相关评论