模式識(shí)別大作業(yè)

1、 模式識(shí)別導(dǎo)論大作業(yè)（2014-2015第一學(xué)期）南京航空航天大學(xué)2014年10月22日基于核的聯(lián)想記憶及聚類算法的研究與應(yīng)用南京航空航天大學(xué) PAGE 4 - PAGE 17 -K均值聚類（20分）功能描述： 將給定文件里的數(shù)據(jù)樣本按照k均值聚類的思想分為3類，將第一、二、三類的數(shù)據(jù)編號(hào)分別輸出并統(tǒng)計(jì)各類別模式向量的總個(gè)數(shù)。K均值聚類通過(guò)不斷調(diào)整類心和各模式的類別，最終使各模式到類心距離平方和最小，故此聚類算法將數(shù)據(jù)非常有效地進(jìn)行了劃分。源代碼#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中樣本個(gè)數(shù)int aSIZE = 0 , bSIZE = 0 , cSIZE = 0 ;double sum1 = 0, sum2 = 0, sum3 = 0;/以二維數(shù)組表示向量，arrayi是第i個(gè)樣本，center64存放第k次和第k+1次初始聚類中心double arrSIZE4, center64 = 0 ;if (fp = fopen(Iris.txt

3、, r) = NULL)/打開(kāi)文件操作printf(cannot open filen);exit(0);for (i = 0; i SIZE; i+)/為數(shù)組賦值，共150個(gè)向量for (j = 0; j 4; j+)fscanf(fp, %lf, &arrij);fclose(fp);/關(guān)閉文件for (i = 0; i 3; i+)/為center64賦初值，將總體前三個(gè)向量作為初始聚類中心。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次放進(jìn)/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用于計(jì)算歐氏距離sum2 += pow(arrij - center1j, 2);sum3 += pow(arrij - center2j, 2);if (sum1 sum2 &sum1sum3)/按距離

5、來(lái)為樣本點(diǎn)分類at = i;t+;for (x = 0; x4; x+)center3x += arrix;/將某一聚類中樣本的和全加起來(lái)，/注意向量各項(xiàng)都要累加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+)/求出新聚類中心放進(jìn)center后三行center3i = center3i / t;/tpq分別是類別123

6、中樣本的個(gè)數(shù)center4i = center4i / p;center5i = center5i / q; while (!fx(center);printf(類別1中的數(shù)據(jù)共計(jì)%d個(gè)，編號(hào)為：n, t);/輸出結(jié)果for (i = 0; i t; i+)printf(%d , ai + 1);printf(n類別2中的數(shù)據(jù)共計(jì)%d個(gè)，編號(hào)為：n, p);for (i = 0; i p; i+)printf(%d , bi + 1);printf(n類別3中的數(shù)據(jù)共計(jì)%d個(gè)，編號(hào)為：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ù)全部格式化寫(xiě)到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屬于第三類；在測(cè)試集上的測(cè)試結(jié)果（給出圖示，正確分類的樣本點(diǎn)與錯(cuò)誤分類的樣本點(diǎn)用不同標(biāo)志標(biāo)出，給出正確率）訓(xùn)練集：第1類

9、正確率:92.31%第2類正確率100%第3類正確率:100%三、貝葉斯決策（20分）選取的訓(xùn)練集與測(cè)試集（訓(xùn)練集大概是整體樣本的2/3）第一類第二類第三類總計(jì)訓(xùn)練集26413490測(cè)試集13201660總計(jì)396150150訓(xùn)練集：（樣本編號(hào)-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個(gè)第二類：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個(gè)第三類：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個(gè)測(cè)試集：（樣本編號(hào)1-150）第一類：133 135 136 137 138 140 141 142144 145 146 148 149，共13個(gè)第二類：52 54 55 56 57 58 59 60 61 62 63 64 65

11、66 67 68 69 70 71 72，共20個(gè)第三類：35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 ，共16個(gè)隨機(jī)選取的2維是：第1、2個(gè)特征；第一類：藍(lán)色方形 第二類：紅色星形 第三類：綠色三角形判別函數(shù)與判別規(guī)則（計(jì)算各個(gè)類別的基本參數(shù)，根據(jù)參數(shù)寫(xiě)出判別函數(shù)）（1）判別函數(shù)：%求均值，注意為列向量M1=mean(A);M2=mean(B);M3=mean(C);%p1,p2,p3分別為先驗(yàn)概率；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屬于第三類；在測(cè)試集上的測(cè)試結(jié)果（給出圖示，正確分類的樣本點(diǎn)與錯(cuò)誤分類的樣本點(diǎn)用不同標(biāo)志標(biāo)出，給出正確率）正確分類樣本顏色：方形 錯(cuò)誤分類樣本顏色：星形訓(xùn)練集：第1類正確率:84.62%第2類正確率75%第3類正確率:93.75%實(shí)驗(yàn)結(jié)果分析 出錯(cuò)原因：樣本的分布具有統(tǒng)計(jì)特性，特征向量不是一個(gè)確定的向量，是隨機(jī)向量，所以只能根據(jù)樣本數(shù)與某一類的可能性大小來(lái)決策它是否屬于某類，故可能出錯(cuò)； 算法優(yōu)點(diǎn)： 貝葉斯決策能對(duì)信息的價(jià)值或是否需要采集新的信息作出科學(xué)的判斷； 它能對(duì)調(diào)查結(jié)果的可能性加以數(shù)量化的評(píng)價(jià)，而不是像一般的決策方法那樣，對(duì)調(diào)查結(jié)果或者是完全相信，或者是完全不

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

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

18、3分別為先驗(yàn)概率；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屬于第三類；在測(cè)試集上的測(cè)試結(jié)果（給出圖示，正確分類的樣本點(diǎn)與錯(cuò)誤分類的樣本點(diǎn)用不同標(biāo)志標(biāo)出，給出正確率）正確分類樣本顏色：方形 錯(cuò)誤分類樣本顏色：星形訓(xùn)練集：第1類正確率:92.31%第2類正確率100%第3類正確率:100%實(shí)驗(yàn)結(jié)果分析正確率第一類第二類第三類貝葉斯決策84.62%75%93.75%K-L加貝葉斯決策92.31%100%100%K-L變換優(yōu)點(diǎn)：去相關(guān)性好，是均方誤差意義下的最佳變換，它在數(shù)據(jù)壓縮技術(shù)中占有重要地位。由表中很

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

23、寬比、像素比( 長(zhǎng)寬比=長(zhǎng)/寬, 像素比=物體像素/擬合矩陣像素）獲取特征：將每個(gè)學(xué)習(xí)樣本用photoshop處理得到物體的長(zhǎng)、寬、物體的像素、圖片中物體用矩陣擬合的矩形區(qū)域像素。然后再用EXCEL得到長(zhǎng)寬比和像素比兩個(gè)特征。學(xué)習(xí)樣本：筆 （第一類）：7個(gè)；直尺（第二類）：7個(gè)；橡皮（第三類）：7個(gè)；學(xué)習(xí)樣本長(zhǎng)寬陰影像素?cái)M合矩陣像素長(zhǎng)寬比像素比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 筆：藍(lán)色方形 直尺：紅色星形 橡皮：綠色三角形判別判別函數(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ī)則因?yàn)椴捎靡粚?duì)一方式的線性判別函數(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）測(cè)試測(cè)試樣本長(zhǎng)寬陰影像素?cái)M合矩陣像素長(zhǎng)寬比像素比筆130.062.89526556986410.4014 1.32683 筆228.641.69389763901816.9467 1.00108 直尺13.653.8138901417963.5827 1.0