1、共享知識分享快樂 模式識別實驗報告 班 級：電子信息科學與技術 13級02班 姓 名： 學 號： 指導老師： 成 績： 通信與信息工程學院 卑微如螻蟻、堅強似大象 實驗一最大最小距離算法 一、實驗內容 1. 熟悉最大最小距離算法，并能夠用程序寫出。 2. 利用最大最小距離算法尋找到聚類中心，并將模式樣本劃分到各聚類中 心對應的類別中。 二、實驗原理 N個待分類的模式樣本 XX2 ，Xn，分別分類到聚類中心 乙,Z2 ，Zn 對應的類別之中。 最大最小距離算法描述： （1）任選一個模式樣本作為第一聚類中心 Z,。 （2）選擇離乙距離最遠的模式樣本作為第二聚類中心 Z2。 （3）逐個計算每個模式樣

2、本與已確定的所有聚類中心之間的距離，并選出 其中的最小距離。 （4） 在所 有最小距離中選出一個最大的 距離，如果 該最大 值達到了 乙Z2的一定分數比值以上，則將產生最大距離的那個模式樣本定義為新增的 聚類中心，并返回上一步。否則，聚類中心的計算步驟結束。這里的Z! Z2的 一定分數比值就是閾值T ,即有： T 憶 Z201 （5）重復步驟（3）和步驟（4），直到沒有新的聚類中心出現為止。在這個 過程中，當有k個聚類中心Z!,Z2 ，Zn時，分別計算每個模式樣本與所有聚 類中心距離中的最小距離值，尋找到N個最小距離中的最大距離并進行判別， 結 果大于閾值T是，Zki存在，并取為產生最大值的相

3、應模式向量；否則，停止尋 找聚類中心。 （6）尋找聚類中心的運算結束后，將模式樣本Xi,i 1,2 , N按最近 距離劃分到相應的聚類中心所代表的類別之中。 三、實驗結果及分析 該實驗的問題是書上課后習題 2.1 ,以下利用的matlab中的元胞存儲10個 二維模式樣本 X1=0;0;X2=1;1;X3=2;2;X4=3;7;X5=3;6; X6=4;6;X7=5;7;X8=6;3;X9=7;3;X10=7;4; 利用最大最小距離算法，matlab運行可以求得 Com mjHnd 謝nd* 1*9, s三 三 mm m 三三三 s= s 三 m mss szse 狽晚礁 臭申心為訂 從matl

4、ab運行結果可以看出，聚類中心為 ,7,9，以X,為聚類中心的 點有Xi,X2,X3，以X7為聚類中心的點有X4,X5,X6,X7，以X9為聚類中心的有 X8,X9,X10。同時，做出聚類分析后的分布圖，如下: 樣本坐標聚類顯示圖 圖中用藍色大圈標記了聚類中心，用星號標記了以Xi為聚類中心的樣本， 用三角符號標記了以以X7為聚類中心的樣本，用紅色小圈標記了以X9為聚類中 心的樣本，該程序成功進行了分類 實驗二感知器算法 、實驗內容 1. 熟悉感知器算法，并能夠用程序寫出。 2. 利用感知器算法進行判別分類，算出判別函數，畫出判別界面 二、實驗原理 直接用來對模式進行分類的準則函數。若分屬于 1

5、,3 2的兩類模式可用一 方程d(X) 0來劃分，那么稱d(X)為判別函數，或稱判決函數、決策函數。如， 一個二維的兩類判別問題，模式分布如圖示，這些分屬于3 i，3 2兩類的模式可 用一直線方程d(X) 0來劃分。其中d (X) wn w2x2 w3 0式中：x1, x2 為坐標變量。 將某一未知模式X代入： d (X)w2x2 w3 若d(X) 0，則X !類; 若d(X) 0,則X 2類； 若d(X) 0，則X 或X 血或拒絕。 兩 類 線 性 可 分 的 模 式 類1, 2 , 設 d(X) WTX 其 中 , W w1,w2, ,wn,wn 1 T ， X x1,x2, ,xn,1T

