模式识别近邻法

《模式识别近邻法》由会员分享，可在线阅读，更多相关《模式识别近邻法（63页珍藏版）》请在金锄头文库上搜索。

1、第四章 近邻法4.1 最近邻法(1-Nearest Neighbor Algor.)一 最近邻决策规则 假定有c类模式，1,2,c,每类有 个样本，i=1,2,c，总样本数为 。 对未知样本 ，找出已知类别的训练样本 集中和 最近的一个样本，把 分到与该 样本一样的类。 最近邻决策算法 存储训练样本； 对一新的样本x，在训练样本集中按某种 距离度量找到x的最近邻(xi,yi)，令x的类 别y和yi相同。 使用欧式距离时： 使用平方距离结果是一样的，免去了开 方运算：近邻法和使用的距离度量关系很大 将所有的特征值规范到相同的范围（比 如-1，1），否则取值范围大的特征起 的作用大。 去掉噪声的、

2、不好的特征，它们影响距 离度量和性能。 利用好的距离度量，如式中 是互信息。 或利用Mahalanobis距离： 使用k-近邻更可靠。二 最近邻法的错误率分析 下面先分析近邻法的错误率，然后讨论 具体实施近邻法时的一些问题。 近邻法错误率分析的思想是把它和贝叶 斯错误率联系起来最近邻法的错误率 分析令 是要分类的点， 是它的最近邻, 的真实类是 ， 的真实类别是 ,对 于 和 ，发生错误的概率为 最近邻法的错误率分析 假定事件“ 是 类”和“ 是 类”是独 立的事件，则最近邻算法的条件错误率 为： 最近邻法的错误率分析 如果密度函数是连续的，而且样本点相当 多，则 的最近邻 将非常接近 ，因

3、此可以合理地认为（假定）代入上式，有 (*)最近邻法的错误率分析 下面分析这个错误率和贝叶斯错误率间 的关系令 是根据贝叶斯决策规则将 所分的 类，即：最近邻法的错误率分析 贝叶斯决策的条件错误率为：(*) 或写成(1) 为了导出 的界，对(*)式中的平方 项，有 (*)对于固定的 值，上式当 ，都相等时取最小值。 又由(*)式，使(*)式的 取最小值的为（2） (*)式可以化为（把（1）和（2）代 入）共(c-1)项，消除了一个(c-1) 把上式代入(*)式并化简有，（3） 最近邻法的错误率分析 而近邻法和贝叶斯决策的错误率定义为 ： 最近邻法的错误率分析 取(3)式期望，并利用上式，有由于

4、贝叶斯错误率是最小的，所以完整的 上下界是： 最近邻法的错误率分析 上式的结果表明，当样本数相当多时， 近邻法的错误率在贝叶斯错误率和两倍 的贝叶斯错误率之间。 的一些特殊情况 当 时， 当 各类的后验概率相等时 的一些特殊情况 4.2 K-近邻法 取未知样本的K个近邻，看这K个 近邻中哪类的样本数最多，就把未 知样本归到该类。 K-近邻法的错误率界 K-近邻的错误率的分析要复杂。当类别数 c=2时，K-近邻法的错误率以一族凹函数 为上界。 具有如下的性质： K-近邻法的错误率界 这些函数的形状如下： K-近邻法的错误率界* K-近邻法的错误率界 证明K-NN法错误率的思路：（对两类， K为奇

