非参数判别分类方法.ppt

1、2020/12/5,中国矿业大学 计算机科学与技术学院,(39)1,3.6 近邻法,自动分类的基本方法有两大类,近邻法则在原理上属于模板匹配,（1）将特征空间划分成决策域 （2）模板匹配,近邻法的缺点：计算量大，存储量大,近邻法的优点：在模板数量很大时其错误率指标还是相当不错的。,近邻法的改进方法,2020/12/5,中国矿业大学 计算机科学与技术学院,(39)2,重点,弄清楚近邻法的定义(包括k近邻法)，与基本做法,弄清“近邻法性能好”是在什么意义上讲的。知道渐进平均错误率的定义,快速搜索方法是使用怎样的原理？,剪辑近邻法的原理是什么? 而压缩近邻法与剪辑近邻法有什么不同之处？,2020/1

2、2/5,中国矿业大学 计算机科学与技术学院,(39)3,3.6.1 近邻法原理及其决策规则,近邻法是由Cover和Hart于1968年提出的，随后得到理论上深入的分析与研究，是非参数法中最重要的方法之一。这一节将讨论其基本原理，错误率分析及若干改进方法。,2020/12/5,中国矿业大学 计算机科学与技术学院,(39)4,将与测试样本最近邻样本的类别作为决策的方法称为最近邻法。对一个C类别问题，每类有Ni个样本，i1,C, 则第i类i的判别函数,最近邻法决策规划,其中Xik表示是i类的第k个样本。,如果,则决策Xj,决策规则为：,2020/12/5,中国矿业大学 计算机科学与技术学院,(39)

3、5,基本规则是，在所有N个样本中找到与测试样本的k个最近邻者，其中各类别所占个数表示成ki,i1,c，则决策规划是：,k近邻法决策规划,如果,则决策Xj,k近邻一般采用k为奇数，跟投票表决一样，避免因两种票数相等而难以决策。,2020/12/5,中国矿业大学 计算机科学与技术学院,(39)6,计算错误的偶然性：因为训练样本集的数量总是有限的，有时多一个少一个训练样本对测试样本分类的结果影响很大。,利用训练样本数量增至极大，来对其性能进行评价。,渐近平均错误率,3.6.2 近邻法错误率分析,2020/12/5,中国矿业大学 计算机科学与技术学院,(39)7,如果所用训练样本集的样本数量N极大，即

4、N时，可以想像X将趋向于X，或者说处于以X为中心的极小邻域内，此时分析错误率问题就简化为在X样本条件下X与一个X(X的极限条件)分属不同类别的问题。如果样本X的两类别后验概率分别为P(1|X)与P(2|X)，那么对X值，在N条件下，发生错误决策的概率为：,最近邻法错误率分析,2020/12/5,中国矿业大学 计算机科学与技术学院,(39)8,(3.6-1),2020/12/5,中国矿业大学 计算机科学与技术学院,(39)9,渐近平均错误率，是PN(e)在N的极限。,与基于最小错误率的贝叶斯决策方法对比,其中,而,则,(3.6-2),(3.6-3),2020/12/5,中国矿业大学 计算机科学与

5、技术学院,(39)10,由,可得,上式减去,从式(3.6-5)可见在一般情况下P是大于零的值， 只要P(1|X)P(2|X)0。 有以下两种例外情况P0， 这两种情况是P(1|X)1或P(1|X)P(2|X)1/2。,(3.6-4),(3.6-5),2020/12/5,中国矿业大学 计算机科学与技术学院,(39)11,思考,什么情况下P(1|X)1或P(2|X)=1? P(1|X)= P(2|X)会出现什么什么情况？,答：一般来说，在某一类样本分布密集区，某一类的后验概率接近或等于1。此时，基于最小错误率贝叶斯决策基本没错，而近邻法出错可能也很小。而后验概率近似相等一般出现在两类分布的交界处，

