清华大学
http://202.197.191.206:8080/30/text/chapter03/3_4_2.htm本转载不以任何商业利益为目的，只为方便学习，如有侵权请联系删除。
3.4.2.1 最近邻法错误率分析
其实近邻法的错误率是比较难算的，因为训练样本集的数量总是有限的，有时多一个少一个训练样本对测试样本分类的结果影响很大。譬如图中
红点表示A类训练样本，蓝点表示B类训练样本，而绿点O表示待测样本。假设以欧氏距离来衡量，O的最近邻是A3，其次是B1，因此O应该属于A类，但若A3被拿开，O就会被判为B类。这说明计算最近邻法的错误率会有偶然性，也就是指与具体的训练样本集有关。同时还可看到，计算错误率的偶然性会因训练样本数量的增大而减小。因此人们就利用训练样本数量增至极大，来对其性能进行评价。这要使用渐近概念，以下都是在渐近概念下来分析错误率的。
图 3.17
当最近邻法所使用的训练样本数量N不是很大时，其错误率是带有偶然性的。为了说明这一点我们拿图3.17所示一个在一维特征空间的两类别情况来讨论。图中X表示一特测试样本，而X'是所用训练样本集中X的最邻近者，则错误是由X与X'分属不同的类别所引起的。由于X'与所用训练样本集有关，因此错误率有较大偶然性。但是如果所用训练样本集的样本数量N极大，即N→∞时，可以想像X'将趋向于X，或者说处于以X为中心的极小邻域内，此时分析错误率问题就简化为在X样本条件下X与一个X(X'的极限条件)分属不同类别的问题。如果样本X的两类别后验概率分别为P(ω1|X)与P(ω2|X)，那么对X值，在N→∞条件下，发生错误决策的概率为：
(3-64)
当训练样本数量无限增多时，一个测试样本X的最近邻在极限意义上讲就是X本身。如果在X处对某一类的的后验概率为P(ω1|X)，则另一类为1- P(ω1|X)。那么当前测试样本与它的最近邻都属于同一类才能分类正确，故正确分类率为 ，故有(3-64)式。
而在这条件下的平均错误率
(3-65)
P称为渐近平均错误率，是PN(e)在N→∞的极限。
为了与基于最小错误率的贝叶斯决策方法对比，下面写出贝叶斯错误率的计算式。
基于最小错误率贝叶斯决策的错误率是出错最低限，因此要与它作比较。
(3-66)
其中 (3-67)
而 (3-68)