6、 應具有性質 d(X) WT X 0, X 0,X 對樣本進行規范化處理，即 2類樣本全部乘以(-1)，則有: d(X ) W T X 0 感知器算法通過對已知類別的訓練樣本集的學習， 尋找一個滿足上式的權向 量。 感知器算法步驟: (1 )選擇N個分屬于3 1和3 2類的模式樣本構成訓練樣本集 X1,X2 ，XN 構成增廣向量形式， 并進行規范化處理。 任取權向量初始值 W(1)， 開始迭代。迭代次數 k=1。 (2)用全部訓練樣本進行一輪迭代，計算 W k Xi 的值，并修正權向量 分兩種情況，更新權向量的值: 1. 若WT k Xi 2 3 0 1 01 ; v2 4 =1 11*; 利

7、用感知器算法，matlab運行得到如下結果： II Command Windc-w 1 Cut ky xcnl plot hrldl 因此，可以得到感知器算法算出的判別函數為: d(X) 3x1 2x2 3x3 1 利用matlab的畫圖函數畫出判別界面以及樣本點，得到如下的分布圖: 由樣本分布圖可以看出，判別界面成功將兩類訓練樣本分離 實驗三LMSE算法 一、實驗內容 1. 了解LMSE算法，并能夠用程序寫出。 2. 利用LMSE算法進行判別分類，算出判別函數，并畫出判別界面。 二、實驗原理 LMSE算法為最小平方誤差算法，其算法過程如下： (1) 將N個分屬于!類和2類的n維模式樣本寫成增

8、廣形式，將屬于2的 訓練樣本乘以( -1 )，寫出規范化增廣樣本矩陣 X 。 (2) 求X的偽逆矩陣X# (XTX)-1XT。 ( 3)設置初值 c 和 B(1)， c 為正的校正增量， B(1) 的各分量大于 0，括號 中數字代表迭代次數 k=1 ，開始迭代。 ( 4)計算 e(k) XW (k) B(k) ，進行可分性判別。 如果e(k) 0,模式線性可分，解為W(k)，算法結束。 如果e(k) 0,模式線性可分，有解。繼續迭代。 如果e(k) 0，停止迭代，檢查XW(k)是否大于0。若大于0,有解，否則無 解，算法結束。 ( 5)計算 W (k 1) 和 B(k 1) 先計算 B(k 1

9、) B(k) ce(k) |e(k)|，再計算 W(k 1) X#B(k 1)，迭代次 數 k 加 1 ，返回第( 4 )步。 三、實驗結果及分析 該實驗用的訓練樣本與感知器算法使用的樣本一致，為以下兩類訓練樣本： 1 : (0,0,0)T ,(1,0,0)T,(1,0,1)T,(1,1,0)T 2: (0,0,1)T,(0,1,1)T,(0,1,0)T,(1,1,1)T 設定初始值B(1) (1,1,1,1,1,1,1,1)T，同樣地利用matlab中的元胞數組存放訓練 樣本點，通過編寫matlab的LMSE程序可以得到以下結果: Cammi nd Whdz 鵝期別因拚為:di.)=+-22

10、 +卜2*13-：I Currenr ph匸 liel止 如I 所以，LMSE算法求得的該兩類訓練樣本的判別函數為 d(X) 2x1 2x2 2x3 1 利用matlab的畫圖函數畫出判別界面以及樣本點，得到如下的分布圖: 由樣本分布圖可以看出，LMSE算法所得的判別界面也成功將兩類訓練樣本 分離。 實驗四Parzen窗估計 一、實驗內容 1. 了解Parzen窗概率密度的估計方法，能用程序實現。 2. 編寫matlab程序，求解一個正態密度的 Parzen窗估計。 二、實驗原理 設區域Rn是一個d維的超立方體，并設hN是超立方體的棱長，則超立方體 的體積為定義窗函數(u)為 (u) 1, u

