《非线性分类器课件》由会员分享，可在线阅读，更多相关《非线性分类器课件（45页珍藏版）》请在金锄头文库上搜索。
1、4.3 近邻法,4.3.1 最近邻法 4.3.2 K-近邻法及错误率分析 4.3.3 减少计算量和存储量的方法,问题的提出及解决,前面利用每一类的“代表点”设计分段线性分类器是最简单而直接的设计方法, 这类方法的缺点是所选择的“代表点”不一定能很好的代表各个类,其结果是使所设计分类器的错误率增加.,需要用其他方法来降低错误率,本章讨论的方法是将各类中全部样本都作为“代表点”的情况,这样的决策方法称为近邻法. 下面我们首先详细介绍一般的近邻法, 然后讨论几种改进的方法.,4.3.1 最近邻法,1 最近邻决策规则,假定有c 个类别1 , 2 , , c 的模式识别问题,每类有标明类别的样本 N i
2、 个, i = 1, 2, , c. 我们可以规定 i 类的判别函数为 g i (x)= min | x xk i | , k= 1, 2, , N i k 其中x k i的下标i 表示 i 类, k表示 i 类N i 个样本中的第k个.,则决策规则可以写为 :,若 g j (x)= min g i (x) , i = 1, 2, , c i,则决策 x j,最近邻法的直观解释相当简单, 就是说对未知样本x, 我们只要比较x与已知样本数为N, 类别为c的样本群之间的欧氏距离, 并决策x与离它最近的样本同类.,如图:假设有N个样本, 被分为3类.,x,则有: x 3,对于未知样本 x, 用最近邻
3、法进行分类.,2 最近邻法的错误率分析,设N个样本下的平均错误率为PN (e), 且样本x的最近邻为x 则, PN (e)= PN (e| x) P(x) d(x) = PN (e| x, x) p(x | x) d x p(x) d(x),我们定义最近邻法的渐进平均错误率P为当N 时, PN (e)的极限, 则有 c P = lim PN (e) = 1- P2 (i| x) p(x) dx N i=1,此时我们可以证明以下关系 P* P P*( 2- c/(c-1) P*) 其中P* 为贝叶斯错误率, c为类数,最近邻法的错误率显然大于或等于贝叶斯错误率P*, 但在某些特定情况下, 可以等
4、于贝叶斯错误率.,均有 P = P*,根据贝叶斯条件错误率, 我们可得以下式子: c 1- P2 (i| x) 2p*(e|x) - c/(c-1)p*(e|x)2 i = 1 (P*)2 p*(e|x)2 p(x)dx,根据以上结果我们可得 P p* 2- c/(c-1) p*,下面用图形来说明最邻近法错误率上下界与贝叶斯错误率的关系,P (c-1)/c,(c-1)/c p*,P=p*,P=p*2-c/(c-1)p*,4.3.2 k-近邻法,k-近邻法是最近邻法的一个推广. 这个方法就是取未知样本x的k个近邻, 看这k个近邻多数属于哪一类, 就把x归为哪一类.,在N个样本中, 若 k1 ,
5、k2 , , kc 分别是k个近邻中属于1, 2, , c的样本数, 则我们可以定义判别函数为:,决策规则为 : 若 g j (x) = max k i,则决策 x j,g i(x) = k i , i= 1, 2, , c,1. k-近邻法决策规则,2. k- 近邻法的错误率分析,将近邻法推广到 k近邻法的一个重要目的就是可以降低决策的错误率, 下面我们先给出一个图形来直观说明一下, x,由最近邻法, 可得 x 1结论, 但似乎不正确,贝叶斯决策面,用k 近邻法决策, x,由于 k2 k1 , 所以 x 2 , 这也和贝叶斯决策面决策的相同.,k = k1+ k2 k2 k1,根据最近邻法错
6、误率分析, 当样本数N 趋于时, P = lim PN (e) N 则有 p*= p = p*2- c/(c-1),下面我们给出当k递增的时候, k-邻近法的错误率p与贝叶斯错误率p*的关系,K=1,K=3,K=7,当k=1时, k-近邻法的错误率对应于最近邻法的错误率. 当k增加时, 上限逐渐靠近下限- 贝叶斯错误率p*, 当k趋于无穷时, 上下限碰在一起, 从而 k-近邻法趋于最优.,近邻法有方法简单的优点, 且 错误率在贝叶斯错误率p*和两倍贝叶斯错误率2p* 之间, 正是近邻法这种优良性质, 使它成为模式分类的重要方法之一.,1 需要将所有样本存入计算机中, 每次决策都要计算识别样本x
7、与全部训练样本之间的距离并进行比较, 因此使得存储量和计算量都很大.,2 虽然在所有情况下, 对未知样本x都可以进行决策, 但当错误代价很大时, 会产生较大的风险.,3 上述分析都是渐进的, 就是说要求样本数 N趋于无穷, 这是在任何实际场合都无法实现的.,?如何解决 ,但是近邻法还存在下列问题,4.3.3 减少计算量和存储量的方法,近邻法的一个缺点就是计算量大, 未知样本x要逐个与全体样本X中每个样本计算欧氏距离. 为了减少计算的次数, 也就是不必计算x到样本集X中每个样本xi 的距离, 只需要计算其中一部分的距离就可以找出最近邻, 于是引出了快速搜索近邻法.,快速近邻法的基本考虑是将样本分
8、级分成一些不相交的子集, 并且在子集的基础上进行搜索.,1 快速搜索算法法,几种算法:快速搜索算法法,剪辑近邻法,压缩近邻法.,1) 最近邻的情况,快速搜索算法分成两个阶段, 第一阶段是将样本集 X 分级分解, 形成树结构. 第二个阶段用搜索算法找出待识样本的最近邻.,第一阶段 : 样本集 X 分级分解,首先将样本集 X 分成l个子集, 每个子集再分成l个子集, 一共将样本集分若干次, 依次下去可以形成一个树结构. 每个结点上对应一群样本. 我们用p表示这样的一个结点.,下面以l=2给出树状结构图,k=0 k=1 k=2,P rp Np,N0,6 r6 N6,5 r5 N5,4 r4 N4,3
9、 r3 N3,1,2,并用下列参数表示p结点对应的样本子集: X p : 结点p对应的样本子集 N p : X p 中的样本数 p : 样本子集 X p 中的样本均值 rp = max D( x i , p ) :从 p 到x i X p 的最大距离 x i Xp,第二阶段 : 搜索 在给出算法之前, 先引出两个规则, 利用它们可以检验未知样本x的最近邻是否在 X p 中,规则1: 如果存在 B + rp D( x , p ) 则 x i X p 不可能是x的最近邻. 其中B是在算法执行过程中, 对于已涉及到的那些样本集X p 中样本到x的最近距离. 初始B可置为 , 以后的B在算法中求得.,
10、下面给出图形来说明:,p,D(x, p ),x,x 现在的近邻,B,我们可以利用这个规则, 不必全部计算 x 到X p 中每个样本x i 的距离, 许多结点p和所对应的样本集X p 就可以被去掉, 从而减少了计算量.,为避免对最终结点中的全部样本计算 D( x, xi )距离, 还需要下面的规则2,xi,B D( x , p ) rp D(x, xi),规则 2: 如果 B + D( xi , p ) D (x , p) 其中 xi X p , 则 xi 不是x的最近邻. 由于D( xi , p ) 在计算rp 中已用到, 并且被存入计算机中, 所以不需要重新计算.,下面给出树搜索算法, 并且
11、结合前面给出的树结构图来分析.,树搜索算法,步骤1 置 B= , k= 0, p=0.,步骤2 将当前结点的所有直接后继结点放入一个目录表中, 并对这些结点计算 D (x , Mp ).,步骤 3 对步骤2中的每个结点p , 根据规则1, 如果有 B + rp D( x , M p ) , 则从目录表里去掉p,步骤 4 如果步骤3 的目录表中已没有结点, 则后退到前 一个水平, 即置 k= k1 . 如果k = 0则停止, 否则转步骤3. 如果目录表中有一个以上的结点存在, 则转步骤5.,步骤 5 在目录表中选择最近结点p , 它使 D (x , p ) 最小化, 并称该p 为当前执行结点,
12、从目录表中去掉P以外的结点. 如果当前的水平k是最终水平, 则转步骤6. 否则置kk+1, 转步骤2.,步骤 6 对现在执行结点p中的每个xi , 利用规则2作如下检验. 如果 D (x , p ) D (x i , p ) +B 则 x i不是x 的最近邻, 从而不计算 D (x , xi), 否则计算D (x , xi). 若 D (x , xi) B 置NN = i 和B= D (x , xi). .在当前执行结点中所有xi被检验之后, 转步骤3.,当算法结束时, 输出x 的最近邻xNN 和x与xNN 的距离 D( x , xNN ) =B,2) 将算法扩展到 k-近邻法的情况.,这只需
13、要对前述算法做部分修改就可以完成.,首先对B做修正, 使它在现在的程序中是x到第k个近邻的距离.,然后当在步骤6中每计算一个距离之后, 就与当前执行近邻表中的k个近邻距离做比较, 若这个新计算的距离小于近邻表中任何一个时, 则从近邻表中去掉最大的一个. 算法的其它部分与最近邻法相同.,+ x,图中两类样本相互交错,2 剪辑近邻法,将未知样本x用近邻法分类是不好处理的.,解决思路:,如果能够剪辑掉两类边界附近交错的一些样本, 并使得剩下的样本形成两个好的聚类, 而且每个聚类中的样本都属于同一类, 它们的分界面十分接近贝叶斯决策面, 那么可以提高利用近邻规则分类的性能.,下面介绍两种剪辑近邻法:
14、1) . 两分剪辑近邻法 2) . 重复剪辑近邻法,1) 两分剪辑近邻法,在两分剪辑近邻法中, 假定给定的样本集X 被分成两个独立的样本集- 考试集X T 和参考集X R . 在参考集中的样本完成参考任务, 在考试集中完成考试任务,并且去掉考试中不合格的样本. 将考试中保留的合格样本构成剪辑样本集, 并利用该样本集对未知样本x利用近邻法作分类决策.,基本思路:,步骤1 假定样本集X 中的每个样本不是被用概率a分到考试集X T 中, 就是用概率1-a分到参考集X R 中,步骤2 利用参考集X R 中的样本对考试集X T中的每个样本用近邻法进行分类决策,*x,步骤 3 剪辑掉考试集X T中被参考集
15、X R利用最近邻法错分类的样本, 然后将X T 中剩余样本构成剪辑样本集 X NTE .,* x,步骤 4 利用剪辑样本集X NTE 和最近邻规则对未知样本x作分类决策.,剪辑近邻法的错误率分析,剪辑近邻法的条件错误率为 PkE (e | x) = P ( e | x) / 2 1- Pk ( e | x) ,由上式可见 , 剪辑近邻法的错误率总是小于等于没有剪辑的近邻法 , 即有 PkE ( e) P ( e ),尤其是在P ( e )很小时, 比如P ( e ) 0.1 , 则可推知 PkE ( e) P ( e ) / 2,由于没有剪辑的近邻法错误率P ( e )的上界为2p*, 因此经过近邻规则剪辑的近邻法错误率接近贝叶斯错误率P*, 即 PkE ( e ) P*,2) 重复剪辑近邻法,重复剪辑近邻法是两分剪辑近邻法的扩展. 只要样本数足够多, 我们可以重复地执行剪辑程序, 以进一步提高近邻法规则分类的性能. 只是将前一步剪辑后的样本形成新的样本集, 然后对其重新随机划分为考试集和参考集, 这就有效的避免了划分子集的相互作用, 从而保证了剪辑的独立性.,问题的提出: 从上一节我们可以看到, 剪辑的结果只是去掉了两类边界附近的样本, 而靠近两类中心的样本几乎没有去掉. 按照近邻规则, 这些样本中的大多数对分类决策没有什么作用. 因此在剪辑的基础
