近鄰法與剪輯近鄰法.doc

云南大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)實驗教學(xué)中心實驗報告云南大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)實驗教學(xué)中心實 驗 報 告課程名稱：模式識別學(xué)期：20092010學(xué)年 第二學(xué)期成績：指導(dǎo)教師： 胡光華學(xué)生姓名：。學(xué)生學(xué)號：。實驗名稱：近鄰法與剪輯近鄰法實驗編號：5實驗日期：2010-5-22實驗學(xué)時：4學(xué)時學(xué)院： 數(shù)學(xué)與統(tǒng)計學(xué)院專業(yè) ： 信息與計算科學(xué)年級： 2007級一、實驗?zāi)康哪芨鶕?jù)給出的訓(xùn)練集與測試集，用近鄰法，k近鄰法與剪輯近鄰法, 重復(fù)剪輯近鄰法給出測試集的分類結(jié)果并分別計算其錯誤率。二、實驗內(nèi)容畫出近鄰法的程序框圖，對給定的分別存放在文件“riply_trn.mat”和”riply_tst.mat”中的兩類樣本訓(xùn)練集250個測試集1000個，試用近鄰法，k近鄰法與剪輯近鄰法, 重復(fù)剪輯近鄰法給出測試集的分類結(jié)果并分別計算其錯誤率。三、實驗環(huán)境Windows XPMatlab6.5四、實驗過程一、程序框圖：載入250個訓(xùn)練集1000個測試集i=1000拿出測試集中一個值計算與250個訓(xùn)練集的距離并且根據(jù)距離來判別其類別i=i+1YN根據(jù)訓(xùn)練集得到的判斷結(jié)果與測試集實際類別比較得到錯誤率開始結(jié)束二、實驗相關(guān)代碼：（1）最近鄰法%計算錯誤率函數(shù)function P=ZQL_func(ys,yr)load riply_tst;yr=y; n=size(ys,2); t=0; for i=1:n if ys(i)-yr(i)=0 t=t+1; end end P=1-t/n;%最近鄰函數(shù)文件function ypd=ZJL_func(Xtr,ytr,Xts,yts)m1,n1=size(Xtr);m2,n2=size(Xts);d=zeros(1,n1);ypd=zeros(1,n2);for i=1:n2 for j=1:n1 d(j)=(Xts(1,i)-Xtr(1,j)2+(Xts(2,i)-Xtr(2,j)2; %歐式距離 end min=d(1); r=1; for t=2:n1 if d(t)=d(r) a=d(t); d(t)=d(r); d(r)=a; b=ytr(t); ytr(t)=ytr(r); %對距離進(jìn)行排序 ytr(r)=b; end end end p=0; q=0; for s=1:k if ytr(s)=1 p=p+1; else q=q+1; %尋找最近的k個來判斷類別 end end if pq ypd(i)=1; else ypd(i)=2; endendZQL_func(ypd,yts)%根據(jù)作圖找使得錯誤率達(dá)到最小的k值k=25:120;k1=44,54;P2=KJL(k);figure(1),plot(k,P2(:)hold onplot(k1,min(P2(:),*r)hold off得到圖形如下：從圖中可看出當(dāng)k值在43附近能使得錯誤率達(dá)到最小，約為0.079。（3）剪輯近鄰法：%剪輯法函數(shù)文件：function Xbz,ybz,n=JJF_func(Xjs,yjs,Xxs,yxs)mj,nj=size(Xjs);mx,nx=size(Xxs);d=zeros(1,nj); k=1; i=1; r=0; min=0; n=0;while k=nx for j=1:nj d(j)=(Xxs(1,i)-Xjs(1,j)2+(Xxs(2,i)-Xjs(2,j)2; end min=d(1); for t=2:nj if d(t)=min min=d(t); r=t; end end if yxs(i)-yjs(r)=0 i=i+1; else for j=i:nx Xxs(i)=Xxs(i+1); %剪輯（通過用后面的值覆蓋前面的值來實現(xiàn)） yxs(i)=yxs(i+1); end n=nx-1; end k=k+1;endXbz=zeros(mx,n);ybz=zeros(1,n);for i=1:n Xbz(:,i)=Xxs(:,i); ybz(i)=yxs(i);end%剪輯法m文件：load riply_trn;Xtr=X;ytr=y;m1,n1=size(Xtr);load riply_tst;Xts=X;yts=y;%訓(xùn)練集的分類比例為 2:3Xjs1=zeros(m1,n1);yjs1=zeros(1,n1);Xxs1=zeros(m1,n1);yxs1=zeros(1,n1);k=1;t=1;s=0;for i=1:n1 s=rand; if s=0.4 Xjs1(:,k)=Xtr(:,i); %劃分樣本 yjs1(k)=ytr(i); k=k+1; else Xxs1(:,t)=Xtr(:,i); yxs1(t)=ytr(i); t=t+1; endendXjs=zeros(m1,k);yjs=zeros(1,k);Xxs=zeros(m1,t);yxs=zeros(1,t);for i=1:k Xjs(:,i)=Xjs1(:,i); yjs(i)=yjs1(i);endfor i=1:t Xxs(:,i)=Xxs1(:,i); yxs(i)=yxs1(i);endXbz,ybz=JJF_func(Xjs,yjs,Xxs,yxs);ypd=ZJL_func(Xtr,ytr,Xts,yts); %調(diào)用最近鄰函數(shù)文件來判斷類別P=ZQL_func(ypd,yts)剪輯法所得結(jié)果：在將樣本數(shù)據(jù)以2:3的比例進(jìn)行“參考集”與“考試集”的劃分，經(jīng)過數(shù)次的重復(fù)運行（因為是隨機(jī)分類故而多運行幾次從而體現(xiàn)出規(guī)律來）后的到得最小錯誤率為：P = 0.0830；自己將劃分比例進(jìn)行了調(diào)整，發(fā)現(xiàn)在比例為4：5附近的時候錯誤率達(dá)到最小，為P =0.0770，而比例比這大或小的時候錯誤率均高于0.0770（4）重復(fù)剪輯法：%重復(fù)剪輯法函數(shù)文件：（把樣本分為5類）function X,Y,t=CFJJ_func(Xtr,ytr)m,n=size(Xtr);x1=zeros(m,n);y1=zeros(1,n);x2=zeros(m,n);y2=zeros(1,n);x3=zeros(m,n);y3=zeros(1,n);x4=zeros(m,n);y4=zeros(1,n);x5=zeros(m,n);y5=zeros(1,n);t1=0;t2=0;t3=0;t4=0;t5=0;for i=1:n t=rand; if t=0.1 t1=t1+1; x1(:,t1)=Xtr(:,i); y1(t1)=ytr(i); elseif t=0.3 t2=t2+1; x2(:,t2)=Xtr(:,i); y2(t2)=ytr(i); elseif t=0.5 t3=t3+1; x3(:,t3)=Xtr(:,i); y3(t3)=ytr(i); elseif t5 c=mod(i+1,5); else c=i+1; end if size(S1,c,2)0 S1,i,Y1,i,p(i)=JJF_func(S1,c,Y1,c,S1,i,Y1,i); end end S=cell2mat(S); %將樣本又歸為一個集合 Y=cell2mat(Y); A,ys,t=CFJJ_func(S,Y); num=sum(p);endG=S;Yypd=ZJL_func(S,Y,Xts,yts);P=ZQL_func(ypd,yts)實驗結(jié)果：自己將代碼運行數(shù)次，分析規(guī)律得到一個錯誤率相對較低的時候剪輯剩下的樣本集及其對應(yīng)的類別為：（大約還剩下28個樣本時候錯分的概率最小）G =0.0976 -0.8415 -0.1913 -0.6803 0.7577 0.6591 0.3727 0.4667 0.7771 0.7771 0.6719 -0.1913 -0.6803 0.7577 0.6591 -0.5541 -0.3665 0.0614 1.0000 1.0000 1.0000 1.0000 2.0000 1.0000 1.0000 1.0000 1.0000 0.3971 0.7107 0.5720 0.7771 0.3341 0.6483 0.5795 0.0763 0.51540.7107 0.7107 0.5720 0.3341 0.3727 0.6483 0.5795 0.3505 0.51541.0000 2.0000 1.0000 1.0000 1.0000 1.0000 2.0000 1.0000 1.0000-0.5976 0.7577 0.0763 0.6320 -0.9859 0.2104 -0.5745 0.0926 0.6371 0.2551 0.6057 0.0763 0.6320 -0.9859 0.2104 0.1862 0.0926 0.