C4：近邻分类.ppt

用近邻函数法进行聚类与分类汤宁SC08023110一．实验原理对应一个样本集中的任意两个样本xi和xj如果xi是xj的第I个近邻点，则定义xi对xj的近邻系数为I，记为d(i,j)=I.定义xi和xj简的近邻函数值为aij=d(i,j)+d(j,i)-2.样本间的近邻函数值越小，彼此越靠近，越相似。

算法步骤如下：1.对于给定待分类的样本集合，计算距离矩阵D：D(i,j)=d(xi,xj)d(xi,xj)为xi和xj的欧式距离。

2.用D计算近邻系数矩阵M，元素Mij为xi对xj的近邻系数。

3.生成近邻函数矩阵L：L(i,j)=Mij+Mji-2并置L对角线上元素为2*N，如果xi和xj有连接，则L(i,j)为连接损失。

4.搜索矩阵L，将每个点与和它有最小近邻函数值的点连接起来，形成初始聚类。

5.对已经分类的各类，计算各类的类内最大距离maxd，类间最小距离mind,如果maxd<mind,则考虑合并类，反之聚类结果合理。

当类数不变时，结束，反之，继续步骤5。

二．结果及分析在给定的样本集合的情况下，由matlab计算得到的初始聚类结果如下图：由图可见，直观上感觉1、2、3、4、5号样本应该归为一类，10、11、12、13、14也应该归为一类，二事实上也是如此，对类进行合并后得到的聚类图示如下：此为最终聚类结果，连在一起的点表示同为一类。

三．附件Matlab程序文件prexp.m,直接运行，按照对话框的提示，返回matlab命令行模式按任意键就可以进行第二步的类合并，结果仍在figure1显示。

Figure1相继显示上述图示结果，程序包含了必要注释。

