模式識別課程報告

1、模式識別實驗報告學(xué)生姓名：班學(xué)號：指導(dǎo)老師：機械與電子信息學(xué)院2014年6月基于K-means算法的改進算法方法一：層次K均值聚類算法在聚類之前，傳統(tǒng)的K均值算法需要指定聚類的樣本數(shù)，由于樣本初始分布 不一致，有的聚類樣本可能含有很多數(shù)據(jù)，但數(shù)據(jù)分布相對集中，而有的樣本集卻 含有較少數(shù)據(jù)，但數(shù)據(jù)分布相對分散。因此，即使是根據(jù)樣本數(shù)目選擇聚類個數(shù)， 依然可能導(dǎo)致聚類結(jié)果中同一類樣本差異過大或者不同類樣本差異過小的問題，無 法得到滿意的聚類結(jié)果。結(jié)合空間中的層次結(jié)構(gòu)而提出的一種改進的層次K均值聚 類算法。該方法通過初步聚類，判斷是否達到理想結(jié)果，從而決定是否繼續(xù)進行更 細層次的聚類，如此迭代執(zhí)行，

2、生成一棵層次型K均值聚類樹，在該樹形結(jié)構(gòu)上可 以自動地選擇聚類的個數(shù)。標準數(shù)據(jù)集上的實驗結(jié)果表明，與傳統(tǒng)的K均值聚類方 法相比，提出的改進的層次聚類方法的確能夠取得較優(yōu)秀的聚類效果。設(shè)X = x1，x2，xi，xn 為n個Rd空間的數(shù)據(jù)。改進的層次結(jié)構(gòu) 的K均值聚類方法(Hierarchical K means)通過動態(tài)地判斷樣本集X當前聚類是 否合適，從而決定是否進行下一更細層次上的聚類，這樣得到的最終聚類個數(shù)一定 可以保證聚類測度函數(shù)保持一個較小的值。具體的基于層次結(jié)構(gòu)的K均值算法：步驟1選擇包含n個數(shù)據(jù)對象的樣本集X = xl, x2,，xi,，xn，設(shè) 定初始聚類個數(shù)k1，初始化聚類目

3、標函數(shù)J （0） =0.01，聚類迭代次數(shù)t初始化為 1，首先隨機選擇k1個聚類中心。步驟2衡量每個樣本xi （i = 1，2，n）與每個類中心 （ j = 1， 2,，k）之間的距離，并將xi歸為與其最相似的類中心所屬的類，并計算當前聚 類后的類測度函數(shù)值J （1）。步驟3進行更細層次的聚類，具體步驟如下：步驟3. 1根據(jù)式（5）選擇類半徑最大的類及其類心ci : ri = max |xj - ci|， j = 1，2，ni 且 xj 屬于 Xj（5）步驟3.2根據(jù)距離公式（1）選擇該類中距離類ci最遠的樣本點xi1，然后 選擇該類中距離xi1最遠的樣本點xi2。步驟3.3以這兩個點和其他聚

4、類中心作為初始聚類中心重新做k均值聚類。步驟4設(shè)e = J （t） - J （t - 1）/J （t - 1），若e ，則返回步驟3 繼續(xù)迭代執(zhí)行；否則算法結(jié)束，輸出聚類結(jié)果X ?X1，X2，Xk。實驗結(jié)果及分析文中作者為比較層次K均值聚類算法中類個數(shù)選擇方法與傳統(tǒng)基于隨機選擇 聚類個數(shù)的K均值算法的有效性，在四個標準數(shù)據(jù)集上（見表1）進行了實驗，并 與傳統(tǒng)的經(jīng)典隨機選擇初始聚類中心的K-means方法作了比較。表I實弱數(shù)據(jù)集數(shù)據(jù)集訓(xùn)練集個數(shù)數(shù)據(jù)維數(shù)ASL25022Banana5 5002Breast _ca.ncer2 0009Spambase1 73157由圖1可以看出，采用傳統(tǒng)的K均值聚

