顯著空間同位模式的多尺度挖掘方法

何占軍，劉啟亮，鄧 敏，蔡建南

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

?

顯著空間同位模式的多尺度挖掘方法

何占軍，劉啟亮，鄧 敏，蔡建南

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

空間同位模式挖掘?qū)τ诮沂镜乩憩F(xiàn)象間的共生、依賴規(guī)律具有重要價(jià)值。然而，空間同位模式挖掘中參數(shù)閾值缺乏先驗(yàn)知識(shí)，若設(shè)置不合理，挖掘結(jié)果中會(huì)遺漏重要的模式或包含冗余的、甚至錯(cuò)誤的模式。為此，本文提出了一種基于模式重建的顯著空間同位模式多尺度挖掘方法。首先，定義了互鄰近距離指標(biāo)，該指標(biāo)可用來確定距離閾值的有效取值范圍。進(jìn)而，以模式重建為基礎(chǔ)構(gòu)建零模型，借助統(tǒng)計(jì)檢驗(yàn)的方法來發(fā)現(xiàn)顯著的空間同位模式，從而避免了興趣度閾值的設(shè)置。最后，對(duì)空間同位模式進(jìn)行多尺度挖掘，并引入生存期的概念對(duì)同位模式多尺度挖掘結(jié)果進(jìn)行有效性評(píng)價(jià)。試驗(yàn)結(jié)果表明:本文方法可有效降低算法參數(shù)設(shè)置的主觀性，從而提升空間同位模式挖掘結(jié)果的準(zhǔn)確性和穩(wěn)健性。

數(shù)據(jù)挖掘；空間同位；統(tǒng)計(jì)顯著模式；模式重建；多尺度

空間同位模式挖掘作為空間數(shù)據(jù)挖掘領(lǐng)域的重要研究?jī)?nèi)容之一，已經(jīng)引起了國(guó)內(nèi)外學(xué)者的廣泛關(guān)注[1-3]?？臻g同位模式挖掘旨在發(fā)現(xiàn)空間數(shù)據(jù)集中滿足一定鄰域關(guān)系的、頻繁發(fā)生的要素或事件集合[4]。空間同位模式挖掘可以發(fā)現(xiàn)空間現(xiàn)象中隱藏的、有意義的模式，從而揭示深層次的領(lǐng)域知識(shí)并服務(wù)于決策支持。目前，空間同位模式挖掘已應(yīng)用于生物研究、疾病防控、犯罪分析、移動(dòng)位置服務(wù)等領(lǐng)域。

空間同位模式挖掘算法的一般框架最初由文獻(xiàn)[4]提出，并給出一種Colocation Miner算法。Colocation Miner算法大致可分為兩個(gè)步驟：①確定空間鄰域，并產(chǎn)生候選同位模式，其中，空間鄰域關(guān)系通常由用戶給定的歐氏距離閾值來確定；②對(duì)候選同位模式的興趣度(頻繁度)進(jìn)行度量，并根據(jù)興趣度度量指標(biāo)對(duì)候選同位模式進(jìn)行過濾，其中，在計(jì)算候選模式的興趣度時(shí)，Colocation Miner采取的是實(shí)例連接的方法，計(jì)算量較大。為提升算法效率，不同學(xué)者陸續(xù)針對(duì)實(shí)例連接方法作了改進(jìn)，如部分連接的方法[5]、無連接方法[6]和基于密度的方法[7]等。此外，空間數(shù)據(jù)的異質(zhì)特性導(dǎo)致空間同位模式可能僅存在局部的空間區(qū)域，空間同位模式挖掘的另一重要研究?jī)?nèi)容是如何挖掘局部空間同位模式[8-11]。

