系統(tǒng)聚類分析課程設(shè)計

1、<p><b>　　《空間分析》</b></p><p>　　系統(tǒng)聚類算法及編程實現(xiàn) </p><p>　　學(xué)院：地質(zhì)工程與測繪學(xué)院 </p><p>　　專業(yè)：遙感科學(xué)與技術(shù)</p><p><b>　　班級： </b></p><p><b>　　學(xué)號

2、：</b></p><p><b>　　學(xué)生姓名：</b></p><p><b>　　指導(dǎo)老師： </b></p><p><b>　　目錄</b></p><p>　　第1章 前言……………………………………………………3</p><p>

3、;　　第2章 算法設(shè)計背景…………………………………………3</p><p>　　2.1 聚類要素的數(shù)據(jù)處理………………………………3</p><p>　　距離的計算…………………………………………5</p><p>　　第3章 算法思想與編程實現(xiàn)…………………………………5</p><p>　　3.1 算法思想……………………………………

4、…………5</p><p>　　3.2 用Matlab編程實現(xiàn)……………………………………7</p><p>　　3.2.1 程序代碼…………………………………………7</p><p>　　3.2.2 編程操作結(jié)果…………………………………12</p><p>　　第4章 K-均值算法應(yīng)用與優(yōu)缺點…………………………13</p>

5、<p>　　4.1 K-均值聚類法的應(yīng)用………………………………13</p><p>　　4.2 K-均值聚類法的優(yōu)缺點……………………………14第5章 課程設(shè)計總結(jié)………………………………………14</p><p>　　主要參考文獻(xiàn)………………………………………………15</p><p><b>　　前言</b></p&

6、gt;<p>　　本課題是根據(jù)**老師所教授的《空間分析》課程內(nèi)容及要求而選定的，是對于系統(tǒng)聚類算法的分析研究及利用相關(guān)軟件的編程而實現(xiàn)系統(tǒng)聚類。研究的是系統(tǒng)聚類算法的分析及編程實現(xiàn)，空間聚類的目的是對空間物體的集群性進(jìn)行分析，將其分為幾個不同的子群（類）。子群的形成的是地理系統(tǒng)運作的結(jié)果，根據(jù)此可以揭示某種地理機(jī)制。此外，子群可以作為其它分析的基礎(chǔ)，例如，公共設(shè)施的建立一般地說是根據(jù)居民點群的分布，而不是具體的居民住宅的

7、分布來布置的，因此需要對居民點群進(jìn)行聚類分析以形成若干居民點子群，這樣便于簡化問題，突出重點。</p><p>　　空間聚類可以采用不同的算法過程。在分析之初假定n個點自成一類，然后逐步合并，這樣在聚類的過程中，分類將越來越少，直至聚至一個適當(dāng)?shù)姆诸悢?shù)目，這一聚類過程稱之為系統(tǒng)聚類。 常見的聚類分析方法有系統(tǒng)聚類法、動態(tài)聚類法和模糊聚類法等。下面主要介紹系統(tǒng)聚類算法，并基于Matlab軟件用K-means算法(即

8、k-均值算法)來實現(xiàn)系統(tǒng)聚類的算法編程。</p><p>　　第二章 算法設(shè)計背景</p><p>　　2.1聚類要素的數(shù)據(jù)處理</p><p>　　假設(shè)有m 個聚類的對象，每一個聚類對象都有 個要素構(gòu)成。它們所對應(yīng)的要素數(shù)據(jù)可用 表3.4.1給出。 在聚類分析中，常用的聚類要素的數(shù)據(jù)處理方法有如下幾種。</p><p><b>