5、類方法，數(shù)據(jù)集ASL在聚類達到25類 后，聚類衡量函數(shù)值的減小變得平緩，因此，該數(shù)據(jù)集聚為25類是比較合適的同 理，對于數(shù)據(jù)集Banana、Breast_cancer、Spambase來說，最佳聚類個數(shù)分別為 20、25、30。由于采用傳統(tǒng)K均值聚類方法開始無法得到最優(yōu)的聚類個數(shù)，但 是，采用本文提出的方法可以自動地獲取聚類的個數(shù)，最終在四個數(shù)據(jù)集上到的聚 類個數(shù)分別為28、22、24、31，與傳統(tǒng)K均值方法多次實驗比較得到的最優(yōu)聚類個數(shù)是一致的。0.80,1!11ASL -k），聚類中心初始化完畢轉(zhuǎn)到步驟；（選擇其他聚類中心）利用公式（5）找到最小點xi為新的聚類中心， q=q+1，轉(zhuǎn)到步驟

6、；K-Mean聚類）利用已經(jīng)獲得聚類中心m1， m2，mk，進行K-Means 聚類。實驗結(jié)果及分析為了證明DWKM算法有效性，作者對K-Means和DWKM算法做對比實驗對K- Means聚類算法和DWKM算法的結(jié)果，可以看出DWKM算法不僅很好地解決了 K- Means的隨機性，而且從總體精度Pc和運行時間上看，降低了錯誤率，提高了算 法的效率。為了證明加權(quán)對聚類結(jié)果的影響，分別取不同的加權(quán)系數(shù)，通過測試數(shù) 據(jù)Iris，說明加權(quán)能夠得到更好的聚類結(jié)果。從表可以看出，通過加權(quán)系數(shù)可以得到比較好的聚類結(jié)果，并且從MSE 上可 以出，當MSE小的時候其總分類精度Pc不是最優(yōu)解，因此算法準則函數(shù)M

7、SE有待 改進。表3 TAVKM加權(quán)系數(shù)不同對比加權(quán)系致垃代次數(shù)聚禿間 距離i聚髡內(nèi)部距禺1 S1.0,1.s1. fl278. P4O85 7H2132600. SS67o L。一 LU.2rU. 65B5.391 I5.4W499 25030. % 670. 1 ,0. 1,2r(L 14B5.39115.409499. 25030.0. 1.0. 1,0.2rI. 8586. 30705.44166幻】0.聽000. L,0. 1,0,2rW4甌 A0705.441666710, 96000. L,0. 1,t).孔o. a4S5. 48$05.373299. 143130的財0. 1,

