第四章近邻法.pptVIP

剪辑近邻法因此如果能将不同类别交界处的样本以适当方式筛选，可以实现既减少样本数又提高正确识别率的双重目的。为此可以利用现有样本集对其自身进行剪辑。下面以两类别问题为例说明这种方法的原理。4.5.2k-近邻法第62页，共104页，星期日，2025年，2月5日剪辑近邻法假设现有一个样本集N，样本数量为N。将此样本集分成两个互相独立的样本子集。一个被当作考试集XNT,另一个作为参考集XNR，数量分别为NT与NR，NT+NR＝N。将XNT中的样本表示成xi(i=1,…,NT)，而在XNR中的样本表示为yi(i=1,…,NR)。4.5.2k-近邻法第63页，共104页，星期日，2025年，2月5日剪辑近邻法将一个样本集分成两个相互独立的样本子集是指，分完以后的两个子集具有相同的分布例如将一个样本集分成两个相互独立的对等子集，则在每个特征空间的子区域，两个子集都有相同的比例，或说各类数量近似相等。要注意的是每个子区域(从大空间到小空间)实际做时要用从总的集合中随机抽取的方式进行。4.5.2k-近邻法第64页，共104页，星期日，2025年，2月5日剪辑近邻法剪辑的过程是：首先对XNT中每一个xi在XNR中找到其最近邻的样本yi(xi)，用yi(xi)表示yi是xi的最近邻参考样本。如果yi与xi不属于同一类别，则将xi从XNT中删除，最后从XNT中得到一个经过剪辑的样本集，称为剪辑样本集。可用来取代原样本集，作为参考样本集对待识别样本进行分类。

4.5.2k-近邻法第65页，共104页，星期日，2025年，2月5日剪辑近邻法XNT经过剪辑后，要作为新的训练样本集，则XNR是对其性能进行测试的样本，如发现XNT中的某个训练样本对分类不利，就要把它剪辑掉。实际上剪辑样本的过程也可以用k-近邻法进行，即对XNT中的每个样本xi，找到在XNR中的k个近邻，用k-近邻法判断xi是否被错分类。从而决定其取舍，其它过程与前述方法完全一样。4.5.2k-近邻法第66页，共104页，星期日，2025年，2月5日剪辑近邻法剪辑近邻法也可用到多类别情况。剪辑过程也可不止一次。重复多次的称为重复剪辑近邻法。图1到图4是一个两类正态分布样本的重复剪辑结果，图1是原始样本集，图2是经一次迭代的结果，图3是三次迭代留下的样本，图4是算法终止时留下的样本。

4.5.2k-近邻法第67页，共104页，星期日，2025年，2月5日剪辑近邻法所使用的重复剪辑算法步骤如下：1.将样本集XNT随机划分为S个子集，即XN={X1,X2,…,Xs},s≥32.用最近邻法，以Xj,j=(i+1)mods为参考集，对Xi中的样本进行分类，其中i＝1，…，s。3.去掉步骤2中被错分类的样本。4.用所有留下的全部样本的构成新的样本集XNT5.如该次剪辑过程中没有样本被删除，则停止，否则转步骤1。4.5.2k-近邻法第68页，共104页，星期日，2025年，2月5日剪辑近邻法由此可见每次迭代过程都要重新对现有样本集进行重新随机划分，以保证了剪辑的独立性。4.5.2k-近邻法第69页，共104页，星期日，2025年，2月5日剪辑近邻法用近邻法容易出错的区域是在两类的交界处，这时某个训练样本存在与否就会影响到某些测试分类的结果。因此剪辑的效果往往把这些处于交界的训练样本给剪辑掉了。以上讨论了剪辑近邻法的原理与算法，另一个问题是对剪辑近邻法错误率的分析。这里只给出简单的结论：

4.5.2k-近邻法第70页，共104页，星期日，2025年，2月5日剪辑近邻法1.利用最近邻法剪辑后得到的样本集进行分类，其错误率总小于原样本集，如用P1E(e),表示其错误率，则有P1E(e)≤P(e)其中P(e)表示用原样本的渐近平均错误率。在P(e)很小，如P(e)0.1情况下可有P1E(e)=1/2P(e)由于近邻法错误率上界为2P*(两倍贝叶斯错误率)，因而P1E(e)=P*4.5.2k-近邻法第71页，共104页，星期日，2025年，2月5日剪辑近邻法2.利用k-近邻法进行剪辑得到的样本集进行分类，则在N→∞及k→∞，且K/N→0的条件下有PkE(e)=P*该式表明k很大时，剪辑样本法的错误率可收敛于最优情况P*。当然实际上k值不能取得太大。3.多类情况，剪辑效果更好。

4.5.2k-近邻法第72页，共104页，星期日，2025年，2月5日压缩近邻法从上述讨论中可以看出，剪辑近邻法所得到的剪辑样本集在样本数量的压缩方面并不十分明显