一種基于多約束的空間聚類方法

劉啟亮，鄧 敏，石 巖，彭東亮

中南大學(xué)地球科學(xué)與信息物理學(xué)院，湖南長(zhǎng)沙410083

1 引 言

空間聚類是當(dāng)前地理空間數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)的一個(gè)重要手段［1－2］，旨在將空間數(shù)據(jù)庫(kù)中的實(shí)體劃分為一系列具有一定分布模式的空間簇，使得同一空間簇中的實(shí)體具有最大的相似度，不同空間簇中的實(shí)體具有最大差別。當(dāng)前，空間聚類已廣泛應(yīng)用于犯罪熱點(diǎn)分析［3］、地震空間分布模式挖掘［4］、制圖自動(dòng)綜合［5－6］、遙感影像分類［7］、公共設(shè)施選址［8］、地價(jià)評(píng)估以及時(shí)空建模［9－10］等諸多領(lǐng)域?？臻g聚類可以分為兩種形式，一種是完全依據(jù)實(shí)體間空間位置的接近程度進(jìn)行聚類；另一種是同時(shí)考慮實(shí)體間空間位置鄰近與專題屬性相似。如何適應(yīng)空間實(shí)體位置分布的復(fù)雜性是這兩種空間聚類問(wèn)題共同面臨的主要問(wèn)題。近年來(lái)國(guó)內(nèi)外學(xué)者曾對(duì)這一問(wèn)題分別進(jìn)行過(guò)研究［4，11－14］。通過(guò)分析，將空間實(shí)體位置分布的復(fù)雜性歸納為以下四個(gè)方面：① 空間密度分布不均勻問(wèn)題，一是不同密度的空間簇［12，13］，二是同一簇中密度不同［11，13］；② 空間簇位置關(guān)系的復(fù)雜性，一是密度相同或不同的空間簇鄰接［12，13］，如“頸問(wèn)題”［15］，二是兩個(gè)空間簇相互包含或咬合［11，14］；③ 噪聲問(wèn)題，一是背景噪聲［4］，二是鏈?zhǔn)絾?wèn)題［12－13］，又分單鏈與多鏈問(wèn)題；④ 空間簇的形態(tài)差異，包括空間簇形狀各異［4，11－14］與空間簇的大小差異［15］。此外，為了深入分析和挖掘地學(xué)空間數(shù)據(jù)庫(kù)中各要素間的關(guān)聯(lián)規(guī)則、分布特征及集聚模式等，在空間聚類過(guò)程中一方面需要能夠顧及空間實(shí)體間專題屬性的相似性［16－17］；另一方面，還需要盡可能少地涉及輸入?yún)?shù)的設(shè)置，以及具有較高的運(yùn)行效率［12，18］。

現(xiàn)有的空間聚類方法大致可以分為：① 劃分的方法［19－20］；② 層次的方法［3，21］；③ 基于密度的方法［11，18，22－23］；④ 基于圖論的方法［12－13，15］；⑤ 基于模型的方法［24－25］；⑥ 基于格網(wǎng)的方法［26］。劃分的方法對(duì)于體積相似、密度相似的球形簇聚類效果較好。但是，這類方法的聚類結(jié)果嚴(yán)重依賴初始聚類中心的選擇，難以發(fā)現(xiàn)任意形狀的空間簇，而且當(dāng)空間簇尺寸、密度變化較大時(shí)難以獲得滿意的聚類結(jié)果。傳統(tǒng)的層次聚類方法只適合發(fā)現(xiàn)球形的空間簇。改進(jìn)的層次空間聚類方法，如CURE使用代表點(diǎn)的策略雖然能夠發(fā)現(xiàn)較為復(fù)雜結(jié)構(gòu)的空間簇［21］，但是其依然無(wú)法發(fā)現(xiàn)任意形狀的空間簇，而且過(guò)多的輸入?yún)?shù)增加了算法的使用難度；傳統(tǒng)的密度聚類方法，如DBSCAN［18］由于采用固定閾值聚類，難以適應(yīng)空間實(shí)體密度的變化。改進(jìn)的密度方法［11，22－23］雖然能夠在一定程度上顧及空間實(shí)體密度的分異特性，然而對(duì)于空間簇鄰近等問(wèn)題依然難以很好解決?，F(xiàn)有基于圖論的聚類方法還不夠穩(wěn)健，容易受空間簇鄰接與密度變化的影響?；谀Ｐ偷姆椒?，需要預(yù)先假定空間數(shù)據(jù)的分布模型，這在某些實(shí)際應(yīng)用中難以準(zhǔn)確獲得?；诟窬W(wǎng)的方法雖然聚類效率得到提高，但是聚類質(zhì)量不高，且易遇到基于密度方法同樣的問(wèn)題［23］?，F(xiàn)有顧及專題屬性的空間聚類方法大致可以分為三類：① 在空間聚類過(guò)程中分別考慮空間鄰近域?qū)ｎ}屬性相似，這類方法多是直接在基于密度方法的基礎(chǔ)上顧及專題屬性的相似性［16，27－28］，與DBSCAN具有類似的缺陷，同時(shí)這類方法大多忽視了專題屬性空間分布的非均勻性與趨勢(shì)性，難以保證同一空間簇中的實(shí)體專題屬性相似；② 將空間屬性與專題屬性歸一化后加權(quán)融合構(gòu)造距離函數(shù)，再采用傳統(tǒng)聚類方法進(jìn)行聚類［9，17］，但是這類方法中空間屬性與專題屬性間權(quán)值的確定比較困難；③ 分別從空間屬性和專題屬性兩方面進(jìn)行聚類［10，29］，這類方法易受其使用的空間屬性聚類與專題屬性聚類方法局限性的影響。