9、　?、倏偤蜆?biāo)準(zhǔn)化</b></p><p>　?、?標(biāo)準(zhǔn)差標(biāo)準(zhǔn)化    </p><p>　　③ 極大值標(biāo)準(zhǔn)化經(jīng)過這種標(biāo)準(zhǔn)化所得的新數(shù)據(jù)，各要素的極大值為1，其余各數(shù)值小于1。</p><p>　?、?極差的標(biāo)準(zhǔn)化經(jīng)過這種標(biāo)準(zhǔn)化所得的新數(shù)據(jù)，各要素的極大值為1，極小值為0，其余的數(shù)值均在0與1之間。</p&g

10、t;<p>　　2.2距離的計算 距離是事物之間差異性的測度，差異性越大，則相似性越小，所以距離是系統(tǒng)聚類分析的依據(jù)和基礎(chǔ)。</p><p>　　選擇不同的距離，聚類結(jié)果會有所差異。在地理分區(qū)和分類研究中，往往采用幾種距離進(jìn)行計算、對比，選擇一種較為合適的距離進(jìn)行聚類。</p><p>　　第三章 算法思想與編程實現(xiàn)</p><p><b&

11、gt;　　3.1算法思想</b></p><p>　　我們已經(jīng)指出系統(tǒng)聚類方法首先將n個空間點看做是n個子群，然后根據(jù)所選用的聚類統(tǒng)計量來計算n個子群之間的關(guān)系。對于距離，計算n個子群兩兩之間的距離，首先選擇距離最近的兩個子群（點）歸為一個新的子群，這樣就得到n-1個子群兩兩之間的聚類統(tǒng)計量，繼續(xù)選擇距離最近的子群合并，再得到n-2個子群……，依此類推，直到所有的子群全部合并。</p>

12、<p>　　K-means算法是硬聚類算法，是典型的局域原型的目標(biāo)函數(shù)聚類方法的代表，它是數(shù)據(jù)點到原型的某種距離作為優(yōu)化的目標(biāo)函數(shù)，利用函數(shù)求極值的方法得到迭代運算的調(diào)整規(guī)則。K-means算法以歐式距離作為相似度測度，它是求對應(yīng)某一初始聚類中心向量V最有分類，使得評價指標(biāo)J最小。算法采用誤差平方和準(zhǔn)則函數(shù)作為聚類準(zhǔn)則函數(shù)。</p><p>　　K-均值算法的聚類準(zhǔn)則是使每一聚類中，多模式點到該類別的中

13、心的距離的平方和最小。其基本思想是：通過迭代，主次移動各類的中心，直到得到最好的 聚類為止。其算法框圖如圖所示。</p><p>　　具體的計算步驟如下：假設(shè)圖像上的目標(biāo)要分為m類，m為已知數(shù)。</p><p>　　第一步：適當(dāng)?shù)剡x取m個類的初始中心Z1(1),Z2(1),···，ZM(1)，初始中心的選擇對聚類結(jié)果有一定的影響，初始中心的選擇一般有如下幾種方

14、法：</p><p>　　根據(jù)問題的性質(zhì)和經(jīng)驗確定類別數(shù)m，從數(shù)據(jù)中找出直觀上看來比較適合的m個類的初始中心。</p><p>　　將全部數(shù)據(jù)隨即地分為m個類型，計算每類的重心，將這些重心作為m個類的初始中心。</p><p>　　第二步：在第k次迭代中，對任一樣本X按如下的方法把它調(diào)整到m個類別中的某一類別中去。對于所有的i ≠ j, i = 1,2,·

15、··，m, 如果∥X-Zj(k)∥﹤∥X-Zi(k)∥，則X∈Sj(k)其中Sj(k)是以Zi(k)為中心的類。</p><p>　　第三步：由第二步得到Sj(k)類新的中心</p><p>　　Zj(k),Zj(k)=</p><p>　　式中，Nj為Sj(k)類中的樣本數(shù)。Zj(k+1)是按照使J最小的原則確定的，J的表達(dá)式為：</p&

