基于GIS的空間聚類算法研究

1、基于GIS的空間聚類算法研究厙向陽1 薛惠鋒1 李繼軍1 彭文祥21(西北工業(yè)大學自動化學院，西安，710072)2(上海交通大學圖像處理與模式識別研究所，上海，200030)摘基金項目：國家博士后科學基金資助項目（）作者簡介：厙向陽(1968-)，男，陜西周至人，西北工業(yè)大學博士生，從事數(shù)據挖掘、人工智能、復雜系統(tǒng)建模與仿真等方面研究。E-mail: 要:面對目前的聚類方法的局限性和空間聚類的特殊性，從基于目標函數(shù)聚類的概念出發(fā)，以GIS的空間數(shù)據管理和空間分析為技術支持，探討了空間樣本間直接可達距離、間接可達距離和可達成本的計算方法。隨機選擇k個樣本作為聚類中心點，以空間樣本到各聚類中心點

2、的可達距離為樣本劃分依據，以空間樣本到其聚類中心點的可達成本的總和為聚類目標函數(shù)，引入遺傳算法，提出一種基于GIS的空間聚類算法。最后，通過實例進行了算法測試。關 鍵 詞:數(shù)據挖掘；聚類算法；地理信息系統(tǒng)(GIS)；遺傳算法；中圖分類號:TP393.3 文獻標識碼1. 引言聚類分析是數(shù)據挖掘和知識發(fā)現(xiàn)中一項重要內容，它是將物理或抽象的對象,按照對象間的相似性進行區(qū)分和分類的過程。聚類所生成的簇是一組數(shù)據對象的集合,在同一簇中的對象之間具有較高的相似度,而不同簇間差別較大。聚類分析已經被廣泛地應用到模式識別、數(shù)據分析、圖像處理、市場研究以及服務設施的選址等領域中。目前的聚類方法有：劃分方法、層次

3、的方法、基于密度的方法、基于網格的方法和基于模型的方法等1。這些聚類方法隱含兩個假設：樣本間是可以直達的，一般采用樣本間的直線距離來衡量樣本間的相似性，忽略了障礙物的約束條件；所有樣本是等權的，也就是所有樣本的重要性、代表性是相同的。然而空間數(shù)據并不具備這樣的假設條件，假如要在一個城市為給定數(shù)目的自動提款機（即ATM）選址，可以對城市所有的居民點按照空間位置特征進行聚類，各個簇的中心點即可作為自動提款機位置。在這一聚類過程中，由于城市中的河流、湖泊、高山等障礙物的約束作用，各居民點并非沿著直線，而是沿著一定的道路或網絡到達到簇的中心點。各居民點由于總人口不同，它在聚類過程中的重要性是不同的。顯

4、然對于空間數(shù)據按照目前的聚類方法進行聚類是不符合實際或者是對實際的一種扭曲。文獻Error! Reference source not found.最早界定了在障礙物約束下的聚類問題(Clustering with Obstructed Distance, COD),并且提出了COD-CLEARNS算法。COD-CLEARNS算法核心思想：在顧及障礙物約束的條件下計算任意兩樣本點間的最近距離，將采樣技術和PAM相結合來，通過迭代的方法來完成在障礙物約束下的聚類問題。文獻Error! Reference source not found.以基于密度的算法（DBSCAN）為基礎，用多邊形表示各種形

5、狀、大小的障礙物，并對多邊形進行了約簡，提出了DBClU0C(Density-Based Clustering with Obstacles Constraints)算法。這些算法盡管解決了在障礙物約束下的聚類問題，但存在如下缺陷：在為數(shù)不多的假定障礙物約束下進行空間聚類；沒有考慮空間樣本的權重；相鄰空間樣本按照直線距離來計算樣本間的相似性。這些缺陷使得空間聚類結果與實際仍然存在較大的差距。在現(xiàn)實生活中，人們總是通過修路、架橋、開鑿隧道和開通水運或者航線等手段來克服障礙物約束，而人流、物流、信息流總是沿著一定的路線（道路、航線和線路等）流動?？臻g數(shù)據除具有空間屬性外，還具有非空間屬性及其空間關

