模式識別結(jié)題論文基于聚類算法和線性判決器的模式分類問題分析

1、基于聚類算法和線性判決器的模式分類問題分析一、模式分類概述一個典型的模式識別系統(tǒng)如圖1所示，由數(shù)據(jù)獲取、預(yù)處理、特征提取、分類決策及分類器設(shè)計五部分組成。一般分為上下兩部分：上部分完成未知類別模式的分類；下半部分屬于分類器設(shè)計的訓(xùn)練過程，利用樣品進(jìn)行訓(xùn)練，確定分類器的具體參數(shù)，完成分類器的設(shè)計。而分類決策在識別過程中起作用，對待識別的樣品進(jìn)行分類決策。數(shù)據(jù)獲取預(yù)處理特征提取分類決策分類結(jié)果未知類別模式的分類圖1 模式識別系統(tǒng)及識別過程訓(xùn)練樣本輸入預(yù)處理特征選擇確定判別函數(shù)改進(jìn)判別函數(shù)分類器設(shè)計誤差檢驗(yàn)?zāi)Ｊ阶R別系統(tǒng)組成單元功能如下：（1）數(shù)據(jù)獲取用計算機(jī)可以運(yùn)算的符號來表示所研究的對象，一般獲取

2、的數(shù)據(jù)類型有一下幾種。二維圖像：文字、指紋、地圖、照片等。一維波形：腦電圖、心電圖、季節(jié)震動波形等。物理參量和邏輯值：體溫、化驗(yàn)數(shù)據(jù)、參量正常與否的描述。（2）預(yù)處理對輸入測量儀器或其他因素所造成的退化現(xiàn)象進(jìn)行復(fù)原、去噪聲，提取有用信息。（3）特征提取和選擇對原始數(shù)據(jù)進(jìn)行變換，得到最能反映分類本質(zhì)的特征。將維數(shù)較高的測量空間（原始數(shù)據(jù)組成的空間）轉(zhuǎn)變?yōu)榫S數(shù)較低的特征空間（分類識別賴以進(jìn)行的空間）。（4）分類決策在特征空間中用模式識別方法把被識別對象歸為某一類別。（5）分類器設(shè)計基本做法是在樣品訓(xùn)練基礎(chǔ)上確定判別函數(shù)，改進(jìn)判別函數(shù)和誤差檢驗(yàn)。二、具體分類方法概述2.1 聚類聚類分析是將數(shù)據(jù)分類到

3、不同的類或者簇的過程，聚類分析是一種探索性的分析，在分類的過程中，人們不必事先給出一個分類的標(biāo)準(zhǔn)，聚類分析能夠從樣本數(shù)據(jù)出發(fā)，自動進(jìn)行分類。從實(shí)際應(yīng)用的角度看，聚類分析是數(shù)據(jù)挖掘的主要任務(wù)之一。而且聚類能夠作為一個獨(dú)立的工具獲得數(shù)據(jù)的分布狀況，觀察每一簇數(shù)據(jù)的特征，集中對特定的聚簇集合作進(jìn)一步地分析。聚類分析還可以作為其他算法（如分類和定性歸納算法）的預(yù)處理步驟。 本課題中主要討論層次聚類和c均值聚類方法。2.1.1 層次聚類在描述基本思想之前，假設(shè) 是將要聚類的l維向量集。層次聚類算法產(chǎn)生一個嵌套聚類的層次。更具體地說，這些算法包含n步，與數(shù)據(jù)向量的數(shù)量一樣多。在第t步，要在前t-1步的聚類

4、基礎(chǔ)上生成新聚類。有兩種不同的算法：合并和分裂層次算法。合并算法中，初始聚類 由n個聚類組成，每個聚類僅包含x中的一個元素。第一步生成聚類 ，它包含n-1個集合，如 。重復(fù)此過程直到產(chǎn)生最后一個聚類 ，它只包含一個單個的聚類集合，即數(shù)據(jù)集x。因而得到聚類的層次為分裂算法與合并算法的思路恰好相反。在這種算法中，初始聚類 僅包括一個集合x。第一步產(chǎn)生聚類 ，它由 個集合組成，如 。重復(fù)此過程直到產(chǎn)生最后一個聚類 ，它包含n個集合，每個集合僅包含x中的一個元素，在這種情況下可得本課題中采用合并算法中的最短距離法。層次聚類算法原理為：n個初始模式樣本自成一類，即建立n類，之后按照以下步驟運(yùn)算：step

