《b非线性分类器》PPT课件.ppt

4.3近邻法,4.3.1最近邻法4.3.2K-近邻法及错误率分析4.3.3减少计算量和存储量的方法,问题的提出及解决,前面利用每一类的“代表点”设计分段线性分类器是最简单而直接的设计方法,这类方法的缺点是所选择的“代表点”不一定能很好的代表各个类,其结果是使所设计分类器的错误率增加.,需要用其他方法来降低错误率,本章讨论的方法是将各类中全部样本都作为“代表点”的情况,这样的决策方法称为近邻法.下面我们首先详细介绍一般的近邻法,然后讨论几种改进的方法.,4.3.1最近邻法,1最近邻决策规则,假定有c个类别1,2,c的模式识别问题,每类有标明类别的样本Ni个,i=1,2,c.我们可以规定i类的判别函数为gi(x)=min|xxki|,k=1,2,Nik其中xki的下标i表示i类,k表示i类Ni个样本中的第k个.,则决策规则可以写为:,若gj(x)=mingi(x),i=1,2,ci,则决策xj,最近邻法的直观解释相当简单,就是说对未知样本x,我们只要比较x与已知样本数为N,类别为c的样本群之间的欧氏距离,并决策x与离它最近的样本同类.,如图:假设有N个样本,被分为3类.,x,则有:x3,对于未知样本x,用最近邻法进行分类.,2最近邻法的错误率分析,设N个样本下的平均错误率为PN(e),且样本x的最近邻为x则,PN(e)=PN(e|x)P(x)d(x)=PN(e|x,x)p(x|x)dxp(x)d(x),我们定义最近邻法的渐进平均错误率P为当N时,PN(e)的极限,则有cP=limPN(e)=1-P2(i|x)p(x)dxNi=1,此时我们可以证明以下关系P*PP*(2-c/(c-1)P*)其中P*为贝叶斯错误率,c为类数,最近邻法的错误率显然大于或等于贝叶斯错误率P*,但在某些特定情况下,可以等于贝叶斯错误率.,均有P=P*,根据贝叶斯条件错误率,我们可得以下式子:c1-P2(i|x)2p*(e|x)-c/(c-1)p*(e|x)2i=1(P*)2p*(e|x)2p(x)dx,根据以上结果我们可得Pp*2-c/(c-1)p*,下面用图形来说明最邻近法错误率上下界与贝叶斯错误率的关系,P(c-1)/c,(c-1)/cp*,P=p*,P=p*2-c/(c-1)p*,4.3.2k-近邻法,k-近邻法是最近邻法的一个推广.这个方法就是取未知样本x的k个近邻,看这k个近邻多数属于哪一类,就把x归为哪一类.,在N个样本中,若k1,k2,kc分别是k个近邻中属于1,2,c的样本数,则我们可以定义判别函数为:,决策规则为:若gj(x)=maxki,则决策xj,gi(x)=ki,i=1,2,c,1.k-近邻法决策规则,2.k-近邻法的错误率分析,将近邻法推广到k近邻法的一个重要目的就是可以降低决策的错误率,下面我们先给出一个图形来直观说明一下,x,由最近邻法,可得x1结论,但似乎不正确,贝叶斯决策面,用k近邻法决策,x,由于k2k1,所以x2,这也和贝叶斯决策面决策的相同.,k=k1+k2k2k1,根据最近邻法错误率分析,当样本数N趋于时,P=limPN(e)N则有p*=p=p*2-c/(c-1),下面我们给出当k递增的时候,k-邻近法的错误率p与贝叶斯错误率p*的关系,K=1,K=3,K=7,当k=1时,k-近邻法的错误率对应于最近邻法的错误率.当k增加时,上限逐渐靠近下限-贝叶斯错误率p*,当k趋于无穷时,上下限碰在一起,从而k-近邻法趋于最优.,近邻法有方法简单的优点,且错误率在贝叶斯错误率p*和两倍贝叶斯错误率2p*之间,正是近邻法这种优良性质,使它成为模式分类的重要方法之一.,1需要将所有样本存入计算机中,每次决策都要计算识别样本x与全部训练样本之间的距离并进行比较,因此使得存储量和计算量都很大.,2虽然在所有情况下,对未知样本x都可以进行决策,但当错误代价很大时,会产生较大的风险.,3上述分析都是渐进的,就是说要求样本数N趋于无穷,这是在任何实际场合都无法实现的.,?如何解决,但是近邻法还存在下列问题,4.3.3减少计算量和存储量的方法,近邻法的一个缺点就是计算量大,未知样本x要逐个与全体样本X中每个样本计算欧氏距离.为了减少计算的次数,也就是不必计算x到样本集X中每个样本xi的距离,只需要计算其中一部分的距离就可以找出最近邻,于是引出了快速搜索近邻法.,快速近邻法的基本考虑是将样本分级分成一些不相交的子集,并且在子集的基础上进行搜索.,1快速搜索算法法,几种算法:快速搜索算法法,剪辑近邻法,压缩近邻法.,1)最近邻的情况,快速搜索算法分成两个阶段,第一阶段是将样本集X分级分解,形成树结构.第二个阶段用搜索算法找出待识样本的最近邻.,第一阶段:样本集X分级分解,首先将样本集X分成l个子集,每个子集再分成l个子集,一共将样本集分若干次,依次下去可以形成一个树结构.每个结点上对应一群样本.我们用p表示这样的一个结点.,下面以l=2给出树状结构图,k=0k=1k=2,PrpNp,N0,6r6N6,5r5N5,4r4N4,3r3N3,1,2,并用下列参数表示p结点对应的样本子集:Xp:结点p对应的样本子集Np:Xp中的样本数p:样本子集Xp中的样本均值rp=maxD(xi,p):从p到xiXp的最大距离xiXp,第二阶段:搜索在给出算法之前,先引出两个规则,利用它们可以检验未知样本x的最近邻是否在Xp中,规则1:如果存在B+rpD(x,p)则xiXp不可能是x的最近邻.其中B是在算法执行过程中,对于已涉及到的那些样本集Xp中样本到x的最近距离.初始B可置为,以后的B在算法中求得.,下面给出图形来说明:,p,D(x,p),x,x现在的近邻,B,我们可以利用这个规则,不必全部计算x到Xp中每个样本xi的距离,许多结点p和所对应的样本集Xp就可以被去掉,从而减少了计算量.,为避免对最终结点中的全部样本计算D(x,xi)距离,还需要下面的规则2,xi,BD(x,p)rpD(x,xi),规则2:如果B+D(xi,p)D(x,p)其中xiXp,则xi不是x的最近邻.由于D(xi,p)在计算rp中已用到,并且被存入计算机中,所以不需要重新计算.,下面给出树搜索算法,并且结合前面给出的树结构图来分析.,树搜索算法,步骤1置B=,k=0,p=0.,步骤2将当前结点的所有直接后继结点放入一个目录表中,并对这些结点计算D(x,Mp).,步骤3对步骤2中的每个结点p,根据规则1,如果有B+rpD(xi,p)+B则xi不是x的最近邻,从而不计算D(x,xi),否则计算D(x,xi).若D(x,xi)B置NN=i和B=D(x,xi).在当前执行结点中所有xi被检验之后,转步骤3.,当算法结束时,输出x的最近邻xNN和x与xNN的距离D(x,xNN)=B,2)将算法扩展到k-近邻法的情况.,这只需要对前述算法做部分修改就可以完成.,首先对B做修正,使它在现在的程序中是x到第k个近邻的距离.,然后当在步骤6中每计算一个距离之后,就与当前执行近邻表中的k个近邻距离做比较,若这个新计算的距离小于近邻表中任何一个时,则从近邻表中去掉最大的一个.算法的其它部分与最近邻法相同.,+x,图中两类样本相互交错,2剪辑近邻法,将未知样本x用近邻法分类是不好处理的.,解决思路:,如果能够剪辑掉两类边界附近交错的一些样本,并使得剩下的样本形成两个好的聚类,而且每个聚类中的样本都属于同一类,它们的分界面十分接近贝叶斯决策面,那么可以提高利用近邻规则分类的性能.,下面介绍两种剪辑近邻法:1).两分剪辑近邻法2).重复剪辑近邻法,1)两分剪辑近邻法,在两分剪辑近邻法中,假定给定的样本集X被分成两个独立的样本集-考试集XT和参考集XR.在参考集中的样本完成参考任务,在考试集中完成考试任务,并且去掉考试中不合格的样本.将考试中保留的合格样本构成剪辑样本集,并利用该样本集对未知样本x利用近邻法作分类决策.,基本思路:,步骤1假定样本集X中的每个样本不是被用概率a分到考试集XT中,就是用概率1-a分到参考集XR中,步骤2利用参考集XR中的样本对考试集XT中的每个样本用近邻法进行分类决策,*x,步骤3剪辑掉考试集XT中被参考集XR利用最近邻法错分类的样本,然后将XT中剩余样本构成剪辑样本集XNTE.,*x,步骤4利用剪辑样本集XNTE和最近邻规则对未知样本x作分类决策.,剪辑近邻法的错误率分析,剪辑近邻法的条件错误率为PkE(e|x)=P(e|x)/21-Pk(e|x),由上式可见,剪辑近邻法的错误率总是小于等于没有剪辑的近邻法,即有PkE(e)P(e),尤其是在P(e)很小时,比如P(e)0.1,则可推知PkE(e)P(e)/2,由于没有剪辑的近邻法错误率P(e)的上界为2p*,因此经过近邻规则剪辑的近邻法错误率接近贝叶斯错误率P*,即PkE(e)P*,2)重复剪辑近邻法,重复剪辑近邻法是两分剪辑近邻法的扩展.只要样本数足够多,我们可以重复地执行剪辑程序,以进一步提高近邻法规则分类的性能.只是将前一步剪辑后的样本形成新的样本集,然后对其重新随机划分为考试集和参考集,这就有效的避免了划分子集的相互作用,从而保证了剪辑的独立性.,问题的提出:从上一节我们可以看到,剪辑的结果只是去掉了两类边界附近的样本,而靠近两类中心的样本几乎没有去掉.按照近邻规则,这些样本中的大多数对分类决策没有什么作用.因此在剪辑的基础上,再去掉一部分这样的样本则有利于进一步缩短计算时间和降低存储要求.一般称这类方法为压缩近邻法.,3压缩近邻法,CONDENSING算法,该算法有两个存储器,分别叫做STORE和GRABBAG.我们把第一个样本放在STORE中,而把所有其它样本放入GRABBAG.算法步骤如下:,步骤1用当前STORE中的样本以最近邻规则对GRABBAG的每个样本分类.假使分类正确,则该样本仍然送回GRABBAG中,否则放在STORE中,对GRABBAG中的所有样本重复上述过程.,步骤2若GRABBAG中的所有样本在进行上述的检验过程中没有一个样本从GRABBAG转到STORE或者当GRABBAG为空时,