空間層次聚類顯著性判別的重排檢驗方法

唐建波，劉啟亮，鄧　敏，黃金彩，蔡建南

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

?

空間層次聚類顯著性判別的重排檢驗方法

唐建波，劉啟亮，鄧敏，黃金彩，蔡建南

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

Foundation support： The National Natural Science Foundation of China (Nos.41471385;41171351);Open Research Fund Program of Key Laboratory of Digital Mapping and Land Information Application Engineering, NASG(No.GCWD201401); Fundamental Research Funds for the Central Universities of Central South University(No.2013zzts247)

摘要：同時顧及空間鄰近與專題屬性相似的空間層次聚類是挖掘空間分布模式的一種有效手段。空間層次聚類方法雖然可以獲得多層次的聚集結(jié)構(gòu)，但聚類結(jié)果顯著性的統(tǒng)計判別依然是一個尚未解決的難題。為此，本文提出了一種空間層次聚類結(jié)果顯著性的統(tǒng)計判別方法，用于確定空間層次聚類的停止準則，減少聚類過程對參數(shù)設(shè)置的依賴。通過試驗分析與比較發(fā)現(xiàn)，該方法能夠有效判別空間層次聚類結(jié)果的顯著性和確定層次聚類合并過程的停止條件，同時具有很好的抗噪性，避免隨機結(jié)構(gòu)的干擾。

關(guān)鍵詞：空間層次聚類；顯著性；空間分布模式；重排檢驗

空間聚類是一種重要的空間數(shù)據(jù)探索性分析手段，能夠有效挖掘地理現(xiàn)象的空間分布模式[1-3]。根據(jù)空間聚類是否顧及實體的專題屬性，可以將空間聚類大致分為兩種類型[4]：一種是只依據(jù)實體間空間位置的接近程度進行聚類，另一種是同時考慮實體間空間位置毗鄰和專題屬性相近。前一類空間聚類問題最先得到關(guān)注，并已經(jīng)提出了一些較為成熟的空間聚類模型，如基于鄰近圖的方法[5]、局部密度自適應(yīng)的方法[6-7]及基于神經(jīng)網(wǎng)絡(luò)的方法[8]等。然而，相比前一種聚類任務(wù)，顧及專題屬性的空間聚類方法在挖掘空間分布模式時更具實際意義，且更為復(fù)雜，已經(jīng)成為當(dāng)前空間聚類分析研究中的一個重點[9-11]。

空間層次聚類是目前使用最為廣泛的一種顧及專題屬性的空間聚類方法[12-13]，可以獲得多層次的聚集結(jié)構(gòu)，但聚類結(jié)果顯著性(或?qū)哟魏喜⒔刂箺l件)的統(tǒng)計判別依然是一個尚未解決的難題。針對層次聚類結(jié)果顯著性的統(tǒng)計判別問題，一些學(xué)者進行了初步的探索研究。如文獻[14]借助多尺度Bootstrap方法，通過比較原始數(shù)據(jù)與隨機樣本的聚類結(jié)果判斷層次聚類結(jié)果的顯著性；文獻[13]以誤差平方和(SSE)作為簇的均質(zhì)性度量指標，通過比較簇內(nèi)實體專題屬性隨機重排前后SSE的大小變化定義簇的顯著性；文獻[15]依據(jù)層次聚類中兩個簇的合并距離判斷聚類的顯著性。這些方法都是針對單純的多維屬性數(shù)據(jù)(如時間序列、基因和微陣列數(shù)據(jù))層次聚類結(jié)果顯著性的判別，未考慮空間位置與專題屬性耦合的問題，無法直接應(yīng)用于顧及專題屬性的空間層次聚類的顯著性判別。同時，文獻[14—15]提出的方法隱含的前提假設(shè)是層次聚類的合并距離是單調(diào)的，但是由于空間層次聚類在聚合的過程中受空間鄰近約束的影響無法保證合并距離的單調(diào)性。文獻[13]可以通過進一步的擴展，對空間層次聚類結(jié)果的顯著性進行檢驗，但是其容易受噪聲的影響，對于實體間的微小差異過于敏感而難以獲得全局最優(yōu)的劃分結(jié)果。為此，本文針對同時顧及空間鄰近與專題屬性相似的層次聚類結(jié)果顯著性檢驗問題，提出了一種空間層次聚類顯著性判別的重排檢驗方法。

1研究策略