11、j1;j 1,2, ,d 0,其他 由于(u)是以原點為中心的一個超立方體，所以當 Xi落入到以X為中心， 體積為V的超立方體時，(u)(X XJ/hN1，否則(u)0，因此落入該 超立方體內的樣本數為 kN (X Xi (hN Pn (X)是p(X)的第N次估計，則有 ?n(X) kN/N Vn 所以聯立上面兩式得 ?n(X) 1 - (- ) N i i VhN 這個式子就是Parzen窗法的基本公式 三、實驗結果與分析 待估計的p(X)的均值為零，方差為1的正態密度函數，利用matlab可以隨 1 2 -u 2 (u) 機產生1個，16個，2 5 6個學習樣本 Xi的樣本集，選取正態窗函

12、數 并設hN ，h1分別取0.25,，0,4.0，利用matlab可以得到不同取值下的 N .2 e 估計結果。 (1)當N 1，h 0.25,1.0,4.0時得到的結果 N=1,h1=0.25 的 Parzen 窗估計 N=1,h1=1 的 Parzen 窗估計 從圖中可以看出，估計概率密度函數是一個樣本為中心的小丘，誤差很大 (2)當N 16，h 0.25,1.0,4.0時得到的結果 原概率分布 0.5 N=l6,h1=0.25 的 Parzen窗 估 計 1.5 r 5 0L -5 N=16,h1=4 的 Parzen 窗估計 從圖中可以看出，在h10.25時，噪聲誤差非常大，產生了不連

13、續性。慢慢 增大時，受到了平滑，但平均性誤差也隨之增大，分辨率降低。 (3) 當N 256，h 0.25,1.0,4.0時得到的結果 從下圖可以看出，當N增大到256，估計量越來越好，在h1 4時，估計量 很接近真實分布。 原概率分布 N=256,h仁0.25 的 Parzen 窗估計 0.8 0.6 0.4 0.2 0 05 N=256,h1=4 的 Parzen 窗估計 -5 N=256,h仁1的Parzen窗估計 0.8 0.6 0.4 0.2 0 -505 從整個實驗來看，Parzen窗法只要樣本足夠多，總可以保證收斂于任何復 雜的未知概率密度函數，但是也受到 hN值的影響，當hN太小

14、時，就會造成不連 續性，噪聲誤差增大。當hN太大時，分辨率就會下降，平均性誤差就會增大。 附錄一 最大最小距離算法程序 clear; clc; X1=0;0;X2=1;1;X3=2;2;X4=3;7;X5=3;6; X6=4;6;X7=5;7;X8=6;3;X9=7;3;X10=7;4; %取第一個點為一個聚類中心 z1=X1; position(1)=1; %計算其它點到 z1 的距離 for i=1:10 d(i)=dist(Xi,z1); end %找到距離 z1 最遠的點的位置 max_dist=max(d); pos=find(d=max(d); z2=Xpos; position(

15、2)=pos; rate=0.5;%分數比值設置為 0.5 T=rate*dist(z1,z2);%初始閾值 min_dist=d; flag=2; index=1; while (1) %循環求出其他距離并與事先設定的閾值作比較 for i=1:10 d(flag,i)=dist(Xi,zflag); if min_dist(i)d(flag,i) min_dist(index)=d(flag,i); else min_dist(index)=min_dist(i); end index=index+1; end index=1; max_dist=max(max(min_dist); x

16、y=find(min_dist=max(min_dist); if (max_distT) flag=flag+1; zflag=Xy; position(flag)=y; else break ; end end fprintf( 以下序號的樣本為聚類中心 :n for i=1:flag fprintf(%dt ,position(i); end fprintf(n= %計算各樣本到各聚類中心的距離 for i=1:10 for j=1:flag distance(i,j)=dist(Xi,zj); end end flag1=1; flag2=1; distance2=distance;

17、mincol I=min(distance2); %對 10 個樣本進行聚類 for i=1:10 for j=1:flag if (I(i)=j) array(j,flag1)=i; flag1=flag1+1; else continue ; end end end %對聚類結果進行輸出 while (flag2=flag) fprintf( n 第%d類的聚類中心為：dn fprintf( 屬于第 %d 類的有 :n ,flag2); for i=1：10 if (array(flag2,i)=0) fprintf(%dt ,array(flag2,i); if flag2=1 plot

18、(Xarray(flag2,i)(1),Xarray(flag2,i)(2), ); ); ,flag2,position(flag2); b* ); holdon; end if flag2=2 plot(Xarray(flag2,i)(1),Xarray(flag2,i)(2),black) holdon; end if flag2=3 plot(Xarray(flag2,i)(1),Xarray(flag2,i)(2), title( 樣本坐標聚類顯示圖 ); holdon; end end end fprintf( n ); flag2=flag2+1; end grid on; ax

19、is(0 8 0 9); hold on plot(Xposition(1)(1),Xposition(1)(2), hold on plot(Xposition(2)(1),Xposition(2)(2), hold on plot(Xposition(3)(1),Xposition(3)(2), o , Markersize o , Markersize o , Markersize ro ); ,10); ,10); ,10); 附錄二 感知器算法程序 clc;clear; w11 = 0 0 0;w12 =1 0 0;w13 =1 0 1;w14 =1 1 0; w21 = 0 0 1

20、;w22 =0 1 1;w23 =0 1 0;w24 =1 1 1; rol col = size(w11); for i=1:4 w1i(rol+1,1)=1; w2i(rol+1,1)=1; w2i=w2i.*-1; end k=1; W(k,:)=-1,-2,-2,0; flag=0; while (1) %w1 的計算 for i=1:4 k=k+1; if (W(k-1,:)*w1i)=0) W(k,:)=W(k-1,:)+w1i; flag=1;%發生錯判，立即將標記位賦 1 else W(k,:)=W(k-1,:); end end %w2 的計算 for i=1:4 k=k+1

21、; if (W(k-1,:)*w2i)=0) W(k,:)=W(k-1,:)+w2i; flag=1;%發生錯判，立即將標記位賦 1 else W(k,:)=W(k-1,:); end end if flag=1 flag=0; else break ; end end fprintf( 求得判別函數為： t ); ,num2str(W(k,1),num2str fprintf( d(X)=(%s*x1)+(%s*x2)+(%s*x3)+(%s)n (W(k,2),num2str(W(k,3),num2str(W(k,4); for i=1:4 w2i=w2i.*-1; end x1=-2:0

22、.01:2; x2=-2:0.01:2; x1 x2=meshgrid(x1,x2); x3=(W(k,1)*x1+W(k,2)*x2+W(k,4)/(-1*W(k,3); surf(x1,x2,x3); hold for i=1:4 plot3(w1i(1),w1i(2),w1i(3),b*); plot3(w2i(1),w2i(2),w2i(3),rA); end title( 感知器算法判別界面及樣本分布圖 ); 附錄三LMSE算法程序 clc;clear; w11 = 0 0 0;w12 =1 0 0;w13 =1 0 1;w14 =1 1 0; w21 = 0 0 1;w22 =0

23、1 1;w23 =0 1 0;w24 =1 1 1; rol col = size(w11); for i=1:4 w1i(rol+1,1)=1; w2i(rol+1,1)=1; w2i=w2i.*-1; end X=w11,w12,w13,w14,w21,w22,w23,w24; XW=inv(X*X)*X; k=1; B(k,:)=1,1,1,1,1,1,1,1; flag=0; c=1; while (1) W(k,:)=XW*B(k,:); e=X*W(k,:)-B(k,:); if mean(abs(e)1.0e-014|e=0 flag=0; break ; end if e=0

24、flag=1; break ; end end k=k+1; B(k,:)=B(k-1,:)+c*(e+abs(e); end if flag=1 fpritf( 該模式樣本線性不可分 n ); else fprintf( 求得判別函數為： t ); ,num2str(W(k,1),num2str ); ); fprintf( d(X)=(%s*x1)+(%s*x2)+(%s*x3)+(%s)n (W(k,2),num2str(W(k,3),num2str(W(k,4); for i=1:4 w2i=w2i.*-1; end x1=-2:0.01:2; x2=-2:0.01:2; x1 x2=

25、meshgrid(x1,x2); x3=(W(k,1)*x1+W(k,2)*x2+W(k,4)/(-1*W(k,3); surf(x1,x2,x3); hold for i=1:4 plot3(w1i(1),w1i(2),w1i(3),b* plot3(w2i(1),w2i(2),w2i(3),rA end end title( LMSE 算法判別界面及樣本分布圖 ); 附錄四Parzen 估計算法程序 clc;clear; X=randn(1,3000); px=normpdf(X,0,1); % N=1 的情況 % pNx1_1=parzen(0.25,1,X); pNx1_2=parze

26、n(1,1,X); pNx1_3=parzen(4,1,X); subplot(221); plot(X,px, . );grid on ; title( 原概率分布 ); subplot(222) plot(X,pNx1_1, . );grid on; title( N=1,h1=0.25 的 Parzen 窗估計 subplot(223); plot(X,pNx1_2, . );grid on; title( N=1,h1=1 的 Parzen 窗估計 ); subplot(224); plot(X,pNx1_3, . );grid on; title( N=1,h1=4 的 Parzen 窗估計 ); % N=16 的情況 % pNx16_1=parzen(0.25,16,X); pNx16_2=parzen(1,1