綜上分析可以發(fā)現(xiàn)，分別從空間屬性與專題屬性兩個(gè)方面進(jìn)行聚類，可以適應(yīng)不同用途的空間聚類應(yīng)用且可操作性更強(qiáng)。實(shí)體間的空間鄰近關(guān)系的定義是空間聚類的核心問(wèn)題，Delaunay三角網(wǎng)是空間聚類中實(shí)體間鄰近關(guān)系表達(dá)的一種有效工具［3，12］，通過(guò)施加不同的距離約束去打斷一些不一致的長(zhǎng)邊，進(jìn)而獲得一系列不連續(xù)的子圖，每一個(gè)子圖視為一個(gè)空間簇。早期的基于Delaunay三角網(wǎng)的空間聚類方法［30］僅依靠從整體上刪除較長(zhǎng)的邊來(lái)進(jìn)行空間聚類操作，受空間實(shí)體密度變化與空間簇鄰近的影響較大。后來(lái)提出一些改進(jìn)的基于Delaunay三角網(wǎng)的空間聚類方法。例如，Amoeba算法［3］采取層次刪除長(zhǎng)邊的策略雖然可以發(fā)現(xiàn)任意形狀的空間簇，但是其依然難以解決“鏈?zhǔn)絾?wèn)題”以及空間簇鄰近問(wèn)題。Autoclust算法［12］采用多步驟刪除長(zhǎng)邊與短邊的方法雖然可以處理某些情況下的“鏈?zhǔn)絾?wèn)題”以及鄰接問(wèn)題，但是其結(jié)果并不穩(wěn)健。Triclust算法［31］采用多個(gè)統(tǒng)計(jì)量加權(quán)融合的策略刪除Delaunay三角網(wǎng)中的不一致邊，進(jìn)而實(shí)現(xiàn)空間聚類，然而不同統(tǒng)計(jì)量的權(quán)值確定比較困難。因此，現(xiàn)有基于Delaunay三角網(wǎng)的空間聚類方法僅依靠距離的約束并不能完全滿足復(fù)雜情況下的聚類操作，尤其是對(duì)于“頸問(wèn)題”、“鏈?zhǔn)絾?wèn)題”等情況，空間簇之間需要打斷的邊經(jīng)常并不是過(guò)長(zhǎng)或過(guò)短的邊，故僅采用距離約束并不能打斷這些邊，從而導(dǎo)致其存在一定局限。此外，這些方法無(wú)法顧及空間實(shí)體間專題屬性的相似性。為此，本文首先發(fā)展一種基于Delaunay三角網(wǎng)的自適應(yīng)的基于空間實(shí)體位置約束的聚類方法。通過(guò)對(duì)Delaunay三角網(wǎng)中的邊施加不同層次、不同類型的約束，獲得一系列離散的、由三角網(wǎng)的邊連接而成的空間簇；進(jìn)而，在每個(gè)簇中構(gòu)建實(shí)體間的空間鄰近關(guān)系；最后，將專題屬性間的相似度視為一種約束，對(duì)空間聚類結(jié)果進(jìn)行過(guò)濾，進(jìn)一步顧及實(shí)體間專題屬性的相似性。

2 基于多約束的空間聚類

本文的空間聚類方法分為兩個(gè)步驟：① 基于空間實(shí)體位置約束的聚類，獲得空間實(shí)體的空間分布模式及其空間鄰近關(guān)系；② 進(jìn)一步考慮實(shí)體間專題屬性的相似度，獲得最終的聚類結(jié)果。下面將針對(duì)這兩個(gè)步驟分別闡述。

2.1 基于空間實(shí)體位置約束的聚類

采取一種從整體到局部的層次約束策略對(duì)Delaunay三角網(wǎng)的邊施加距離約束，進(jìn)而，發(fā)展一種方向約束指標(biāo)，用來(lái)提取空間實(shí)體間局部的聚集趨勢(shì)。首先，仿照文獻(xiàn)［3］中的層次邊長(zhǎng)約束策略來(lái)定義整體約束條件，具體表達(dá)如下。

定義1 整體約束條件：給定包含n個(gè)空間實(shí)體的空間數(shù)據(jù)集SDB，DT表示n個(gè)空間實(shí)體生成的Delaunay三角網(wǎng)。對(duì)于任一空間實(shí)體p，其直接Delaunay鄰近實(shí)體表示為NN（p），CGlobal（p）表示與空間實(shí)體p連接的所有邊的整體約束條件，表示為

式中，Mean（DT）表示三角網(wǎng)的平均邊長(zhǎng)；SD（DT）表示三角網(wǎng)所有邊的標(biāo)準(zhǔn)差；NI（p）表示噪聲點(diǎn)指數(shù)；Mean（p）表示與空間實(shí)體p連接的所有邊的平均值；α表示調(diào)節(jié)系數(shù)，默認(rèn)設(shè)為1。

