特定空間對象同位模式挖掘算法研究

摘要：空間同位模式挖掘研究主要以區(qū)域劃分為基礎(chǔ)，考慮對象實例兩兩之間的距離關(guān)系，這樣挖掘出的同位模式是雙向?qū)ΨQ的。但區(qū)域的劃分起止位置不確定，可能出現(xiàn)由于區(qū)域劃分的不一致而得到不一樣的空間同位模式結(jié)果。該文提出以指定對象為核心的空間同位模式挖掘，這樣不必?fù)?dān)心區(qū)域劃分的起止位置對挖掘結(jié)果的影響，而且更能有針對性地發(fā)現(xiàn)特定空間對象與其它哪些對象具有空間同位關(guān)系。

關(guān)鍵詞：空間數(shù)據(jù)庫；空間數(shù)據(jù)挖掘；空間同位模式

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2015）04-0082-04

Abstract： The research concerning over Spatial data mining based mainly on partitioning of areas， in regard to the spatial distance between each object instance， Co-location pattern obtained will be symmetric. Yet the position where the partition begins and ends is indeterminate， therefore the Spatial Co-location pattern obtained could vary due to different partition. This paper proposed a specified object centered Spatial data mining method in case of inaccuracy caused by partitioning position， moreover， the finding of Spatial Co-location pattern between specific spatial object and the others can get more well-focused.

Key words： spatial database； spatial data mining； spatial Co-location pattern

空間數(shù)據(jù)挖掘是從大量空間數(shù)據(jù)中發(fā)現(xiàn)潛在知識的過程。目前，空間數(shù)據(jù)挖掘技術(shù)主要包括空間分類、空間聚類、空間離群挖掘、空間關(guān)聯(lián)規(guī)則以及空間同位模式挖掘。其中空間同位主要關(guān)注空間對象之間在一定區(qū)域內(nèi)同時出現(xiàn)的關(guān)系，這些空間對象的實例在地理空間上接近并且頻繁出現(xiàn)，期間蘊涵了某些關(guān)聯(lián)關(guān)系。因此，空間同位模式的研究對于發(fā)現(xiàn)在地理位置上具有依存性、關(guān)聯(lián)性的對象有著重要的幫助和意義，例如用于挖掘共生植被分布情況、城市公共資源布局決策等。

空間同位模式挖掘研究主要以區(qū)域劃分為基礎(chǔ)，考慮對象實例兩兩之間的距離關(guān)系，這樣挖掘出的同位模式是雙向?qū)ΨQ的。但區(qū)域的劃分起止位置不確定，可能出現(xiàn)由于區(qū)域劃分的不一致而得到不一樣的空間同位模式結(jié)果，如Meter Celick的分區(qū)模式挖掘算法[1]，從四個四邊形中得到的頻繁同位模式，與它們中間的重疊區(qū)域得到的同位模式不一樣。該文提出以指定關(guān)注對象為中心的同位模式挖掘，也即原來我們挖掘的是“哪些對象具有同位關(guān)系”，而現(xiàn)在我們考慮的是“這個對象與哪些對象具有同位關(guān)系”。這樣的挖掘結(jié)果更具針對性和實用性，對決策支持或是空間布局等更具指導(dǎo)性。

1 相關(guān)概念

4 實驗及評價

算法用模擬數(shù)據(jù)進(jìn)行實驗，JAVA編寫程序，通過在程序入口和出口處使用函數(shù) System.currentTimeMillis（） 計算時間差，從而獲得程序運行所需時間開銷。

4.1 算法時間消耗

隨著最小參與度閾值的增加，k階頻繁同位模式減小，從而k+1階候選表實例數(shù)也快速減少，算法時間開銷也隨之減小。

4.2 對象數(shù)對算法運行時間的影響

以文獻(xiàn)1中的Zonal Co-location挖掘算法和本文的SDCLM算法進(jìn)行對比實驗，在同一距離閾值要求下，SDCLM算法可能會得到更多的頻繁同位模式，因為SDCLM算法考慮的是某個特定對象周圍的同位模式，而Zonal Co-location算法考慮的是兩兩對象互為同位的模式。

當(dāng)距離閾值增大到一個較大范圍時，兩個算法得到頻繁同位模式集基本一致，因為距離閾值范圍的增大也就意味著包容的對象實例數(shù)增多，則對象實例的單向同位和互為同位就趨于平衡，因而頻繁模式數(shù)差異不大。

5 小結(jié)

本文提出挖掘特定對象的空間同位模式概念，旨在發(fā)現(xiàn)更具針對性的空間同位模式，尋找與該對象在同一區(qū)域范圍內(nèi)頻繁出現(xiàn)的對象。為此，對傳統(tǒng)空間同位模式的定義進(jìn)行了相應(yīng)調(diào)整，定義了一組相匹配的概念，并給出了挖掘算法及實驗分析。接下來還將考慮對空間同位模式挖掘的效率問題以及有效性問題進(jìn)行研究。

參考文獻(xiàn)：

[1] Mete Celik，James M.Kanf，Shashi Shekhar. Zonal Co-location Pattern Discovery with Dynamic Parameters[C].Proceedingof the 7th IEEE International Conference on Data Mining（ICDM 2007）.2007

[2] 周劍云，王麗珍，楊增芳.基于加權(quán)歐氏距離的空間Co-location模式挖掘算法研究[J].計算機科學(xué)，2014，41（6A）：425-428.

[3] 高世健，王麗珍等.基于凝聚層次聚類的co_location模式挖掘[J].廣西師范大學(xué)學(xué)報：自然科學(xué)版，2011（29）：167-173.

[4] Yoo Jin Soung，Shekhar S，Celik M.A Join-less Approach for Co-location Pattern Mining： A Summary of Results[C].Proceedings of the IEEE International Conference on Data Mining （ICDM），Houston，USA，2005.

[5] Yoo Jin Soung，Shekhar S.A partial join approach for mining co-location patterns[A] Foser D P，ruz IF，Ronthaler M ，eds.12thACM International Workshop on Geographic Information Systems[C]. Washington，DC，USA，2004：241-249.