模式识别 第5章 近邻法

第5章 近邻法

武汉大学电子信息学院

模式识别与神经网络 Pattern Recognition and Neural Network第五章 近邻法

第5章 近邻法

模式识别与神经网络

内容目录5.0 引言 5.1 最近邻法 5.2 k-近邻法 5.3 改进的近邻法 5.4 讨论

第五章 近邻法

第5章 近邻法

5.0 引言最小距离分类器: 最小距离分类器: 它将各类训练样本划分成若干 子类，并在每个子类中确定代表点。测试样本的 类别则以其与这些代表点距离最近作决策。该方 法的缺点是所选择的代表点并不一定能很好地代 表各类，其后果将使错误率增加。 近邻法: 近邻法: 最小距离分类器的一种极端的情况，以 全部训练样本作为代表点，计算测试样本与所有 样本的距离，并以最近邻者的类别作为决策。 最初的近邻法是由Cover和Hart于1968年提出的， 最初的近邻法是由Cover和Hart于1968年提出的， 随后得到理论上深入的分析与研究，是非参数法 中最重要的方法之一。

第五章 近邻法

第5章 近邻法

5.1 最近邻法最近邻法：nearest 最近邻法：nearest neighborhood classifier (nnc),将与测试 (nnc),将与测试 样本最近邻样本的类别作为决策的结果。 对一个C类别问题，每类有N 个样本，i 对一个C类别问题，每类有Ni个样本，i=1,…,C,则第i ,则第i 类ωi的判别函数为：

gi ( x ) = min x x i k , k = 1,..., N ik

决策规则：

if g j ( x ) = min gi ( x ) then x ∈ ω ji

最近邻法在原理上最直观，方法上也十分简单，明显的缺 点就是计算量大，存储量大。 ‖·‖表示某种距离(相似性)度量，常用欧氏距离作为相 似性度量。

第五章 近邻法

第5章 近邻法

最近邻法错误率分析最近邻法的错误率高于贝 叶斯错误率，可以证明以 下关系式成立：* *

NNC

C P ≤ P ≤ P (2 P* ) C 1

由于一般情况下P 由于一般情况下P*很小， P* ≤ P ≤ 2 P* 因此又可粗略表示成： 可粗略说最近邻法的渐 近平均错误率在贝叶斯 错误率的两倍之内

第五章 近邻法

第5章 近邻法

5.2 k-近邻法k-近邻法: 最近邻法的扩展，其基本规则是， 近邻法: 最近邻法的扩展，其基本规则是， 在所有N个样本中找到与测试样本的k 在所有N个样本中找到与测试样本的k个最 近邻者，其中各类别所占个数表示成ki, i= 近邻者，其中各类别所占个数表示成k )=k 1,…,c。定义判别函数为： gi(x)=ki, i=1, 定义判别函数为： 2,…,c 2,…,c。 决策规则为：j = argmax gi ( x ), i = 1,..., ci

k-近邻一般采用k为奇数，跟投票表决一样， 近邻一般采用k 避免因两种票数相等而难以决策。第五章 近邻法6

第5章 近邻法

k-近邻法错误率分析

kNN

在N→∞的条件下，k-近邻法的错误率要低于最近 →∞的条件下，k 邻法。 最近邻法和k 最近邻法和k-近邻法的错误率上下界都是在一倍 到两倍贝叶斯决策方

法的错误率范围内。

第五章 近邻法

第5章 近邻法

5.3 改进的近邻法近邻法的一个严重不足与问题是需要存储全 近邻法的一个严重不足与问题是需要存储全 部训练样本，以及繁重的 部训练样本，以及繁重的距离计算量。 量。 两类改进的方法： 一种是对样本集进行组织与整理，分群分层， 尽可能将计算压缩到在接近测试样本邻域的小 范围内，避免盲目地与训练样本集中每个样本 进行距离计算。 另一种则是在原有样本集中挑选出对分类计算 有效的样本，使样本总数合理地减少，以同时 达到既减少计算量，又减少存储量的双重效果。

第五章 近邻法

第5章 近邻法

快速搜索近邻法快速搜索近邻法，包括两个阶段：1. 样本集的分级分解 2. 搜索

