1、武漢理工大學模式識別導論題 目： 模式識別綜述 完 成 人： 師敏 班 級： 1001班 專 業： 電路與系統 學 制： 2.5年 學 號： 模式識別綜述摘要：本文主要介紹了模式識別中常用的模糊k-均值及最小均方誤差兩種算法。介紹了模糊k-均值算法的基本思路及步驟和最小均方誤差驗證可分性及分類算法的原理和方法。并使用MATLAB軟件編寫程序實現了具體的例子，給出了實驗結果并對結果進行了分析。關鍵詞：模糊k-均值 最小均方誤差 可分性0 引言聚類是數據分析中的一項重要技術【1】，是眾多科學領域和工程技術中的一項基礎性工作。聚類分析被廣泛應用于生物學、天體物理學、模式識別、決策支持、數據挖掘、圖像

2、處理、最優化問題等。所謂聚類是把d維特征空間中N個數據點分成k個不同的類，使類內數據點的相似度高、不同類之問的數據點的相似度低【2-5】。這里的相似在特征空間中表現為距離近，所以距離可以用來對2個數據點進行相似性測度。在模糊聚類分析法中，模糊集合相當于模糊類，模式之間的相似性通常用模糊關系、隸屬度來表示。模糊聚類分析的具體方法很多，而且新方法不斷出現，本文討論的是模糊k-均值算法。最小均方誤差（Least Mean Square Error, LMSE）算法的推導利用了梯度概念，它除了對線性可分的模式類收斂外，對線性不可分的情況也可以在算法的迭代過程中明確的表示出來，避免造成空等現象白白浪費時

3、間。這個獨特的性能使這種算法成為設計模式分類器的有用工具。1 模糊k-均值算法 模糊k-均值算法在聚類過程中每次得到的類別邊界仍然是模糊的，每類聚類中心的修改都要用到所有的樣本，此外聚類準則也體現了模糊性。模糊k-均值算法聚類的結果仍然是模糊集合，但是如果實際問題需要一個明確的界限，也可以對結果進行去模糊化，通過一定得規則將模糊聚類轉化為確定性分類。1) 基本思路模糊k-均值算法的基本思路是先設定一些類及每個樣本對各類的隸屬度，然后通過迭代不斷調整隸屬度至收斂。收斂條件是隸屬度的變化量小于規定的閾值。2）實現步驟（1）假定要聚為個類，由人為決定個類中心，為樣本個數。（2）根據先驗知識確定樣本對

4、各模式類的隸屬度，建立初始隸屬度矩陣，其中矩陣的行號為類別編號，列號為樣本編號。表示第個元素對第類的隸屬度。對隸屬度矩陣的第列而言，它表示第個元素分別對各模式類的隸屬度，因此矩陣的每列元素之和等于1。（3）求各類的聚類中心，為迭代次數。 式中參數，是一個控制聚類結果模糊程度的常數，即模糊化指數?？梢钥闯龈骶垲愔行牡挠嬎惚仨氂玫饺康膫€樣本，這是與非模糊k-均值算法的區別之一。在k-均值算法中，某一類的聚類中心只由該類樣本決定，不涉及其他類。（4）計算新的隸屬度矩陣，矩陣元素的計算方法【6】為為每個聚類的中心，是第個樣本對于第類的隸屬度函數。（5）回到第三步，重復至收斂。收斂條件為 其中為規定的

5、參數。當算法收斂時就得到了各類的聚類中心以及表示各樣本對各類隸屬程度的隸屬度矩陣，模糊聚類到此結束。這時準則函數達到最小。當需要給出確定的分類結果時，可以根據隸屬度矩陣，按照隸屬原則進行劃分，即若則 3）實驗分析實例：設有九個一維樣本-5.0,-4.5,-4.1,-3.9,2.5,2.8,3.1,3.9,4.5,取參數，利用模糊k-均值算法把她們聚為兩類。用MATLAB軟件編寫程序如下：clear all%初始化參數值D=-5.0,-4.5,-4.1,-3.9,2.5,2.8,3.1,3.9,4.5 %聚類樣本k=2; %聚類中心數b=2; %模糊化指數J=100;%模糊聚類主程序i,j=si