5、数的情况） 若 ，而 时则发生错分，其错 误率为 K-近邻法的错误率界 同样，当 ，而 时发生误分 类，其错误率为 K-近邻法的错误率界 所以，给出x时的条件错误率为 K-近邻法的错误率界 上式可以化为 (3) K-近邻法的错误率界 其中： （当K为偶数时，有：, ) (4) K-近邻法的错误率界 而给出x时的条件贝叶斯风险为 (5) （Maclaulin）马克劳林级数展开 K-近邻法的错误率界 利用上面的式，有 (回想过去讲的 和 间联系了起来，贝叶斯错误率的Bhattacharyya界， 称 为B距离。） K-近邻法的错误率界 例 投票法最近邻分类的错误率 K-近邻法的错误率界 粗略地说，

6、有些样本落在了其它类的决 策区，错了。而这个错的样本又可能把 正确地落在区域内的样本弄错，所以最 近邻法的错误率在贝叶斯错误率和2倍贝 叶斯错误率之间。 最近邻法的决策边界：训练样本的部 分Voronoi Diagram 近邻法虽然没有直接计算决策边界，然 而所得到的决策边界是训练样本Voronoi Diagram的一个子集。 每一条线是不同类样本间连线的平分线。样本越多，决策边界越复杂。减少近邻法的计算和存储问题 减少训练样本的数量，尽量利用“好”的 训练样本。 设计好的数据结构和查找算法快速查找x 的k近邻。存储所有的训练样本需要大量的存储， 要从训练样本中挑选一些好的样本 常用的方法有两

7、种： 逐步从训练集中删掉一些“坏的”样本。 逐步从训练集中挑选出一些“好的”代表 样本。4.3 剪辑近邻法 由前面的图可以看出，在投票法的k近 邻法中，第 类的样本落在 类的区域 后，它可能成为某些 类样本的近邻， 因而引起额外的错误，这是为什么近邻 法的错误率大于贝叶斯错误率的原因。 这些额外的错误可以通过去掉 类落 在 类区域中的样本而减少（上图中 的1、3、5、6）。 在实际问题中，由于不知道准确的贝叶 斯决策边界，所以不能准确确定 类落 在 类区域中的样本。而代之以去掉被k 近邻分错的样本。这样得到的样本集合 称为剪辑（Edited set）集。以后的实验 样本集用剪辑集按k近邻法分类

8、。这种算 法称为剪辑近邻法。 在剪辑近邻法中， 类的落在 类区域 中的有些样本被（正确）分到了 类， 因而未被剪掉。而 类的在 区域中的 一些样本则有可能被误分类，而被剪辑 掉。所以剪辑近邻法的错误率不可能和 贝叶斯错误率一样。下面我们分析渐进 情况下（即 ）时的错误率。1 剪辑的最近邻法的错误率 假定给出x的后验概率为 和 ， 在使用投票法的最近邻中，被正确分类 和不正确分类的概率为 和 i=1,2 剪辑的最近邻法的错误率 当剪辑掉被错分的，保留分对的时，在 剪辑集中x的后验概率为剪辑的最近邻法的错误率 原来样本集若用剪辑集按NN法分类，则错误 率为 式中利用了 ，当 时 。 剪辑的最近邻法

9、的错误率 可以证明，未剪辑的最近邻法的错误率 和贝叶斯错误率分别为上式的上下界：, ( ) 更一般的剪辑近邻法 用一近邻剪辑，用一近邻分类更一般的剪辑近邻法 重复使用最近邻法，把落在 类区域中类的样本剪掉，其错误率的情况为 4.4 压缩近邻法 近邻法存在的问题 计算量大，存储量大，要计算大量的样本间 的距离 在投票近邻法，靠近贝叶斯决策边界的点对 分类有关键作用。而位于各类类中心附近、 远离决策边界的点不影响分类，因而可以把 它们去掉。这样减少（参考）样本点，可以 节省近邻法的时间和空间。这类的算法称为压缩近邻法。压缩近邻法 每个样本x的条件风险 是表示x是否靠 近决策边界的一种度量。因此可设

10、置一 个阈值，并把小于阈值的样本去掉，。为了避免如剪辑法中讨论的问题 ，减少额外的错误，应当先剪辑，后压 缩。 压缩近邻法下面是一个压缩算法：（这个算法没有计 算 ，另种思路） Condensing algor.设两个存储器Store和Grabbag。 1. 把第一个样本放入Store中，把所有其它 样本放在Grabbag中 压缩近邻法2. 用当前Store中的样本按一近邻规则对 Grabbag中样本进行分类。若分类正确 ，则该样本仍放回Grabbag中；否则， 放入Store中。对Grabbag中的所有样本 重复以上过程。 3. 若从Grabbag中转到Store中的样本数为0 ，或Grab

11、bag中的样本数变为0时，停止 。否则转2。 4. 压缩后，以Store中的样本作为分类的参 考集（设计集） 4.5 查找k近邻的快速算法（树搜索） 为了减少查找k近邻的计算量，需要尽 量避免穷尽地计算和所有样本间的距离， 可把样本组织（分解）成一定的等级如树 结构等，尽量排除一些不必要的计算。 常用的是k-d树等一类结构和搜索算法。 假定样本集 ，目的是要在X 中寻找未知样本x的k个近邻。为了简 单，先假定k1，即最近邻的搜索。下面介绍另外一种把样本组织成树结构的算 法。算法分两个阶段:1. 把样本集X 分级分解，组织成树结构。 可根据样本在特征空间中所占的位置， 把样本集分成不相交的一些子

12、集（ 个 ），然后把这些样本子集再分解成不相 交的子集，如此进行下去，直到每个终 端点只含一个样本为止。如下图： 树的中间节点 都代表一个样本子集， 可以用下列参数描述：节点k所对应的样本子集： 中的样本数： 中的样本均值，从 到 中的样本 的 最大距离（不妨称为 的半径） 分成子集的方法，可根据样本在特征空 间中所占的位置，把相邻样本组织成一 个子集。可以用聚类分析的方法（如c均 值聚类算法）可以利用下面两个规则加快搜索。判断xi 或xi所属的子集有否可能是x的近邻。2. 搜索未知样本的（最，k）近邻（分支限 界算法）规则1：令B是算法执行过程中已经找 到的x的最近邻离x的距离，程序开始 时

13、可设B的初值为。令 是 的半径，若 ，则 不 可能是x的最近邻。 这个规则可以排除不可能是x近邻的 ， 不用计算每个 ， 。直观意义 如下： 根据三角不等式：规则1对于终端节点 ，可以利用下面的规则2 迅速检验它能否成为x的最近邻，省去计 算所有的 。 规则2：若 , ,则 不是x的最近邻。（ ）规则2 由于 在计算 时已经算过，可 以存起来。 利用规则1或2，可以剔除不可能是x最近 邻的子集或点 利用上面两个规则，可以设计适当的树 搜索算法。 在实际应用时，要综合考虑树的层数和 节点所含的样本数。上述最近邻的搜索 算法可以容易地推广到k近邻的搜索。 维数灾难问题（The Curse of Dimensionality） 当维数增加时，近邻法会遇到麻烦，因 为要找的邻域会变得很大。 假定5000个样本均匀分布在一个立方体 上。假定未知样本在原点上，在利用5近 邻法分类时， 一维时，平均在距离5/5000=0.001内可找 到5个样本，两维时平均 距离，d维 时平均 才会得到原体积的0.001。 d=10时，需要（平均）距离0.501。维数和查找距离的关系噪声特征、“坏”特征的影响 假定待分类点在原点，第一近邻点在x1,第二近 邻点在x2。 x1和x2的类别不同。 假定加上一个均匀分布的噪声特征，这时有可能x2成为第一近邻。