模式识别近邻法解读.ppt

K-近邻法的错误率界 例 投票法最近邻分类的错误率 K-近邻法的错误率界 粗略地说，有些样本落在了其它类的决策区，错了。而这个错的样本又可能把正确地落在区域内的样本弄错，所以最近邻法的错误率在贝叶斯错误率和2倍贝叶斯错误率之间。 最近邻法的决策边界：训练样本的部分Voronoi Diagram 近邻法虽然没有直接计算决策边界，然而所得到的决策边界是训练样本Voronoi Diagram的一个子集。 每一条线是不同类样本 间连线的平分线。 样本越多，决策边界 越复杂。 减少近邻法的计算和存储问题 减少训练样本的数量，尽量利用“好”的训练样本。 设计好的数据结构和查找算法快速查找x的k近邻。 存储所有的训练样本需要大量的存储，要从训练样本中挑选一些好的样本 常用的方法有两种： 逐步从训练集中删掉一些“坏的”样本。 逐步从训练集中挑选出一些“好的”代表样本。 4.3 剪辑近邻法 由前面的图可以看出，在投票法的k－近邻法中，第 类的样本落在 类的区域后，它可能成为某些 类样本的近邻，因而引起额外的错误，这是为什么近邻法的错误率大于贝叶斯错误率的原因。 这些额外的错误可以通过去掉 类落在 类区域中的样本而减少（上图中的1、3、5、6）。 在实际问题中，由于不知道准确的贝叶斯决策边界，所以不能准确确定 类落在 类区域中的样本。而代之以去掉被k近邻分错的样本。这样得到的样本集合称为剪辑（Edited set）集。以后的实验样本集用剪辑集按k近邻法分类。这种算法称为剪辑近邻法。 在剪辑近邻法中， 类的落在 类区域中的有些样本被（正确）分到了 类，因而未被剪掉。而 类的在 区域中的一些样本则有可能被误分类，而被剪辑掉。所以剪辑近邻法的错误率不可能和贝叶斯错误率一样。下面我们分析渐进情况下（即 ）时的错误率。 1 剪辑的最近邻法的错误率 假定给出x的后验概率为 和 ，在使用投票法的最近邻中，被正确分类和不正确分类的概率为 和 i=1,2 剪辑的最近邻法的错误率 当剪辑掉被错分的，保留分对的时，在剪辑集中x的后验概率为 剪辑的最近邻法的错误率 原来样本集若用剪辑集按NN法分类，则错误率为 式中利用了 ，当 时。 剪辑的最近邻法的错误率 可以证明，未剪辑的最近邻法的错误率和贝叶斯错误率分别为上式的上下界： , ( ) 更一般的剪辑近邻法 用一近邻剪辑，用一近邻分类 更一般的剪辑近邻法 重复使用最近邻法，把落在 类区域中 类的样本剪掉，其错误率的情况为 4.4 压缩近邻法 近邻法存在的问题 计算量大，存储量大，要计算大量的样本间的距离 在投票近邻法，靠近贝叶斯决策边界的点对分类有关键作用。而位于各类类中心附近、远离决策边界的点不影响分类，因而可以把它们去掉。这样减少（参考）样本点，可以节省近邻法的时间和空间。 这类的算法称为压缩近邻法。 压缩近邻法 每个样本x的条件风险 是表示x是否靠近决策边界的一种度量。因此可设置一个阈值τ，并把小于阈值的样本去掉， 。为了避免如剪辑法中讨论的问题，减少额外的错误，应当先剪辑，后压缩。 压缩近邻法 下面是一个压缩算法：（这个算法没有计算 ，另种思路） Condensing algor. 设两个存储器Store和Grabbag。 把第一个样本放入Store中，把所有其它样本放在Grabbag中 压缩近邻法 用当前Store中的样本按一近邻规则对Grabbag中样本进行分类。若分类正确，则该样本仍放回Grabbag中；否则，放入Store中。对Grabbag中的所有样本重复以上过程。 若从Grabbag中转到Store中的样本数为0，或Grabbag中的样本数变为0时，停止。否则转2。 压缩后，以Store中的样本作为分类的参考集（设计集） 4.5 查找k近邻的快速算法（树有哪些信誉好的足球投注网站） 为了减少查找k－近邻的计算量，需要尽量避免穷尽地计算和所有样本间的距离，可把样本组织（分解）成一定的等级如树结构等，尽量排除一些不必要的计算。 常用的是k-d树等一类结构和有哪些信誉好的足球投注网站算法。 假定样本集 ，目的是要在 X 中寻找未知样本x的k个近邻。为了简单，先假定k＝1，即最近邻的有哪些信誉好的足球投注网站。 下面介绍另外一种把样本组织成树结构的算法。算法分两个