盡管國(guó)內(nèi)外學(xué)者陸續(xù)發(fā)展了不同的空間同位模式的挖掘方法，但這些方法的大多仍遵循Colocation Miner算法的框架。在此框架下，模式挖掘結(jié)果主要受到挖掘參數(shù)閾值(鄰近距離閾值和興趣度閾值)的影響。而實(shí)際中，這些參數(shù)閾值的設(shè)置通常缺乏先驗(yàn)知識(shí)，從而影響了挖掘結(jié)果的可靠性。以興趣度度量指標(biāo)為例，若設(shè)置太高會(huì)導(dǎo)致模式的遺漏，而設(shè)置太低又會(huì)導(dǎo)致挖掘結(jié)果中包含太多的模式，從而造成模式解譯及應(yīng)用的難題。為減輕挖掘結(jié)果對(duì)參數(shù)閾值的依賴，國(guó)內(nèi)外諸學(xué)者開展了積極的探索。具體而言，對(duì)于距離閾值的設(shè)置，通常由兩種策略，基于最近鄰的方法和基于空間自相關(guān)指標(biāo)的方法[13]；對(duì)于興趣度閾值的設(shè)置，文獻(xiàn)[12]給出一種TOP-N空間同位模式的挖掘策略，文獻(xiàn)[13]則假設(shè)同位模式的興趣度指標(biāo)服從正態(tài)分布，進(jìn)而結(jié)合拉依達(dá)準(zhǔn)則篩選出顯著模式。最近，文獻(xiàn)[14]給出一種降低興趣度參數(shù)影響的新方法(SSCSP)。該方法首先假設(shè)數(shù)據(jù)中不包含任何同位模式(即零假設(shè))，進(jìn)而對(duì)候選模式進(jìn)行假設(shè)檢驗(yàn)，最終不滿足零假設(shè)的模式即為顯著模式。該方法的優(yōu)勢(shì)在于將模式判別轉(zhuǎn)化為假設(shè)檢驗(yàn)問題，避免了人為設(shè)置興趣度閾值。具體而言，該方法主要包含3個(gè)步驟：①點(diǎn)分布模式擬合，若點(diǎn)分布體現(xiàn)較強(qiáng)的空間自相關(guān)特征，則假設(shè)由泊松類聚過程生成[15]，否則假設(shè)由一般泊松過程生成，在此假設(shè)的基礎(chǔ)上，對(duì)每種類型的點(diǎn)要素分布模型的參數(shù)進(jìn)行估計(jì)；②模擬數(shù)據(jù)生成，根據(jù)上一步驟中估計(jì)的模型生成模擬數(shù)據(jù)，從而使得模擬數(shù)據(jù)盡量保持和原始數(shù)據(jù)相似的分布特征；③顯著空間同位模式發(fā)現(xiàn)，以同位模式的興趣度作為統(tǒng)計(jì)量，通過比較零假設(shè)和實(shí)際數(shù)據(jù)中模式的興趣度的差異來確定同位模式是否顯著。

分析上述空間同位模式挖掘的相關(guān)研究可發(fā)現(xiàn)，當(dāng)前同位模式挖掘工作尚存在以下不足：①當(dāng)前同位模式挖掘算法大多試圖發(fā)現(xiàn)單一的、最佳的鄰近距離閾值，而事實(shí)上，采用不同的距離閾值時(shí)，空間同位模式挖掘結(jié)果不同[16]，因而很難確定最佳的距離閾值；②為避免興趣度閾值的設(shè)置，現(xiàn)有方法均對(duì)數(shù)據(jù)特征或模型進(jìn)行了特定假設(shè)。例如，SSCSP方法假設(shè)空間自相關(guān)的點(diǎn)模式由泊松類聚類型產(chǎn)生，而實(shí)際上單一的泊松類聚類型并不能描述所有類型的空間點(diǎn)模式。因此，若這些假設(shè)未能很好地滿足，由此帶來的誤差就會(huì)影響最終模式挖掘的結(jié)果。為解決以上問題，本文提出一種基于模式重建的顯著空間同位模式多尺度挖掘方法。

1 基于模式重建的顯著空間同位模式多尺度挖掘

