“多元”關(guān)聯(lián)模式的時空數(shù)據(jù)挖掘

陳新保 ，LI Song-nian，朱建軍，陳建群

(1.中南大學(xué) 地球科學(xué)與信息物理學(xué)院，湖南 長沙，410083；2. 瑞爾森大學(xué) 土木工程系，加拿大 多倫多，M5B 2K3)

空間數(shù)據(jù)關(guān)聯(lián)挖掘為基于空間關(guān)聯(lián)的知識獲取提供了途徑，在交通[1]、生物[2-3]、公共安全[4]、氣候[5]、人口普查[6]等領(lǐng)域有廣泛的用途。經(jīng)過數(shù)十年的發(fā)展，國內(nèi)外對空間數(shù)據(jù)關(guān)聯(lián)模式挖掘的研究[2,7-14]已取得一些成果。對空間關(guān)聯(lián)挖掘的研究主要體現(xiàn)在兩大方面：一方面，基于數(shù)值型的地理要素的區(qū)域(Region)關(guān)聯(lián)規(guī)則挖掘，即地理要素的“點”、“線”和“面”狀數(shù)值轉(zhuǎn)化為定性“級別”或“布爾型”，對其在參考區(qū)域內(nèi)的“交易頻繁”分析，適合基于位置的空間數(shù)據(jù)類型，如柵格數(shù)據(jù)[15]或?qū)傩灾档牡乩硪亍ennis等[9]用關(guān)聯(lián)分析法，很好地詮釋了社會地理要素(社會經(jīng)濟指標(biāo))與自然地理要素(土地覆蓋值)的因果機制；但在關(guān)聯(lián)分析中，局限于“面域”空間維的關(guān)聯(lián)挖掘。Lee等[4,16]提出了“點”、“線”和“面”等空間多維的關(guān)聯(lián)挖掘分析，但他們都將“點”和“線”特性值轉(zhuǎn)化為“面域”值，仍然是在“面域”的基礎(chǔ)上進(jìn)行分析。同樣，Ding等[17]提出了基于“面域”關(guān)聯(lián)挖掘的框架，并引入“面域”關(guān)聯(lián)規(guī)則的空間影響度(Scoping)。另一方面，基于離散型對象在整個空間數(shù)據(jù)集中的“交易”分析，此時“交易”的對象可以是空間對象本身，也可對象間的關(guān)系。Yang等[10,18]基于空間對象的距離關(guān)系探討了“星型(star)”、“序列型(sequence)”和“晶體型(clique)”等關(guān)聯(lián)模式。Lee等[19]則對“trajectory”關(guān)聯(lián)模式進(jìn)行了探討。不過，這些組合式關(guān)聯(lián)規(guī)則在空間對象和關(guān)系上都較單一，屬于同類和同質(zhì)。Huang等[20]已經(jīng)擴展到復(fù)雜空間對象(例如線和多邊形異類)，但都最終當(dāng)作“面點”對象來挖掘。對于挖掘算法，Agrawal等[21]首先提出關(guān)聯(lián)規(guī)則模型，并給出求解算法AIS來挖掘顧客交易數(shù)據(jù)庫中項集間的關(guān)聯(lián)規(guī)則問題。此后，諸多研究人員對關(guān)聯(lián)規(guī)則的挖掘算法進(jìn)行了研究，出現(xiàn)了SETM和Apriori等算法。其中，Apriori已經(jīng)成為關(guān)聯(lián)規(guī)則模型中的經(jīng)典算法，許多相關(guān)研究[12,22-25]對該算法進(jìn)行了改進(jìn)，其核心是基于兩階段頻集思想的遞推算法，即用頻繁的(k–1)項集生成候選的頻繁k-項集和用數(shù)據(jù)庫掃描和模式匹配計算候選集的支持度和置信度；Apriori算法要求關(guān)聯(lián)規(guī)則在分類上屬于單維、單層、布爾關(guān)聯(lián)規(guī)則。但是，上述空間關(guān)聯(lián)模式和挖掘算法存在以下問題：一是挖掘源主要集中于空間數(shù)據(jù)庫，而缺乏考慮時間或淡化時間在整個挖掘過程的存在；二是空間關(guān)聯(lián)維度局限于單維，如(X→Y)規(guī)則，要求X和Y為同類型要素，即點對點、線對線和面對面等；空間關(guān)聯(lián)規(guī)則構(gòu)建較單一：要求同質(zhì)，如X→Y規(guī)則可能局限于空間拓?fù)湟?guī)則，對混合的空間關(guān)聯(lián)規(guī)則研究較少；三為挖掘算法針對單規(guī)則，不適合多規(guī)則組合式模式。由此，本文作者對空間關(guān)聯(lián)模式挖掘進(jìn)行了進(jìn)一步工作：(1) 挖掘源從空間數(shù)據(jù)庫擴展到時空數(shù)據(jù)庫，挖掘的對象也從空間數(shù)據(jù)擴展到時空數(shù)據(jù)，即從大量歷史地理空間要素中挖掘某種時空關(guān)聯(lián)模式；(2) 空間關(guān)聯(lián)規(guī)則以空間關(guān)系和時態(tài)關(guān)系為主，空間關(guān)聯(lián)的對象擴展至地理要素，即要素“多類型”和關(guān)聯(lián)“多規(guī)則”；(3) 用圖論構(gòu)建和表達(dá)如“星型”和“序列型”等多類型要素下的多規(guī)則的關(guān)聯(lián)組合模式，即“多元”關(guān)聯(lián)模式；(4) 探討“多元”關(guān)聯(lián)模式下的挖掘算法。

