近鄰分類分類器設(shè)計(jì)

近鄰分類分類器設(shè)計(jì)一、設(shè)計(jì)任務(wù)對(duì)“data3?數(shù)據(jù)，采用剪輯法、壓縮法生成參考集，近似描繪其決策面，并用所有數(shù)據(jù)測(cè)試其分類效果。二、設(shè)計(jì)原理1、最近鄰法最近鄰分類器（nearestneighborhoodclassifier最小九距離分類器的一種極端的情況，以全部訓(xùn)練樣本作為代表點(diǎn)，計(jì)算測(cè)試樣本與所有樣本的距離，并以最近鄰者的類別作為決策。最初的近鄰法是由Cover和Hart于1968年提出的，隨后得到理論上深入的分析與研究，是非參數(shù)法中最重要的方法之一。最近鄰法：將與測(cè)試樣本最近鄰樣本的類別作為決策的結(jié)果。對(duì)一個(gè)C類別問題，每類有N個(gè)樣本,ii1,2,…問題，每類有N個(gè)樣本,ii1,2,…C，則第i類的判別函數(shù)為:ig(x)imin||xkXkllk1,2,.,Ni i(1)因此，最近鄰決策規(guī)則：若g(X)j因此，因此，最近鄰決策規(guī)則：若g(X)j因此，k-近鄰決策規(guī)則:若g(x)jmaxkiiming(x),i1,2,???c.ii(2)則決策 xj由上可以看出最近鄰法在原理上最直觀，方法上也十分簡(jiǎn)單，但明顯的缺點(diǎn)就是計(jì)算量大，存儲(chǔ)量大。2、k-近鄰法k-近鄰法即為最近鄰法的擴(kuò)展，其基本規(guī)則是，在所有N個(gè)樣本中找到與測(cè)試樣本的k個(gè)最近鄰者，其中各類別所占個(gè)數(shù)表示成k,i1,2,…C，定義判i別函數(shù)為：(3)g(x)k,i1,2,…c(3)i i(4)則決策k-近鄰一般采用k為奇數(shù)，跟投票表決一樣，避免因兩種票數(shù)相等而難以決策。決策規(guī)則為：j=argmaxg(x),i=1,…,cii3、改進(jìn)的近鄰法近鄰法的一個(gè)嚴(yán)重問題是需要存儲(chǔ)全部訓(xùn)練樣本，以及繁重的距離計(jì)算量。從而提出了兩類改進(jìn)的方法：一種是對(duì)樣本集進(jìn)行組織與整理，分群分層，盡可能將計(jì)算壓縮到在接近測(cè)試樣本鄰域的小范圍內(nèi)，避免盲目地與訓(xùn)練樣本集中每個(gè)樣本進(jìn)行距離計(jì)算。另一種則是在原有樣本集中挑選出對(duì)分類計(jì)算有效的樣本，使樣本總數(shù)合理地減少，以同時(shí)達(dá)到既減少計(jì)算量，又減少存儲(chǔ)量的雙重效果。3.1、剪輯近鄰法剪輯近鄰法：其基本思想是，利用現(xiàn)有樣本集對(duì)其自身進(jìn)行剪輯，將不同類別交界處的樣本以適當(dāng)方式篩選，可以實(shí)現(xiàn)既減少樣本數(shù)又提高正確識(shí)別率的雙重目的。剪輯的過程是：將樣本集Xn分成兩個(gè)互相獨(dú)立的子集：test集咒nt和reference集Xnr。第一步：用reference集Xnr中每一個(gè)樣本y對(duì)test集Xnt中的i樣本x用近鄰法進(jìn)行分類。如果y與x不屬于同一類別，則將x從設(shè)計(jì)集Xnt中i ii i刪除，最后得到一個(gè)剪輯的樣本集XNTE(剪輯樣本集)，以取代原樣本集，對(duì)待識(shí)別樣本進(jìn)行分類；第二步：用剪輯的樣本集XNTE并用最近鄰法對(duì)未知的樣本x進(jìn)行分類。k逝鄰剪輯：與最近鄰剪輯相似，第一步用k-近鄰法進(jìn)行剪輯，得到剪輯的樣本集XNTE;第二步：用剪輯的樣本集XNTE并用最近鄰法對(duì)未知的樣本x進(jìn)行分類。重復(fù)剪輯近鄰法：將樣本集重復(fù)進(jìn)行剪輯，常用的是MULTIEDIT算法：、將樣本集XN隨機(jī)劃分為s個(gè)子集，即XN={X,X,X},S>3；123、用最近鄰法，以x 為參考集，對(duì)X,i=1,2,…s中的樣本進(jìn)行分類；(i+1)mod(s) i、去掉在(2)被錯(cuò)分類的樣本；、用所有留下的樣本構(gòu)成新的樣本集XNTE；、重復(fù)(1)~(5)步，直到?jīng)]有樣本被剪輯掉，則停止。3.2、壓縮近鄰法壓縮近鄰法：利用現(xiàn)有樣本集，逐漸生成一個(gè)新的樣本集，使該樣本集在保留最少量樣本的條件下，仍能對(duì)原有樣本的全部用最近鄰法正確分類，那末該樣本集也就能對(duì)待識(shí)別樣本進(jìn)行分類，并保持正常識(shí)別率。壓縮近鄰法的步驟是：定義兩個(gè)存儲(chǔ)器，一個(gè)用來存放即將生成的樣本集，稱為Store；另一存儲(chǔ)器則存放原樣本集，稱為Grabbag。其算法是：(1)、初始化。Store是空集，原樣本集存入Grabbag；從Grabbag中任意選擇一樣本放入Store中作為新樣本集的第一個(gè)樣本。(2)、樣本集生成。在Grabbag中取出第i個(gè)樣本用Store中的當(dāng)前樣本集按最近鄰法分類。若分類錯(cuò)誤，則將該樣本從Grabbag轉(zhuǎn)入Store中，若分類正確，則將該樣本放回Grabbag中。(3)、結(jié)束過程。若Grabbag中所有樣本在執(zhí)行第二步時(shí)沒有發(fā)生轉(zhuǎn)入Store的現(xiàn)象，或Grabbag已成空集，則算法終止，否則轉(zhuǎn)入第二步。最后我們以Store中的樣本作為最近鄰法的設(shè)計(jì)集，但這時(shí)的樣本數(shù)目卻大大減少了，因此可大大節(jié)省存儲(chǔ)量。三、關(guān)鍵程序由于老師給的數(shù)據(jù)太長(zhǎng)，故在此將其省去，詳見隨包所帶附件，本設(shè)計(jì)的關(guān)鍵程序如下：%%%%%%%%%%%%%%%%%%%剪輯近鄰法%%%%%%%%%%%%%%%%%%%TH=0.3;%閾值，決定考試集和參考集中數(shù)據(jù)的個(gè)數(shù)，其中考試集的個(gè)數(shù)為N*(1-TH)，參考集的個(gè)數(shù)為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;%總共循環(huán)次數(shù)NN=1;%統(tǒng)計(jì)某次剪輯掉多少個(gè)數(shù)據(jù)num=0;%統(tǒng)計(jì)一共剪輯掉多少個(gè)數(shù)據(jù)key=0;%統(tǒng)計(jì)一共有多少次一個(gè)數(shù)據(jù)都沒有剪輯掉cishu=0;%統(tǒng)計(jì)剪輯次數(shù)k=1;%當(dāng)k=1時(shí)即為最近鄰法，反之則為k近鄰法，比如當(dāng)k=3時(shí)即為3近鄰法fx=[];fy=[];Xmax=max(X0(:，1));Ymax=max(X0(:，2));Xmin=ceil(Xmax);Ymax=ceil(Ymax);whileii<18&&key<5rand('seed',22);%使下行的crossvalind隨機(jī)分配數(shù)據(jù)函數(shù)每次遠(yuǎn)行時(shí)產(chǎn)生的隨機(jī)數(shù)一樣，如果將其刪除，則每次產(chǎn)生的隨機(jī)數(shù)不同，從而遠(yuǎn)行結(jié)果也不同[Test,Reference]=crossvalind('HoldOut',YTH);%將data.3中的數(shù)據(jù)隨機(jī)分成2部分，一半由于訓(xùn)練，另一部分用于測(cè)試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=[];fori=1:lx_Rforj=1:lx_Txnew(j,:)=X_R(i,:);endf(i,:)=sum(((xnew-X_T).人2)');endf=f';forj=1:k[ff,TN]=min(f);fori=1:lx_Rf(TN(i),i)=1/eps;endINDEX(j,:)=TN;enddd=zeros(lx_R,1);fori=1:kdd=dd+Y_T(INDEX(i,:));enddd=sign(dd);dif=Y_R-dd;chang=find(dif);ifisempty(chang)key=key+1;elsekey=0;cishu=cishu+1;xtp=find(Y_T>0);%考試集第一類數(shù)據(jù)xtn=find(Y_TvO);%考試集第二類數(shù)據(jù)xrp=find(Y_R>0);%參考集第一類數(shù)據(jù)xrn=find(Y_RvO);%參考集第二類數(shù)據(jù)figure;holdon;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(參考集)','剪輯掉的數(shù)據(jù)'，‘boxoff);holdon;holdon;plot(X_R(chang，1)，X_R(chang，2)，'rs');holdon;zuobiao=[060020];fori=1:length(chang)fx=[fxX_R(chang(i)，1)];fy=[fyX_R(chang(i)，2)];endendX_R(chang，:)=[];Y_R(chang，:)=[];lxx=lx_T+length(Y_R);NN=NN-lxx;num=num+NN;ifNN>0title({'\color{magenta}data3.m中用近鄰法中的\color{blue}剪輯近鄰法\color{magenta}進(jìn)行處理';['第'num2str(cishu)'次剪輯'];['本次剪輯掉'num2str(NN)'個(gè)數(shù)據(jù)累計(jì)剪輯掉'num2str(num)'個(gè)數(shù)據(jù)']});enddrawnowholdoff;Y=ones(lxx，1);X0=[X_T;X_R];Y0=[Y_T;Y_R];ii=ii+1;clearxnewfffTNchangINDEXendxtp=find(Y_T>0);%考試集第一類數(shù)據(jù)xtn=find(Y_TvO);%考試集第二類數(shù)據(jù)xrp=find(Y_R>0);%參考集第一類數(shù)據(jù)xrn=find(Y_RvO);%參考集第二類數(shù)據(jù)figuresubplot(2，1，1);holdon;plot(xl(:,l),xl(:,2),'b*',x2(:,l),x2(:,2),'gO')%畫出原數(shù)據(jù)axisequalholdon;plot(fx,fy,'rs');holdontitle({'原數(shù)據(jù)其中紅色框住的為即將剪輯掉的數(shù)據(jù)';['一共需剪輯掉'num2str(num)'個(gè)數(shù)據(jù)']},'Color','m');holdoffdrawnowsubplot(2,1,2);holdon;plot(X_T(xtp,1),X_T(xtp,2),'b*',X_T(xtn,1),X_T(xtn,2),'gO')axisequalholdon;plot(X_R(xrp,1),X_R(xrp,2),'b*',X_R(xrn,1),X_R(xrn,2),'gO')holdontitle('\color{blue}采用\color{magenta}剪輯近鄰法\color{blue}最終得到的數(shù)據(jù)');holdoff;drawnowclearff2XYlxxnew%%%%%%%%%%%%%%%%用近鄰法畫出決策面%%%%%%%%%%%%%%%%%%X=[X_T;X_R];Y=[Y_T;Y_R];sxp=find(Y>0);sxn=find(Y<0);lx=length(Y);m=0;figure;plot(X(sxp,l),X(sxp,2),'b*',X(sxn,l),X(sxn,2),'gO')%畫出剪輯后的數(shù)據(jù)holdondrawnowxnew=[];f=[];lims=axis;xx=[];forix=0:0.2:lims(2)forjy=0:0.2:lims(4)mindistan=(X(1,1)-ix)A2+(X(1,2)-jy)A2;forkk=2:lxdistan=(X(kk,1)-ix)A2+(X(kk,2)-jy)A2;ifmindistan>=distanmindistan=distan;lab=kk;endendlabel=Y(lab);ifjy~=0 %找出分類界面點(diǎn)label2=label-m;iflabel2~=0xx=[xx;ixjy];endendm=label;endendplot(xx(:,l),xx(:,2),'r.')%畫出剪輯近鄰法的決策面holdontitle('\color{blue}采用近鄰法畫出通過\color{magenta}剪輯近鄰法\color{blue}剪輯后的決策');holdoffdrawnow%%%%%%%%%采用非線性SVM畫出剪輯法的決策面%%%%%%%%%%%%%%%%%X=[xl;x2];Y=YY;lx=length(Y);sxp=find(Y>0);sxn=find(Y<0);kernel=zeros(lx);aa=2;fori=l:lxforj=l:lxkernel(i,j)=exp(-sum(((X(i,:)-X(j,:)).A2)')'/(2*aaA2));endendfigure;plot(X(sxp,l),X(sxp,2),'b*',X(sxn,l),X(sxn,2),'gO')holdondrawnowaxis(zuobiao)lims=axis;H=(Y*Y').*(kernel);H=H+le-l0*eye(size(H));%防止Hessian矩陣陷入最壞情形.C=5000;f=-ones(lx,l);Aeq=Y';Beq=0;lb=zeros(lx,l);ub=C*ones(lx,l);x0=rand(lx,l);[x,feil]=quadprog(H,f,[],[],Aeq,Beq,lb,ub,x0);svm=find(abs(x)>sqrt(eps));%找出支持向量svmlsvm=length(svm);ifisempty(svm)b=0;error('沒有支持向量)；else[maxx,maxPos]=max(x);b=Y(maxPos)-sum((Y(svm).*x(svm)).*kernel(svm,maxPos));%求出分界面系數(shù)bendclearkernel[Xorig,Yorig]=meshgrid(linspace(lims(1),lims(2)),linspace(lims(3),lims(4)));Xnew=[Xorig(:),Yorig(:)];xnew=[];f=[];a=[];fori=1:length(Xnew)forj=1:lsvmxnew(j,:)=Xnew(i,:);endfsvm(i)=(exp(-sum(((xnew-X(svm,:)).A2)')'/(2*aaA2)))'*(x(svm,:).*Y(svm))+b;enda=X(svm,:);fori=1:lsvmm(i)=a(i,1);n(i)=a(i,2); %%用于畫支撐矢量endholdonplot(m,n,'rs');holdon[~,h]=contour(Xorig,Yorig,reshape(fsvm,size(Xorig)),[00],'m');set(h,'ShowText','on','TextStep',get(h,'LevelStep')*2)holdontitle({'\color{magenta}data3.m中的全部數(shù)據(jù)用\color{cyan}非線性SVM\color{magenta}求得決策面為：';['\color{magenta}其中支持向量個(gè)數(shù)='num2str(lsvm)]});text(Xmax-7,Ymax-1,'*x1','BackgroundColor',[.7.9.7],'EdgeColor','red');text(Xmax-7,Ymax-2,'ox2','BackgroundColor',[.7.9.7],'EdgeColor','red');text(Xmax-7,Ymax-3,'正方形為支持向量','BackgroundColor',[.7.9.7],'EdgeColor','red','FontSize',8);drawnowholdoffclearbb%%%%%%用近鄰法和SVM分別畫出各自的決策面以便比較各自性能%%%%%%%%%figure;plot(X(sxp,1),X(sxp,2),'b*',X(sxn,1),X(sxn,2),'gO')holdonaxis(zuobiao)[?,h]=contour(Xorig,Yorig,reshape(fsvm,size(Xorig)),[00],'m')%畫出非線性SVM決策面set(h,'ShowText','on','TextStep',get(h,'LevelStep')*2)holdonplot(xx(:,l),xx(:,2),'r.')%畫出剪輯近鄰法的決策面holdontitle('\color{blue}對(duì)所有數(shù)據(jù)米用\color{green}剪輯近鄰法\color{blue}和\color{magenta}非線性SVM\color{blue}分別畫出各自的決策面');text(Xmax-18,Ymax-l,'深紅線近鄰法畫出的決策面','BackgroundColor',[.7.9.7],'EdgeColor','red');text(Xmax-18,Ymax-2，粉紅線SVM畫出的決策面','BackgroundColor',[.7.9.7],'EdgeColor','red');holdoffdrawnowclearXYsxnsxpcmnxnewXnewkernelaAeqBeqlbubx0Y0X0%%%%%%%%%%%%%%%%壓縮近鄰法%%%%%%%%%%%%%%%%%%%%%forquzhi=1:2%quzhi=1是采用所有data3.m的數(shù)據(jù)進(jìn)行壓縮，反之當(dāng)quzhi=2時(shí)采用前面剪輯近鄰法剪輯后的數(shù)據(jù)進(jìn)行壓縮近鄰法分類ifquzhi==1Grabbag_X=[x1;x2];%取所有data3.m的數(shù)據(jù)賦給Grabbag_Xlxx=length(Grabbag_X);chuzhi=randi(lxx);Grabbag_Y=ones(lxx,1);Grabbag_Y(length(x1)+1:lxx)=-1;elseclearIIStore_XStore_YGrabbag_XGrabbag_YGrabbag_X=[X_T;X_R];%取剪輯近鄰法后的數(shù)據(jù)賦給Grabbag_Xlxx=length(Grabbag_X);chuzhi=randi(lxx);Grabbag_Y=[Y_T;Y_R];endStore_X=Grabbag_X(chuzhi,:);%隨機(jī)從Grabbag_X中取一個(gè)數(shù)據(jù)放到Store_X中Store_Y=Grabbag_Y(chuzhi,:);Grabbag_X(chuzhi,:)=[];%從Grabbag_X中將剛才取出的那個(gè)數(shù)據(jù)從Grabbag_X中刪除Grabbag_Y(chuzhi,:)=[];key=1;%記錄Grabbag_X中的數(shù)據(jù)在樣本集生成過程中沒發(fā)生變化的次數(shù)cishu=0;whilekey>0&&~isempty(Grabbag_X)lx_G1=length(find(Grabbag_Y>0));lx_G2=length(find(Grabbag_Y<0));lx_G=lx_G1+lx_G2;lx_S1=length(find(Store_Y>0));lx_S2=length(find(Store_Y<0));lx_S=lx_S1+lx_S2;xnew=[];cmd=[];key=0;forII=1:lx_G-1xnew=[];INDEX=[];forj=1:lx_Sxnew(j,:)=Grabbag_X(II,:);endf2=sum(((xnew-Store_X).人2)');f2=f2';forj=1:k[ff,TN]=min(f2);f2(TN)=1/eps;INDEX(j)=TN;enddd=0;fori=1:kdd=dd+Store_Y(INDEX(i));%K-近鄰法判斷所取點(diǎn)屬于哪一類,k為奇數(shù)enddd=sign(dd);%%K-近鄰法判斷所取點(diǎn)屬于哪一類即當(dāng)dd為正時(shí)屬于第一類(Y=1)dif=Grabbag_Y(II,:)-dd;%是否分類正確，若dif=O,則分類正確，反之分類錯(cuò)誤chang=find(dif);if~isempty(chang)key=key+1;cishu=cishu+1;Store_X=[Store_X;Grabbag_X(II,:)]%若分類錯(cuò)誤，則將該樣本從Grabbag轉(zhuǎn)入Store中Store_Y=[Store_Y;Grabbag_Y(II,:)];cmd=[cmdII];endlx_S1=length(find(Store_Y>0));lx_S2=length(find(Store_Y<0));lx_S=lx_S1+lx_S2;endGrabbag_Y(cmd,:)=[];%從Grabbag_Y中刪除掉分類錯(cuò)誤的數(shù)據(jù)Grabbag_X(cmd,:)=[];%從Grabbag_X中刪除掉分類錯(cuò)誤的數(shù)據(jù)lx_G1=length(find(Grabbag_Y>0));lx_G2=length(find(Grabbag_Y<0));lx_G=lx_G1+lx_G2;lx_S1=length(find(Store_Y>0));lx_S2=length(find(Store_Y<0));lx_S=lx_S1+lx_S2;endsxp=find(Store_Y>0);sxn=find(Store_Y<0);lx=length(Store_Y);figure;holdon;plot(Store_X(sxp,1),Store_X(sxp,2),'b*',Store_X(sxn,1),Store_X(sxn,2),'gO')holdon;axis(zuobiao)ifquzhi==1title({'\color{blue}data3.m中的全部數(shù)據(jù)用\color{red}壓縮近鄰法\color{blue}進(jìn)行分類'；['{\color{blue}采用壓縮近鄰法后剩余的數(shù)據(jù)為'num2str(lx)'\color{blue}個(gè)數(shù)據(jù)}']});elsetitle({'\color{blue}data3.m中數(shù)據(jù)先經(jīng)\color{cyan}剪輯近鄰法\color{blue}剪輯再用\color{red}壓縮近鄰法\color{blue}進(jìn)行分類';['\color{blue}最后剩余的數(shù)據(jù)為'num2str(lx)'個(gè)數(shù)據(jù)']},'Color','b');enddrawnowholdoff;clearff2xxlablabel%%%%%%%%%%%%%%用近鄰法畫出決策面%%%%%%%%%%%%%%%%%X=Store_X;Y=Store_Y;m=0;figure;plot(X(sxp,1),X(sxp,2),'b*',X(sxn,1),X(sxn,2),'gO')holdondrawnowxnew=[];f=[];lims=axis;xx=[];forix=0:0.2:lims(2)forjy=0:0.2:lims(4)mindistan=(X(l,l)-ix)人2+(X(l,2)-jy)人2;forkk=2:lxdistan=(X(kk,1)-ix)A2+(X(kk,2)-jy)A2;ifmindistan>=distanmindistan=distan;lab=kk;endendlabel=Y(lab);label2=label-m;iflabel2~=0xx=[xx;ixjy];endendm=label;endendplot(xx(:,1),xx(:,2),'r.')holdonifquzhi==1title({'\color{blue}對(duì)所有數(shù)據(jù)采用\color{red}壓縮近鄰法\color{blue}后采用\color{green}近鄰法';'\color{blue}得到的決策面為'});elsetitle({'\color{blue}對(duì)所有數(shù)據(jù)先經(jīng)\color{cyan}剪輯近鄰法\color{blue}剪輯再用\color{red}壓縮近鄰法\color{blue}最后經(jīng)\color{green}近鄰法';'\color{blue}得到的決策面為'});endholdoffdrawnow%%對(duì)所有數(shù)據(jù)采用壓縮近鄰法和非線性SVM共同畫出決策面以便進(jìn)行效果比較%%figure;plot(xl(:,l),xl(:,2),'b*',x2(:,l),x2(:,2),'gO')%畫出所有分類數(shù)據(jù)點(diǎn)holdonplot(xx(:,1),xx(:,2),'r.')%畫出壓縮近鄰法的分段線性決策面holdon[C,h]=contour(Xorig,Yorig,reshape(fsvm,size(Xorig)),[00],'m')%畫出svm的決策面set(h,'ShowText','on','TextStep',get(h,'LevelStep')*2)ifquzhi==ltitle({'\color{blue}對(duì)所有數(shù)據(jù)采用\color{red}壓縮近鄰法\color{blue}后再用\color{green}近鄰法\color{blue}畫出的決策面';'和對(duì)所有數(shù)據(jù)只采用\color{cyan}非線性SVM\color{blue}得到的決策面兩者共同表示為'});elsetitle({'\color{blue}對(duì)所有數(shù)據(jù)先經(jīng)\color{magenta}剪輯近鄰法\color{blue}剪輯再用\color{red}壓縮近鄰法';'\color{blue}最后經(jīng)\color{green}近鄰法\color{blue}得到的決策面'；'和對(duì)所有數(shù)據(jù)只采用\color{cyan}非線性SVM\color{blue}得到的決策面兩者共同表示為'});endtext(Xmax-18,Ymax-1,'深紅線近鄰法畫出的決策面','BackgroundColor',[.7.9.7],'EdgeColor','red');text(Xmax-18,Ymax-2，粉紅線SVM畫出的決策面’,'BackgroundColor',[.7.9.7],'EdgeColor','red');drawnowholdoffclearmnxxend四、程序仿真及結(jié)果分析1、采用剪輯近鄰法

下圖為采用剪輯近鄰法對(duì)data3.m中的數(shù)據(jù)進(jìn)行第一次剪輯時(shí)得到得仿真圖:data3.m中用近鄰法中的剪輯近鄰法進(jìn)行處理笫1友剪輯2個(gè)數(shù)揺累計(jì)剪茅掉2個(gè)劉抿201814171U*O+0□~T-Ki

x2v1m2〔考試集）〔考試集｝〔參考集）（參考集）1814171U*O+0□~T-Ki

x2v1m2〔考試集）〔考試集｝〔參考集）（參考集）剪輯掉的數(shù)拆2O1020304050COO*半°36C圖一第一次迭代后留下的樣本下圖為采用近鄰法中的剪輯近鄰法對(duì)data3.m中的數(shù)據(jù)連續(xù)進(jìn)行五次迭代時(shí)留下的樣本，由圖可知本次一共剪輯掉一個(gè)數(shù)據(jù)，累計(jì)剪輯12個(gè)數(shù)據(jù)：data3.m中用近鄰法申的勇輯逅鄰法進(jìn)行處理第匸次前編本次翦輯掉1個(gè)埶需象計(jì)瑪輯掉10個(gè)數(shù)據(jù)231314121Jzi3004-305J6C卡卡半1314121Jzi3004-305J6C卡卡半+居B)B)a)B)數(shù)試試號(hào)虧的肴考參e掉..111.■..11.■..11..■..11..■X1QK1血剪*O+-O口圖二經(jīng)連續(xù)5次迭代后留下的樣本當(dāng)連續(xù)四次沒有數(shù)據(jù)被剪輯時(shí)退出剪輯過程，在本次運(yùn)行時(shí)在連續(xù)進(jìn)行8次迭代后就沒有數(shù)據(jù)再被剪輯，由圖知本次剪輯掉I個(gè)數(shù)據(jù)，一共剪輯掉15個(gè)數(shù)據(jù)。

