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

1、空間分析系統(tǒng)聚類算法及編程實(shí)現(xiàn)學(xué)院：地質(zhì)工程與測(cè)繪學(xué)院專業(yè)：遙感科學(xué)與技術(shù)班級(jí)：2011260601學(xué)號(hào)：學(xué)生姓名：指導(dǎo)老師：李斌目錄 TOC o 1-5 h z HYPERLINK l bookmark10 o Current Document 第1章前言3 HYPERLINK l bookmark13 o Current Document 第2章 算法設(shè)計(jì)背景3 HYPERLINK l bookmark16 o Current Document 2.1聚類要素的數(shù)據(jù)處理3 HYPERLINK l bookmark39 o Current Document 2.2 距離的計(jì)算5 HYPERL

2、INK l bookmark66 o Current Document 第3章算法思想與編程實(shí)現(xiàn)5 HYPERLINK l bookmark69 o Current Document 3.1算法思想5 HYPERLINK l bookmark74 o Current Document 3.2用Matlab編程實(shí)現(xiàn)7 HYPERLINK l bookmark77 o Current Document 3.2.1程序代碼7 HYPERLINK l bookmark80 o Current Document 3.2.2編程操作結(jié)果12 HYPERLINK l bookmark83 o Current

3、 Document 第4章K-均值算法應(yīng)用與優(yōu)缺點(diǎn)13 HYPERLINK l bookmark86 o Current Document K-均值聚類法的應(yīng)用13 HYPERLINK l bookmark92 o Current Document K-均值聚類法的優(yōu)缺點(diǎn)14 HYPERLINK l bookmark98 o Current Document 第5章課程設(shè)計(jì)總結(jié)14 HYPERLINK l bookmark101 o Current Document 主要參考文獻(xiàn)15第一章前言本課題是根據(jù)李斌老師所教授的空間分析課程內(nèi)容及要求而選定的， 是對(duì)于系統(tǒng)聚類算法的分析研究及利用相關(guān)軟

4、件的編程而實(shí)現(xiàn)系統(tǒng)聚類。研 究的是系統(tǒng)聚類算法的分析及編程實(shí)現(xiàn)，空間聚類的目的是對(duì)空間物體的集 群性進(jìn)行分析，將其分為幾個(gè)不同的子群（類）。子群的形成的是地理系統(tǒng)運(yùn) 作的結(jié)果，根據(jù)此可以揭示某種地理機(jī)制。此外，子群可以作為其它分析的 基礎(chǔ)，例如，公共設(shè)施的建立一般地說(shuō)是根據(jù)居民點(diǎn)群的分布，而不是具體 的居民住宅的分布來(lái)布置的，因此需要對(duì)居民點(diǎn)群進(jìn)行聚類分析以形成若干 居民點(diǎn)子群，這樣便于簡(jiǎn)化問(wèn)題，突出重點(diǎn)?？臻g聚類可以采用不同的算法過(guò)程。在分析之初假定n個(gè)點(diǎn)自成一類，然 后逐步合并，這樣在聚類的過(guò)程中，分類將越來(lái)越少，直至聚至一個(gè)適當(dāng)?shù)姆?類數(shù)目，這一聚類過(guò)程稱之為系統(tǒng)聚類。常見(jiàn)的聚類分析方法

5、有系統(tǒng)聚類法、 動(dòng)態(tài)聚類法和模糊聚類法等。下面主要介紹系統(tǒng)聚類算法，并基于Matlab軟 件用K-means算法（即k-均值算法）來(lái)實(shí)現(xiàn)系統(tǒng)聚類的算法編程。第二章算法設(shè)計(jì)背景2.1聚類要素的數(shù)據(jù)處理假設(shè)有m個(gè)聚類的對(duì)象，每一個(gè)聚類對(duì)象都有個(gè)要素構(gòu)成。它們所對(duì)應(yīng)的 要素?cái)?shù)據(jù)可用表3.4.1給出。在聚類分析中，常用的聚類要素的數(shù)據(jù)處理方 法有如下幾種。表3.41聚美對(duì)篡與要素螭類對(duì)象要索曲A ,A ,1.A ?A ?2勺1X22A ,孩A ,NM-MMMMMi知砧A ,XVA ?戰(zhàn)MMMMMmA ?A ?nr MM總和標(biāo)準(zhǔn)化X-高=疽 。= 12%方;J = 12人對(duì)2-1且 Z # = 1 (J