空間簇的顯著性判別實際上是對空間簇的均質(zhì)性進行度量和評價?？臻g簇的均質(zhì)性度量需要同時滿足兩方面條件：一方面每個空間實體與其空間鄰近實體的專題屬性相似，另一方面同一空間簇內(nèi)實體的專題屬性相似。度量一個空間實體與其鄰近實體專題屬性相似性的顯著程度，可以借鑒局部空間自相關(guān)指數(shù)(如局部Moran’s I)顯著性判別的策略[16]。本文對空間簇內(nèi)實體的專題屬性相似性度量提出如下假設(shè)：①若一個空間簇是均質(zhì)的，則簇內(nèi)實體的專題屬性隨機重排(即隨機分配簇內(nèi)實體的專題屬性值)后每個空間實體與其空間鄰近實體的專題屬性應(yīng)仍是相似的;②若重排后出現(xiàn)實體與其空間鄰近實體的專題屬性不相似的情況，則說明空間簇內(nèi)實體專題屬性間不滿足簇內(nèi)相似性約束，即簇內(nèi)實體的專題屬性值之間存在著較大的差異。

因此，度量簇的均質(zhì)性可轉(zhuǎn)化為度量簇內(nèi)隨機重排后每個空間實體與其鄰近實體的專題屬性相似性的保持情況：如果重排后空間簇內(nèi)實體與其鄰近實體的專題屬性依然是顯著相似的，說明該空間簇滿足均質(zhì)性度量的兩個約束條件， 則定

義該空間簇是顯著的。下面給出一個簡單的示例對本文的研究策略進行說明。如圖1(a)所示，每個單元格表示一個空間實體，數(shù)字表示實體的專題屬性，C表示一個均質(zhì)的空間簇。對C內(nèi)實體專題屬性進行隨機重排后(如圖1(b)所示)，位于簇C中心的實體與其空間鄰近實體(箭頭表示鄰近關(guān)系)的專題屬性仍然是相似的。圖1(c)顯示了一個非均質(zhì)的空間簇D，位于簇D中心的空間實體雖然也滿足與其空間鄰近實體專題屬性相似，然而簇內(nèi)重排后可以發(fā)現(xiàn)(如圖1(d)所示)，如位于中心位置的實體與其空間鄰近實體的專題屬性具有較大的差異，簇內(nèi)實體間專題屬性不相似。

圖1　示例數(shù)據(jù)和簇內(nèi)隨機重排Fig.1　An example of the random permutation within a cluster

基于上述思想，本文方法主要包括3方面內(nèi)容：首先識別空間數(shù)據(jù)中與其空間鄰近實體專題屬性顯著相似的空間實體(本文稱之為核點)，核點及其空間鄰近實體是構(gòu)成均質(zhì)簇的基本要素；其次，在方差增量最小約束下，將核點及其空間鄰近實體凝聚成簇；最后，空間簇內(nèi)進行隨機重排，對簇內(nèi)實體的專題屬性相似性進行統(tǒng)計判別。與當(dāng)前研究策略相比，本文的研究思路一方面可以對空間數(shù)據(jù)中有無聚集結(jié)構(gòu)進行統(tǒng)計檢驗，另一方面可以對空間層次聚類的停止準則進行判別，減少聚類過程對參數(shù)設(shè)置的依賴?；谏鲜霾呗裕旅娼榻B本文方法的具體步驟。

2空間層次聚類顯著性判別的重排檢驗方法

2.1基于全局隨機重排的核點檢測

空間層次聚類顯著性判別的首要步驟為識別空間實體中的核點。受局部空間自相關(guān)探測的啟發(fā)，首先需要對實體的空間鄰域進行定義；進一步，需要定義核點顯著性判別的零假設(shè)及統(tǒng)計量；最后，依據(jù)零假設(shè)通過隨機模擬計算統(tǒng)計量的經(jīng)驗概率密度分布，識別空間實體中的核點。

對于空間數(shù)據(jù)集SD={P1,P2,…,Pn}，與實體Pi在空間上相鄰的實體的集合稱為Pi的空間鄰居，Pi與其空間鄰居的集合稱為Pi的空間鄰域，記為NN(Pi)。對于格網(wǎng)或面狀數(shù)據(jù)，可以直接依據(jù)拓撲鄰接關(guān)系定義實體的空間鄰域；針對不規(guī)則點數(shù)據(jù)，由于約束Delaunay三角網(wǎng)法[17]具有良好的自適應(yīng)性，且不需要參數(shù)設(shè)置，因此本文采用約束Delaunay三角網(wǎng)法構(gòu)建不規(guī)則點的空間鄰域。