data3.m中用逅鄰法中的剪輯近鄰法進(jìn)行處理

第9次前輯1個(gè)數(shù)據(jù)重計(jì)剪輯掉15個(gè)數(shù)據(jù)201814M1（考試集）Om2（考試集）*x1201814M1（考試集）Om2（考試集）*x1（參考集）x2（蔘考集）□翦輯掉的數(shù)據(jù)*1210以心。。Jd■I6IcP°mII*4- 4-10304050601030405060圖三剪輯算法終止時(shí)留下的樣本下圖為剪輯前后對(duì)照?qǐng)D，有剪輯后的圖形可以看到2類數(shù)據(jù)交界面附近的如果靠的很近都將被剪輯掉，剩下的數(shù)據(jù)可以看出交界面是寬了許多。原數(shù)據(jù)其中紅色框住的沏即將剪輯掉的數(shù)據(jù)—共需剪輯掉15個(gè)數(shù)拐0 10 原數(shù)據(jù)其中紅色框住的沏即將剪輯掉的數(shù)據(jù)—共需剪輯掉15個(gè)數(shù)拐0 10 20 30 40 50采用剪輯近鄰法最終得到的數(shù)據(jù)圖四剪輯前后對(duì)照?qǐng)D下圖使用近鄰法畫出通過剪輯法后剩余數(shù)據(jù)的決策面（深紅色曲線所示），由圖可知該決策面是分段線性的：栗用ifi鄰法畫出通過剪輯近鄰法剪輯后的決策201816141210864￥20203040圖五近鄰法畫出的決策面下圖是對(duì)剪輯后留下的樣本點(diǎn)采用非線性SVM201816141210864￥20203040圖五近鄰法畫出的決策面下圖是對(duì)剪輯后留下的樣本點(diǎn)采用非線性SVM法求出的決策面：data3.m中的全部數(shù)撈用非線'^SVM求得決策面為：直中簣持向量個(gè)^4=5160*x1□x2*x1□x2正方農(nóng)為支持向量201816U1210864200 10 20 30 40 50 60圖六采用非線性SVM法畫出的決策面下圖為對(duì)所有data3.m中的數(shù)據(jù)分別采用剪輯近鄰法和非線性SVM法對(duì)其進(jìn)行分類的效果比較比較圖：￡T所有數(shù)揺采用勇輯近鄰法和非線'ftsvM分別畫出各自的決策面2U 4rI I I I I18深紅線近鄰法畫出的塊策旦粉紅線畫出的決策面16'-*14O半1210ScP。E+■42**1020**18深紅線近鄰法畫出的塊策旦粉紅線畫出的決策面16'-*14O半1210ScP。E+■42**1020**°0圖七2類分類方法對(duì)原數(shù)據(jù)進(jìn)行分類效果對(duì)比由上圖可以看到如果采用剪輯近鄰法則在兩類數(shù)據(jù)交界面附近處的數(shù)據(jù)出現(xiàn)錯(cuò)分類，這也是剪輯近鄰法的不足體現(xiàn)，而這個(gè)誤差只能減小而不能取消。而與之相比較的對(duì)所有data3.m中的數(shù)據(jù)采用非線性SVM則分類效果非常好，不過從圖中可以看到采用剪輯近鄰法得出的決策面與采用非線性SVM法得出的決策面十分接近。而且通過重復(fù)剪輯近鄰法剪輯后留下的樣本點(diǎn)比原來data3.m中的數(shù)據(jù)（共210個(gè)數(shù)據(jù)）少了15個(gè)，故存儲(chǔ)量和運(yùn)算量減少，特別是從算法復(fù)雜度上來看采用剪輯近鄰法的到得決策面的復(fù)雜度遠(yuǎn)遠(yuǎn)低于非線性SVM,在本次實(shí)驗(yàn)中如果采用剪輯近鄰法畫出決策面所耗時(shí)間大概0.5秒，而采用非線性SVM求出決策面則需要3秒鐘，可見運(yùn)算速度快也是剪輯近鄰法的優(yōu)點(diǎn)2、壓縮近鄰法

