文档介绍：张学工《模式识别》教学课件
第六章其他分类方法
Xuegong Zhang, Tsinghua University
邻不可能在Xp中
,结点p中的样本Xi w X
若 D(x,Mp) B D(Xi,Mp)
则Xi不是X的最近邻
两大步：
.事先把样本子集划分好(比如用 聚类算法), 计算并存储Xp的Mp, rp及D(Xi,Mp)
.用分支定界算法搜索 X的最近邻
Xuegong Zhang, Tsinghua University
张学工《模式识别》教学课件
搜索算法：（最近邻）
1 ° （初始化）
置B = 8,l = 0, p=0 （当前结点）
2° （当前结点展开）
把当前结点的直接子结点放入（当前水平的）一个 目录哀（活动哀）中，对它们计
算并存储D（x,Mp）o
（注意：活动表在每个水平上一个，下文均指当前水平的活动表）
3° （检验）
对活动表中每个结点，若 D（x,Mp）＞ B+rp,则从表中去掉。
（规则1）
11
Xuegong Zhang, Tsinghua University
张学工《模式识别》教学课件
4° （回溯）
若活动表中已无结点，则回到上一级，置 L = L - 1
如L == 0 ,则算法终止；
如L # 0 ,则转3°;
若活动表中有结点，则继续 5\
5。（选择最近结点）
在目录表中选择最近结点（ D（x,Mp）最小），记为p',以它为当前结点，若当前
水平L为最终水平，则转 6%
否则，置L = L+1,转2’。
12
Xuegong Zhang, Tsinghua University
张学工《模式识别》教学课件
6° (检验)
对当前结点P'中的每个为，
若 D(x,Mp)> D(Xi,Mp)+ B,则非最近邻；
否则，计算D(x,xJ,
若 D(x,xJ< B,则置 NN =i , B= D(x,Xi)
p’中所有X被检验过之后，转 3\
算法终止时，输由x的最近邻xnn和D(x, xnn ) = B
(K-近邻时只须修正上述算法的第
(规则2)
60步）
Xuegong Zhang, Tsinghua University
13
张学工《模式识别》教学课件
from traMEg set
剪辑近邻法
基本理解：
处在两类交界处或分布重合区的样本可能误导近邻法决策。
应将它们从样本集中去掉。
基本思路：
考查样本是否为可能的误导样本，
若是则从样本集中去掉 —— 剪辑。
考查方法是通过试分类，认为错分样本为误导样本
14
Xuegong Zhang, Tsinghua University
张学工《模式识别》教学课件
基本做法：
将样本集分为考试集XNT和参考集X NR ： X N = X NT u X NR , X NT n X NR =巾
剪辑：用XNR中的样本对X NT中的样本进行近邻法分类
剪掉XNT中被错分的样本，XNT中剩余样本构成剪辑样本集 X NTE
分类：利用X NTE和近邻法对未知样本 x分类。
思考：
将样本集分为考试集和参考集是为了剪辑的独立性， 但既然样本都是独立的，可否
考虑下面的做法？（借鉴 LOOCV ）
即：对XN中每个Xi,用所有其他样本对它分类，若分错则剪掉。
15
Xuegong Zhang, Tsinghua University
张学工《模式识别》教学课件
错误率分析(渐近错误率)
1,若用最近邻剪辑，用最近邻分类，则错误率
即 pE(e)w P(e)
RE(e|x)二
P(e|x)
2[1 - P(e|x)]
(P(e|x)、P(e)是近邻法的错误率)
当 P(e)很小时，如 P(e) < 0,1 ,则有 P1E(e) = ；P(e)
* _ _ _ 士. . .. . .. .
而P(e) £ 2P ( P为贝叶斯错误率)。
. F . 、 >、、 一 *
故此时R (e)接近P。
16
Xuegong Zhang, Tsinghua University
张学工《模式识别》教学课件
2,若用k近邻剪辑，用最近邻分类，则
PkE(e|x) [e号 片(e|x)
2[1- Pk(e|x)]
当kT8时