在此基礎(chǔ)上，采用方差度量空間實體Pi與其空間鄰域NN(Pi)內(nèi)實體間專題屬性的相似性，稱為Pi的局部方差，記為LV(Pi)，具體表達為

(1)

式中，mi表示NN(Pi)內(nèi)實體專題屬性均值；ni為NN(Pi)內(nèi)實體數(shù)目；Z(Pk)表示空間實體Pk的專題屬性值。需要注意的是，局部方差的計算實際上附加了空間鄰近關(guān)系的約束(即僅計算空間實體與其空間鄰近實體的專題屬性的方差)，因而同時考慮了空間與專題屬性相似兩方面的因素。進而，本文從空間隨機性的角度定義零假設(shè)，即任意空間位置上的專題屬性值不依賴于空間鄰近位置上的專題屬性值[18]。基于該假設(shè)，采用隨機重排的方法構(gòu)造空間隨機數(shù)據(jù)，計算實體局部方差的經(jīng)驗概率密度分布，并對核點的顯著性進行統(tǒng)計判別，具體步驟如下：

(1) 給定空間數(shù)據(jù)集SD={P1,P2,…,Pn}，依據(jù)式(1)計算實體Pk(k=1,2,…,n)的局部方差LV(P1)、LV(P2)、…、LV(Pn)。

(3) 重復(fù)步驟(2)m次，可以得到實體局部方差的樣本矩陣W = [D1D2…Dm](W矩陣即為通過全局隨機重排構(gòu)造的顯著性檢驗統(tǒng)計量的零假設(shè)概率密度分布)，由此可以計算出每個空間實體局部方差的顯著性p-value(·)

i=1,2,…,n

(2)

式中,Wik表示矩陣W的第i行第k列的元素值;I(·)表示指示函數(shù)。

圖2　隨機重排構(gòu)造實體局部方差經(jīng)驗概率密度分布示例Fig.2　Construction of the empirical probability density distribution of local variance

在給定的顯著性水平α下，如果實體局部方差的顯著性p-value(·)小于α，則將該實體標記為核點。需要注意的是，由于對局部方差顯著性的假設(shè)檢驗是一種多重假設(shè)檢驗問題，當(dāng)要求嚴格時需要進一步對其校正。本文試驗中采用FDR方法[19]進行多重假設(shè)檢驗的校正。如上所述，核點是構(gòu)成均質(zhì)空間簇的基本要素，為了避免聚類過程中噪聲干擾，進一步的聚類過程將只針對核點及其空間鄰域內(nèi)實體(稱為邊界點)進行凝聚式的合并聚類。如果在全局隨機重排步驟中未檢測到核點，則聚類過程結(jié)束，即數(shù)據(jù)近似隨機分布不存在聚集模式。

2.2方差約束下的凝聚合并

空間數(shù)據(jù)中的核點識別后，需要進一步將核點及邊界點凝聚成簇。本文采用空間約束的Ward法[11]進行凝聚聚類，首先從局部方差最小的核點出發(fā)，在凝聚合并時每個空間簇只與其空間鄰近的簇計算專題屬性相似性，這樣保證了在空間相鄰的前提下將專題屬性相似的實體聚合到一起。聚類開始首先將每一個實體視為一個簇，分別計算每個簇與其空間鄰接的簇合并前后的方差增量，將方差增量最小且通過簇內(nèi)均質(zhì)性檢驗的兩個簇進行合并，更新各空間簇的鄰接關(guān)系；重復(fù)以上過程，直到所有實體聚合為一個類或沒有可以合并的簇時停止。本文提出的重排檢驗方法與空間層次聚類緊密結(jié)合，下面介紹簇內(nèi)均質(zhì)性判別方法。

2.3簇內(nèi)均質(zhì)性統(tǒng)計判別

在空間層次聚類過程中，需要對每次合并獲得的空間簇的均質(zhì)性進行統(tǒng)計判別，以確定合并的停止條件。若經(jīng)過大量簇內(nèi)隨機重排操作后，簇內(nèi)核點與鄰近實體專題屬性仍是顯著相似的(即核點穩(wěn)定)，則稱該空間簇是顯著的或均質(zhì)的。具體計算步驟如下：