針對(duì)任一空間實(shí)體p，若與其直接相連接的邊的長(zhǎng)度大于整體約束條件，則刪除該邊。圖1（b）為經(jīng)過(guò)整體約束條件刪減后的結(jié)果?？梢园l(fā)現(xiàn)，整體上分異較為明顯的空間聚集現(xiàn)象及噪聲點(diǎn)已經(jīng)很好地被區(qū)分，起到了整體約束的效果。其中α可以用于調(diào)節(jié)整體約束條件的嚴(yán)格程度，α越大，則整體約束條件的敏感性較低，較多的長(zhǎng)邊將會(huì)被保留；α越小，整體約束條件越嚴(yán)格，可能分割整體上的聚集現(xiàn)象。據(jù)文獻(xiàn)［3］，通過(guò)試驗(yàn)證明α可以默認(rèn)地設(shè)為1。

圖1 空間數(shù)據(jù)聚類與空間鄰近關(guān)系建立Fig.1 Spatial data clustering and the construction of spatial proximity relationship

定義2 K階鄰近：給定一個(gè)圖G，p為G的一個(gè)頂點(diǎn)，則任意一個(gè)到p的路徑小于或等于K的頂點(diǎn)與p之間滿足K階鄰近關(guān)系；所有與p滿足K階鄰近關(guān)系的頂點(diǎn)構(gòu)成了p的K階鄰域。

本文將一個(gè)實(shí)體的二階鄰域視為一個(gè)局部空間實(shí)體集，進(jìn)一步給出局部約束條件。

定義3 局部約束條件：SG＝｛G1，G2，…，Gm｝為SDB中的所有空間實(shí)體在整體約束條件下劃分得到的m個(gè)圖，任一空間實(shí)體p的二階鄰域表示為NN2（p）。針對(duì)包含k個(gè)空間實(shí)體的圖Gi，p表示圖Gi中的任一頂點(diǎn)，CLocali（p）表示p的二階鄰域范圍內(nèi)所有邊的局部約束條件，表達(dá)為

式中，Mean（NN2（p））表示圖Gi中，p的二階鄰域內(nèi)所有邊的平均值；SD（pj）為圖Gi中，pj的一階鄰域內(nèi)所有邊的標(biāo)準(zhǔn)差；Mean（SDi）表示圖Gi中，所有實(shí)體的一階鄰域內(nèi)邊長(zhǎng)標(biāo)準(zhǔn)差的平均值；β表示調(diào)節(jié)系數(shù)，默認(rèn)條件下設(shè)為1。

針對(duì)圖Gi中的任一頂點(diǎn)p，若其二階鄰域內(nèi)的任一邊的長(zhǎng)度大于局部約束條件，則將其刪除。分析式（3）和式（4）可以發(fā)現(xiàn)，局部約束條件實(shí)際上是傳統(tǒng)的“k倍標(biāo)準(zhǔn)差統(tǒng)計(jì)準(zhǔn)則”的變種，β值超過(guò)2時(shí)，局部約束條件敏感性降低僅可能打斷整體的長(zhǎng)邊；β值過(guò)?。ㄐ∮?）時(shí)，局部約束過(guò)于嚴(yán)格，將會(huì)產(chǎn)生過(guò)多的小簇，因此β一般設(shè)為1～2之間，可以默認(rèn)設(shè)為1。圖1（c）為經(jīng)過(guò)局部約束條件進(jìn)行刪邊后的結(jié)果，下部的兩個(gè)球型簇A、B與簇C之間的局部長(zhǎng)邊被很好地打斷。經(jīng)過(guò)整體與局部約束，Delaunay三角網(wǎng)中的長(zhǎng)邊可以有效被打斷。但是，某些不一致的邊仍然存在，如圖1（c），A、B兩簇之間形成的“頸”。為此，本文發(fā)展一種方向約束條件來(lái)解決這種“頸問(wèn)題”與“鏈?zhǔn)絾?wèn)題”。主要思想可以描述為：空間實(shí)體間的相互作用可以借助一種凝聚力的形式來(lái)表達(dá)，即空間實(shí)體間的相互作用與它們之間的空間距離的平方滿足反比關(guān)系，實(shí)體間距離越遠(yuǎn)，其相互之間的凝聚力作用越小。Delaunay三角網(wǎng)確定的鄰接關(guān)系可以用來(lái)約束實(shí)體間凝聚力的作用范圍，即一個(gè)空間實(shí)體只與其直接Delaunay鄰近實(shí)體間具有凝聚力作用，與其他實(shí)體間的凝聚力作用可以忽略，進(jìn)而空間實(shí)體間的凝聚力作用可以仿照萬(wàn)有引力的形式表達(dá)為

式中，k為凝聚力常數(shù)，本文設(shè)為1；mp、mqi為實(shí)體p、qi的質(zhì)量，考慮到可以將空間點(diǎn)實(shí)體均視為單位質(zhì)點(diǎn)，故令mp、mqi均為1；d（p，qi）為實(shí)體p與qi的歐氏距離；epqi為p指向qi的單位矢量。

進(jìn)而，針對(duì)任一空間實(shí)體p，其直接Delaunay鄰近域內(nèi)其他實(shí)體對(duì)p的凝聚力合力可以表達(dá)為

