第六章最近邻方法 模式识别

1、第六章第六章 最近邻方法最近邻方法 Nearest Neighbour Classification 6.1 最近邻决策规则 6.2 剪辑最近邻法 6.3 误判概率及其上下界 c类问题,设 ( ) (1,2, , 1,2,) i jii xicjN? 最近邻方法最近邻方法 6.1 最近邻决策规则1- NN 最近邻分类规则: 对待识别模式 , 分别计算它与 个已知类别的样本 的距离,将它判为距离最近 的那个样本所属的类。 1 c i i NN ? ? ? ( ) i j x x () 1,2, ( )min i i ij jN dxxx ? ? 1,2,ic? 1,2, ( )min( ) mi

2、 ic dxd x ? ? m x? 如果 则 即 最近邻方法最近邻方法 6.1 最近邻决策规则1- NN (1)已知N个已知 类别样本X (2)输入未知类别 样本x (3)计算x到 x i? X，(i=1, 2,N)的 距离di (x) (4)找出最小距离 dm(x)=mind i(x) (5)看x m属于 哪一类： (6) 判x? 2 k-NN分类思想: 对待识别模式 , 分别计算它与 个已知类别的样本 的距离,取k个最近邻样本,这 k个样本中哪一类最多, 就判属哪一类。 1 c i i NN ? ? ? ( ) i j x x 最近邻方法最近邻方法 6.1 最近邻决策规则k- NN 即,

3、令 与 i的距离 ( ) ii d xk?1,2, ;ic? m x? 如果 则 1,2, ( )max( ) mi ic dxd x ? ? 1 c i i kk ? ? ?x i k其中 表示k个近邻元中属于 i的样本个数 最近邻方法最近邻方法 6.1 最近邻决策规则k- NN (1)已知N个已 知类别样本X (2)输入未知类别 样本x (6) 判x? 2 (4)找出x的k个最近邻 元X k=xi,i=1,2, ,k (5)看X k中属于哪一类的 样本最多k1=30，则N个独立样本 落在S外 的概率为 x ( )p x 12 , N x xx 12 (,)(1) N NS P x xxP?

4、 12 01 011 lim(,)lim(1)0 SS N NS NN PP P xxxP ? ? ? ? ? 00 lim1 lim(|)() S NN Pp xxxx? ? ? ? ? 1 0 P xx ? ? 即 以概率1收敛于 记为 x 0 x 因为 ，故 条件下的渐近误判概率为 1 0 P xx ? ? 02 1/ 1 lim( |,)1(|) c Ni N i PexxPx? ? ? ? ? ? x 000 11/ 2002 11 ( | )lim( | ,) (| ) 1(| )()1(| ) NNN N cc ii ii PexPexxp xx dx Pxxxd xPx? ?

5、? ? ? ? ? ? ? 00 1/ 1 (|,)1(| ) (|) c Nii i Pe x xPx Px? ? ? ? 一、1-NN法误判概率及其上下界 条件下的渐近误判概率 x 000 11/ 200 1 2 1 ( | )lim( | ,) (| ) 1(| ) () 1(| ) NNN N c i i c i i Pe xPe x xp xx dx Pxxx dx Px ? ? ? ? ? ? ? ? ? ? ? ? ? 11 2 1 ( )( | ) ( ) 1(| ) ( ) NNNN c i i PePe x p x dx Pxp x dx? ? ? ? ? ? ? 一、1-

6、NN法误判概率及其上下界 1,., (| )max(| ) mi ic PxPx? ? ? 最小误判概率准则： 若 m x?则 这时的条件误判概率为 ( | )1(| ) Bm P e xPx? ( )( | ) ( )1(| ) ( ) BBm P ePe x p x dxPxp x dx? ? 2 1 1 () 1(| )() c NNi i PePxp x dx? ? ? ? ? 一、1-NN法误判概率及其上下界 1, (| ) 0, i im Px im ? ? ? ? ? ? （1）确定情况下，即 这时 2 1 1 () 1(| )() c NNi i PePxp x dx? ? ?

7、 ? ? ( ) 1( | ) ( ) Bm P ePxp x dx? ? 0? 0? 一、1-NN法误判概率及其上下界 2 1 1 ()1(| )() c NNi i PePxp x dx? ? ? ? ? （2）最不确定的情况下，即各类的后验概 率为均匀分布： (|)1/ , 1,2, i Pxcic? 1c c ? ? 1c c ? ?( )1(| ) ( ) Bm P ePxp x dx? ? 一、1-NN法误判概率 1c c ? ( ) B Pe 1c c ? 1 ( ) NN Pe ? 1 ( )( )( )2( ) 1 BNNBB c P ePeP eP e c ? ? ? 二、k-NN法误判概率 0.5