(1) 假設(shè)空間層次聚類過程中簇A和簇B將要合并為一個新的空間簇S，為了判別其顯著性(或能否合并的條件)，首先計算位于S內(nèi)的核點Pi(i=1,2,…,g)的局部方差LV(Pi)。

(3) 重復(fù)步驟(2)r次，空間簇S的顯著性可通過下式計算

(3)

在給定的統(tǒng)計顯著性水平β下，如果p-value(S)≤β，則稱空間簇S是顯著的或均質(zhì)的。

經(jīng)過上述步驟計算后，若空間簇S是顯著的，則簇A和簇B滿足合并條件，合并A和B，更新當(dāng)前所有空間簇的空間鄰接關(guān)系并進行下一次的凝聚合并，直到數(shù)據(jù)集中沒有滿足合并條件或所有實體聚為一個類時停止，并返回最后一次的合并結(jié)果作為最終的聚類結(jié)果。由于該方法聚類過程中不需要人為指定簇的數(shù)目或聚類停止條件，更具實用性，且簇合并時可根據(jù)空間鄰接關(guān)系向任意方向進行擴展，因此可以識別復(fù)雜形狀的空間簇。

3試驗分析與應(yīng)用

為了驗證本文方法的有效性，分別采用模擬數(shù)據(jù)與實際數(shù)據(jù)進行試驗分析，并與文獻[13]和ST-DBSCAN[20]、Mean shift[21]進行比較。試驗中隨機重排次數(shù)(m和r)的選擇，需從效率和精度兩個方面進行折中考慮，本文對重排次數(shù)的設(shè)置進行了試驗分析：所采用的測試數(shù)據(jù)集SD1如圖3(a)所示，包含324個核點；測試環(huán)境為Windows 8 系統(tǒng)，CPU 2.0 GHz，內(nèi)存8 GB，每種重排次數(shù)都試驗20次，取其運行時間的平均值。如表1所示，運行時間與重排次數(shù)呈線性增長的關(guān)系，當(dāng)重排次數(shù)大于5000時檢測結(jié)果趨于穩(wěn)定?，F(xiàn)有研究亦發(fā)現(xiàn)，當(dāng)重排次數(shù)為9999次時，p-value(·)可以取得的最小值為0.000 1，在顯著性水平為0.05時，可以滿足絕大多數(shù)應(yīng)用的精度需求[22]。試驗中全局和簇內(nèi)隨機重排次數(shù)(m和r)均設(shè)為9999，核點和簇的顯著性水平(α和β)均取0.05。

3.1模擬試驗與比較

為了說明本文方法在挖掘隨機數(shù)據(jù)中均質(zhì)簇的能力，設(shè)計模擬數(shù)據(jù)集SD1如圖3(a)所示，在中心位置設(shè)置了一個由兩個專題屬性差異很小的矩形區(qū)域構(gòu)成的空間簇(區(qū)域A和B大小均為20×10，區(qū)域A內(nèi)實體專題屬性值都為1，區(qū)域B內(nèi)實體專題屬性值都為1.1)，其余實體的專題屬性值設(shè)置為1到100之間的隨機整數(shù)。文獻[13]的聚類結(jié)果如圖3(c)所示。由于區(qū)域A和B合并前誤差平方和為0，而將這兩個簇的專題屬性進行隨機重排后誤差平方和必然變大，文獻[13]判斷其不能合并，故兩個專題屬性值差異很小的區(qū)域被錯誤割裂。本文方法的核點檢測結(jié)果如圖3(b)所示，聚類結(jié)果如圖3(d)所示，與人眼的識別結(jié)果相吻合，發(fā)現(xiàn)了被隨機噪聲包圍的均質(zhì)簇(圖3(a)中藍色區(qū)域)。由此可見，文獻[13]針對簡單的空間數(shù)據(jù)依然過于保守，為此在接下來的試驗中將不與文獻[13]作進一步的比較。

表1　隨機重排次數(shù)與核點檢測的準確性和運行時間的關(guān)系

注：運行時間是取20次重復(fù)試驗的平均值；核點個數(shù)括號內(nèi)的數(shù)字表示20次試驗出現(xiàn)該結(jié)果的次數(shù)。

