基于星形模型的時空拓撲關聯模式挖掘

摘 要： 為了簡捷表達多維時空拓撲關聯模式，針對時空數據庫的事件，提出了一種基于事件的星形關聯模型，該模型能夠表示點線面以外的更多時空信息；針對這種模型提出了一種基于粒度計算的時空拓撲關聯模式挖掘算法，該算法只需掃描一次時空數據庫，避免了重復計算，有效地提高了挖掘效率。

關鍵詞： 星形關聯模型； 拓撲關聯模式； 粒度計算； 時空數據挖掘

中圖分類號：TP311 文獻標志碼：A 文章編號：1006-8228（2013）04-07-02

Spatio-temporal topology associated pattern mining based on star model

Fang Gang， Ying Hong， Tu Chengsheng， Guo Jiao， Liu Huacheng

（Chongqing Three Gorges University， Wanzhou， Chongqing 404000， China）

Abstract： In order to simply express multi-dimensional spatio-temporal topology associated patterns， aiming at events of spatial-temporal database， a star association model based on event is proposed in this paper. This model can display more spatio-temporal information besides point， line and plane. A mining algorithm of spatio-temporal topology associated patterns based on granular computing is presented for the star association model. This algorithm only scans spatio-temporal database once， avoids repeating computation and improves mining efficiency.

Key words： star association model； topology associated patterns； granular computing； spatio-temporal data mining

0 引言

發現空間關聯模式是空間數據挖掘的重要任務之一，目前，空間關聯模式已經在很多領域得到了廣泛應用，如城市交通[1]、社會安全[2]、氣候預測[3]和人口統計[4]等。近些年來，挖掘空間關聯模式也取得了許多研究成果，這些研究成果主要可分為兩類：一是基于點、線、面數值地理要素的頻繁關聯模式[5-7]，即將數值屬性轉換成布爾量進行傳統關聯模式挖掘；二是基于空間對象及其布局關系離散地理要素的頻繁關聯模式[8，9]，即將空間對象轉換為類別集按布爾關聯模式挖掘。然而這些研究成果大多從空間數據庫出發，沒有充分考慮時間要素，且模型表達的信息維數不夠多，數據結構冗余。近些年來，隨著地理信息系統、移動計算技術和多媒體數據庫的不斷發展，同時支持時間和空間的數據建模和時空數據庫系統已成為研究熱點。目前時態拓撲關系和時空拓撲關系的定義還沒有一個完整合理的定義，這對研究時空數據庫模型是極為不利的。時空信息的認知和數據模型的研究進展是時空數據挖掘研究的基礎，時空數據挖掘的理論研究主要受到空間數據挖掘和時態數據挖掘研究的影響，并以經典的數據挖掘理論為基礎，挖掘時空知識或規則。于是，本文首先針對時空數據庫，提出了一種基于事件的星形關聯模型，然后根據這種模型的特點，探討了頻繁時空拓撲關聯模式的挖掘問題。

1 基于事件的星形關聯模型

定義1 基于事件的星形關聯模型定義為一個五元組EM=，參數含義如下：

e：稱為時空事件，其是來源于時空數據庫；

ec：稱為模型的核心元素，其是時空事件的主體對象；

F：稱為事件要素，用于描述事件的主要成分，本文這里包括時間（time）、方位（orientation）、距離（distance）和拓撲（topology）關系；

P：稱為事件要素的謂詞值域集；若P={ptime，porientation，pdistance，ptopology}，本文各要素的謂詞值域則分別表示為：

ptime={p|isTemporal（operation），operation∈[before，after，equal]}；

porientation={p|isOrientation（operation），operation∈[east-of，west-of，south-of，north-of]}；

pdistance={p=isDistance（operation），operation∈[close_to，far_away]}；

ptopology={p|isTopology（operation），operation∈[disjoint，cover，

contain，touch，coveredby，inside，overlap]}；

E：稱為模型的非核心元素，可表示為E={e1，e2，…，em}，這里核心元素與每個非核心元素之間有且僅有一種關聯。

例1，事件e描述為：下午一點，一輛出租車從學校出發，沿著濱江路向東開往火車站。

ec即核心元素為出租車taxi；

E即非核心元素集，為：上午morning，下午afternoon，晚上night，學校school，江river，火車站station；

事件用謂詞表達為：

isTemporal（before（ec，night），after（ec，morning），equal（ec，

afternoon））isOrientation（east-of（ec））isDistance（close_to（ec，school），far_away（ec，station））isTopology（touch（ec，river））。

例2，事件e描述為：去年學校南邊附近修建了一條鐵路橫跨護城河。

ec即核心元素為鐵路railway；

E即非核心元素集，為：今年this，去年last，學校school，護城河river；

事件用謂詞表達為：

isTemporal（before（ec，this），equal（ec，last））isOrientation（south-of（ec）isDistance（close_to（ec，school））isTopology（overlap（ec，river））。

2 基于粒度計算的時空拓撲關聯模式挖掘

2.1 基于星形關聯模型的粒度計算

定義2 基于星形關聯模型的時空信息系統定義為一個六元組STIS=（U，E，F，{Vf|f∈F}，L，I），各參數含義如下：

U：論域，是一個非空有限集，即時空數據庫中事件的集合；

