模式识别-第8讲-近邻法

模式识别授课教师薛耀红[e-mail]第8讲近邻法本节课主要内容1最近邻法2k－近邻法3改进的近邻法3.1快速搜索近邻法3.2剪辑近邻法3.3压缩近邻法4最佳距离度量近邻法回顾最简单的分段线性分类器：把各类划分为若干子类，以子类中心作为类别代表点，考查新样本到各代表点的距离并将它分到最近的代表点所代表的类。极端情况，将所有样本都作为代表点－－－－近邻法1最近邻法问题描述:特征向量类别X=(0.1,0.1)?特征向量类别(0.1,0.2)W1(0.2,0.1)W1(0.4,0.5)W2(0.5,0.4)W21最近邻法最小距离分类器：将各类训练样本划分成若干子类，并在每个子类中确定代表点，一般用子类的质心或邻近质心的某一样本为代表点。测试样本的类别则以其与这些代表点距离最近作决策。该法的缺点是所选择的代表点并不一定能很好地代表各类，其后果将使错误率增加。最近邻法的基本思想：以全部训练样本作为“代表点”，计算测试样本与这些“代表点”，即所有样本的距离，并以最近邻者的类别作为决策。近邻法是由Cover和Hart于1968年提出的，随后得到理论上深入的分析与研究，是非参数法中最重要的方法之一。1最近邻法将与测试样本最近邻样本的类别作为决策的方法称为最近邻法。1最近邻法1最近邻法在二维情况下，最近邻规则算法使得二维空间被分割成了许多Voronoi网格，每一个网格代表的类别就是它所包含的训练样本点所属的类别。最近邻法的错误率最近邻法的错误率是比较难计算的，这是因为训练样本集的数量总是有限的，有时多一个少一个训练样本对测试样本分类的结果影响很大。红点表示A类训练样本，蓝点表示B类训练样本，而绿点O表示待测样本。假设以欧氏距离来衡量，O的最近邻是A3，其次是B1，因此O应该属于A类；但若A3被拿开，O就会被判为B类。最近邻法的错误率这说明计算最近邻法的错误率会有偶然性，也就是指与具体的训练样本集有关。同时还可看到，计算错误率的偶然性会因训练样本数量的增大而减小。因此我们就利用训练样本数量增至极大，来对其性能进行评价。这要使用渐近概念，以下都是在渐近概念下来分析错误率的。最近邻法的错误率当最近邻法所使用的训练样本数量N不是很大时，其错误率是带有偶然性的。下图所示为一个在一维特征空间的两类别情况：X表示一待测试样本，而X'是所用训练样本集中X的最邻近者，则错误是由X与X'分属不同的类别所引起的。最近邻法的错误率由于X’与所用训练样本集有关，因此错误率有较大偶然性。但是如果所用训练样本集的样本数量N极大，即N→∞时，可以想像X’将趋向于X，或者说处于以X为中心的极小邻域内，此时分析错误率问题就简化为在X样本条件下X与一个X(X’的极限条件)分属不同类别的问题。如果样本X的两类别后验概率分别为P(ω1|X)与P(ω2|X)，那么对X值，在N→∞条件下，发生错误决策的概率为：最近邻法的错误率而在这条件下的平均错误率P称为渐近平均错误率，是PN(e)在N→∞的极限。为了与基于最小错误率的贝叶斯决策方法对比，下面写出贝叶斯错误率的计算式：其中最近邻法的错误率若是两类问题，则贝叶斯错误率：最近邻法错误率：可见在一般情况下△P是大于零的值，只要P(ω1|X)＞P(ω2|X)＞0。最近邻法的错误率有以下两种例外情况△P＝0：P(ω1|X)＝1P(ω1|X)＝P(ω2|X)＝1/2。最近邻法的错误率请想一下，什么情况下P(ω1|X)＝1或P(ω2|X)=1?P(ω1|X)=P(ω2|X)会出现什么什么情况？一般来说，在某一类样本分布密集区，某一类的后验概率接近或等于1。此时，基于最小错误率贝叶斯决策基本没错，而近邻法出错可能也很小。而后验概率近似相等一般出现在两类分布的交界处，此时分类没有依据，因此基于最小错误率的贝叶斯决策也无能为力了，近邻法也就与贝叶斯决策平起平坐了。从以上讨论可以看出，当N→∞时，最近邻法的渐近平均错误率的下界是贝叶斯错误率，这发生在样本对某类别后验概率处处为1的情况或各类后验概率相等的情况。最近邻法的错误率最近邻法的错误率最近邻法的错误率高于贝叶斯错误率，可以证明以下关系式成立：由于一般情况下P*很小，因此又可粗略表示成：**2PPP可粗略说最近邻法的渐近平均错误率在贝叶斯错误率的两倍之内。***(2)1cPPPPc*P：贝叶斯错误率P：最近邻法错误率小结模式识别（机器自动分类）的基本方法有两大类：I.一类是将特征空间划分成决策域，这就要确定判别函数或确定分界面方程。II.另一种方法则称为模板匹配，即将待分类样本与标准模板进行比较，看跟哪个模板匹配度更好些，从而确定待测试样本的分类。前面讨论的方法可以说都是将特征空间划分为决策域，并用判别函数或决策面方程表示决策域的方法。近邻法则在原理上属于模板匹配。它将训练样本集中的每个样本都作为模板，用测试样本与每个模板做比较，看与哪个模板最相似(即为近邻)，就按最近似的模板的类别作为自己的类别。作业：1、什么是模式与模式识别？2、一个典型的模式识别系统主要由哪几个部分组成？3、什么是后验概率？4、描述贝叶斯公式及其主要作用。5、请详细写出感知器训练算法步骤。6、请详细写出Fisher算法实现步骤。2k－近邻法k-近邻法:最近邻法的扩展，其基本规则是，在所有N个样本中找到与测试样本的k个最近邻者，其中各类别所占个数表示成ki,i＝1，…，c。判别函数为：gi(x)=ki,i=1,2,…,c。决策规则为：()max(),1,...,jiigxgxic。k-近邻一般采用k为奇数，跟投票表决一样，避免因两种票数相等而难以决策。2k－近邻法从样本点x开始生长，不断扩大区域，直到包含进k个训练样本点为止，并且把测试样本点x的类别归为这最近的k个训练样本点中出现频率最大的类别。K近邻法的错误率对于最近邻法PN(e|x,x’)＝P(ω1|x)P(ω2|x’)+P(ω2|x)P(ω1|x’)当N-∞时，P(ωi|x’)近似等于P(ωi|x)PN-∞(e|x,x’)＝P(ω1|x)P(ω2|x)+P(ω2|x)P(ω1|x)对于K近邻法(1)/21120(1)/22210(|)(|)(|)(|)+(|)(|)(|)kkjjkjNkjkjjkjkjPexPxCPxPxPxCPxPxK近邻法的错误率对所有的x，有：PN-∞k(e|x)≤Ck[P*(e|x)](Ck[P*(e|x)]为贝叶斯条件错误率的函数)根据Jensen不等式,P=E[PNk(e|x)]≤E{Ck[P*(e|x)]}≤CkE{[P*(e|x)]}=Ck(P*)不等式关系P*≤P≤Ck(P*)≤Ck-1(P*)≤…≤C1(P*)≤2P*(1-P*)k－近邻法的错误率最近邻法和k-近邻法的错误率上下界都是在一倍到两倍贝叶斯决策方法的错误率范围内。在k→∞的条件下，k-近邻法的错误率要低于最近邻法。在k→∞的条件下，k-近邻法的错误率等于贝叶斯误差率。*PP3改进的近邻法尽管近邻法有其优良品质，但是它的一个严重弱点与问题是需要存储全部训练样本，以及繁重的距离计算量。但以简单的方式降低样本数量，只能使其性能降低，这也是不希望的。为此要研究既能减少近邻法计算量与存储量，同时又不明显降低其性能的一些改进算法。改进的方法大致分为两种原理。一种是对样本集进行组织与整理，分群分层，尽可能将计算压缩到在接近测试样本邻域的小范围内，避免盲目地与训练样本集中每个样本进行距离计算。另一种原理则是在原有样本集中挑选出对分类计算有效的样本，使样本总数合理地减少，以同时达到既减少计算量，又减少存储量的双重效果。3.1改进的近邻法-快速搜索近邻法这种方法着眼于只解决减少计算量，但没有达到减少存储量的要求。基本思想：•将样本集按邻近关系分解成组，给出每组的质心所在，以及组内样本至该质心的最大距离。这些组又可形成层次结构，即组又分子组。•因而待识别样本可将搜索近邻的范围从某一大组，逐渐深入到其中的子组，直至树的叶结点所代表的组，确定其相邻关系。快速搜索近邻法（1）样本集的分级分解首先将整个样本分成l个子集，每个子集又分为它的l个子集，如此进行若干次就能建立起一个样本集的树形结构。分成子集的原则是该子集内的样本尽可能聚成堆，这可用聚类方法实现。结点参数：树形结构，每个结点表示一样本子集，描述该子集的参数是：快速搜索近邻法用树结构表示样本分级:p:树中的一个结点，对应一个样本子集KpNp:Kp中的样本数Mp:Kp中的样本均值rp:从Kp中任一样本到Mp的最大距离快速搜索近邻法（2）快速搜索算法要实现快速搜索近邻，需要有方法快速判断某个样本子集是否是该待识样本的可能近邻样本集，从而可将无关的样本子集尽快排除;另一方面在某样本子集内寻找哪个样本是近邻时，需快速排除不可能为近邻的样本。这两个快速判别算法可用以下两个规则表示。快速搜索近邻法规则1：如果存在则不可能是X的近邻。其中B是待识别样本在搜索近邻过程中的当前近邻距离，B在搜索过程中不断改变与缩小。算法开始可将B设为无穷大。表示待识样本X到结点的均值点距离。快速搜索近邻法规则2：如果其中Xi∈，则Xi不可能是X的近邻。由此可见，只要将每个样本子集中的每个样本Xi到其均值Mp的距离D(Xi,Mp)存入存储器中，就可利用上式将许多不可能成为测试样本近邻的训练样本排除。快速搜索近邻法（3）搜索算法搜索算法的大体过程是这样的：当搜索树形样本集结构由高层次向低层次深入时，对同一层次的所有结点，可以利用规则1排除掉一些不可能包含待识别样本的近邻的结点(样本子集)。但是这往往不能做到只留下唯一的待搜索结点，因此必须选择其中某一结点先深入搜索，以类似于深度优先的方法确定搜索路径直至叶结点。然而在该叶结点中找到的近邻并不能保证确实是全样本集中的最近邻者，所找到的该近邻样本需要在那些有可能包含最近邻的样本子集中核对与修正，直至找到真正的最近邻样本为止。树搜索算法1.置B=∞，L=0，p=02.将当前结点的所有直接后继结点放入一个目录表中，并对这些结点计算D(x,Mp)3.根据规则1从目录表中去掉step2中的某些结点4.如果目录表已无结点则置L=L-1，如果L=0则停止，否则转Step3。如果目录表有一个以上的结点，则转step55.在目录表中选出最近结点p’为当前执行结点。如果当前的水平L是最终水平，则转Step6，否则置L=L+1，转Step26.对当前执行结点p’中的每个xi，根据规则2决定是否计算D(x,xi)。若D(x,xi)B，则置NN=i和B=D(x,xi)，处理完当前执行结点中的每个xi后转Step3当算法结束时，输出x的最近邻xNN和x与xNN的距离B3.2改进的近邻法-剪辑近邻法目的：去掉靠近两类中心的样本？基本思想：当不同类别的样本在分布上有交迭部分的，分类的错误率主要来自处于交迭区中的样本。当我们得到一个作为识别用的参考样本集时，由于不同类别交迭区域中不同类别的样本彼此穿插，导致用近邻法分类出错。因此如果能将不同类别交界处的样本以适当方式筛选，可以实现既减少样本数又提高正确识别率的双重目的。为此可以利用现有样本集对其自身进行剪辑。3.2改进的近邻法-剪辑近邻法剪辑的过程是：将样本集KN分成两个互相独立的子集：考试（test）集KT和参考（reference）集KR。首先对KT中每一个Xi在参考集KR中找到其最近邻的样本Yi(Xi)。如果Yi与Xi不属于同一类别，则将Xi从考试集KT中删除，最后得到一个剪辑的样本集KTE（剪辑样本集），以取代原样本集，对待识别样本进行分类。剪辑的结果是去掉两类边界附近的样本。MULTIEDIT算法正太分布样本集合正太分布样本集合正太分布样本集合正太分布样本集合非正太分布样本集合非正太分布样本集合非正太分布样本集合3.3改进的近邻法-压缩近邻法压缩近邻法：利用现有样本集，逐渐生成一个新的样本集，使该样