1 問題描述

空間對象關(guān)聯(lián)模式類型如圖1所示。與傳統(tǒng)空間關(guān)聯(lián)組合模式不同，“多元”關(guān)聯(lián)模式呈現(xiàn)以下特性：(1) 挖掘?qū)ο髷U展至地理要素，可處理復(fù)雜的空間對象(如線和面等概化的地理要素)；(2) 地理要素間的多種空間關(guān)系(如距離、方向和拓?fù)涞?同時存在；(3) 要素間存在著時態(tài)關(guān)系；(4) 要素間可能存在某地理經(jīng)濟要素(如GDP)跟地理基礎(chǔ)要素的約束關(guān)系。此時，模式存在“多類型”和“多關(guān)系”下的多個要素共同參與的關(guān)聯(lián)組合，將此類組合統(tǒng)稱為“多元”關(guān)聯(lián)模式。而對此類模式的挖掘和發(fā)現(xiàn)稱之為“多元”關(guān)聯(lián)模式的時空數(shù)據(jù)挖掘。在此特說明，本文所涉及的挖掘關(guān)聯(lián)要素多源于有限的離散要素集。顯然，“多元”的概念可概括為：要素有多個且呈現(xiàn)類型多樣性(即“多類型”)以及要素間關(guān)系異質(zhì)多樣性(即“多規(guī)則”)?，F(xiàn)就“多元”關(guān)聯(lián)模式構(gòu)建與挖掘中一些基本概念和問題表述給予定義和形式化闡述。

定義 1 地理要素。地理要素(Geographic feature,GF)是指地理空間中具有確定的位置和形態(tài)特征的有地理意義的實體，它是現(xiàn)實世界的地理實體在計算機中的表達(dá)。根據(jù)要素特征不同，地理要素可分成多種類型(FeatureType)，如點、線、面和實體等幾何要素。依據(jù)要素的功能不同，地理要素亦可分成多種類型，如城市規(guī)劃中的道路(Road)、房屋等，而道路又細(xì)分成高速路、鐵路等；房屋可劃分為居住和商業(yè)等。設(shè)F={f1,f2, …,fr}為地理要素類別集合。

圖1 空間對象關(guān)聯(lián)模式類型Fig.1 Type of association patterns

規(guī)定1 設(shè)時空數(shù)據(jù)庫D={＜o(jì)bj1,obj2，…＞,…,objN}，則地理對象集＜o(jì)bj1,obj2，…,objm＞∈fi為地理要素類別fi的m個具體實例(Instance)或記錄(Record)，每個實例的屬性集可表示為＜Instance Id,FeatureType,fId＞。fId為fi所屬要素類型的標(biāo)識符；實例具有時態(tài)性，其時間屬性描述為＜sTime,duration＞，即sTime為起始時間(ts)，duration為存在持續(xù)時間td。

定義 2 要素關(guān)聯(lián)規(guī)則。要素關(guān)聯(lián)規(guī)則(Feature association rule, FAR)是反映地理要素間關(guān)系(或結(jié)構(gòu))一些顯性特征，是區(qū)域地理要素在空間和時間上的組合方式的最基本描述。關(guān)注空間數(shù)據(jù)，強調(diào)要素在時間和空間上的位置布局，則時間、方向、距離和拓?fù)涫且仃P(guān)聯(lián)規(guī)則描述、表達(dá)與獲取的最基本規(guī)則。

規(guī)定2 設(shè)要素關(guān)聯(lián)規(guī)則函數(shù)RL，它對每個命題邏輯語義La中的要素fi，fj賦以實體RL(Fp)，則有：

其中：isTemp指要素fi和fj間的時態(tài)關(guān)系；isDist指要素fi和fj間的距離關(guān)系；isOrien指要素fi和fj間的方位關(guān)系；isTopo指要素fi和fj間的拓?fù)潢P(guān)系?？梢杂脀ij=RL(fi,fj) 表征RL(fi,fj)規(guī)則集函數(shù)，例如橫穿某城市的干道fi于2000年順利通車，其后某二環(huán)線fj于2005年竣工，兩者存在空間相交和時間先后關(guān)系，于是，可表達(dá)成：wij=RL(fi,fj)={before,far-away,NO,intersect}或所對應(yīng)的索引標(biāo)識符[13]形式{101, 200, 300, 415}。

4種關(guān)聯(lián)關(guān)系具體描述如下。

