曾 新，李曉偉，楊 健

（大理大學數(shù)學與計算機學院，云南大理 671003）

隨著移動技術(shù)的快速發(fā)展和廣泛普及，人們可以利用先進的空間數(shù)據(jù)收集系統(tǒng)，例如地理信息系統(tǒng)（GIS）、全球位置系統(tǒng)（GPS）等，以至于積累了大量的空間數(shù)據(jù)集。

面對具有海量性、高維性、非線性、多尺度和模糊性等特點的空間數(shù)據(jù)集，如何從空間數(shù)據(jù)庫當中挖掘出潛在的、人們感興趣的知識或其他沒有顯示在存儲空間數(shù)據(jù)庫中的模式，從而指導科學決策，顯得尤為重要，目前空間數(shù)據(jù)挖掘已經(jīng)成為熱點研究內(nèi)容之一。

空間co-location模式表示空間對象的一個子集，其對象實例經(jīng)常被發(fā)現(xiàn)同時出現(xiàn)在同一鄰近區(qū)域內(nèi)，如交通堵塞常常伴有交警、車禍和救護車的出現(xiàn)；在生態(tài)學中，尼羅鱷出現(xiàn)的地方也會頻繁出現(xiàn)埃及鸻〔1〕。

1 相關(guān)工作

自從Agrawal等人研究出Apriori算法以來，colocation模式挖掘成為數(shù)據(jù)挖掘的研究熱點之一，基于確定數(shù)據(jù)集、不確定數(shù)據(jù)集和空間數(shù)據(jù)集的研究成果不斷涌現(xiàn)。Join-based算法首次在文獻〔1〕中被提出，將頻繁模式通過全連接的方式產(chǎn)生候選模式，然后計算所有候選模式的表實例，最后確定其頻繁度；針對模式連接操作產(chǎn)生的時間開銷問題，文獻〔2〕和文獻〔3〕分別提出部分連接算法和無連接算法，部分連接算法首先事務(wù)化連續(xù)的空間數(shù)據(jù)，并將在事務(wù)中未識別的剩余實例采用實例連接的方法，而無連接算法通過星型鄰近方式對數(shù)據(jù)集進行劃分，然后采用行實例查找方式來代替時間開銷巨大的行實例連接操作；對于不確定數(shù)據(jù)集，模糊參與率、模糊參與度和模糊對象的co-location模式挖掘算法（FB）在文獻〔4〕中被提出；文獻〔5〕針對空間對象實例存在約束條件問題，提出帶有時間約束的co-location模式挖掘；文獻〔6〕針對模式當中存在稀有特征，導致有些模式無法獲取的情況，提出一種帶稀有特征的空間co-location模式挖掘新方法。

除此之外，文獻〔7〕將效用概念引入到空間colocation模式挖掘中，定義了模式效用、模式效用率、擴展模式效用等概念，并提出完全剪枝算法；文獻〔8〕針對高平均效用項集挖掘算法需要耗費大量的時間問題，提出將效用信息保存到效用列表當中，并給出高平均效用項集挖掘的改進算法FHAUI；文獻〔9〕充分考慮同一特征不同實例間的差異，提出帶效用值的空間實例，定義了新的效用參與度UPI作為高效用co-location模式的有趣度量指標，并將領(lǐng)域知識應(yīng)用到挖掘過程當中；文獻〔10〕提出一個高效用項集的增量挖掘算法；目前為止，空間co-location模式挖掘都只關(guān)注某一個時刻的空間co-location模式，然而，在實際應(yīng)用中，數(shù)據(jù)庫中的數(shù)據(jù)是隨著時間變化的，文獻〔11〕提出高效的空間co-location模式增量挖掘算法；針對發(fā)展的空間數(shù)據(jù)庫當中新的數(shù)據(jù)和鄰近關(guān)系，文獻〔12〕提出在發(fā)展的空間數(shù)據(jù)庫當中有效的更新高效用co-location模式。