1.1 研究策略

如上文中指出，空間同位模式挖掘結(jié)果會(huì)隨著鄰近距離閾值的改變而變化，確定單一的、最佳的距離閾值并不現(xiàn)實(shí)。一種更為合理的策略是在不同的距離閾值下發(fā)現(xiàn)和評(píng)價(jià)空間同位模式，即實(shí)現(xiàn)空間同位模式的多尺度挖掘。為此，需要解決以下3個(gè)問題：①給定數(shù)據(jù)集，首先確定空間同位模式可能存在的空間范圍，即：鄰域距離取何值時(shí)可能發(fā)現(xiàn)同位模式；②選定某一距離閾值，模式的興趣度閾值設(shè)置應(yīng)該采取一種較為客觀的方法，而不是人為設(shè)定興趣度閾值；③綜合多個(gè)尺度的挖掘結(jié)果，對(duì)空間同位模式的有效性作出評(píng)價(jià)，篩選出數(shù)據(jù)集中最顯著的模式。

鑒于以上考慮，本文提出一種顯著空間同位模式的多尺度挖掘方法，包含以下3個(gè)步驟：

(1) 鄰近距離閾值有效范圍的確定。引入一種新的度量指標(biāo)——互鄰近距離，該指標(biāo)可以刻畫不同要素實(shí)例間的鄰近分布特征，從而界定鄰近距離閾值的有效取值范圍。

(2) 零模型構(gòu)建和顯著空間同位模式挖掘。假設(shè)不同要素之間相互獨(dú)立(零模型)，在此基礎(chǔ)上借助一種非參數(shù)方法(模式重建)生成模擬數(shù)據(jù)。模擬數(shù)據(jù)中保持各類要素的分布特征，但卻破壞不同類別要素實(shí)例間的依賴關(guān)系。進(jìn)而，將空間同位模式挖掘轉(zhuǎn)化為統(tǒng)計(jì)假設(shè)檢驗(yàn)問題，避免了人為設(shè)置興趣度的困境。最終，不滿足原假設(shè)的模式即為顯著同位模式。

(3) 顯著空間同位模式多尺度挖掘結(jié)果評(píng)價(jià)，引入生存期的概念對(duì)不同尺度下的挖掘結(jié)果進(jìn)行評(píng)價(jià)，從而確定數(shù)據(jù)中主要的模式，下文將對(duì)方法給出詳細(xì)的描述。

1.2 鄰近距離閾值估計(jì)

為了確定鄰近距離閾值的有效取值范圍，首先給出以下相關(guān)定義。

(1)

圖1 要素實(shí)例鄰近關(guān)系Fig.1 Neighboring relationship of feature instances

定義2：空間同位模式參與指數(shù)(participation index,PI)[5]。給定同位模式C，其參與指數(shù)定義為

(2)

式中，k表示同位模式共包含的要素類型數(shù)目；fi對(duì)應(yīng)其中某一種要素類型；table_instance表示空間同位模式包含的實(shí)例集合；π表示刪除重復(fù)項(xiàng)的關(guān)系映射操作。由式(2)可知，分母為要素類型fi的實(shí)例總數(shù)目，分子為滿足同位關(guān)系C中的fi實(shí)例數(shù)目。顯然，參與指數(shù)的取值范圍為[0～1]。

定義3：鄰近距離域(neighboring distance range,NDR)。記數(shù)據(jù)集中所有實(shí)例的互最近鄰距離集合為DC，DC中以最小值和最大值為界構(gòu)成的距離范圍定義為鄰近距離域。結(jié)合定義1可知：MNND刻畫的是不同類型要素間鄰近距離的特征，當(dāng)距離閾值小于min(DC)時(shí)，任意兩個(gè)不同類型要素實(shí)例均不相鄰，此時(shí)參與指數(shù)為0；而當(dāng)距離閾值大于max(DC)時(shí)，任意實(shí)例的鄰域內(nèi)均含有其他類型要素，參與指數(shù)達(dá)到最大值1。因此，鄰近距離域?qū)?yīng)的范圍即為有效的鄰近距離閾值取值。

