陳娛，許珺，徐敏政

（1.中國(guó)科學(xué)院地理科學(xué)與資源研究所資源與環(huán)境信息系統(tǒng)國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京 100101；2.中國(guó)科學(xué)院大學(xué)，北京 100049）

0 引言

空間聚類的目的是對(duì)空間物體的集群性進(jìn)行分析，將其分為不同的子群［1］。聚類分析研究的經(jīng)典算法有K－means、DBSCAN算法等，其主要應(yīng)用于空間聚類分析中。空間聚類算法中常用的有基于劃分的方法、基于層次的方法和基于密度的方法［2］?；趧澐值姆椒ㄊ侵冈诜诸愔躅A(yù)先確定分類個(gè)數(shù)，創(chuàng)建一個(gè)初始劃分，然后循環(huán)再定位，從而改變節(jié)點(diǎn)的歸宿，最終得到最優(yōu)聚類結(jié)果，其典型代表是經(jīng)典的K－means算法［3］。系統(tǒng)聚類就是基于層次的方法，不斷地合并空間點(diǎn)直到聚至一個(gè)適當(dāng)?shù)姆诸悅€(gè)數(shù)?；诿芏鹊姆椒ㄖ饕枷胧侵灰徑鼌^(qū)域的密度超過(guò)某個(gè)閾值，就繼續(xù)聚類，可以發(fā)現(xiàn)任意形狀的類，DBSCAN是這類算法的代表［4］。

上述算法存在著不同的缺陷，其中一個(gè)引起關(guān)注較多的問(wèn)題是：在不知道分類個(gè)數(shù)的情況下，如何獲得最優(yōu)的聚類結(jié)果？例如在K－means算法中，必須確定聚類個(gè)數(shù)之后，才能利用類內(nèi)方差這個(gè)準(zhǔn)則函數(shù)判斷最優(yōu)的聚類結(jié)果。而在復(fù)雜網(wǎng)絡(luò)研究領(lǐng)域，模塊度的概念被提出，用于評(píng)價(jià)復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)聚類質(zhì)量的好壞，模塊度值越大說(shuō)明聚類結(jié)果越優(yōu)。如此則在復(fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)聚類中無(wú)需預(yù)先設(shè)定類的個(gè)數(shù)。本文借鑒這個(gè)值的定義，構(gòu)造了評(píng)價(jià)空間聚類結(jié)果質(zhì)量好壞的標(biāo)準(zhǔn)——集聚度；然后基于該值提出了一個(gè)快速的層次聚類算法，可以在不預(yù)知分類個(gè)數(shù)的情況下得到空間點(diǎn)集的最優(yōu)聚類結(jié)果，且時(shí)間復(fù)雜度較低。

1 集聚度S值的定義

1.1 模塊度Q值

復(fù)雜網(wǎng)絡(luò)的研究意在探尋事物之間錯(cuò)綜復(fù)雜的關(guān)系，挖掘出意想不到的規(guī)律。例如，城市路網(wǎng)、航線網(wǎng)絡(luò)、社交網(wǎng)絡(luò)等都是典型的復(fù)雜網(wǎng)絡(luò)。在復(fù)雜網(wǎng)絡(luò)研究領(lǐng)域中，社區(qū)結(jié)構(gòu)挖掘是一個(gè)研究熱點(diǎn)。將網(wǎng)絡(luò)劃分為若干個(gè)群，群內(nèi)節(jié)點(diǎn)間的連接較為緊密，而群與群之間的連接較為稀疏，社區(qū)就是指這樣的群，社區(qū)結(jié)構(gòu)挖掘其實(shí)就是復(fù)雜網(wǎng)絡(luò)領(lǐng)域的聚類分析。如圖1中的小型網(wǎng)絡(luò)，它具有較為明顯社區(qū)結(jié)構(gòu)（圖2）。為了得到網(wǎng)絡(luò)最優(yōu)的社區(qū)結(jié)構(gòu)，提出模塊度的概念。模塊度即為網(wǎng)絡(luò)呈現(xiàn)出的模塊化的結(jié)構(gòu)，是衡量網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)挖掘質(zhì)量好壞的標(biāo)準(zhǔn)［5］，模塊度值越大則這種模塊化結(jié)構(gòu)越明顯。其公式為：其中，eij表示網(wǎng)絡(luò)中連接社區(qū)i和j的節(jié)點(diǎn)的邊占所有邊的比例，ai表示與第i個(gè)社區(qū)中的節(jié)點(diǎn)相連的邊占所有邊的比例，其值為eij矩陣的第i行元素之和。模塊度的物理意義是：社區(qū)內(nèi)部邊的數(shù)目占網(wǎng)絡(luò)總邊數(shù)的比例減去社區(qū)內(nèi)部邊數(shù)的期望值占網(wǎng)絡(luò)總邊數(shù)的比例。Q值越大（上限為1）表示社區(qū)內(nèi)部連接的稠密程度大于隨機(jī)分布下的期望值，Q值越接近1，說(shuō)明網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)越明顯。