(1) 時態(tài)關(guān)系，如時間先后等；時態(tài)謂詞描述：isTemp(operator1)。其中：operator1為時態(tài)算子，如before(前)/after(后)/equal(相等)/start(起始)/meet(相接)/overlap(相疊)等。

(2) 空間定向，即 GIS方位謂詞描述：isOrien(operator2)，其中，operator2為方位算子，如east-of(東)/west-of(西)/south-of(南)/north-of(北)等。

(3) 空間距離，距離謂詞描述為isDist(operator3)。其中：operator3為距離算子，如DisConstant(距離常數(shù))、CloseTo(接近關(guān)系)和Far-away(遠(yuǎn)離關(guān)系)。以及定量表示距離的算子distance；若distance(x, y)≤DisConstant，則x，y的距離關(guān)系為CloseTo，否則，為Far-away。

(4) 拓?fù)潢P(guān)系，即 GIS拓?fù)渲^詞描述：isTopo(operator4)，其中，operator4 為拓?fù)渌阕樱鏳isjoint(相隔)/intersect(相交)/contain(包含)等。

定義 3 “多元”關(guān)聯(lián)模式挖掘。“多元”關(guān)聯(lián)模式容許多類型的地理要素和多異質(zhì)的關(guān)聯(lián)規(guī)則同時存在，那么挖掘“多元”關(guān)聯(lián)模式挖掘的過程就是對多種規(guī)則組合式的發(fā)現(xiàn)。本文只涉及時空數(shù)據(jù)關(guān)聯(lián)挖掘，其時空數(shù)據(jù)源于有限的離散地理要素集。此時，時空關(guān)聯(lián)挖掘過程的形式化定義為：

式中：Find(P,F,D)就是對n個“顯著”RL關(guān)聯(lián)規(guī)則(n≥2)的關(guān)聯(lián)組合，從而形成關(guān)聯(lián)規(guī)則P模式。

規(guī)定 3 與傳統(tǒng)關(guān)聯(lián)規(guī)則挖掘一樣，將“支持度(Support)”和“置信度(Confidence)”確定為衡量一個要素關(guān)聯(lián)規(guī)則重要性的2個關(guān)鍵性指標(biāo)。在關(guān)聯(lián)規(guī)則挖掘中，由于地理要素缺乏“交易”概念，在此用要素間存在某種時空“關(guān)系”來表征一種“交易”，其在時空數(shù)據(jù)庫中的多次出現(xiàn)來表達(dá)“頻繁(Frequency)”特性。設(shè)F={f1,f2, …,fr}為r個地理要素類別集，每個類別集都包含數(shù)量不等的地理對象；R={r1,r2, …,rn}為n個要素關(guān)聯(lián)關(guān)系。則類型不同的2個要素間(X→Y)的某種關(guān)聯(lián)規(guī)則表達(dá)及其“支持度(sup)”和“置信度(conf)”計算如下：

其中：?為“關(guān)系”數(shù)量算子。式(3)求解支持度表征著某空間或時間關(guān)系的熱度；式(4)求解表達(dá)某空間關(guān)系在某時態(tài)關(guān)系上的強度。要素關(guān)系關(guān)聯(lián)規(guī)則X→Y(S，%，C，%)，存在支持度(S，%)和置信度(C，%)。表1所示為支持度和置信度的計算過程。

規(guī)定4 關(guān)聯(lián)規(guī)則等同性、層次性和顯著差異性。關(guān)聯(lián)規(guī)則中的拓?fù)洹⒎轿缓途嚯x等關(guān)系同時存在，且這些關(guān)系都置于時態(tài)中。它們的重要性在本質(zhì)上是等同的。但這些關(guān)聯(lián)關(guān)系存在層次性：空間關(guān)系和時態(tài)關(guān)系為關(guān)聯(lián)規(guī)則同一最高級別；根據(jù)空間距離由遠(yuǎn)及近等，距離級別大于拓?fù)?；而距離和方位層次等同。在求解“顯著”性，父層級的關(guān)系級數(shù)為子層級之和。在挖掘算法中，將“關(guān)系”表征為“交易”，用每種“關(guān)系”所出現(xiàn)的次數(shù)表征著該“關(guān)系”的“頻繁”。此時，該“頻繁”可能呈現(xiàn)“顯著差異性”，而高“頻繁”表示該“關(guān)系”顯著。這種“顯著”特性對關(guān)聯(lián)模式的挖掘非常重要，影響著拓?fù)洹⒎较?、距離等關(guān)系的取舍。某類空間關(guān)系“頻繁”跟時態(tài)關(guān)系“頻繁”相組合，容易形成某類時空關(guān)聯(lián)模式。如方位且距離關(guān)系“顯著”(即均衡的位置布局和要素間鄰近)和時態(tài)“顯著”(即關(guān)系在某時間段的大量涌現(xiàn)，這種現(xiàn)象稱之為“時態(tài)聚集”)易形成“星型”模式?？臻g拓?fù)涞泥徑P(guān)系(此時表現(xiàn)為高“頻繁”)在時間上的先后出現(xiàn)(又表現(xiàn)著高“頻繁”)易形成“序列”模式。某兩類型地理要素的關(guān)聯(lián)規(guī)則“顯著”求解步驟：

