空間co-location模式挖掘表實(shí)例的計(jì)算方法

曾 新，李曉偉，楊 健

（大理大學(xué)數(shù)學(xué)與計(jì)算機(jī)學(xué)院，云南大理 671003）

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

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

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

1 相關(guān)工作

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

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

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

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

圖1 空間對(duì)象及其實(shí)例

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

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

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

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

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

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

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

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

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

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

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

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

3 算法

3.1 問(wèn)題描述假設(shè)最小參與度閾值min_prev=0.5，圖1中模式{A,B}的表實(shí)例為{{A.1,B.1},{A.4,B.2}}，{A,C}的表實(shí)例為{{A.1,C.1},{A.3,C.3},{A.4,C.2} }，根據(jù)參與率和參與度的計(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}進(jìn)行連接得到候選模式{A,B,C}，然后，我們通過(guò)前綴模式{A,B}的表實(shí)例來(lái)計(jì)算候選模式{A,B,C}的表實(shí)例。如果{A,B}的一個(gè)行實(shí)例{A.i,B.j}中的每個(gè)實(shí)例都與對(duì)象C的一個(gè)實(shí)例C.m是空間鄰近的，那么{A.i,B.j,C.m}為候選模式{A,B,C}的一個(gè)行實(shí)例，所有行實(shí)例的集合為表實(shí)例。

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

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

輸入

空間實(shí)例集S；

空間鄰近距離閾值dis_thre；

最小參與度閾值min_prev;

中間變量

模式的階k；

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

Ck中表實(shí)例的集合Tabk；

k階頻繁模式集合Pk；

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

輸出

頻繁模式集P

過(guò)程：

（1）頻繁1項(xiàng)集P1為所有對(duì)象；

（2）P=?；

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

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

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

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

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

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

e.P=P?Pk；

f.返回頻繁模式集P。

4 實(shí)驗(yàn)分析

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

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

圖2 不同實(shí)例集下運(yùn)行效率

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

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

圖3 不同鄰近距離閾值下運(yùn)行效率

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

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

圖4 不同參與度閾值下運(yùn)行效率

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

5 結(jié)束語(yǔ)

空間co-location模式挖掘中，模式表實(shí)例的計(jì)算尤為重要，join-based-D和join-based-Z方法能夠?qū)崿F(xiàn)對(duì)候選模式表實(shí)例的計(jì)算。但是，在內(nèi)存大小允許的情況下，join-based-Z方法的執(zhí)行效率要遠(yuǎn)高于join-based-D方法。由于join-based-Z方法受到內(nèi)存大小的限制，所以，未來(lá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〕歐陽(yáng)志平，王麗珍，陳紅梅.模糊對(duì)象的空間co-location模式挖掘研究〔J〕.計(jì)算機(jī)學(xué)報(bào)，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〕.南京大學(xué)學(xué)報(bào)（自然科學(xué)），2012，48（1）：99-107.

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

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

〔9〕江萬(wàn)國(guó)，王麗珍，方圓，等.領(lǐng)域驅(qū)動(dòng)的高效用co-loca?tion模式挖掘方法〔J〕.計(jì)算機(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〕.軟件學(xué)報(bào)，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?