因此，三角網(wǎng)的每條邊可以抽象為一條力的作用線，每個(gè)空間實(shí)體受到的合力方向反映其自然的聚集趨勢(shì)，故方向約束條件可以進(jìn)行如下定義。

定義4 方向約束條件：針對(duì)任一空間實(shí)體p，qi∈NN（p），若qi與p通過(guò)公共邊連接，則必須滿足

式中，CDirection（p）表示實(shí)體p與其直接Delaunay鄰近實(shí)體間的方向約束條件；θ（FT（p）、F（p，qi））表示凝聚合力與凝聚分力的矢量夾角。

方向約束主要是基于物理學(xué)中力的合成與分解原理來(lái)建立的。若分力與合力的夾角方向小于90°，則說(shuō)明該分力對(duì)合力方向有貢獻(xiàn)，空間實(shí)體在合力的作用下將具有趨向力源（即產(chǎn)生這些分力的實(shí)體）聚集的趨勢(shì)；若分力與合力的夾角方向大于90°，則該分力對(duì)合力方向有削弱作用，空間實(shí)體將有背離產(chǎn)生這些分力的實(shí)體的趨勢(shì)。據(jù)此可以對(duì)一些較為復(fù)雜的“頸”或“鏈”問(wèn)題進(jìn)行區(qū)分，下面通過(guò)一個(gè)實(shí)例來(lái)說(shuō)明方向約束的應(yīng)用。

圖2（a）為圖1（a）中虛線框部分的放大顯示，是一種典型的“頸問(wèn)題”。選取圖2（a）中虛線框中部分實(shí)體進(jìn)行分析，圖2（b）為其放大顯示的情況，A、B兩個(gè)空間簇被短邊p1p2、p1p3形成的“頸”連接起來(lái)，從而無(wú)法分離。FT（p1）、FT（p2）、FT（p3）分別為實(shí)體p1、p2、p3所受的凝聚合力方向（合力的作用線只表示方向不表示標(biāo)量的大小）。以空間實(shí)體p1為例，p1在合力FT（p1）的作用下有向?qū)嶓wq1、q2、q3聚集的局部趨勢(shì)，同理p3將向q5、q6、q7聚集，p2則趨向于p3、q4、q5，依據(jù)方向約束條件p1、p2、p3之間構(gòu)成的“頸”可以進(jìn)行自然地區(qū)分。這種策略同樣也適用于“鏈?zhǔn)絾?wèn)題”的解決。如圖1（d）所示，A、B兩個(gè)簇經(jīng)過(guò)方向約束條件后，很好地進(jìn)行了區(qū)分。

圖2 方向約束簡(jiǎn)例Fig.2 Example of directional constraint

經(jīng)過(guò)以上三個(gè)步驟后，所有通過(guò)公共邊連接的空間實(shí)體即構(gòu)成一個(gè)簇，如圖1（d）所示。在此基礎(chǔ)上，可以借助Delaunay三角網(wǎng)來(lái)構(gòu)建實(shí)體間的鄰近關(guān)系。具體方法為：在各個(gè)簇中依據(jù)整體約束條件刪邊后的實(shí)體間的連接關(guān)系，采用放寬的局部約束條件刪除各個(gè)簇邊界處的長(zhǎng)邊，具有公共邊的空間實(shí)體被定義為互相鄰近。由于在聚類過(guò)程中，局部約束條件較為嚴(yán)格，在各個(gè)簇內(nèi)部可能打斷了部分整體上并不顯著的局部長(zhǎng)邊，如圖1（c）所示。因此，在構(gòu)建實(shí)體間鄰近關(guān)系時(shí)，通過(guò)增大β值，放寬了局部約束條件。如前文所述，當(dāng)β值設(shè)為2～3時(shí)，局部約束條件僅可能打斷整體的長(zhǎng)邊，可以有效避免邊界長(zhǎng)邊的干擾，如圖1（e）所示，其中在構(gòu)建實(shí)體間空間關(guān)系時(shí)均將β設(shè)為2。

2.2 基于空間實(shí)體位置和專題屬性約束的空間聚類

基于空間實(shí)體位置約束的空間聚類過(guò)程能夠獲得：① 實(shí)體的空間分布模式；② 實(shí)體間的空間鄰近關(guān)系。進(jìn)一步，需要在每個(gè)空間簇中考慮鄰近實(shí)體間專題屬性的約束。通?？臻g實(shí)體的專題屬性在空間上的分布是非均勻的，且經(jīng)常帶有某種趨勢(shì)性，如我國(guó)的氣溫分布從南到北有比較明顯的漸變趨勢(shì)，這些特點(diǎn)在聚類中必須予以充分的考慮。為此，下面引入直接專題屬性距離可達(dá)與間接專題屬性距離相連的概念。

定義5 直接專題屬性距離可達(dá)：對(duì)于空間實(shí)體p1、p2，若二者之間具有公共邊，且dAttr（p1，p2）≤εdirect，則稱p1、p2專題屬性距離可達(dá)，記為p1?p2。其中，dAttr（p1，p2）表示實(shí)體p1、p2間的專題屬性差異，為各維專題屬性分別歸一化后的歐式距離，具體操作與文獻(xiàn)［17］中的方法相同；εdirect表示專題屬性差異最小閾值。

