模式識別大作業(yè)

1、 模式識別導論大作業(yè)（2014-2015第一學期）南京航空航天大學2014年10月22日基于核的聯(lián)想記憶及聚類算法的研究與應用南京航空航天大學 PAGE 4 - PAGE 17 -K均值聚類（20分）功能描述： 將給定文件里的數(shù)據(jù)樣本按照k均值聚類的思想分為3類，將第一、二、三類的數(shù)據(jù)編號分別輸出并統(tǒng)計各類別模式向量的總個數(shù)。K均值聚類通過不斷調(diào)整類心和各模式的類別，最終使各模式到類心距離平方和最小，故此聚類算法將數(shù)據(jù)非常有效地進行了劃分。源代碼#include#include#include#define SIZE 150/宏定義，表示模式樣本的總量int fx(double cen64);

2、/判斷前后聚類中心是否相等，全相等，return 1；否則return 0；int main()FILE *fp;int i = 0, j = 0, t = 0, p = 0, q = 0, x = 0;/t、p、q分別記錄類別123中樣本個數(shù)int aSIZE = 0 , bSIZE = 0 , cSIZE = 0 ;double sum1 = 0, sum2 = 0, sum3 = 0;/以二維數(shù)組表示向量，arrayi是第i個樣本，center64存放第k次和第k+1次初始聚類中心double arrSIZE4, center64 = 0 ;if (fp = fopen(Iris.txt

3、, r) = NULL)/打開文件操作printf(cannot open filen);exit(0);for (i = 0; i SIZE; i+)/為數(shù)組賦值，共150個向量for (j = 0; j 4; j+)fscanf(fp, %lf, &arrij);fclose(fp);/關閉文件for (i = 0; i 3; i+)/為center64賦初值，將總體前三個向量作為初始聚類中心。for (j = 0; j 4; j+)centerij = arrij;centeri + 3j = arrij;dot = 0;p = 0;q = 0;for (i = 3; i 6; i+)f

4、or (j = 0; j 4; j+)centeri - 3j = centerij;/將第k+1次的聚類中心取代第k次放進/center前三行centerij = 0;/后三行置0for (i = 0; i SIZE; i+)sum1 = 0;sum2 = 0;sum3 = 0;for (j = 0; j 4; j+)sum1 += pow(arrij - center0j, 2);/sum用于計算歐氏距離sum2 += pow(arrij - center1j, 2);sum3 += pow(arrij - center2j, 2);if (sum1 sum2 &sum1sum3)/按距離

5、來為樣本點分類at = i;t+;for (x = 0; x4; x+)center3x += arrix;/將某一聚類中樣本的和全加起來，/注意向量各項都要累加if (sum2 sum3 &sum2 sum1)bp = i;p+;for (x = 0; x4; x+)center4x += arrix;if (sum3 sum2 &sum3 sum1)cq = i;q+;for (x = 0; x4; x+)center5x += arrix;for (i = 0; i 4; i+)/求出新聚類中心放進center后三行center3i = center3i / t;/tpq分別是類別123