1.3 顯著空間同位模式判別

空間同位模式是很難憑借經(jīng)驗(yàn)進(jìn)行判別的。一個(gè)更為合理策略是假設(shè)空間數(shù)據(jù)集中不存在空間同位模式，進(jìn)而比較實(shí)際挖掘所得模式與零假設(shè)的差異，將顯著偏離原假設(shè)的模式視為真實(shí)的空間同位模式。為此，需設(shè)計(jì)零模型并根據(jù)零模型生成模擬數(shù)據(jù)。其中，零模型主要滿足兩個(gè)條件：①不同要素間相互獨(dú)立；②對(duì)于同一要素，模擬數(shù)據(jù)和真實(shí)數(shù)據(jù)具有相似的空間分布特征。由于不同空間要素分布模式的復(fù)雜性和差異性，條件②是零模型構(gòu)建中的難點(diǎn)問題，也是關(guān)鍵所在。

(3)

給定觀測(cè)數(shù)據(jù)D，根據(jù)式(3)可生成N個(gè)具有相同要素分布特征的模擬數(shù)據(jù)集{D1,D2,Di,…,DN}。記實(shí)際數(shù)據(jù)集D中同位模式C對(duì)應(yīng)的參與指數(shù)記為PIobs(C),同一模式在數(shù)據(jù)Di的參與指數(shù)記為PIi(C),則同位模式C的顯著性根據(jù)下式進(jìn)行計(jì)算

(4)

式中，sign為取值為0或1的符號(hào)運(yùn)算。給定顯著性水平α,若p(C)小于α,則C為顯著同位模式。

1.4 多尺度挖掘結(jié)果評(píng)價(jià)

單個(gè)距離閾值下挖掘得到的同位模式通常不能充分刻畫數(shù)據(jù)特征，更有意義的是在多個(gè)距離閾值下挖掘空間同位模式，即實(shí)現(xiàn)空間同位模式的多尺度挖掘。然而，多尺度挖掘結(jié)果中通常包含較多的模式，若返回所有的模式會(huì)造成結(jié)果分析困難，不利于輔助決策，因此需對(duì)多尺度挖掘結(jié)果進(jìn)行評(píng)價(jià)和篩選。

文獻(xiàn)[20]指出，模式穩(wěn)定性和視覺顯著性存在明顯的對(duì)應(yīng)關(guān)系，即：顯著的模式會(huì)在較廣的視覺范圍內(nèi)被優(yōu)先感知?；诖耍墨I(xiàn)[21]首次定義了生存期的概念，并用來描述尺度空間聚類算法中聚類模式的穩(wěn)定性。類似的，文獻(xiàn)[22]定義了聚類數(shù)目的生存期，并將其作為多尺度聚類算法結(jié)果的篩選標(biāo)準(zhǔn)。鑒于此，本文引入生存期的概念對(duì)空間同位模式多尺度挖掘結(jié)果進(jìn)行評(píng)價(jià)，空間同位模式的生存期定義如下。

定義4：生存期(living time,LT)。將鄰近距離域均分為N等份，并在此N個(gè)距離上分別進(jìn)行同位模式挖掘。若同位模式C在其中連續(xù)的P個(gè)距離上均統(tǒng)計(jì)顯著，則同位模式C的生存期定義為：LT(C)=P。生存期P對(duì)應(yīng)距離閾值的范圍即為同位模式存在的空間范圍。需指出，生存期度量的是模式的相對(duì)重要性，模式的生存期越長(zhǎng)，表示該模式相對(duì)越重要，這對(duì)于模式挖掘結(jié)果的篩選有著重要的指導(dǎo)作用。

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