6、系屬性，具有復雜的數(shù)據結構。地理信息系統(tǒng)(GIS)是空間數(shù)據采集、管理、分析、建模和可視化的工具Error! Reference source not found.?？臻g數(shù)據管理、空間分析是GIS特有的功能。將GIS與聚類算法相結合，它能為聚類算法提供必要的空間數(shù)據管理和空間分析的技術支持，使得空間聚類更加符合實際情況。基于以上分析，面對目前的聚類方法的局限性和空間聚類的特殊性，從基于目標函數(shù)聚類的概念出發(fā)，以GIS的空間數(shù)據管理和空間分析為技術支持，探討了空間樣本間直接可達距離、間接可達距離和可達成本的計算方法。隨機選擇k個樣本作為聚類中心點，以空間樣本距各聚類中心點的可達距離為樣本劃分依據

7、，以各空間樣本到其聚類中心點的可達成本總和為聚類目標函數(shù)，引入遺傳算法，提出一種基于GIS的空間聚類算法。最后，通過實例進行了算法測試。2. 空間數(shù)據聚類的基礎2.1. 基于目標函數(shù)的聚類模型設為待聚類樣本的全體（稱為論域），為觀測樣本的特征矢量或模式矢量，對應特征空間中的一個點，為特征矢量的第維特征取值。設為聚類數(shù)，為樣本數(shù)，聚類中心點集，為硬劃分矩陣。若按照最近距離進行樣本劃分，則樣本硬劃分矩陣計算如下：（1）式中表示樣本與中心點之間的歐氏距離。若以類內平方誤差和（WGSS）最小化為聚類目標函數(shù)，則聚類的目標函數(shù)表示為：聚類就是通過分析論域中的個樣本所對應模式矢量間的相似性，按照樣本間的親

8、疏關系，在滿足（2）式的前提下，將劃分成個子集（也稱為族），并滿足如下條件：2.2. 基于GIS的空間聚類樣本表達空間待聚類樣本可以抽象為空間上的點和點間的弧段，如圖1（a）所示?？臻g上的點除了具有空間屬性外，還具有非空間屬性及其空間關系屬性（拓撲關系、距離關系和方位關系）。由于空間上的點并非假想的均質平原上的點，而是實際地理空間上的點，必然受到一些障礙物的約束，并通過特定的網絡來連接。地理信息系統(tǒng)作為管理和分析空間數(shù)據的工具，它按照主題圖方法來描述空間對象。對于待聚類的空間樣本，可用點、線兩個主體圖來描述。例如：使用點主題圖層表示空間樣本點，它的綜合屬性表如圖1（b）所示,表中第二列表示空間

9、樣本點的空間屬性（如空間坐標等），其余表示空間樣本點的非空間屬性（如居民點的人口、地價等）。使用線圖層表示空間樣本點間的空間關系，它的綜合屬性表如圖1（c）所示，第二列表示弧段的空間屬性（如構成弧段的所有點的空間坐標對），其余表示弧線段的非空間屬性（如弧段長度、起始端點號等）。(a) (b) (c)圖1 GIS對空間聚類樣本的表達2.3. 可達距離和可達成本的定義障礙物的存在使得空間樣本間通過弧段相連接，它們之間的距離并非是兩點間的直線距離，而是弧段長度的代數(shù)和。樣本距各個聚類中心點（從樣本點集中選擇的一組點）的距離是樣本劃分的依據，也是聚類質量評價的基礎。在空間樣本點中，有一些點是直接可達的