定義6 間接專題屬性距離相連：對(duì)于空間實(shí)體集合S＝｛p1，p2，p3，…，pi－1｝，若dAttr（Avg（p1，p2，…，pi－1），pi）≤εindirect，則稱S、pi間接專題屬性距離相連，記為S⊕pi。其中，Avg（p1，p2，…，pi－1）表示實(shí)體p1，p2，…，pi－1的專題屬性平均值；εindirect表示間接專題屬性距離最小閾值。

顧及專題屬性聚類時(shí)，選取任一空間實(shí)體pi，采用鄰域擴(kuò)張的策略，依次將1階、2階、…、K階鄰近域內(nèi)所有同時(shí)滿足與pi直接專題屬性距離可達(dá)與間接專題屬性距離相連的實(shí)體歸為一類，不能歸入任何簇的空間實(shí)體被標(biāo)識(shí)為異常點(diǎn)，直到所有空間實(shí)體或被歸入某個(gè)空間簇或被標(biāo)識(shí)為異常點(diǎn)時(shí)，聚類終止。其中閾值參數(shù)εdirect和εindirect的設(shè)置類似于文獻(xiàn)［16］，即設(shè)為最鄰近實(shí)體專題屬性差異的平均值。可見(jiàn)，專題屬性聚類過(guò)程中既顧及了直接空間鄰近實(shí)體間的專題屬性差異又加入了與整體差異的約束，故能夠有效避免專題屬性在空間上的漸變?cè)斐傻挠绊憽?/p>

3 試驗(yàn)分析

為了驗(yàn)證本文方法的有效性與優(yōu)越性，共設(shè)計(jì)了兩組試驗(yàn)。試驗(yàn)1采用如圖3（a）所示在Arcgis 9.2中生成的模擬數(shù)據(jù)庫(kù)，其中包括了常見(jiàn)的“點(diǎn)云”等不均勻的空間簇；試驗(yàn)2采用兩組實(shí)際數(shù)據(jù)，一組是我國(guó)西南地區(qū)的地震空間分布數(shù)據(jù)，另一組為我國(guó)陸地區(qū)域49年年平均氣溫監(jiān)測(cè)數(shù)據(jù)。所有試驗(yàn)中，本文方法的各個(gè)調(diào)節(jié)系數(shù)均為默認(rèn)值，即α＝1，施加局部約束時(shí)β＝1，構(gòu)建空間鄰近關(guān)系時(shí)β＝2。

3.1 模擬試驗(yàn)

本文方法針對(duì)模擬數(shù)據(jù)庫(kù)的聚類結(jié)果如圖3（b）所示，圖3（c）～圖3（f）分別給出了K－means、Amoeba、DBSCAN以及Autoclust四種算法的聚類結(jié)果?？梢园l(fā)現(xiàn)本文方法的兩個(gè)重要特點(diǎn)：① 可以有效適應(yīng)空間實(shí)體密度不均勻情況下的空間聚類操作，針對(duì)點(diǎn)云的情況（簇9和 10）雖然在邊緣處產(chǎn)生個(gè)別小簇，但空間簇的主體結(jié)構(gòu)仍可以有效識(shí)別；② 可以有效發(fā)現(xiàn)空間上鄰近的空間簇，如簇1、簇2、簇3。而其他經(jīng)典方法：①K－means算法對(duì)復(fù)雜形狀的空間簇聚類結(jié)果較差，如圖3（c），簇3被錯(cuò)誤劃分為3個(gè)簇；②Amoeba算法受“鏈?zhǔn)絾?wèn)題”與空間簇鄰接問(wèn)題的影響較大，如圖3（d），由于“鏈”和“頸”的影響，簇1、簇2、簇3無(wú)法分離，空間簇中實(shí)體的分布存在一定差異時(shí)，Amoeba算法容易將其錯(cuò)誤分割，如圖3（d），簇4和簇5的情況；③當(dāng)空間實(shí)體密度差異較大時(shí)，DBSCAN算法聚類效果較差，如圖3（e），簇6、簇7、簇8被錯(cuò)誤歸為一類，DBSCAN算法同樣受“鏈?zhǔn)絾?wèn)題”與空間簇鄰接問(wèn)題的影響較大，如圖3（e），簇1、簇2、簇3無(wú)法區(qū)分；④Autoclust算法僅依靠距離約束的策略受“短鏈”和“頸問(wèn)題”影響較大，如圖3（f），簇1與簇3間的“短鏈”無(wú)法移除，簇1和簇2無(wú)法正確區(qū)分，同時(shí)Autoclust算法可能對(duì)一些分布不均勻的空間簇進(jìn)行錯(cuò)誤分割，如圖3（f），簇5被錯(cuò)誤分成兩部分。本文方法比傳統(tǒng)方法更具優(yōu)勢(shì)的主要原因在于，其顧及了地理現(xiàn)象由整體到局部的層次關(guān)系，采取針對(duì)性的約束條件進(jìn)行聚類，而傳統(tǒng)方法如K－means與DBSCAN實(shí)際上是基于全局參數(shù)的，忽視了局部的差異性［3］；Amoeba與Autoclust將整體與局部影響進(jìn)行融合的策略，缺乏層次性與針對(duì)性，導(dǎo)致算法的不穩(wěn)健。

