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

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

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

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

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

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

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

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

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

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

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

11、91.933111.450107.4078.73489.99107.40079.19592.0270.7091.9378.7379.190【間接可達(dá)距離】以其它空間點(diǎn)作為傳遞點(diǎn)而間接可達(dá)的空間樣本點(diǎn)間的最短路徑長(zhǎng)度稱為間接可達(dá)距離。以直接可達(dá)距離為基礎(chǔ)，使用一些空間樣本點(diǎn)或者接點(diǎn)（非空間樣本點(diǎn)，而是弧段連接點(diǎn)）作為傳遞點(diǎn)，來(lái)計(jì)算間接可達(dá)距離。由于選取不同的傳遞點(diǎn)（即計(jì)算路徑不同），則路徑長(zhǎng)度不同。間接可達(dá)距離是按照最短路徑所計(jì)算的弧段長(zhǎng)度和，這是符合空間聚類實(shí)際的，因?yàn)槟骋粋€(gè)居民點(diǎn)的人到服務(wù)中心接受服務(wù)一般會(huì)選擇最短路徑到達(dá)。以直接可達(dá)矩陣為基礎(chǔ)使用Dijkstra算法可以計(jì)算任意兩樣本點(diǎn)間的

12、間接可達(dá)距離Error! Reference source not found.。任何兩個(gè)空間樣本點(diǎn)間總是可以通達(dá)的，也就是說(shuō)不是直接可達(dá)，就是間接可達(dá)?？臻g樣本點(diǎn)間直接可達(dá)距離和間接可達(dá)距離，統(tǒng)稱為可達(dá)距離。由直接可達(dá)距離和間接可達(dá)距離可以構(gòu)成任何兩個(gè)空間樣本點(diǎn)間的可達(dá)矩陣，它是一個(gè)對(duì)稱矩陣。圖1中的可達(dá)距離可以構(gòu)成如表2所示的可達(dá)矩陣?？蛇_(dá)矩陣 表2點(diǎn)號(hào)點(diǎn)號(hào)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【可達(dá)成本】某一個(gè)居民點(diǎn)的人到服務(wù)中心接受服務(wù)的總成本不僅與可達(dá)距離相關(guān)，而且與居民點(diǎn)的總?cè)丝谟嘘P(guān)。空間樣本點(diǎn)的權(quán)重乘以到某一特定空間樣本點(diǎn)的可達(dá)距離稱為該空間樣本點(diǎn)到某一特定空間樣本點(diǎn)的可達(dá)成本，計(jì)算公式如下：式中：空間樣本點(diǎn)到空間樣本點(diǎn)可達(dá)成本；樣本點(diǎn)的權(quán)重；空間樣本點(diǎn)和間可達(dá)距離。3. 基于GIS的空間聚類算法3.1. 基本思想基于GIS空間技術(shù)的空間聚類可以歸納為一個(gè)基于目標(biāo)函數(shù)的優(yōu)化問題。遺傳算法是由美國(guó)Holland教授于1975年提出的，它是一種基于

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

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

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

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

18、直接可達(dá)距離、間接可達(dá)距離和可達(dá)成本的計(jì)算方法。引入遺傳算法，提出一種基于GIS的空間聚類算法?；贕IS的空間聚類使得空間數(shù)據(jù)的聚類結(jié)果更加符合實(shí)際情況。圖2 基于GIS的空間聚類結(jié)果參考文獻(xiàn):1 Jiawei Han, Micheline kamber,范明，孟小峰譯數(shù)據(jù)挖掘概念與技術(shù)M北京：機(jī)械工業(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 邱長(zhǎng)春，薛超英，劉海波一種基于障礙約束的空間數(shù)據(jù)聚類方法J計(jì)算機(jī)工程與應(yīng)用，2003 (31): 186-1874 陳述彭，魯學(xué)軍，周成虎地理信息導(dǎo)論M北京：科學(xué)出版社19995 錢頌迪等運(yùn)籌學(xué)M北京：清華大學(xué)出版社19906 李敏強(qiáng)，寇紀(jì)淞，林丹等遺傳算法的基本理論與應(yīng)用M北京：科學(xué)出版社，20027 高新波模糊聚類分析及其應(yīng)用M西安：西安電子科技大學(xué)出版社，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