10、，如圖1（a）中的0和1、0和5、0和4空間樣本點之間，另外一些點是借助其它空間點間接可達的，如圖1（a）中的1和3、0和2、4和2空間樣本點之間?！局苯涌蛇_距離】直接可達的空間樣本點之間所對應的弧段長度稱為直接可達距離?？臻g樣本點0和1之間的直接可達距離可由來表示。為了便于計算，特作如下的約定：GIS軟件一般可以計算直接可達空間樣本點間的弧段長度。按照（4）式的定義可以構造空間樣本點直接可達矩陣，它是一個對稱矩陣。圖1中的空間樣本點的直接可達矩陣如表1所示。直接可達矩陣 表1點號點號0123450081.0289.9992.02181.020140.4770.702140.470111.45

11、91.933111.450107.4078.73489.99107.40079.19592.0270.7091.9378.7379.190【間接可達距離】以其它空間點作為傳遞點而間接可達的空間樣本點間的最短路徑長度稱為間接可達距離。以直接可達距離為基礎，使用一些空間樣本點或者接點（非空間樣本點，而是弧段連接點）作為傳遞點，來計算間接可達距離。由于選取不同的傳遞點（即計算路徑不同），則路徑長度不同。間接可達距離是按照最短路徑所計算的弧段長度和，這是符合空間聚類實際的，因為某一個居民點的人到服務中心接受服務一般會選擇最短路徑到達。以直接可達矩陣為基礎使用Dijkstra算法可以計算任意兩樣本點間的

12、間接可達距離Error! Reference source not found.。任何兩個空間樣本點間總是可以通達的，也就是說不是直接可達，就是間接可達?？臻g樣本點間直接可達距離和間接可達距離，統(tǒng)稱為可達距離。由直接可達距離和間接可達距離可以構成任何兩個空間樣本點間的可達矩陣，它是一個對稱矩陣。圖1中的可達距離可以構成如表2所示的可達矩陣?？蛇_矩陣 表2點號點號0123450081.21183.94170.7389.9992.02181.210140.47149.42149.8970.702183.94140.470111.45171.1291.933170.73149.42111.45010

13、7.4078.73489.99149.89171.12107.40079.19592.0270.7091.9378.7379.190【可達成本】某一個居民點的人到服務中心接受服務的總成本不僅與可達距離相關，而且與居民點的總人口有關?？臻g樣本點的權重乘以到某一特定空間樣本點的可達距離稱為該空間樣本點到某一特定空間樣本點的可達成本，計算公式如下：式中：空間樣本點到空間樣本點可達成本；樣本點的權重；空間樣本點和間可達距離。3. 基于GIS的空間聚類算法3.1. 基本思想基于GIS空間技術的空間聚類可以歸納為一個基于目標函數(shù)的優(yōu)化問題。遺傳算法是由美國Holland教授于1975年提出的，它是一種基于

14、生物進化論和自然遺傳學說的自適應、隨機全局優(yōu)化的并行算法6。具有較強的的魯棒性，并具有收斂到全局最優(yōu)的能力，對目標函數(shù)既不要求連續(xù)，也不要求可微。因而，使用遺傳算法解決空間聚類問題具有明顯的優(yōu)勢。1.樣本劃分方法：在待聚類樣本集合中，隨機選擇與聚類數(shù)目相同個數(shù)的樣本點作為聚類中心點，其余待聚類樣本點根據距各個聚類中心點的可達距離，劃分給最近的中心點，樣本劃分方法可按（6）進行：（1）式中表示樣本與聚類中心點之間的可達距離。2.目標函數(shù)：目標函數(shù)對應于遺傳算法中的適應度函數(shù)。所有空間樣本點到其聚類中心點的可達成本總和的最小化可以作為空間聚類的目標函數(shù)。這樣（2）式可改寫為：3.染色體編碼基于遺傳