6、此时分类没有依据，因此基于最小错误率的贝叶斯决策也无能为力了，近邻法也就与贝叶斯决策平起平坐了。,2020/12/5,中国矿业大学 计算机科学与技术学院,(39)12,当N时，最近邻法的渐近平均错误率的下界是贝叶斯错误率，这发生在样本对某类别后验概率处处为1的情况或各类后验概率相等的情况。,在其它条件下，最近邻法的错误率要高于贝叶斯错误率，可以证明以下关系式成立。,一般情况下P*很小,最近邻法错误率上下界与贝叶斯错误率的关系,2020/12/5,中国矿业大学 计算机科学与技术学院,(39)13,k近邻法错误率分析,对于两类别问题,k-邻域的情况，则错误出现在k个邻域样本中，正确的类别所占样本未

7、过半数，得到,(3.6-6),2020/12/5,中国矿业大学 计算机科学与技术学院,(39)14,将(3.6-7)与(3.6-6)相比较，(3.6-6)相当于(3.6-7)中k1的情况，而在(3.6-7)中当k增大时PkN(e|X)是单调递减的。因此可以得出结论，在N的条件下，k-近邻法的错误率要低于最近邻法，从图中也可看出，无论是最近邻法，还是k-近邻法，其错误率的上下界都是在一倍到两倍贝叶斯决策方法的错误率范围内。,K-近邻法错误率上下界与贝叶斯错误率的关系,2020/12/5,中国矿业大学 计算机科学与技术学院,(39)15,3.6.3 改进的近邻法,近邻法的严重弱点与问题：需要存储全

8、部训练样本，以及繁重的距离计算量。,改进的方法大致分为两种原理：,（1）对样本集进行组织与整理，分群分层，尽可能将计算压缩到在接近测试样本邻域的小范围内，避免盲目地与训练样本集中每个样本进行距离计算。,（2）在原有样本集中挑选出对分类计算有效的样本，使样本总数合理地减少，以同时达到既减少计算量，又减少存储量的双重效果。,2020/12/5,中国矿业大学 计算机科学与技术学院,(39)16,3.6.3.1 快速搜索近邻法,这种方法着眼于只解决减少计算量，但没有达到减少存储量的要求。其基本思想是将样本集按邻近关系分解成组，给出每组的质心所在，以及组内样本至该质心的最大距离。这些组又可形成层次结构，

9、即组又分子组，因而待识别样本可将搜索近邻的范围从某一大组，逐渐深入到其中的子组，直至树的叶结点所代表的组，确定其相邻关系。为了简单先从最近邻法讨论起。,2020/12/5,中国矿业大学 计算机科学与技术学院,(39)17,首先将整个样本分成l个子集，每个子集又分为它的l个子集。分成子集的原则是该子集内的样本尽可能聚成堆，这可用聚类方法实现。,一、样本集分级分解,结点参数： 树形结构，每个结点表示一样本子集，描述该子集的参数如下。,2020/12/5,中国矿业大学 计算机科学与技术学院,(39)18,树形结构样本集,样本集分解举例,2020/12/5,中国矿业大学 计算机科学与技术学院,(39)

10、19,要实现快速搜索近邻，需要有方法快速判断某个样本子集是否是该待识样本的可能近邻样本集，从而可将无关的样本子集尽快排除。另一方面在某样本子集内寻找哪个样本是近邻时，需快速排除不可能为近邻的样本。这两个快速判别算法可用以下两个规则表示：,二、快速搜索算法,规则1：,则Xip不可能是X的近邻。其中B是待识别样本在搜索近邻过程中的当前近邻距离，B在搜索过程中不断改变与缩小。算法开始可将B设为无穷大。D(X,Mp)表示待识样本X到结点p的均值点距离。,如果存在B+rp D(X,Mp),2020/12/5,中国矿业大学 计算机科学与技术学院,(39)20,这个规则的证明是显而易见的，下图表示一待识样本

