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-近邻法剪辑、多类情况、重复剪 辑