試驗(yàn)首先采用模擬數(shù)據(jù)集將本文方法與經(jīng)典Colocation Miner方法、SSCSP方法進(jìn)行對(duì)比分析，以驗(yàn)證本文方法的有效性和可靠性；在此基礎(chǔ)上，進(jìn)一步給出實(shí)際應(yīng)用中的空間同位挖掘?qū)嵗治觥?/p>

2.1 模擬數(shù)據(jù)試驗(yàn)分析

模擬試驗(yàn)中包含5組數(shù)據(jù)(S1—S5)，分布范圍均為10×10的單元,空間分布如圖2所示。主要考慮以下3種情形：多要素實(shí)例、空間自相關(guān)、多要素類型。其中，S1、S2對(duì)應(yīng)多要素實(shí)例情形。S1中所有B要素實(shí)例均位于A要素實(shí)例的鄰域，但兩類要素?cái)?shù)目差別較大；S2中兩類要素?cái)?shù)據(jù)均較多，且都隨機(jī)分布在研究區(qū)域。S3、S4對(duì)應(yīng)空間自相關(guān)的情形。其中，S3中A要素分布呈空間自相關(guān)；B要素隨機(jī)分布；S4中A、B要素均表現(xiàn)出空間自相關(guān)，但兩者相互獨(dú)立。S5對(duì)應(yīng)多要素類型的情形，其中人為設(shè)定了兩種模式，同位模式{A,B,C,D}和互斥模式{E,F}。其中，同位模式由多要素類聚過程產(chǎn)生，鄰近距離為1；互斥模式由多類型Strauss過程[15](作用半徑為1，核半徑為0.5)生成。空間同位模式挖掘過程中，Colocation Miner和SSCSP算法中鄰近距離閾值設(shè)置采取文獻(xiàn)[12]中的建議，根據(jù)改進(jìn)的L函數(shù)進(jìn)行設(shè)置。本文方法多尺度中，模擬次數(shù)為999次，并將鄰近距離域均分為20等分。

由于S1—S4數(shù)據(jù)集僅包含兩類要素，將Cross-K函數(shù)結(jié)果作為基準(zhǔn)對(duì)空間同位模式挖掘結(jié)果進(jìn)行評(píng)價(jià)(圖3)，本文方法挖掘結(jié)果列于表1，對(duì)比分析圖3和表1，可得到如下結(jié)論：

圖2 5組模擬數(shù)據(jù)集Fig.2 Five simulated datasets

圖3 S1—S4數(shù)據(jù)集的Cross-K函數(shù)值(虛線:理論值;實(shí)線:觀測(cè)值;灰色條帶:95%置信區(qū)間)Fig.3 Cross-K function of S1—S4(dotted line:expected value;solid line:observed value;grey band:95% confidence interval)

表1 文本方法的顯著空間同位模式探測(cè)結(jié)果(S1—S4)

Tab.1 Results of significant co-location patterns discovered by the proposed multi-scale approach(S1—S4)

數(shù)據(jù)集同位模式最小距離閾值最大距離閾值生存期同位距離S1{A?B}0．183．348[0．48～0．95]S2{A?B}0．061．620S3{A?B}0．032．640S4{A?B}0．063．280

上述結(jié)果表明，對(duì)于包含兩種要素類型的簡(jiǎn)單數(shù)據(jù)集，SSCSP方法和本文方法均可有效識(shí)別真實(shí)的同位模式。進(jìn)一步，研究了多要素類型的空間同位挖掘，挖掘結(jié)果列于表2。

表2 顯著空間同位模式探測(cè)結(jié)果(S5)

S5數(shù)據(jù)集中,預(yù)設(shè)同位模式為{A-B-C-D},真實(shí)的同位模式應(yīng)為{A-B-C-D}的子集。由表2可知，盡管SSCSP算法可以發(fā)現(xiàn)所有正確的同位模式，但同時(shí)也存在著誤判現(xiàn)象，如模式{A-E-F}。這可能是由于模式擬合過程中存在誤差，且誤差隨要素類型的數(shù)目而累積。本文方法很好地識(shí)別本實(shí)例中所有的空間同位模式，既無漏判現(xiàn)象，也無誤判現(xiàn)象。

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