圖1 小型的網(wǎng)絡(luò)Fig.1 A small network

圖2 社區(qū)結(jié)構(gòu)Fig.2 Community structure

1.2 集聚度S值

對(duì)于空間上的點(diǎn)集，聚類的基本思想是：根據(jù)點(diǎn)與點(diǎn)之間的空間距離，將點(diǎn)群劃分為若干個(gè)群，群內(nèi)的點(diǎn)盡可能集中，不同的點(diǎn)群盡可能分離。不管是網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)還是空間點(diǎn)集的群簇結(jié)構(gòu)，聚類的目標(biāo)一致。因此，根據(jù)復(fù)雜網(wǎng)絡(luò)理論中的模塊度公式構(gòu)造一個(gè)類似的函數(shù)S，用來(lái)判別空間點(diǎn)群的集聚性。

事物彼此相關(guān)，如果把這種影響看成其間的關(guān)系，用“連接”表達(dá)，就會(huì)形成一個(gè)網(wǎng)絡(luò)［6］。因此，把空間上的點(diǎn)集看做是兩兩相連的網(wǎng)絡(luò)，而其間的空間距離就反映了連接的強(qiáng)弱，邊長(zhǎng)即為兩點(diǎn)間的空間距離。

首先，獲得點(diǎn)集的直徑O（點(diǎn)集中相距最遠(yuǎn)的兩點(diǎn)間的距離），dvw表示節(jié)點(diǎn)v和w 間的距離，定義δvw＝1－dvw／O，該值反映了相距為dvw的兩個(gè)節(jié)點(diǎn)v和w之間的相似度。若兩節(jié)點(diǎn)相距為0，則相似度為1，若兩節(jié)點(diǎn)相距為整個(gè)點(diǎn)集的直徑大小，則相似度為0。由此，定義Dij，它表示群簇i中的點(diǎn)與群簇j中的點(diǎn)的相似度與點(diǎn)集中所有點(diǎn)對(duì)之間的相似度之和的比值。

其中，v、w分別表示群簇i和j中的節(jié)點(diǎn)，δvw表示其間的歐式距離，M表示點(diǎn)集中所有點(diǎn)對(duì)之間的相似度之和。根據(jù)式（2），可以構(gòu)建矩陣Dij。

其中，U表示整個(gè)點(diǎn)集。

定義ci為矩陣Dij中每行元素之和：

ci表示群簇i中的點(diǎn)與其他所有群簇中的點(diǎn)的相似度之和與點(diǎn)集中所有點(diǎn)對(duì)之間的相似度之和的比值。

由此得到S的表達(dá)式如下：

對(duì)于不同的點(diǎn)群集合，S值越大代表該集合的集聚性明顯（即有更為明顯的群簇結(jié)構(gòu)）。

2 基于集聚度S的空間聚類算法