改进 方法

其基本思想是将样本集按邻近关系分解成组，给 其基本思想是将样本集按邻近关系 ，给 出每组的质心所在，以及组内样本至该质心的 出每组的 所在，以及组内样本至该质心的最 大距离。这些组又可形成层次结构，即组又分子 。这些组又可形成层次结构，即组又分子 组，因而待识别样本可将搜索近邻的范围从某一 大组，逐渐深入到其中的子组，直至树的叶结点 所代表的组，确定其相邻关系。这种方法着眼于 只解决减少计算量，但没有达到减少存储量的要 求。第五章 近邻法9

第5章 近邻法

样本集的层次结构用树结构表示样本分 级: p: 树中的一个结点， 对应一个样本子集K 对应一个样本子集Kp Np : Kp中的样本数 Mp : Kp中的样本均 值 rp : 从Kp中任一样本 到Mp的最大距离

第五章 近邻法

第5章 近邻法

减少计算的规则规则1 规则1: D 如果满足： (x, M p ) > B + rp 则Kp中的样本都不可能是 x的最近邻，B是算法执行 的最近邻，B 中当前到x 中当前到x的最近距离 规则2 规则2: 如果满足： D(x, M p ) > B + D(xi , M p ) 则xi不是x的最近邻 不是x

改进 方法

第五章 近邻法

第5章 近邻法

树搜索算法1. 2.

改进 方法

3. 4.

5.

6.

置B=∞,L=0,p=0 =0, 将当前结点的所有直接后继结点放入一个目录表中，并 对这些结点计算D 对这些结点计算D(x,Mp) 根据规则1从目录表中去掉step2中的某些结点 根据规则1从目录表中去掉step2中的某些结点 如果目录表已无结点则置L 如果目录表已无结点则置L=L-1,如果L=0则停止，否则 如果L=0则停止，否则 转Step3。如果目录表有一个以上的结点，则转step5 Step3。如果目录表有一个以上的结点，则转step5 在目录表中选出最近结点p 在目录表中选出最近结点p’为当前执行结点。如果当前 的水平L是最终水平，则转Step6,否则置L +1,转 的水平L是最终水平，则转Step6,否则置L=L+1,转 Step2 对当前执行结点p 中的每个x ,根据规则2 对

当前执行结点p’中的每个xi,根据规则2决定是否计算 D(x, xi)。若D(x, xi)<B,则置NN=i和B= D(x, xi),处理完 )<B,则置NN= 当前执行结点中的每个x 后转Step3 当前执行结点中的每个xi后转Step3 当算法结束时，输出x的最近邻xNN和与xNN的距离B 第五章 近邻法12

第5章 近邻法

剪辑近邻法

改进 方法

剪辑近邻法：其基本思想是，利用现有 ：其基本思想是，利用现有 样本集对其自身进行剪辑，将不同类别 样本集对其自身进行剪辑， 交界处的样本以适当方式筛选，可以实 ，可以实 现既减少样本数又提高正确识别率的双 重目的。

第五章 近邻法

第5章 近邻法

剪辑近邻法

改进 方法

剪辑的过程是：将样本集K 剪辑的过程是：将样本集KN分成两个 互相独立的子集：test集 互相独立的子集：test集KT和reference 集KR。首先对KT中每一个Xi在KR中找 。首先对K 中每一个X 。如果Y 到其最近邻的样本Y 到其最近邻的样本Yi(Xi) 。如果Yi与Xi 不属于同一类别，则将X 不属于同一类别，则将Xi从KT中删除， 最后得到一个剪辑的样本集K 最后得到一个剪辑的样本集KTE(剪辑 样本集),以取代原样本集，对待识别 ),以取代原样本集，对待识别 样本进行分类。第五章 近邻法14

第5章 近邻法

压缩近邻法压缩近邻法：利用现有样本集，逐渐 ：利用现有样本集，逐渐 生成一个新的样本集，使该样本集在 保留最少量样本的条件下，仍能对原 有样本的全部用最近邻法正确分类， 那末该样本集也就能对待识别样 …… 此处隐藏：2488字，全部文档内容请下载后查看。喜欢就下载吧 ……