1、空間分析系統聚類算法及編程實現學院：地質工程與測繪學院專業：遙感科學與技術班級：2011260601學號：學生姓名：指導老師：目錄 TOC o 1-5 h z HYPERLINK l bookmark8 o Current Document 第1章前言3第2章算法設計背景32.1聚類要素的數據處理3 HYPERLINK l bookmark15 o Current Document 2.2距離的計算5第3章算法思想與編程實現 53.1算法思想5 HYPERLINK l bookmark25 o Current Document 3.2用Matlab編程實現 6 HYPERLINK l book

2、mark28 o Current Document 第4章課程設計總結 10 HYPERLINK l bookmark31 o Current Document 主要參考文獻11第一章前言本課題是根據李斌老師所教授的空間分析課程內容及要求而選定的，是 對于系統聚類算法的分析研究及利用相關軟件的編程而實現系統聚類。研究的是 系統聚類算法的分析及編程實現，空間聚類的目的是對空間物體的集群性進行分 析，將其分為幾個不同的子群（類）。子群的形成的是地理系統運作的結果，根 據此可以揭示某種地理機制。此外，子群可以作為其它分析的基礎，例如，公共 設施的建立一般地說是根據居民點群的分布，而不是具體的居民住宅

3、的分布來布 置的，因此需要對居民點群進行聚類分析以形成若干居民點子群，這樣便于簡化 問題，突出重點。空間聚類可以采用不同的算法過程。在分析之初假定n個點自成一類，然后逐步合并，這樣在聚類的過程中，分類將越來越少，直至聚至一個適當的分類 數目，這一聚類過程稱之為系統聚類。常見的聚類分析方法有系統聚類法、動態 聚類法和模糊聚類法等。下面主要介紹系統聚類算法，并基于Matlab軟件來實現算法的編程。第二章算法設計背景2.1聚類要素的數據處理假設有m個聚類的對象，每一個聚類對象都有個要素構成。它們所對應的要 素數據可用表3.4.1給出。在聚類分析中，常用的聚類要素的數據處理方法有如下 幾種。聚類對象要