5、1：計算各類之間（即各樣本間）的距離，得一個維數(shù)為nn的距離矩陣d(0)?！?”表示初始狀態(tài)。step2：假設(shè)已求得距離矩陣d(n)（n為逐次聚類合并的次數(shù)），找出d(n)中的最小元素，將其對應(yīng)的兩類合并為一類。由此建立新的分類：step3：計算合并后所得到的新類別之間的距離，得d(n+1)。step4：跳至第2步，重復(fù)計算及合并。直到滿足下列條件時即可停止計算：取距離閾值t，當(dāng)d(n)的最小分量超過給定值 t 時，算法停止。所得即為聚類結(jié)果?；虿辉O(shè)閾值t，一直到將全部樣本聚成一類為止，輸出聚類的分級樹。 2.1.2 c均值算法c均值算法首先取定c個類別數(shù)量并對這c個類別數(shù)量選取c個聚類中心，

6、按最小距離原則將各模式分配到c類中的某一類，之后不斷地計算類心和調(diào)整各模式的類別，最終使各模式到其對應(yīng)的判屬類別中心的距離平方之和最小。上述算法也可以先初始化聚類中心，然后再執(zhí)行迭代過程。算法性能依賴于初始聚類中心。2.2 線性判決器在特征空間中，通過學(xué)習(xí)，不同的類別可以得到不同的判別函數(shù)，比較不同類別的判別函數(shù)值大小，就可以進(jìn)行分類。統(tǒng)計模式識別方法把特征空間劃分為決策區(qū)對模式進(jìn)行分類。一個模式類同一個或幾個決策區(qū)相對應(yīng)。每個決策區(qū)對應(yīng)一個判別函數(shù)。對于特征空間中的每個特征向量x,可以計算相應(yīng)于各個決策區(qū)的判別函數(shù)gi(x),i=1,2,c。用判別函數(shù)進(jìn)行分類的方法就是：若對所有的i均有g(shù)i

7、(x)gi(x),則把x分為第j類,記成r(x)=j。本課題中選用最小歐式距離判別準(zhǔn)則設(shè)計線性分類器：； ；判別函數(shù)： ；三、實(shí)驗(yàn)部分3.1 實(shí)驗(yàn)一 區(qū)分圖片中的汽車與背景首先，對樣本進(jìn)行解釋：每個樣本的特征有252個，其中前12個為第四層高頻系數(shù)，中間48個是第三層高頻系數(shù)，后192個是第二層高頻系數(shù)。所以可以考慮從252維特征中選取不同的多個特征，分析其各自的分類效果，進(jìn)行比較。3.1.1 基于線性分類器的仿真結(jié)果利用合適的特征設(shè)計分類器區(qū)分汽車和背景兩類數(shù)據(jù)，并分析結(jié)果。進(jìn)行訓(xùn)練樣本集和測試樣本集的劃分:將所給的n個樣本隨機(jī)的分成兩個子集，每個子集有n/2個樣本。利用其中的一個子集作為訓(xùn)

8、練樣本集設(shè)計分類器，然后用另一個子集進(jìn)行測試，計算錯誤率。隨機(jī)選取多次，求出平均錯誤率，作為性能指標(biāo)。 說明：程序首先調(diào)用自己編寫的randq子程區(qū)分訓(xùn)練樣本和測試樣本，通過得到相關(guān)參數(shù)，設(shè)計最小歐式距離判別器，再用來檢測所有的測試樣本，最后分別得到每次的錯誤率：err_vg（將汽車誤判為背景時的錯判率）；err_gv(將背景誤判為汽車時的錯判率)；由于特定每次得到的錯誤率和數(shù)據(jù)樣本的分布有關(guān)，所以要估計整個分類器的錯誤率，所以本子程設(shè)定循環(huán)抽樣十次分別求取得到不同的單次抽樣率，求得錯誤率的平均值： err_vg（將汽車誤判為背景時的錯判率）；err_gv(將背景誤判為汽車時的錯判率)；此外，

9、本程序設(shè)置了兩個變量：k_s ，k_d 用來靈活的設(shè)定所選擇的特征。k_s標(biāo)識選擇的特征起始標(biāo)號，k_d表示選擇的特征結(jié)束標(biāo)號，通過選定不同的特征，得到不同的錯誤率進(jìn)行比較，得到最有區(qū)分度的特征。結(jié)果分析:通過選定指定的特征，選取10次訓(xùn)練和測試樣本集的不同劃分，求取平均錯誤辨識率，得到平均錯誤率，該錯誤率基本減小了樣本分布的差異。選取不同的k_s, k_d值得到不同的特征選擇，進(jìn)行訓(xùn)練，判別，得到對應(yīng)不同的錯誤率，進(jìn)行比較分析。選取1：252維所有特征時：err_vg = 0.0348； err_gv = 0.0392；選取1：12維所有第四層高頻系數(shù)作為特征時：err_vg = 0.279