基于模塊度的概念，Clauset等提出一個(gè)快速社區(qū)挖掘算法（CNM算法）［7］，該算法的思想是：初始時(shí)認(rèn)為每個(gè)節(jié)點(diǎn)就是一個(gè)社區(qū)，不斷地合并能得到模塊度值增加最大的兩個(gè)社區(qū)，直到網(wǎng)絡(luò)的模塊度值達(dá)到峰值。根據(jù)CNM算法，本文根據(jù)S值提出了一種空間聚類算法，基本思想是：首先將點(diǎn)集中每個(gè)節(jié)點(diǎn)看做一個(gè)群簇，如果合并兩個(gè)群簇i和j，則S的變化值為ΔSij：

因?yàn)镾值越大，表示聚類的結(jié)果越優(yōu)，所以合并的方向應(yīng)該沿著使ΔSij值最大的方向進(jìn)行，直到S值達(dá)到峰值停止合并過(guò)程。這種算法是一種基于貪婪算法思想的層次凝聚算法。具體步驟為：

（1）初始化，每個(gè)節(jié)點(diǎn)為一個(gè)獨(dú)立的群簇。讀取節(jié)點(diǎn)的坐標(biāo)，計(jì)算兩兩之間的距離和點(diǎn)集的直徑O，初始化Dij和ci如下：

（2）根據(jù)式（5）構(gòu)建初始ΔSij矩陣；

（3）選擇最大的ΔSij，合并相應(yīng)的群簇i和j，標(biāo)記合并后的群簇為j，同時(shí)更新ΔSij矩陣。在本文中，對(duì)于空間聚類，當(dāng)群簇i和群簇j合并，另一個(gè)群簇k與合并后的群簇之間的距離不是原本的dik與djk之和，而是k與合并后群簇的距離，為了簡(jiǎn)便，采取的是二者的均值，因此ΔSij矩陣中ΔS′jk更新為：

由式（9），更新矩陣的第j行和第j列元素，刪除i行i列的元素。

（4）記錄合并后的S值：

（5）重復(fù)步驟3、步驟4，直到歸并為一個(gè)群簇為止。

3 實(shí)驗(yàn)與討論

3.1 不同點(diǎn)集的S值對(duì)比實(shí)驗(yàn)

對(duì)于不同的空間點(diǎn)集，可以根據(jù)S值判斷其空間分布是否具有較強(qiáng)的集聚特性。圖3為實(shí)驗(yàn)的3種不同的空間點(diǎn)集經(jīng)過(guò)本文算法得到的S值。圖3a與圖3b均為20個(gè)點(diǎn)，但圖3b的空間集聚度高，它的S值為0.013，大于圖3a的0.0076；圖3b與圖3c相比，雖然圖3c空間點(diǎn)數(shù)目多（為30個(gè)），但二者集聚度相差不大。

為了提供對(duì)比，引入空間聚類中類內(nèi)方差（群內(nèi)所有點(diǎn)到其質(zhì)心的距離平方和）和類間方差（群簇的質(zhì)心之間的距離平方和）概念。在K－means算法中，類內(nèi)方差值作為準(zhǔn)則函數(shù)，在ward算法中，直接以類內(nèi)方差值的增量作為聚類統(tǒng)計(jì)量［8］。一類簇的緊湊程度可用類內(nèi)方差刻畫(huà)，而對(duì)于點(diǎn)集總體可以由類間方差與類內(nèi)方差之比來(lái)度量［9］，為了比較不同點(diǎn)集，用其均值之比來(lái)衡量。類內(nèi)均方差SSE和類間均方差SSB表達(dá)式為：

其中，N指點(diǎn)的總數(shù)，xT和yT是指類T的質(zhì)心坐標(biāo)，xC和yC是指整個(gè)點(diǎn)集的質(zhì)心坐標(biāo)，nT是指類T中的節(jié)點(diǎn)個(gè)數(shù)。

圖3中的3個(gè)點(diǎn)集都聚為3類時(shí)，類內(nèi)均方差和類間均方差以及類間均方差與類內(nèi)均方差的比值如表1所示。類間方差越大，類內(nèi)方差越?。幢戎翟酱螅﹦t聚類結(jié)果空間上集聚性越明顯。從表1看出，本文提出的集聚度S值與該比值一致，都反映出圖3b的集聚性最高，其次是圖3c。這同時(shí)也說(shuō)明，本文提出的集聚度S不僅僅與類內(nèi)的緊密度相關(guān)，也與類間的差異度相關(guān)，S值越大點(diǎn)集的群簇結(jié)構(gòu)越明顯。

