6.0引言 口最小距离分类器：将各类训练样本划分成若千子 类，并在每个子类中确定代表点。待测样本的类 第六章近邻法 别则以其与这些代表点距离最近作决策。该方法 的缺点是所选择的代表点并不一定能很好地代表 各类，其后果将使错误率增加。 2009-11-17 6.0引言 6.1最近邻法 口最小距离分类器：将各类训练样本划分成若千子 ▣最近邻法nearest neighborhood classifier(NNC): 类，并在每个子类中确定代表点。待测样本的类 将与测试样本最近邻样本的类别作为决策的结果。 别则以其与这些代表点距离最近作决策。该方法 口对一个C类别问题，每类有N,个样本，则第类 的缺点是所选择的代表点并不一定能很好地代表 ⊙的判别函数为： 各类，其后果将使错误率增加。 g(x)=minxk=1...N, 口近邻法：是最小距离分类器的一种极端情况，以 全部训练样本作为代表点，计算待测样本与所有 样本的距离，并以最近邻者的类别作为决策。 Ⅱ·‖表示某种距离（相似性）度 口最初的近邻法是由Cover和Hart于l968年提出 量，常用欧氏距离作为相似性度量。 的，随后得到理论上深入的分析与研究，是非参 B 数法中最重要的方法之一。 B B 6.1最近邻法 6.1最近邻法 口最近邻法nearest neighborhood classifier(NNC): 口最近邻法的错误率分析 将与测试样本最近邻样本的类别作为决策的结果。 口对一个C类别问题，每类有N,个样本，则第类 ω，的判别函数为： Pw g.(x)=minx k=1N 口决策规则： if g (x)=ming,(x)then xe,; 口最近邻法在原理上最直观，方法上也十分简单； 明显的缺点就是计算量大，存储量大
第六章 近邻法 2009-11-17 2 6.0 引言 最小距离分类器: 将各类训练样本划分成若干子 类，并在每个子类中确定代表点。待测样本的类 别则以其与这些代表点距离最近作决策。该方法 的缺点是所选择的代表点并不一定能很好地代表 各类，其后果将使错误率增加。 3 6.0 引言 最小距离分类器: 将各类训练样本划分成若干子 类，并在每个子类中确定代表点。待测样本的类 别则以其与这些代表点距离最近作决策。该方法 的缺点是所选择的代表点并不一定能很好地代表 各类，其后果将使错误率增加。 近邻法: 是最小距离分类器的一种极端情况，以 全部训练样本作为代表点，计算待测样本与所有 样本的距离，并以最近邻者的类别作为决策。 最初的近邻法是由 Cover 和 Hart 于1968年提出 的，随后得到理论上深入的分析与研究，是非参 数法中最重要的方法之一。 4 6.1 最近邻法 最近邻法 nearest neighborhood classifier (NNC)： 将与测试样本最近邻样本的类别作为决策的结果。 对一个 C 类别问题，每类有 Ni 个样本，则第i类 ωi 的判别函数为： ( ) min , 1,..., , k i ii k g kN x xx ‖·‖表示某种距离（相似性）度 量，常用欧氏距离作为相似性度量。 5 6.1 最近邻法 最近邻法 nearest neighborhood classifier (NNC)： 将与测试样本最近邻样本的类别作为决策的结果。 对一个 C 类别问题，每类有 Ni 个样本，则第i类 ωi 的判别函数为： 决策规则： 最近邻法在原理上最直观，方法上也十分简单； 明显的缺点就是计算量大，存储量大。 ( ) min , 1,..., , k i ii k g kN x xx if ( ) min ( ) then ; ji j i g g x xx 6 6.1 最近邻法 最近邻法的错误率分析
6.1最近邻法 6.1最近邻法 口最近邻法的错误率分析 口最近邻法的错误率分析 ■在此条件下的渐近平均错误率： ■当N→∞时，x的最近邻x将趋向于x P=imP(e)=m」R(elpx)h ■如果样本x的两类别后验概率分别为P(⊙x)与 P(ωx),那么对样本x,在N一∞条件下，发生 =jl-∑p2(a,lpx) 错误决策的概率为： ■基于最小错误率贝叶斯决策的错误率 lim B.(elx)=1->p2(@lx); V-h p'=∫p'(elx)px)dk P'(elx)=1-P(@lx),P(@Ix)=max P(@,lx); 6.1最近邻法 6.1最近邻法 P(w.IX) 口最近邻法的错误率分析 口最近邻法的错误率分析 ■如用图中的例子，则有 ■最近邻法的错误率高于贝叶斯错误率，可以证明 以下关系式成立： P'(elx)=1-P(@,lx), imP(elx)=1-P-(@lx)-P2(@Ix): P'sPsP'(2-C P) -1 a)P()>P(x)>0 其中：P是贝叶斯错误率； AP=lim P(elx)-P'(elx) P,是样本无穷多时最 P(@,Ix)-P(lx)-=1 近邻法的错误率（渐 进平均错误率)。 =P(@:Ix)[P(@lx)-P(@x)=P(lx)=1/2 c.1 11 12 6.1最近邻法 6.2k近邻法 口最近邻法的错误率分析 口k-近邻法：最近邻法的扩展，其基本规则是，在 ■最近邻法的错误率高于贝叶斯错误率，可以证明 所有N个样本中找到与测试样本的k个最近邻 以下关系式成立： 者，其中各类别所占个数表示成k,i=1,,C 定义判别函数为：g()=k,l,2,,C ■由于一般情况下P*很小，因此又可粗略表示成： 口决策规则：j=argmax g,(x),i=l,,c p'≤P≤2P; 即，可粗略说最近邻法的渐近平均错误率在贝叶 口k-近邻一般采用k为奇数，跟投票表决一样，避 斯错误率的两倍之内。 免因两种票数相等而难以决策
7 6.1 最近邻法 最近邻法的错误率分析 当N→∞时，x 的最近邻 x’将趋向于 x； 如果样本 x 的两类别后验概率分别为 P(ω1| x) 与 P(ω2| x)，那么对样本 x ，在N→∞条件下，发生 错误决策的概率为： 2 1 lim ( | )1 ( | ); c N i N i Pe P x x 8 6.1 最近邻法 最近邻法的错误率分析 在此条件下的渐近平均错误率： 基于最小错误率贝叶斯决策的错误率 2 1 lim ( ) lim ( | )() [1 ( | )] ( ) . N N N N c i i P Pe Pe p d P pd x xx x xx * * * (| )() , ( | )1 ( | ), ( | ) max ( | ); mm i i P Pe p d Pe P P P x xx x xx x 9 6.1 最近邻法 最近邻法的错误率分析 如用图中的例子，则有 * 1 2 2 1 2 ( | ) 1 ( | ), lim ( | )1 ( | ) ( | ); N N Pe P Pe P P x x x xx * 2 11 2 21 2 lim ( | ) ( | ) ( | )[1 ( | )] ( | ) ( | )[ ( | ) ( | )]; N N P Pe Pe P PP PP P x x xx x xx x a) P(ω1|x)＞P(ω2| x)＞0 b) P(ω1|x)=1 c) P(ω1|x)= P(ω2|x)=1/2 10 6.1 最近邻法 最近邻法的错误率分析 最近邻法的错误率高于贝叶斯错误率，可以证明 以下关系式成立： 其中：P*是贝叶斯错误率； P1是样本无穷多时最 近邻法的错误率（渐 进平均错误率）。 ** * (2 ), 1 C P PP P C 11 6.1 最近邻法 最近邻法的错误率分析 最近邻法的错误率高于贝叶斯错误率，可以证明 以下关系式成立： 由于一般情况下 P* 很小，因此又可粗略表示成： 即，可粗略说最近邻法的渐近平均错误率在贝叶 斯错误率的两倍之内。 ** * (2 ), 1 C P PP P C * * PP P 2 ; 12 6.2 k-近邻法 k-近邻法: 最近邻法的扩展，其基本规则是，在 所有 N 个样本中找到与测试样本的 k 个最近邻 者，其中各类别所占个数表示成 ki , i＝1,…,c。 定义判别函数为： gi (x) = ki , i=1,2,…,c。 决策规则： k-近邻一般采用 k 为奇数，跟投票表决一样，避 免因两种票数相等而难以决策。 argmax ( ), 1,..., ; i i j gi c x
6.2k近邻法 6.2k近邻法 口k近邻法错误率分析 ■在N一∞的条件下，k-近邻法的错误率要低于最 近邻法。 ■最近邻法和k近邻法的错误率上下界都是在一倍 到两倍贝叶斯决策方法的错误率范围内。 k=1 特定点 k=2 k=3 k=99 贝叶斯误 6.3改进的近邻法 6.3.1快速搜索近邻法 口近邻法的一个严重不足与问题是需要存储全部训 口基本思想：将样本集按邻近关系分解成组，给出 练样本，以及繁重的距离计算量。 每组的质心所在，以及组内样本至该质心的最大 口两类改进的方法： 距离。这些组又可形成层次结构，即组又分子 组，因而待识别样本可将搜索近邻的范围从某一 ■一种是对样本集进行组织与整理，分群分层，尽 大组，逐渐深入到其中的子组，直至树的叶结点 可能将计算压编到在接近测试样本邻域的小范围 所代表的组，确定其相邻关系。这种方法着眼于 内，避免盲目地与训练样本集中每个样本进行距 离计算。 只解决减少计算量，但没有达到减少存储量的要 求 ■另一种则是在原有样本集中挑选出对分类计算有 效的样本，使样本总数合理地减少，以同时达到 口算法包括两个阶段： 既减少计算量，又减少存储量的双重效果。 ■训练样本集的分级分解； ■搜索； 6.3.1快速搜索近邻法 6.3.1快速搜索近邻法 阶段一：训练样本集的分级分解 =708 M-350 ■符号约定 口P树中的一个结点； 口K:p对应一个样本子集； cN2:K,中的样本数； =102 N:=292 口M。:K中的样本均值： 口rp从K,中任一样本到M的最大距离 T。=max D(x,Mn） 玉，CA
13 6.2 k-近邻法 14 6.2 k-近邻法 k-近邻法错误率分析 在 N→∞ 的条件下，k-近邻法的错误率要低于最 近邻法。 最近邻法和 k-近邻法的错误率上下界都是在一倍 到两倍贝叶斯决策方法的错误率范围内。 15 6.3 改进的近邻法 近邻法的一个严重不足与问题是需要存储全部训 练样本，以及繁重的距离计算量。 两类改进的方法： 一种是对样本集进行组织与整理，分群分层，尽 可能将计算压缩到在接近测试样本邻域的小范围 内，避免盲目地与训练样本集中每个样本进行距 离计算。 另一种则是在原有样本集中挑选出对分类计算有 效的样本，使样本总数合理地减少，以同时达到 既减少计算量，又减少存储量的双重效果。 16 6.3.1 快速搜索近邻法 基本思想：将样本集按邻近关系分解成组，给出 每组的质心所在，以及组内样本至该质心的最大 距离。这些组又可形成层次结构，即组又分子 组，因而待识别样本可将搜索近邻的范围从某一 大组，逐渐深入到其中的子组，直至树的叶结点 所代表的组，确定其相邻关系。这种方法着眼于 只解决减少计算量，但没有达到减少存储量的要 求。 算法包括两个阶段： 训练样本集的分级分解； 搜索； 17 6.3.1 快速搜索近邻法 阶段一：训练样本集的分级分解 符号约定 p:树中的一个结点； Kp：p对应一个样本子集； Np：Kp中的样本数； Mp：Kp中的样本均值； rp：从 Kp中任一样本到Mp的最大距离， max ( , ). i p p ip K r D x x M 18 6.3.1 快速搜索近邻法
6.3.1快速搜索近邻法 6.3.1快速搜索近邻法 阶段二：快速搜索算法 阶段二：快速搜索算法 ■规则一：如果满足 ■规则一：如果满足 D(x,M.)>B+rp, D(x,M,)>B+rp 则K,中的样本都不可能是x的最近邻，B是算法 则K,中的样本都不可能是x的最近邻，B是算法 执行中当前到x的最近距离。 执行中当前到x的最近距离。 X现在的近邻 ■规则二：如果满足 D(x,Me) Dx,M)>B+Ds,M)bS∈Kp 则x不是x的最近邻. 6.3.1快速搜索近邻法 6.3.1快速搜索近邻法 树搜索算法（最近邻) 树搜索算法（最近邻) 1.[初始化]置B=∞，L=0(当前层次)，p=0 5.[选择最近结点]在目录表中选出最近结点p (确定当前结点)。 (即D(x,Mp)最小)为当前执行结点。如果当 2. [当前节点展开]把当前结点的所有直接后继结 前的层次L是最终层次，则转step6;否则置 点放入层的一目录表中，并对这些结点计算 L=L+1,转step2。 D(x,M). 6. [检验]对当前执行结点p中的每个X,根据想 3. [检验]对层目录表中的每个结点P,用规则一将 则三决定是否计算D(x,x。若Dx,x)<B,则 与近邻无关的结点从目录表中排除 置N=i和B-=D(x,x),处理完当前执行结点中 的每个x,后转step3. 4.[回溯]如果目录表已无结点，则回到上一层次 (置L=L-1);如L-0则终止，否则转step3. 算法结束时，输出x的最近邻xw和与D(x,Xw)。 如目录表有一个以上的结点，则转step5。 k-近邻法只须修正算法的step6. 2 6.3.2剪辑近邻法 6.3.2剪辑近邻法 口出发点：处在两类交界处或分布重合区的样本可 口剪辑的过程 能误导近邻法决策，应将它们从样本集中去掉。 ■将样本集KW分成两个互相独立的子集：test集 class 1 class 2 KT和reference集KR; ■首先对KT中每一个X在KR中找到其最近邻的 样本y):如果y,与x不属于同一类别，则将 samples removed x从KT中刷除； 口基本思路： from traming set ■最后得到一个剪辑的样本集KTE(剪辑样本集) ■考查样本是否为可能的误导样本： 以取代原样本集，对待识别样本进行最近邻分类。 ■若是则从样本集中去掉一剪辑。 口可扩展到：k-近邻法剪辑、多类情况、重复剪 ■考查方法是通过试分类，认为错分样本为误导样 辑。 本
19 6.3.1 快速搜索近邻法 阶段二：快速搜索算法 规则一：如果满足 则 Kp中的样本都不可能是 x 的最近邻，B是算法 执行中当前到 x 的最近距离。 (, ) , D Br x Mp p 20 6.3.1 快速搜索近邻法 阶段二：快速搜索算法 规则一：如果满足 则 Kp中的样本都不可能是 x 的最近邻，B是算法 执行中当前到 x 的最近距离。 规则二：如果满足 则 xi 不是 x 的最近邻。 (, ) , D Br x Mp p ( , ) ( , ), , D BD K xM x M x p ipi p 21 6.3.1 快速搜索近邻法 树搜索算法（最近邻） 1. [初始化]置 B＝∞，L＝0（当前层次），p＝0 (确定当前结点）。 2. [当前节点展开]把当前结点的所有直接后继结 点放入层的一目录表中，并对这些结点计算 D(x，Mp)。 3. [检验]对层目录表中的每个结点p，用规则一将 与近邻无关的结点从目录表中排除。 4. [回溯]如果目录表已无结点，则回到上一层次 （置 L=L-1）；如 L=0 则终止，否则转 step3。 如目录表有一个以上的结点，则转 step5。 22 6.3.1 快速搜索近邻法 树搜索算法（最近邻） 5. [选择最近结点]在目录表中选出最近结点 p’ （即 D(x, MP’) 最小）为当前执行结点。如果当 前的层次 L 是最终层次，则转 step6；否则置 L=L+1，转 step2。 6. [检验]对当前执行结点 p’ 中的每个 xi ，根据规 则二决定是否计算 D(x, xi )。若 D(x, xi ) < B，则 置 NN=i 和 B= D(x, xi )，处理完当前执行结点中 的每个 xi 后转 step3。 算法结束时，输出x的最近邻xNN和与D(x, xNN )。 k-近邻法只须修正算法的 step6。 23 6.3.2 剪辑近邻法 出发点：处在两类交界处或分布重合区的样本可 能误导近邻法决策，应将它们从样本集中去掉。 基本思路： 考查样本是否为可能的误导样本； 若是则从样本集中去掉 —剪辑。 考查方法是通过试分类，认为错分样本为误导样 本。 24 6.3.2 剪辑近邻法 剪辑的过程 将样本集 KN 分成两个互相独立的子集：test 集 KT 和 reference 集 KR； 首先对 KT 中每一个 xi 在 KR 中找到其最近邻的 样本 yi (xi ) ：如果 yi 与 xi 不属于同一类别，则将 xi 从 KT 中删除； 最后得到一个剪辑的样本集 KTE（剪辑样本集） 以取代原样本集，对待识别样本进行最近邻分类。 可扩展到： k-近邻法剪辑、多类情况、重复剪 辑
6.3.2剪辑近邻法 6.3.2剪辑近邻法 口错误率分析（渐进错误率) 口重复剪释算法(MULTIEDIT) ■用最近邻法剪辑后得到的样本集进行分类，其错 1.将样本集随机划分为S(≥3)个子集，K,,K 误率总小于没有剪辑的最近邻法的错误率，即 2.用最近邻法，以K0=(+1)modS)为参考集， P(e)≤P(e 对K中的样本进行分类，其中i=1,…,S ■用k~近邻法进行剪辑得到的样本集进行分类，则 3.去掉步骤2中被错分类的样本 在N一∞及k∞，且kN一0的条件下有 4.用所有留下的全部样本的构成新的样本集KT。 P(e)=P'; 5.如经k次迭代后，再没有样本被剪辑掉，则停 止；否则转步骤1. ■多类情况，多类剪辑近邻错误率小于两类情况： 每次迭代时都要对现有样本集进行重新随机划 ■重复剪辑：样本足够多时，重复剪辑效果更好。 分，以保证剪辑的独立性。 6.3.4压缩近邻法 原始祥本集 口基本思想：利用现有样本集，逐渐生成一个新的 下的样 一次选 样本集，使该样本集在保留最少量样本的条件 下，仍能对原有样本的全部用最近邻法正确分 类；那么该样本集也能对待识别样本进行分类， 并保持正常识别率。 留下的样 口算法思路：定义两个存储器，一个用来存放即将 第三次选代后 留下的样本 算法终止后 生成的样本集，称为Store;另一存储器则存放 原样本集，称为Grabbag。 0 6.3.4压缩近邻法 6.3.4压缩近邻法 口算法步骤 1. [初始化]Store是空集，原样本集存入Grabbag: 从Grabbag中任意选择一样本放入Store中作 为新样本集的第一个样本。 2. [样本集生成]在Grabbag中取出第i个样本用 Store中的当前样本集按最近邻法分类。若分类 错误，则将该样本从Grabbag转入Store中； 若分类正确，则将该样本放回Grabbag中。 3. [结来过程]若Grabbag中所有样本在执行第二 步时没有发生转入Store的现象，或Grabbag ■在算法终止后，Store中的样本集作为压缩样本 已成空集，则算法终止，否则转入第二步。 集，可用来对待识别样本按最近邻法分类
25 6.3.2 剪辑近邻法 错误率分析（渐进错误率） 用最近邻法剪辑后得到的样本集进行分类，其错 误率总小于没有剪辑的最近邻法的错误率，即 用k-近邻法进行剪辑得到的样本集进行分类，则 在N→∞及k→∞，且 k/N→0 的条件下有 多类情况，多类剪辑近邻错误率小于两类情况； 重复剪辑：样本足够多时，重复剪辑效果更好。 1 ( ) ( ); E P e Pe * () ; E Pe P k 26 6.3.2 剪辑近邻法 重复剪辑算法 (MULTIEDIT) 1. 将样本集随机划分为S (≥3) 个子集，K1,…,KS； 2. 用最近邻法，以 Kj (j = (i+1) mod S)为参考集， 对 Ki 中的样本进行分类，其中i＝1,…,S； 3. 去掉步骤2中被错分类的样本; 4. 用所有留下的全部样本的构成新的样本集 KNT。 5. 如经 k 次迭代后，再没有样本被剪辑掉，则停 止；否则转步骤1。 每次迭代时都要对现有样本集进行重新随机划 分，以保证剪辑的独立性。 27 原始样本集 留下的样本 第一次迭代后 留下的样本 第三次迭代后 留下的样本 算法终止后 28 6.3.4 压缩近邻法 基本思想：利用现有样本集，逐渐生成一个新的 样本集，使该样本集在保留最少量样本的条件 下，仍能对原有样本的全部用最近邻法正确分 类；那么该样本集也能对待识别样本进行分类， 并保持正常识别率。 算法思路：定义两个存储器，一个用来存放即将 生成的样本集，称为 Store；另一存储器则存放 原样本集，称为 Grabbag。 29 6.3.4 压缩近邻法 算法步骤 1. [初始化] Store是空集，原样本集存入Grabbag； 从 Grabbag 中任意选择一样本放入 Store 中作 为新样本集的第一个样本。 2. [样本集生成] 在 Grabbag 中取出第 i 个样本用 Store 中的当前样本集按最近邻法分类。若分类 错误，则将该样本从 Grabbag 转入 Store 中； 若分类正确，则将该样本放回 Grabbag 中。 3. [结束过程] 若 Grabbag 中所有样本在执行第二 步时没有发生转入 Store 的现象，或 Grabbag 已成空集，则算法终止，否则转入第二步。 30 6.3.4 压缩近邻法 在算法终止后，Store 中的样本集作为压缩样本 集，可用来对待识别样本按最近邻法分类
6.3.4压缩近邻法 6.4讨论 口近邻法是典型的非参数法； 口在原理上最直观，方法上也十分简单，明显的缺 点就是计算量大，存储量大。 重复剪辑近邻算法结果 重复剪辑后再用压缩近 邻法的结果
31 6.3.4 压缩近邻法 重复剪辑近邻算法结果 重复剪辑后再用压缩近 邻法的结果 32 6.4 讨论 近邻法是典型的非参数法； 在原理上最直观，方法上也十分简单，明显的缺 点就是计算量大，存储量大