第四章近邻法.pptVIP

第1章 绪论 第4章 近邻法 4.1　最近邻法 4.2　k—近邻法 4.3 改进的近邻法 前面我们介绍了Bayes方法和概率密度函数的估计。可以看出，Bayes方法的应用受到很大限制。事实上，非参数模式识别方法更为实用。由于能解决许多实际的模式识别问题，虽然在许多情况下它们不是最优的，但却是应用的最多的有效的方法。统计模式识别中常用的基本非参数方法除了前面介绍的线性判别函数外，还有将要介绍的近邻法和聚类。近邻法属于有监督学习，聚类属于无监督学习。它是在已知模式类别的训练样本的条件下，绕开概率的估计，按最近距离原则对待识别模式直接进行分类。 第4章 近邻法则和集群 * 近邻法 最近邻分类器(nearest neighborhood classifier, nnc): 最小距离分类器的一种极端的情况，以全部训练样本作为代表点，计算测试样本与所有样本的距离，并以最近邻者的类别作为决策。 最初的近邻法是由Cover和Hart于1968年提出的，随后得到理论上深入的分析与研究，是非参数法中最重要的方法之一。 4.1 最近邻法 最近邻法：nearest neighborhood classifier (nnc)，将与测试样本最近邻样本的类别作为决策的结果。 对一个C类别问题，每类有Ni个样本，i＝1，…，C，则第i类ωi的判别函数为： ‖·‖表示某种距离（相似性）度量，常用欧氏距离作为相似性度量。 决策规则 最近邻法在原理上最直观，方法上也十分简单。 明显的缺点就是计算量大，存储量大。 下面我们先定性的比较一下最近邻分类法与最小错误率的Bayes分类方法的分类能力。 我们把 的最近邻 的类别看成是一个随机变量 ， 的概率为后验概率 最近邻法错误率分析 按最小错误率的Bayes决策法则：以概率1决策 ； 按最近邻决策法则：以概率 决策 ； 最近邻法则可以看成是一个随机化决策 ——按照概率 来决定 的类别。 定义： 这里假设在三类问题中， 的后验概率分别为 按最小错误率的Bayes决策法则：以概率1决策 ； 按最近邻决策法则：以概率 决策 ；以概率 决策 。 当 时，最近邻法的决策结果与最小错误率的Bayes决策的决策结果相同，它们的错误率都是比较小的，两种方法同样的好，当 ，两者的错误概率接近于 ，两种方法同样的坏。下面我们将进一步分析近邻法的错误率。 最近邻法的错误率高于贝叶斯错误率，可以证明以下关系式成立： 由于一般情况下P*很小，因此又可粗略表示成： 可粗略说最近邻法的渐近平均错误率在贝叶斯错误率的两倍之内。 4.2 k-近邻法 k-近邻法: 最近邻法的扩展，其基本规则是，在所有N个样本中找到与测试样本的k个最近邻者，其中各类别所占个数表示成ki, i＝1，…，c。定义判别函数为： gi(x)=ki, i=1, 2,…,c。 k-近邻一般采用k为奇数，跟投票表决一样，避免因两种票数相等而难以决策。 决策规则为： argmax表示寻找具有最大评分的参量 在N→∞的条件下，k-近邻法的错误率要低于最近邻法。 最近邻法和k-近邻法的错误率上下界都是在一倍到两倍贝叶斯决策方法的错误率范围内。 最近邻法错误率分析 从上面可以看出近邻法有方法简单的优点，但也存在这一些缺点： （1）存储量和计算量都很大； （2）没有考虑决策的风险，如果决策的错误代价很大时，会产生很大的风险； （3）以上的分析——渐近平均错误率，都是建立在样本数趋向无穷大的条件下得来的，在实际应用时大多是无法实现的。 4.3 改进的近邻法 近邻法的一个严重不足与问题是需要存储全部训练样本，以及繁重的距离计算量。 两类改进的方法： 一种是对样本集进行组织与整理，分群分层，尽可能将计算压缩到在接近测试样本邻域的小范围内，避免盲目地与训练样本集中每个样本进行距离计算。 另一种则是在原有样本集中挑选出对分类计算有效的样本，使样本总数合理地减少，以同时达到既减少计算量，又减少存储量的双重效果。 快速有哪些信誉好的足球投注网站近邻法 其基本思想是将样本集按邻近关系分解成组，给出每组的质心所在，以及组内样本至该质心的最大距离。这些组又可形成层次结构，即组又分子组，因而待识别样本可将有哪些信誉好的足球投注网站近邻的范围从某一大组，逐渐深入到其中的子组，直至树的