圖3 空間點(diǎn)集及其S值Fig.3 Space point sets and their Svalues

表1 3幅圖對(duì)應(yīng)的SSE、SSB及SSB／SSETable 1 TheSSE，SSBandSSB／SSEvalues of the three datasets

3.2 空間聚類算法實(shí)驗(yàn)

本文首先用圖3a所示的空間點(diǎn)集對(duì)算法進(jìn)行實(shí)驗(yàn)，聚類過(guò)程中S值的變化曲線如圖4所示。發(fā)現(xiàn)S值并未出現(xiàn)與CNM算法中模塊度一樣的變化趨勢(shì)，而是一直增大，直到整個(gè)點(diǎn)集聚合為一類。

在CNM算法中，由于網(wǎng)絡(luò)的模塊度會(huì)隨著不斷合并而達(dá)到峰值，再繼續(xù)合并會(huì)帶來(lái)模塊度的下降，因此峰值就對(duì)應(yīng)著最優(yōu)的聚類結(jié)果。這是由于在復(fù)雜網(wǎng)絡(luò)中，有少部分節(jié)點(diǎn)的度很高，也有一些節(jié)點(diǎn)的度很小，它不是一個(gè)兩兩相連的完全耦合圖（如果網(wǎng)絡(luò)為規(guī)則圖形，則所有節(jié)點(diǎn)聚合為一個(gè)社區(qū)是最佳的聚類結(jié)果）。而本文中考慮的是點(diǎn)集中兩兩間的距離，相當(dāng)于將點(diǎn)集看作兩兩相連的網(wǎng)絡(luò)，因此根據(jù)模塊度的定義，其增量值必然不斷增大直到合并為一個(gè)群簇為止（圖5）。如此面臨和其他大多數(shù)空間聚類算法一樣的問(wèn)題：凝聚過(guò)程在何時(shí)停止獲得的是最優(yōu)結(jié)果。

圖4 算法過(guò)程中S值變化曲線Fig.4 The Svalue over the course of the algorithm

圖5 聚類過(guò)程的樹(shù)狀圖Fig.5 The dendrogram of the algorithm

基于這個(gè)問(wèn)題修改算法：當(dāng)兩點(diǎn)間的距離大于一定值時(shí)，其間沒(méi)有影響力，即沒(méi)有這種隱藏的邊相連接，這時(shí)δvw＝0。本文將該值作為點(diǎn)集中所有點(diǎn)到點(diǎn)集質(zhì)心的平均距離ˉd。同時(shí)不采用網(wǎng)絡(luò)直徑O，而是取小于ˉd的距離中的最大值。相應(yīng)地，修改O值為ˉd。具體修改后的算法為：

（1）初始化，每個(gè)節(jié)點(diǎn)為一個(gè)獨(dú)立的群簇。讀取節(jié)點(diǎn)的坐標(biāo)，計(jì)算兩兩之間的距離dij以及所有點(diǎn)到點(diǎn)集質(zhì)心的平均距離ˉd，初始化Dij和ci如下：

其中：

（2）根據(jù)式（5）構(gòu)建初始ΔSij矩陣；

（3）選擇最大的ΔSij，合并相應(yīng)的群簇i和j，標(biāo)記合并后的群簇為j，同時(shí)更新ΔSij矩陣。此時(shí)更新分為3種情況：群簇k和群簇i、j間的距離均小于ˉd；群簇k僅僅與群簇i的距離小于ˉd；群簇k僅僅與群簇j的距離小于ˉd。3種情況對(duì)應(yīng)的更新值如下：

由式（16），更新矩陣的第j行和第j列元素，刪除i行i列的元素。

（4）記錄合并后的S值：

（5）重復(fù)步驟3、步驟4，直到S值達(dá)到峰值為止。

