第6章 近邻法最新版本

.,模式识别,徐蔚然北京邮电大学信息工程学院,.,近邻法简介,产生由Cover和Hart于1968年提出理论上深入分析是模式识别中最重要的方法之一,.,近邻法原理及其决策规则,回顾最小距离分类器它将各类训练样本划分成若干子类并在每个子类中确定代表点用子类的质心或邻近质心的某一样本为代表点测试样本的类别则以其与这些代表点距离最近作决策缺点:所选择的代表点并不一定能很好地代表各类，其后果将使错误率增加,.,近邻法简介,最小距离分类器每个类别只有一个”代表点”,.,近邻法简介,基于距离的分段线性函数每个类别用多个”代表点”表示,.,近邻法原理及其决策规则,分析:增加代表点的数量有没有可能获得性能好的分类器呢?一种极端的情况是以全部训练样本作为“代表点”，也称为”模板”分类方法:(也是一种模板匹配算法)测试样本与每个”代表点”做比较与哪个模板最相似(即为近邻),就按最近似的”代表点”的类别作为分类的类别这种方法就是近邻法的基本思想,.,近邻法简介,例A类有10个训练样本，因此有10个模板，B类有8个训练样本，就有8个模板。任何一个待测试样本在分类时与这18个模板都算一算相似度，如最相似的那个近邻是B类中的一个，就确定待测试样本为B类，否则为A类。因此原理上说近邻法是最简单的。,.,近邻法简介,近邻法优点在模板数量很大时，其错误率指标还是相当不错的近邻法缺点存储量大要存储的模板很多计算量大每个测试样本要对每个模板计算一次相似度,.,近邻法简介,改进的办法剪辑近邻法压缩近邻法,.,本章学习要点,(1)弄清楚近邻法的定义(包括k近邻法)，与基本做法(2)弄清“近邻法性能好”是在什么意义上讲的。知道渐进平均错误率的定义(3)快速搜索方法是使用怎样的原理？(4)剪辑近邻法的原理是什么?而压缩近邻法与剪辑近邻法有什么不同之处？,.,最近邻法决策规划,最近邻法将与测试样本最近邻样本的类别作为决策的方法称为最近邻法具体方法对一个C类别问题，每类有Ni个样本，i1，C，则第i类的判别函数为,其中xik表示是i类的第k个样本。,k1，Ni,.,最近邻法决策规划,具体方法判别函数的决策规则为：,如果,则决策xj,由此可见最近邻法在原理上最直观，方法上也十分简单,.,近邻法错误率分析,有时多一个少一个训练样本对测试样本分类的结果影响很大,以下都是在渐近概念下来分析错误率,怎样计算近邻法的错误率？,估计错误率比较困难,即:假设训练样本数量增至极大，来对其性能进行评价。,仅分析极限情况下的错误率,.,近邻法错误率分析,特征空间中x点的错分概率x:是待分类的样本x:是x的最近邻样本已经有N个已知类别的训练样本，而x是其中之一特征空间中x点的错分概率:,.,近邻法错误率分析,最近邻的收敛性x和x的关系P(x|x)怎样计算？非常困难既然x是x的近邻,则p(x|x)在x=x附近应该有尖峰已知类别的训练样本数N越大，则p(x|x)的峰越尖锐,.,近邻法错误率分析,最近邻的收敛性那么当N时p(x|x)会变成什么样？变成delta函数证明N时，p(x|x)(x-x)假设在给定的x点，p(x)连续且非零则样本落在以x为中心的一个超球s里的概率:,.,近邻法错误率分析,最近邻的收敛性那么当N时p(x|x)会变成什么样？变成delta函数证明N时，p(x|x)(x-x)一个样本落在s外的概率:(1-Ps)N个样本落在s外的概率:(1-Ps)N,.,近邻法错误率分析,最近邻的收敛性那么当N时p(x|x)会变成什么样？变成delta函数证明N时，p(x|x)(x-x),.,近邻法错误率分析,最近邻规则的错误概率N对随机变量(x1,1),(x2,2)(xN,N)统计独立，则错误是由于P(,|x,x)=,P(|x),P(|x),类别不同产生的,.,近邻法错误率分析,.,近邻法错误率分析,渐近平均错误率,.,近邻法错误率分析,先在一维特征空间的两类别情况来讨论下图中x表示一特测试样本x是所用训练样本集中x的最邻近者则错误是由x与x分属不同的类别所引起的如果所用训练样本集的样本数量N极大，即N则:x将趋向于x，即说处于以x为中心的极小邻域内，此时分析错误率问题就简化为:在x样本条件下x与一个x(x的极限条件)分属不同类别的问题,.,近邻法错误率分析,在一维特征空间的两类别情况来讨论。,.,近邻法错误率分析,如果样本x的两类别后验概率分别为P(1|x)与P(2|x)，那么对x值，在N条件下，发生错误决策的概率为：而在这条件下的平均错误率,.,近邻法错误率分析,为了与基于最小错误率的贝叶斯决策方法对比，下面写出贝叶斯错误率的计算式。,其中,而,.,近邻法错误率分析,考虑两类情况贝叶斯错误率公式中有而近邻法错误率为：两式相减，并写成P，则有,.,近邻法错误率分析,分析从上式可见在一般情况下P是大于零的值，只要P(1|x)P(2|x)0。有以下两种例外情况P0，这两种情况是P(1|x)1的情况P(1|x)P(2|x)1/2。,请想一下，什么情况下P(1|x)1或P(2|x)=1?P(1|x)=P(2|x)会出现什么什么情况？,.,近邻法错误率分析,可以证明以下关系式成立即最近邻法的渐近平均错误率的上下界分别为贝叶斯错误率由于一般情况下P*很小，因此又可粗略表示成,.,近邻法错误率分析,计算P的上下限计算P的下限最小错误率是贝叶斯错误率P*,.,近邻法错误率分析,计算P的上限,贝叶斯错误率P*(e|x),m使得错误概率最小,(1)求其下界,并和P*(e|x)联系起来,(2)求P里面的积分和P*联系起来,结论,近邻法错误率分析,.,k-近邻法决策规则,k-近邻法决策规则最近邻法可以扩展成找测试样本的k个最近样本作决策依据的方法基本规则在所有N个样本中找到与测试样本的k个最近邻者，其中各类别所占个数表示成ki,i1，c则决策规划是：,如果,则决策xj,k近邻一般采用k为奇数，跟投票表决一样，避免因两种票数相等而难以决策。,.,k-近邻法错误率分析,以上我们从定性分析的角度讨论了最近邻法错误率问题，下面以同样的方法更简略地讨论k-近邻法的渐近平均错误率。对于两类别问题，错误率可以改写成推广到k-邻域的情况，则错误出现在k个邻域样本中，正确的类别所占样本未过半数，得到,.,6.3改进的近邻法,近邻法缺点存储量大要存储的模板很多计算量大每个测试样本要对每个模板计算一次相似度,.,改进的近邻法,改进方法的两种原理一种是对样本集进行组织与整理，分群分层，尽可能将计算压缩到在接近测试样本邻域的小范围内，避免盲目地与训练样本集中每个样本进行距离计算。另一种原理则是在原有样本集中挑选出对分类计算有效的样本，使样本总数合理地减少，以同时达到既减少计算量，又减少存储量的双重效果。,.,改进的近邻法,改进的近邻法快速搜索近邻法剪辑近邻法压缩近邻法,.,改进的近邻法:快速搜索近邻法,快速搜索近邻法这种方法着眼于只解决减少计算量，但没有达到减少存储量的要求。基本思想是将样本集按邻近关系分解成组，给出每组的质心所在，以及组内样本至该质心的最大距离这些组又可形成层次结构，即组又分子组因而待识别样本可将搜索近邻的范围从某一大组，逐渐深入到其中的子组，直至树的叶结点所代表的组，确定其相邻关系,.,改进的近邻法:快速搜索近邻法,样本集分级分解根据以上基本思想，先对样本集进行分级分解分级分解过程可列举如下首先将整个样本分成l个子集,每个子集又分为它的l个子集如此进行若干次就能建立起一个样本集的树形结构分成子集的原则是该子集内的样本尽可能聚成堆，这可用聚类方法实现。,.,改进的近邻法:快速搜索近邻法,结点参数：树形结构，每个结点表示一样本子集，描述该子集的参数是：,一个树形结构样本集，其中分支数l3,.,改进的近邻法:快速搜索近邻法,实现快速搜索近邻的基本思路需要有方法快速判断某个样本子集是否是该待识样本的可能近邻样本集，从而可将无关的样本子集尽快排除。另一方面在某样本子集内寻找哪个样本是近邻时，需快速排除不可能为近邻的样本这两个快速判别算法可用两个规则表示,.,改进的近邻法:快速搜索近邻法,实现快速搜索算法的两个规则规则1：如果存在,则不可能是x的近邻。其中B是待识别样本在搜索近邻过程中的当前近邻距离，B在搜索过程中不断改变与缩小。算法开始可将B设为无穷大。表示待识样本x到结点的均值点距离。,.,改进的近邻法:快速搜索近邻法,.,改进的近邻法:快速搜索近邻法,实现快速搜索算法的两个规则规则2：如果,其中xi，则xi不可能是x的近邻。,.,改进的近邻法:快速搜索近邻法,搜索算法的大体过程当搜索树形样本集结构由高层次向低层次深入时，对同一层次的所有结点，可以利用规则1排除掉一些不可能包含待识别样本的近邻的结点(样本子集)。但是这往往不能做到只留下唯一的待搜索结点，因此必须选择其中某一结点先深入搜索，以类似于深度优先的方法确定搜索路径直至叶结点。然而在该叶结点中找到的近邻并不能保证确实是全样本集中的最近邻者，所找到的该近邻样本需要在那些有可能包含最近邻的样本子集中核对与修正，直至找到真正的最近邻样本为止。,.,改进的近邻法:快速搜索近邻法,树搜索算法步骤:步骤1：初始化置B，L1(当前层次)，p0(确定当前结点)。步骤2：置后选待搜索结点把当前结点的所有直接后继结点放入层的一目录表中，并对这些结点计算D(x，Mp)。步骤3：排除无关结点对层目录表中的每个结点P，用规则1将与近邻无缘的结点从目录表中清除。,.,改进的近邻法:快速搜索近邻法,树搜索算法步骤:步骤4：路径选择如该层次目录表中有不止一个结点，选其中D(x，Mp)最小者，将该结点从目录表中删除，如该结点是叶结点转步骤5，如不是叶结点，则LL+1，转步骤2；如该层次目录表中无结点待搜索，则LL-1，如L0则停止，否则转步骤3。步骤5：近邻样本搜索对现在执行结点p中的每个样本xi，利用规则2作如下检验：如果D(x，Mp)D(xi,Mp)+B则xi不是x的最近邻，否则计算D(x，xi)，若D(x，xi)B，置NNi和BD(x,xi)。对当前执行结点中所有xi被检验后，转步骤3。,在算法结束时，输出x的最近邻xNN及两者间距离。,.,改进的近邻法:剪辑近邻法,剪辑近邻法的基本思想一个现象:即当不同类别的样本在分布上有交迭部分的，分类的错误率主要来自处于交迭区中的样本当我们得到一个作为识别用的参考样本集时，由于不同类别交迭区域中不同类别的样本彼此穿插，导致用近邻法分类出错。因此如果能将不同类别交界处的样本以适当方式筛选，可以实现既减少样本数又提高正确识别率的双重目的。为此可以利用现有样本集对其自身进行剪辑。,示例,.,改进的近邻法:剪辑近邻法,算法步骤:1.将样本集随机划分为S个子集，即2.用最近邻法，以为参考集，对样本集中的样本进行分类，其中i1，s。3.去掉步骤2中被错分类的样本。4.用所有留下的全部样本构成新的样本集5.如该次剪辑过程中没有样本被删除，则停止，否则转步骤1。,.,改进的近邻法:压缩近邻法,压缩近邻法压缩样本的思想它利用现有样本集，逐渐生成一个新的样本集。使该样本集在保留最少量样本的条件下,仍能对原有样本的全部用最近邻法正确分类，那末该样本集也就能对待识别样本进行分类,并保持正常识别率。,.,改进的近邻法:剪辑近邻法,算法的实现它定义两个存储器，一个用来存放即将生成的样本集，称为Store；另一存储器则存放原样本集，称为Grabbag。,.,改进的近邻法:剪辑近邻法,算法的实现其算法是：1.初始化Store