模式识别第四章45近邻法ppt课件

n利用每一类的“代表点设计分段线性分类器问题是最简单而直观的设计方法，这类方法的缺点是所选择的“代表点不一定能很好地代表各个类，其后果是使所设计分类器的错误率增加。n将各类中全部样本都作为“代表点进行决策的方法称为近邻法。n近邻法是模式识别非参数法中最重要的方法之一。u4.5.1最近邻法最近邻法 u4.5.2 k-近邻法近邻法 u4.5.3 最佳距离度量近邻法最佳距离度量近邻法 4.5.1最近邻法最近邻法 u一、最近邻决策规则u最近邻分类是假定有c个类别1，2，c的模式识别问题，每类有标明类别的样本Ni个，i=1,2，cu规定i类的判别函数为 ikiiiNkg,2,1|min)(，xxx其中 的角标i表示i类，k表示i类Ni个样本中的第k个。按照上式。决策规则可以写为 kix4.5.1最近邻法最近邻法 n这一决策方法称为最近邻法。ciggiij，21)(min)(xx假设 n则决策 xjn其直观解释是相当简单的，就是说对未知样本x，只要比较x与 个已知类n别的样本之间的欧氏距离，并决策x与离它最近的样本同类。ciiNN1u一、最近邻决策规则u二、最近邻法的错误率分析n近邻法的错误率很难计算，因为训练样本集的数量总是有限的，有时多一个少一个训练样本对测试样本分类的结果影响很大。如图中所示4.5.1最近邻法最近邻法 n当最近邻法所使用的训练样本数量N不是很大时，其错误率是带有偶然性的。为了说明这一点用如图所示一个在一维特征空间的两类别情况来讨论。4.5.1最近邻法最近邻法 二、最近邻法的错误率分析n当最近邻法应用于特定的一组样本时，所得到的错误率与样本的偶然性有关。n特别是用不同组的N个样本对x进行分类的话，则x的最近邻可能是不相同的x。n由于决策完全取决于该最近邻样本，所以条件错误率是PN(e|x,x)，它同x和x都有关系。若对x取平均，得给定x时的条件错误率4.5.1最近邻法最近邻法 二、最近邻法的错误率分析)|(),|()|(xxxxxxdpePePNNn其中条件概率密度p(x|x)的确切表达式是难以得到的。但按定义x应为x的最近邻，所以可以设想该密度在x附近尖峰凸起，而在其它地方则较小。n就是说在已知x条件下，x的最近邻x在x附近概率密度最大，这显然是合理的。n而且当N时，可以期望p(x|x)趋于一个中心在x的函数。n这样就使上式的计算简单化了。为了严格证明这点，假定对于给定的x，p(x)是连续且非零的。4.5.1最近邻法最近邻法 二、最近邻法的错误率分析n在这样的条件下，任何样本落在以x为中心的一个超球s里的概率为一正数，记为Ps，且 4.5.1最近邻法最近邻法 二、最近邻法的错误率分析ssdpP)(xxxn这样，一个样本落在s外的概率为(l-Ps)，N个独立样本x1，x2，xN落在s外的概率为nP(x1，x2，xN)=(1-Ps)Nn当N 时，这一概率趋于零。n由于s可以任意小，所以N 时，x落在以x为中心无限小区域中的概率趋于l。n就是说x以概率为l收敛于x，从而4.5.1最近邻法最近邻法 二、最近邻法的错误率分析)()|(limxxxxpNn当说有N个独立抽取并有类别标记的样本时，意思是说有N对 n随机变量其中xi是独立抽取的样本，是xi的类别标记，且 是c个类别状态1，2，c之一。),(,),(),(2211NNxxxii4.5.1最近邻法最近邻法 二、最近邻法的错误率分析n假定抽取一对(x，)并假定标以 的x是x的最近邻。由于抽出x时，它的类别状态和x无关，因此有 n采用近邻规则的条件错误率就是)|()|(),|,(xxxxPPPciiiciiiNPPPeP11)|()|(1),|,(1),|(xxxxxx4.5.1最近邻法最近邻法 二、最近邻法的错误率分析ciiNNPeP12)|(1),|(limxxxciiciiNNNNPdPdPePeP1212)|(1)()|(1)|(),|(lim)|(limxxxxxxxxxxx4.5.1最近邻法最近邻法 二、最近邻法的错误率分析n按渐近平均错误率的定义，有 xxxxxxxxxdpPdpePdpePePPciiNNNNNN)()|(1)()|(lim)()|(lim)(lim12n上式提供了最近邻法错误率P的计算公式。nP称为渐近平均错误率，是PN(e)在N的极限。n根据贝叶斯错误率的讨论，若设)|(max)|(xxiimPPn则有Bayes条件错误率)|(1)|(*xxmPeP因此 xxxdpePP)()|(*4.5.1最近邻法最近邻法 二、最近邻法的错误率分析n对于两类问题，由前面公式212)|(1)|(limiiNNPePxx)|()|(1)|(lim2212xxxPPePNNn将上式减去贝叶斯错误率)|(1)|(*1xxPeP4.5.1最近邻法最近邻法 二、最近邻法的错误率分析n可得n 可得)|()|()|()|()|(1)|(2122211xxxxxxPPPPPPP从式中可见在一般情况下只要P(1|x)P(2|x)0，P是大于零的值。在两种例外情况下P0：P(1|x)1或P(1|x)P(2|x)1/2。4.5.1最近邻法最近邻法 二、最近邻法的错误率分析n在P(m|x)=1时，0)(11 xx dpP0)()|(1)()|(*mxxxxxxdpPdpePP此时P=P*。特例特例4.5.1最近邻法最近邻法 二、最近邻法的错误率分析在P(i|x)=1/c,（i=1，2，c时，即各类后验概率相等的情况，有此时也有P=P*。ccdpcPci1)(11 12xxccdpcP1)(11*xx4.5.1最近邻法最近邻法 二、最近邻法的错误率分析n请想一下，什么情况下P(1|x)1或P(2|x)=1?P(1|x)=P(2|x)会出现什么情况？n答：一般来说，在某一类样本分布密集区，某一类的后验概率接近或等于1。此时，基于最小错误率贝叶斯决策基本没错，而近邻法出错可能也很小。而后验概率近似相等一般出现在两类分布的交界处，此时分类没有依据，因此基于最小错误率的贝叶斯决策无能为力，近邻法与贝叶斯决策效果相同。4.5.1最近邻法最近邻法 二、最近邻法的错误率分析n从以上讨论可以看出，当N时，最近邻法的渐近平均错误率的下界是贝叶斯错误率，这发生在样本对某类别后验概率处处为1的情况或各类后验概率相等的情况。n在其它条件下，最近邻法的错误率要高于贝叶斯错误率。4.5.1最近邻法最近邻法 二、最近邻法的错误率分析n可以证明以下关系式成立 *)12(*PccPPPn上式实际上给出了最近邻法渐近平均错误率P的范围，指出它在Bayes错误率P*和 之间。*)12(*PccPn其中P*为贝叶斯错误率，c为类数。4.5.1最近邻法最近邻法 二、最近邻法的错误率分析n证明P的上界是*)12(*PccPn仍然考虑下式4.5.1最近邻法最近邻法 二、最近邻法的错误率分析xxxdpPPcii)()|(1 12n并已知Bayes条件错误率nP*(e|x)=1P(m|x)n以上两式表明：对已知的P(m|x)，n 的最小值对应于P的最大值。ciiP12)|(xn若记4.5.1最近邻法最近邻法 二、最近邻法的错误率分析则在以下约束条件miimciiPPP)|()|()|(2212xxx0)|(xiP)|(*)|(1)|(xxxePPPmmiin 除m外，其它后验概率都相等，即，i=1，2，c；i m APi)|(x满足时 达到极小。ciiP12)|(x4.5.1最近邻法最近邻法 二、最近邻法的错误率分析miiiePPcP)|(*)|()1()|(xxxmiePmicePPi，)|(*11)|(*)|(xxxn根据第二个约束条件，有4.5.1最近邻法最近邻法 二、最近邻法的错误率分析)|(*1)|(*211)|(*)|(*1)1()|(*)|(*1)|()|()|(2222222212xxxxxxxxxePccePcePePcePePPPPmimiimciin 整理上式得)|(*1)|(*2)|(1212xxxePccePPcii4.5.1最近邻法最近邻法 二、最近邻法的错误率分析n求P*(e|x)的方差DP*(e|x)。n根据式：xxxdpePP)()|(*nEP*(e|x)=P*n根据方差定义有 0*)()|(*)(*)|(*)|(*222PdpePdpPePePDxxxxxxxn上述表达式证明了P2P*。4.5.1最近邻法最近邻法 二、最近邻法的错误率分析即 xxxdpePP)()|(*22xxxdpPPcii)()|(1 12n根据错误率公式n及上述结果，可得*)12(*1*2)()|(*1)()|(*2)()|(*1)|(*2)()|(1 22212PccPPccPdpePccdpePdpePccePdpPPciixxxxxxxxxxxxx图4.14示出近邻法的上下界。一般地，最近邻法的错误率落在图中的阴影区域中。4.5.1最近邻法最近邻法 二、最近邻法的错误率分析c类别最近邻类别最近邻分类器可能分类器可能渐近误差率渐近误差率n由于一般情况下P*很小，因此错误率又可粗略表示成*2*PPP因此可以说最近邻法的渐近平均错误率在贝叶斯错误率的两倍之内。从这点说最近邻法是优良的，因此它是模式识别重要方法之一。4.5.1最近邻法最近邻法 二、最近邻法的错误率分析4.5.2 k-近邻法近邻法 nk-近邻法是取未知样本x的k个近邻，看这k个近邻中多数属于哪一类，就把x归于那一类，就是说在N个已知样本中，找出x的k个近邻。n人为确定k(根据经验设定)，k大，错误率小，计算量大。4.5.2 k-近邻法近邻法 n如图4.15所示k-近邻算法示意图。4.5.2 k-近邻法近邻法 n设这N个样本中，来自1类的样本有N1个，来自2类的样本有N2个，来自c类的样本有Nc个，若k1，k2，kc分别是k个近邻中属于1，2，c类的样本数，定义判别函数为ngi(x)=ki，i=1，2，c (4-61)iiikgmax)(xn决策规则为n，则决策xj。n这就是k-近邻法的基本规则。若分错，则风险很大，错误率大，损失大。nk近邻一般采用k为奇数，跟投票表决一样，避免因两种票数相等而难以决策。n考虑到风险(损失)问题，对ki加以约束，假设21kki则xi，否则拒判。4.5.2 k-近邻法近邻法 n对最近邻法条件错误率式，对两类问题稍加变化可以写成n当N 时，x与其最近邻x非常接近，于是有)|()|()|()|(),|(1221xxxxxxPPPPePNP(i|x)P(i|x)4.5.2 k-近邻法近邻法)|()|()|()|(),|(1221xxxxxxPPPPePNn很容易推广到k-近邻法。若设x属于1，而k1小于等于 ，则发生误判这一事件的概率为21kn同样可得到x属于2 的情况。jkjkjjkPPC)|()|(212/)1(0 xxn式中)!(!jkjkCjk2/)1(1122212/)1(01)|()|()|()|()|()|()|(kjjkjjkjkjkjjkkNPPCPPPCPePxxxxxxx4.5.2 k-近邻法近邻法 n其中第一项和第二项分别式对于x1和x2的条件概率。其一般情况为：kkjjkijijkijkijikjjkikNPPCPPPCPeP2/)1(2/)1(0)|(1)|()|(1)|(1)|()|()|(xxxxxxxn其中第一项为xi而决策 的概率，第二项为 而决策xi的概率。ixix4.5.2 k-近邻法近邻法 n为了得到渐近平均错误率Pk，可以对所有的x求上式的期望。n此时，Bayes条件错误率为kkjjkjjkjkjkjjkkNePePCePePePCePeP2/)1(2/)1(0)|(*1)|(*)|(*1)|(*1)|(*)|(*)|(xxxxxxx)|(xePkNn这是很困难的。定义一个Bayes条件错误率P*(e|x)的函数CkP*(e|x)为大于 最小凹函数，4.5.2 k-近邻法近邻法 P*P Ck(P*)Ck1(P*)C1(P*)2P*(1P*)n即对所有x有)|(*)|(xxePCePkkN那么*)()|(*)|(*)|(PCePECePCEePEPkkkkNxxxn由于 随k的增大单调减小，故最小凹函数Ck也随k单调减小。所以得到下列不等式关系：)|(xePkN4.5.2 k-近邻法近邻法 n其中2P*(1P*)是两类最近邻法错误率的上限，即c=2的情况。0.50.50.250.2500Ck(P*)贝叶斯错误率k=99k=1k=3k=5k=7图 4.15nk=1时的情况对应于图4.14中最近邻法的情况。n当k增加时，上限逐 渐 靠 近 下 限Bayes错误率P*。n当k趋于无穷时，上下限重合，从而k-近邻法最优。n图4.15中示出了具有不同k值的k-近邻法错误率的上下限。4.5.2 k-近邻法近邻法 结论n上述结论是在样本数N趋于无穷的假设下取得的。n在实际问题中，样本数是有限的。因此，通常在k-近邻法中选择k值时，一方面采用大一些的k值以减小错误率，另一方面要求k个近邻都很靠近x，以保证P(i|x)和P(i|x)近似相等。n选择k值时折衷考虑，使它总是样本数的一小部分。4.5.2 k-近邻法近邻法 n最近邻法和k-近邻法都有方法简单的优点，而且分类效果比较好，其错误率为*)12(*PccPPPn由于P*一般很小，因此上式可近似表示为nP*P 2P*n即近邻法错误率在Bayes错误率P*和两倍Bayes错误率2P*之间。n正因为此优良性质，使其成为模式识别的重要方法之一。4.5.2 k-近邻法近邻法 n但近邻法存在以下问题：n需要将所有样本存入计算机中，每次决策都要计算待识别样本x与全部训练样本 ，i=1，2，c，k=1，2，Ni之间的距离并进行比较。kixn存储量和计算量都很大n虽然在一般情况下，对未知样本x都可以进行决策，但当错误代价很大时，会产生较大的风险。4.5.2 k-近邻法近邻法 n但近邻法存在以下问题(续)：n要求样本数N ，这在任何实际场合是无法实现的。n为了解决上述问题出现了一些改进算法，如剪辑近邻法解决存储量大的问题；快速搜索近邻法解决计算量大的问题等。4.5.2 k-近邻法近邻法 n近邻法举例 Figure shows the decision boundary of the(K=8)-nearest neighbor classifier.4.5.2 k-近邻法近邻法 快速搜索近邻法快速搜索近邻法 n这种方法只解决减少计算量，但没有达到减少存储量的要求。n其基本思想是将样本集按邻近关系分解成组，给出每组的质心所在，以及组内样本至该质心的最大距离。这些组又可形成层次结构，即组又分子组，因而待识别样本可将搜索近邻的范围从某一大组，逐渐深入到其中的子组，直至树的叶结点所代表的组，确定其相邻关系。4.5.2 k-近邻法近邻法 一、样本集分级分解一、样本集分级分解n根据以上基本思想，先对样本集进行分级分解，分级分解过程可列举如下：n首先将整个样本分成l个子集，每个子集又分为它的l个子集，如此进行若干次就能建立起一个样本集的树形结构。分成子集的原则是该子集内的样本尽可能聚成堆，这可用聚类方法实现。4.5.2 k-近邻法近邻法 一、样本集分级分解一、样本集分级分解n结点参数：树形结构，每个结点表示一样本子集，描述该子集的参数是：nXp该结点对应的样本子集代号；nNpp中包含的样本个数；nMp是样本子集p的样本均值；4.5.2 k-近邻法近邻法),(maxpipMDrpixxMp到所属成员的最大距离。二、快速搜索算法二、快速搜索算法 n要实现快速搜索近邻，需要有方法快速判断某个样本子集是否是该待识样本的可能近邻样本集，从而可将无关的样本子集尽快排除。n另一方面在某样本子集内寻找哪个样本是近邻时，需快速排除不可能为近邻的样本。n这两个快速判别算法可用以下两个规则表示：4.5.2 k-近邻法近邻法 二、快速搜索算法二、快速搜索算法 n规则1：如果存在 nB+rpD(x，Mp)n则xiXp不可能是x的近邻。其中B是待识别样本在搜索近邻过程中的当前近邻距离，B在搜索过程中不断改变与缩小。算法开始可将B设为无穷大。nD(x,Mp)表示待识样本x到结点Xp的均值点距离。4.5.2 k-近邻法近邻法 二、快速搜索算法二、快速搜索算法 n这个规则的证明是显而易见的，如图表示一待识样本及其当前近邻与一样本子集的关系。B+rpD(x，Mp)4.5.2 k-近邻法近邻法 二、快速搜索算法二、快速搜索算法 n如果以x为圆心，B为半径作圆，则圆与样本子集Xp的分布圆不会相交，因而Xp中任一样本不可能比x的当前近邻更靠近x。B+rpD(x，Mp)4.5.2 k-近邻法近邻法 二、快速搜索算法二、快速搜索算法 n规则2：假设 B+D(xi，Mp)D(x，Mp)n其中xiX，则xi不可能是x的近邻。规则2的证明同规则1。n由此可见，只要将每个样本子集中的每个样本xi到其均值Mp的距离D(xi，Mp)存入存储器中，就可利用上式将许多不可能成为测试样本近邻的训练样本排除。4.5.2 k-近邻法近邻法 二、快速搜索算法二、快速搜索算法 n如何运用这两个规则设计一个近邻的快速搜索算法?n搜索算法的大体过程是这样的：当搜索树形样本集结构由高层次向低层次深入时，对同一层次的所有结点，可以利用规则1排除掉一些不可能包含待识别样本的近邻的结点(样本子集)。4.5.2 k-近邻法近邻法 二、快速搜索算法二、快速搜索算法 n但是这往往不能做到只留下唯一的待搜索结点，因此必须选择其中某一结点先深入搜索，以类似于深度优先的方法确定搜索路径直至叶结点。n然而在该叶结点中找到的近邻并不能保证确实是全样本集中的最近邻者，所找到的该近邻样本需要在那些有可能包含最近邻的样本子集中核对与修正，直至找到真正的最近邻样本为止。4.5.2 k-近邻法近邻法 二、快速搜索算法二、快速搜索算法 n树搜索算法具体的搜索步骤：n步骤1：初始化置B，L1(当前层次)，p0(确定当前结点)。n步骤2：置后选待搜索结点把当前结点的所有直接后继结点放入层的一目录表中，并对这些结点计算D(x，Mp)。n步骤3：排除无关结点对层目录表中的每个结点P，用规则1将与近邻无缘的结点从目录表中清除。4.5.2 k-近邻法近邻法 二、快速搜索算法二、快速搜索算法 n步骤4：路径选择如该层次目录表中有不止一个结点，选其中D(x，Mp)最小者，将该结点从目录表中删除，如该结点是叶结点转 步骤5，如不是叶结点，则LL+1，转步骤2；如该层次目录表中无结点待搜索，则LL-1，如L0则停止，否则转步骤3。4.5.2 k-近邻法近邻法 二、快速搜索算法二、快速搜索算法 n步骤5：近邻样本搜索对现在执行结点p中的每个样本xi，利用规则2作如下检验：如果D(x，Mp)D(xi，Mp)+B则xi不是x的最近邻，否则计算D(x，xi)，若D(x，xi)B，置NNi和BD(x，xi)。对当前执行结点中所有xi被检验后，转步骤3。n在算法结束时，输出x的最近邻xNN及两者间距离 D(x，xNN)=B。4.5.2 k-近邻法近邻法 k-近邻法的快速计算近邻法的快速计算 nk-近邻法快速计算是搜索待测样本的k个最近邻，以做到最后在这k个最近邻中计算占多数的训练样本类别。因此只要发现有一个训练样本比当前第k个近邻的距离要小，就把当前第k个近邻剔除出当前k近邻组。4.5.2 k-近邻法近邻法 k-近邻法的快速计算近邻法的快速计算 nk-近邻法的快速计算法与上述过程大体相同，只是B值修改为当前第k个近邻的距离值。然后在步骤5中，对所计算的距离要与该k个当前的近邻比较，若比其中某个距离小，则删除最大者。除了以上两点修正外，其它算法与最近邻快速算法一样。4.5.2 k-近邻法近邻法 剪辑近邻法剪辑近邻法 n以上讨论的快速算法只是研究如何减少计算量的问题，而不考虑存储量的压缩。实际上由于对样本进行分层次分组，并附有一些参数，实际的存储量还有可能增加。n本节讨论的算法着眼于如何减少模板样本数目，从而可同时减少分类时的计算量及模板样本的存储量，同时还能进一步改进分类器的性能，如降低错误率等要求。本节讨论的剪辑近邻法除了在样本数量上有一定程度的减少外，更主要的优点是错误率的降低。4.5.2 k-近邻法近邻法 剪辑近邻法剪辑近邻法 n剪辑近邻法的基本思想是从这样一个现象出发的，即当不同类别的样本在分布上有交迭部分的，分类的错误率主要来自处于交迭区中的样本。当得到一个作为识别用的参考样本集时，由于不同类别交迭区域中不同类别的样本彼此穿插，导致用近邻法分类出错。4.5.2 k-近邻法近邻法 剪辑近邻法剪辑近邻法 n因此如果能将不同类别交界处的样本以适当方式筛选，可以实现既减少样本数又提高正确识别率的双重目的。n为此可以利用现有样本集对其自身进行剪辑。n下面以两类别问题为例说明这种方法的原理。4.5.2 k-近邻法近邻法 剪辑近邻法剪辑近邻法 n假设现有一个样本集N，样本数量为N。将此样本集分成两个互相独立的样本子集。n一个被当作考试集XNT,另一个作为参考集XNR，数量分别为NT与NR，NT+NRN。将XNT中的样本表示成xi(i=1,NT)，而在XNR中的样本表示为yi(i=1,NR)。4.5.2 k-近邻法近邻法 剪辑近邻法剪辑近邻法 n将一个样本集分成两个相互独立的样本子集是指，分完以后的两个子集具有相同的分布例如将一个样本集分成两个相互独立的对等子集，则在每个特征空间的子区域，两个子集都有相同的比例，或说各类数量近似相等。n要注意的是每个子区域(从大空间到小空间)实际做时要用从总的集合中随机抽取的方式进行。4.5.2 k-近邻法近邻法 剪辑近邻法剪辑近邻法 n剪辑的过程是：首先对XNT中每一个xi在XNR中找到其最近邻的样本yi(xi)，用yi(xi)表示yi是xi的最近邻参考样本。如果yi与xi不属于同一类别，则将xi从XNT中删除，最后从XNT中得到一个经过剪辑的样本集，称为剪辑样本集。可用来取代原样本集，作为参考样本集对待识别样本进行分类。4.5.2 k-近邻法近邻法 剪辑近邻法剪辑近邻法 nXNT经过剪辑后，要作为新的训练样本集，则XNR是对其性能进行测试的样本，如发现XNT中的某个训练样本对分类不利，就要把它剪辑掉。n实际上剪辑样本的过程也可以用k-近邻法进行，即对XNT中的每个样本xi，找到在XNR中的k个近邻，用k-近邻法判断xi是否被错分类。从而决定其取舍，其它过程与前述方法完全一样。4.5.2 k-近邻法近邻法 剪辑近邻法剪辑近邻法 n剪辑近邻法也可用到多类别情况。n剪辑过程也可不止一次。重复多次的称为重复剪辑近邻法。n图1到图4是一个两类正态分布样本的重复剪辑结果，图1是原始样本集，图2是经一次迭代的结果，图3是三次迭代留下的样本，图4是算法终止时留下的样本。4.5.2 k-近邻法近邻法 剪辑近邻法剪辑近邻法 n所使用的重复剪辑算法步骤如下：n1.将样本集XNT随机划分为S个子集，即nXN=X1,X2,Xs,s3n2.用最近邻法，以Xj,j=(i+1)mod s为参考集，对 Xi中的样本进行分类，其中i1，s。n3.去掉步骤2中被错分类的样本。n4.用所有留下的全部样本的构成新的样本集XNTn5.如该次剪辑过程中没有样本被删除，则停止，否则转步骤1。4.5.2 k-近邻法近邻法 剪辑近邻法剪辑近邻法 n由此可见每次迭代过程都要重新对现有样本集进行重新随机划分，以保证了剪辑的独立性。4.5.2 k-近邻法近邻法 剪辑近邻法剪辑近邻法 n用近邻法容易出错的区域是在两类的交界处，这时某个训练样本存在与否就会影响到某些测试分类的结果。因此剪辑的效果往往把这些处于交界的训练样本给剪辑掉了。n以上讨论了剪辑近邻法的原理与算法，另一个问题是对剪辑近邻法错误率的分析。n这里只给出简单的结论：4.5.2 k-近邻法近邻法 剪辑近邻法剪辑近邻法 n1.利用最近邻法剪辑后得到的样本集进行分类，其错误率总小于原样本集，如用P1E(e),表示其错误率，则有 nP1E(e)P(e)n其中P(e)表示用原样本的渐近平均错误率。n在P(e)很小，如P(e)0.1情况下可有nP1E(e)=1/2 P(e)n由于近邻法错误率上界为2P*(两倍贝叶斯错误率)，因此nP1E(e)=P*4.5.2 k-近邻法近邻法 剪辑近邻法剪辑近邻法 n2.利用k-近邻法进行剪辑得到的样本集进行分类，则在N及k，且K/N0的条件下有nPkE(e)=P*n该式表明k很大时，剪辑样本法的错误率可收敛于最优情况P*。当然实际上k值不能取得太大。n3.多类情况，剪辑效果更好。4.5.2 k-近邻法近邻法 压缩近邻法压缩近邻法n从上述讨论中可以看出，剪辑近邻法所得到的剪辑样本集在样本数量的压缩方面并不十分明显，它的作用在于将原样本集中处于边界处的样本删除掉，但靠近两类中心的大部分样本仍被保留下来。n然而按近邻规则来看，这些样本中的大多数对分类决策没什么用处，如能在剪辑的基础上再去掉一部分这样的样本，将有助于进一步缩短计算时间与压缩存储量，这种方法称为压缩近邻法。4.5.2 k-近邻法近邻法 压缩近邻法压缩近邻法n压缩近邻法压缩样本的思想很简单，它利用现有样本集，逐渐生成一个新的样本集。使该样本集在保留最少量样本的条件下,仍能对原有样本的全部用最近邻法正确分类，那末该样本集也就能对待识别样本进行分类,并保持正常识别率。该算法的作法也十分简单，它定义两个存储器，一个用来存放即将生成的样本集，称为Store；另一存储器则存放原样本集，称为Grabbag。4.5.2 k-近邻法近邻法 压缩近邻法压缩近邻法n其算法是：n1.初始化Store是空集，原样本集存入Grabbag；从Grabbag中任意选择一样本放入Store中作为新样本集的第一个样本。n2.样本集生成在Grabbag中取出第i个样本用Store中的当前样本集按最近邻法分类。若分类错误，则将该样本从Grabbag转入Store中，若分类正确，则将该样本放回Grabbag中，对Grabbag中所有样本重复上述过程。4.5.2 k-近邻法近邻法 压缩近邻法压缩近邻法n其算法是：n3.结束过程若Grabbag中所有样本在执行第二步时没有发生转入Store的现象，或Grabbag已成空集，则算法终止，否则转入第二步。n在算法终止后，Store中的样本集作为压缩样本集，可用来对待识别样本按最近邻法分类。4.5.2 k-近邻法近邻法 压缩近邻法压缩近邻法4.5.2 k-近邻法近邻法 压缩近邻法压缩近邻法n图5与图6显示了用压缩近邻法得到的样本集及其分界决策面。其中图5所示为一个两类别问题用剪辑近邻法得到的样本集。图中虚线表示贝叶斯决策面，实线为最近邻法相应的决策域边界。图6则是图5中的剪辑样本经压缩近邻法生成的压缩样本集。4.5.2 k-近邻法近邻法 压缩近邻法压缩近邻法n图5与图6显示了用压缩近邻法得到的样本集及其分界决策面。其中图5所示为一个两类别问题用剪辑近邻法得到的样本集。图中虚线表示贝叶斯决策面，实线为最近邻法相应的决策域边界。图6则是图5中的剪辑样本经压缩近邻法生成的压缩样本集。从中可看出样本的数量极大地减少了。图中还画出了贝叶斯分界面与压缩后的近邻法决策面，它虽然比剪辑样本的近邻产生的决策面偏离贝叶斯决策面要大些，但所需样本数量却大大减少了，4.5.2 k-近邻法近邻法 压缩近邻法压缩近邻法n从中可看出样本的数量极大地减少了。图中还画出了贝叶斯分界面与压缩后的近邻法决策面，它虽然比剪辑样本的近邻产生的决策面偏离贝叶斯决策面要大些，但所需样本数量却大大减少了，4.5.2 k-近邻法近邻法 压缩近邻法压缩近邻法n从图1至6可以看出来，其实处于同一类样本密集区的测试样本并不一定要全部保留，几乎绝大部分都可去掉，只要保留若干个训练样本即可。问题是保留哪些好。压缩近邻法采用了用测试集测试的办法，采用只要分类有错，在出错处添加一个训练样本的做法。4.5.2 k-近邻法近邻法 压缩近邻法压缩近邻法n试想一下压缩近邻法的思想与错误修正算法有什么相似与不同之处?n答：其实两者的想法还是很像的。压缩近邻法是用测试样本找一些各类的代表点，用近邻原则计算，而错误修正法是找一些代表性增广权向量，其参数由错分类修正。具体计算的机制不一样，一是计算相似度，而错误修正法的aTy严格意义上讲不是相似度。4.5.2 k-近邻法近邻法 4.5.3 最佳距离度量近邻法最佳距离度量近邻法 n在最近邻法中，选择未知样本x的最近邻时，没有考虑具体的距离量度。n当样本数N ，渐近平均错误率和具体的距离量度无关。nP 2P*n然而，N 的条件是无法实现的。在有限样本怎样才能得到较小的错误率？n用距离函数。4.5.3 最佳距离度量近邻法最佳距离度量近邻法 PN(e|x)=P(1|x)P(2|x)+P(2|x)P(1|x)=P(1|x)1P(1|x)+P(1|x)P(2|x)=2P(1|x)P(2|x)+P(1|x)P(2|x)P(1|x)P(1|x)n当N 时，渐近条件错误率)|()|(2)|(lim)|(21xxxxPPePePNNn上面两式都表示最近邻法的条件错误率，只不过一个是对有限样本，而另一个是对无穷样本。两者间的误差为n PN(e|x)P(e|x)n=P(1|x)P(2|x)P(1|x)P(1|x)4.5.3 最佳距离度量近邻法最佳距离度量近邻法 n若定义n(x，x)=P(1|x)P(1|x)n对于确定的x，由于上式右边前一个因子P(1|x)P(2|x)是常数，使有限样本与无穷样本错误率之间的均方误差nEPN(e|x)P(e|x)2|xn减至最小，等价于使nE2(x，x)|xn减至最小。4.5.3 最佳距离度量近邻法最佳距离度量近邻法 n可以通过增加样本数N使上式减小。n若样本数N不增加，定义一个距离度量D(x，)，使上式减至最小，从而使有限样本与无穷样本之间错误率的均方误差减至最小。4.5.3 最佳距离度量近邻法最佳距离度量近邻法 n在x的一个局部邻近区域，P(1|x)可通过截尾的级数展开做线性近似为nP(1|x)P(1|x)+P(1|x)T(xx)TP)|(1xn其中 表示 P(1|x)的梯度转置。n利用上式的近似有)()|(),(1xxxxxTP那么|)()|(|),(212xxxxxxxTPEE4.5.3 最佳距离度量近邻法最佳距离度量近邻法 n即若定义新的距离函数为n其中x为x的局部邻近区域中的样本，则必有 n利用(x，x)的近似表达式，在x的局部邻近区域中，x的最近邻x应使n 为最小。|)()|(|1xxxTP|)()|(|),(1xxxxxTPD),(min),(xxxxDDl4.5.3 最佳距离度量近邻法最佳距离度量近邻法 n就是说，如果按上式定义的新距离，在x的局部邻近区域中选择x的最近邻x，则可使有限样本与无穷样本的错误率之差在均方意义下达到最小。n上述距离度量是通过对P(1|x)的局部邻近区域中做线性近似得到的。n因此它只适用于XN中与x较为接近的那些样本。|)()|(|),(1xxxxxTPD4.5.3 最佳距离度量近邻法最佳距离度量近邻法 n设A表示以x为中心的一个局部邻近区域，rA为欧氏距离意义下的A的半径，则有：n假设|xx|rA，则xAn定义x处的一个局部期望向量为|)()|(|),(1xxxxxTPD)|(1xP)|(1xPn计算D(x，)的关键是求 ，至少是求 的估计值。4.5.3 最佳距离度量近邻法最佳距离度量近邻法 AliillilllidupAExxxxxxxxxx)()|()(|)()(且其中Alilidpuxxx)|()(p(xl|i)为xl的类条件密度。4.5.3 最佳距离度量近邻法最佳距离度量近邻法 n将p(xl|i)做泰勒级数展开为)|()(21)()|()|()|(2iTllTiiilppppxxxxxxxxn利用上式，那么AilliTllAiilTllAiilliudpupdupd)(1)()|()(21)()|()()()|()()(2xxxxxxxxxxxxxxxxxxxxxx4.5.3 最佳距离度量近邻法最佳距离度量近邻法 n由于积分限A对x点对称，上式中第一项和第三项为零，因此有 4.5.3 最佳距离度量近邻法最佳距离度量近邻法)|()()()(iiAlTllipudxxxxxxxxn因为A是以x为中心的一个小区域，因此可得近似式nui(x)VA p(x|i)n其中VA为区域A的体积。经推导后，上面式子可写为)|()|()(iiippcxxx其中常数c为 222drcAd为样本空间的维数。4.5.3 最佳距离度量近邻法最佳距离度量近邻法 n可以在A上定义混合均值向量n0(x)=E(xlx)|xlAn同样可推导得)()()(0 xxxppcn利用上述结果可以计算)()()|(1)()|()()|()()()|()()|(02xxxxxxxxxxiiiiiiiiPcppppPppPP4.5.3 最佳距离度量近邻法最佳距离度量近邻法)|(1xP)|(11xPn设1(x)和0(x)的估计值为M1(x)和M0(x)，则利用上式可以得到 的估计值为)()()|()|(01111xxxxMMcPPn 的大小不影响寻找x的近邻x，因此，上面式中前面的系数可以忽略，得到)|(1xP|()|(|),(11lTlPDxxxxxn在用距离度量时，)()()|(0111xxxMMP4.5.3 最佳距离度量近邻法最佳距离度量近邻法 n如果在局部邻近区域A中有NA个样本x，其中NAi 个属于 i类，则局部样本均值的估计为iAiNlAiNM)(1)(xxx以及AiNlANM)(1)(0 xxx4.5.3 最佳距离度量近邻法最佳距离度量近邻法 计算|xx1|，|xxN|；找出与x距离最短的NA个近邻xl；利用xl计算M1M2;用D(x，xl)寻找x最近邻的程序步骤：|)()(|,|,)()(|0101NAlTlTMMMMxxxxklxklxklx 计算 选出其中最小者，若为 ，那么 为x的按距离D(x，xl)度量的最近邻，即 =x。4.5.3 最佳距离度量近邻法最佳距离度量近邻法 n找到x后，就可以用一般的最近邻法将x归为与x相同的类，并且这样的分类将保证与无穷样本最近邻法错误率的均方误差最小。n只多了NA次距离计算，通常NAN，因此所增加的计算时间不大。4.5.3 最佳距离度量近邻法最佳距离度量近邻法 n将上述结果推广到多类情况。一般最近邻法在c类时的条件错误率为cjjiijNPPeP1)|()|()|(xxxcjjiijNPPeP1)|()|(lim)|(xxxn当N 时渐近条件错误率为 n两式相减并经化简后可得|)|()|()(|(|)|()|(|1cjiijNPPPePePxxxxx4.5.3 最佳距离度量近邻法最佳距离度量近邻法 n在x的局部邻近区域A中对P(i|x)取线性近似得 n则与两类情况一样，极小化n等价于极小化|)()|()|(|)|()|(|11cjTijNPPePePxxxxxxcjijPP11)|()|(xx令|)|()|(|2xxxePePEN|)(|()|(|211xxxxxcjTijPPE4.5.3 最佳距离度量近邻法最佳距离度量近邻法 n利用局部样本可估计P(i|x)为 1n可 将写成局部均值向量的形式 cjijcjijPcPP1011)()()|(1)|()|(xxxxxNNPii)|(x4.5.3 最佳距离度量近邻法最佳距离度量近邻法 n同样可用局部样本均值向量Mi代替i，这样ciiiMMNNc1021)()()(1xxn求出 后，即可以找到最佳距离度量 1|)(|),(1lTDxxxxn并应用类似算法，可求得任意x的最近邻x，然后按最近邻法分类。n从上面分析可见，采用现在定义的距离度量，在不增加样本数N的情况下，可以使最近邻法的性能与N 时最近邻法的平方差别最小，因此称这样定义的距离是最佳的。4.5.3 最佳距离度量近邻法最佳距离度量近邻法