模式识别课件(第六章NO1)(最近邻法).ppt

1、第六章 近邻法,6.1 最近邻法 一. 最近邻法的基本思想 此法是一种根据全部样本提供的信息，绕开概率的估计而直接决策的方法，所以它是非参数决策方法的一种。 其基本思想是：设有一组N个样本 = X1,X2,XN 其中每个样本都已标以类别标志。如果在这N个样本中与待分样本X相距最近的一个样本为Xi，则把X分到Xi所在的类别中去。,二. 最近邻法的决策规则 设有c类模式样本， 1, 2, c 每类有Ni个样本(i=1,2,c)，则最近邻法的(i类)判别函数为: 式中 表示i类中的第k个样本。,对应的决策规则为： 如果 则决策 即只要将待分样本X与全部N( )个已知类别的样本进行欧氏距离之间的比较，

2、然后将X归到离它最近的类别中。 由于这种方法只根据离待分样本X最近的一个样本的类别而决定其类别，所以通常称为1-最近邻法(亦称1-NN方法),三. 最近邻法的错误率问题 最近邻法是一种次优方法，它的错误率比最小错误概率的Bayes决策规则下的错误率要大，但是，当样本数目无限时，它的错误率不会超过Bayes错误率的一倍。 定性分析： 若将X的最近邻Xj的类别看成是一个随机变量 ，于是 的概率就是后验概率 . 当样本数目很多时，可以认为X的最近邻Xj 离它很近，从而近似的认为,这时最近邻法可看成是如下的随机化决策： 按照概率 来决定X的类别。 故最近邻法可看成是用后验概率来对X进行分类的。 再进一

3、步说，就是如果有下式成立： 则依Bayes决策，应取 作为X的类别。而在最近邻法中，最近邻的类别为 的概率为 ，所以X分到 类去的概率为 ，而不分到 类去的概率为：,这也就是说： 按Bayes决策的话：以概率为1，而得决策 按最近邻法决策的话：以概率为，而得决策 显然，当接近于1时，最近邻法与最小错误率下的Bayes法的结果就几乎相同了。也就是说，当最小错误概率较小时，最近邻法的错误概率也是较小的，这两种方法同样“好”。 而当各类的都接近于 时(即所有类别是等可能的)，最近邻法与Bayes法的结果就不一样了。这时两者的错误率都接近于,定量描述： 式中：p为最近邻法的渐近平均错误率 为 Baye

4、s错误率 c 为类别数 一般较小,6.2 k-近邻法(k-NN法) 为了克服单个样本类别的偶然性以增加分类的可靠性，可将最近邻法则进行改进，一个简单的方法就是k-近邻法。 此法就是考察待分样本X的k个最近邻样本，这k个最近邻元素中哪一类的样本最多，就将X判属哪一类。或者说，就是在N个已知类别的样本中，找出X的k个近邻，这k个近邻中多数属于的那一类 ，就是 。 具体就是：设k1,k2,.,kc分别为X的k个最近邻样本中属于 类的样本数，,则定义 类的判别函数为： 决策规则为： 如果 则判 最近邻法和k-近邻法的共同优点是简单，而且结果是比较好的，但是它们也存在下述问题： 需要将全部样本存入机器中

5、，每次决策都要计算X与全部样本间的距离并进行比较。所以要求的存储容量和计算量都很大。 没有考虑到决策的风险，所以如果决策的错误代价很大时，会产生很大的风险。 上述分析是建立在样本数 的假定上的，这在实际应用中是无法实现的。,6.3 近邻法的改进算法 共同特点是如何尽快地找出最近邻可能存在的小的空间，减少搜索的范围，从而达到减少近邻法中的计算量和存储量的问题。 一. 快速近邻算法 该算法对最近邻法和k-近邻法都适用。下面以最近邻法为例来讨论。 1. 基本思想 将全部已知样本按级分成一些不相交的子集，并在子集的基础上进行搜索。也就是说，该算法由两个阶段组成： 第一阶段：将样本集按级分解，形成树状结

6、构。 第二阶段：用搜索算法找出待识样本的最近邻。,2. 涉及的规则 设=X1,X2,XN表示全部样本集； P表示节点P对应的样本子集，即P； NP表示P中的样本数； MP表示P中的样本均值(即“类心”)； rP ：表示从MP到Xip 的最大距离； B表示除p中的样本之外的样本到待分样本X的最近距离。B的初值设为，以后再不断修正。 规则1如果存在 则Xip不可能是X的最近邻。,证明：对任意 ，据三角不等式有 而据 rp定义有 由上两式可得 即得 则 不可能是X的最近邻。,的近邻,i,Mp,rP,规则2.如果存在 则 不可能是X的最近邻。 证明：比较规则1与规则2，并参图，可知 故得证。,3. 快

7、速近邻算法 第一阶段：将样本集按级分解。 首先将分为l个子集，每个子集再分成l个子子集，依次分下去，图6.3为l=3的情况。这时每个节点上对应一群样本。 第二阶段：搜索 树搜索算法： step1：设置B=，L=0，P=0.(L是当前水平，P是当前节点)。 step2：将当前节点P的所有直接后继节点(即子节点)放入一个目录表中，并对这些节点X计算,二. 剪辑近邻法 此类方法的基本思想是：剪掉(清理)两类间的边界，取掉类别混杂的样本，使两类边界更清晰。 1. 两分剪辑近邻法(亦称剪辑最近邻法) 基本过程为： 设N个样本分成c类 = , , (N1+N2+,+Nc= N) step1：剪辑。利用已知样本集 中的样本进行预分 类，并剪辑掉被错分类的样本，留下的样本构成 剪辑样本集 step2：分类。利用 和近邻规则对未知样本X进行 分类。,下面以两类情况进行具体介绍： 设将已知类别的样本集N分成测试集NT和参照集NR两个独立的部分(即这两部分没有公共元素)，它们的样本数各为NR和NT，且NR+NT=N。 剪辑步：利用参照集NR中的样本 对测试集NT 中的