k-近邻法最近邻法的扩展-Read.ppt

模式识别理论及应用Pattern Recognition - Methods and Application 第五章 近邻法 内容目录 5.0 引言 最小距离分类器: 它将各类训练样本划分成若干子类，并在每个子类中确定代表点。测试样本的类别则以其与这些代表点距离最近作决策。该方法的缺点是所选择的代表点并不一定能很好地代表各类，其后果将使错误率增加。 近邻法: 最小距离分类器的一种极端的情况，以全部训练样本作为代表点，计算测试样本与所有样本的距离，并以最近邻者的类别作为决策。 最初的近邻法是由Cover和Hart于1968年提出的，随后得到理论上深入的分析与研究，是非参数法中最重要的方法之一。 5.1 最近邻法 最近邻法：nearest neighborhood classifier (nnc)，将与测试样本最近邻样本的类别作为决策的结果。 对一个C类别问题，每类有Ni个样本，i＝1，…，C，则第i类ωi的判别函数为： 最近邻法错误率分析 最近邻法的错误率高于贝叶斯错误率，可以证明以下关系式成立： 5.2 k-近邻法 k-近邻法: 最近邻法的扩展，其基本规则是，在所有N个样本中找到与测试样本的k个最近邻者，其中各类别所占个数表示成ki, i＝1，…，c。定义判别函数为： gi(x)=ki, i=1, 2,…,c。 k-近邻法错误率分析 在N→∞的条件下，k-近邻法的错误率要低于最近邻法。 最近邻法和k-近邻法的错误率上下界都是在一倍到两倍贝叶斯决策方法的错误率范围内。 5.3 改进的近邻法 近邻法的一个严重不足与问题是需要存储全部训练样本，以及繁重的距离计算量。 两类改进的方法： 一种是对样本集进行组织与整理，分群分层，尽可能将计算压缩到在接近测试样本邻域的小范围内，避免盲目地与训练样本集中每个样本进行距离计算。 另一种则是在原有样本集中挑选出对分类计算有效的样本，使样本总数合理地减少，以同时达到既减少计算量，又减少存储量的双重效果。 快速有哪些信誉好的足球投注网站近邻法 快速有哪些信誉好的足球投注网站近邻法，包括两个阶段： 样本集的分级分解 有哪些信誉好的足球投注网站 其基本思想是将样本集按邻近关系分解成组，给出每组的质心所在，以及组内样本至该质心的最大距离。这些组又可形成层次结构，即组又分子组，因而待识别样本可将有哪些信誉好的足球投注网站近邻的范围从某一大组，逐渐深入到其中的子组，直至树的叶结点所代表的组，确定其相邻关系。这种方法着眼于只解决减少计算量，但没有达到减少存储量的要求。 样本集的层次结构 用树结构表示样本分级: p: 树中的一个结点，对应一个样本子集Kp Np : Kp中的样本数 Mp : Kp中的样本均值 rp : 从Kp中任一样本到Mp的最大距离 减少计算的规则 规则1：如果满足：则Kp中的样本都不可能是x的最近邻，B是算法执行中当前到x的最近距离 树有哪些信誉好的足球投注网站算法 置B=∞，L=0，p=0 将当前结点的所有直接后继结点放入一个目录表中，并对这些结点计算D(x,Mp) 根据规则1从目录表中去掉step2中的某些结点 如果目录表已无结点则置L=L-1，如果L=0则停止，否则转Step3。如果目录表有一个以上的结点，则转step5 在目录表中选出最近结点p’为当前执行结点。如果当前的水平L是最终水平，则转Step6，否则置L=L+1，转Step2 对当前执行结点p’中的每个xi，根据规则2决定是否计算D(x, xi)。若D(x, xi)B，则置NN=i和B= D(x, xi)，处理完当前执行结点中的每个xi后转Step3 剪辑近邻法 剪辑近邻法：其基本思想是，利用现有样本集对其自身进行剪辑，将不同类别交界处的样本以适当方式筛选，可以实现既减少样本数又提高正确识别率的双重目的。 剪辑近邻法 剪辑的过程是：将样本集KN分成两个互相独立的子集：test集KT和reference集KR。首先对KT中每一个Xi在KR中找到其最近邻的样本Yi(Xi) 。如果Yi与Xi不属于同一类别，则将Xi从KT中删除，最后得到一个剪辑的样本集KTE（剪辑样本集），以取代原样本集，对待识别样本进行分类。 压缩近邻法 压缩近邻法：利用现有样本集，逐渐生成一个新的样本集，使该样本集在保留最少量样本的条件下，仍能对原有样本的全部用最近邻法正确分类，那末该样本集也就能对待识别样本进行分类，并保持正常识别率。 压缩近邻算法 定义两个存储器，一个用来存放即将生成的样本集，称为Store；另一存储器则存放原样本集，称为Grabbag。其算法是： 初始化。Store是空集，原样本集存入Grabbag；从Grabbag中任意选择一样本放入Store中作为新样本集的第一个样本。 样本集生成。在Grabbag中取出第i个样本用Store中的当前样本集按最近邻法分类。若分类错误，则将该样本从Grabbag转入Store中，若