下圖為用data3.m中的全部數(shù)據(jù)用壓縮近鄰法分類得到的結(jié)果圖，由圖可知經(jīng)過壓縮近鄰法后剩余的數(shù)據(jù)為35個(gè)，由此可知留下的樣本大大減少，并且兩類數(shù)據(jù)中遠(yuǎn)離分類界面的數(shù)據(jù)被刪除，最后剩余的數(shù)據(jù)為分類界面附近的數(shù)據(jù)：data3.m中的全部數(shù)據(jù)用壓縮近鄰法進(jìn)行分類采用圧縮近鄰法后剩余的數(shù)據(jù)為36個(gè)數(shù)據(jù)201816'-141210°0IO2030405060°0IO2030405060圖八原數(shù)據(jù)經(jīng)壓縮近鄰法后留下的樣本下圖為對(duì)壓縮近鄰法后留下的數(shù)據(jù)（共36個(gè)）用近鄰法畫出的決策面:對(duì)所有數(shù)據(jù)采用壓縮近鄰法后采用近鄰法圖九用近鄰法畫出決策面下圖為對(duì)data3.m中的所有數(shù)據(jù)采用壓縮近鄰法后對(duì)留下的數(shù)據(jù)用近鄰法畫出其決策面和對(duì)所有數(shù)據(jù)只采用非線性SVM法的到得決策面相比較：朋聘蠶驛普縮近鄰法彎晶決策面髓曙I罷20深紅線近鄰法畫出的決策面粉紅線畫出的決策面匚18**非1412108o616'-4**?+°0爭(zhēng)I1020深紅線近鄰法畫出的決策面粉紅線畫出的決策面匚18**非1412108o616'-4**?+°0爭(zhēng)I1020304060圖十2類分類方法效果比較由上圖可以看出對(duì)所有數(shù)據(jù)經(jīng)壓縮近鄰法后再用近鄰法畫出的決策面和采用非線性SVM法得出的決策面十分接近。雖然在分類效果上不如非線性SVM,但總體上看只有在2類數(shù)據(jù)的交界面附近一兩個(gè)點(diǎn)被錯(cuò)分類，可見其分類效果還是挺不錯(cuò)的。而最重要的一點(diǎn)是由圖八可以清楚地看出通過壓縮近鄰法后留下的樣本點(diǎn)只有36個(gè)，相比較與data3.m中的210個(gè)樣本點(diǎn)來說這時(shí)留下的樣本數(shù)目大大減少了，因此可以大大節(jié)省存儲(chǔ)量的運(yùn)算時(shí)間，在保證精確度的前提下從而大大提高了運(yùn)算速度。下圖為先對(duì)data3.m中的所有數(shù)據(jù)經(jīng)剪輯法后再用壓縮近鄰法后