4、素陽也A ,心A ,1殆知a 切h *g2忑21 “22 A 兀JAf孟2抑kM M M M M M兀L X垢八龍擴h、MnkM M M M M M0 g A , % Af g總和標準化殆=2i/ i-l= 12A，淤;j = 1,2, A，方)且乞對i(7 = 12A E)i-l極大值標準化勺Q 12A gj = 2A /)經過這種標準化所得的新數據，各要素的極大值為 1,其余各數值小于i經過這種標準化所得的新數據，各要素的極大值為1,極小值為0,其余的數值均在 0與1之間。2.2距離的計算距離是事物之間差異性的測度，差異性越大，則相似性越小，所以距離是系統聚 類分析的依據和基礎。(D 巨離

5、(i.J = (i.J = 1,2,A 坯)明科夫斯基距禽應材=221舄取琨隅LJ切比雪夫距離當明科夫斯基距尸T8時表有選擇不同的距離，聚類結果會有所差異。在地理分區和分類研究中，往往采用幾 種距離進行計算、對比，選擇一種較為合適的距離進行聚類第三章算法思想與編程實現3.1算法思想我們已經指出系統聚類方法首先將n個空間點看做是n個子群，然后根據所選用的聚類統計量來計算n個子群之間的關系。對于距離，計算n個子群 兩兩之間的距離，首先選擇距離最近的兩個子群(點)歸為一個新的子群，這樣就 得到n-1個子群兩兩之間的聚類統計量，繼續選擇距離最近的子群合并，再得到 n-2個子群，依此類推，直到所有的子群

6、全部合并。3.2用Matlab編程實現運用Matlab中的一些基本矩陣計算方法，通過自己編程實現聚類算法，在此只 討論根據最短距離規則聚類的方法。調用函數：minl.m求矩陣最小值，返回最小值所在行和列以及值的大小min2.m -比較兩數大小，返回較小值stdl.m -用極差標準化法標準化矩陣dsl.m用絕對值距離法求距離矩陣cluster.m -應用最短距離聚類法進行聚類分析prin tl.m調用各子函數，顯示聚類結果聚類分析算法假設距離矩陣為vector，a階，矩陣中最大值為max，令矩陣上三角元素等于max聚類次數=a-1,以下步驟作a-1次循環：求改變后矩陣的階數，計作c求矩陣最小值，

7、返回最小值所在行e和列f以及值的大小gfor l=1:c,為 vector(c+1,l)賦值，產生新類令第c+1列元素，第e行和第f行所有元素為，第e列和第f列所有元素 為max源程序如下：%std1.m,用極差標準化法標準化矩陣fun cti on std=std1(vector)max=max(vector);%對歹U求最大值min=mi n(vector);a,b=size(vector);%巨陣大小,a為行數,b為列數for i=1:afor j=1:bstd(i,j)= (vector(ij)-mi n(j)/(max(j)-mi n(j);endend%ds1.m用絕對值法求距離f

8、un cti on d=ds1(vector);a,b=size(vector);d=zeros(a);for i=1:afor j=1:afor k=1:bd(i,j)=d(i,j)+abs(vector(i,k)-vector(j,k);endendendfprintf(絕對值距離矩陣如下：n);disp(d)%mi nl.m求矩陣中最小值，并返回行列數及其值function v15v25v3=min1(vector);%v1為行數，v2 為列數，v3 為其值v,v2=mi n( mi n(vector);v,v1=mi n( mi n(vector);v3=min(min( vector

9、);%min2.m比較兩數大小，返回較小的值fun cti on v仁 min( v2,v3);if v2v3v1=v3;elsev 仁 v2;end%cluster.m,最短距離聚類法function result=cluster(vector);a,b=size(vector);max=max(max(vector);for i=1:afor j=i:bvector(i,j)=max;endend;for k=1:(b-1)c,d=size(vector);fprintf(第9 次聚類:n,k);e,f,g=mi n1(vector);fprintf(最小值=%g將第9區和第g區并為一類，

10、記作 G%gnn,g,e,f,c+1);for l=1:cif l=mi n2(e,f)vector(c+1,l)=mi n2(vector(e,l),vector(f,l);elsevector(c+1,l)=mi n2(vector(l,e),vector(l,f);endend;vector(1:c+1,c+1)=max;vector(1:c+1,e)=max;vector(1:c+1,f)=max;vector(e,1:c+1)=max;vector(f,1:c+1)=max;end%printl，調用各子函數function print=print1(filename,a,b); %

11、a為地區個數，b 為指標數fid=fope n(filen ame,r)vector=fsca nf(fid,%g,a b);fprintf(標準化結果如下：n)v1=std1(vector)v2=ds1(v1);cluster(v2);%輸出結果prin t1(fname,9,7)第四章課程設計總結通過此次課程設計，對空間分析中的聚類分析有了更一步的了解和體會，尤其是 對系統聚類分析有了深刻的掌握，基于Matlab軟件的方便性和語言的簡潔易懂性， 基本完成了該次課程設計的程序編寫。當然，在課程設計主要是依據空間分析該書中聚類分析章節中的系統聚類分 析來，空間聚類可以采用不同的算法過程。在分析

12、之初假定n個點自成一類，然后 逐步合并，這樣在聚類的過程中，分類將越來越少，直至聚至一個適當的分類數 目，這一聚類過程稱之為系統聚類。顯然，距離是事物之間差異性的測度，差異性 越大，則相似性越小，所以距離是系統聚類分析的依據和基礎。設計算法思想和選 用其中的最短距離的原則來進行系統聚類，我們已經指出系統聚類方法首先將n個空間點看做是n個子群，然后根據所選用的聚類統計量來計算n個子群 之間的關系。對于距離，計算n個子群兩兩之間的距離，首先選擇距離最近的兩個 子群(點)歸為一個新的子群，這樣就得到n-1個子群兩兩之間的聚類統計量，繼續 選擇距離最近的子群合并，再得到n-2個子群，依此類推，直到所有的子群全 部合并。設計的程序也有不足之處，對于數據量大的空間聚類顯得不實用，僅僅較適合 數據小的系統聚類，即一般數據量的空間聚類分析，對于提高程序空間聚