16、gt;<p><b>　　J=</b></p><p>　　第四步：對于所有的i=1,2···，m，如果Zi(k+1)=Zi(k),則迭代結(jié)束，否則轉(zhuǎn)到第二步繼續(xù)迭代。</p><p>　　這種算法的結(jié)果受到所選聚類中心的數(shù)目和其初始位置以及模式分布的幾何性質(zhì)和讀入次序等因素的影響，并且在迭代過程中又沒有調(diào)整類數(shù)的措施，因此

17、可能產(chǎn)生不同的初始分類得到不同的結(jié)果，這是這種方法的缺點?？梢酝ㄟ^其他的簡單的聚類中心試探方法，如最大距離法，找出初始中心，提高分類效果。</p><p>　　3.2用 Matlab 編程實現(xiàn)</p><p><b>　　3.2.1程序代碼</b></p><p>　　對于上述的K-mean算法用Matlab軟件實現(xiàn)編程并調(diào)用數(shù)據(jù)小的圖片進(jìn)行聚

18、類分析及編程是否正確性的檢測。</p><p><b>　　具體程序代碼如下：</b></p><p><b>　　%%讀取圖片</b></p><p>　　Imag = imread('hand.jpg'); %%只能讀取三個波段</p><p>　　sample =

19、 rgb2gray(Imag); %%將彩色圖片轉(zhuǎn)換為灰度圖片</p><p>　　[m n] = size(sample); %%讀取圖片的維數(shù)</p><p>　　sample = reshape(sample,m*n,1); %%將矩陣變換為m*n行1列的向量</p><p>　　k = 4;

20、 %%分成4類</p><p>　　t = 0; %%控制循環(huán)次數(shù)</p><p>　　flag = 0; %%一個和sample等維數(shù)的標(biāo)記向量</p><p>　　ocentre1 = 80; %%選取第1類聚類中心</p><p>　　ocentre2 = 160;

21、 %%選取第2類聚類中心</p><p>　　ocentre3 = 220; %%選取第3類聚類中心</p><p>　　ocentre4 = 255; %%選取第4類聚類中心</p><p>　　sample = double(sample); %%將uint8類型轉(zhuǎn)換為double型</p><p

22、>　　while t == 0</p><p>　　%fsample1 = 0;</p><p>　　%fsample2 = 0;</p><p>　　%fsample3 = 0;</p><p>　　%fsample4 = 0;</p><p>　　fsample = zeros(4,1);</p>

23、<p>　　num = zeros(4,1);</p><p>　　dis = zeros(1,4);</p><p>　　for i = 1:m*n</p><p>　　%a = 5 - 2;</p><p>　　%b = 2 - 5;</p><p>　　dis(1) = abs(sample(i)

24、- ocentre1); %%求到第1個聚類中心距離</p><p>　　dis(2) = abs(sample(i) - ocentre2); %%求到第2個聚類中心距離</p><p>　　dis(3) = abs(sample(i) - ocentre3); %%求到第3個聚類中心距離</p><p>　　dis(4) = abs(sample(i

25、) - ocentre4); %%求到第4個聚類中心距離</p><p>　　mindis = min([dis(1) dis(2) dis(3) dis(4)]); %%求最小的距離</p><p>　　%選取最小值，第一個值給dis1，第二個值給dis2，判斷dis2<dis1，則給dis2值于dis1，計算第三個距離給dis2，返回第三步，循環(huán)</p>&

26、lt;p>　　switch mindis</p><p>　　case dis(1)</p><p>　　%flag = cat(1,flag,1); %%將標(biāo)記數(shù)組賦值1，該點屬于第1類</p><p>　　%fsample1 = cat(1,fsample1,sample(i));</p><p>　　flag(i) = 1;&

27、lt;/p><p>　　fsample(1) = fsample(1) + sample(i);</p><p>　　num(1) = num(1) + 1;</p><p>　　case dis(2)</p><p>　　%flag = cat(1,flag,2); %%將標(biāo)記數(shù)組賦值2，該點屬于第2類</p><p&g

