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

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

?

空間層次聚類顯著性判別的重排檢驗(yàn)方法

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

中南大學(xué)地球科學(xué)與信息物理學(xué)院，湖南 長(zhǎng)沙 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)

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

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

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

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

1研究策略

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

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

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

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

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

2空間層次聚類顯著性判別的重排檢驗(yàn)方法

2.1基于全局隨機(jī)重排的核點(diǎn)檢測(cè)

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

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

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

(1)

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

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

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

i=1,2,…,n

(2)

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

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

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

2.2方差約束下的凝聚合并

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

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

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

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

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

(3)

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

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

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

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

3.1模擬試驗(yàn)與比較

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

表1　隨機(jī)重排次數(shù)與核點(diǎn)檢測(cè)的準(zhǔn)確性和運(yùn)行時(shí)間的關(guān)系

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

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

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

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

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

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

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

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

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

圖7　本文方法對(duì)2009年年降水量和氣溫?cái)?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)計(jì)檢驗(yàn)方法，能克服空間層次聚類方法合并截止條件判別困難的缺陷。通過(guò)試驗(yàn)分析與比較發(fā)現(xiàn)，本文方法能夠有效判別空間層次聚類結(jié)果的顯著性，提取數(shù)據(jù)中顯著的結(jié)構(gòu)模式，避免隨機(jī)結(jié)構(gòu)的干擾。

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

參考文獻(xiàn)：

[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]艾廷華, 郭仁忠. 基于格式塔識(shí)別原則挖掘空間分布模式[J]. 測(cè)繪學(xué)報(bào), 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é)報(bào), 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]李光強(qiáng), 鄧敏, 程濤, 等. 一種基于雙重距離的空間聚類方法[J]. 測(cè)繪學(xué)報(bào), 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]郭慶勝, 鄭春燕, 胡華科. 基于鄰近圖的點(diǎn)群層次聚類方法的研究[J]. 測(cè)繪學(xué)報(bào), 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]李光強(qiáng), 鄧敏, 劉啟亮, 等. 一種適應(yīng)局部密度變化的空間聚類方法[J]. 測(cè)繪學(xué)報(bào), 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]程博艷, 劉強(qiáng), 李小文. 一種建筑物群智能聚類法[J]. 測(cè)繪學(xué)報(bào), 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]李新運(yùn), 鄭新奇, 閆弘文. 坐標(biāo)與屬性一體化的空間聚類方法研究[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é)報(bào)(信息科學(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é)報(bào)(信息科學(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]. 測(cè)繪學(xué)報(bào), 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]王遠(yuǎn)飛, 何洪林. 空間數(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]《中華人民共和國(guó)氣候圖集》編委會(huì). 中華人民共和國(guó)氣候圖集[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

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

中圖分類號(hào)：P208

文獻(xiàn)標(biāo)識(shí)碼：A

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

通信作者：吳亮

作者簡(jiǎn)介：第一 陳占龍 (1980—)，男，博士，副教授，主要研究方向?yàn)榭臻g分析算法、空間推理、地理信息系統(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

引文格式：唐建波，劉啟亮，鄧敏，等.空間層次聚類顯著性判別的重排檢驗(yàn)方法[J].測(cè)繪學(xué)報(bào)，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.