模式识别近邻法精选PPT.ppt

《模式识别近邻法精选PPT.ppt》由会员分享，可在线阅读，更多相关《模式识别近邻法精选PPT.ppt（63页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

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

4、课件共63页哦把上式代入(*)式并化简有，（3）第14页，此课件共63页哦最近邻法的错误率分析而近邻法和贝叶斯决策的错误率定义为：第15页，此课件共63页哦最近邻法的错误率分析第16页，此课件共63页哦取(3)式期望，并利用上式，有 由于贝叶斯错误率是最小的，所以完整的上下界是：第17页，此课件共63页哦最近邻法的错误率分析上式的结果表明，当样本数相当多时，近邻法的错误率在贝叶斯错误率和两倍的贝叶斯错误率之间。第18页，此课件共63页哦的一些特殊情况 当 时，第19页，此课件共63页哦当 各类的后验概率相等时 的一些特殊情况 第20页，此课件共63页哦4.2 K-近邻法 取未知样本的K个近邻，

5、看这K个近邻中哪类的样本数最多，就把未知样本归到该类。第21页，此课件共63页哦K-近邻法的错误率界 K-近邻的错误率的分析要复杂。当类别数c=2时，K-近邻法的错误率以一族凹函数 为上界。具有如下的性质：第22页，此课件共63页哦K-近邻法的错误率界这些函数的形状如下：第23页，此课件共63页哦K-近邻法的错误率界第24页，此课件共63页哦*K-近邻法的错误率界证明K-NN法错误率的思路：（对两类，K为奇数的情况）若 ，而 时则发生错分，其错误率为 第25页，此课件共63页哦K-近邻法的错误率界同样，当 ，而 时发生误分类，其错误率为 第26页，此课件共63页哦K-近邻法的错误率界所以，给出

6、x时的条件错误率为 第27页，此课件共63页哦K-近邻法的错误率界上式可以化为 (3)第28页，此课件共63页哦K-近邻法的错误率界其中：（当K为偶数时，有：,)(4)第29页，此课件共63页哦K-近邻法的错误率界而给出x时的条件贝叶斯风险为 (5)（Maclaulin）马克劳林级数展开 第30页，此课件共63页哦K-近邻法的错误率界利用上面的式，有(回想过去讲的 和 间联系了起来，贝叶斯错误率的Bhattacharyya界，称为B距离。）第31页，此课件共63页哦K-近邻法的错误率界例 投票法最近邻分类的错误率 第32页，此课件共63页哦K-近邻法的错误率界粗略地说，有些样本落在了其它类的决

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

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

9、t）集。以后的实验样本集用剪辑集按k近邻法分类。这种算法称为剪辑近邻法。第38页，此课件共63页哦在剪辑近邻法中，类的落在 类区域中的有些样本被（正确）分到了 类，因而未被剪掉。而 类的在 区域中的一些样本则有可能被误分类，而被剪辑掉。所以剪辑近邻法的错误率不可能和贝叶斯错误率一样。下面我们分析渐进情况下（即 ）时的错误率。第39页，此课件共63页哦1 剪辑的最近邻法的错误率假定给出x的后验概率为 和 ，在使用投票法的最近邻中，被正确分类和不正确分类的概率为 和 i=1,2 第40页，此课件共63页哦剪辑的最近邻法的错误率当剪辑掉被错分的，保留分对的时，在剪辑集中x的后验概率为第41页，此课件

10、共63页哦剪辑的最近邻法的错误率原来样本集若用剪辑集按NN法分类，则错误率为式中利用了 ，当 时。第42页，此课件共63页哦剪辑的最近邻法的错误率可以证明，未剪辑的最近邻法的错误率和贝叶斯错误率分别为上式的上下界：,()第43页，此课件共63页哦更一般的剪辑近邻法用一近邻剪辑，用一近邻分类第44页，此课件共63页哦更一般的剪辑近邻法重复使用最近邻法，把落在 类区域中 类的样本剪掉，其错误率的情况为 第45页，此课件共63页哦4.4 压缩近邻法近邻法存在的问题计算量大，存储量大，要计算大量的样本间的距离 在投票近邻法，靠近贝叶斯决策边界的点对分类有关键作用。而位于各类类中心附近、远离决策边界的点

11、不影响分类，因而可以把它们去掉。这样减少（参考）样本点，可以节省近邻法的时间和空间。这类的算法称为压缩近邻法。第46页，此课件共63页哦压缩近邻法每个样本x的条件风险 是表示x是否靠近决策边界的一种度量。因此可设置一个阈值，并把小于阈值的样本去掉，。为了避免如剪辑法中讨论的问题，减少额外的错误，应当先剪辑，后压缩。第47页，此课件共63页哦压缩近邻法下面是一个压缩算法：（这个算法没有计算 ，另种思路）Condensing algor.设两个存储器Store和Grabbag。1.把第一个样本放入Store中，把所有其它样本放在Grabbag中 第48页，此课件共63页哦压缩近邻法2.用当前Sto

12、re中的样本按一近邻规则对Grabbag中样本进行分类。若分类正确，则该样本仍放回Grabbag中；否则，放入Store中。对Grabbag中的所有样本重复以上过程。3.若从Grabbag中转到Store中的样本数为0，或Grabbag中的样本数变为0时，停止。否则转2。4.压缩后，以Store中的样本作为分类的参考集（设计集）第49页，此课件共63页哦4.5 查找k近邻的快速算法（树搜索）为了减少查找k近邻的计算量，需要尽量避免穷尽地计算和所有样本间的距离，可把样本组织（分解）成一定的等级如树结构等，尽量排除一些不必要的计算。常用的是k-d树等一类结构和搜索算法。第50页，此课件共63页哦假

13、定样本集 ，目的是要在 X 中寻找未知样本x的k个近邻。为了简单，先假定k1，即最近邻的搜索。下面介绍另外一种把样本组织成树结构的算法。算法分两个阶段:第51页，此课件共63页哦1.把样本集X 分级分解，组织成树结构。可根据样本在特征空间中所占的位置，把样本集分成不相交的一些子集（个），然后把这些样本子集再分解成不相交的子集，如此进行下去，直到每个终端点只含一个样本为止。如下图：第52页，此课件共63页哦第53页，此课件共63页哦树的中间节点 都代表一个样本子集，可以用下列参数描述：节点k所对应的样本子集 ：中的样本数 ：中的样本均值 ，从 到 中的样本 的最大距离（不妨称为 的半径）第54页

14、，此课件共63页哦分成子集的方法，可根据样本在特征空间中所占的位置，把相邻样本组织成一个子集。可以用聚类分析的方法（如c均值聚类算法）第55页，此课件共63页哦 可以利用下面两个规则加快搜索。判断xi或xi所属的子集有否可能是x的近邻。2.搜索未知样本的（最，k）近邻（分支限界算法）规则1：令B是算法执行过程中已经找到的x的最近邻离x的距离，程序开始时可设B的初值为。第56页，此课件共63页哦令 是 的半径，若 ，则 不可能是x的最近邻。这个规则可以排除不可能是x近邻的 ，不用计算每个 ，。直观意义如下：第57页，此课件共63页哦根据三角不等式：规则1 对于终端节点 ，可以利用下面的规则2迅速

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