8、0. 1 r().3r.s485. 4KS05. J782yg. 20. %(110. 1.0. 1,0,c. 52財.13015.4637就 73640.9533方法三：基于集對分析的遙感圖像K 一均值聚類算法基于歐式距離的K 均值聚類算法是一種硬分類(把每個待辨識的對象嚴格 地劃分到某個類中)方法，面對具有不確定性和混合像元特征的遙感圖像數(shù)據(jù)，傳 統(tǒng)K 一均值聚類算法很難得到滿意的分類結(jié)果。為解決這一難題，將集對分析 (set pair analysis， SPA)理論推廣到遙感圖像聚類算法，通過引入一個能統(tǒng)一 描述同一性、差異性和對立性的同異反(identical discrepancy

9、 contrary， IDC) 聯(lián)系度，提出了基于IDC聯(lián)系度的改進的K 均值聚類算法。該方法克服了傳統(tǒng)K 一均值算法硬分類的缺陷，可以有效地提高遙感圖像聚類精度。對Landsat5 TM衛(wèi) 星數(shù)據(jù)的聚類分析實驗表明，在含有混合像元的遙感圖像地物覆蓋分類中，改進的 K均值聚類方法的分類效果要優(yōu)于傳統(tǒng)K 均值聚類方法。該算法的具體實現(xiàn)步驟如下：設(shè)定輸入數(shù)據(jù)集X = ( x1，x2，x n，聚類簇個數(shù)K，差異度系數(shù)i， 最大循環(huán)次數(shù)I；輸出為滿足“誤差平方和最小”標準的K個聚類Ck。1，步驟一初始化。令1=1,隨機選取K個初始類簇中心mk (1), k =2,K；步驟二 計算IDC聯(lián)系度。計算待分

10、類樣本xl與聚類中心mk的IDC聯(lián)系度 ulk；步驟三 分配xl。計算樣本點xl與這K個簇中心之間的IDC距離Dlk，如果 滿足 Dlk = min ( Dlk, k = 1,2，K ，則 xleCk；步驟四 修正簇中心Ck。令I(lǐng)=I + 1,重新分配K個新的聚類中心，即叫)=十M叫=1注，m k = 2步驟五計算誤差平方和J,即J-1 (8)jfc M 1 J Cg.步驟六收斂判斷。如果J值收斂，則返回mk( I) , k = 1,2，K;算法 結(jié)束；否則，返回步驟二。實驗結(jié)果及分析為了評價改進算法的聚類性能，選取一景多光譜遙感圖像作為實驗數(shù)據(jù)，并 與傳統(tǒng)K 均值算法進行比較。通過作者的對比

11、我發(fā)現(xiàn)，與傳統(tǒng)K均值聚類方法 相比，利用基于SPA改進的K 均值聚類方法對含混合地物的土地覆蓋能得到更精 確的劃分。善2 卻境埃ti 遙親條站累Clirlcm? n| inidilnul K -mrarp h勒rMhinttti息UMHEK耳如1響SiCccd1 0B43. 11g7k5i0(iK44|項1Dl75lii. WtWTtIIKKA2. H企g7.71iw1a2.v4. hitt*o424a.1：MS5. nnt10732?3.HHlVIfiE 旬III?131 151辟1 E1 M221911 g4. ,驟1別MM2.44.Mfl.Z2 4根據(jù)表2及表3,發(fā)現(xiàn)對于建筑用地、植被稀

12、疏地、草地和林地的錯分、漏 分誤差，基于SPA的改進算法要低于傳統(tǒng)K 均值算法；對于總體分類精度和 Kappa系數(shù)，基于SPA的改進算法明顯高于傳統(tǒng)K均值算法。改進的K 均值聚類方法利用同異反（IDC）聯(lián)系度來度量樣本間的相似性， 嘗試解決傳統(tǒng)K 均值算法在含有混合像元的遙感圖像地物覆蓋分類中由硬分類 造成分類精度不高的問題。實驗結(jié)果顯示，在傳統(tǒng)K均值聚類算法面對具復(fù)雜特 征的遙感圖像數(shù)據(jù)無法獲得較好聚類效果時，基于SPA改進的K均值聚類算法仍 然能夠獲得較好的聚類效果。參考文獻【1】胡偉，改進的層次K均值聚類算法，計算機工程與應(yīng)用，2011-10-24【2】萬廣通；王行風(fēng)，基于密度的加權(quán)K-Means算法，測繪科學(xué)，2013-07- 20【3】謝相建；趙俊三；陳學(xué)輝，袁思，基于集對分析的遙感圖像K 均值聚 類算法，國土資源遙感，2012-12-15【4】王曉丹，高曉峰，姚旭等，SVM集成研究與應(yīng)用J,空軍工程 大學(xué)學(xué)報：自然科學(xué)版，2012-2-13【5】武佳薇，李雄飛，孫濤等，鄰域平衡密度聚類算法J,計算機研究與 發(fā)展，2010心得體會學(xué)習(xí)了模式識別這門課程，我學(xué)會了利用Matlab軟件對遙感圖像進行簡單的 處理，可為遙感影像的判讀提供良好的條件，從而提高判讀精度，還學(xué)會了使用軟 件ENVI，對遙感圖像進行數(shù)據(jù)處理、圖像分類等