E：概括集，論域對象的非核心元素類別概括集；

F：要素集，用于描述論域對象的主要成分，即事件描述的主要成分，本文包括時間、方位、距離和拓撲關系；

Vf：謂詞集，要素f（f∈F）的謂詞值域；

L：謂詞描述語言，若V（e（θ）∈E*?E）為謂詞值域，則謂詞描述語言可表達如下：

；

I：信息函數，即I：U→V。

定義3 時空信息粒定義為一個二元組STIG=（ζ，ψ（ζ）），參數含義如下：

ζ：是粒度的內涵，f∈F，k=1，2，…，|ζ|，ζ∈L）；

ψ（ζ）：是粒度的外涵，。

定義4 原子時空信息粒也是一個時空信息粒STIG=（ζ，ψ（ζ）），參數含義如下：

ζ：稱為內涵，ζ=（ζe）（ζe∈V，e∈E，f∈F，ζ∈L）；

ψ（ζ）：稱為外涵ψ（ζ）={u∈U|I（u）=ζe}。

定義5 時空信息粒的“并”運算定義為?，設兩個時空信息粒被分別表示為STIGα=（ζα，ψ（ζα））和STIGβ=（ζβ，ψ（ζβ）），則?定義為：

STIG=（ζ，ψ（ζ））=STIGα?STIGβ=（ζα∪ζβ，ψ（ζα）∩ψ（ζβ））。

2.2 頻繁時空拓撲關聯模式挖掘

頻繁時空拓撲關聯模式挖掘就是從時空數據庫中挖掘事件發生時，主體對象與事件非核心元素類別集之間時空拓撲關系之間的關聯。本文借助傳統關聯模式的經典挖掘算法Apriori的思想，從時空數據庫中挖掘頻繁時空拓撲關聯模式，具體步驟如下：

Step1：掃描時空數據庫，建立時空信息系統STIS=（U，E，F，{Vf|f∈F}，L，I）；

Step2：計算出所有的原子時空信息粒ASTIG=（ζ，ψ（ζ））；

Step3：發現頻繁的原子時空信息粒ASTIG*=（ζ，ψ（ζ）），即找出|ψ（ζ）|≥minisup的原子時空信息粒，并將粒度的內涵ζ=operation（ec，e）存入F和C中；

Step4：增長連接計算，即ζα=operation（ec，eα）ζβ=operation（ec，eβ）（eα≠eβ，ζα∈C，ζβ∈C）；

Step5：計算出時空信息粒度STIG=（ζ，ψ（ζ）），若|ψ（ζ）|≥minisup，則將粒度內涵ζ存入C中，并刪除F中ζ的子集后，同時將ζ寫入F中；

Step6：繼續增長連接計算頻繁時空信息粒的內涵，即重復執行Step4-5，直到|C|=0；

Step7：輸出F。

3 結束語

本文首先提出了一種基于事件的星形關聯模型，這種模型除了能夠同時表達時空信息外，還能表達空間對象的其他屬性信息，表達形式方便靈活；然后提出一種基于粒度計算的時空拓撲關聯模式挖掘算法，該算法掃描一次時空數據庫，獲取原子時空信息粒，為支持數據計算提供了方便，避免了重復掃描數據庫，有效地提高了挖掘效率。這種模型靈活構建的特點能夠應用于云計算挖掘時空拓撲關聯模式，這也是我們進一步研究的重點。

參考文獻：

[1] 杜寧睿，李淵.規劃支持系統（PSS）及其在城市空間規劃決策中的應用[J].武漢大學學報（工學版），2005.38（1）：137-142

[2] Lee I.， Phillips P.， Urban crime analysis through areal categorized

multivariate associations mining[J].Applied Artificial Intelligence，2008.22（5）：483-499

[3] Huang Y.， Kao L.， Sandnes F.， Predicting ocean salinity and

temperature variations using data mining and fuzzy inference [J].International Journal of Fuzzy Systems，2007.9（3）：143-151

[4] Chang C.， Shyue S.， Association rules mining with GIS： An

application to Taiwan census 2000[C].In Proceedings of the 6th international conference on Fuzzy systems and knowledge discovery （Tianjin， China），2009：65-69

[5] Mennis J.， Liu J.， Mining association rules in spatio-temporal data：

An analysis of urban socioeconomic and land cover change [J].Transactions in GIS，2005.9（1）：5-17

[6] Lee I.， Mining multivariate associations within GIS environments[C].

In Proceedings of 17th International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems（Ottawa， Canada），2004：1062-1071

[7] Ding W.， Eick C.， Wang J.， et al.， A framework for regional

association rule mining in spatial datasets [C].In Proceedings of the Sixth IEEE International Conference on Data Mining （Hong Kong），2006：851-856

[8] Yang H.， Parthasarathy S.， Mining spatial and spatio-temporal

patterns in scientific data [C].In Proceedings of 22nd International Conference on Data Engineering Workshops （Atlanta， GA， USA），2006：146

[9] Yang H.， Parthasarathy S.， Mehta S.， Mining spatial object

associations for scientific data [C]. In Proceedings of the 19th International Joint Conference on Artificial Intelligence （Edinburgh， UK），2005：902-907