knn算法

第五章近邻法王文伟WangWenwei,Dr.-Ing.Tel:[phone]Email:@yahoo.cnWeb:电子信息学院第五章近邻法2TableofContents5.0引言5.1最近邻法5.2k-近邻法5.3改进的近邻法5.4讨论电子信息学院第五章近邻法35.0引言最小距离分类器:它将各类训练样本划分成若干子类，并在每个子类中确定代表点。未知样本的类别则以其与这些代表点距离最近作决策。该方法的缺点是所选择的代表点并不一定能很好地代表各类，其后果将使错误率增加。m1m2xg(x)=0x第五章近邻法4近邻法最近邻分类器(nearestneighborhoodclassifier,nnc):最小距离分类器的一种极端的情况，以全部训练样本作为代表点，计算测试样本与所有样本的距离，并以最近邻者的类别作为决策。最初的近邻法是由Cover和Hart于1968年提出的，随后得到理论上深入的分析与研究，是非参数法中最重要的方法之一。引言第五章近邻法55.1最近邻法最近邻法：nearestneighborhoodclassifier(nnc)，将与测试样本最近邻样本的类别作为决策的结果。对一个C类别问题，每类有Ni个样本，i＝1，…，C，则第i类ωi的判别函数为：()min,1,...,kiiikgkNxxx‖·‖表示某种距离（相似性）度量，常用欧氏距离作为相似性度量。第五章近邻法6决策规则if()min()thenjijiggxxx最近邻法在原理上最直观，方法上也十分简单。明显的缺点就是计算量大，存储量大。NNCj=argmin()iigx第五章近邻法7最近邻法错误率分析最近邻法的错误率高于贝叶斯错误率，可以证明以下关系式成立：***(2)1CPPPPC由于一般情况下P*很小，因此又可粗略表示成：可粗略说最近邻法的渐近平均错误率在贝叶斯错误率的两倍之内。**2PPPNNC第五章近邻法85.2k-近邻法k-近邻法:最近邻法的扩展，其基本规则是，在所有N个样本中找到与测试样本的k个最近邻者，其中各类别所占个数表示成ki,i＝1，…，c。定义判别函数为：gi(x)=ki,i=1,2,…,c。k-近邻一般采用k为奇数，跟投票表决一样，避免因两种票数相等而难以决策。决策规则为：argmax(),1,...,iijgicx第五章近邻法9k-近邻法错误率分析在N→∞的条件下，k-近邻法的错误率要低于最近邻法。最近邻法和k-近邻法的错误率上下界都是在一倍到两倍贝叶斯决策方法的错误率范围内。kNN第五章近邻法10最近邻与k-近邻法分类演示kNN3-近邻最近邻第五章近邻法115.3改进的近邻法近邻法的一个严重问题是需要存储全部训练样本，以及繁重的距离计算量。两类改进的方法：一种是对样本集进行组织与整理，分群分层，尽可能将计算压缩到在接近测试样本邻域的小范围内，避免盲目地与训练样本集中每个样本进行距离计算。另一种则是在原有样本集中挑选出对分类计算有效的样本，使样本总数合理地减少，以同时达到既减少计算量，又减少存储量的双重效果。第五章近邻法12快速搜索近邻法快速搜索近邻法，包括两个阶段：•样本集的分级分解•搜索改进方法其基本思想是将样本集按邻近关系分解成组，给出每组的质心所在，以及组内样本至该质心的最大距离。这些组又可形成层次结构，即组又分子组，因而待识别样本可将搜索近邻的范围从某一大组，逐渐深入到其中的子组，直至树的叶结点所代表的组，确定其相邻关系。这种方法着眼于只解决减少计算量，但没有达到减少存储量的要求。第五章近邻法13样本集的层次结构用树结构表示样本分级:p:树中的一个结点，对应一个样本子集KpNp:Kp中的样本数Mp:Kp中的样本均值rp:从Kp中任一样本到Mp的最大距离改进方法第五章近邻法14减少计算的规则规则1：如果满足：则Kp中的样本都不可能是x的最近邻，B是算法执行中当前到x的最近距离(,)ppDBrxM(,)(,)pipDBDxMxM规则2：如果满足：则xi不是x的最近邻改进方法第五章近邻法15树搜索算法1.置B=∞，L=0，p=02.将当前结点的所有直接后继结点放入一个目录表中，并对这些结点计算D(x,Mp)3.根据规则1从目录表中去掉step2中的某些结点4.如果目录表已无结点则置L=L-1，如果L=0则停止，否则转Step3。如果目录表有一个以上的结点，则转step55.在目录表中选出最近结点p’为当前执行结点。如果当前的水平L是最终水平，则转Step6，否则置L=L+1，转Step26.对当前执行结点p’中的每个xi，根据规则2决定是否计算D(x,xi)。若D(x,xi)B，则置NN=i和B=D(x,xi)，处理完当前执行结点中的每个xi后转Step3当算法结束时，输出x的最近邻xNN和与xNN的距离B改进方法第五章近邻法16剪辑近邻法剪辑近邻法：其基本思想是，利用现有样本集对其自身进行剪辑，将不同类别交界处的样本以适当方式筛选，可以实现既减少样本数又提高正确识别率的双重目的。改进方法第五章近邻法17剪辑近邻法剪辑的过程是：将样本集KN分成两个互相独立的子集：test集KT和reference集KR。首先对KT中每一个Xi在KR中找到其最近邻的样本Yi(Xi)。如果Yi与Xi不属于同一类别，则将Xi从KT中删除，最后得到一个剪辑的样本集KTE（剪辑样本集），以取代原样本集，对待识别样本进行分类。改进方法第五章近邻法18压缩近邻法压缩近邻法：利用现有样本集，逐渐生成一个新的样本集，使该样本集在保留最少量样本的条件下，仍能对原有样本的全部用最近邻法正确分类，那末该样本集也就能对待识别样本进行分类，并保持正常识别率。改进方法第五章近邻法19压缩近邻算法定义两个存储器，一个用来存放即将生成的样本集，称为Store；另一存储器则存放原样本集，称为Grabbag。其算法是：1.初始化。Store是空集，原样本集存入Grabbag；从Grabbag中任意选择一样本放入Store中作为新样本集的第一个样本。2.样本集生成。在Grabbag中取出第i个样本用Store中的当前样本集按最近邻法分类。若分类错误，则将该样本从Grabbag转入Store中，若分类正确，则将该样本放回Grabbag中。3.结束过程。若Grabbag中所有样本在执行第二步时没有发生转入Store的现象，或Grabbag已成空集，则算法终止，否则转入第二步。改进方法第五章近邻法205.4讨论近邻法是典型的非参数法在原理上最直观，方法上也十分简单，明显的缺点就是计算量大，存储量大第五章近邻法21习题1.设在一个二维空间，A类有三个训练样本，图中用红点表示，B类四个样本，图中用蓝点表示。试问：（1）按近邻法分类，这两类最多有多少个分界面（2）画出实际用到的分界面B3B4B1B2A3A1A2第五章近邻法22解答按近邻法，对任意两个由不同类别的训练样本构成的样本对，如果它们有可能成为测试样本的近邻，则它们构成一组最小距离分类器，它们之间的中垂面就是分界面，因此由三个A类与四个B类训练样本可能构成的分界面最大数量为3×4＝12。实际分界面如下图所示，由9条线段构成。B3B4B1B2A3A1A2