表1 兩要素X→Y“關(guān)系”關(guān)聯(lián)規(guī)則的“支持度”和“置信度”求解過程Table 1 Calculations of support and confidence degree for FAR of ‘X→Y ’

(3) ifri?rt, “顯著”, thenRL(ri⊕rt)=“顯著”；otherwise“不清楚”。

2 “星型”和“序列型”關(guān)聯(lián)模式搭建

“多元”關(guān)聯(lián)模式挖掘，關(guān)聯(lián)模式的搭建是關(guān)鍵。本文只討論2種常見的關(guān)聯(lián)模式，分別為“星型”和“序列型”，圖1(c)和(d)所示分別為這2種模式在“空間對象關(guān)聯(lián)”和“地理要素‘多元’關(guān)聯(lián)”所不同的表達(dá)方式。在“多元”關(guān)聯(lián)模式中，要素間的關(guān)系可以表征成有向圖(即圖論)：節(jié)點(Node)對應(yīng)于要素類型fi∈F；邊(Edge)表示節(jié)點(要素間)的關(guān)聯(lián)性；邊(Edge)的粗細(xì)表示節(jié)點(要素間)的關(guān)聯(lián)熱度強弱；箭頭(Arrow)可表征要素間的時態(tài)關(guān)系，如fi→fj表示fi先于fj；虛線方格(Grid)用于確定要素的空間方位(如東、西、左、右等)。額外，圖1(c)所示節(jié)點(Node)的多層包圍圈，表示不同時間段的要素狀態(tài)(如形狀、大小等)，用顏色填充來標(biāo)注要素不同的產(chǎn)生時間等。

2.1 星型(Star-like MVAP)

此類模式為要素關(guān)聯(lián)規(guī)則模式的一個特例，也是現(xiàn)實中較常見的一種現(xiàn)象：要求有1個“核心”要素，與其他要素間至少存在某種關(guān)聯(lián)關(guān)系，其他的要素間不一定要求關(guān)聯(lián)。在此，其他要素可稱之為“配套要素”?！靶切汀蹦Ｊ娇擅枋鰹镻＜fc:{f1, …,fk}＞，且時間順序有fc＜fl，fc＜f2，…，fc＜fk或fc＞fl，fc＞f2，…，fc＞fk。“星型”模式具體詳細(xì)說明如圖2所示。

(1)a,b,c,g為時空要素的實例，則該“星型”模式的實例可表示為：＜g:{a,b,c}＞；左圖要素顏色填充不同，表示要素出現(xiàn)的時間先后順序不同。

(2) 按要素出現(xiàn)的先后順序有2種形式：一是“核心”要素出現(xiàn)后，導(dǎo)致其他要素出現(xiàn)，即時間約束為(g.ts＜a.ts)∧(g.ts＜b.ts)∧(g.ts＜c.ts)；二是相關(guān)要素相繼出現(xiàn)后，“核心”要素才出現(xiàn)，即時間約束為(g.ts＞a.ts)∧(g.ts＞b.ts)∧(g.ts＞c.ts)。

(3) “核心”要素和“配套要素”存在一定的空間關(guān)系(如距離和拓?fù)涞?。

圖2 “星型”模式實例Fig.2 An example of ‘start-like’ pattern

2.2 序列型(Sequence MVAP)

此類模式為時空序列模式(Flow patterns)的典型實例，要素個數(shù)為k的序列模式可表達(dá)為P=要求要素兩兩間至少存在時間和空間相鄰的 2種關(guān)聯(lián)關(guān)系?！靶蛄小蹦Ｊ娇擅枋鰹镻＜f1,f2,…,fk＞?！靶蛄行汀蹦Ｊ骄唧w說明如圖3所示(其中，fj為線要素(如公路))。

(1)a,b,c,d為時空要素的實例，該“序列”模式的實例可表示為：＜a,b,c,d＞；要素顏色填充不同，表示要素出現(xiàn)先后順序不同。

(2) 空間距離要求“鄰近”，拓?fù)潢P(guān)系要求“相離”：CloseTo(fi,,fi+1)∧Disjoint(fi,,fi+1)。

(3) 時態(tài)要求相近，保持時間前后關(guān)系，如,fi+1在fi后出現(xiàn)：after(fi,,fi+1)。

圖3 “序列”模式實例Fig.3 An example of ‘sequence-like’ pattern

3 挖掘算法

對“星型”和“序列型”的關(guān)聯(lián)模式進(jìn)行時空數(shù)據(jù)挖掘算法探討。在現(xiàn)有空間關(guān)聯(lián)挖掘Apriori算法的基礎(chǔ)上，由單獨的同類雙要素挖掘擴展至多類型下的多個要素的多規(guī)則組合式的模式挖掘。為了方便快速搭建“多元”組合關(guān)聯(lián)模式，引入“等價類”[26]。

3.1 “等價類”概念

定義4 等價類[10,18](Equivalence classes)。