如圖3a中的點(diǎn)集，點(diǎn)9（10，9.5）和11（16，4.5）之間的距離約為7.81，大于（約等于）7.768，定義其初始的Dij為0。根據(jù)修改后的算法，得到的S值的變化如圖6所示，在第17步合并時(shí)，S值達(dá)到峰值0.2206，這時(shí)對(duì)應(yīng)點(diǎn)集的最優(yōu)聚類結(jié)果（圖7），可以得到3個(gè)群簇。

圖6 算法過(guò)程中S值變化曲線Fig.6 The Svalue over the course of the algorithm

圖7 聚類過(guò)程的樹(shù)狀圖Fig.7 The dendrogram of the algorithm

綜上所述，S值的優(yōu)勢(shì)在于，對(duì)于不同的空間點(diǎn)集，可以比較它們的S值，其值越大代表該點(diǎn)集聚類特性越明顯。同時(shí)，S值的提出解決了空間系統(tǒng)聚類中聚合過(guò)程的有效終止時(shí)刻的問(wèn)題。最后，本文借鑒CNM算法提出的基于S值增量矩陣的快速聚類算法時(shí)間復(fù)雜度較低，經(jīng)過(guò)試驗(yàn)可以快速準(zhǔn)確地實(shí)現(xiàn)空間點(diǎn)聚類。

4 結(jié)語(yǔ)

本文借鑒了復(fù)雜網(wǎng)絡(luò)研究領(lǐng)域的概念，基于空間上事物越接近越相關(guān)的定律，將空間點(diǎn)集看做是有邊相連的網(wǎng)絡(luò)，邊表示其間的相關(guān)度，刻畫(huà)這種相關(guān)度值為距離的函數(shù)，從而提出了集聚度S值的概念，用于評(píng)價(jià)空間點(diǎn)集的群簇結(jié)構(gòu)。對(duì)于不同的空間點(diǎn)集，該值可以反映出其中哪個(gè)群簇結(jié)構(gòu)更加明顯?；赟值的增量矩陣，提出一個(gè)快速空間聚類算法能夠快速有效地挖掘出群簇結(jié)構(gòu)，且不用事先設(shè)定聚類個(gè)數(shù)。

本文還有值得深入研究之處。在算法中，合并兩個(gè)群簇，第3個(gè)群簇與合并后的群簇間的距離采用的是合并前的距離的均值，此處優(yōu)化為群簇間質(zhì)心的距離更為準(zhǔn)確。同時(shí)，還可以繼續(xù)探究其與經(jīng)典算法（如K－means、DBSCAN）相比的優(yōu)劣。

［1］ 郭仁忠.空間分析（第二版）［M］.北京：高等教育出版社，2001.93.

［2］ 羅可，蔡碧野，吳一帆，等.數(shù)據(jù)挖掘中聚類的研究［J］.計(jì)算機(jī)工程與應(yīng)用，2003（20）：182－184.

［3］ LLOYD S P.Least squares quantization in PCM［J］.IEEE Transactions on Information Theory，1982，28：128－137.

［4］ ESTER M，KRIEGEL H P，SANDER J，et al.A density－based algorithm for discovering clusters in large spatial databases［A］.Proceedings of the 2nd Internatinal Conference on KnowledgeDiscovery and Data Mining［C］.Amsterdam：Elsevier Science，1996.226－231.

［5］ NEWMAN M E J，GIRVAN M.Finding and evaluating community structure in networks［J］.Phys.Rev.E，2004，69（026113）.

［6］ BARABáSI A L.徐彬（譯）.Linked［M］.長(zhǎng)沙：湖南科學(xué)技術(shù)出版社，2007.8.

［7］ CLAUSET A，NEWMAN M E J，MOORE C.Finding community structure in very large networks［J］.Phys.Rev.E，2004，70（066111）.

［8］ TAN P N，STEINBACH M，KUMAR V.數(shù)據(jù)挖掘?qū)д摚ㄓ⑽陌妫跰］.北京：機(jī)械工業(yè)出版社，2010.523－524.

［9］ 孫吉貴，劉杰，趙連宇.聚類算法研究［J］.軟件學(xué)報(bào)，2008，19（1）：48－61.