實(shí)際應(yīng)用中采取我國(guó)東北洪河濕地部分區(qū)域的生態(tài)群落數(shù)據(jù)。數(shù)據(jù)中包含毛果苔草、狹葉甜茅、漂筏苔草、小葉章、沼柳等類別。各類物種的空間分布如圖4所示，同位模式挖掘結(jié)果列于表3。

圖4 不同物種的空間分布圖Fig.4 Distribution of five species

模式生存期同位距離{毛果苔草，狹葉甜茅}9[20～180]{漂筏苔草，小葉章}7[20～140]{狹葉甜茅，沼柳}1[20～40]{漂筏苔草，沼柳}1[20～40]{毛果苔草，狹葉甜茅，沼柳}2[40～60]{漂筏苔草，小葉章，沼柳}3[40～80]

空間同位模式挖掘在生態(tài)群落分析中有著重要的應(yīng)用價(jià)值，結(jié)合物種的空間分布及本文方法挖掘結(jié)果，可知：顯著同位模式挖掘可避免模式的誤判發(fā)生。如圖4(e)所示,沼柳數(shù)目最多且散布在整個(gè)研究區(qū)域，Colocation Miner方法易將沼柳和其他所有物種誤判為同位模式。本文方法由于不受興趣度參數(shù)閾值的影響，可避免誤判發(fā)生；不同鄰近距離閾值下，同位模式挖掘結(jié)果并不完全相同。本文方法可以挖掘不同距離閾值下顯著同位模式，對(duì)數(shù)據(jù)中的同位模式進(jìn)行完整的描述；生存期可較好地度量多尺度挖掘結(jié)果中同位模式的相對(duì)重要性，從而使結(jié)果篩選和分析更加簡(jiǎn)單。顯然，該數(shù)據(jù)集中最顯著的同位模式為{毛果苔草-狹葉甜茅}和{漂筏苔草-小葉章}，且對(duì)應(yīng)的同位距離范圍分別為[20～180]和[20～140]。

3 結(jié) 論

針對(duì)空間同位模式挖掘中參數(shù)閾值設(shè)置缺乏先驗(yàn)的問題，本文發(fā)展了一種基于模式重建的顯著空間關(guān)聯(lián)模式多尺度挖掘方法。具體而言，通過互鄰近距離來界定鄰近距離的有效取值范圍，借助模式重建和假設(shè)檢驗(yàn)策略從而避開了興趣度閾值設(shè)置的難題，并引入生存期的概念對(duì)多尺度挖掘結(jié)果進(jìn)行評(píng)價(jià)。試驗(yàn)結(jié)果表明：本文方法可避免挖掘參數(shù)的設(shè)置問題及由此造成的模式誤判問題；算法挖掘結(jié)果中不僅包含了同位模式的類型，同時(shí)反映了模式存在的空間范圍，挖掘結(jié)果更加精確。

進(jìn)一步的研究工作主要集中在兩個(gè)方面：本文方法在模式重建的過程僅考慮了單一要素的分布特征，需進(jìn)一步研究協(xié)變量對(duì)空間分布的影響(如：土壤類型對(duì)某植物空間分布的影響)；方法采用了蒙特卡洛模擬，計(jì)算量較大，需研究分布式計(jì)算框架下的算法實(shí)現(xiàn)，以進(jìn)一步提升算法效率。

[1] 李光強(qiáng), 鄧敏, 朱建軍. 基于Voronoi圖的空間關(guān)聯(lián)規(guī)則挖掘方法研究[J]. 武漢大學(xué)學(xué)報(bào)(信息科學(xué)版), 2008, 33(12): 1242-1245. LI Guangqiang, DENG Min, ZHU Jianjun. Spatial Association Rules Mining Methods Based on Voronoi Diagram[J]. Geomatics and Information Science of Wuhan University, 2008, 33(12): 1242-1245.

