空間co-location模式挖掘表實例的計算方法

曾 新，李曉偉，楊 健

（大理大學數學與計算機學院，云南大理 671003）

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

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

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

1 相關工作

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

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

2 相關定義及性質

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

圖1 空間對象及其實例

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

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

假設實例集為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}}。

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

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

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

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

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

假設c={ }f1,f2,…,fk，

所以模式c的參與度也是單調遞減的。

3 算法

3.1 問題描述假設最小參與度閾值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} }，根據參與率和參與度的計算公式有：

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

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

假定候選模式c={f1,f2,…,fk}，根據co-location模式的反單調性，候選模式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方法的主要區別在于前者將候選模式的前綴模式表實例存儲于數據庫中，后者將其存放于字典中，但是二者都是基于joinbased算法進行算法設計，具體的算法描述如下：

輸入

空間實例集S；

空間鄰近距離閾值dis_thre；

最小參與度閾值min_prev;

中間變量

模式的階k；

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

Ck中表實例的集合Tabk；

k階頻繁模式集合Pk；

空間鄰近關系集neiR

輸出

頻繁模式集P

過程：

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

（2）P=?；

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

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

a.將Pk-1連接產生k階候選模式集Ck；

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

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

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

e.P=P?Pk；

f.返回頻繁模式集P。

4 實驗分析

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

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

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

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

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

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

同一實例集下，隨著鄰近距離閾值的增大，鄰近關系集會隨之擴大，候選模式的行實例數目可能會增大，導致表實例的計算開銷增加。join-based-D方法多次掃描數據庫帶來極大的時間開銷，而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算法的主要時間開銷為連接操作和表實例的計算，而參與度閾值用來衡量模式是否頻繁的標準。隨著參與度閾值的增大，頻繁模式的數目會相應減少，導致連接操作和表實例的計算開銷適當減少。但是，join-based-Z方法的運行效率仍然高于join-based-D方法。

5 結束語

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

〔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模式挖掘技術初探〔J〕.小型微型計算機系統，2014，35（10）：2302-2307.

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

〔9〕江萬國，王麗珍，方圓，等.領域驅動的高效用co-loca?tion模式挖掘方法〔J〕.計算機應用，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?