K-近邻法的错误率界利用上面的③–⑤式，有(回想过去讲的和间联系了起来，贝叶斯错误率的Bhattacharyya界，称为B距离。）第31页，共63页，星期日，2025年，2月5日K-近邻法的错误率界例投票法最近邻分类的错误率第32页，共63页，星期日，2025年，2月5日K-近邻法的错误率界粗略地说，有些样本落在了其它类的决策区，错了。而这个错的样本又可能把正确地落在区域内的样本弄错，所以最近邻法的错误率在贝叶斯错误率和2倍贝叶斯错误率之间。第33页，共63页，星期日，2025年，2月5日最近邻法的决策边界：训练样本的部分VoronoiDiagram近邻法虽然没有直接计算决策边界，然而所得到的决策边界是训练样本VoronoiDiagram的一个子集。每一条线是不同类样本间连线的平分线。样本越多，决策边界越复杂。第34页，共63页，星期日，2025年，2月5日减少近邻法的计算和存储问题减少训练样本的数量，尽量利用“好”的训练样本。设计好的数据结构和查找算法快速查找x的k近邻。第35页，共63页，星期日，2025年，2月5日存储所有的训练样本需要大量的存储，要从训练样本中挑选一些好的样本常用的方法有两种：逐步从训练集中删掉一些“坏的”样本。逐步从训练集中挑选出一些“好的”代表样本。第36页，共63页，星期日，2025年，2月5日4.3剪辑近邻法由前面的图可以看出，在投票法的k－近邻法中，第类的样本落在类的区域后，它可能成为某些类样本的近邻，因而引起额外的错误，这是为什么近邻法的错误率大于贝叶斯错误率的原因。这些额外的错误可以通过去掉类落在类区域中的样本而减少（上图中的1、3、5、6）。第37页，共63页，星期日，2025年，2月5日在实际问题中，由于不知道准确的贝叶斯决策边界，所以不能准确确定类落在类区域中的样本。而代之以去掉被k近邻分错的样本。这样得到的样本集合称为剪辑（Editedset）集。以后的实验样本集用剪辑集按k近邻法分类。这种算法称为剪辑近邻法。第38页，共63页，星期日，2025年，2月5日在剪辑近邻法中，类的落在类区域中的有些样本被（正确）分到了类，因而未被剪掉。而类的在区域中的一些样本则有可能被误分类，而被剪辑掉。所以剪辑近邻法的错误率不可能和贝叶斯错误率一样。下面我们分析渐进情况下（即）时的错误率。第39页，共63页，星期日，2025年，2月5日1剪辑的最近邻法的错误率假定给出x的后验概率为和，在使用投票法的最近邻中，被正确分类和不正确分类的概率为和i=1,2第40页，共63页，星期日，2025年，2月5日剪辑的最近邻法的错误率当剪辑掉被错分的，保留分对的时，在剪辑集中x的后验概率为第41页，共63页，星期日，2025年，2月5日剪辑的最近邻法的错误率原来样本集若用剪辑集按NN法分类，则错误率为式中利用了，当时。第42页，共63页，星期日，2025年，2月5日剪辑的最近邻法的错误率可以证明，未剪辑的最近邻法的错误率和贝叶斯错误率分别为上式的上下界：,()第43页，共63页，星期日，2025年，2月5日更一般的剪辑近邻法用一近邻剪辑，用一近邻分类第44页，共63页，星期日，2025年，2月5日更一般的剪辑近邻法重复使用最近邻法，把落在类区域中类的样本剪掉，其错误率的情况为第45页，共63页，星期日，2025年，2月5日第1页，共63页，星期日，2025年，2月5日一最近邻决策规则假定有c类模式，ω1,ω2,…,ωc,每类有个样本，i=1,2,…,c，总样本数为。对未知样本，找出已知类别的训练样本集中和最近的一个样本，把分到与该样本一样的类。第2页，共63页，星期日，2025年，2月5日最近邻决策算法存储训练样本；对一新的样本x，在训练样本集中按某种距离度量找到x的最近邻(xi,yi)，令x的类别y和yi相同。使用欧式距离时：使用平方距离结果是一样的，免去了开方运算：第3页，共63页，星期日，2025年，2月5日近邻法和使用的距离度量关