設(shè)fi和fj為2個集合，且pk=(fi,fj)為頻繁k-MVAP，若fi為(k-1)-MVAPs模式，則稱pk為k階等價類，記為Ek(fi, fj)。其中：Ek為k-等價類集；Ekfi和Ekfj分別為Ek的前綴和后綴要素，且Ek(fi,*)為前綴相同的k-等價類集,Ek(*,fj)為后綴相同的k-等價類集。若Ek的前綴fi或后綴fj要素一致的等價類有m個，則所對應(yīng)的m個k-MVAPs模式可合并成(k+m-1)-MVAPs模式。

等價類的引入一方面可利用來自同一等價類中的要素項集，快速搭建“多元”時空關(guān)聯(lián)模式，另一方面可降低頻集和規(guī)則的冗余度，大大提高挖掘的質(zhì)量。k階等價類規(guī)定須滿足2個特性：(1) 其為k階時空關(guān)聯(lián)模式，記為k-MVAPs；(2) 其前k-1要素集必為k-1階時空關(guān)聯(lián)模式，記為(k-1)-MVAPs。

3.2 挖掘算法實現(xiàn)

(1) 掃描時空數(shù)據(jù)庫 1次，計算各種專題要素個數(shù)N(Fi)，可能時空數(shù)據(jù)量∑N(Fi)非常大，可根據(jù)自身感興趣的要素或要素級別，即設(shè)置要素權(quán)重w(Fi)；先檢索，后掃描，去除不重要或意義不大的要素，生成一新的表。若w(Fi)×N(Fi)/∑N(Fi)≥wminSup(權(quán)重支持度)，則p1i(Fi)為1-MVAP頻繁模式，P1={p11,p12, …,p1i}為一階頻繁集。

(2) 依照時空謂詞算子和時空關(guān)系層次化的搜索原則，先時態(tài)算子(operator1)、方位算子(operator2)、距離算子(operator3)和拓?fù)渌阕?operator4)，對一階頻繁集(P1)進(jìn)行掃描，并記錄該算子下的關(guān)系次數(shù)；若兩要素p2i(fi,fj)滿足以下情況：(1) 在時間上滿足|fit-fjt|≤t，空間距離滿足distance(fj-fi)≤d，且 N(p1i)/ ∑N(p1i)≥minSup，則p2i(fi,fj)為2-MVAPs“準(zhǔn)星型”頻繁模式，P2={p21,p22, …,p2i}為“準(zhǔn)星型”二階頻繁集；(2) 在時間上滿足fjt-fit≤t(i＜j且t＞0)，空間距離滿足distance(fj-fi)≤d，且N(p1i)/∑N(p1i)≥minSup，則p2i(fi,fj)為2-MVAPs“準(zhǔn)序列”頻繁模式，P2={p21,p22,…,p2i}為“準(zhǔn)序列”二階頻繁集。

(3) 在二階頻繁集(P2)的基礎(chǔ)上，構(gòu)建2-等價類，即兩要素p2i(fi,fj)為頻繁2-MVAPs模式，且fi,fi∈P1，則p2i(fi,fj)也為 2-等價類，記為E2(fi,fj)。其中：E2為2-等價類集，E2.fi,E2.fj分別為E2的前綴和后綴要素，又且E2(fi,*)為前綴相同的為2-等價類集，E2(*,fj)為后綴相同的為2-等價類集。例如：p21=(f1,f2)(其中，f1為1-MVAP頻繁模式)，則p21為2-等價類，記為E2(f1,f2)，即E2(f1,*)為前綴相同的為2-等價類集。

(4) 在2-等價類集(E2)中，搜索相關(guān)等價類，分別搭建所需要的多元關(guān)聯(lián)模式，若E2的前綴fi或后綴fj要素一致的等價類有m個，則所對應(yīng)的m個2-MVAP模式可合并構(gòu)建成(m+1)-MVAP“星型”模式；若E2的后綴fj要素和前綴fi相同，且有m個這樣的等價類，則所對應(yīng)的m個 2-MVAP模式可合并構(gòu)建成(m+1)-MVAP“序列型”模式。又如：

對于“星型”關(guān)聯(lián)模，

對于“序列”關(guān)聯(lián)模，

具體算法實現(xiàn)如下：

//Algorithm算法: MVAPs-Mining

//目的: 從時空數(shù)據(jù)源中，挖掘出類似“星型”和“序列”的時空關(guān)聯(lián)模式

Input: Spatiotemporal DatabaseD;

Spatial Distance thresholdR;

Time spanning thresholdW;

Minimum Support minSup;

Output: A set of frequent “Start-like” St;

A set of frequent “Sequence” Se;

1.Scan databaseDand classified into n thematic layers,formedFi (if necessary);

2.P1←Gen1-MVAPs(minSup); //Generalize 1-MVAPs;

3.Θ(fi∈D)∩(P1≠Φ)

4. FOR Each featurefi∈P1ANDi＜∑N(Fi)DO

5.i+=1; // GenRelation-ST(fi,fi+1,R,W,Type): The Solving process of Spatiotemporal relationships

