模式識(shí)別課程報(bào)告

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

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

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

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

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

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

7、SE有待 改進(jìn)。表3 TAVKM加權(quán)系數(shù)不同對(duì)比加權(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.聽(tīng)000. L,0. 1,0,2rW4甌 A0705.441666710, 96000. L,0. 1,t).孔o(hù). a4S5. 48$05.373299. 143130的財(cái)0. 1,

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

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

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

11、我發(fā)現(xiàn)，與傳統(tǒng)K均值聚類方法 相比，利用基于SPA改進(jìn)的K 均值聚類方法對(duì)含混合地物的土地覆蓋能得到更精 確的劃分。善2 卻境埃ti 遙親條站累Clirlcm? n| inidilnul K -mrarp h勒rMhinttti息UMHEK耳如1響SiCccd1 0B43. 11g7k5i0(iK44|項(xiàng)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)對(duì)于建筑用地、植被稀

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