圖3 模擬數(shù)據(jù)庫(kù)聚類結(jié)果（×——孤立點(diǎn)）Fig.3 Spatial clustering results of simulated datasets（×—outlier）

3.2 實(shí)際算例

下面分別采用本文方法進(jìn)行地震數(shù)據(jù)空間分布模式挖掘與我國(guó)陸地區(qū)域氣溫分布模式挖掘。圖4（a）顯示了根據(jù)文獻(xiàn)［32］整理后的我國(guó)西南地區(qū)（92°E～104°E，21°N～38°N）1970—2004年的134次5級(jí)以上強(qiáng)震的空間分布?？臻g聚類的具體步驟如圖4（b）～（d）所示，空間聚類的結(jié)果如圖4（e）所示，從圖中可以比較明顯地發(fā)現(xiàn)A、B、C、D、E等五條線性地震帶，與該地區(qū)大的活躍斷層構(gòu)造十分吻合，如A簇主要位于祁連山斷層，D簇主要位于麗江—小金河斷裂帶上，E簇主要位于小江斷裂帶［32－33］；同時(shí)可以發(fā)現(xiàn)Ⅰ、Ⅱ、Ⅲ等三個(gè)地震叢簇結(jié)構(gòu)，主要位于川滇菱形塊體區(qū)域［32］，反映了不同方向的斷層構(gòu)造相互作用的結(jié)果。聚類結(jié)果與文獻(xiàn)［32］中的研究結(jié)論非常吻合，充分證明了所提出的空間聚類方法在挖掘地震數(shù)據(jù)空間分布模式中的有效性，可以進(jìn)一步用于識(shí)別該區(qū)域的活動(dòng)斷層構(gòu)造。

圖4 地震數(shù)據(jù)空間分布模式挖掘（×——孤立點(diǎn)）Fig.4 Discovery of spatial patterns in seismic database（×—outlier）

進(jìn)而，顧及空間實(shí)體的專題屬性挖掘我國(guó)陸地區(qū)域49年（1960—2008）年平均氣溫的空間分布模式。采用國(guó)家氣象局提供的我國(guó)187個(gè)氣象站的氣溫監(jiān)測(cè)數(shù)據(jù)，每個(gè)站點(diǎn)的主要屬性包括：站點(diǎn)經(jīng)緯度坐標(biāo)，高程，年平均氣溫，建站時(shí)間與站點(diǎn)名。同時(shí)與一種基于雙重距離的空間聚類算法DDBSC進(jìn)行比較。圖5（a）～（d）顯示本文方法聚類的具體過(guò)程，聚類最終結(jié)果如圖5（d）所示。這里εdirect、εindirect均設(shè)為氣象站氣溫最鄰近差異的平均值［16］。分析聚類結(jié)果可以發(fā)現(xiàn)，圖5（d）中由南到北分布的1～8等8個(gè)主要空間簇中其平均氣溫（單位：攝氏度）分別為：24.5、21.7、16.9、10.5、8.8、5.4、3.3、－0.4，較為準(zhǔn)確地反應(yīng)了我國(guó)氣溫由南到北逐漸降低的實(shí)際情況，與現(xiàn)有的研究結(jié)論相符。DDBSC算法的聚類結(jié)果如圖5（e）所示，可以發(fā)現(xiàn)DDBSC算法從南到北識(shí)別了一個(gè)條形的空間簇A，顯然與實(shí)際情況不符。這主要由于我國(guó)氣溫分布由南到北具有漸變性，鄰近站點(diǎn)間的差異不大，然而這種差異的積累導(dǎo)致同一空間簇中實(shí)體間專題屬性的差異性較大。由此亦可說(shuō)明，本文提出的間接專題屬性可達(dá)與K階鄰域擴(kuò)張聚類策略的必要性與實(shí)用性。進(jìn)一步，可以應(yīng)用本文的聚類結(jié)果研究局部地區(qū)氣溫的突變性與差異性，對(duì)研究我國(guó)氣候演變規(guī)律具有重要意義。

圖5 氣溫?cái)?shù)據(jù)空間分布模式挖掘（×——孤立點(diǎn)）Fig.5 Discovery of spatial patterns in temperature database（×—outlier）

4 結(jié)論與展望

提出一種基于多約束的空間聚類新方法，通過(guò)施加不同層次、不同類型的約束可以適應(yīng)復(fù)雜情況的空間聚類分析。通過(guò)模擬試驗(yàn)與實(shí)際算例分析可以發(fā)現(xiàn)：① 本文方法可以適應(yīng)空間數(shù)據(jù)分布不均勻、空間簇形態(tài)各異、位置鄰近等復(fù)雜情況下的聚類，同時(shí)對(duì)各種噪聲影響較為穩(wěn)??；② 聚類輸入?yún)?shù)較少，有利于用戶實(shí)際使用；③ 聚類結(jié)果可以同時(shí)滿足空間簇中實(shí)體既空間鄰近又專題屬性相似的要求。