6.St_P2i←GenRelation-ST(fi,fi+1,R,W,St); //Generalize Candidate with “Star-like” pattern;

7.Se_P2i←GenRelation-ST(fi,fi+1,R,W,Se); //Generalize Candidate 2-MVAPs with “Sequence” pattern;

8.St_P2←St_P2i;Se_P2←Se_P2i;P2←{St_P2,Se_P2}; //2-MVAPs

9.END FOR

10.FOR Each relationshipsRj∈P2ANDj＜iDO

11. IF(Rj.fleft∈P1)and (Rj.fright∈P1)THEN //construct the Equivalence classes

12.k+=1;E2(k)={Rj.fleft,Rj.fright};E2←E2(k); //E2sets

13. END IF

14.END FOR

15. FOR Each classE2(m)∈E2ANDm＜kDO //fix up those“star-like” and “sequence” patterns

16.n=p=q=0; St_temp(0)= Se_temp(0)=E2(m);

17. FORn＜k-mDO

17.n+=1;

18. IF (E2(m).fleft)=(E2(m+n).fleft) THEN //the “star- like”pattern

19. St_temp (p+1)←{E2(m+n).fright};END IF

20. IF (E2(m).fright)=(E2(m+n).fleft) THEN //the “sequence”pattern

21.Se_temp(q)=E2(m); Se_temp(q+1)←{Se_temp(q)}∪{E2(m+n).fright}; END IF

22. END FOR

23.St←St_temp(p);Se←Se_temp(q);

24. END FOR

4 合成實例求證-城市規(guī)劃

城市化是構(gòu)建在社會經(jīng)濟發(fā)展過程中的時空演變過程。城市化空間格局與城市化空間過程是揭示城市化進(jìn)程的2個重要方面[13]。而對城市空間規(guī)劃諸方法的研究中，尤其是發(fā)現(xiàn)城市各空間要素間的秩序與邏輯的方法和技術(shù)，歷來都是城市規(guī)劃研究的熱點和前沿性課題。而對時空關(guān)聯(lián)模式的研究有助于釋義城市空間的位置和結(jié)構(gòu)布局模式以及揭示城市化過程的演變，進(jìn)而深入解析城市各地理要素的空間效用和功能[27]。城市化進(jìn)程中的要素符合“有限的離散的地理要素集”特性，特用合成實例(城市規(guī)劃)詮釋“多元”關(guān)聯(lián)模式的時空數(shù)據(jù)挖掘過程，驗證模式及其挖掘算法的可用性。在此，更重視模式從規(guī)劃時空數(shù)據(jù)集的構(gòu)建到模式挖掘的整個過程，而忽略挖掘算法的效率等問題。

4.1 規(guī)劃要素集

現(xiàn)實的地理規(guī)劃要素需在計算機中得以表達(dá)，才能實現(xiàn)數(shù)據(jù)的存儲，故首先需要構(gòu)建數(shù)據(jù)集。規(guī)劃要素具有時間和空間屬性，以(空間)數(shù)據(jù)庫方式存儲，進(jìn)而形成所謂的時空地理要素集即規(guī)劃要素時空數(shù)據(jù)集，用符號D表示，時空數(shù)據(jù)集具有時空特性。設(shè)時空數(shù)據(jù)集D共有n個地理要素fi，各自分布在r個數(shù)據(jù)集中。若數(shù)據(jù)集對應(yīng)于時間快照(Snapshot)圖，則快照圖可表示成:W={W1,W2,…,Wr}。其中：Wi是按時間排序：W1＜W2＜…＜Wr；若數(shù)據(jù)集對應(yīng)于專題(Thematic maps)圖，則專題圖可表示成：M={m1,m2,…,mr}(其中，mi可按數(shù)據(jù)類型劃分：m1|m2|…|mm，可做多維度時空關(guān)聯(lián)挖掘)；如兩者都存在，則考慮先按要素類型分類，再按時間排序。假設(shè)n個要素存在q種 MVAPs，則模式集對應(yīng)于P={p1,p2,…,pq}。時空數(shù)據(jù)集的記錄和存儲方式，如圖4和表2所示。

圖4 時空數(shù)據(jù)實例的視圖表示Fig.4 View of spatiotemporal database example

表2 時空數(shù)據(jù)的記錄和存儲機制Table 2 Records and storage of spatiotemporal data

4.2 規(guī)劃要素關(guān)聯(lián)模式挖掘過程

在規(guī)劃進(jìn)程中，規(guī)劃要素權(quán)重的確定與要素的作用空間范圍和時間效應(yīng)有關(guān)。時空關(guān)聯(lián)模式的挖掘過程(包括數(shù)據(jù)流程和算法)如表 3～5所示。其數(shù)據(jù)流程說明如下：

(1) 首先根據(jù)要素專題特性，對規(guī)劃要素進(jìn)行分類，內(nèi)部按時間排序，見表3。

(2) 根據(jù)挖掘任務(wù)，檢索出自身感興趣的要素層，并計算N(Fi)/∑N(Fi)≥wminSup，見表 4。

表3 要素分類Table 3 Classification of features