6、 = 12 A M)2-1標(biāo)準(zhǔn)差標(biāo)準(zhǔn)化極大值標(biāo)準(zhǔn)化X-司=；-9=1% 容；J = LZA）J max （砌經(jīng)過(guò)這種標(biāo)準(zhǔn)化所得的新數(shù)據(jù)，各要素的極大值為1,其余各數(shù)值小于1。極差的標(biāo)準(zhǔn)化 經(jīng)過(guò)這種標(biāo)準(zhǔn)化所得的新數(shù)據(jù)，各要素的極大值為1,極小值為0,其余的數(shù)值 均在0與1之間。二 。二 12人二 12A 涎）2.2距離的計(jì)算距離是事物之間差異性的測(cè)度，差異性越大，則相似性越小，所以距離是系統(tǒng) 聚類分析的依據(jù)和基礎(chǔ)。鋼蹶蔑d薄=切林.勺：! （z J =1,2,A骯2=1 0離a,=i?2,a，就:明科夫斯基距蔑1初二y|工說(shuō)-兀忱。疽=Ina切比寰夫距離選擇不同的距離，聚類結(jié)果會(huì)有所差異。在地理

7、分區(qū)和分類研究中，往往采用 幾種距離進(jìn)行計(jì)算、電對(duì)比，選擇一種較為合適的距離進(jìn)行聚類。匕.=m羿；做一誑 （入j = 1,2,A，歐）FV第三章算法思想與編程實(shí)現(xiàn)3.1算法思想我們已經(jīng)指出系統(tǒng)聚類方法首先將n個(gè)空間點(diǎn)看做是n個(gè)子群，然后根據(jù)所選用的聚類統(tǒng)計(jì)量來(lái)計(jì)算n個(gè)子群之間的關(guān)系。對(duì)于距離，計(jì)算n個(gè)子群兩兩之間 的距離，首先選擇距離最近的兩個(gè)子群（點(diǎn)）歸為一個(gè)新的子群，這樣就得到 n-1個(gè)子群兩兩之間的聚類統(tǒng)計(jì)量，繼續(xù)選擇距離最近的子群合并，再得到n-2 個(gè)子群，依此類推，直到所有的子群全部合并。K-means算法是硬聚類算法，是典型的局域原型的目標(biāo)函數(shù)聚類方法的代表， 它是數(shù)據(jù)點(diǎn)到原型的某

8、種距離作為優(yōu)化的目標(biāo)函數(shù)，利用函數(shù)求極值的方法得到 迭代運(yùn)算的調(diào)整規(guī)則。K-means算法以歐式距離作為相似度測(cè)度，它是求對(duì)應(yīng)某 一初始聚類中心向量V最有分類，使得評(píng)價(jià)指標(biāo)J最小。算法采用誤差平方和準(zhǔn) 則函數(shù)作為聚類準(zhǔn)則函數(shù)。K-均值算法的聚類準(zhǔn)則是使每一聚類中，多模式點(diǎn)到該類別的中心的距離的平 方和最小。其基本思想是：通過(guò)迭代，主次移動(dòng)各類的中心，直到得到最好的聚 類為止。其算法框圖如圖所示。具體的計(jì)算步驟如下：假設(shè)圖像上的目標(biāo)要分為m類，m為已知數(shù)。第一步：適當(dāng)?shù)剡x取m個(gè)類的初始中心Z1（i）,Z2（i）, , Zm（i），初始中心的選 擇對(duì)聚類結(jié)果有一定的影響，初始中心的選擇一般有如下幾

9、種方法：1）根據(jù)問(wèn)題的性質(zhì)和經(jīng)驗(yàn)確定類別數(shù)m，從數(shù)據(jù)中找出直觀上看來(lái)比 較適合的m個(gè)類的初始中心。2）將全部數(shù)據(jù)隨即地分為m個(gè)類型，計(jì)算每類的重心，將這些重心 作為m個(gè)類的初始中心。第二步：在第k次迭代中，對(duì)任一樣本X按如下的方法把它調(diào)整到m個(gè)類別 中的某一類別中去。對(duì)于所有的i乏j, i = 1,2, ，m,如果X-Zj（k） X-Z（k），則XeS （k）其中S （k）是以Z （k）為中心的類。ijji第三步：由第二步得到Sj（k）類新的中心一 一 1 LZ,（k）,Z,（k）= Xj X eS（K） j式中，N為S（k）類中的樣本數(shù)。Z（k+i）是按照使J最小的原則確定的，J的表達(dá)式 j

