近邻分类分类器设计一、设计任务对“data3•数据，采用剪辑法、压缩法生成参考集，近似描绘其决策面，并用所有数 据测试其分类效果二、设计原理1、最近邻法最近邻分类器（nearest neighborhood classifier最小九距离分类器的一种 极端的情况，以全部训练样本作为代表点，计算测试样本与所有样本的距离，并 以最近邻者的类别作为决策最初的近邻法是由Cover和Hart于1968年提出的，随后得到理论上深入的 分析与研究，是非参数法中最重要的方法之一最近邻法：将与测试样本最近邻样本的类别作为决策的结果对一个C类别问题，每类有N个样本,ii1,2,…C，则第i类 的判别函数为:ig(x)imin ||xkXkllk 1,2,.,Ni i(1)因此，最近邻决策规则：若g(X)j因此，k-近邻决策规则:若g(x)jmaxki imin g (x),i 1,2,・・・c. ii(2)则决策 xj由上可以看出最近邻法在原理上最直观，方法上也十分简单，但明显的缺点就是 计算量大，存储量大2、k -近邻法k-近邻法即为最近邻法的扩展，其基本规则是，在所有N个样本中找到与 测试样本的k个最近邻者，其中各类别所占个数表示成k,i 1,2,…C，定义判 i别函数为：(3)g (x) k ,i 1,2,…ci i(4)则决策k-近邻一般采用k为奇数，跟投票表决一样，避免因两种票数相等而难以决策。
决策规则为：j = arg maxg (x), i = 1,…,ci i3、改进的近邻法近邻法的一个严重问题是需要存储全部训练样本，以及繁重的距离计算量 从而提出了两类改进的方法：一种是对样本集进行组织与整理，分群分层，尽可能将计算压缩到在接近测 试样本邻域的小范围内，避免盲目地与训练样本集中每个样本进行距离计算另一种则是在原有样本集中挑选出对分类计算有效的样本，使样本总数合理 地减少，以同时达到既减少计算量，又减少存储量的双重效果3.1、剪辑近邻法剪辑近邻法：其基本思想是，利用现有样本集对其自身进行剪辑，将不同类 别交界处的样本以适当方式筛选，可以实现既减少样本数又提高正确识别率的双 重目的剪辑的过程是：将样本集Xn分成两个互相独立的子集：test集咒nt和reference集Xnr第一步：用reference集Xnr中每一个样本y对test集Xnt中的i样本x用近邻法进行分类如果y与x不属于同一类别，则将x从设计集Xnt中i i i i删除，最后得到一个剪辑的样本集X NTE (剪辑样本集)，以取代原样本集，对待识别样本进行分类；第二步：用剪辑的样本集X NTE并用最近邻法对未知的样本x 进行分类。
k逝邻剪辑：与最近邻剪辑相似，第一步用k -近邻法进行剪辑，得到剪辑的样本集X NTE;第二步：用剪辑的样本集X NTE并用最近邻法对未知的样本x进 行分类重复剪辑近邻法：将样本集重复进行剪辑，常用的是MULTIEDIT算法：(1) 、将样本集XN随机划分为s个子集，即XN = {X , X , X }, S > 3 ；123(2) 、用最近邻法，以x 为参考集，对X ,i = 1,2,…s中的样本进行分类；(i+1)mod( s) i(3) 、去掉在(2)被错分类的样本；(4) 、用所有留下的样本构成新的样本集X NTE ；(5) 、重复(1)~(5)步，直到没有样本被剪辑掉，则停止3.2、压缩近邻法压缩近邻法：利用现有样本集，逐渐生成一个新的样本集，使该样本集在保留最少量样本的条件下，仍能对原有样本的全部用最近邻法正确分类，那末该样 本集也就能对待识别样本进行分类，并保持正常识别率 压缩近邻法的步骤是：定义两个存储器，一个用来存放即将生成的样本集， 称为Store；另一存储器则存放原样本集，称为Grabbag其算法是：(1)、初始化Store是空集，原样本集存入Grabbag；从Grabbag中任意选择一 样本放入 Store 中作为新样本集的第一个样本。
2)、样本集生成在 Grabbag 中取出第 i 个样本用 Store 中的当前样本集按最 近邻法分类若分类错误，则将该样本从 Grabbag 转入 Store 中，若分类正确， 则将该样本放回 Grabbag 中 3)、结束过程若 Grabbag 中所有样本在执行第二步时没有发生转入 Store 的 现象，或Grabbag已成空集，则算法终止，否则转入第二步最后我们以Store中的样本作为最近邻法的设计集，但这时的样本数目却大 大减少了，因此可大大节省存储量三、关键程序 由于老师给的数据太长，故在此将其省去，详见随包所带附件，本设计的关 键程序如下：%%%%%%%%%%%%%%%%%%% 剪辑近邻法 %%%%%%%%%%%%%%%%%%%TH=0.3;%阈值，决定考试集和参考集中数据的个数，其中考试集的个数为N*(1-TH)，参考集 的个数为 N*THlxx1=length(x1); lxx2=length(x2);lxx=lxx1+lxx2; Y0=ones(lxx，1);Y=ones(lxx，1);X0=[x1;x2];Y0(lxx1+1:lxx)=-1;ii=1;%总共循环次数NN=1;%统计某次剪辑掉多少个数据num=0;%统计一共剪辑掉多少个数据key=0;%统计一共有多少次一个数据都没有剪辑掉cishu=0;%统计剪辑次数k=1;%当k=1时即为最近邻法，反之则为k近邻法，比如当k=3时即为3近邻法 fx=[]; fy=[];Xmax=max(X0(:，1));Ymax=max(X0(:，2)); Xmin=ceil(Xmax);Ymax=ceil(Ymax);while ii<18&&key<5rand('seed',22);%使下行的crossvalind随机分配数据函数每次远行时产生的随机数一样，如果 将其删除，则每次产生的随机数不同，从而远行结果也不同[Test, Reference] = crossvalind('HoldOut',Y TH);%将 data.3 中的数据随机分成 2 部分，一半由 于训练，另一部分用于测试NN=lxx;X_R=X0(Reference(1:lxx),:);Y_R=Y0(Reference(1:lxx),:);X_T=X0(Test(1:lxx),:);Y_T=Y0(Test(1:lxx),:); lx_R1=length(find(Y_R>0)); lx_R2=length(find(Y_R<0));lx_R=lx_R1+lx_R2; lx_T1=length(find(Y_T>0)); lx_T2=length(find(Y_T<0));lx_T=lx_T1+lx_T2;xnew=[];for i=1:lx_Rfor j=1:lx_T xnew(j,:)=X_R(i,:);endf(i,:)=sum(((xnew-X_T).人2)');endf=f';for j=1:k[ff,TN]=min(f);for i=1:lx_R f(TN(i),i)=1/eps;end INDEX(j,:)=TN;enddd=zeros(lx_R,1);for i=1:kdd=dd+Y_T(INDEX(i,:));enddd=sign(dd);dif=Y_R-dd;chang=find(dif);if isempty(chang)key=key+1;elsekey=0;cishu=cishu+1;xtp=find(Y_T>0);%考试集第一类数据xtn=find(Y_TvO);%考试集第二类数据xrp=find(Y_R>0);%参考集第一类数据xrn=find(Y_RvO);%参考集第二类数据figure; hold on;plot(X_T(xtp,1),X_T(xtp,2),'b*',X_T(xtn,1),X_T(xtn,2),'bO',X_R(xrp,1),X_R(xrp,2),'c*',X_R(xrn ,1),X_R(xrn,2),'cO',X_R(chang,1),X_R(chang,2),'rs')hlegl = legend('xl (考试集)','x2 (考试集)’,'xl (参考集)','x2 (参考集)','剪辑掉的数 据'，‘boxoff);hold on;hold on; plot(X_R(chang，1)，X_R(chang，2)，'rs');hold on; zuobiao=[0 60 0 20];for i=1:length(chang)fx=[fx X_R(chang(i)，1)];fy=[fy X_R(chang(i)，2)];endendX_R(chang，:)=[];Y_R(chang，:)=[]; lxx=lx_T+length(Y_R);NN=NN-lxx; num=num+NN;if NN>0title({ '\color{magenta}data3.m中用近邻法中的 \color{blue}剪辑近邻法 \color{magenta} 进行处理';[ ' 第 ' num2str(cishu) '次剪辑'];[ ' 本次剪辑掉 ' num2str(NN) ' 个数据 累计剪 辑掉 ' num2str(num) ' 个数据']});enddrawnow hold off;Y=ones(lxx，1);X0=[X_T;X_R];Y0=[Y_T;Y_R];ii=ii+1;clear xnew f ff TN chang INDEXendxtp=find(Y_T>0);%考试集第一类数据xtn=find(Y_TvO);%考试集第二类数据 xrp=find(Y_R>0);%参考集第一类数据 xrn=find(Y_RvO);%参考集第二类数据 figuresubplot(2，1，1);hold on;plot(xl(:,l),xl(:,2),'b*',x2(:,l),x2(:,2),'gO')% 画出原数据axis equalhold on; plot(fx,fy,'rs');hold ontitle({ '原数据 其中红色框住的为即将剪辑掉的数据';[ '一共需剪辑掉 ' num2str(num) ' 个数据']},'Color','m');hold offdrawnow subplot(2,1,2);hold on; plot(X_T(xtp,1),X_T(xtp,2),'b*',X_T(xtn,1),X_T(xtn,2),'gO') axis equalhold on; plot(X_R(xrp,1),X_R(xrp,2),'b*',X_R(xrn,1),X_R(xrn,2),'gO') hold ontitle('\color{blue}采用 \color{magenta}剪辑近邻法 \color{blue}最终得到的数据'); hold off;drawnowclear f f2 X Y lx xnew%%%%%%%%%%%%%%%% 用近邻法画出决策面 %%%%%%%%%%%%%%%%%% X=[X_T;X_R];Y=[Y_T;Y_R]。