11、及其当前近邻与一样本子集的关系。,判断某子集是否可能为最近邻,2020/12/5,中国矿业大学 计算机科学与技术学院,(39)21,规则2：,则Xi不可能是X的近邻。,规则2的证明同规则1，不再赘述。由此可见，只要将每个样本子集p中的每个样本Xi到其均值Mp的距离D(Xi,Mp)存入存储器中，就可利用上式将许多不可能成为测试样本近邻的训练样本排除。,如果B+D(Xi,Mp) D(X,Mp), 其中Xip,2020/12/5,中国矿业大学 计算机科学与技术学院,(39)22,当搜索树形样本集结构由高层次向低层次深入时，对同一层次的所有结点，可以利用规则1排除掉一些不可能包含待识别样本的近邻的结点

12、(样本子集)。但是这往往不能做到只留下唯一的待搜索结点，因此必须选择其中某一结点先深入搜索，以类似于深度优先的方法确定搜索路径直至叶结点。然而在该叶结点中找到的近邻并不能保证确实是全样本集中的最近邻者，所找到的该近邻样本需要在那些有可能包含最近邻的样本子集中核对与修正，直至找到真正的最近邻样本为止。,搜索算法的大体过程,2020/12/5,中国矿业大学 计算机科学与技术学院,(39)23,步骤1：初始化置B，L1(当前层次)，p0(确定当前结点)。,步骤2：设置后选待搜索结点把当前结点的所有直接后继结点放入层的一目录表中，并对这些结点计算D(X，Mp)。,步骤3：排除无关结点对层目录表中的每个

13、结点P，用规则1将与近邻无缘的结点从目录表中清除。,步骤4：路径选择如该层次目录表中有不止一个结点，选其中D(X，Mp)最小者，将该结点从目录表中删除，如该结点是叶结点转步骤5，如不是叶结点，则LL+1，转步骤2；如该层次目录表中无结点待搜索，则LL-1，如L0则停止，否则转步骤3。,2020/12/5,中国矿业大学 计算机科学与技术学院,(39)24,步骤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被检验后，

14、转步骤3。,2020/12/5,中国矿业大学 计算机科学与技术学院,(39)25,k-近邻法快速计算是搜索待测样本的k个最近邻，以做到最后在这k个最近邻中计算占多数的训练样本类别。因此只要发现有一个训练样本比当前第k个近邻的距离要小，就把当前第k个近邻剔除出当前k近邻组。,k近邻法的快速搜索算法,k-近邻法的快速计算法与上述过程大体相同，只是B值修改为当前第k个近邻的距离值。然后在步骤5中，对所计算的距离要与该k个当前的近邻比较，若比其中某个距离小，则删除最大者。除了以上两点修正外，其它算法与最近邻快速算法一样。,以上是快速算法的原理与计算过程。至于树结构的层次与叶结点内样本个数的选择在设计时

15、根据中间结点计算与叶结点计算的综合平衡考虑。,2020/12/5,中国矿业大学 计算机科学与技术学院,(39)26,3.6.3.2 剪辑近邻法,剪辑近邻法着眼于如何减少模板样本数目，从而可同时减少分类时的计算量及模板样本的存储量，同时还能进一步改进分类器的性能，如降低错误率等要求。,剪辑近邻法除了在样本数量上有一定程度的减少外，更主要的优点是错误率的降低。,2020/12/5,中国矿业大学 计算机科学与技术学院,(39)27,当不同类别的样本在分布上有交迭部分的，分类的错误率主要来自处于交迭区中的样本。当我们得到一个作为识别用的参考样本集时，由于不同类别交迭区域中不同类别的样本彼此穿插，导致用

