模式识别_第6章_近邻法.ppt

1、第6章 近邻法,6.1最近邻法， k近邻法 6.2误判概率上下界 6.3 改进的近邻法,Bayes方法需要借助概率密度函数估计。可以看出，其应用受到很大限制。事实上，非参数模式识别方法更为实用。由于能解决许多实际的模式识别问题，虽然在许多情况下它们不是最优的，但却是应用的最多的有效的方法。统计模式识别中常用的基本非参数方法除了前面介绍的线性判别函数外，还有将要介绍的近邻法和聚类。近邻法属于有监督学习，聚类属于无监督学习。它是在已知模式类别的训练样本的条件下，绕开概率的估计，按最近距离原则对待识别模式直接进行分类。,近邻法,最近邻分类器(nearest neighborhood classifi

2、er, nnc): 最小距离分类器的一种极端的情况，以全部训练样本作为代表点，计算测试样本与所有样本的距离，并以最近邻者的类别作为决策。 最初的近邻法是由Cover和Hart于1968年提出的，随后得到理论上深入的分析与研究，是非参数法中最重要的方法之一。,c类问题,设,最近邻方法6.1 最近邻决策规则1-NN,最近邻分类规则: 对待识别模式 , 分别计算它与 个已知类别的样本 的距离,将它判为距离最近的那个样本所属的类。,最近邻方法6.1 最近邻决策规则1-NN,(4)找出最小距离dm(x)=mindi(x),(5)看xm属于哪一类：xm2,(6) 判x2,k-NN分类思想: 对待识别模式

3、, 分别计算它与 个已知类别的样本 的距离,取k个最近邻样本,这k个样本中哪一类最多, 就判属哪一类。,最近邻方法6.1 最近邻决策规则k-NN,其中 表示k个近邻元中属于i的样本个数,最近邻方法6.1 最近邻决策规则k-NN,(6) 判x2,(3)计算x到xiX，(i=1, 2,N)的距离di(x),下面我们先定性的比较一下最近邻分类法与最小错误率的Bayes分类方法的分类能力。 我们把 的最近邻 的类别看成是一个随机变量 ， 的概率为后验概率,最近邻法错误率分析,按最小错误率的Bayes决策法则：以概率1决策 ； 按最近邻决策法则：以概率 决策 ；,最近邻法则可以看成是一个随机化决策 按照

4、概率 来决定 的类别。 定义：,这里假设在三类问题中， 的后验概率分别为 按最小错误率的Bayes决策法则：以概率1决策 ； 按最近邻决策法则：以概率 决策 ；以概率 决策 。 当 时，最近邻法的决策结果与最小错误率的Bayes决策的决策结果相同，它们的错误率都是比较小的，两种方法同样的好，当 ，两者的错误概率接近于 ，两种方法同样的坏。下面我们将进一步分析近邻法的错误率。,最近邻法的错误率高于贝叶斯错误率，可以证明以下关系式成立：,由于一般情况下P*很小，因此又可粗略表示成： 可粗略说最近邻法的渐近平均错误率在贝叶斯错误率的两倍之内。,在N的条件下，k-近邻法的错误率要低于最近邻法。 最近邻

5、法和k-近邻法的错误率上下界都是在一倍到两倍贝叶斯决策方法的错误率范围内。,最近邻法错误率分析,从上面可以看出近邻法有方法简单的优点，但也存在这一些缺点： （1）存储量和计算量都很大； （2）没有考虑决策的风险，如果决策的错误代价很大时，会产生很大的风险； （3）以上的分析渐近平均错误率，都是建立在样本数趋向无穷大的条件下得来的，在实际应用时大多是无法实现的。,6.3 改进的近邻法,近邻法的一个严重不足与问题是需要存储全部训练样本，以及繁重的距离计算量。 两类改进的方法： 一种是对样本集进行组织与整理，分群分层，尽可能将计算压缩到在接近测试样本邻域的小范围内，避免盲目地与训练样本集中每个样本进

6、行距离计算。 另一种则是在原有样本集中挑选出对分类计算有效的样本，使样本总数合理地减少，以同时达到既减少计算量，又减少存储量的双重效果。,对于两类问题，设将已知类别的样本集X(N)分成参照集X(NR)和测试集X(NT)两部分，X(NR)X(NT)=，它们的样本数各为NR和NT，NR+NT=N。利用参照集X(NR)中的样本 采用最近邻规则对已知类别的测试集X(NT)中的每个样本 进行分类，剪辑掉X(NT)中被错误分类的样本。,6.2 剪辑最近邻方法,获得剪辑样本集X(NTE)后，对待识模式 采用最近邻规则进行分类。,剪辑最近邻方法,剪辑最近邻方法,12X(NR)X(NT),用X(NR)中的样本采

7、用最近邻规则对X(NT)中的每个样本分类，剪辑掉X(NT)中被错误分类的样本。,余下判决正确的样本组成剪辑样本集X(NTE) 。,用X(NTE) 对输入的未知样本做K-NN分类。,剪辑最近邻法可以推广至k-NN近邻法中。步骤： 第一步 用k-NN 法进行剪辑; 第二步 用1-NN 法进行分类。,如果样本足够多，就可以重复地执行剪辑程序，以进一步提高分类性能。称为重复剪辑最近邻法。,剪辑最近邻方法 6.2.2 剪辑k-NN最近邻方法,（1） 将样本集X(N)随机地划分为s个子集： （2） 用最近邻法，以 为参照集，对Xi中的样本进行分类，其中i =1,2,s; （3）去掉（2）中被错误分类的样本； （4）用所留下的样本构成新的样本集X(NE)； （5）如果经过k 次迭代再没有样本被剪辑掉则停止；否则转至（1）。,MULTIEDIT算法,剪辑最近邻方法 6.2.3 重复剪辑最近邻方法,妈妈新开了个淘宝店，欢迎前来捧场 妈妈的淘宝点开了快半年了，主要卖的是毛绒玩具、坐垫、抱枕之类的，但生意一直不是很好，感觉妈妈还是很用心的，花了不少功夫，但是