15、算法聚類的關鍵是如何將聚類問題的解編碼到基因串中67。由（7）式得目標函數(shù)與聚類中心點集和樣本劃分矩陣有關，而劃分矩陣又與聚類中心點集相關。因而，使用遺傳算法來求解這一聚類問題可以直接對聚類中心點進行編碼。若采用自然編碼方案，則染色體編碼為：其中表示聚類中心點取自樣本集中第個樣本。3.2. 聚類算法算法：基于GIS的空間聚類算法。輸入：聚類數(shù)目K，包含n個待聚類樣本的空間數(shù)據庫（點和網絡圖層）。輸出：空間樣本劃分矩陣和聚類中心點集，使空間樣本點間的可達成本總和最小。方法：Step1.設置GA相關參數(shù)，包括最大迭代次數(shù)、群體大小、交叉概率、變異概率；Step2.群體初始化，按照染色體編碼方案對染

16、色體群體進行初始化；Step3.群體評價，對染色體進行解碼，獲得聚類中心點，基于可達距離對樣本集進行劃分，采用空間樣本點的可達成本總和對染色體群體進行評價；Step4.染色體選擇，依據評價結果，選擇較優(yōu)的染色體，進行下一步操作；Step5.染色體交叉；Step6.染色體變異；Step7.染色體保留；Step8.中止條件檢驗，如果小于最大迭代次數(shù)，則轉向Step3，否則停止迭代，輸出空間樣本劃分矩陣和聚類中心點集。4. 算法測試為了測試本文提出的聚類算法的有效性，使用Matlab語言編制了相應的計算機程序。以陜西省所轄市縣為空間聚類樣本點，以陜西省境內的道路網絡為空間樣本點的聯(lián)接關系，以各縣市總

17、人口為空間樣本點的權重。使用地理信息系統(tǒng)ArcGIS8.3軟件建立空間信息系統(tǒng)，并將各縣市總人口、縣市間的直接可達矩陣輸出為*.Text文本文件。使用Matlab語言編制相應的計算機程序，讀取*.Text文本文件，并計算各縣市間的可達矩陣，進行空間聚類分析。最后將聚類結果通過ArcGIS8.3軟件進行可視化表達。遺傳算法中參數(shù)設置：染色體群體大小為30；最大迭代次數(shù)為500次；交叉概率為0.7；變異概率為0.05。當聚類數(shù)目為5時，染色體群體在223代時達到最優(yōu)值：，空間聚類結果如圖2所示。5. 結束語面對目前的聚類方法的局限性，引入GIS技術來管理和分析空間數(shù)據。在此基礎上，探討了空間對象間

18、直接可達距離、間接可達距離和可達成本的計算方法。引入遺傳算法，提出一種基于GIS的空間聚類算法。基于GIS的空間聚類使得空間數(shù)據的聚類結果更加符合實際情況。圖2 基于GIS的空間聚類結果參考文獻:1 Jiawei Han, Micheline kamber,范明，孟小峰譯數(shù)據挖掘概念與技術M北京：機械工業(yè)出版社，20012 A K H Tung, J HOU, J Han. Spatial clustering in the presence of obstacleCIn: Proc 2001 Int. Conf. On Data Engineering ICDE (01), 2001,359

19、-3673 邱長春，薛超英，劉海波一種基于障礙約束的空間數(shù)據聚類方法J計算機工程與應用，2003 (31): 186-1874 陳述彭，魯學軍，周成虎地理信息導論M北京：科學出版社19995 錢頌迪等運籌學M北京：清華大學出版社19906 李敏強，寇紀淞，林丹等遺傳算法的基本理論與應用M北京：科學出版社，20027 高新波模糊聚類分析及其應用M西安：西安電子科技大學出版社，2004The research on the spatial clustering algorithm based on GISShe xiangyang1, Peng wenxiang2, Xue huifeng1, L

20、i jijun11 (College of Automation, Northwest Polytechnic university, Xian, 710072,China)2(Institute of Image Processing & Pattern Recognition, Shanghai Jiao Tong University, Shanghai, 200030,China)Abstract: Facing the localization of present cluster approach and spatial data particularity, the direct accessibility distance, the indirect accessibility distance and accessibility cost are defined between spatial samples, from cluster concept based on a