[2] 謝超, 陳毓芬, 王英杰. Apriori算法在ACViS中用戶行為監(jiān)測(cè)數(shù)據(jù)挖掘中的應(yīng)用研究[J]. 測(cè)繪學(xué)報(bào), 2010, 39(4): 397-403.

XIE Chao, CHEN Yufen, WANG Yingjie. Application of Apriori Algorithm in User Action Monitoring Data Mining in Adaptive Cartographic Visualization System[J]. Acta Geodaetica et Cartographica Sinica, 2010, 39(4): 397-403.

[3] 田晶, 王一恒, 顏芬, 等. 一種網(wǎng)絡(luò)空間現(xiàn)象同位模式挖掘的新方法[J]. 武漢大學(xué)學(xué)報(bào)(信息科學(xué)版), 2015, 40(5): 652-660.

TIAN Jing, WANG Yiheng, YAN Fen, et al. A New Method for Mining Co-location Patterns between Network Spatial Phenomena[J]. Geomatics and Information Science of Wuhan University, 2015, 40(5): 652-660.

[4] HUANG Yan, SHEKHAR S, XIONG Hui. Discovering Colocation Patterns from Spatial Data Sets: A General Approach[J]. IEEE Transactions on Knowledge and Data Engineering, 2004, 16(12): 1472-1485.

[5] YOO J S, SHEKHAR S, SMITH J, et al. A Partial Join Approach for Mining Co-Location Patterns[C]∥Proceedings of the 12th Annual ACM International Workshop on Geographic Information Systems. New York: ACM, 2004: 241-249.

[6] YOO J S, SHEKHAR S. A Joinless Approach for Mining Spatial Colocation Patterns[J]. IEEE Transactions on Knowledge and Data Engineering, 2006, 18(10): 1323-1337.

[7] XIAO Xiangye, XIE Xing, LUO Qiong, et al. Density Based Co-Location Pattern Discovery[C]∥Proceedings of the 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York: ACM, 2008.

[8] EICK C F, PARMAR R, DING Wei, et al. Finding Regional Co-Location Patterns for Sets of Continuous Variables in Spatial Datasets[C]∥Proceedings of the 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York: ACM, 2008.

[9] DING Wei, EICK C F, YUAN Xiaojing, et al. A Framework for Regional Association Rule Mining and Scoping in Spatial Datasets[J]. GeoInformatica, 2011, 15(1): 1-28.

[10] MOHAN P, SHEKHAR S, SHINE J A, et al. A Neighborhood Graph based Approach to Regional Co-Location Pattern Discovery: A Summary of Results[C]∥Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York: ACM, 2011: 122-132.

[11] QIAN Feng, CHIEW K, HE Qinming, et al. Mining Regional Co-Location Patterns withkNNG[J]. Journal of Intelligent Information Systems, 2014, 42(3): 485-505.

[12] YOO J S, BOW M. Mining Spatial Colocation Patterns: A Different Framework[J]. Data Mining and Knowledge Discovery, 2012, 24(1): 159-194.

[13] QIAN Feng, HE Qinming, CHIEW K, et al. Spatial Co-Location Pattern Discovery Without Thresholds[J]. Knowledge and Information Systems, 2012, 33(2): 419-445.

[14] BARUA S, SANDER J. Mining Statistically Significant Co-location and Segregation Patterns[J]. IEEE Transactions on Knowledge and Data Engineering, 2014, 26(5): 1185-1199.

[15] GELFAND A E, DIGGLE P, GUTTORP P, et al. Handbook of Spatial Statistics[M]. Boca Raton, Florida: CRC Press, 2010.

[16] BARUA S, SANDER J. Mining Statistically Sound Co-Location Patterns at Multiple Distances[C]∥Proceedings of the 26th International Conference on Scientific and Statistical Database Management. New York: ACM, 2014.