進(jìn)一步的研究工作主要集中在：① 研究空間聚類結(jié)果的定量評(píng)價(jià)方法。目前尚沒(méi)有一種有效的評(píng)價(jià)指標(biāo)能夠準(zhǔn)確地對(duì)空間聚類結(jié)果進(jìn)行定量評(píng)價(jià)［34］，因此本文對(duì)聚類結(jié)果的評(píng)價(jià)主要依賴已有研究論斷與先驗(yàn)知識(shí)；② 研究專題屬性參數(shù)的自動(dòng)確定方法，采用文獻(xiàn)［16］中的設(shè)置方法實(shí)際上是一種全局的策略，在專題屬性空間分布不均勻的情況可能存在一定誤差，需要進(jìn)一步顧及專題屬性分布的局部特征。

［1］ MILLER H，HAN J.Geographic Data Mining and Knowledge Discovery［M］.2nd ed.London：CRC Press，2009.

［2］ LI Deren，WANG Shuliang，LI Deyi，et al.Theories and Technologies of Spatial Data Mining and Knowledge Discovery［J］.Geomatics and Information Science of Wuhan University，2002，27（3）：221－233.（李德仁，王樹良，李德毅，等.論空間數(shù)據(jù)挖掘和知識(shí)發(fā)現(xiàn)的理論和方法［J］.武漢大學(xué)學(xué)報(bào)：信息科學(xué)版，2002，27（3）：221－233.）

［3］ ESTIVILL－CASTRO V，LEE I.Multi－level Clustering and Its Visualization for Exploratory Spatial Analysis［J］.GeoInformatica，2002，6（2）：123－152.

［4］ PEI T，ZHU A X，ZHOU C H，et al.A New Approach to the Nearest－neighbor Method to Discover Cluster Features in Overlaid Spatial Point Processes［J］.International Journal of Geographical Information Science，2006，20（2）：153－168.

［5］ WU Fang，QIAN Haizhong，DENG Hongyan，et al.Spatial Information Intelligence Management Aims to Map Automatic Generalization［M］.Beijing：Science Press，2008.（武芳，錢海忠，鄧紅艷，等.面向地圖自動(dòng)綜合的空間信息智能處理［M］.北京：科學(xué)出版社，2008.）

［6］ GUO Q S，ZHENG C Y，HU H K.Hierachical Clustering Method of Group of Pionts Based on the Neighborhood Graph［J］.Acta Geodaetica et Cartographica Sinica，2008，37（2）：256－261.（郭慶勝，鄭春燕，胡華科.基于鄰近圖的點(diǎn)群層次聚類方法的研究［J］.測(cè)繪學(xué)報(bào)，2008，37（2）：256－261.）

［7］ LUO Jiacheng，LIANG Yi，ZHOU Chenghu.Scale Space Based Hierarchical Clustering Method and Its Application to Remotely Sensed Data Classification［J］.Acta Geodaetica et Cartographica Sinica，1999，28（4）：319－314.（駱劍承，梁怡，周成虎.基于尺度空間的分層聚類方法及其在遙感影像分類中的應(yīng)用［J］測(cè)繪學(xué)報(bào)，1999，28（4）：319－314.）

［8］ MAO Zhengyuan，LI Lin.The Measure of Spatial Patterns and Its Applications［M］.Beijing：Science Press，2004.（毛政元，李霖.空間模式的測(cè)度及其應(yīng)用［M］.北京：科學(xué)出版社，2004.）

［9］ JIAO Limin，LIU Yaolin，LIU Yanfang.Spatial Autocorrelation Patterns of Datum Land Price of Cities in a Region［J］.Geomatics and Information Science of Wuhan University，2009，34（7）：873－877.（焦利民，劉耀林，劉艷芳.區(qū)域城鎮(zhèn)基準(zhǔn)地價(jià)水平的空間自相關(guān)格局分析［J］.武漢大學(xué)學(xué)報(bào)：信息科學(xué)版，2009，34（7）：873－877.）

［10］ WANG Haiqi，WANG Jinfeng.Local Neural Networks of Space－time Modeling Based on Partitioning for Lattice Data in GIS［J］.Journal of Remote Sensing，2008，12（5）：707－715.（王海起，王勁峰.基于分區(qū)的局域神經(jīng)網(wǎng)絡(luò)時(shí)空建模方法研究［J］.遙感學(xué)報(bào)，2008，12（5）：707－715.）

［11］ NOSOVSKIY G V，LIU D，SOURINA O.Automatic Clustering and Boundary Detection Algorithm Based on Adaptive Influence Function［J］.Pattern Recognition，2008，41（9）：2757－2776.

［12］ ESTIVILL－CASTRO V，LEE I.Argument Free Clustering for Large Spatial Point－data Sets［J］.Computers，Environment and Urban Systems，2002，26（4）：315－334.

［13］ ZHONG C，MIAO D Q，WANG R Z.A Graph－theoretical Clustering Method Based on Two Rounds of Minimum Spanning Trees［J］.Pattern Recognition，2010，43（3）：752－766.

［14］ HANDL J，KNOELES J.An Evolutionary Approach to Multiobjective Clustering［J］.IEEE Transactions on Evolutionary Computation，2007，11（1）：56－76.

［15］ ZAHN C T.Graph－theoretical Methods for Detecting and Describing Gestalt Clusters［J］.IEEE Transaction on Computers，1971，C20（1）：68－86.

