模式识别_第6章_近邻法.ppt

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

1、1 1第第6 6章章 近邻法近邻法6.1最近邻法最近邻法，k近邻法近邻法6.2误判概率上下界误判概率上下界6.3 改进的近邻法改进的近邻法2 2BayesBayes方法需要借助概率密度函数估计。可以看出，其方法需要借助概率密度函数估计。可以看出，其方法需要借助概率密度函数估计。可以看出，其方法需要借助概率密度函数估计。可以看出，其应用受到很大限制。事实上，非参数模式识别方法更为应用受到很大限制。事实上，非参数模式识别方法更为应用受到很大限制。事实上，非参数模式识别方法更为应用受到很大限制。事实上，非参数模式识别方法更为实用。由于能解决许多实际的模式识别问题，虽然在许实用。由于能解决许多实际的模

2、式识别问题，虽然在许实用。由于能解决许多实际的模式识别问题，虽然在许实用。由于能解决许多实际的模式识别问题，虽然在许多情况下它们不是最优的，但却是应用的最多的有效的多情况下它们不是最优的，但却是应用的最多的有效的多情况下它们不是最优的，但却是应用的最多的有效的多情况下它们不是最优的，但却是应用的最多的有效的方法。统计模式识别中常用的基本非参数方法除了前面方法。统计模式识别中常用的基本非参数方法除了前面方法。统计模式识别中常用的基本非参数方法除了前面方法。统计模式识别中常用的基本非参数方法除了前面介绍的线性判别函数外，介绍的线性判别函数外，介绍的线性判别函数外，介绍的线性判别函数外，还有将要介绍

3、的近邻法和聚类。还有将要介绍的近邻法和聚类。还有将要介绍的近邻法和聚类。还有将要介绍的近邻法和聚类。近邻法属于有监督学习，聚类属于无监督学习。近邻法属于有监督学习，聚类属于无监督学习。近邻法属于有监督学习，聚类属于无监督学习。近邻法属于有监督学习，聚类属于无监督学习。它是在它是在它是在它是在已知模式类别的训练样本的条件下，绕开概率的估计，已知模式类别的训练样本的条件下，绕开概率的估计，已知模式类别的训练样本的条件下，绕开概率的估计，已知模式类别的训练样本的条件下，绕开概率的估计，按最近距离原则对待识别模式直接进行分类。按最近距离原则对待识别模式直接进行分类。按最近距离原则对待识别模式直接进行分