[17] ILLIAN J, PENTTINEN A, STOYAN H, et al. Statistical Analysis and Modelling of Spatial Point Patterns[M]. Chichester: Wiley, 2008.

[18] WIEGAND T, HE Fangliang, HUBBELL S P. A Systematic Comparison of Summary Characteristics for Quantifying Point Patterns in Ecology[J]. Ecography, 2013, 36(1): 92-103.

[19] WIEGAND T, MOLONEY K A. Handbook of Spatial Point-Pattern Analysis in Ecology[M]. New York, NY: Chapman and Hall/CRC Press, 2014.

[20] WITKIN A. Scale-Space Filtering: A New Approach to Multi-Scale Description[C]∥Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing. San Diego, California, USA: IEEE, 1984: 150-153.

[21] LEUNG Y, ZHANG Jiangshe, XU Zongben. Clustering by Scale-Space Filtering[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22(12): 1396-1410.

[22] PEI Tao, ZHU A-Xing, 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.

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

A Multi-scale Method for Mining Significant Spatial Co-location Patterns

HE Zhanjun,LIU Qiliang,DENG Min,CAI Jiannan

Department of Geo-Informatics, Central South University, Changsha 410083, China

Spatial co-location patterns discovery aims to detect spatial features whose instances are frequently located in geographic proximity. Such patterns can reveal unknown regularity in geographic phenomena and they are helpful for decision-making. However, due to the little prior knowledge, it is difficult to specify thresholds for neighbor distance and prevalence index.As a result, the outcomes of most algorithms always include insignificant or even erroneous patterns. A pattern-reconstruction-based approach was proposed to discover only significant co-location patterns. Firstly, we introduce a new definition of MNND, which can identify the lower and upper bounds of neighbor distance threshold. Then, a null model was constructed based on the pattern reconstruction. On basis of that, selection of prevalence threshold is replaced by hypothesis testing. Finally, significant colocation patterns were mined at multiple distances and the results were evaluated by the notion of lifetime. The experimental results show that our approach could avoid the subjectivity in determining those thresholds, thereby improving the correctness and robustness.

data mining; spatial co-location; statistical significant patterns; pattern reconstruction; multi-scale

The National Natural Science Foundation of China (Nos. 41471385;41601410);The Hunan Provincial Science Fund for Distinguished Young Scholars (No.14JJ1007); State Key Laboratory of Resources and Environmental Information System;The Science and Technology Foundation of Hunan Province(No.2015SK2078)

LIU Qiliang

何占軍，劉啟亮，鄧敏，等.顯著空間同位模式的多尺度挖掘方法[J].測(cè)繪學(xué)報(bào)，2016,45(11)：1335-1341.

10.11947/j.AGCS.2016.20150371.

HE Zhanjun,LIU Qiliang,DENG Min,et al.A Multi-scale Method for Mining Significant Spatial Co-location Patterns[J]. Acta Geodaetica et Cartographica Sinica,2016,45(11):1335-1341. DOI:10.11947/j.AGCS.2016.20150371.

P208

A

1001-1595(2016)11-1335-07

國(guó)家自然科學(xué)基金(41471385;41601410)；湖南省自然科學(xué)杰出青年基金(14JJ1007)；資源與環(huán)境信息系統(tǒng)國(guó)家重點(diǎn)實(shí)驗(yàn)室開放基金；湖南省科技計(jì)劃項(xiàng)目(2015SK2078)

2015-07-13

修回日期： 2016-09-10

何占軍(1987—)，男，博士生，主要研究方向?yàn)闀r(shí)空關(guān)聯(lián)模式挖掘方法及應(yīng)用。First author： HE Zhanjun (1987—)，male，PhD candidate, majors in spatial-temporal association patterns mining.

E-mail： hezhanjun000@126.com

劉啟亮

E-mail： qiliang.liu@csu.edu.cn