模擬數(shù)據(jù)SD2(32×32)包含4個大簇，每個大簇包含4個小簇，如圖4(a)所示。模擬數(shù)據(jù)的方差矩陣如圖4(c)(M表示專題屬性均值，S表示專題屬性標準方差)所示。本文方法聚類結(jié)果如圖4(d)所示，準確地識別了數(shù)據(jù)中預(yù)設(shè)的4個大簇。對于每個整體上顯著的大簇，可以進一步通過迭代求解的方式識別局部的小簇，即將聚類結(jié)果中的每個大簇作為新的數(shù)據(jù)集再進行聚類。例如，對左上角的大簇A進行分析，可獲得其中的4個小簇A1—A4，如圖4(e)。如此重復(fù)迭代，即可識別數(shù)據(jù)局部所有顯著的聚集結(jié)構(gòu)(共16個簇)。這一從整體到局部的聚類過程亦符合人類視覺多尺度認知由整體到局部，由粗到細的識別過程。

模擬數(shù)據(jù)SD3包含了8個空間簇，如圖5(a)所示，圖中Z表示簇內(nèi)實體專題屬性的取值范圍，噪聲點的專題屬性值設(shè)置為0~10之間的任意隨機數(shù)。其中，C1為高密度的空間簇，C2表示了變密度的空間簇，C3、C4以及C5和C6表示了任意形狀且相鄰的空間簇，C7表示了面積較小的空間簇，C8表示了低密度的空間簇。本文方法核點檢測結(jié)果和最終聚類結(jié)果如圖5(b)和5(c)所示，可以發(fā)現(xiàn)本文方法很好地識別出數(shù)據(jù)中預(yù)設(shè)的各類空間簇。在一些空間簇的周圍包含了個別的“噪聲點”(圖5(c)中帶圓圈的點)，但通過進一步的觀察發(fā)現(xiàn)，這些點的專題屬性值與空間簇的專題屬性值分布一致，這進一步驗證了本文方法探測均勻簇的能力。核點檢測是本文的關(guān)鍵步驟，為了顯示本文策略探測核點的有效性，與經(jīng)典

的Meanshift算法進行比較，圖5(d)—(f)顯示了Meanshift算法在不同帶寬下局部極值點(modes)檢測結(jié)果和聚類結(jié)果，可以發(fā)現(xiàn)Meanshift算法難以準確的識別預(yù)設(shè)的聚集結(jié)構(gòu)，簇內(nèi)包含了大量的隨機噪聲。此外，Meanshift算法兩個帶寬(即空間帶寬Hs和屬性帶寬Hr)的設(shè)置缺乏嚴密的依據(jù)，因而增加了用戶實際使用的難度。

為了進一步驗證本文方法的有效性，與經(jīng)典ST-DBSCAN聚類方法進行對比試驗分析。ST-DBSCAN算法的參數(shù)采用文章作者推薦的啟發(fā)式方法進行設(shè)置，掃描半徑Eps和最小包含點數(shù)MinPts，聚類結(jié)果如圖6所示，可以發(fā)現(xiàn)：ST-DBSCAN算法僅正確識別了SD1中最簡單的空間簇；對于SD2聚類效果較差，未能識別主要聚類結(jié)構(gòu)；對于SD3未能識別空間簇的完整結(jié)構(gòu)，類別面積較小的空間簇(C7)亦未能正確識別。

3.2實際應(yīng)用與分析

降水和氣溫的空間分布模式是地理學(xué)的研究熱點，我國具有復(fù)雜的氣候條件，降水和氣溫都具有明顯的空間分異性，提取其中的均質(zhì)區(qū)域，對于研究降水、氣溫分布規(guī)律和特征具有重要作用，亦可為進一步的深入研究提供有益的參考。此外，對于我國降水和氣溫分布具備一定的先驗知識，可以為檢驗聚類結(jié)果的有效性提供一定的依據(jù)。本文方法對2009年我國554個陸地氣象觀測站的年降水量和年平均氣溫數(shù)據(jù)進行分析，聚類結(jié)果如圖7所示，在表2顯示了各個簇內(nèi)專題屬性的標準方差(其中，Std.Dev表示數(shù)據(jù)總體的標準方差)。

圖3　模擬數(shù)據(jù)SD1以及試驗結(jié)果對比Fig.3　Experiments on simulated dataset SD1

圖4　模擬數(shù)據(jù)SD2以及聚類結(jié)果Fig.4　Experiments on simulated dataset SD2

圖5　模擬數(shù)據(jù)SD3聚類結(jié)果及Meanshift聚類結(jié)果Fig.5　Clustering result of SD3and modes detected by Meanshift with different band widthparamters

