6.3.2剪辑近邻法 6.3.2剪辑近邻法 口错误率分析（渐进错误率) 口重复剪释算法(MULTIEDIT) ■用最近邻法剪辑后得到的样本集进行分类，其错 1.将样本集随机划分为S(≥3)个子集，K,,K 误率总小于没有剪辑的最近邻法的错误率，即 2.用最近邻法，以K0=(+1)modS)为参考集， P(e)≤P(e 对K中的样本进行分类，其中i=1,…,S ■用k~近邻法进行剪辑得到的样本集进行分类，则 3.去掉步骤2中被错分类的样本 在N一∞及k∞，且kN一0的条件下有 4.用所有留下的全部样本的构成新的样本集KT。 P(e)=P'; 5.如经k次迭代后，再没有样本被剪辑掉，则停 止；否则转步骤1. ■多类情况，多类剪辑近邻错误率小于两类情况： 每次迭代时都要对现有样本集进行重新随机划 ■重复剪辑：样本足够多时，重复剪辑效果更好。 分，以保证剪辑的独立性。 6.3.4压缩近邻法 原始祥本集 口基本思想：利用现有样本集，逐渐生成一个新的 下的样 一次选 样本集，使该样本集在保留最少量样本的条件 下，仍能对原有样本的全部用最近邻法正确分 类；那么该样本集也能对待识别样本进行分类， 并保持正常识别率。 留下的样 口算法思路：定义两个存储器，一个用来存放即将 第三次选代后 留下的样本 算法终止后 生成的样本集，称为Store;另一存储器则存放 原样本集，称为Grabbag。 0 6.3.4压缩近邻法 6.3.4压缩近邻法 口算法步骤 1. [初始化]Store是空集，原样本集存入Grabbag: 从Grabbag中任意选择一样本放入Store中作 为新样本集的第一个样本。 2. [样本集生成]在Grabbag中取出第i个样本用 Store中的当前样本集按最近邻法分类。若分类 错误，则将该样本从Grabbag转入Store中； 若分类正确，则将该样本放回Grabbag中。 3. [结来过程]若Grabbag中所有样本在执行第二 步时没有发生转入Store的现象，或Grabbag ■在算法终止后，Store中的样本集作为压缩样本 已成空集，则算法终止，否则转入第二步。 集，可用来对待识别样本按最近邻法分类。25 6.3.2 剪辑近邻法  错误率分析（渐进错误率）  用最近邻法剪辑后得到的样本集进行分类，其错 误率总小于没有剪辑的最近邻法的错误率，即  用k-近邻法进行剪辑得到的样本集进行分类，则 在N→∞及k→∞，且 k/N→0 的条件下有  多类情况，多类剪辑近邻错误率小于两类情况；  重复剪辑：样本足够多时，重复剪辑效果更好。 1 ( ) ( ); E P e Pe  * () ; E Pe P k  26 6.3.2 剪辑近邻法  重复剪辑算法 (MULTIEDIT) 1. 将样本集随机划分为S (≥3) 个子集，K1,…,KS； 2. 用最近邻法，以 Kj (j = (i+1) mod S)为参考集， 对 Ki 中的样本进行分类，其中i＝1,…,S； 3. 去掉步骤2中被错分类的样本; 4. 用所有留下的全部样本的构成新的样本集 KNT。 5. 如经 k 次迭代后，再没有样本被剪辑掉，则停 止；否则转步骤1。  每次迭代时都要对现有样本集进行重新随机划 分，以保证剪辑的独立性。 27 原始样本集 留下的样本 第一次迭代后 留下的样本 第三次迭代后 留下的样本 算法终止后 28 6.3.4 压缩近邻法  基本思想：利用现有样本集，逐渐生成一个新的 样本集，使该样本集在保留最少量样本的条件 下，仍能对原有样本的全部用最近邻法正确分 类；那么该样本集也能对待识别样本进行分类， 并保持正常识别率。  算法思路：定义两个存储器，一个用来存放即将 生成的样本集，称为 Store；另一存储器则存放 原样本集，称为 Grabbag。 29 6.3.4 压缩近邻法  算法步骤 1. [初始化] Store是空集，原样本集存入Grabbag； 从 Grabbag 中任意选择一样本放入 Store 中作 为新样本集的第一个样本。 2. [样本集生成] 在 Grabbag 中取出第 i 个样本用 Store 中的当前样本集按最近邻法分类。若分类 错误，则将该样本从 Grabbag 转入 Store 中； 若分类正确，则将该样本放回 Grabbag 中。 3. [结束过程] 若 Grabbag 中所有样本在执行第二 步时没有发生转入 Store 的现象，或 Grabbag 已成空集，则算法终止，否则转入第二步。 30 6.3.4 压缩近邻法  在算法终止后，Store 中的样本集作为压缩样本 集，可用来对待识别样本按最近邻法分类