7近邻法(2学时)

1哈尔滨工业大学第6章近邻法李君宝20.引言1.近邻法原理及其决策规则2.快速搜索近邻法3.剪辑近邻法4.压缩近邻法30.引言4【引言】模式识别或者分类的基本方法有两大类:一类是将特征空间划分成决策域,需要确定判别函数或确定分界面方程。另一类是模板匹配:将待分类样本与标准模板进行比较，看跟哪个模板匹配度更好些，从而确定待测试样本的分类。近邻法在原理上属于模板匹配。它将训练样本集中的每个样本都作为模板，用测试样本与每个模板做比较，看与哪个模板最相似(即为近邻)，就以最近似的模板的类别作为自己的类别。5【引言】近邻法优缺点：1）原理简单、易于实现，在模板数量很大时其错误率低。2）计算量大，存储量大，要存储的模板很多，每个测试样本要对每个模板计算一次相似度。61.近邻法原理及其决策规则7【基本原理】背景：最小距离分类器是将各类训练样本划分成若干子类，并在每个子类中确定代表点，一般用子类的质心或邻近质心的某一样本为代表点。测试样本的类别则以其与这些代表点距离最近作决策。该法的缺点是所选择的代表点并不一定能很好地代表各类,后果将使错误率增加。近邻法的基本思想：一种极端的情况是以全部训练样本作为“代表点”，计算测试样本与这些“代表点”，即所有样本的距离，并以最近邻者的类别作为决策。8【最近邻法决策规则】若则其中表示是类的第个样本。决策规则为:定义：将与测试样本最近邻样本类别作为决策的方法。对一个类别问题，每类有个样本，，则第类的判别函数9【最近邻法决策规则】用‖·‖表示距离，采用任何一种相似性的度量，一般以欧氏距离为相似性度量。由于特征向量各个分量之间对应的物理意义很可能不一致，因此究竟采用何种相似性度量要看问题而定。计算量：最近邻法在原理上最直观，方法上也十分简单，只要对所有样本进行次距离运算，然后以最小距离者的类别作决策。10最近邻法可以扩展成找测试样本的个最近样本作决策依据的方法。其基本规则是，在所有个样本中找到与测试样本的个最近邻者；其中各类别所占个数表示成则决策为：【-近邻法决策规则】注意：近邻一般采用为奇数，跟投票表决一样，避免因两种票数相等而难以决策。若则11错误率：【近邻法的错误率】由于一般较小，忽略上式中的二次项得到：近邻法错误率在贝叶斯错误率和两倍贝叶斯错误率之间。12【存在的问题】存在的问题：1）需要存储全部训练样本，以及繁重的距离计算量。2）以简单的方式降低样本数量，只能使其性能降低。为此要研究既能减少近邻法计算量与存储量，同时又不明显降低其性能的一些改进算法。改进算法大致基于两种原理。1）对样本集进行组织与整理，分群分层，尽可能将计算压缩到在接近测试样本邻域的小范围内，避免与训练样本集中每个样本进行距离计算。2）原有样本集中挑选出对分类计算有效的样本，使样本总数合理地减少，以同时达到既减少计算量，又减少存储量的双重效果。132.快速搜索近邻法14【基本思想】基本思想：将样本集按邻近关系分解成组，给出每组的质心、组内样本至质心的最大距离。这些组又可形成层次结构，即组又分子组，因而待识别样本可将搜索近邻的范围从某一大组，逐渐深入到其中的子组，直至树的叶结点所代表的组，确定其相邻关系。特点：这种方法着眼于解决减少计算量，但没有达到减少存储量的要求。15【样本集分级分解】：结点对应的样本子集：样本子集中的样本数目：样本子集中的样本均值：从到的最大距离思路：先对样本集进行分级分解，形成树结构，然后利用搜索算法找出最近邻。步骤：将整个样本分成l个子集，每个子集又分为它的l个子集，如此进行若干次就能建立起一个样本集的树形结构。子集分解的原则是该子集内的样本尽可能聚成堆。结点参数:树形结构，每个结点表示一样本子集，描述该子集的参数是：16【样本集分级分解示例】17【样本集搜索规则】规则1：如果成立，则不可能是的最近邻。规则2：如果成立，其中，则不可能是的最近邻。：当前已经涉及到的样本集中的样本到的最近距离。18【搜索算法的基本思想】搜索算法过程：当搜索树形样本集结构由高层次向低层次深入时，对同一层次的所有结点，可以利用规则1排除掉一些不可能包含待识别样本的近邻的结点(样本子集)。但是这往往不能做到只留下唯一的待搜索结点，因此必须选择其中某一结点先深入搜索，以类似于深度优先的方法确定搜索路径直至叶结点。然而在该叶结点中找到的近邻并不能保证确实是全样本集中的最近邻者，所找到的该近邻样本需要在那些有可能包含最近邻的样本子集中核对与修正，直至找到真正的最近邻样本为止。19【讨论】1.分级数目增多，结点增多，最终结点对应的样本数减少。2.分级数目增少，结点增少，最终结点对应的样本数增多。3.推广到-近邻203.剪辑近邻法21【概念的提出】以上讨论的快速算法只是研究如何减少计算量的问题，而不考虑存储量的压缩。实际上由于对样本进行分层次分组，并附有一些参数，实际的存储量还有可能增加。本节如何减少模板样本数目，从而可同时减少分类时的计算量及模板样本的存储量，同时还能进一步改进分类器的性能，如降低错误率等要求。本节讨论的剪辑近邻法除了在样本数量上有一定程度的减少外，更主要的优点是错误率的降低。22【基本原理】剪辑近邻法的基本思想是从这样一个现象出发的，即当不同类别的样本在分布上有交迭部分的，分类的错误率主要来自处于交迭区中的样本。当我们得到一个作为识别用的参考样本集时，由于不同类别交迭区域中不同类别的样本彼此穿插，导致用近邻法分类出错。因此如果能将不同类别交界处的样本以适当方式筛选，可以实现既减少样本数又提高正确识别率的双重目的。为此可以利用现有样本集对其自身进行剪辑。23【基本步骤】第一步：剪辑利用已知样本集中的样本进行预分类，并剪辑掉被错分的样本，留下的样本构成剪辑样本集。第二步：分类利用剪辑样本集和近邻规则对未知样本进行分类。24【基本步骤】两分剪辑近邻法剪辑：利用参考集的中样本对考试集的每个样本利用最近邻法进行分类决策，剪辑掉那些被参考集中样本错分类的样本，然后将参考集中剩余样本构成剪辑样本集。分类：利用剪辑样本集和最近邻规则对未知样本做分类决策。假定样本集被分为两个独立的样本集-考试集和参考集，分别对应于错误率估计中的考试集和设计集。25【基本步骤】重复剪辑近邻法步骤：（1）将样本集X随机划分为多个子集合X={X1,X2,…,Xs}；（2）用最近邻法,X(i+1)mod(s)作为参考集对集合Xi进行分类；（3）去掉步骤（2）中被错分的样本；（4）用所有留下的样本，构成新的样本集（5）经过k次操作，若没有样本被剪辑掉则停止。前提条件：样本数足够多。26【举例】27【举例】28【举例】29【举例】30【举例】314.压缩近邻法32【问题的提出】剪辑近邻法所得到的剪辑样本集在样本数量的压缩方面并不十分明显，它的作用在于将原样本集中处于边界处样本删除掉，但靠近两类中心大部分样本仍被保留下来。按近邻规则来看，这些样本中的大多数对分类决策没什么用处，如能在剪辑的基础上再去掉一部分这样的样本，将有助于进一步缩短计算时间与压缩存储量，这种方法称为压缩近邻法。33【基本思想】压缩近邻法压缩样本的思想很简单，它利用现有样本集，逐渐生成一个新的样本集。使该样本集在保留最少量样本的条件下,仍能对原有样本的全部用最近邻法正确分类，那末该样本集也就能对待识别样本进行分类,并保持正常识别率。该算法的作法也十分简单，它定义两个存储器，一个用来存放即将生成的样本集，称为Store；另一存储器则存放原样本集，称为Grabbag。34【步骤】1.［初始化］Store是空集，原样本集存入Grabbag；从Grabbag中任意选择一样本放入Store中作为新样本集第一个样本。2.［样本集生成］在Grabbag中取出第i个样本用Store中的当前样本集按最近邻法分类。若分类错误，则将该样本从Grabbag转入Store中，若分类正确，则将该样本放回Grabbag中，对Grabbag中所有样本重复上述过程。3.［结束过程］若Grabbag中所有样本在执行第二步时没有发生转入Store的现象，或Grabbag已成空集，则算法终止，否则转入第二步。35【举例】剪辑样本经压缩近邻法生成的压缩样本集。从中可看出样本的数量极大地减少了。图中还画出了贝叶斯分界面与压缩后的近邻法决策面，它虽然比剪辑样本的近邻产生的决策面偏离贝叶斯决策面要大些，但所需样本数量却大大减少了，因此可以大大节省存储量。36【本章小结】几个要点：(1)弄清楚近邻法的定义以及基本做法。(2)弄清“近邻法性能好”是在什么意义上讲的？(3)快速搜索方法是使用怎样的原理？(4)剪辑近邻法的原理是什么?而压缩近邻法与剪辑近邻法有什么不同之处？•有7个二维向量:x1=[1;0],x2=[0;1],x3=[0;-1],x4=[0;0],x5=[0;2],x6=[0;-2],x7=[-2;0]其中前三个属于w1类，后四个属于w2类。请画出最近邻法决策面。37【课后习题】38本章结束