2 相關(guān)定義及性質(zhì)

圖1中，有A,B,C3個不同空間對象，分別表示不同種類的事務(wù)，例如：醫(yī)院、商店、餐館，而每個對象出現(xiàn)在不同的位置表示對象實例，對象A,B,C分別有4、2和3個對象實例。

圖1 空間對象及其實例

空間鄰近關(guān)系R用來表示空間對象實例之間的空間關(guān)系，一般采用歐幾里得距離來表示：

d是預先設(shè)定的距離閾值，例如圖1中A.1和B.1是鄰近的，用實線連接。

假設(shè)實例集為I={i1,i2,…,in}，如果I中的任何兩個實例間都滿足{R(ix,iy)|1≤x≤n,1≤y≤n}則稱I為團，例如在圖1中{A.1,B.1,C.1}就是一個團。

空間co-location模式表示空間對象的一個子集，用c表示，例如在圖1中c={A,B,C}就是一個空間co-location模式。模式c的行實例是一個團，它包含模式c的全部對象，而其任何子集不包含模式c的全部對象。例如在圖1中{A.4,B.2,C.2}就是模式c的一個行實例。而模式c的所有行實例組成的集合稱為c的表實例，用table_instance(c)來表示。例如在圖1中模式c的表實例為：

{{A.1,B.1,C.1},{A.4,B.2,C.2}}。

假設(shè)fi為空間的某個對象，fi在模式c={f1,f2,…,fk}中的參與率表示為：

其中π是關(guān)系的投影操作，例如在圖1中模式c的表實例為{{A.1,B.1,C.1},{A.4,B.2,C.2} }，而對象A,B,C的實例個數(shù)分別為4、2和3，模式c中對象參與率為：

模式c的參與度是其所有空間對象參與率的最小值，記為則模式c的參與度為：PI(c)=min(0.5,1,0.67)=0.5。如果模式c的參與度PI(c)大于或等于用戶預先設(shè)定的最小參與度閾值min_prev，則c是頻繁模式，否則c是非頻繁模式。例如用戶預先設(shè)定min_prev=0.5，而PI(c)=0.5≥min_prev，因此模式c是頻繁模式。

定理1參與度和參與率隨著co-location模式c的階的增大而單調(diào)遞減。

證明：假設(shè)模式c的行實例中包含某一空間對象fi的實例，如果模式c′是c的子集，那么fi的實例也一定被包含在c′的行實例中，反之則不然，因此空間對象的參與率隨著模式階的增長而遞減。

假設(shè)c={ }f1,f2,…,fk，

所以模式c的參與度也是單調(diào)遞減的。

3 算法

3.1 問題描述假設(shè)最小參與度閾值min_prev=0.5，圖1中模式{A,B}的表實例為{{A.1,B.1},{A.4,B.2}}，{A,C}的表實例為{{A.1,C.1},{A.3,C.3},{A.4,C.2} }，根據(jù)參與率和參與度的計算公式有：

模式{A,B}為頻繁模式；

模式{A,C}為頻繁模式。同理可知，模式{B,C}也是頻繁的。

假定候選模式c={f1,f2,…,fk}，根據(jù)co-location模式的反單調(diào)性，候選模式c的k-1階模式都是頻繁的，我們稱c′={f1,f2,…,fk-1}為模式c的前綴模式，而其他的k-1階模式均不為前綴模式。例如候選模式{A,B,C}的前綴模式為{A,B}，其他二階模式不作為其前綴模式。

將頻繁模式{A,B}和{A,C}進行連接得到候選模式{A,B,C}，然后，我們通過前綴模式{A,B}的表實例來計算候選模式{A,B,C}的表實例。如果{A,B}的一個行實例{A.i,B.j}中的每個實例都與對象C的一個實例C.m是空間鄰近的，那么{A.i,B.j,C.m}為候選模式{A,B,C}的一個行實例，所有行實例的集合為表實例。