28、t;　　%fsample2 = cat(1,fsample2,sample(i));</p><p>　　flag(i) = 2;</p><p>　　fsample(2) = fsample(2) + sample(i);</p><p>　　num(2) = num(2) + 1;</p><p>　　case dis(3)</p&

29、gt;<p>　　%flag = cat(1,flag,3); %%將標(biāo)記數(shù)組賦值3，該點屬于第3類</p><p>　　%fsample3 = cat(1,fsample3,sample(i));</p><p>　　flag(i) = 3;</p><p>　　fsample(3) = fsample(3) + sample(i);</p

30、><p>　　num(3) = num(3) + 1;</p><p>　　case dis(4)</p><p>　　%flag = cat(1,flag,4); %%將標(biāo)記數(shù)組賦值4，該點屬于第4類</p><p>　　%fsample4 = cat(1,fsample4,sample(i));</p><p>　

31、　flag(i) = 4;</p><p>　　fsample(4) = fsample(4) + sample(i);</p><p>　　num(4) = num(4) + 1;</p><p><b>　　end</b></p><p><b>　　end</b></p><

32、;p>　　%%重新計算聚類中心</p><p>　　%[m1 n1] = size(fsample1);</p><p>　　%[m2 n2] = size(fsample2);</p><p>　　%[m3 n3] = size(fsample3);</p><p>　　%[m4 n4] = size(fsample4);</p

33、><p>　　%ncentre1 = sum(fsample1)/(m1 - 1);</p><p>　　%ncentre2 = sum(fsample2)/(m2 - 1);</p><p>　　%ncentre3 = sum(fsample3)/(m3 - 1);</p><p>　　%ncentre4 = sum(fsample4)/(m4

34、 - 1);</p><p><b>　　%flag</b></p><p><b>　　%fsample</b></p><p>　　ncentre1 = fsample(1)/num(1);</p><p>　　ncentre2 = fsample(2)/num(2);</p>&

35、lt;p>　　ncentre3 = fsample(3)/num(3);</p><p>　　ncentre4 = fsample(4)/num(4);</p><p>　　%flag(1) = [];</p><p>　　if ncentre1 == ocentre1 && ncentre2 == ocentre2...</p>

36、<p>　　&& ncentre3 == ocentre3 && ncentre4 == ocentre4</p><p>　　for i = 1:m*n</p><p>　　switch flag(i)</p><p><b>　　case 1</b></p><p>　　s

37、ample(i) = 60;</p><p><b>　　case 2</b></p><p>　　sample(i) = 120;</p><p><b>　　case 3</b></p><p>　　sample(i) = 180;</p><p><b>　　

38、case 4</b></p><p>　　sample(i) = 240;</p><p><b>　　end</b></p><p><b>　　end</b></p><p><b>　　t = 1;</b></p><p><b&

39、gt;　　else</b></p><p>　　ocentre1 = ncentre1;</p><p>　　ocentre2 = ncentre2;</p><p>　　ocentre3 = ncentre3;</p><p>　　ocentre4 = ncentre4;</p><p><b>

40、;　　end</b></p><p><b>　　end</b></p><p>　　sample = uint8(sample);</p><p>　　sample = reshape(sample,m,n);</p><p>　　imshow(sample);</p><p>　　

41、3.2.2編程操作結(jié)果</p><p><b>　　實驗調(diào)用前圖片：</b></p><p>　　實驗調(diào)用后結(jié)果截圖圖片：</p><p>　　第四章 K-均值算法應(yīng)用與優(yōu)缺點</p><p>　　4.1K-均值聚類法的應(yīng)用</p><p>　　① 在機(jī)械設(shè)備鐵路監(jiān)測技術(shù)中的應(yīng)用。</p&