16、近邻法分类出错。因此如果能将不同类别交界处的样本以适当方式筛选，可以实现既减少样本数又提高正确识别率的双重目的。为此可以利用现有样本集对其自身进行剪辑。下面以两类别问题为例说明这种方法的原理。,剪辑近邻法的基本思想,2020/12/5,中国矿业大学 计算机科学与技术学院,(39)28,假设现有一个样本集N，样本数量为N。将此样本集分成两个互相独立的样本子集。一个被当作考试集NT，另一个作为参考集NR，数量分别为NT与NR，NT+NRN。将NT中的样本表示成Xi,(i=1,2, NT)，而在NR中的样本表示为Yj,(j=1,2, NR)。,剪辑近邻法,一个样本集分成两个相互独立的样本子集是指，分

17、完以后的两个子集具有相同的分布，例如将一个样本集分成两个相互独立的对等子集，则在每个特征空间的子区域，两个子集都有相同的比例，或说各类数量近似相等。要注意指出的是每个子区域(从大空间到小空间)实际做时要用从总的集合中随机抽取的方式进行。,2020/12/5,中国矿业大学 计算机科学与技术学院,(39)29,首先对NT中每一个Xi在NR中找到其最近邻的样本Yi(Xi)，用Yi(Xi)表示Yi是Xi的最近邻参考样本。如果Yi与Xi不属于同一类别，则将Xi从NT中删除，最后从NT中得到一个经过剪辑的样本集，称为剪辑样本集NTE。 NTE可用来取代原样本集N，作为参考样本集对待识别样本进行分类。,剪辑

18、的过程,NT经过剪辑后，要作为新的训练样本集，则NR是对其性能进行测试的样本，如发现NT中的某个训练样本对分类不利，就要把它剪辑掉。,2020/12/5,中国矿业大学 计算机科学与技术学院,(39)30,剪辑样本的过程也可以用k-近邻法进行。,剪辑近邻法也可用到多类别情况。,剪辑过程也可不止一次，重复多次的称为重复剪辑近邻法。,2020/12/5,中国矿业大学 计算机科学与技术学院,(39)31,1. 将样本集N随机划分为S个子集，即,重复剪辑法步骤,N=1, 2, S, S=3,2. 用最近邻法，以j,j=(i+1)mod S为参考集，对i中的样本进行分类，其中i1,S。,3. 去掉步骤2中

19、被错分类的样本。,4. 用所有留下的全部样本的构成新的样本集NE 。,5. 如该次剪辑过程中没有样本被删除，则停止，否则转步骤1。,2020/12/5,中国矿业大学 计算机科学与技术学院,(39)32,从图1到图4可以看出,剩下的样本集形成了两个很好的聚类,并且在每个聚类中的样本都属于同一类.,MULTIEDIT算法实验,图1 原始样本集,图2 经一次迭代的结果,2020/12/5,中国矿业大学 计算机科学与技术学院,(39)33,图3 经三次迭代的结果,图4 算法终止时留下的样本,动画演示,2020/12/5,中国矿业大学 计算机科学与技术学院,(39)34,1. 利用最近邻法剪辑后得到的样

20、本集进行分类，其错误率总小于原样本集，如用P1E(e)表示其错误率，则有,剪辑近邻法错误率的分析,其中P(e)表示用原样本的渐近平均错误率。,由于近邻法错误率上界为2P*(两倍贝叶斯错误率)，因而,在P(e)很小，如P(e)0.1情况下可有,2020/12/5,中国矿业大学 计算机科学与技术学院,(39)35,2. 利用k-近邻法进行剪辑得到的样本集进行分类，则在N及k，且K/N0的条件下有,该式表明k很大时，剪辑样本法的错误率可收敛于最优情况P*。当然实际上k值不能取得太大。,3.多类情况，剪辑效果更好。,2020/12/5,中国矿业大学 计算机科学与技术学院,(39)36,3.6.3.3 压缩近邻法,剪辑近邻法所得到的剪辑样本集在样本数量的压缩方面并不十分明显，它的作用在于将原样本集中处于边界处的样本删除掉，但靠近两类中心的大部分样本仍被保留下来。,然而按近邻规则来看，这些样本