圖6　模擬數(shù)據(jù)集SD1、SD2和SD3的ST-DBSCAN聚類結(jié)果Fig.6　Clustering results of ST-DBSCAN on dataset SD1, SD2and SD3

參數(shù)C1C2C3C4C5C6C7C8C9C10C11C12C13C14C15Std.Dev降水/mm79.984.6108.792.7107.3129.8100.3160.886.9129.4153.2177.2138.5176.3123.4475.5氣溫/℃1.671.571.811.471.461.360.971.060.992.181.182.712.021.80—6.57

從圖7可以發(fā)現(xiàn)，不同空間簇間均具有比較明顯的分界線。對于降水?dāng)?shù)據(jù)的聚類結(jié)果(圖7(a))，較好反映了我國降水空間分布的基本特征，圖中標記的紅色線由北向南分別代表我國年降水量400 mm、800 mm和1600 mm等值線，如簇C2與簇(C1、C3和C4)的邊界構(gòu)成了我國400 mm年降水量等值線；簇C3、C4與簇C5、C8、C9、C10的邊界構(gòu)成了我國800 mm降水等值線；簇C5、C6與簇C7、C12、C14的邊界構(gòu)成了我國1600 mm降水等值線。對于氣溫數(shù)據(jù)的聚類結(jié)果(圖7(b))，充分反映了我國氣溫分布的空間分異特征，由北到南發(fā)現(xiàn)的空間簇與相關(guān)氣象資料[23]中我國主要氣溫帶十分吻合，如簇C9對應(yīng)了寒溫帶，簇C1、C2、C3表示了中溫帶、簇C4表示了暖溫帶、簇C5、C13對應(yīng)了北亞熱帶、簇C6表示了中亞熱帶、簇C7代表了南亞熱帶、簇C8、C14表示了邊緣熱帶、簇C10、C12表示了高原溫帶、簇C11代表了高原寒帶。此外，進一步結(jié)合克里金插值結(jié)果亦可以發(fā)現(xiàn)同一空間簇內(nèi)各站點的氣溫和降水相似，說明了空間聚類結(jié)果保證了簇內(nèi)部的均質(zhì)性，且與氣象領(lǐng)域的分區(qū)結(jié)果相吻合。

為了進行比較分析，圖8給出了ST-DBSCAN的聚類結(jié)果，可以發(fā)現(xiàn)，針對降水?dāng)?shù)據(jù)絕大部分站點都被識別為噪聲，并沒有發(fā)現(xiàn)降水的空間分布模式；針對氣溫數(shù)據(jù)僅僅發(fā)現(xiàn)了東部和中部地區(qū)幾個小簇，我國氣溫分異特征難以從聚類結(jié)果中得到反映。

圖7　本文方法對2009年年降水量和氣溫數(shù)據(jù)聚類結(jié)果Fig.7　Clustering results obtained by the proposed method

圖8　年降水量和年平均氣溫的ST-DBSCAN算法聚類結(jié)果Fig.8　Clustering results obtained by ST-DBSCAN

4總結(jié)與展望

本文提出的統(tǒng)計檢驗方法，能克服空間層次聚類方法合并截止條件判別困難的缺陷。通過試驗分析與比較發(fā)現(xiàn)，本文方法能夠有效判別空間層次聚類結(jié)果的顯著性，提取數(shù)據(jù)中顯著的結(jié)構(gòu)模式，避免隨機結(jié)構(gòu)的干擾。

重排檢驗要進行大量的數(shù)據(jù)模擬，運行效率較低，在海量數(shù)據(jù)的分析應(yīng)用中可能會有一定的局限性，進一步工作將研究采用并行計算、數(shù)據(jù)分塊或采樣等技術(shù)手段提升算法的運行效率，使其可以適用于海量數(shù)據(jù)的分析處理。對于高維專題屬性聚類依然是當(dāng)前研究的一個難點，本文提出的方法針對高維專題屬性聚類問題的應(yīng)用效果及擴展亦將是未來的一個重要研究方向。本文方法在其他領(lǐng)域中具有一定的應(yīng)用前景，如地圖綜合、遙感圖像的分割和分類等。

參考文獻：

[1]李德仁, 王樹良, 李德毅. 空間數(shù)據(jù)挖掘理論與應(yīng)用[M]. 北京: 科學(xué)出版社, 2006.

LI Deren, WANG Shuliang, LI Deyi. Spatial Data Mining Theories and Applications[M]. Beijing: Science Press, 2006.

