03第三章非参数判别分类方法3_6.ppt

3.6 近邻法;重点;3.6.1 近邻法原理及其决策规则;将与测试样本最近邻样本的类别作为决策的方法称为最近邻法。对一个C类别问题，每类有Ni个样本，i＝1,…,C, 则第i类ωi的判别函数;基本规则是，在所有N个样本中找到与测试样本的k个最近邻者，其中各类别所占个数表示成ki,i＝1,…,c，则决策规划是：;计算错误的偶然性：因为训练样本集的数量总是有限的，有时多一个少一个训练样本对测试样本分类的结果影响很大。 ;如果所用训练样本集的样本数量N极大，即N→∞时，可以想像X将趋向于X，或者说处于以X为中心的极小邻域内，此时分析错误率问题就简化为在X样本条件下X与一个X(X的极限条件)分属不同类别的问题。如果样本X的两类别后验概率分别为P(ω1|X)与P(ω2|X)，那么对X值，在N→∞条件下，发生错误决策的概率为：;(3.6-1);渐近平均错误率，是PN(e)在N→∞的极限。 ;由;思考;当N→∞时，最近邻法的渐近平均错误率的下界是贝叶斯错误率，这发生在样本对某类别后验概率处处为1的情况或各类后验概率相等的情况。;k—近邻法错误率分析;将(3.6-7)与(3.6-6)相比较，(3.6-6)相当于(3.6-7)中k＝1的情况，而在(3.6-7)中当k增大时PkN→∞(e|X)是单调递减的。因此可以得出结论，在N→∞的条件下，k-近邻法的错误率要低于最近邻法，从图中也可看出，无论是最近邻法，还是k-近邻法，其错误率的上下界都是在一倍到两倍贝叶斯决策方法的错误率范围内。;3.6.3 改进的近邻法;3.6.3.1 快速有哪些信誉好的足球投注网站近邻法;首先将整个样本分成l个子集，每个子集又分为它的l个子集。分成子集的原则是该子集内的样本尽可能聚成堆，这可用聚类方法实现。;树形结构样本集;要实现快速有哪些信誉好的足球投注网站近邻，需要有方法快速判断某个样本子集是否是该待识样本的可能近邻样本集，从而可将无关的样本子集尽快排除。另一方面在某样本子集内寻找哪个样本是近邻时，需快速排除不可能为近邻的样本。这两个快速判别算法可用以下两个规则表示：;这个规则的证明是显而易见的，下图表示一待识样本及其当前近邻与一样本子集的关系。;规则2：;当有哪些信誉好的足球投注网站树形样本集结构由高层次向低层次深入时，对同一层次的所有结点，可以利用规则1排除掉一些不可能包含待识别样本的近邻的结点(样本子集)。但是这往往不能做到只留下唯一的待有哪些信誉好的足球投注网站结点，因此必须选择其中某一结点先深入有哪些信誉好的足球投注网站，以类似于深度优先的方法确定有哪些信誉好的足球投注网站路径直至叶结点。然而在该叶结点中找到的近邻并不能保证确实是全样本集中的最近邻者，所找到的该近邻样本需要在那些有可能包含最近邻的样本子集中核对与修正，直至找到真正的最近邻样本为止。;步骤1：[初始化]置B＝∞，L＝1(当前层次)，p＝0(确定当前结点)。;步骤5：[近邻样本有哪些信誉好的足球投注网站]对现在执行结点p中的每个样本Xi，利用规则2作如下检验： 如果D(X，Mp)＞D(Xi,Mp)+B则Xi不是X的最近邻，否则计算D(X，Xi)，若D(X，Xi)＜B，置NN＝i和B＝D(X,Xi)。对当前执行结点中所有Xi被检验后，转步骤3。;k-近邻法快速计算是有哪些信誉好的足球投注网站待测样本的k个最近邻，以做到最后在这k个最近邻中计算占多数的训练样本类别。因此只要发现有一个训练样本比当前第k个近邻的距离要小，就把当前第k个近邻剔除出当前k近邻组。 ;3.6.3.2 剪辑近邻法;当不同类别的样本在分布上有交迭部分的，分类的错误率主要来自处于交迭区中的样本。当我们得到一个作为识别用的参考样本集时，由于不同类别交迭区域中不同类别的样本彼此穿插，导致用近邻法分类出错。因此如果能将不同类别交界处的样本以适当方式筛选，可以实现既减少样本数又提高正确识别率的双重目的。为此可以利用现有样本集对其自身进行剪辑。下面以两类别问题为例说明这种方法的原理。;假设现有一个样本集N，样本数量为N。将此样本集分成两个互相独立的样本子集。一个被当作考试集?NT，另一个作为参考集?NR，数量分别为NT与NR，NT+NR＝N。将?NT中的样本表示成Xi,(i=1,2,…, NT)，而在?NR中的样本表示为Yj,(j=1,2,…, NR)。 ;首先对?NT中每一个Xi在?NR中找到其最近邻的样本Yi(Xi)，用Yi(Xi)表示Yi是Xi的最近邻参考样本。如果Yi与Xi不属于同一类别，则将Xi从?NT中删除，最后从?NT中得到一个经过剪辑的样本集，称为剪辑样本集?NTE。 ?NTE可用来取代原样本集?N，作为参考样本集对待识别样本进行分类。;剪辑样本的过程也可以用k-近邻法进行。;1. 将样本集?N随机划分为S个子集，即;从图1到图4可以看出,剩下的样本集形成了两个很好的聚类,并且在每个聚类中的样本都属于同一类.;图3 经三次迭代的结果;1. 利用最近邻法剪辑后得到的样本集进行