10、2； err_gv = 0.1620；選取13：60維所有第三層高頻系數(shù)作為特征時：err_vg = 0.0448； err_gv = 0.0196；選取61：252維所有第二層高頻系數(shù)作為特征時：err_vg = 0.0688； err_gv = 0.0512；選取13：252維所有第二層和第三層高頻系數(shù)作為特征時：err_vg = 0.0316； err_gv = 0.0184；結(jié)論：通過數(shù)據(jù)分析，可以得到：針對最小歐式距離判決準(zhǔn)則的線性分類器，當(dāng)它選取不同的特征進(jìn)行訓(xùn)練，判決時，得到的錯誤率還是有比較大的差別，尤其是僅選取小波變換后得到的第四層系數(shù)時，得到的錯誤率比較大，此后錯誤率大小依

11、次是第二層，第三層。而若將第二層和第三層的特征結(jié)合起來考慮，得到的錯誤率最小，甚至比選取所有維的特征都小。由于我們是隨機(jī)選取的訓(xùn)練樣本和測試樣本，并求取最后的平均錯誤率，所以基本可以得出結(jié)論：在本問題中，若使用基于最小歐式距離的線性判決器，則選取其小波變化后的第三和第二層系數(shù)作為特征，其最終的判決結(jié)果較好。3.1.2 基于層次聚類的仿真結(jié)果程序說明：首先用pdist函數(shù)算出對象兩兩之間的距離，然后利用linkage函數(shù)建立層次化的結(jié)構(gòu)樹。通過比較分類結(jié)果，選擇適合本類樣本特點(diǎn)的類內(nèi)平方距離最小誤差算法。最后調(diào)用cluster函數(shù)，對于結(jié)構(gòu)樹進(jìn)行聚類，確定最終的類別。 結(jié)果分析：通過聚類，得到背

12、景誤判概率（樣本為背景，錯判為其它類）err_bg0.0420；汽車誤判概率（樣本為汽車，錯判為其它類）err_car0.0400；行人誤判概率（樣本為行人，錯判為其它類）err_hm=0.002;其中數(shù)組class_1，class_2，class_3各自存儲著該類數(shù)據(jù)對應(yīng)的樣本在總樣本集中的下標(biāo)值。從中我們可以得到哪些樣本得到了正確的劃分，哪些被錯分到了不同類。比較最遠(yuǎn)距離聚類算法得到的結(jié)果，該種算法得到的結(jié)果是非常好的，錯誤率比較低，最高不超過5。也就是說500個樣本數(shù)據(jù)，僅有25個錯誤數(shù)據(jù)，效果還是不錯的。 總結(jié)：無標(biāo)簽分層聚類算法：因?yàn)槭菬o標(biāo)簽學(xué)習(xí)，所以沒有學(xué)習(xí)訓(xùn)練過程，直接根據(jù)數(shù)據(jù)樣

13、本在所處的特征空間的位置進(jìn)行聚類，所以選用適合樣本分布特點(diǎn)的聚類算法是至關(guān)重要的，它決定了最終的分類效果。3.2 實(shí)驗(yàn)二 根據(jù)身高體重特征區(qū)分男女生用a.txt、b.txt和/或c.txt的數(shù)據(jù)作為本次實(shí)驗(yàn)使用的樣本集，其中存放身高體重數(shù)據(jù)，利用c均值聚類法和層次聚類法對樣本集進(jìn)行聚類分析，對結(jié)果進(jìn)行分析，從而加深對所學(xué)內(nèi)容的理解和感性認(rèn)識。3.2.1 基于c均值方法的仿真結(jié)果 3.2.2 基于層次算法的仿真結(jié)果 通過兩種方法的分類可以看出，在當(dāng)前樣本的情況下，c均值方法100組數(shù)據(jù)分錯五組，錯誤率5%，層次方法100組數(shù)據(jù)分錯6組，錯誤率6%，結(jié)果受樣本選取的影響比較大，再加上樣本選取的范圍

14、比較小，故錯誤率比較高。應(yīng)該再多選取幾組數(shù)據(jù)進(jìn)行試驗(yàn)，這樣才能比較出兩種方法的優(yōu)缺點(diǎn)。四、源程序代碼4.1 實(shí)驗(yàn)一 區(qū)分圖片中的汽車與背景函數(shù)介紹：1 pdist函數(shù) 調(diào)用格式：y=pdist(x,metric)說明：用 metric指定的方法計算 x 數(shù)據(jù)矩陣中對象之間的距離。 x：一個mn的矩陣，它是由m個對象組成的數(shù)據(jù)集，每個對象的大小為n。metric取值如下：euclidean：歐氏距離（默認(rèn)）；seuclidean：標(biāo)準(zhǔn)化歐氏距離；mahalanobis：馬氏距離；cityblock：布洛克距離；minkowski：明可夫斯基距離；2. linkage函數(shù) 調(diào)用格式：z=linka