[2]艾廷華, 郭仁忠. 基于格式塔識別原則挖掘空間分布模式[J]. 測繪學(xué)報, 2007, 36(3): 302-308.

AI Tinghua, GUO Renzhong. Polygon Cluster Pattern Mining Based on Gestalt Principles[J]. Acta Geodaetica et Cartographica Sinica, 2007, 36(3): 302-308.

[3]汪閩, 周成虎, 裴韜, 等. MSCMO: 基于數(shù)學(xué)形態(tài)學(xué)算子的尺度空間聚類方法[J]. 遙感學(xué)報, 2004, 8(1): 45-50.

WANG Min, ZHOU Chenghu, PEI Tao, et al. MSCMO: A Scale Space Clustering Algorithm Based on Mathematical Morphology Operators[J]. Journal of Remote Sensing, 2004, 8(1): 45-50.

[4]李光強, 鄧敏, 程濤, 等. 一種基于雙重距離的空間聚類方法[J]. 測繪學(xué)報, 2008, 37(4): 482-488.

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.

[5]郭慶勝, 鄭春燕, 胡華科. 基于鄰近圖的點群層次聚類方法的研究[J]. 測繪學(xué)報, 2008, 37(2): 256-261.

GUO Qingsheng, ZHENG Chunyun, HU Huake. Hierarchical Clustering Method of Group of Points Based on the Neighborhood Graph[J]. Acta Geodaetica et Cartographica Sinica, 2008, 37(2): 256-261.

[6]李光強, 鄧敏, 劉啟亮, 等. 一種適應(yīng)局部密度變化的空間聚類方法[J]. 測繪學(xué)報, 2009, 38(3): 255-263.

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.

[7]PEI Tao, ZHU Axing, ZHOU Chenghu, et al. A New Approach to the Nearest-Neighbour Method to Discover Cluster Features in Overlaid Spatial Point Processes[J]. International Journal of Geographical Information Science, 2006, 20(2): 153-168.

[8]程博艷, 劉強, 李小文. 一種建筑物群智能聚類法[J]. 測繪學(xué)報, 2013, 42(2): 290-294.

CHENG Boyan, LIU Qiang, LI Xiaowen. Intelligent Building Grouping Using Selft-organizing Map[J]. Acta Geodaetica et Cartographica Sinica, 2013, 42(2): 290-294.

[9]李新運, 鄭新奇, 閆弘文. 坐標與屬性一體化的空間聚類方法研究[J]. 地理與地理信息科學(xué), 2004, 20(2): 38-40.

LI Xinyun, ZHENG Xinqi, YAN Hongwen. On Sptial Clustering Combination of Coordinate and Attribute[J]. Geography and Geo-Information Science, 2004, 20(2): 38-40.

[10]宋曉眉, 程昌秀, 周成虎, 等. 利用k階空間鄰近圖的空間層次聚類方法[J]. 武漢大學(xué)學(xué)報(信息科學(xué)版), 2010, 35(12): 1496-1499.

SONG Xiaomei, CHENG Changxiu, ZHOU Chenghu, et al. Spatial Hierarchical Clustering Method Based on k-order Spatial Neighbouring Map[J]. Geomatics and Information Science of Wuhan University, 2010, 35(12): 1496-1499.

[11]焦利民, 洪曉峰, 劉耀林. 空間和屬性雙重約束下的自組織空間聚類研究[J]. 武漢大學(xué)學(xué)報(信息科學(xué)版), 2011, 36(7): 862-866.

JIAO Limin, HONG Xiaofeng, LIU Yaolin. Self-organizing Spatial Clustering under Spatial and Attribute Constraints[J]. Geomatics and Information Science of Wuhan University, 2011, 36(7): 862-866.

[12]GUO Diansheng. Greedy Optimization for Contiguity-Constrained Hierarchical Clustering[C]∥Proceedings of IEEE International Conference on Data Mining Workshops.Miami, FL: IEEE, 2009: 591-596.

[13]PARK P J, MANJOURIDES J, BONETTIM, et al. A Permutation Test for Determining Significance of Clusters with Applications to Spatial and Gene Expression Data[J]. Computational Statistics and Data Analysis, 2009, 53(12): 4290-4300.

[14]SUZUKI R, SHIMODAIRA H. Pvclust: An R Package for Assessing the Uncertainty in Hierarchical Clustering[J]. Bioinformatics, 2006, 22(12): 1540-1542.

