模式识别近邻法VIP免费

第四章近邻法4.1最近邻法(1-NearestNeighborAlgor.)一最近邻决策规则•假定有c类模式，ω1,ω2,…,ωc,每类有个样本，i=1,2,…,c，总样本数为。对未知样本，找出已知类别的训练样本集中和最近的一个样本，把分到与该样本一样的类。iNciiNN10x0x0x最近邻决策算法•存储训练样本；•对一新的样本x，在训练样本集中按某种距离度量找到x的最近邻(xi,yi)，令x的类别y和yi相同。•使用欧式距离时：•使用平方距离结果是一样的，免去了开方运算：近邻法和使用的距离度量关系很大•将所有的特征值规范到相同的范围（比如[-1，1]），否则取值范围大的特征起的作用大。•去掉噪声的、不好的特征，它们影响距离度量和性能。•利用好的距离度量，如式中是互信息。或利用Mahalanobis距离：●使用k-近邻更可靠。二最近邻法的错误率分析•下面先分析近邻法的错误率，然后讨论具体实施近邻法时的一些问题。•近邻法错误率分析的思想是把它和贝叶斯错误率联系起来最近邻法的错误率分析令是要分类的点，是它的最近邻,的真实类是，的真实类别是,对于和，发生错误的概率为0xkx0xpkxsk0xkxkskprxxP,00xkxpsk最近邻法的错误率分析•假定事件“是类”和“是类”是独立的事件，则最近邻算法的条件错误率为：0xpkxskcikiskriprNNxPxPxe1001最近邻法的错误率分析•如果密度函数是连续的，而且样本点相当多，则的最近邻将非常接近，因此可以合理地认为（假定）代入上式，有(*)0xkx0x00xPxPxPiriprkiskrciirciirirNNxPxPxPxe120100011最近邻法的错误率分析•下面分析这个错误率和贝叶斯错误率间的关系令是根据贝叶斯决策规则将所分的类，即：B0x00maxxPxPjrjBr最近邻法的错误率分析•贝叶斯决策的条件错误率为：(**)或写成(1)00001xPxPxePxeBrBiirrB001xexPBBr•为了导出的界，对(*)式中的平方项，有(***)0xeNNBiirBrciirxPxPxP2020120•对于固定的值，上式当，，都相等时取最小值。0xPBr0xPirBiciirciirirNNxPxPxPxe120100011•又由(**)式，使(***)式的取最小值的为（2）00xexPBBiirciirxP1200xPirBicxexPBir,10000001xPxPxePxeBrBiirrBBiirBrciirxPxPxP2020120•(***)式可以化为（把（1）和（2）代入）共(c-1)项，消除了一个(c-1)110220120cxexexPBBciirBiirBrciirxPxPxP2020120•把上式代入(*)式并化简有，（3）0200220012111xeccxecxexexeBBBBNNciirciirirNNxPxPxPxe120100011110220120cxexexPBBciir最近邻法的错误率分析•而近邻法和贝叶斯决策的错误率定义为：dxxpxPxeEciirNNNN121dxxpxexeEBBB最近邻法的错误率分析22BBxeE022xeExeExeVarBBB•取(3)式期望，并利用上式，有由于贝叶斯错误率是最小的，所以完整的上下界是：212BBNNccBBBNNBcc21220200220012111xeccxecxexexeBBBBNN最近邻法的错误率分析•上式的结果表明，当样本数相当多时，近邻法的错误率在贝叶斯错误率和两倍的贝叶斯错误率之间。的一些特殊情况•当时，BNNee1xPBr0xeB0xeNNBNNee•当各类的后验概率相等时的一些特殊情况BNNeecxPir1cccxeB111ccccxPxeciirNN111212...