2012-2013春学期第六讲模式识别引论近邻分类器赵启军四川大学计算机学院分类器•贝叶斯决策（第2、3讲）–随机模式分类；最小错误率、最小风险•判别函数法（第4、5讲）–确定模式分类；线性、非线性•近邻分类器（第6讲）–无参数分类器•支持向量机（第11、12讲）–统计学习理论2基于均值的分段线性判别函数•根据测试样本到各类均值的距离远近来分类如果基于测试样本到各类所有样本的距离远近来分类呢？3近邻分类器•基于距离的分段线性判别函数的极端情况–将各类中的全部样本都作为“代表点”•典型的近邻分类器–最近邻分类器–K近邻分类器–针对计算速度和存储量的改进的近邻分类器45最近邻分类器•问题定义–c 类，第i 类有N i 个样本–对测试样本x 进行分类•决策规则i ki k i N k x x x g ,,2,1||,||min )(L =−=x 到第i 类样本的最小距离ji i j x c i x g x g ω∈==则如果},,2,1|)({min )(L 欧氏距离是最常用的距离度量，其它的如余弦距离、马氏距离、测地距离等6最近邻分类器的错误率•当训练样本数趋向于无穷大时，最近邻分类器的错误率为•上述错误率是渐进意义下的错误率。

实际操作中，样本数总是有限的，最近邻分类器的错误率并不容易计算其中，P *为贝叶斯错误率，c 为类别数)12(***P c c P P P −−≤≤7K 近邻分类器•问题定义–c 类，第i 类有N i 个样本–对测试样本x 进行分类•决策规则类的样本个数个近邻中属于第表示i c i k x g i i K ),,2,1()(L ==j i i j x c i x g x g ω∈==则如果},,2,1|)({max )(L K=1时，就是最近邻分类器K>1时，相当于K 个近邻投票决定测试样本的类别8K 近邻分类器•两类问题中，K一般取奇数，以避免近邻中属于两类的样本数目相等•两类问题K近邻分类器在样本数趋于无穷大时的错误率)1(2***P P P P −≤≤K近邻分类器•K个近邻在投票过程中的重要性相同？•如果用K个近邻到测试样本的距离对其投票进行加权，使得越近的样本权重越大，这就是“模糊K近邻分类器”9近邻分类器的优缺点•近邻分类器是典型的非参数法，其优点是–实现简单–分类结果比较好•近邻分类器的主要缺点是–对计算机的存储量和计算量的要求很大，耗费大量测试时间–没有考虑决策的风险–对其错误率的分析都是建立在渐进理论基础上的10改进的近邻分类器•针对近邻分类器的计算量和存储量比较大的缺点，从两个思路改进近邻分类器•快速搜索近邻–对样本进行组织和整理，搜索近邻只在某些子集中进行，避免对每个样本进行距离计算•剪辑和压缩样本–在原有样本集中挑选出对分类计算有效的样本，使样本总数合理地减少，达到既减少计算量又减少存储量的效果11快速搜索近邻法•算法分成两个阶段–第一阶段：将样本集按照邻近关系分组，每一组再进一步分组，如此形成树状结构–第二阶段：利用搜索算法找到待识别样本的最近邻（或K近邻）•要实现快速搜索近邻，需要快速判断某个样本子集是否是测试样本的可能近邻集，从而可将无关的样本子集尽快排除•在某个样本子集内寻找哪个样本是近邻时，需要快速排除不可能为近邻的样本1213快速搜索近邻法•第一阶段：样本分组（聚类分析）中的样本数结点p N p :中的样本均值结点p M p :其均值的最大距离中的样本到结点 :),(max p M x D r p i X x p p i ∈=中的样本集结点p X p :快速搜索近邻法•第二阶段：搜索近邻–根据两条规则快速排除不含近邻的子集和非近邻样本–规则一：如果子集X p满足B＋r p<D(x,M p)，则该子集中不可能含有测试样本x的近邻–规则二：如果子集X p中的样本x i满足B+D(xi ,Mp)<D(x,Mp)，则该样本不可能是x的近邻–上述规则中B表示测试样本在搜索近邻过程中的当前近邻距离，B在搜索过程中不断改变与缩小。

近邻分类分类器设计一、设计任务对“data3.m”数据，采用剪辑法、压缩法生成参考集，近似描绘其决策面，并用所有数据测试其分类效果。

二、设计原理1、最近邻法最近邻分类器(nearest neighborhood classifier, nnc): 最小距离分类器的一种极端的情况，以全部训练样本作为代表点，计算测试样本与所有样本的距离，并以最近邻者的类别作为决策。

最初的近邻法是由Cover 和Hart 于1968年提出的，随后得到理论上深入的分析与研究，是非参数法中最重要的方法之一。

最近邻法：将与测试样本最近邻样本的类别作为决策的结果。

对一个C 类别问题，每类有 i N 个样本,1,2,i C =，则第i 类i ω的判别函数为：()min ||||,1,2,,k i i i k g x x x k N =-= (1)因此，最近邻决策规则：若 ()min (),1,2,j i i g x g x i c ==(2)则决策 j x ω∈由上可以看出最近邻法在原理上最直观，方法上也十分简单，但明显的缺点就是计算量大，存储量大。

2、k -近邻法k -近邻法即为最近邻法的扩展，其基本规则是，在所有 N 个样本中找到与测试样本的k 个最近邻者，其中各类别所占个数表示成i k ,1,2,i C =，定义判别函数为：(),1,2,i i g x k i c == (3)因此，k -近邻决策规则：若 ()max j i ig x k = (4)则决策 j x ω∈k -近邻一般采用k 为奇数，跟投票表决一样，避免因两种票数相等而难以决策。

决策规则为：arg (),1,,i i j maxg x i c ==3、改进的近邻法近邻法的一个严重问题是需要存储全部训练样本，以及繁重的距离计算量。

从而提出了两类改进的方法：一种是对样本集进行组织与整理，分群分层，尽可能将计算压缩到在接近测试样本邻域的小范围内，避免盲目地与训练样本集中每个样本进行距离计算。