4、类。按最近距离原则对待识别模式直接进行分类。3 3近邻法近邻法最近邻分类器最近邻分类器最近邻分类器最近邻分类器(nearest neighborhood classifier,(nearest neighborhood classifier,nncnnc):最小距离分类器的一种极端的情况，最小距离分类器的一种极端的情况，最小距离分类器的一种极端的情况，最小距离分类器的一种极端的情况，以全部训练样以全部训练样以全部训练样以全部训练样本作为代表点本作为代表点本作为代表点本作为代表点，计算测试样本与所有样本的距离，计算测试样本与所有样本的距离，计算测试样本与所有样本的距离，计算测试样本与所有样本的距

5、离，并以最近邻者的类别作为决策。并以最近邻者的类别作为决策。并以最近邻者的类别作为决策。并以最近邻者的类别作为决策。最初的近邻法是由最初的近邻法是由最初的近邻法是由最初的近邻法是由CoverCover和和和和HartHart于于于于19681968年提出的，随年提出的，随年提出的，随年提出的，随后得到理论上深入的分析与研究，后得到理论上深入的分析与研究，后得到理论上深入的分析与研究，后得到理论上深入的分析与研究，是非参数法是非参数法是非参数法是非参数法中最中最中最中最重要的方法之一。重要的方法之一。重要的方法之一。重要的方法之一。4 4c c类问题类问题,设设最近邻方法最近邻方法6.1 最近邻

6、决策规则最近邻决策规则1-NN1-NN最近邻分类规则最近邻分类规则:对待识别模式对待识别模式 ,分别计算它与分别计算它与个已知类别的样本个已知类别的样本 的距离的距离,将它判为距离最将它判为距离最近的那个样本所属的类。近的那个样本所属的类。如果如果则则即即5 5最近邻方法最近邻方法6.1 最近邻决策规则最近邻决策规则1-NN1-NN(1)(1)已知已知N N个已知个已知类别样本类别样本X X(2)(2)输入未知类别输入未知类别样本样本x x(3)(3)计算计算x x到到x xi i X X，(i=1,(i=1,2,2,N),N)的的距离距离d di i(x(x)(4)(4)找出最小距离找出最小

7、距离d dm m(x(x)=)=mindmindi i(x(x)(5)(5)看看x xm m属于哪属于哪一类：一类：x xm m 2 2(6)(6)判判x x 2 26 6k-NNk-NN分类思想分类思想:对待识别模式对待识别模式 ,分别计算它与分别计算它与个已知类别的样本个已知类别的样本 的距离的距离,取取k k个最近邻样本个最近邻样本,这这k k个样本中哪一类最多个样本中哪一类最多,就判属哪一类就判属哪一类。最近邻方法最近邻方法6.1 最近邻决策规则最近邻决策规则k-NNk-NN即即,令令 与与i i的距离的距离如果如果则则其中其中 表示表示k k个近邻元中属于个近邻元中属于i i的样本个

8、数的样本个数7 7最近邻方法最近邻方法6.1 最近邻决策规则最近邻决策规则k-NNk-NN(1)(1)已知已知N N个已知个已知类别样本类别样本X X(2)(2)输入未知类别输入未知类别样本样本x x(6)(6)判判x x 2 2(4)(4)找出找出x x的的k k个最近邻个最近邻元元X Xk k=x xi i,i,i=1,2,=1,2,k,k(5)(5)看看X Xk k中属于哪一类的样中属于哪一类的样本最多本最多k k1 1=3k=3k2 2=4=4(3)(3)计算计算x x到到x xi i X X，(i=1,(i=1,2,2,N),N)的的距离距离d di i(x(x)8 8下面我们先定性

9、的比较一下最近邻分类法与最小错误率下面我们先定性的比较一下最近邻分类法与最小错误率下面我们先定性的比较一下最近邻分类法与最小错误率下面我们先定性的比较一下最近邻分类法与最小错误率的的的的BayesBayes分类方法的分类能力。分类方法的分类能力。分类方法的分类能力。分类方法的分类能力。我们把我们把我们把我们把 的最近邻的最近邻的最近邻的最近邻 的类别看成是一个随机变量的类别看成是一个随机变量的类别看成是一个随机变量的类别看成是一个随机变量 ，的概率为后验概率的概率为后验概率的概率为后验概率的概率为后验概率最近邻法错误率分析最近邻法错误率分析9 9按最小错误率的按最小错误率的按最小错误率的按最小

10、错误率的BayesBayes决策法则：以概率决策法则：以概率决策法则：以概率决策法则：以概率1 1决策决策决策决策 ；按最近邻决策法则：以概率按最近邻决策法则：以概率按最近邻决策法则：以概率按最近邻决策法则：以概率 决策决策决策决策 ；最近邻法则可以看成是一个随机化决策最近邻法则可以看成是一个随机化决策最近邻法则可以看成是一个随机化决策最近邻法则可以看成是一个随机化决策 按照概率按照概率按照概率按照概率 来决定来决定来决定来决定 的类别。的类别。的类别。的类别。定义：定义：定义：定义：1010这里假设在三类问题中，这里假设在三类问题中，这里假设在三类问题中，这里假设在三类问题中，的后验概率分别

11、为的后验概率分别为的后验概率分别为的后验概率分别为按最小错误率的按最小错误率的按最小错误率的按最小错误率的BayesBayes决策法则：以概率决策法则：以概率决策法则：以概率决策法则：以概率1 1决策决策决策决策 ；按最近邻决策法则：以概率按最近邻决策法则：以概率按最近邻决策法则：以概率按最近邻决策法则：以概率 决策决策决策决策 ；以；以；以；以概率概率概率概率 决策决策决策决策 。当当当当 时，最近邻法的决策结果与最小错误率的时，最近邻法的决策结果与最小错误率的时，最近邻法的决策结果与最小错误率的时，最近邻法的决策结果与最小错误率的BayesBayes决策的决策结果相同，它们的错误率都是比较

12、小决策的决策结果相同，它们的错误率都是比较小决策的决策结果相同，它们的错误率都是比较小决策的决策结果相同，它们的错误率都是比较小的，两种方法同样的好，当的，两种方法同样的好，当的，两种方法同样的好，当的，两种方法同样的好，当 ，两者的错误，两者的错误，两者的错误，两者的错误概率接近于概率接近于概率接近于概率接近于 ，两种方法同样的坏。下面我们将进一，两种方法同样的坏。下面我们将进一，两种方法同样的坏。下面我们将进一，两种方法同样的坏。下面我们将进一步分析近邻法的错误率。步分析近邻法的错误率。步分析近邻法的错误率。步分析近邻法的错误率。1111最近邻法的错误率高于贝叶斯最近邻法的错误率高于贝叶斯

13、最近邻法的错误率高于贝叶斯最近邻法的错误率高于贝叶斯错误率，可以证明以下关系错误率，可以证明以下关系错误率，可以证明以下关系错误率，可以证明以下关系式成立：式成立：式成立：式成立：uuu由于一般情况下由于一般情况下由于一般情况下由于一般情况下P P*很小，很小，很小，很小，因此又可粗略表示成：因此又可粗略表示成：因此又可粗略表示成：因此又可粗略表示成：uuu可粗略说最近邻法的渐近平可粗略说最近邻法的渐近平可粗略说最近邻法的渐近平可粗略说最近邻法的渐近平可粗略说最近邻法的渐近平可粗略说最近邻法的渐近平均错误率在贝叶斯错误率的均错误率在贝叶斯错误率的均错误率在贝叶斯错误率的均错误率在贝叶斯错误率的

14、均错误率在贝叶斯错误率的均错误率在贝叶斯错误率的两倍之内。两倍之内。两倍之内。两倍之内。两倍之内。两倍之内。1212在在N的条件下，的条件下，k-近邻法的错误率要低于近邻法的错误率要低于最近邻法。最近邻法。最近邻法和最近邻法和k-近邻法的错误率上下界都是在一近邻法的错误率上下界都是在一倍到两倍贝叶斯决策方法的错误率范围内。倍到两倍贝叶斯决策方法的错误率范围内。最近邻法错误率分析最近邻法错误率分析1313从上面可以看出近邻法有方法简单的优点，但也存在从上面可以看出近邻法有方法简单的优点，但也存在从上面可以看出近邻法有方法简单的优点，但也存在从上面可以看出近邻法有方法简单的优点，但也存在这一些缺点

15、：这一些缺点：这一些缺点：这一些缺点：（1 1 1 1）存储量和计算量都很大；）存储量和计算量都很大；）存储量和计算量都很大；）存储量和计算量都很大；（2 2 2 2）没有考虑决策的风险，如果决策的错误）没有考虑决策的风险，如果决策的错误）没有考虑决策的风险，如果决策的错误）没有考虑决策的风险，如果决策的错误代价代价代价代价很很很很大时，会产生很大的风险；大时，会产生很大的风险；大时，会产生很大的风险；大时，会产生很大的风险；（3 3 3 3）以上的分析）以上的分析）以上的分析）以上的分析渐近平均错误率，都是建立在渐近平均错误率，都是建立在渐近平均错误率，都是建立在渐近平均错误率，都是建立在样

16、本数趋向无穷大的条件下得来的，在实际应用时大样本数趋向无穷大的条件下得来的，在实际应用时大样本数趋向无穷大的条件下得来的，在实际应用时大样本数趋向无穷大的条件下得来的，在实际应用时大多是无法实现的。多是无法实现的。多是无法实现的。多是无法实现的。14146 6.3 3 改进的近邻法改进的近邻法近邻法的一个严重不足与问题是需要近邻法的一个严重不足与问题是需要存储全部存储全部训练样本训练样本，以及繁重的，以及繁重的距离计算距离计算量。量。两类改进的方法：两类改进的方法：一种是对样本集进行组织与整理，分群分层，尽一种是对样本集进行组织与整理，分群分层，尽一种是对样本集进行组织与整理，分群分层，尽一种

17、是对样本集进行组织与整理，分群分层，尽可能将计算可能将计算可能将计算可能将计算压缩压缩压缩压缩到在接近测试样本邻域的小范围到在接近测试样本邻域的小范围到在接近测试样本邻域的小范围到在接近测试样本邻域的小范围内，避免盲目地与训练样本集中每个样本进行距内，避免盲目地与训练样本集中每个样本进行距内，避免盲目地与训练样本集中每个样本进行距内，避免盲目地与训练样本集中每个样本进行距离计算。离计算。离计算。离计算。另一种则是在原有样本集中挑选出对分类计算另一种则是在原有样本集中挑选出对分类计算另一种则是在原有样本集中挑选出对分类计算另一种则是在原有样本集中挑选出对分类计算有有有有效的样本效的样本效的样本效

18、的样本，使样本总数合理地减少，以同时达到，使样本总数合理地减少，以同时达到，使样本总数合理地减少，以同时达到，使样本总数合理地减少，以同时达到既减少计算量，又减少存储量的双重效果。既减少计算量，又减少存储量的双重效果。既减少计算量，又减少存储量的双重效果。既减少计算量，又减少存储量的双重效果。1515对于两类问题，设将已知类别的样本集对于两类问题，设将已知类别的样本集X X(N)(N)分成参分成参照集照集X X(NR)(NR)和测试集和测试集X X(NT)(NT)两部分，两部分，X X(NR)(NR)X X(NT)(NT)=，它，它们的样本数各为们的样本数各为NRNR和和NTNT，NR+NT=

19、NNR+NT=N。利用参照集。利用参照集X X(NR)(NR)中的样本中的样本 采用最近邻规则对已采用最近邻规则对已知类别的测试集知类别的测试集X X(NT)(NT)中的每个样本中的每个样本 进行分类，剪辑掉进行分类，剪辑掉X X(NT)(NT)中被错误分类的样本。中被错误分类的样本。与与 异类的异类的 ，余下的判决正确的样本组成剪，余下的判决正确的样本组成剪辑样本集辑样本集X(NTE)。这一操作称为。这一操作称为剪辑剪辑。若若是是的最近邻元，剪辑掉的最近邻元，剪辑掉6.2 剪辑最近邻方法剪辑最近邻方法1616获得剪辑样本集获得剪辑样本集X(NTE)后，对待识模式后，对待识模式 采用采用最近邻

20、规则进行分类。最近邻规则进行分类。如果如果则则这里这里剪辑最近邻方法剪辑最近邻方法1717剪辑最近邻方法剪辑最近邻方法 1 2 X(NR)X(NT)用用X X(NR)(NR)中的样本采中的样本采用最近邻规则对用最近邻规则对X X(NT)(NT)中的每个样本中的每个样本分类，剪辑掉分类，剪辑掉X X(NT)(NT)中被错误分类的样中被错误分类的样本。本。余下判决正确的余下判决正确的样本组成剪辑样样本组成剪辑样本集本集X(NTE)。用用X(NTE)对输入对输入的未知样本做的未知样本做K-NNK-NN分类。分类。1818剪辑最近邻法可以推广至剪辑最近邻法可以推广至k-NNk-NN近邻法中。步骤：近邻

21、法中。步骤：第一步第一步 用用k-NN k-NN 法进行剪辑法进行剪辑;第二步第二步 用用1-NN 1-NN 法进行分类。法进行分类。如果样本足够多，就可以重复地执行剪辑程如果样本足够多，就可以重复地执行剪辑程序，以进一步提高分类性能。称为序，以进一步提高分类性能。称为重复剪辑最近重复剪辑最近邻法邻法。剪辑最近邻方法剪辑最近邻方法 6.2.2 剪辑剪辑k k-NN-NN最近邻方法最近邻方法1919（1 1）将样本集将样本集X X(N)(N)随机地划分为随机地划分为s s个子集：个子集：（2 2）用最近邻法，以用最近邻法，以 为参照集，对为参照集，对X Xi i中中的样本进行分类，其中的样本进行

22、分类，其中i=1,2,i=1,2,s,s;（3 3）去掉（）去掉（2 2）中被错误分类的样本；）中被错误分类的样本；（4 4）用所留下的样本构成新的样本集）用所留下的样本构成新的样本集X X(NE)(NE)；（5 5）如果经过）如果经过k k 次迭代再没有样本被剪辑掉则停次迭代再没有样本被剪辑掉则停止；否则转至（止；否则转至（1 1）。）。MULTIEDITMULTIEDIT算法算法剪辑最近邻方法剪辑最近邻方法 6.2.3 重复重复剪辑最近邻方法剪辑最近邻方法2020 妈妈新开了个淘宝店，欢迎前来捧场妈妈新开了个淘宝店，欢迎前来捧场妈妈的淘宝点开了快半年了，主要卖的是毛绒玩具、坐垫、抱枕之类的

23、，妈妈的淘宝点开了快半年了，主要卖的是毛绒玩具、坐垫、抱枕之类的，但生意一直不是很好，感觉妈妈还是很用心的，花了不少功夫，但是就是没但生意一直不是很好，感觉妈妈还是很用心的，花了不少功夫，但是就是没有人气，所以我也来出自己的一份力，帮忙宣传一下。有人气，所以我也来出自己的一份力，帮忙宣传一下。并且妈妈总是去五亭龙挑最好的玩具整理、发货，质量绝对有保证。并且妈妈总是去五亭龙挑最好的玩具整理、发货，质量绝对有保证。另外我家就在扬州五亭龙玩具城旁边，货源丰富，质量可靠，价格便宜。另外我家就在扬州五亭龙玩具城旁边，货源丰富，质量可靠，价格便宜。欢迎大家来逛逛欢迎大家来逛逛【扬州五亭龙玩具总动员扬州五亭龙玩具总动员】个人小广告：个人小广告：