表4 檢索出的感興趣的要素層Table 4 Interested feature layer

表5 時空要素關(guān)聯(lián)索引矩陣Table 5 Indexed matrix of S-T association features

(3) 構(gòu)建時空要素關(guān)聯(lián)索引矩陣，見表5，其中，可以引入“要素權(quán)重”。

(4) 構(gòu)建等價類，依需要搭建多元關(guān)聯(lián)模式?？赏茖?dǎo)出：

對“星型”，

對“序列型”，

4.3 結(jié)果與討論

在飽嘗了城市惡性膨脹所帶來的交通、能源和環(huán)境危機惡果之后，許多城市開始檢討其城市發(fā)展方向。Calthorp倡導(dǎo)的公交導(dǎo)向發(fā)展(TOD)策略逐漸被認(rèn)同，是新都市主義在城市規(guī)劃方面的實踐模式之一[28]。這一模式主張城市規(guī)劃應(yīng)布置緊湊，以公共交通作為城市運行的支持系統(tǒng)，以公共交通(軌道交通、公交系統(tǒng))節(jié)點作為城市規(guī)劃發(fā)展的基礎(chǔ)，圍繞著公共交通站點布置城市服務(wù)設(shè)施(居住、商業(yè)、就業(yè)、教育等)。TOD模式在圖4所示的時空視圖中得到很好的詮釋。

地鐵和城市環(huán)路是城市化擴展非常重要的引擎。地鐵和環(huán)路的交叉區(qū)域往往易形成非常重要的公共交通站點，進(jìn)而引發(fā)大量的基礎(chǔ)設(shè)施新建。樣例中挖掘出f3:{f5;f6}和f3:{f8;f9;f10}等“星型”模式。忽略規(guī)劃要素對經(jīng)濟GDP的影響，從TOD模式結(jié)合“星型”和“序列型”模式可以進(jìn)一步探討：(1) 城市進(jìn)程的引擎動力于城市郊區(qū)的“規(guī)劃城市環(huán)線”是否高于“地鐵延伸至郊區(qū)”；(2) 規(guī)劃城市環(huán)線某段的發(fā)展?fàn)顩r描述?？梢杂盟诰颉靶切汀蹦Ｊ降臄?shù)量、熱度和強度等來說明以上2點。

5 結(jié)論

(1) 在關(guān)聯(lián)規(guī)則方面，提出了“要素關(guān)聯(lián)規(guī)則”的新定義：一是空間對象擴展至地理要素；二是空間關(guān)系集合了距離、方位和拓?fù)涞?，以及時態(tài)關(guān)系。由“要素關(guān)聯(lián)規(guī)則”新定義，提出了“多元”關(guān)聯(lián)模式，即不同類型要素參與下的多關(guān)聯(lián)規(guī)則的組合。在關(guān)聯(lián)模式方面，圖論表述了“星型”和“序列型”“多元”關(guān)聯(lián)模式。最后，在挖掘算法上，引入了“等價類”，快速搭建“多元”關(guān)聯(lián)模式。

(2) 本文只涉及 2種類型的關(guān)聯(lián)模式，其發(fā)現(xiàn)的過程稱為“顯式”探索，即模式預(yù)先定義，在大量的關(guān)系實體中進(jìn)行比配。另外，實例只用于說明挖掘的流程，并未在實際案例中得以實踐。

(3) 下一步工作是進(jìn)一步完善關(guān)聯(lián)模式的類型和探討有關(guān)“隱式”關(guān)聯(lián)模式挖掘方法，并給予實證。當(dāng)然，整合“地理經(jīng)濟要素(如GDP)與地理基礎(chǔ)要素的約束關(guān)系”等關(guān)聯(lián)規(guī)則，構(gòu)建更復(fù)雜的“面向文本表達(dá)的地理知識”關(guān)聯(lián)模式也有待于進(jìn)一步研究。

[1] 杜寧睿, 李淵. 規(guī)劃支持系統(tǒng)(PSS)及其在城市空間規(guī)劃決策中的應(yīng)用[J]. 武漢大學(xué)學(xué)報: 工學(xué)版, 2005, 38(1): 137-142.DU Ning-rui, LI Yuan. Planning support system (PSS) and its application to decision-making for urban spatial development[J].Engineering Journal of Wuhan University, 2005, 38(1): 137-142.

[2] Pandey G, Atluri G, Steinbach M, et al. An association analysis approach to biclustering[C]//KDD’09. Paris, France, 2009：677-686.

[3] Saha S, Bridges S, Magbanua Z, et al. Discovering relationships among dispersed repeats using spatial association rule mining[J].BMC Bioinformatics, 2008, 9(Suppl 10): 1-4.

[4] Lee I, Phillips P. Urban crime analysis through areal categorized multivariate associations mining[J]. Applied Artificial Intelligence, 2008, 22(5): 483-499.

[5] 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.

[6] Chang C, Shyue S. Association rules mining with GIS: An application to Taiwan census 2000[C]//Fuzzy Systems and Knowledge discovery, FSKD’09. Tianjin, China, 2009: 65-69.