例如前綴模式{A,B}的表實例{{A.1,B.1},{A.4,B.2} }，行實例{A.1,B.1}中的每個實例都與對象C的實例C.1空間鄰近，所以{A.1,B.1,C.1}為候選模式{A,B,C}的一個行實例，而{A.4,B.2}中每個實例都與C.2空間鄰近，{A.4,B.2,C.2}為{A,B,C} 的行實例，最終得出{A,B,C}的表實例為{{A.1,B.1,C.1},{A.4,B.2,C.2}}。

3.2 基本算法在候選模式表實例的計算中，joinbased-D方法與join-based-Z方法的主要區(qū)別在于前者將候選模式的前綴模式表實例存儲于數(shù)據(jù)庫中，后者將其存放于字典中，但是二者都是基于joinbased算法進行算法設(shè)計，具體的算法描述如下：

輸入

空間實例集S；

空間鄰近距離閾值dis_thre；

最小參與度閾值min_prev;

中間變量

模式的階k；

k階co-location模式候選集Ck；

Ck中表實例的集合Tabk；

k階頻繁模式集合Pk；

空間鄰近關(guān)系集neiR

輸出

頻繁模式集P

過程：

（1）頻繁1項集P1為所有對象；

（2）P=?；

（3）由實例的坐標和距離閾值dis_thre，產(chǎn)生不同對象實例間的空間鄰近關(guān)系集neiR；

（4）for( )k=2;Pk-1≠?;k++

a.將Pk-1連接產(chǎn)生k階候選模式集Ck；

b.根據(jù)Ck、neiR和前綴模式表實例生成候選模式的表實例集Tabk，若通過掃描數(shù)據(jù)庫獲取前綴模式作為join-based-D方法，而從字典中獲取前綴模式作為join-based-Z方法；

c.根據(jù)Tabk計算每個候選模式的參與度；

d.候選模式的參與度大于或等于min_prev，則為頻繁模式pk，否則丟棄；

e.P=P?Pk；

f.返回頻繁模式集P。

4 實驗分析

為了評估join-based-D方法和join-based-Z方法在不同的實例集、不同的距離閾值和不同的參與度閾值下的運行效率，本文進行了大量實驗，并以對比圖的方式呈現(xiàn)實驗結(jié)果。實驗基于的硬件平臺為Intel core i3處理器、4 GB內(nèi)存、64位Win?dows 7操作系統(tǒng)；軟件編程環(huán)境為Python 2.7版本。

4.1 不同實例集下join-based-D與join-based-Z的效率數(shù)據(jù)集共有10個對象，每個對象的實例個數(shù)都是隨機生成的，其中鄰近距離閾值dis_thre＝5，最小參與度閾值min_prev=0.5，分別在實例個數(shù)為152、390、623、940和1 306下比較join-based-D方法和join-based-Z方法的運行效率，見圖2。

圖2 不同實例集下運行效率

從圖2中可以看出，在其他條件一定的情況下，隨著實例數(shù)目的增大，join-based-Z方法的運行效率要遠高于join-based-D方法，但是join-based-Z方法中采用字典存儲前綴模式，字典的大小受到內(nèi)存大小的限制，實例個數(shù)達到一定數(shù)目時，joinbased-Z方法將無法計算模式的表實例，所以小數(shù)據(jù)集下采用join-based-Z方法，運行效率高。

4.2 不同距離閾值下join-based-D與join-based-Z的效率數(shù)據(jù)集共有10個對象，每個對象的實例個數(shù)都是隨機產(chǎn)生的，在實例數(shù)目為623、最小參與度閾值min_prev=0.5的情況下，分別對距離閾值為1、2、3、4和5進行實驗，比較join-based-D方法與join-based-Z方法的運行效率，見圖3。

圖3 不同鄰近距離閾值下運行效率

