模式识别_第6章_近邻法（精选）.ppt

第6章近邻法
最近邻法, k—近邻法
误判概率上下界
改进的近邻法
Bayes方法需要借助概率密度函数估计。可以看出,其应用受到很大限制。事实上,非参数模式识别方法更为实用。由于能解决许多实际的模式识别问题,虽然在许多情况下它们不是最优的,但却是应用的最多的有效的方法。统计模式识别中常用的基本非参数方法除了前面介绍的线性判别函数外,还有将要介绍的近邻法和聚类。近邻法属于有监督学习,聚类属于无监督学习。它是在已知模式类别的训练样本的条件下,绕开概率的估计,按最近距离原则对待识别模式直接进行分类。
近邻法
最近邻分类器(nearest neighborhood classifier, nnc): 最小距离分类器的一种极端的情况,以全部训练样本作为代表点,计算测试样本与所有样本的距离,并以最近邻者的类别作为决策。
最初的近邻法是由Cover和Hart于1968年提出的,随后得到理论上深入的分析与研究,是非参数法中最重要的方法之一。
c类问题,设
最近邻方法 最近邻决策规则—1-NN
最近邻分类规则:
对待识别模式, 分别计算它与
个已知类别的样本的距离,将它判为距离最近的那个样本所属的类。
如果
则
即
最近邻方法 最近邻决策规则—1-NN
(1)已知N个已知类别样本X
(2)输入未知类别样本x
(3)计算x到xiX,(i=1,
2,…,N)的距离di(x)
(4)找出最小距离dm(x)=min{di(x)}
(5)看xm属于哪一类:xmω2
(6) 判xω2
k-NN分类思想:
对待识别模式, 分别计算它与
个已知类别的样本的距离,取k个最近邻样本,这k个样本中哪一类最多, 就判属哪一类。
最近邻方法 最近邻决策规则—k-NN
即,令与ωi的距离
如果
则
其中表示k个近邻元中属于ωi的样本个数
最近邻方法 最近邻决策规则—k-NN
(1)已知N个已知类别样本X
(2)输入未知类别样本x
(6) 判xω2
(4)找出x的k个最近邻元Xk={xi,i=1,2,…,k}
(5)看Xk中属于哪一类的样本最多k1=3<k2=4
(3)计算x到xiX,(i=1,
2,…,N)的距离di(x)
下面我们先定性的比较一下最近邻分类法与最小错误率的Bayes分类方法的分类能力。
我们把的最近邻的类别看成是一个随机变量,
的概率为后验概率
最近邻法错误率分析
按最小错误率的Bayes决策法则:以概率1决策;
按最近邻决策法则:以概率决策;
最近邻法则可以看成是一个随机化决策——按照概率来决定的类别。
定义:
这里假设在三类问题中, 的后验概率分别为
按最小错误率的Bayes决策法则:以概率1决策;
按最近邻决策法则:以概率决策;以概率决策。
当时,最近邻法的决策结果与最小错误率的Bayes决策的决策结果相同,它们的错误率都是比较小的,两种方法同样的好,当,两者的错误概率接近于,两种方法同样的坏。下面我们将进一步分析近邻法的错误率。