6、中樣本的個數(shù)center4i = center4i / p;center5i = center5i / q; while (!fx(center);printf(類別1中的數(shù)據(jù)共計%d個，編號為：n, t);/輸出結(jié)果for (i = 0; i t; i+)printf(%d , ai + 1);printf(n類別2中的數(shù)據(jù)共計%d個，編號為：n, p);for (i = 0; i p; i+)printf(%d , bi + 1);printf(n類別3中的數(shù)據(jù)共計%d個，編號為：n, q);for (i = 0; i q; i+)printf(%d , ci + 1);printf(n)

7、;if (fp = fopen(sort_result.txt, w) = NULL)printf(cannot open filen);exit(0);for (i = 0; i t; i+)/將數(shù)據(jù)全部格式化寫到sort_result.txt里x = ai;fprintf(fp, %lf %lf %lf %lfn, arrx0, arrx1,arrx2,arrx3);for (i = 0; i p; i+)x = bi;fprintf(fp, %lf %lf %lf %lfn, arrx0, arrx1, arrx2, arrx3);for (i = 0; i q; i+)x = ci;f

8、printf(fp, %lf %lf %lf %lfn, arrx0, arrx1, arrx2, arrx3);fclose(fp);return 0;/判斷前后聚類中心是否相等，全相等，return 1；否則return 0；int fx(double cen64)int i, j;for (i = 0; i 3; i+)for (j = 0; j 0且g13(X)0，則X屬于第一類； g21(X)0且g23(X)0，則X屬于第二類； g31(X)0且g32(X)0，則X屬于第三類；在測試集上的測試結(jié)果（給出圖示，正確分類的樣本點與錯誤分類的樣本點用不同標志標出，給出正確率）訓練集：第1類

9、正確率:92.31%第2類正確率100%第3類正確率:100%三、貝葉斯決策（20分）選取的訓練集與測試集（訓練集大概是整體樣本的2/3）第一類第二類第三類總計訓練集26413490測試集13201660總計396150150訓練集：（樣本編號-150）第一類：51 53 78 101 103 104 105 106 108 109 110 111 112 113 116 117 118 119 121 123 125 126 129 130 131 132，共26個第二類：73 74 75 76 77 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93

10、94 95 96 97 98 99 100 102 107 114 115 120 122 124 127 128 134 139 143 147 150，共41個第三類：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34，共34個測試集：（樣本編號1-150）第一類：133 135 136 137 138 140 141 142144 145 146 148 149，共13個第二類：52 54 55 56 57 58 59 60 61 62 63 64 65

11、66 67 68 69 70 71 72，共20個第三類：35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 ，共16個隨機選取的2維是：第1、2個特征；第一類：藍色方形 第二類：紅色星形 第三類：綠色三角形判別函數(shù)與判別規(guī)則（計算各個類別的基本參數(shù)，根據(jù)參數(shù)寫出判別函數(shù)）（1）判別函數(shù)：%求均值，注意為列向量M1=mean(A);M2=mean(B);M3=mean(C);%p1,p2,p3分別為先驗概率；p1=N1/39;p2=N2/61;p3=N3/50;%求協(xié)方差矩陣C1、C2、C3C1=zeros(2,2);for i=1:N1 C1=C1

12、+(A(i,1),A(i,2)-M1)*(A(i,1),A(i,2)-M1);endC1=C1/N1;C2=zeros(2,2);for i=1:N2 C2=C2+(B(i,1),B(i,2)-M2)*(B(i,1),B(i,2)-M2);endC2=C2/N2;C3=zeros(2,2);for i=1:N3 C3=C3+(C(i,1),C(i,2)-M3)*(C(i,1),C(i,2)-M3);endC3=C3/N3;g1 = (-0.5)*(X-M1)*(inv(C1)*(X-M1)-0.5*log(det(C1) + log(p1);g2 = (-0.5)*(X-M2)*(inv(C2

13、)*(X-M2)-0.5*log(det(C2) + log(p2);g3 = (-0.5)*(X-M3)*(inv(C3)*(X-M3)-0.5*log(det(C3) + log(p3);M1 = 6.9615; 3.0731p1=0.6667M2 = 5.8854; 2.7390p2=0.6721M3 = 5.0500; 3.4794p3=0.6800C1 =inv(C1)=0.2354 0.03674.5118 -1.69890.0367 0.0974-1.6989 10.9117C2 =inv(C2)= 0.1754 0.0369 6.5124 -3.85370.0369 0.062

14、4-3.8537 18.3113C3 =inv(C3)=0.1307 0.101017.8981 -13.26260.1010 0.1363-13.2626 17.1622綜上，判別函數(shù)：g1(X)= -0.5*(X-M1)*inv(C1)*(X-M1)+1.5126g2(X)= -0.5*(X-M2)*inv(C2)*(X-M2)+1.9268g3(X)= -0.5*(X-M3)*inv(C3)*(X-M3)+2.0530（2）判別規(guī)則： g1(X) g2(X)且g1(X) g3(X)，則X屬于第一類； g2(X) g1(X)且g2(X)g3(X)，則X屬于第二類； g3(X) g1(X)且

15、g3(X)g2(X)，則X屬于第三類；在測試集上的測試結(jié)果（給出圖示，正確分類的樣本點與錯誤分類的樣本點用不同標志標出，給出正確率）正確分類樣本顏色：方形 錯誤分類樣本顏色：星形訓練集：第1類正確率:84.62%第2類正確率75%第3類正確率:93.75%實驗結(jié)果分析 出錯原因：樣本的分布具有統(tǒng)計特性，特征向量不是一個確定的向量，是隨機向量，所以只能根據(jù)樣本數(shù)與某一類的可能性大小來決策它是否屬于某類，故可能出錯； 算法優(yōu)點： 貝葉斯決策能對信息的價值或是否需要采集新的信息作出科學的判斷； 它能對調(diào)查結(jié)果的可能性加以數(shù)量化的評價，而不是像一般的決策方法那樣，對調(diào)查結(jié)果或者是完全相信，或者是完全不

16、相信； 如果說任何調(diào)查結(jié)果都不可能完全準確，先驗知識或主觀概率也不是完全可以相信的，那么貝葉斯決策則巧妙將信息有機地結(jié)合起來。 = 4 * GB3 * MERGEFORMAT 它可以在決策過程中根據(jù)具體情況下不斷的使用，使決策逐步完善和更加科學。缺點：它需要的數(shù)據(jù)多，分析計算比較復雜，特別在解決復雜問題時，這個矛盾就更為突出。四、特征選擇（20分）特征選擇依據(jù)K-L變換以最小均方誤差為準則進行數(shù)據(jù)壓縮，是最小均方誤差意義下的最優(yōu)正交變換。K-L變換是一種常用的特征提取方法，適用于任意的概率密度函數(shù)，在消除模式特征之間的相關性、突出差異性方面有最優(yōu)的效果。本次試利用相關矩陣R做K-L變換進行特征

17、提取。首先，求樣本的總體自相關矩陣R；然后求R的特征值，對特征值由大到小驚醒排隊，選擇前兩個較大的特征值；之后，計算兩個特征值對應的特征向量，歸一化后構(gòu)成變換矩陣，最后，對樣本中的每個X進行K-L變換，即可得到提取后的二維的特征。選取的訓練集與測試集（訓練集大概是整體樣本的2/3）第一類第二類第三類總計訓練集26413490測試集13201660總計396150150注意：為了比較正確率，故樣本選擇和第二題一樣判別函數(shù)與判別規(guī)則（計算各個類別的基本參數(shù)，根據(jù)參數(shù)寫出判別函數(shù)）（1）判別函數(shù)：%求均值，注意為列向量M1=mean(A);M2=mean(B);M3=mean(C);%p1,p2,p

18、3分別為先驗概率；p1=N1/39;p2=N2/61;p3=N3/50;%求協(xié)方差矩陣K1、K2、K3K1=zeros(2,2);for i=1:N1 K1=K1+A(i,1),A(i,2)*A(i,1),A(i,2);endK1=K1/N1-M1*M1;K2=zeros(2,2);for i=1:N2 K2=K2+B(i,1),B(i,2)*B(i,1),B(i,2);endK2=K2/N2-M2*M2;K3=zeros(2,2);for i=1:N3 K3=K3+C(i,1),C(i,2)*C(i,1),C(i,2);endK3=K3/N3-M3*M3;g1 = (-0.5)*(X-M1)

19、*(inv(K1)*(X-M1)-0.5*log(det(K1) + log(p1);g2 = (-0.5)*(X-M2)*(inv(K2)*(X-M2)-0.5*log(det(K2) + log(p2);g3 = (-0.5)*(X-M3)*(inv(K3)*(X-M3)-0.5*log(det(K3) + log(p3);M1 = 5.6689; 7.9373p1=0.6667M2 = 4.9818; 6.2727p2=0.6721M3 = 5.5865; 2.8754p3=0.6800C1 =inv(C1)=0.1498 0.11158.2462 -2.10820.1115 0.436

20、2-2.1082 2.8313C2 =inv(C2)= 0.1214 0.0662 9.0967 -1.57040.0662 0.3835-1.5704 2.8785C3 =inv(C3)=0.2215 0.05085.8946 -6.02340.0508 0.0497-6.0234 26.2844綜上，判別函數(shù)：g1(X)= -0.5*(X-M1)*inv(C1)*(X-M1)+1.0642g2(X)= -0.5*(X-M2)*inv(C2)*(X-M2)+1.9804g3(X)= -0.5*(X-M3)*inv(C3)*(X-M3)+2.7738（2）判別規(guī)則： g1(X) g2(X)且g

21、1(X) g3(X)，則X屬于第一類； g2(X) g1(X)且g2(X)g3(X)，則X屬于第二類； g3(X) g1(X)且g3(X)g2(X)，則X屬于第三類；在測試集上的測試結(jié)果（給出圖示，正確分類的樣本點與錯誤分類的樣本點用不同標志標出，給出正確率）正確分類樣本顏色：方形 錯誤分類樣本顏色：星形訓練集：第1類正確率:92.31%第2類正確率100%第3類正確率:100%實驗結(jié)果分析正確率第一類第二類第三類貝葉斯決策84.62%75%93.75%K-L加貝葉斯決策92.31%100%100%K-L變換優(yōu)點：去相關性好，是均方誤差意義下的最佳變換，它在數(shù)據(jù)壓縮技術(shù)中占有重要地位。由表中很

22、明顯的看出K-L變換后再用貝葉斯決策正確率有很大的提高。缺點：因為要求特征值和特征向量，這并不是一件容易的事，維數(shù)較高時甚至求不出來。即使能借助計算機求解，也很難滿足實時處理的要求，這些因素造成了K-L變換在工程實踐中不能廣泛使用。五、系統(tǒng)設計（12分）任務描述：設計一個模式識別系統(tǒng)，可以識別筆、直尺與橡皮。基本功能：按照統(tǒng)計類模式識別的基本過程，給出每一步的設計與實現(xiàn)過程。例如選擇什么特征，如何獲取特征，學習樣本有多少，利用作圖的方式畫出學習樣本在特征空間中的分布或者以列表的形式給出學習樣本數(shù)據(jù)，然后選擇什么分類器進行分類，判別規(guī)則以及判別函數(shù)形式是什么，最后給出測試結(jié)果。（1）選取特征：長

23、寬比、像素比( 長寬比=長/寬, 像素比=物體像素/擬合矩陣像素）獲取特征：將每個學習樣本用photoshop處理得到物體的長、寬、物體的像素、圖片中物體用矩陣擬合的矩形區(qū)域像素。然后再用EXCEL得到長寬比和像素比兩個特征。學習樣本：筆 （第一類）：7個；直尺（第二類）：7個；橡皮（第三類）：7個；學習樣本長寬陰影像素擬合矩陣像素長寬比像素比A111.361.3410506122368.4776 1.16467 A222.262.7535226492188.0945 1.39721 A320.462.0528217336409.9805 1.19219 A418.981.0913986166

24、7817.4128 1.19248 A59.981,.276392101887.8583 1.59387 A617.171.46293323569511.7603 1.21693 A713.271.3332865395019.9774 1.20192 B119.473.4252194535445.6930 1.02587 B213.693.6338532399643.7713 1.03716 B310.321.8527201273005.5784 1.00364 B436.128.42426492437124.3000 1.00438 B56.141.41683469604.3546 1.01

25、844 B612.061.372306042306888.8029 1.00036 B723.746.491207551228323.6579 1.01720 C16.672.8024388243892.3821 1.00004 C217.187.8989061009682.2026 1.02085 C321.3113.262115542271041.6071 1.07350 C412.844.9749616513242.5835 1.03442 C511.477.6268990702001.5052 1.01754 C68.945.1664087659011.7326 1.02831 C71

26、8.1210.361497201516301.7490 1.01276 筆：藍色方形 直尺：紅色星形 橡皮：綠色三角形判別判別函數(shù)：%求均值，注意為列向量X1=mean(A); X2=mean(B); X3=mean(C);%求類內(nèi)離散度矩陣S1、S2、S3S1=zeros(2,2);for i=1:N1 S1=S1+(A(i,1),A(i,2)-X1)*. (A(i,1),A(i,2)-X1 );endS2=zeros(2,2);for i=1:N2 S2=S2+(B(i,1),B(i,2)-X2)*. (B(i,1),B(i,2)-X2 );endS3=zeros(2,2);for i=1

27、:N3 S3=S3+(C(i,1),C(i,2)-X3)*. (C(i,1),C(i,2)-X3 );end%求線性判別函數(shù)加權(quán)向量W和另一參數(shù)w0W12=(inv(S1+S2)*(X1-X2);w012=(W12*X1+W12*X2)/2;W23=(inv(S2+S3)*(X2-X3);w023=(W23*X2+W23*X3)/2;W13=(inv(S1+S3)*(X1-X3);w013=(W13*X1+W13*X3)/2;第1、2類判別函數(shù)：g12(X)=W12*X-w012第1、3類判別函數(shù)：g13(X)=W13*X-w013第2、3類判別函數(shù)：g23(X)=W23*X-w023判別規(guī)則因為采用一對一方式的線性判別函數(shù)即wi/wj兩分法，所以： g12(X)0且g13(X)0，則X屬于第一類； g21(X)0且g23(X)0，則X屬于第二類； g31(X)0且g32(X)0，則X屬于第三類；（3）測試測試樣本長寬陰影像素擬合矩陣像素長寬比像素比筆130.062.89526556986410.4014 1.32683 筆228.641.69389763901816.9467 1.00108 直尺13.653.8138901417963.5827 1.0