07 近邻法.ppt

7近邻法 利用每一类的 代表点 设计分段线性分类器问题是最简单而直观的设计方法 这类方法的缺点是所选择的 代表点 不一定能很好地代表各个类 其后果是使所设计分类器的错误率增加 将各类中全部样本都作为 代表点 进行决策的方法称为近邻法 近邻法是模式识别非参数法中最重要的方法之一 7近邻法 7 1最近邻法7 2k 近邻法7 3最佳距离度量近邻法 7 1最近邻法 一 最近邻决策规则最近邻分类是假定有c个类别 1 2 c的模式识别问题 每类有标明类别的样本Ni个 i 1 2 c规定 i类的判别函数为 其中的角标i表示 i类 k表示 i类Ni个样本中的第k个 按照上式 决策规则可以写为 7近邻法 7 1最近邻法 这一决策方法称为最近邻法 若 则决策x j 其直观解释是相当简单的 就是说对未知样本x 只要比较x与个已知类别的样本之间的欧氏距离 并决策x与离它最近的样本同类 一 最近邻决策规则 二 最近邻法的错误率分析 近邻法的错误率很难计算 因为训练样本集的数量总是有限的 有时多一个少一个训练样本对测试样本分类的结果影响很大 如图中所示 7 1最近邻法 从以上讨论可以看出 当N 时 最近邻法的渐近平均错误率的下界是贝叶斯错误率 这发生在样本对某类别后验概率处处为1的情况或各类后验概率相等的情况 在其它条件下 最近邻法的错误率要高于贝叶斯错误率 7 1最近邻法 二 最近邻法的错误率分析 可以证明以下关系式成立 上式实际上给出了最近邻法渐近平均错误率P的范围 指出它在Bayes错误率P 和之间 其中P 为贝叶斯错误率 c为类数 7 1最近邻法 二 最近邻法的错误率分析 图7 14示出近邻法的上下界 一般地 最近邻法的错误率落在图中的阴影区域中 7 1最近邻法 二 最近邻法的错误率分析 c类别最近邻分类器可能渐近误差率 由于一般情况下P 很小 因此错误率又可粗略表示成 因此可以说最近邻法的渐近平均错误率在贝叶斯错误率的两倍之内 从这点说最近邻法是优良的 因此它是模式识别重要方法之一 7 1最近邻法 二 最近邻法的错误率分析 7 2k 近邻法 k 近邻法是取未知样本x的k个近邻 看这k个近邻中多数属于哪一类 就把x归于那一类 就是说在N个已知样本中 找出x的k个近邻 人为确定k 根据经验设定 k大 错误率小 计算量大 7近邻法 7 2k 近邻法 如图7 15所示k 近邻算法示意图 7近邻法 7 2k 近邻法 设这N个样本中 来自 1类的样本有N1个 来自 2类的样本有N2个 来自 c类的样本有Nc个 若k1 k2 kc分别是k个近邻中属于 1 2 c类的样本数 定义判别函数为gi x ki i 1 2 c 4 71 决策规则为 则决策x j 这就是k 近邻法的基本规则 若分错 则风险很大 错误率大 损失大 k近邻一般采用k为奇数 跟投票表决一样 避免因两种票数相等而难以决策 考虑到风险 损失 问题 对ki加以约束 若 则x i 否则拒判 7 2k 近邻法 结论 上述结论是在样本数N趋于无穷的假设下取得的 在实际问题中 样本数是有限的 因此 通常在k 近邻法中选择k值时 一方面采用大一些的k值以减小错误率 另一方面要求k个近邻都很靠近x 以保证P i x 和P i x 近似相等 选择k值时折衷考虑 使它总是样本数的一小部分 7 2k 近邻法 最近邻法和k 近邻法都有方法简单的优点 而且分类效果比较好 其错误率为 由于P 一般很小 因此上式可近似表示为P P 2P 即近邻法错误率在Bayes错误率P 和两倍Bayes错误率2P 之间 正因为此优良性质 使其成为模式识别的重要方法之一 7 2k 近邻法 但近邻法存在以下问题 需要将所有样本存入计算机中 每次决策都要计算待识别样本x与全部训练样本 i 1 2 c k 1 2 Ni之间的距离并进行比较 存储量和计算量都很大 虽然在一般情况下 对未知样本x都可以进行决策 但当错误代价很大时 会产生较大的风险 7 2k 近邻法 但近邻法存在以下问题 续 要求样本数N 这在任何实际场合是无法实现的 为了解决上述问题出现了一些改进算法 如剪辑近邻法解决存储量大的问题 快速搜索近邻法解决计算量大的问题等 7 2k 近邻法 近邻法举例 Figureshowsthedecisionboundaryofthe K 8 nearestneighborclassifier 7 2k 近邻法 快速搜索近邻法 这种方法只解决减少计算量 但没有达到减少存储量的要求 其基本思想是将样本集按邻近关系分解成组 给出每组的质心所在 以及组内样本至该质心的最大距离 这些组又可形成层次结构 即组又分子组 因而待识别样本可将搜索近邻的范围从某一大组 逐渐深入到其中的子组 直至树的叶结点所代表的组 确定其相邻关系 7 2k 近邻法 一 样本集分级分解 根据以上基本思想 先对样本集进行分级分解 分级分解过程可列举如下 首先将整个样本分成l个子集 每个子集又分为它的l个子集 如此进行若干次就能建立起一个样本集的树形结构 分成子集的原则是该子集内的样本尽可能聚成堆 这可用聚类方法实现 7 2k 近邻法 一 样本集分级分解 结点参数 树形结构 每个结点表示一样本子集 描述该子集的参数是 Xp 该结点对应的样本子集代号 Np p中包含的样本个数 Mp 是样本子集p的样本均值 7 2k 近邻法 Mp到所属成员的最大距离 二 快速搜索算法 要实现快速搜索近邻 需要有方法快速判断某个样本子集是否是该待识样本的可能近邻样本集 从而可将无关的样本子集尽快排除 另一方面在某样本子集内寻找哪个样本是近邻时 需快速排除不可能为近邻的样本 这两个快速判别算法可用以下两个规则表示 7 2k 近邻法 二 快速搜索算法 规则1 如果存在B rp D x Mp 则xi Xp不可能是x的近邻 其中B是待识别样本在搜索近邻过程中的当前近邻距离 B在搜索过程中不断改变与缩小 算法开始可将B设为无穷大 D x Mp 表示待识样本x到结点Xp的均值点距离 7 2k 近邻法 二 快速搜索算法 这个规则的证明是显而易见的 如图表示一待识样本及其当前近邻与一样本子集的关系 B rp D x Mp 7 2k 近邻法 二 快速搜索算法 如果以x为圆心 B为半径作圆 则圆与样本子集Xp的分布圆不会相交 因而Xp中任一样本不可能比x的当前近邻更靠近x B rp D x Mp 7 2k 近邻法 二 快速搜索算法 规则2 如果B D xi Mp D x Mp 其中xi X 则xi不可能是x的近邻 规则2的证明同规则1 由此可见 只要将每个样本子集中的每个样本xi到其均值Mp的距离D xi Mp 存入存储器中 就可利用上式将许多不可能成为测试样本近邻的训练样本排除 7 2k 近邻法 二 快速搜索算法 如何运用这两个规则设计一个近邻的快速搜索算法 搜索算法的大体过程是这样的 当搜索树形样本集结构由高层次向低层次深入时 对同一层次的所有结点 可以利用规则1排除掉一些不可能包含待识别样本的近邻的结点 样本子集 7 2k 近邻法 二 快速搜索算法 但是这往往不能做到只留下唯一的待搜索结点 因此必须选择其中某一结点先深入搜索 以类似于深度优先的方法确定搜索路径直至叶结点 然而在该叶结点中找到的近邻并不能保证确实是全样本集中的最近邻者 所找到的该近邻样本需要在那些有可能包含最近邻的样本子集中核对与修正 直至找到真正的最近邻样本为止 7 2k 近邻法 二 快速搜索算法 树搜索算法具体的搜索步骤 步骤1 初始化 置B L 1 当前层次 p 0 确定当前结点 步骤2 置后选待搜索结点 把当前结点的所有直接后继结点放入层的一目录表中 并对这些结点计算D x Mp 步骤3 排除无关结点 对层目录表中的每个结点P 用规则1将与近邻无缘的结点从目录表中清除 7 2k 近邻法 二 快速搜索算法 步骤4 路径选择 如该层次目录表中有不止一个结点 选其中D x Mp 最小者 将该结点从目录表中删除 如该结点是叶结点转步骤5 如不是叶结点 则L L 1 转步骤2 如该层次目录表中无结点待搜索 则L L 1 如L 0则停止 否则转步骤3 7 2k 近邻法 二 快速搜索算法 步骤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 在算法结束时 输出x的最近邻xNN及两者间距离D x xNN B 7 2k 近邻法 k 近邻法的快速计算 k 近邻法快速计算是搜索待测样本的k个最近邻 以做到最后在这k个最近邻中计算占多数的训练样本类别 因此只要发现有一个训练样本比当前第k个近邻的距离要小 就把当前第k个近邻剔除出当前k近邻组 7 2k 近邻法 k 近邻法的快速计算 k 近邻法的快速计算法与上述过程大体相同 只是B值修改为当前第k个近邻的距离值 然后在步骤5中 对所计算的距离要与该k个当前的近邻比较 若比其中某个距离小 则删除最大者 除了以上两点修正外 其它算法与最近邻快速算法一样 7 2k 近邻法 剪辑近邻法 以上讨论的快速算法只是研究如何减少计算量的问题 而不考虑存储量的压缩 实际上由于对样本进行分层次分组 并附有一些参数 实际的存储量还有可能增加 本节讨论的算法着眼于如何减少模板样本数目 从而可同时减少分类时的计算量及模板样本的存储量 同时还能进一步改进分类器的性能 如降低错误率等要求 本节讨论的剪辑近邻法除了在样本数量上有一定程度的减少外 更主要的优点是错误率的降低 7 2k 近邻法 剪辑近邻法 剪辑近邻法的基本思想是从这样一个现象出发的 即当不同类别的样本在分布上有交迭部分的 分类的错误率主要来自处于交迭区中的样本 当得到一个作为识别用的参考样本集时 由于不同类别交迭区域中不同类别的样本彼此穿插 导致用近邻法分类出错 7 2k 近邻法 剪辑近邻法 因此如果能将不同类别交界处的样本以适当方式筛选 可以实现既减少样本数又提高正确识别率的双重目的 为此可以利用现有样本集对其自身进行剪辑 下面以两类别问题为例说明这种方法的原理 7 2k 近邻法 剪辑近邻法 假设现有一个样本集N 样本数量为N 将此样本集分成两个互相独立的样本子集 一个被当作考试集XNT 另一个作为参考集XNR 数量分别为NT与NR NT NR N 将XNT中的样本表示成xi i 1 NT 而在XNR中的样本表示为yi i 1 NR 7 2k 近邻法 剪辑近邻法 将一个样本集分成两个相互独立的样本子集是指 分完以后的两个子集具有相同的分布例如将一个样本集分成两个相互独立的对等子集 则在每个特征空间的子区域 两个子集都有相同的比例 或说各类数量近似相等 要注意的是每个子区域 从大空间到小空间 实际做时要用从总的集合中随机抽取的方式进行 7 2k 近邻法 剪辑近邻法 剪辑的过程是 首先对XNT中每一个xi在XNR中找到其最近邻的样本yi xi 用yi xi 表示yi是xi的最近邻参考样本 如果yi与xi不属于同一类别 则将xi从XNT中删除 最后从XNT中得到一个经过剪辑的样本集 称为剪辑样本集 可用来取代原样本集 作为参考样本集对待识别样本进行分类 7 2k 近邻法 剪辑近邻法 XNT经过剪辑后 要作为新的训练样本集 则XNR是对其性能进行测试的样本 如发现XNT中的某个训练样本对分类不利 就要把它剪辑掉 实际上剪辑样本的过程也可以用k 近邻法进行 即对XNT中的每个样本xi 找到在XNR中的k个近邻 用k 近邻法判断xi是否被错分类 从而决定其取舍 其它过程与前述方法完全一样 7 2k 近邻法 剪辑近邻法 剪辑近邻法也可用到多类别情况 剪辑过程也可不止一次 重复多次的称为重复剪辑近邻法 图1到图4是一个两类正态分布样本的重复剪辑结果 图1是原始样本集 图2是经一次迭代的结果 图3是三次迭代留下的样本 图4是算法终止时留下的样本 7 2k 近邻法 原始样本集 第一次迭代后的结果 三次迭代后结果 算法最总留下的样本 剪辑近邻法 所使用的重复剪辑算法步骤如下 1 将样本集XNT随机划分为S个子集 即XN X1 X2 Xs s 32 用最近邻法 以Xj j i 1 mods为参考集 对Xi中的样本进行分类 其中i 1 s 3 去掉步骤2中被错分类的样本 4 用所有留下的全部样本的构成新的样本集XNT5 如该次剪辑过程中没有样本被删除 则停止 否则转步骤1 7 2k 近邻法 剪辑近邻法 由此可见每次迭代过程都要重新对现有样本集进行重新随机划分 以保证了剪辑的独立性 7 2k 近邻法 剪辑近邻法 用近邻法容易出错的区域是在两类的交界处 这时某个训练样本存在与否就会影响到某些测试分类的结果 因此剪辑的效果往往把这些处于交界的训练样本给剪辑掉了 以上讨论了剪辑近邻法的原理与算法 另一个问题是对剪辑近邻法错误率的分析 这里只给出简单的结论 7 2k 近邻法 剪辑近邻法 1 利用最近邻法剪辑后得到的样本集进行分类 其错误率总小于原样本集 如用P1E e 表示其错误率 则有P1E e P e 其中P e 表示用原样本的渐近平均错误率 在P e 很小 如P e 0 1情况下可有P1E e 1 2P e 由于近邻法错误率上界为2P 两倍贝叶斯错误率 因而P1E e P 7 2k 近邻法 剪辑近邻法 2 利用k 近邻法进行剪辑得到的样本集进行分类 则在N 及k 且K N 0的条件下有PkE e P 该式表明k很大时 剪辑样本法的错误率可收敛于最优情况P 当然实际上k值不能取得太大 3 多类情况 剪辑效果更好 7 2k 近邻法 压缩近邻法 从上述讨论中可以看出 剪辑近邻法所得到的剪辑样本集在样本数量的压缩方面并不十分明显 它的作用在于将原样本集中处于边界处的样本删除掉 但靠近两类中心的大部分样本仍被保留下来 然而按近邻规则来看 这些样本中的大多数对分类决策没什么用处 如能在剪辑的基础上再去掉一部分这样的样本 将有助于进一步缩短计算时间与压缩存储量 这种方法称为压缩近邻法 7 2k 近邻法 压缩近邻法 压缩近邻法压缩样本的思想很简单 它利用现有样本集 逐渐生成一个新的样本集 使该样本集在保留最少量样本的条件下 仍能对原有样本的全部用最近邻法正确分类 那末该样本集也就能对待识别样本进行分类 并保持正常识别率 该算法的作法也十分简单 它定义两个存储器 一个用来存放即将生成的样本集 称为Store 另一存储器则存放原样本集 称为Grabbag 7 2k 近邻法 压缩近邻法 其算法是 1 初始化 Store是空集 原样本集存入Grabbag 从Grabbag中任意选择一样本放入Store中作为新样本集的第一个样本 2 样本集生成 在Grabbag中取出第i个样本用Store中的当前样本集按最近邻法分类 若分类错误 则将该样本从Grabbag转入Store中 若分类正确 则将该样本放回Grabbag中 对Grabbag中所有样本重复上述过程 7 2k 近邻法 压缩近邻法 其算法是 3 结束过