第5章-近邻法分析课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第5章 近邻法,第5章 近邻法,5.1最近邻法,5.2,k,近邻法,5.3 剪辑近邻法,5.4可做拒绝决策的近邻法,第5章 近邻法5.1最近邻法,前面我们介绍了Bayes方法和概率密度函数的估计。可以看出，Bayes方法的应用受到很大限制。事实上，非参数模式识别方法更为实用。由于能解决许多实际的模式识别问题，虽然在许多情况下它们不是最优的，但却是应用的最多的有效的方法。统计模式识别中常用的基本非参数方法除了前面介绍的线性判别函数外，,还有本章将要介绍的近邻法和集群。近邻法属于有监督学习，集群属于无监督学习。,近邻法是由Cover和Hart于1968年提出来的。,它是在已知模式类别的训练样本的条件下，绕开概率的估计，按最近距离原则对待识别模式直接进行分类。,返回本章首页,前面我们介绍了Bayes方法和概率密度函数的估计。可以看出，,5.1 最近邻法,返回本章首页,最近邻决策规则,给定,c,个类别 ，每类有标明类别的样本 个，近邻法的判别函数为,决策法则为,直观的说，就是对待识别的模式向量 ，只要比较 与所有已知类别的样本之间的欧式距离，并决策 与离它最近的样本同类。,5.1 最近邻法返回本章首页最近邻决策规则,返回本章首页,返回本章首页,返回本章首页,下面我们先定性的比较一下最近邻分类法与最小错误率的Bayes分类方法的分类能力。,我们把 的最近邻 的类别看成是一个随机变量 ，,的概率为后验概率,最近邻法则可以看成是一个随机化决策 按照概率,来决定 的类别。,定义：,返回本章首页下面我们先定性的比较一下最近邻分类法与最小错误率,返回本章首页,按最小错误率的Bayes决策法则：以概率1决策 ；,按最近邻决策法则：以概率 决策 ；,这里假设在三类问题中，的后验概率分别为,按最小错误率的Bayes决策法则：以概率1决策 ；,按最近邻决策法则：以概率 决策 ；以概率 决策 。,当 时，最近邻法的决策结果与最小错误率的Bayes决策的决策结果相同，它们的错误率都是比较小的，两种方法同样的好，当 ，两者的错误概率接近于 ，两种方法同样的坏。下面我们将进一步分析近邻法的错误率。,返回本章首页按最小错误率的Bayes决策法则：以概率1决策,返回本章首页,最近邻法的错误率分析,在前面我们曾给出平均错误率的,在最小错误率的Bayes决策中，决策使条件错误率 尽可能小，从而平均错误率 也一定最小。这里，设,采用,N,个样本的最近邻法的平均错误率 ，并设,返回本章首页最近邻法的错误率分析,返回本章首页,则有以下的不等式成立：,证明：最近邻法属于随机化决策，待分类模式 的近邻随样本集的变化而随机变化，设其最近邻为 ，错误的条件错误率为 。对于 取平均,返回本章首页则有以下的不等式成立：,返回本章首页,返回本章首页,返回本章首页,下面我们看一下上面的两个表达式。,设对于给定的 ，概率密度是连续的且不为零。那么，任何样本落入以 为中心的一个超球,S,中的概率为,N,个独立的样本落在,S,外的概率为,即是，一个样本也不落在,S,内的概率为,0,，也就是说总有一个样本落在,S,内的概率为1。无论S多么小，这个结论也是成立的，所以,返回本章首页下面我们看一下上面的两个表达式。,返回本章首页,上式即是最近法错误率的计算公式，先看下界的证明，这里指出下面的 两种特殊情况。,（1）（2）,返回本章首页上式即是最近法错误率的计算公式，先看下界的证明，,返回本章首页,现在在来求最近邻法分类错误率的精确上,界。,返回本章首页现在在来求最近邻法分类错误率的精确上界。,返回本章首页,返回本章首页,返回本章首页,例题,1 设在一个二维空间，A类有三个训练样本，图中用,红点表示，B类四个样本，图中用蓝点表示。试问：,（1）按近邻法分类，这两类最多有多少个分界面（2）画出实际用到的分界面（3）A,1,与B,4,之间的分界面没有用到,返回本章首页例题1 设在一个二维空间，A类有三个训练样本，,返回本章首页,答：按近邻法，对任意两个由不同类别的训练样本构成的样本对，,如果它们有可能成为测试样本的近邻，则它们构成一组最小距离分,类器，它们之间的中垂面就是分界面，因此由三个A类与四个B类训,练样本可能构成的分界面最大数量为3412。实际分界面如下图所示，由9条线段构成：,返回本章首页答：按近邻法，对任意两个由不同类别的训练样本构成,返回本章首页,例题2,当,时，,（1）证明一维问题的Bayes错误率,（2）证明此时最近邻法渐近平均错误率,返回本章首页例题2,返回本章首页,解：,返回本章首页解：,返回本章首页,课后习题,P160：6.3 6.4 6.5,P81：3.1 3.4 3.15,返回本章首页课后习题,5.2,k,近邻法,返回本章首页,k,近邻法是在近邻法的基础上加以改进而来的，这个法则就是在 的,k,个近邻中，按出现最多的样本类别来作为 的类别。前面我们详细讨论了近邻法的错误率的表达式及其上下界。同样，对于,k,近邻法则，我们也讨论一下错误率的问题，这里以 和 二类问题为例。为避免出现 而不能判决的情况，我们取 为奇数。对待识别模式 误分类有以下两种情况：,5.2 k近邻法返回本章首页k近邻法是在近邻法的基础上,返回本章首页,前面我们已经说过，当 ，的,k,个已知类别的最近邻样本 以概率 1 收敛于 ，所以这,k,个样本可以不标出下标，统记为 。对于给定的 的条件错误率为,返回本章首页前面我们已经说过，当 ，的 k,返回本章首页,返回本章首页,返回本章首页,渐近平均错误率,这里定义Bayes条件错误率 的函数 为大于 的最小凹函数，即对所有的,返回本章首页渐近平均错误率,返回本章首页,近邻法则讨论,返回本章首页近邻法则讨论,返回本章首页,从上面可以看出近邻法有方法简单的优点，但也存在这一些缺点：,（1）存储量和计算量都很大；,（2）没有考虑决策的风险，如果决策的错误代价很大时，会产生很大的风险；,（3）以上的分析渐近平均错误率，都是建立在样本数趋向无穷大的条件下得来的，在实际应用时大多是无法实现的。,返回本章首页从上面可以看出近邻法有方法简单的优点，但也存在这,5.3 剪辑近邻法,返回本章首页,这种方法的思想是,清理两类间的边界，去掉类别混杂的样本，使两类边界更清晰。这种方法的性能在理论上明显好于一般的最近邻法。,1 剪辑最近邻法,对于两类问题，设将已知类别的样本集 分成参照集,和考试集 两部分，这两部分没有公共元素，两部分的样本数分别为 和 ，且 。,第一步：利用参照集中的样本 采用最近邻法对考试集中的样本 进行分类，剪辑掉,中被错分类的样本，具体的说就是：是,的最近邻元，剪辑掉 中不与 同类 余下的部分构成剪辑样本集 。,5.3 剪辑近邻法返回本章首页这种方法的思想是,清理两类间,返回本章首页,第二步：利用剪辑样本集 和最近邻法对待分类模式 作分类决策。,定理,：当样本数 时，,。如果 是 和 的连续点，设 在,中的最近邻为 ，则 在 中的最近邻 有,那么我们可以得到 的近邻 属于 的渐近概率为,返回本章首页第二步：利用剪辑样本集 和最近邻法对待分,返回本章首页,误判的情况,：属于 类而其近邻元属于 ，或 属于,类但其近邻元属于 类，因此没有剪辑的最近邻法的渐近条件错误率为,剪辑了的最近邻法的渐近条件错误了率为,返回本章首页误判的情况：属于 类而其近邻元属于 ，或,返回本章首页,返回本章首页,返回本章首页,返回本章首页,返回本章首页,2 重复剪辑近邻法,只要样本足够多，就可以重复地执行剪辑程序，以提高分类性能。这里从理论上对二类问题重复剪辑最近邻法的错误率进行分析。经过第一次剪辑后，,的最近邻样本 属于 的概率为,返回本章首页2 重复剪辑近邻法,返回本章首页,第二次剪辑后，,的最近邻样本属于 的概率为,返回本章首页第二次剪辑后，的最近邻样本属于 的概,返回本章首页,第,M,次剪辑后，,的最近邻样本属于 的概率为,返回本章首页第M次剪辑后，的最近邻样本属于 的概,返回本章首页,返回本章首页,5.4 可做拒绝决策的近邻法,返回本章首页,在运用,k,近邻法时，为克服,k,个近邻元属于不同类别的样本数的偶然性，采用的方法之一是增大,k,，然而这仍然不能完全消除,k,个近邻元类别的偶然性。我们说若k个近邻元中某一类的样本数占很大的优势，则误判的可能性就较小；如果是微弱优势，则作出判别决策，误判的可能性就很大。进一步，在某些实际问题中误判的风险很大的话，则会付出很大的代价，因此在这种情况下引入拒绝决策就很有必要了，一般记为 类。,下面我们结合前面讲述的,k,近邻法和剪辑近邻法进行分析。,5.4 可做拒绝决策的近邻法返回本章首页在运用k近邻法时,返回本章首页,1 具有拒绝决策的,k,近邻法,对于两类问题，引入了拒绝决策,k,近邻法的思想是，根据可信性要求选定一个 值，应使 ，如果待识别模式 的,k,个近邻中有大于或等于 个样本属于某一类 ,则判 ，否则拒绝作出类别决策。,的,k,个近邻元至少有 个来自 类的渐近概率为,返回本章首页1 具有拒绝决策的k近邻法,返回本章首页,当 的 个近邻中有少于 个属于同一类时，则考虑拒绝，这时的概率为,返回本章首页当 的 个近邻中有少于 个属于同一类时，,返回本章首页,决策的错误率,决策的拒绝率,2 具有拒绝决策的剪辑近邻法,拒绝决策的近邻法推广到剪辑近邻法。,首先选定 和 ，然后我们按以下的步骤对样本集进行剪辑，然后用剪辑样本集对待识别模式进行分类。,返回本章首页决策的错误率,返回本章首页,步骤如下：,（1）对于训练集 中的每个样本 ，从 中找出它的 个近邻元；,（2）如果 的 个近邻至少有 个属于 类，则记类别标签 ，否则 。,（3）在 中只保留 和 的样本，即去掉被错分类的样本。,（4）将 的那些样本 归为拒绝类 ，从而组成含有三类剪辑样本集 。,（5）利用 和最近邻规则对待识别模式 进行分类决策。,返回本章首页步骤如下：,THANK YOU VERY MUCH！,本章到此结束,下一章“,特征选择和特征提取”,返回本章首页,结 束放映,THANK YOU VERY MUCH！本章到此结束返回本,