[15]GREENACRE M, PRIMICERIO R. Multivariate Analysis of Ecological Data[M]. Bilbao: Fundación BBVA, 2013.

[16]ANSELIN L. Local Indicators of Spatial Association-LISA[J]. Geographical Analysis, 1995, 27(2): 93-115.

[17]劉啟亮, 鄧敏, 石巖, 等. 一種基于多約束的空間聚類方法[J]. 測繪學(xué)報, 2011, 40(4): 509-516.

LIU Qiliang, DENG Min, SHI Yan, et al. A Novel Spatial Clustering Method Based on Multi-Constraints[J]. Acta Geodaetica et Cartographica Sinica, 2011, 40(4): 509-516.

[18]王遠飛, 何洪林. 空間數(shù)據(jù)分析方法[M]. 北京: 科學(xué)出版社, 2007.

WANG Yuanfei, HE Honglin. Spatial Data Analysis Method[M]. Beijing: Science Press, 2007.

[19]BENJAMINI Y, YEKUTIELI D. The Control of the False Discovery Rate in Multiple Testing under Dependency[J]. The Annals of Statistics, 2001, 29(4): 1165-1188.

[20]BIRANT D, KUT A. ST-DBSCAN: An Algorithm for Clustering Spatial-temporal Data[J]. Data & Knowledge Engineering, 2007, 60(1): 208-221.

[21]COMANICIU D, MEER P. Mean Shift: A Robust Approach Toward Feature Space Analysis[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 24(5): 603-619.

[22]OJALA M, GARRIGA G C. Permutation Tests for Studying Classifier Performance[J]. The Journal of Machine Learning Research, 2010, 11(1): 1833-1863.

[23]《中華人民共和國氣候圖集》編委會. 中華人民共和國氣候圖集[M]. 北京: 氣象出版社, 2002.

The Editorial Board of Climatic Atlas of the People’s Republic of China. Climatological Atlas of the People’s Republic of China[M]. Beijing: China Meteorological Press, 2002.

(責(zé)任編輯：宋啟凡)

修回日期： 2015-10-13

A Permutation Test for Identifying Significant Clusters in Spatial Dataset

TANG Jianbo,LIU Qiliang,DENG Min,HUANG Jincai,CAI Jiannan

School of Geosciences and Info-Physics, Central South University, Changsha 410083, China

Abstract：Spatial hierarchical clustering methods considering both spatial proximity and attribute similarity play an important role in exploratory spatial data analysis. Although existing methods are able to detect multi-scale homogeneous spatial contiguous clusters, the significance of these clusters cannot be evaluated in an objective way. In this study, a permutation test was developed to determine the significance of clusters discovered by spatial hierarchical clustering methods. Experiments on both simulated and meteorological datasets show that the proposed permutation test is effective for determining significant clustering structures from spatial datasets.

Key words：spatial hierarchical clustering; significance; spatial pattern; permutation test

基金項目：國家自然科學(xué)基金(41471385；41171351)；數(shù)字制圖與國土信息應(yīng)用工程國家測繪地理信息局重點實驗室開放基金(GCWD201401)；中南大學(xué)中央高?；究蒲袠I(yè)務(wù)費專項資金(2013zzts247)

中圖分類號：P208

文獻標識碼：A

文章編號：1001-1595(2016)02-0233-08

通信作者：吳亮

作者簡介：第一 陳占龍 (1980—)，男，博士，副教授，主要研究方向為空間分析算法、空間推理、地理信息系統(tǒng)軟件開發(fā)與應(yīng)用。

收稿日期：2014-12-09

First author： CHEN Zhanlong(1980—)，male， PhD, associate professor，majors in spatial analysis algorithms，spatial reasoning，geographic information system software and application development.

E-mail： chenzhanlong2005@126.com

Corresponding author： WU Liang

E-mail： wuliang133@189.cn

引文格式：唐建波，劉啟亮，鄧敏，等.空間層次聚類顯著性判別的重排檢驗方法[J].測繪學(xué)報，2016,45(2)：233-240.DOI:10.11947/j.AGCS.2016.20140605.

TANG Jianbo,LIU Qiliang,DENG Min,et al.A Permutation Test for Identifying Significant Clusters in Spatial Dataset[J]. Acta Geodaetica et Cartographica Sinica,2016,45(2):233-240.DOI:10.11947/j.AGCS.2016.20140605.