15、ge(y,method) 輸入值說明：y為pdist函數(shù)返回的m*(m-1)/2個元素的行向量，用method參數(shù)指定的算法計算系統(tǒng)聚類樹。method：可取值如下：single：最短距離法（默認(rèn)）；complete：最長距離法；average：未加權(quán)平均距離法； weighted： 加權(quán)平均法；centroid：質(zhì)心距離法；median：加權(quán)質(zhì)心距離法；ward：內(nèi)平方距離法（最小方差算法）返回值說明：z為一個包含聚類樹信息的（m-1）3的矩陣，其中前兩列為索引標(biāo)識，表示哪兩個序號的樣本可以聚為同一類，第三列為這兩個樣本之間的距離。另外，除了m個樣本以外，對于每次新產(chǎn)生的類，依次用m+1、m

16、+2、來標(biāo)識。為了表示z矩陣，我們可以用更直觀的聚類數(shù)來展示，方法為：dendrogram(z), 產(chǎn)生的聚類數(shù)是一個n型樹，最下邊表示樣本，然后一級一級往上聚類，最終成為最頂端的一類。縱軸高度代表距離列。另外，還可以設(shè)置聚類數(shù)最下端的樣本數(shù)，默認(rèn)為30，可以根據(jù)修改dendrogram(z,n)參數(shù)n來實(shí)現(xiàn)，1n=0.5) if (j250) for a=1:252 test(k,a)=x(i,a); end k=k+1; else for a=1:252 tr(j,a)=x(i,a); end j=j+1; end else if(k250) for a=1:252 tr(j,a)=x(i

17、,a); end j=j+1; else for a=1:252 test(k,a)=x(i,a); end k=k+1; end end endname_tr=tr;name_test=test;設(shè)計線性分類器把汽車和背景兩類數(shù)據(jù)區(qū)分：根據(jù)最小歐式距離判別準(zhǔn)則設(shè)計線性分類器load vehicle;load background;for j=1:10k_s=1;k_d=252;vec_tr(250,252)=0;vec_test(250,252)=0;vec_tr,vec_test=randq(vehicle);randq(background);bg_tr(250,252)=0;bg_te

18、st(250,252)=0;bg_tr,bg_test=randq(background);m_vec=vec_tr(1,k_s:k_d);for i=2:250m_vec=m_vec+(vec_tr(i,k_s:k_d);endm_vec=m_vec/250;m_bg=bg_tr(1,k_s:k_d);for i=2:250m_bg=m_bg+(bg_tr(i,k_s:k_d);endm_bg=m_bg/250;d_vec=(m_vec*m_vec)/2;d_bg=(m_bg*m_bg)/2; 求取分類器對應(yīng)的各參數(shù)flag_vec(250)=0;flag_bg(250)=0;dk_vec=

19、0;dk_bg=0;for i=1:250dk_vec=vec_test(i,k_s:k_d)*m_vec-d_vec; 設(shè)計線性分類器 dk_bg=vec_test(i,k_s:k_d)*m_bg-d_bg; if(dk_vec=dk_bg) flag_vec(i)=1; else flag_vec(i)=0; endends1_vec=sum(flag_vec);for i=1:250 dk_vec=bg_test(i,k_s:k_d)*m_vec-d_vec; dk_bg=bg_test(i,k_s:k_d)*m_bg-d_bg; if(dk_bg=dk_vec) flag_bg(i)=

20、1; else flag_bg(i)=0; endends1_bg=sum(flag_bg);err_vg(j)=(250-s1_vec)/500;err_gv(j)=(250-s1_bg)/500;enderr_vg=0;err_gv=0;for i=1:10 err_vg=err_vg+err_vg(i); err_gv=err_gv+err_gv(i);enderr_vg=err_vg/10err_gv=err_gv/104.1.2 層次聚類程序load feature_table;w=feature_table;dist=pdist(w); 計算兩兩對象之間的距離tree=linkag

21、e(dist,ward); 建立層次化的結(jié)構(gòu)樹（類內(nèi)平方距離最小誤差）class=cluster(tree,3); 聚類class_1=find(class=1); 第一類class_2=find(class=2); 第二類class_3=find(class=3); 第三類n1=size(class_1);n2=size(class_2);n3=size(class_3);a1=0;a2=0;a3=0;for i=1:n1(1) if(1000=class_1(i)1500) a1=a1+1; endendfor i=1:n2(1) if(500=class_2(i)1000) a2=a2+1; endendfor i=1:n3(1) if(0=class_3(i)500) a3=a3+1; endend err_bg=abs