同一實例集下，隨著鄰近距離閾值的增大，鄰近關(guān)系集會隨之擴大，候選模式的行實例數(shù)目可能會增大，導致表實例的計算開銷增加。join-based-D方法多次掃描數(shù)據(jù)庫帶來極大的時間開銷，而joinbased-Z方法運行效率高。

4.3 join-based-D與join-based-Z在不同參與度閾值下的效率在10個空間對象下，共隨機生成623個實例，最小距離閾值dis_thre＝3，分別在參與度閾值為0.5、0.6、0.7、0.8和0.9下進行實驗，比較joinbased-D方法和join-based-Z方法在不同參與度閾值下的運行效率，見圖4。

圖4 不同參與度閾值下運行效率

由于join-based算法的主要時間開銷為連接操作和表實例的計算，而參與度閾值用來衡量模式是否頻繁的標準。隨著參與度閾值的增大，頻繁模式的數(shù)目會相應(yīng)減少，導致連接操作和表實例的計算開銷適當減少。但是，join-based-Z方法的運行效率仍然高于join-based-D方法。

5 結(jié)束語

空間co-location模式挖掘中，模式表實例的計算尤為重要，join-based-D和join-based-Z方法能夠?qū)崿F(xiàn)對候選模式表實例的計算。但是，在內(nèi)存大小允許的情況下，join-based-Z方法的執(zhí)行效率要遠高于join-based-D方法。由于join-based-Z方法受到內(nèi)存大小的限制，所以，未來我們將主要研究join-based-Z方法的優(yōu)化策略。

〔1〕 HUANG Y，SHEKHAR S，XIONG H.Discovering colocation patterns From spatial data sets：a general ap?proach〔J〕.IEEE Transactions on Knowledge and Data Engineering， 2004，16（12）：1472-1485.

〔2〕 YOO J S，SHEKHAR S.A partial Join Approach for Mining Co-location Patterns〔C〕∕∕Proc.of the 12th An?nualACM Int.Workshop on Geographic Information Systems.Washington DC.USA，2004：241-249.

〔3〕YOO J S，SHEKHAR S，CELIK M.A join-less ap?proach for co-location pattern mining：A summary of results〔C〕∕∕In： Proc.of the 5th IEEE Int.Conf.on Data Mining.Washington：IEEE ComputerSociety，2005：813-816.

〔4〕歐陽志平，王麗珍，陳紅梅.模糊對象的空間co-location模式挖掘研究〔J〕.計算機學報，2011，34（10）：1947-1955.

〔5〕 ZENG X，YANG J.Co-location patterns mining with time constraint〔J〕.Computer Science，2016，2（43）：293-296.

〔6〕馮嶺，王麗珍，高世健.一種帶稀有特征的空間co-loca?tion模式挖掘新方法〔J〕.南京大學學報（自然科學），2012，48（1）：99-107.

〔7〕楊世晟，王麗珍，蘆俊麗，等.空間高效用co-location模式挖掘技術(shù)初探〔J〕.小型微型計算機系統(tǒng)，2014，35（10）：2302-2307.

〔8〕王敬華，羅相洲，吳倩.基于效用表的快速高平均效用挖掘算法〔J〕.計算機應(yīng)用，2016，36（11）：3062-3066.

〔9〕江萬國，王麗珍，方圓，等.領(lǐng)域驅(qū)動的高效用co-loca?tion模式挖掘方法〔J〕.計算機應(yīng)用，2017，37（2）：322-328.

〔10〕LIN C W，LAN G C，HONG T P.An incremental?mining algorithm for high utility itemsets〔J〕.Expert Systems with Applications，2012，39：7173-7180.

〔11〕蘆俊麗，王麗珍，肖清，等.空間co-location模式增量挖掘及演化分析〔J〕.軟件學報，2014，25（2）：189-200.

〔12〕WANG X X，WANG L Z，LU J，et al.Effectively Updating High Utility Co-location Patterns in Evolv?ing Spatial Databases〔C〕∕∕InternationalConference on Web-Age Information Management.Springer Inter?