［16］ LI Guangqiang，DENG Min，CHENG Tao，et al.A Dual Distance Based Spatial Clustering Method［J］.Acta Geodaetica et Cartographica Sinica，2008，37（4）：482－488.（李光強(qiáng)，鄧敏，程濤，等.一種基于雙重距離的空間聚類方法［J］.測(cè)繪學(xué)報(bào)，2008，37（4）：482－488.）

［17］ LI Xinyun，ZHENG Xinqi，YAN Hongwen.On Spatial Clustering of Combination of Coordinate and Attribute［J］.Geography and Geo－Information Science，2004，20（2）：38－40.（李新運(yùn)，鄭新奇，閆弘文.坐標(biāo)與屬性一體化的空間聚類方法研究［J］.地理與地理信息科學(xué)，2004，20（2）：38－40.）

［18］ ESTER M，KRIEGEL H P，SANDER J，et al.A Density－based Algorithm for Discovering Clusters in Large Spatial Databases with Noise［C］∥Proceeding of the 2nd the International Conference on Knowledge Discovery and Data Mining.Portland：AAAI Press，1996：226－231.

［19］ MACQUEEN J.Some Methods for Classification and Analysis of Multivariate Observations［C］∥Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability.Berkeley：University of California Press，1967：281－297.

［20］ NG R T，HAN J.Efficient and Effective Clustering Method for Spatial Data Mining［C］∥Proceedings of the 20th International Conference on Very Large Data Bases.San Francisco：Morgan Kaufmann Publishers Inc，1994：144－155.

［21］ GUHA S，RASTOGI R，SHIM K.CURE：An Efficient Clustering Algorithm for Large Databases［C］∥Proceedings of 1998ACM－SIGMOD International Conference on Management of Data.New York：ACM，1998：73－84.

［22］ LI Guangqiang，DENG Min，LIU Qiliang，et al.A Spatial Clustering Method Adaptive to Local Density Change［J］.Acta Geodaetica et Cartographica Sinica，2009，38（3）：255－263.（李光強(qiáng)，鄧敏，劉啟亮，等.一種適應(yīng)局部密度變化的空間聚類方法［J］.測(cè)繪學(xué)報(bào)，2009，38（3）：255－263.）

［23］ PEI T，JASRA A，HAND D J，et al.DECODE：A New Method for Discovering Clusters of Different Densities in Spatial Data［J］.Data Mining and Knowledge Discovery，2009，18（3）：337－369.

［24］ DEMPSTER A，LAIRD N，RUBIN D.Maximum Likelihood from Incomplete Data via the EM Algorithm［J］.Journal of the Royal Statistical Society：Series B，1977，39（1）：1－38.

［25］ XU X W，ESTER M，KRIEGE H P，et al.A Distributionbased Clustering Algorithm for Mining in Large Spatial Databases［C］∥Proceedings of the 14th International Conference on Data Engineering.Washington：IEEE Computer Society，1998，324－331.

［26］ WANG W，YANG J，MUNTZ R.STING：A Statistical Information Grid Approach to Spatial Data Mining［C］∥Proceedings of the 23rd International Conference on Very Large Data Bases.San Francisco：Morgan Kaufmann Publishers Inc，1997：186－195.

［27］ ZHOU J G，GUAN J H，LI P X.DCAD：A Dual Clustering Algorithm for Distributed Spatial Databases［J］.Geo－spatial Information Science，2007，10（2）：137－144.

［28］ BIRANT D，KUT A.ST－DBSCAN：An Algorithm for Clustering Spatial－temporal Data［J］.Data ＆Knowledge Engineering，2007，60（1）：208－221.

［29］ LIN C R，LIU K H，CHEN M S.Dual Clustering：Integrating Data Clustering over Optimization and Constraint Domains［J］.IEEE Transactions on Knowledge and Data Engineering，2005，17（5）：628－637.

［30］ KANG I，KIM T，LI K.A Spatial Data Mining Method by Delaunay Triangulation［C］∥Proceedings of the 5th ACM international workshop on Advances in geographic information systems.New York：ACM，1997：35－39.

［31］ LIU D，NOSOVSKIY G V，SOURINA O.Effective Clustering and Boundary Detection Algorithm Based on Delaunay Triangulation［J］.Pattern Recognition Letters，2008，29（9）：1261－1273.

［32］ JIANG Haikun，LI Yongli，QU Yanjun，et al.Spatial Distribution Features of Sequence Types of Moderate and Strong Earthquakes in Chinese Mainland［J］.Acta Seismologica Sinica，2006，28（4）：389－398.（蔣海昆，李永莉，曲延軍，等.中國(guó)大陸中強(qiáng)地震序列類型的空間分布特征［J］.地震學(xué)報(bào)，2006，28（4）：389－398.）

［33］ HUANG Fugang，LI Zhonghua，QIN Jiazheng，et al.Correlation of Seismicity in Sichuan－Yunnan Rhombic Block［J］.Journal of Seismological Research，2007，30（3）：205－209.（皇甫崗，李忠華，秦嘉政，等.川滇菱形塊體強(qiáng)震活動(dòng)關(guān)聯(lián)分析［J］.地震研究，2007，30（3）：205－209.）

［34］ YUE S Y，WANG J S，WU T，et al.A New Separation Measure for Improve the Effectiveness of Validity Indices［J］.Information Sciences，2010，180（5）：748－764.