基于星形模型的時(shí)空拓?fù)潢P(guān)聯(lián)模式挖掘

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

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

中圖分類號：TP311 文獻(xiàn)標(biāo)志碼：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)計(jì)[4]等。近些年來，挖掘空間關(guān)聯(lián)模式也取得了許多研究成果，這些研究成果主要可分為兩類：一是基于點(diǎn)、線、面數(shù)值地理要素的頻繁關(guān)聯(lián)模式[5-7]，即將數(shù)值屬性轉(zhuǎn)換成布爾量進(jì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í)間要素，且模型表達(dá)的信息維數(shù)不夠多，數(shù)據(jù)結(jié)構(gòu)冗余。近些年來，隨著地理信息系統(tǒng)、移動計(jì)算技術(shù)和多媒體數(shù)據(jù)庫的不斷發(fā)展，同時(shí)支持時(shí)間和空間的數(shù)據(jù)建模和時(shí)空數(shù)據(jù)庫系統(tǒng)已成為研究熱點(diǎn)。目前時(shí)態(tài)拓?fù)潢P(guān)系和時(shí)空拓?fù)潢P(guān)系的定義還沒有一個(gè)完整合理的定義，這對研究時(shí)空數(shù)據(jù)庫模型是極為不利的。時(shí)空信息的認(rèn)知和數(shù)據(jù)模型的研究進(jìn)展是時(shí)空數(shù)據(jù)挖掘研究的基礎(chǔ)，時(shí)空數(shù)據(jù)挖掘的理論研究主要受到空間數(shù)據(jù)挖掘和時(shí)態(tài)數(shù)據(jù)挖掘研究的影響，并以經(jīng)典的數(shù)據(jù)挖掘理論為基礎(chǔ)，挖掘時(shí)空知識或規(guī)則。于是，本文首先針對時(shí)空數(shù)據(jù)庫，提出了一種基于事件的星形關(guān)聯(lián)模型，然后根據(jù)這種模型的特點(diǎn)，探討了頻繁時(shí)空拓?fù)潢P(guān)聯(lián)模式的挖掘問題。

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

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

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

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

F：稱為事件要素，用于描述事件的主要成分，本文這里包括時(shí)間（time）、方位（orientation）、距離（distance）和拓?fù)洌╰opology）關(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}，這里核心元素與每個(gè)非核心元素之間有且僅有一種關(guān)聯(lián)。

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

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

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

事件用謂詞表達(dá)為：

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é)校南邊附近修建了一條鐵路橫跨護(hù)城河。

ec即核心元素為鐵路railway；

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

事件用謂詞表達(dá)為：

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

2 基于粒度計(jì)算的時(shí)空拓?fù)潢P(guān)聯(lián)模式挖掘

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

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

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

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

F：要素集，用于描述論域?qū)ο蟮闹饕煞郑词录枋龅闹饕煞郑疚陌〞r(shí)間、方位、距離和拓?fù)潢P(guān)系；

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

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

；

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

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

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

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

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

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

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

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

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

2.2 頻繁時(shí)空拓?fù)潢P(guān)聯(lián)模式挖掘

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

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

Step2：計(jì)算出所有的原子時(shí)空信息粒ASTIG=（ζ，ψ（ζ））；

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

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

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

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

Step7：輸出F。

3 結(jié)束語

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

參考文獻(xiàn)：

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