6、ze(D) %得到數據樣本規格，j為數據個數，i為樣本的維度。 %初始化隸屬度矩陣member=rand(j,k)for ii=1:j %歸一化隸屬度函數矩陣member temp1=0; for iii=1:k temp1=(member(ii,iii)+temp1 end for iiii=1:k scal_member(ii,iiii)=member(ii,iiii)/temp1 endendmember=scal_member %歸一化后的隸屬度矩陣 %計算k個模糊聚類中心的位置ccwhilefor m=1:k sum1=0 sum2=0 for n=1:j sum1=sum1+D(n

7、)*power(member(n,m),b) sum2=sum2+power(member(n,m),b) end cc(m)=sum1/sum2 %計算聚類中心end %更新隸屬度矩陣 for vv=1:j sum4=0 for uu=1:k sum4=sum4+power(1/(D(vv)-cc(uu)2,1/(b-1) end for uv=1:k new_member(vv,uv)=(power(1/(D(vv)-cc(uv)2,1/(b-1)/sum4 endend %計算終止條件指標，以聚類中心隸屬度函數變化率很小為終止目標。index_mat=new_member-members

8、um5=0for num=1:k*j sum5=sum5+(index_mat(num)2endJ=sum5member=new_memberend %輸出聚類結果disp(聚類中心結果為)for num2=1:k disp(cc(num2)enddisp(每個樣本對于每個聚類中心的隸屬度為)member實驗結果如下：聚類中心結果為每個樣本對于每個聚類中心的隸屬度為member = 實驗結果分析：實驗數據為D=-5.0,-4.5,-4.1,-3.9,2.5,2.8,3.1,3.9,4.5，（1）模糊化指數和模式類別數分別為。（2）初始隸屬度矩陣為member = 可知傾向于為一類，為一類。（3

9、）計算聚類中心cc = （4）計算新的隸屬度矩陣new_member =此時，不滿足收斂條件，回到第（3）步繼續迭代運算。得新的聚類中心為。，如此迭代了三次，最終滿足了收斂條件，迭代結束。得到如上的實驗結果。從結果中按照隸屬原則進行劃分得：為一類，為一類。從實驗數據可以看出該分類結果是正確的。2 最小均方誤差（LMSE）驗證可分性及分類算法的設計與實現1）LMSE驗證可分性算法的基本原理LMSE算法【7】是對準則函數引進最小均方誤差這一條件而建立起來的，這種算法的主要特點是在訓練過程中判定訓練集是否線性可分，從而對結果的收斂性做出判斷。LMSE算法把對滿足式的求解改為對滿足的求解，式中是各分量

10、均為正值的矢量，故這兩個公式是互相等價的。LMSE算法的出發點就是選擇一個準則函數，使其達到極小值時，可以得到最小二乘近似解。依據這樣的思路，可將準則函數定義為可以看出，有唯一的極小值0，發生在時。準則函數的值等于與誤差的平方之和，此時，我們的目標是使這個誤差的平方和最小，因此稱這一準則導出的算法為最小均方誤差算法。2）LMSE算法的迭代計算過程 設初始值，需使其的每一分量都為正值，括號中的數字代表迭代次數。 式中，稱為的偽逆，為階長方陣，為階長方陣。在上面的過程中和互相獨立，因此兩者計算的先后次序對計算結果沒有影響。3）模式類別可分性的判別可以證明，當模式類別線性可分，且校正系數滿足時，該算

11、法收斂，可求得解。因為理論上不能證明到底需要迭代多少步才能達到收斂，所以在執行時可以監視出現解的過程，從而判斷是否收斂。通常的方法是每次迭代計算后檢查一下的各分量和誤差向量，從而可以判斷是否收斂。具體分為以下幾種情況： 如果，表明，有解。 如果，表明，隱含著有解。若繼續迭代，可使。 如果，也就是說的所有分量為負數或零，但不全部為零，表明模式類別線性不可分，停止迭代，無解。此時若繼續迭代，數據將不再發生變化，不能再調整。從上面的過程可以清楚地看出，當后，若繼續迭代下去，和都不會再發生變化。因此只有當中有大于零的分量時，才需要繼續迭代，一旦的全部分量只有0和負數，則立即停止。實際上，對一線性不可分

12、模式，要達到全部分量都為非正，需要迭代很多次，往往早在全部分量都達到非正值以前就能看出其中有些分量向正值變化得極慢，這時已能估計出造成線性不可分的某些樣品，及早采取對策【8】。下面以一個實例來說明這種情況。假設有4個訓練樣品，共分為兩類：。顯然它們是線性可分的。用MATLAB軟件編程采用LMSE算法來驗證其可分性。w1=0 0;0 1w2=1 0;1 1x=0 0 1;0 1 1;-1 0 -1;-1 -1 -1xsharp=inv(x*x)*xB=1 1 1 1;c=1;W=xsharp*Be=x*W-Bif e0 for i=1:4 W=W+c*xsharp*abs(e) B=B+c*(e

13、+abs(e) e=x*W-B i=i+1; end if eeps disp(模式類線性可分，解為) disp(W) end if e0 disp(模式類線性不可分，無解) end end實驗結果如下：模式類線性可分，解為實驗結果分析：對所有樣品增1，并對取負后可得樣品矩陣為X的規范逆矩陣為取和得。因為，因而即為所求的解，這時。判別函數為。4）LMSE分類算法原理 LMSE算法以最小均方誤差作為準則，因均方誤差為 因而準則函數為準則函數在時得的最小值。準則函數對的偏導數為帶入迭代方程對于多類問題來說,類問題應該有個權函數方程，對于每一個權函數方程來說，如，則否則5）LMSE分類算法實現【9】

14、設各個權矢量的初值為0，即。輸入第次樣品，計算。若，則，否則。 計算，其中。 循環執行第步，直到屬于類的所有樣品都滿足條件： 下面用一個實例來說明該算法的進行過程。給定兩類樣品：現在用MATLAB軟件編寫程序來實現LMSE算法計算判別函數。function y=lmseclassify(sample) load templet pattern； w=zeros(26,10); flag=1; num=0; num1=0; d= ; m= ; r= ; while flag flag=0; num1=num1+1; for j=1:40 for i=1:10 num=num+1; r=0 0 0

15、 0 0 0 0 0 0 0; r(i)=1; pattern(i).feature(26,j)=1; for k=1:10 m=pattern(i).feature(:,j); d(k)=w(:,k)*m; end for k=1:10 if k=i if d(i)200 flag=0; end end sample(26)=1; b=; for k=1:10 h(k)=w(:,k)*sample; end maxval,maxpos=max(h);y=maxpos-1;實驗結果如下：實驗結果分析：在進行迭代運算之前，各樣品的特征向量經過增1：取。LMSE算法判別函數實現步驟如下： 令，因此

16、 ,因此 ，因此 ，因此 因此經過19次迭代后，得到可以滿足要求的結果為 因此判別函數為：參考文獻：【1】 蘇瑞.基于層次的模糊K均值聚類算法研究J.安陽師范學院學報,2010,(02).【2】 Domany E. Superparamagnetic C1ustering of DataThe Definitive Solution of an Posed ProblemJPhysica A，1999，(263)：158169【3】 Blatt M，Wiseman S，Domany ESuperparamagnetic Clustering of DataJPhysical Review Letters，1996，(76)：3 2513 255【4】 Blmt M，Wiseman S，Domany EC1ustering Data through an Analogy to the Potts ModelAAdvances in Neural Infor