10、 jj為：j= j= j=1 X eS（k） jZ（5第四步：對(duì)于所有的i=1,2 ,m，第四步：對(duì)于所有的i=1,2 ,m，如果Zi（k+i）=Zi（k）,則迭代結(jié)束，否則轉(zhuǎn)到0第二步繼續(xù)迭代。這種算法的結(jié)果受到所選聚類中心的數(shù)目和其初始位置以及模式分布的幾 何性質(zhì)和讀入次序等因素的影響，并且在迭代過(guò)程中又沒(méi)有調(diào)整類數(shù)的措施，因 此可能產(chǎn)生不同的初始分類得到不同的結(jié)果，這是這種方法的缺點(diǎn)?？梢酝ㄟ^(guò)其 他的簡(jiǎn)單的聚類中心試探方法，如最大距離法，找出初始中心，提高分類效果。3.2用Mat lab編程實(shí)現(xiàn)3.2.1程序代碼對(duì)于上述的K-mean算法用Matlab軟件實(shí)現(xiàn)編程并調(diào)用數(shù)據(jù)小的圖片進(jìn)行聚

11、類分析及編程是否正確性的檢測(cè)。具體程序代碼如下：%控制循環(huán)次數(shù)%控制循環(huán)次數(shù)%個(gè)和sample等維數(shù)的標(biāo)記向量%選取第1類聚類中心%選取第2類聚類中心%選取第3類聚類中心%選取第4類聚類中心%讀取圖片Imag = imread(hand.jpg);sample = rgb2gray(Imag);m n = size(sample);sample = reshape(sample,m*n,1);k = 4;%分成4類t = 0;flag = 0;ocentre1 = 80;ocentre2 = 160;ocentre3 = 220;ocentre4 = 255;sample = double(s

12、ample);while t = 0%fsample1 = 0;%fsample2 = 0;%fsample3 = 0;%fsample4 = 0;fsample = zeros(4,1);num = zeros(4,1);%只能讀取三個(gè)波段%將彩色圖片轉(zhuǎn)換為灰度圖片%讀取圖片的維數(shù)%將矩陣變換為m*n行1列的向量%將uint8類型轉(zhuǎn)換為double型dis = zeros(1,4);for i = 1:m*n%a = 5 - 2;%b = 2 - 5;dis(1)=abs(sample(i)-ocentre1);%求到第1個(gè)聚類中心距離dis(2)=abs(sample(i)-ocentre

13、2);%求到第2個(gè)聚類中心距離dis(3)=abs(sample(i)-ocentre3);dis(1)=abs(sample(i)-ocentre1);%求到第1個(gè)聚類中心距離dis(2)=abs(sample(i)-ocentre2);%求到第2個(gè)聚類中心距離dis(3)=abs(sample(i)-ocentre3);%求到第3個(gè)聚類中心距離dis(4)=abs(sample(i)-ocentre4);%求到第4個(gè)聚類中心距離mindismin(dis(1) dis(2) dis(3) dis(4);%求最小的距離判斷 判斷 dis2dis1， 循環(huán)%選取最小值，第一個(gè)值給dis1,第二

14、個(gè)值給dis2 則給dis2值于dis1,計(jì)算第三個(gè)距離給dis2，返回第三步switch mindiscase dis(1)%flag = cat(1,flag,1);%將標(biāo)記數(shù)組賦值1，該點(diǎn)屬于第1類%fsample1 = cat(1,fsample1,sample(i);flag(i) = 1;fsample(1) = fsample(1) + sample(i);num(1) = num(1) + 1;case dis(2)%flag = cat(1,flag,2);%將標(biāo)記數(shù)組賦值2,該點(diǎn)屬于第2類%fsample2 = cat(1,fsample2,sample(i);flag(i

15、) = 2;fsample(2) = fsample(2) + sample(i);num(2) = num(2) + 1;case dis(3)%flag = cat(1,flag,3);%將標(biāo)記數(shù)組賦值3,該點(diǎn)屬于第3類%fsample3 = cat(1,fsample3,sample(i);flag(i) = 3;fsample(3) = fsample(3) + sample(i);num(3) = num(3) + 1;case dis(4)%flag = cat(1,flag,4);%將標(biāo)記數(shù)組賦值4，該點(diǎn)屬于第4類%fsample4 = cat(1,fsample4,sample

16、(i);flag(i) = 4;fsample(4) = fsample(4) + sample(i);num(4) = num(4) + 1;endend%重新計(jì)算聚類中心弘 毅 明 德 篤 學(xué) 創(chuàng) 新%m1 n1 = size(fsamplel);%m2 n2 = size(fsample2);%m3 n3 = size(fsample3);%m4 n4 = size(fsample4);%ncentre1 = sum(fsample1)/(m1 - 1);%ncentre2 = sum(fsample2)/(m2 - 1);%ncentre3 = sum(fsample3)/(m3 -

17、1);%ncentre4 = sum(fsample4)/(m4 - 1);%flag%fsamplencentre1 = fsample(1)/num(1);ncentre2 = fsample(2)/num(2);ncentre3 = fsample(3)/num(3);ncentre4 = fsample(4)/num(4);%flag(1)=;if ncentre1 = ocentre1 & ncentre2 = ocentre2.& ncentre3 = ocentre3 & ncentre4 = ocentre4for i = 1:m*nswitch flag(i)case 1sa

18、mple(i) = 60;case 2sample(i) = 120;case 3sample(i) = 180;case 4sample(i) = 240;endendt = 1；elseocentrel = ncentrel;ocentre2 = ncentre2;ocentre3 = ncentre3;ocentre4 = ncentre4;endendsample = uint8(sample);sample = reshape(sample,m,n);imshow(sample);3.2.2編程操作結(jié)果實(shí)驗(yàn)調(diào)用前圖片:實(shí)驗(yàn)調(diào)用后結(jié)果截圖圖片:第四章K-均值算法應(yīng)用與優(yōu)缺點(diǎn)4.1K-均

19、值聚類法的應(yīng)用在機(jī)械設(shè)備鐵路監(jiān)測(cè)技術(shù)中的應(yīng)用。在人力資源管理中的應(yīng)用。在商業(yè)銀行客戶分類中的應(yīng)用。4.2K -均值聚類法的優(yōu)缺點(diǎn)缺點(diǎn)在K-means算法中K是事先給定的，這個(gè)K值的選定是非常難以 估計(jì)的。在K-means算法中，首先需要根據(jù)初始聚類中心來(lái)確定一個(gè)初始劃 分，然后對(duì)初始劃分進(jìn)行優(yōu)化。從K-means算法框架可以看出，該算法需要不斷地進(jìn)行樣本分類調(diào) 整，不斷地計(jì)算調(diào)整后的新的聚類中心，因此當(dāng)數(shù)據(jù)量非常大時(shí)，算法的 時(shí)間開銷是非常大的。優(yōu)點(diǎn)：本算法確定的K個(gè)劃分到達(dá)平方誤差最小。當(dāng)聚類是密集的，且類與 類之間區(qū)別明顯時(shí)，效果較好。對(duì)于處理大數(shù)據(jù)集，這個(gè)算法是相對(duì)可伸 縮和高效的，計(jì)算的復(fù)雜度為O(NKt)，其中N是數(shù)據(jù)對(duì)象的數(shù)目，t是迭 代的次數(shù)。一般來(lái)說(shuō)，KN，tN。第五章 課程設(shè)計(jì)總結(jié)通過(guò)此次課程設(shè)計(jì)，對(duì)空間分析中的聚類分析有了更一步的了解和體會(huì)，尤 其是對(duì)系統(tǒng)聚類分析有了深刻的掌握，基于Matlab軟件的方便性和語(yǔ)言的簡(jiǎn)潔 易懂性，基本完成了該次課程設(shè)計(jì)的程序編寫。當(dāng)然，在課程設(shè)計(jì)主要是依據(jù)空間分析及模式識(shí)別導(dǎo)論