42、gt;<p>　?、?在人力資源管理中的應(yīng)用。</p><p>　　③ 在商業(yè)銀行客戶分類中的應(yīng)用。</p><p>　　4.2K-均值聚類法的優(yōu)缺點</p><p><b>　　缺點</b></p><p>　?、?在 K-means 算法中 K 是事先給定的，這個 K 值的選定是非常難以估計的。<

43、/p><p>　?、?在 K-means 算法中，首先需要根據(jù)初始聚類中心來確定一個初始劃分，然后對初始劃分進(jìn)行優(yōu)化。</p><p>　?、?從 K-means 算法框架可以看出，該算法需要不斷地進(jìn)行樣本分類調(diào)整，不斷地計算調(diào)整后的新的聚類中心，因此當(dāng)數(shù)據(jù)量非常大時，算法的時間開銷是非常大的。</p><p><b>　　優(yōu)點：</b></

44、p><p>　　本算法確定的K 個劃分到達(dá)平方誤差最小。當(dāng)聚類是密集的，且類與類之間區(qū)別明顯時，效果較好。對于處理大數(shù)據(jù)集，這個算法是相對可伸縮和高效的，計算的復(fù)雜度為O(NKt)，其中N是數(shù)據(jù)對象的數(shù)目，t是迭代的次數(shù)。一般來說，K<<N，t<<N 。</p><p>　　第五章 課程設(shè)計總結(jié)</p><p>　　通過此次課程設(shè)計，對空間分析

45、中的聚類分析有了更一步的了解和體會，尤其是對系統(tǒng)聚類分析有了深刻的掌握，基于Matlab軟件的方便性和語言的簡潔易懂性，基本完成了該次課程設(shè)計的程序編寫。</p><p>　　當(dāng)然，在課程設(shè)計主要是依據(jù)《空間分析》及《模式識別導(dǎo)論》兩本所學(xué)課程教材中的聚類分析章節(jié)來參考編寫的，空間聚類可以采用不同的算法過程。在分析之初假定n個點自成一類，然后逐步合并，這樣在聚類的過程中，分類將越來越少，直至聚至一個適當(dāng)?shù)姆诸悢?shù)目

46、，這一聚類過程稱之為系統(tǒng)聚類。顯然，距離是事物之間差異性的測度，差異性越大，則相似性越小，所以距離是系統(tǒng)聚類分析的依據(jù)和基礎(chǔ)。設(shè)計算法思想和選用其中的最短距離的原則來進(jìn)行系統(tǒng)聚類，我們已經(jīng)指出系統(tǒng)聚類方法首先將n個空間點看做是n個子群，然后根據(jù)所選用的聚類統(tǒng)計量來計算n個子群之間的關(guān)系。對于距離，計算n個子群兩兩之間的距離，首先選擇距離最近的兩個子群（點）歸為一個新的子群，這樣就得到n-1個子群兩兩之間的聚類統(tǒng)計量，繼續(xù)選擇距離最近的子

47、群合并，再得到n-2個子群……，依此類推，直到所有的子群全部合并。</p><p>　　設(shè)計的程序也有不足之處，對于數(shù)據(jù)量大的空間聚類顯得不實用，僅僅較適合數(shù)據(jù)小的系統(tǒng)聚類，如上述小數(shù)據(jù)量的圖片的聚類分析，對于提高程序空間聚類分析能力，還待進(jìn)一步的研究。</p><p><b>　　主要參考文獻(xiàn)</b></p><p>　　1 郭仁忠，空間分析

48、，北京：高等教育出版社，2001</p><p>　　2 范久倫，趙鳳，等.模式識別導(dǎo)論，西安：西安電子科技大學(xué)出版社，2012.5</p><p>　　3 張強(qiáng)，王正林，精通 MATLAB 圖像處理，電子工業(yè)出版社，2009</p><p>　　4 張克權(quán)，組合指標(biāo)分類方法簡介與分析，北京：測繪出版社，1980</p><p>　　5 郭仁