近邻法（2学时）ppt课件.ppt

《近邻法（2学时）ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、哈尔滨工业大学第6章近邻法李君宝1主要内容0.引言1.近邻法原理及其决策规则2.快速搜索近邻法3.剪辑近邻法4.压缩近邻法20.引言3【引言】模式识别或者分类的基本方法有两大类:一类是将特征空间划分成决策域,需要确定判别函数或确定分界面方程。另一类是模板匹配:将待分类样本与标准模板进行比较，看跟哪个模板匹配度更好些，从而确定待测试样本的分类。近邻法在原理上属于模板匹配。它将训练样本集中的每个样本都作为模板，用测试样本与每个模板做比较，看与哪个模板最相似(即为近邻)，就以最近似的模板的类别作为自己的类别。4【引言】近邻法优缺点：1）原理简单、易于实现，在模板数量很大时其错误率低

2、。2）计算量大，存储量大，要存储的模板很多，每个测试样本要对每个模板计算一次相似度。51.近邻法原理及其决策规则6【基本原理】背景：最小距离分类器是将各类训练样本划分成若干子类，并在每个子类中确定代表点，一般用子类的质心或邻近质心的某一样本为代表点。测试样本的类别则以其与这些代表点距离最近作决策。该法的缺点是所选择的代表点并不一定能很好地代表各类,后果将使错误率增加。近邻法的基本思想：一种极端的情况是以全部训练样本作为“代表点”，计算测试样本与这些“代表点”，即所有样本的距离，并以最近邻者的类别作为决策。7【最近邻法决策规则】若则其中表示是类的第个样本。决策规则为:定义：将与

3、测试样本最近邻样本类别作为决策的方法。对一个类别问题，每类有个样本，，则第类的判别函数8【最近邻法决策规则】用‖·‖表示距离，采用任何一种相似性的度量，一般以欧氏距离为相似性度量。由于特征向量各个分量之间对应的物理意义很可能不一致，因此究竟采用何种相似性度量要看问题而定。计算量：最近邻法在原理上最直观，方法上也十分简单，只要对所有样本进行次距离运算，然后以最小距离者的类别作决策。9最近邻法可以扩展成找测试样本的个最近样本作决策依据的方法。其基本规则是，在所有个样本中找到与测试样本的个最近邻者；其中各类别所占个数表示成则决策为：【-近邻法决策规则】注意：近邻一般采用为奇数，跟投

4、票表决一样，避免因两种票数相等而难以决策。若则10错误率：【近邻法的错误率】由于一般较小，忽略上式中的二次项得到：近邻法错误率在贝叶斯错误率和两倍贝叶斯错误率之间。11【存在的问题】存在的问题：1）需要存储全部训练样本，以及繁重的距离计算量。2）以简单的方式降低样本数量，只能使其性能降低。为此要研究既能减少近邻法计算量与存储量，同时又不明显降低其性能的一些改进算法。改进算法大致基于两种原理。1）对样本集进行组织与整理，分群分层，尽可能将计算压缩到在接近测试样本邻域的小范围内，避免与训练样本集中每个样本进行距离计算。2）原有样本集中挑选出对分类计算有效的样本，使样本总数合理地减

5、少，以同时达到既减少计算量，又减少存储量的双重效果。122.快速搜索近邻法13【基本思想】基本思想：将样本集按邻近关系分解成组，给出每组的质心、组内样本至质心的最大距离。这些组又可形成层次结构，即组又分子组，因而待识别样本可将搜索近邻的范围从某一大组，逐渐深入到其中的子组，直至树的叶结点所代表的组，确定其相邻关系。特点：这种方法着眼于解决减少计算量，但没有达到减少存储量的要求。14【样本集分级分解】：结点对应的样本子集：样本子集中的样本数目：样本子集中的样本均值：从到的最大距离思路：先对样本集进行分级分解，形成树结构，然后利用搜索算法找出最近邻。步骤：将整个样本分成l个子集，

6、每个子集又分为它的l个子集，如此进行若干次就能建立起一个样本集的树形结构。子集分解的原则是该子集内的样本尽可能聚成堆。结点参数:树形结构，每个结点表示一样本子集，描述该子集的参数是：15【样本集分级分解示例】16【样本集搜索规则】规则1：如果成立，则不可能是的最近邻。规则2：如果成立，其中，则不可能是的最近邻。：当前已经涉及到的样本集中的样本到的最近距离。17【搜索算法的基本思想】搜索算法过程：当搜索树形样本集结构由高层次向低层次深入时，对同一层次的所有结点，可以利用规则1排除掉一些不可能包含待识别样本的近邻的结点(样本子集)。但是这往往不能做到只留下唯一的待搜索结点，因此必

7、须选择其中某一结点先深入搜索，以类似于深度优先的方法确定搜索路径直至叶结点。然而在该叶结点中找到的近邻并不能保证确实是全样本集中的最近邻者，所找到的该近邻样本需要在那些有可能包含最近邻的样本子集中核对与修正，直至找到真正的最近邻样本为止。18【讨论】分级数目增多，结点增多，最终结点对应的样本数减少。分级数目增少，结点增少，最终结点对应的样本数增多。推广到-近邻193.剪辑近邻法20【概念的提出】以上讨论的快速算法只是研究如何减少计算量的问题，而不考虑存储量的压缩。实际上由于对样本进行分层次分组，并附有一