[7] Koperski K, Han J. Discovery of spatial association rules in geographic information databases[C]//Proceedings of the 4th International Symposium on Large Spatial Databases. Portland,ME: Berlin: Springer, 1995: 47-66.

[8] Zeitouni K, Yeh L, Aufaure M. Join indices as a tool for spatial data mining[C]//International Workshop on Temporal, Spatial and Spatiotemporal Data Mining. Berlin: Springer, 2000:102-114.

[9] 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: 5-17.

[10] Yang H, Parthasarathy S. Mining spatial and spatio-temporal patterns in scientific data[C]//22nd International Conference on Data Engineering Workshops (ICDEW'06). IEEE Computer Society, 2006: x146.

[11] 曾玲, 熊才權(quán), 胡恬. 關(guān)聯(lián)規(guī)則在空間數(shù)據(jù)挖掘中的研究[J].計算機與數(shù)字工程, 2005, 33(6): 71-73.ZENG Ling, XIONG Cai-Quan, HU Tian. Research on association rules of spatial data ming[J]. Computer and Digital Engineering, 2005, 33(6): 71-73.

[12] 呂峰, 易曉峰. 用模糊遺傳算法挖掘空間關(guān)聯(lián)規(guī)則[J]. 武漢理工大學(xué)學(xué)報, 2006, 28(1): 96-104.Lü Feng, YI Xiao-feng. Ming spatial association rule by fuzzy genetic algorithm[J]. Journal of Wuhan University of Technology,2006, 28(1): 96-104.

[13] 馬榮華, 蒲英霞, 馬曉冬, 等. GIS空間關(guān)聯(lián)模式發(fā)現(xiàn)[M]. 北京: 科學(xué)出版社, 2007: 251-360.MA Rong-hua, PU Ying-xia, MA Xiao-dong. Mining spatial association patterns from GIS database[M]. Beijing: Science Press, 2007: 251-360.

[14] 張雪伍. 時空過程及其關(guān)聯(lián)規(guī)則挖掘[D]. 上海: 同濟大學(xué)測量與國土信息工程系, 2009: 128-134.ZHANG Xue-wu. Spatiotemporal process and its association rule mining[D]. Shanghai: Tongji University. Department of Surveying and Geo-informatics, 2009: 128-134.

[15] Sheng C, Hsu W, Lee M, et al. Discovering spatial interaction patterns[M]. Berlin: Springer, 2008: 95-109.

[16] Lee I. Mining multivariate associations within GIS environments[J]. Innovations in Applied Artificial Intelligence,2004: 1062-1071.

[17] Ding W, Eick C, Wang J, et al. A framework for regional association rule mining in spatial datasets[C]//Proceedings of the Sixth IEEE International Conference on Data Mining(ICDM’06). Hong Kong, 2006: 851-856.

[18] Yang H, Parthasarathy S, Mehta S. Mining spatial objectassociations for scientific data[C]//Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI).Edinburgh, UK. 2005: 902-907.

[19] Lee A, Chen Y, Ip W. Mining frequent trajectory patterns in spatial-temporal databases[J]. Information Sciences, 2009,179(13): 2218-2231.

[20] Huang Y, Xiong H, Shekhar S, et al. Mining confident co-location rules without a support threshold[C]//Proceedings of the 18th ACM Symposium on Applied Computing (ACM SAC).Melbourne, FL. 2003: 497-501.

[21] Agrawal R, Imielinski T, Swami A. Mining association rules between sets of items in large databases[J]. ACM SIGMOD Record, 1993, 22(2): 207-216.

[22] Han J, Pei J, Y Y. Mining frequent patterns without candidate generation[C]//Proceedings of the ACM SIGMOD International Conference on Management of Data. Dallas, USA. 2000: 1-12.

[23] Lee H, Han J, Miller H, et al. Temporal and spatiotemporal data mining[M]. NewYork: IGI Publishing, 2007: 127-143.

[24] Tanbeer S, Ahmed C, Jeong B, et al. Efficient single-pass frequent pattern mining using a prefix-tree[J]. Information Sciences, 2009, 179(5): 559-583.

[25] Lee A J T, Liu Y H, Tsai H M, et al. Mining frequent patterns in image databases with 9D-SPA representation[J]. The Journal of Systems and Software, 2008, 82: 603-618.

[26] Zaki M J. New algorithms for fast discovery of association rules[R]. New York: Rensselaer Polytechnic Institute, 1997:10-24.

[27] 王靜文. 空間句法理論的三維擴展及其應(yīng)用研究[D]. 武漢:武漢大學(xué)測繪遙感信息工程國家重點實驗室, 2006: 36-45.WANG Jing-wen. Syntax paraphrase for social dimension[D].Wuhan: Wuhan University. State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, 2006:36-45.

[28] 焦點房地產(chǎn)網(wǎng). 探索萬年花城 TOD社區(qū)模式[EB/OL].[2008-06-16]. http://house.focus.cn.Focus on estate. Exploratory TOD community patterns[EB/OL].[2008-06-16]. http://house.focus.cn.