第5章近邻法

第5章近邻法第5章近邻法5.1最近邻法5.2k—近邻法5.3剪辑近邻法5.4可做拒绝决策的近邻法第5章近邻法前面我们介绍了Bayes方法和概率密度函数的估计。可以看出，Bayes方法的应用受到很大限制。事实上，非参数模式识别方法更为实用。由于能解决许多实际的模式识别问题，虽然在许多情况下它们不是最优的，但却是应用的最多的有效的方法。统计模式识别中常用的基本非参数方法除了前面介绍的线性判别函数外，还有本章将要介绍的近邻法和集群。近邻法属于有监督学习，集群属于无监督学习。近邻法是由Cover和Hart于1968年提出来的。它是在已知模式类别的训练样本的条件下，绕开概率的估计，按最近距离原则对待识别模式直接进行分类。返回本章首页第5章近邻法5.1最近邻法返回本章首页最近邻决策规则给定c个类别，每类有标明类别的样本个，近邻法的判别函数为决策法则为直观的说，就是对待识别的模式向量，只要比较与所有已知类别的样本之间的欧式距离，并决策与离它最近的样本同类。x12,,,cxxiN()min,1,2,,kiiiigkNxxx()min(),1,2,,jiiggicjxxx第5章近邻法返回本章首页132x第5章近邻法返回本章首页下面我们先定性的比较一下最近邻分类法与最小错误率的Bayes分类方法的分类能力。我们把的最近邻的类别看成是一个随机变量，的概率为后验概率最近邻法则可以看成是一个随机化决策——按照概率来决定的类别。定义：xNxn,1,,2,iicNlim()()iiNPPNxxx()iPx()max()1,2,,miPPicxx第5章近邻法返回本章首页按最小错误率的Bayes决策法则：以概率1决策；按最近邻决策法则：以概率决策；这里假设在三类问题中，的后验概率分别为按最小错误率的Bayes决策法则：以概率1决策；按最近邻决策法则：以概率决策；以概率决策。当时，最近邻法的决策结果与最小错误率的Bayes决策的决策结果相同，它们的错误率都是比较小的，两种方法同样的好，当，两者的错误概率接近于，两种方法同样的坏。下面我们将进一步分析近邻法的错误率。()mPxmmx123()0.4()0.3()0.3PPPxxx1x1()0.4Px1x11()0.6Px1x()1mPx1()mPcx11c第5章近邻法返回本章首页最近邻法的错误率分析在前面我们曾给出平均错误率的在最小错误率的Bayes决策中，决策使条件错误率尽可能小，从而平均错误率也一定最小。这里，设采用N个样本的最近邻法的平均错误率，并设()max()1,2,,miPPicxx()()()PePepdxxx()Pex()Pe()1()()()mPePPPepdxxxxx()NPelim()NNPPe第5章近邻法返回本章首页则有以下的不等式成立：证明：最近邻法属于随机化决策，待分类模式的近邻随样本集的变化而随机变化，设其最近邻为，错误的条件错误率为。对于取平均21cPPPPc()NPex,xlim()()Npxxxx11()1(,)1()()ccNiiiiiiPePPPx,xx,xxxxx()()()NNPePepdxx,xxxxx第5章近邻法返回本章首页212121lim()lim()()lim1()()lim1()1(())NNNNciNiciNiciiPePepdPpdPdPxx,xxxxxxxxxxxxx11()1(,)()()1cciiiiiiNPePPPx,xx,xxx21lim()1()cNiNiPePx,xx第5章近邻法返回本章首页下面我们看一下上面的两个表达式。设对于给定的，概率密度是连续的且不为零。那么，任何样本落入以为中心的一个超球S中的概率为N个独立的样本落在S外的概率为即是，一个样本也不落在S内的概率为0，也就是说总有一个样本落在S内的概率为1。无论S多么小，这个结论也是成立的，所以lim()()Npxxxxx()SPpdxSxxx(1)NSPlim(1)0NSNPlim()()Npxxxx第5章近邻法返回本章首页21lim()lim()()1()()NNNNciiPPePepdPpdxxxxxx上式即是最近法错误率的计算公式，先看下界的证明，这里指出下面的两种特殊情况。（1）（2）21()1()0()()01()()1mciiPePPPepdPPpdxxxxxxxx()1mPx1()1,2,,iPiccx21()1()(1)()()(1)1()()(1)mciiPePccPPepdccPPpdccxxxxxxxxPP第5章近邻法返回本章首页现在在来求最近邻法分类错误率的精确上界。2221222221222122()1()()()min1()()()()()()()()()()1()12)1)(((ciicimimiiimimccimiiimiimimimciimPPpdPPPPPPPPPePPePPPePePcxxxxxxxxxxxxxxxxxx2)()1cPecxx第5章近邻法返回本章首页221221221222()12()()11()2()()11()()2()()()12()()()()12(2)211()ciiciiciicPPePeccPPePeccPPpdPePepdccPepdPepdcccPPPPPccPexxxxxxxxxxxxxxxxxxxx2()pdPxx第5章近邻法返回本章首页例题1设在一个二维空间，A类有三个训练样本，图中用红点表示，B类四个样本，图中用蓝点表示。试问：（1）按近邻法分类，这两类最多有多少个分界面（2）画出实际用到的分界面（3）A1与B4之间的分界面没有用到1A2A3A2B3B1B4B第5章近邻法返回本章首页答：按近邻法，对任意两个由不同类别的训练样本构成的样本对，如果它们有可能成为测试样本的近邻，则它们构成一组最小距离分类器，它们之间的中垂面就是分界面，因此由三个A类与四个B类训练样本可能构成的分界面最大数量为3×4＝12。实际分界面如下图所示，由9条线段构成：1A2A3A2B3B1B4B第5章近邻法返回本章首页例题2当时，（1）证明一维问题的Bayes错误率（2）证明此时最近邻法渐近平均错误率1,01()1,110,icrxccrpixicx其它1()iPcPrPrPP第5章近邻法返回本章首页解：11()()()()()()()()1,011,01()1,1()11,0,1,0()11,ciiiiiciiiiimpPPppPpPcrxcrccxccrPixipcccrxPccxxxxxxxx其它其它其它第5章近邻法返回本章首页1021201111,0()1()10,11()()(1)()111()()1()mcrccrccciiicrxPePccccrPPepdpdrcccPPpdpdPcxxxxxxxxxxxx其它课后习题P160：6.36.46.5P81：3.13.43.15第5章近邻法5.2k—近邻法返回本章首页k—近邻法是在近邻法的基础上加以改进而来的，这个法则就是在的k个近邻中，按出现最多的样本类别来作为的类别。前面我们详细讨论了近邻法的错误率的表达式及其上下界。同样，对于k—近邻法则，我们也讨论一下错误率的问题，这里以和二类问题为例。为避免出现而不能判决的情况，我们取为奇数。对待识别模式误分类有以下两种情况：x1xx212kk12kkk(1)212112120(1)221201211212()()()()2kjjkjkjkjjkjkjkkkkkkCPPPPkkCxxxxxx第5章近邻法返回本章首页前面我们已经说过，当，的k个已知类别的最近邻样本以概率1收敛于，所以这k个样本可以不标出下标，统记为。对于给定的的条件错误率为12,,,kxxx12(1)21101(1)2120(1)221(1)20111()(()()()()()1()1)()(())))(1(kNkkjjjkkjjkjkjkjjkjkjkkjjjkjkjCPPCPPPPPPePPPCPCPxxxxxxxxxxxxxxNxxx第5章近邻法返回本章首页(1)21110111(1)21111(1)21211()()()1()1()()1()()12()()1()min(),()min(),1(()kkjjkjNkjkkjjjkjkkkjjjkjkPePCPPPCPPPPCPePPPPPPxxxxxxxxxxxxxxxx(1)2)()()()121()()kkjjkjNkjkPeCPePePePexxxxx第5章近邻法返回本章首页渐近平均错误率这里定义Bayes条件错误率的函数为大于的最小凹函数，即对所有的()kNPEPex()Pex()kCPex()kNPex()()kNkPeCPexxx()()()()kNkkkPEPeECPeCEPeCPxxx()kNkkPCP11()()()2(1)21kkcPPCPCPCPPPPPcPP第5章近邻法返回本章首页近邻法则讨论11()()()2(1)21kkPPCPCPCPPPcPPPPcP(1)cc(1)ccP0P0.50.5P1k()kCP5k7k0第5章近邻法返回本章首页从上面可以看出近邻法有方法简单的优点，但也存在这一些缺点：（1）存储量和计算量都很大；（2）没有考虑决策的风险，如果决策的错误代价很大时，会产生很大的风险；（3）以上的分析——渐近平均错误率，都是建立在样本数趋向无穷大的条件下得来的，在实际应用时大多是无法实现的。第5章近邻法5.3剪辑近邻法NTX返回本章首页这种方法的思想是,清理两类间的边界，去掉类别混杂的样本，使两类边界更清晰。这种方法的性能在理论上明显好于一般的最近邻法。1剪辑最近邻法对于两类问题，设将已知类别的样本集分成参照集和考试集两部分，这两部分没有公共元素，两部分的样本数分别为和，且。第一步：利用参照集中的样本采用最近邻法对考试集中的样本进行分类，剪辑掉中被错分类的样本，具体的说就是：是的最近邻元，剪辑掉中不与同类余下的部分构成剪辑样本集。NXNRNRXNTXNTNRNTN12,,,NRyyy