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

關(guān)鍵詞： 星形關(guān)聯(lián)模型； 拓撲關(guān)聯(lián)模式； 粒度計算； 時空數(shù)據(jù)挖掘

中圖分類號：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 引言

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

1 基于事件的星形關(guān)聯(lián)模型

定義1 基于事件的星形關(guān)聯(lián)模型定義為一個五元組EM=，參數(shù)含義如下：

e：稱為時空事件，其是來源于時空數(shù)據(jù)庫；

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

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

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}，這里核心元素與每個非核心元素之間有且僅有一種關(guān)聯(lián)。

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

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

E即非核心元素集，為：上午morning，下午afternoon，晚上night，學(xué)校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描述為：去年學(xué)校南邊附近修建了一條鐵路橫跨護城河。

ec即核心元素為鐵路railway；

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

事件用謂詞表達為：

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

2 基于粒度計算的時空拓撲關(guān)聯(lián)模式挖掘

2.1 基于星形關(guān)聯(lián)模型的粒度計算

定義2 基于星形關(guān)聯(lián)模型的時空信息系統(tǒng)定義為一個六元組STIS=（U，E，F(xiàn)，{Vf|f∈F}，L，I），各參數(shù)含義如下：

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

E：概括集，論域?qū)ο蟮姆呛诵脑仡悇e概括集；

F：要素集，用于描述論域?qū)ο蟮闹饕煞郑词录枋龅闹饕煞?，本文包括時間、方位、距離和拓撲關(guān)系；

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

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

；

I：信息函數(shù)，即I：U→V。

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

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

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

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

ζ：稱為內(nèi)涵，ζ=（ζe）（ζe∈V，e∈E，f∈F，ζ∈L）；

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

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

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

2.2 頻繁時空拓撲關(guān)聯(lián)模式挖掘

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

Step1：掃描時空數(shù)據(jù)庫，建立時空信息系統(tǒng)STIS=（U，E，F(xiàn)，{Vf|f∈F}，L，I）；

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

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

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

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

Step6：繼續(xù)增長連接計算頻繁時空信息粒的內(nèi)涵，即重復(fù)執(zhí)行Step4-5，直到|C|=0；

Step7：輸出F。

3 結(jié)束語

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

參考文獻：

[1] 杜寧睿，李淵.規(guī)劃支持系統(tǒng)（PSS）及其在城市空間規(guī)劃決策中的應(yīng)用[J].武漢大學(xué)學(xué)報（工學(xué)版），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