帶鄰近作用的高增益率co-location模式挖掘

曾　新，李曉偉，楊　健

(大理大學 數(shù)學與計算機學院，云南 大理 671003)(*通信作者電子郵箱hbzengxin@163.com)

0　引言

隨著信息技術(shù)的快速發(fā)展，空間數(shù)據(jù)集呈現(xiàn)爆炸式的增長。面對具有海量性、高維性等特點的空間數(shù)據(jù)集，如何從空間數(shù)據(jù)庫當中挖掘出潛在的、人們感興趣的知識或其他沒有顯示在存儲空間數(shù)據(jù)庫中的模式，從而指導科學決策，顯得尤為重要，目前空間數(shù)據(jù)挖掘已經(jīng)成為熱點研究內(nèi)容之一。

空間co-location模式是空間特征的一個子集，它們的實例在空間中頻繁關(guān)聯(lián)。空間co-location模式廣泛存在于現(xiàn)實生活當中，如西尼羅河病毒通常發(fā)生在蚊子泛濫、飼養(yǎng)家禽的區(qū)域；植物學家們發(fā)現(xiàn)“半濕潤常綠闊葉林”生長的地方80%會有“蘭類”植物生長[1]。

目前大多數(shù)空間co-location模式挖掘的一般流程為：

1)根據(jù)用戶設(shè)定的鄰近距離閾值計算出不同對象實例間的鄰近關(guān)系集；

2)通過連接k階頻繁模式，生成(k+1)階模式候選集；

3)依據(jù)鄰近關(guān)系集生成候選模式的表實例；

4)從模式的表實例中獲取模式的參與度，如果模式參與度大于或等于用戶設(shè)定的閾值，則模式為頻繁模式，否則為非頻繁模式。

從空間co-location模式挖掘的一般流程中可以看出：大多數(shù)co-location模式挖掘僅僅利用距離閾值確定實例間的鄰近關(guān)系，進而依據(jù)參與度閾值確定co-location模式，并未考慮不同對象的鄰近實例相互作用和模式的增益率問題，使得用戶感興趣的部分高增益率模式并沒有被捕捉到，造成決策失誤。例如：A、B兩種蔬菜，如果按照傳統(tǒng)的co-location模式挖掘方法，A、B不滿足頻繁模式條件，但是將A和B進行套間種植，可以相互促進生長，增加各自的收益，最終獲得的模式增益率要遠高于傳統(tǒng)挖掘方法獲得的頻繁模式的增益率，這類高增益率模式也是用戶感興趣的模式。

1　相關(guān)工作

近年來，空間co-location模式挖掘取得了豐碩成果。文獻[2]提了出基于全連接的方式生成候選項集，并計算候選項集表實例的join-based算法；文獻[3]提出了將實例進行分塊處理，對塊內(nèi)、塊間實例進行連接的partial-join(部分連接)算法；文獻[4]提出了一種基于星型鄰近擴展的join-less(無連接)算法，通過查詢操作來代替連接操作，以解決候選模式生成中的連接開銷問題；文獻[5]提出了基于前綴樹的CPI-tree(Co-location Pattern Instance tree)算法，以樹型結(jié)構(gòu)表示空間對象實例間的鄰近關(guān)系，co-location表實例通過CPI-tree快速生成，算法性能超過了join-less算法；文獻[6]針對空間對象實例存在約束條件問題，提出了帶有時間約束的co-location模式挖掘。

高效用模式挖掘綜合考慮了項的出現(xiàn)次數(shù)和項本身的權(quán)重，其在實際場景當中具有更廣泛的應(yīng)用。文獻[7]提出了不產(chǎn)生候選項集的高效用項集挖掘算法；文獻[8]針對高效用項集挖掘算法，提出了一些剪枝策略；文獻[9]提出了從事務(wù)數(shù)據(jù)庫當中挖掘出高效用項集的有效算法；文獻[10]利用估計效用同現(xiàn)的剪枝策略，提出了快速高效用挖掘算法；文獻[11]提出了目前已知最優(yōu)高平均效用項集挖掘算法HAUI-Miner(High Average Utility Itemset Miner),該算法采用AU-list(Average Utility List)結(jié)構(gòu)保存項集效用信息，通過AU-list連接比較挖掘出所有的高平均效用項集，實驗表明其時空性能最優(yōu)；文獻[12]將效用概念引入到空間co-location模式挖掘中，定義了模式效用、模式效用率、擴展模式效用等概念，并提出了完全剪枝算法；文獻[13]提出了挖掘高平均效用項集的改進算法FHAUI(Fast High Average Utility Itemset)，其將效用信息保存到效用列表中，通過效用列表的比較挖掘出高平均效用值；文獻[14]充分考慮同一特征不同實例間的差異，提出了帶效用值的空間實例，定義了新的效用參與度UPI(Utility Participation Index)作為高效用co-location模式的有趣度量指標，并將領(lǐng)域知識應(yīng)用到挖掘過程當中。

2　問題描述

下面以一個例子來描述本文研究的問題：不同對象的鄰近實例相互作用對co-location模式增益率的影響。

四種不同種類的蔬菜名稱及其季均收益如表1所示。

表1　蔬菜名稱及其季均收益Tab. 1　Vegetable name and its seasonal average income

其中季均收益表示對象某個實例在一個季度內(nèi)的平均收益，默認同一對象的所有實例具有相同的季均收益，此處的季均收益就是對象的效用值，在高效用co-location模式挖掘的相關(guān)文獻[7-14]中都以效用值來表示。

四種不同種類的蔬菜套間種植對收益的影響，即不同對象的鄰近實例相互作用對收益產(chǎn)生的影響如表2所示。

表2　相互作用率Tab. 2　Interaction between objects

其中套間種植是指在用戶給定的距離閾值內(nèi)，對F1和F2進行合理種植，對象之間會在陽光、土壤、水分等方面相互影響、互相補充，促進各自生長。而(F1,F2)的相互作用率由兩部分組成：1%～5%，1%～5%，前1個數(shù)據(jù)表示套間種植時，F(xiàn)1的季均收益會提升1%～5%，后1個數(shù)據(jù)表示F2的季均收益會提升1%～5%，即二者進行套間種植能夠達到共同增加收益的目的。例如：韭菜和豇豆套間種植會相互促進生長，提升總收益。

以增益率為目的的co-location模式挖掘與傳統(tǒng)的co-location模式挖掘有一定的區(qū)別，其以增益率作為衡量co-location模式挖掘效果的標準，下面以實例進行詳細闡述。

四種不同種類的蔬菜F1、F2、F3和F4，分別有3、2、3和4個不同的品種，不同品種的種植分布情況如圖1所示。

圖1　不同種類蔬菜及其品種分布圖Fig. 1　Distribution of different kinds of vegetables and their varieties

如果兩種不同品種的蔬菜進行間套種植(鄰近)，則用實線將二者連接起來。

用戶設(shè)定參與度閾值為：min_prev=0.7,從圖1中可以分析出，二階模式{F2,F4}和{F3,F4}的表實例分別為：{(F2.1,F4.2),(F2.2,F4.1),(F2.2,F4.3)}和{(F3.2,F4.2),(F3.3,F4.1)}。PI({F2,F4})=min(2/2,3/4)=0.75≥min_prev,{F2,F4}為頻繁模式；PI({F3,F4})=min(2/3,2/4)=0.5≤min_prev,{F3,F4}為非頻繁模式。而模式{F2,F4}和{F3,F4}的收益為：

SY({F2,F4})=2×2×(1+(5%～10%))+

3×2×(1+(-10%～-5%))

SY({F3,F4})=2×5×(1+(1%～10%))+

2×2×(1+(1%～10%))

模式{F2,F4}和{F3,F4}的增益率分別為：

由于作用率還受到其他因素的影響，因此是一個變化的值，在研究當中，我們將在給定的作用率范圍內(nèi)隨機取值。

假設(shè)模式收益SY({F2,F4})和SY({F3,F4})分別取各自的最大值和最小值，那么max(ZYRate({F2,F4}))=0.01,而min(ZYRate({F3,F4}))=0.01,則有如下關(guān)系式：

ZYRate({F3,F4})≥ZYRate({F2,F4})

因此將模式增益率作為co-location模式挖掘標準，模式{F3,F4}更讓用戶感興趣，而在傳統(tǒng)模式挖掘中，其作為非頻繁模式被丟棄。

現(xiàn)實生活當中，很多農(nóng)戶將不同作物進行套間種植，期望獲得更好的收益，但是盲目的作物套間種植有可能會導致作物減產(chǎn)。例如西紅柿和土豆進行套間種植，它們會被同樣的枯萎病襲擊，導致雙減產(chǎn)，因此研究帶鄰近影響的co-location模式挖掘為科學進行作物套間種植提供理論依據(jù)。

3　相關(guān)概念及定義

3.1　空間co-location模式挖掘概念

空間對象是指空間不同類別的事物，而在空間某個確定位置上的對象稱為空間對象實例。例如圖2中有A、B、C三個不同空間對象，每個空間對象分別有4、2和3個對象實例。

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

R(A.1,B.1) ?distance(A.1,B.1)≤d

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

圖2　空間對象及其實例Fig. 2　Spatial objects and their instances

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

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

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

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

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

假設(shè)：

c={f1,f2,…,fk}

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

3.2　高增益率co-location模式挖掘定義

高增益率co-location模式挖掘是指挖掘增益率大于或等于用戶給定增益率閾值的模式。

假設(shè)給定的數(shù)據(jù)集中有n個不同對象，對象集表示為F={f1,f2, …,fn},每個對象fi的季均收益表示為jas(fi)；模式c由k個對象組成，表示為c={f1,f2,…,fk},其中k≤n；模式c的表實例表示為table_instance(c),那么模式c中某個對象fi的實例在table_instance(c)中不重復出現(xiàn)的個數(shù)表示為ct=fi(table_instance(c))。

定義1模式c={f1,f2,…,fk},模式c中的一組對象(fi,fj)進行套間種植的相互作用率為(xi%～yi%,xj%～yj%),xi%～yi%表示套間種植fj→fi產(chǎn)生正或負的作用率，xj%～yj%表示套間種植fi→fj產(chǎn)生正或負的作用率，用EZYRate(fj→fi)來表示fj→fi的作用率，其中1≤i,j≤k,i≠j。

由于模式c中每個對象fi與其他(k-1)個對象進行套間種植，同時受到(k-1)個對象的影響，所以對象fi在模式c中的作用率為：

稱DZYRate(fi,c)為對象作用率。

若由總體X的樣本X1,X2,…,Xn確定的兩個統(tǒng)計量為：

θ1=θ1(X1,X2,…,Xn),θ2=θ2(X1,X2,…,Xn)

且θ1<θ2，則稱[θ1,θ2]為隨機區(qū)間。

如果獲得樣本值x1,x2,…,xn,那么θ1(x1,x2,…,xn)和θ2(x1,x2,…,xn)都是常數(shù)，[θ1,θ2]成為常數(shù)區(qū)間。

設(shè)θ是總體X的一個未知參數(shù)，0<α<1能滿足P{θ1≤θ≤θ2}=1-α,則區(qū)間[θ1,θ2]是θ置信度為1-α的置信區(qū)間。

對象作用率DZYRate(fi,c)等于多個不同實例的相互作用率之和，因此，存在區(qū)間[θ1,θ2]使得θ=DZYRate(fi,c)滿足P{θ1≤θ≤θ2}=1-α,并具有1-α置信度，所以對象作用率具有一定的有效性。

定義2模式c={f1,f2,…,fk},模式c中某個對象fi的總收益等于fi的實例在table_instance(c)中不重復出現(xiàn)的個數(shù)ct與對象fi的季均收益jas(fi)的乘積，用YDZSY(fi,c)表示：

YDZSY(fi,c)=ct×jas(fi)

稱YDZSY(fi,c)為原對象總收益。

定義3模式c={f1,f2,…,fk},模式c的原始總收益等于模式內(nèi)所有對象的原對象總收益之和，用YSZSY(c)表示：

稱YSZSY(c)為模式c的原始總收益。

定義4在帶鄰近作用的co-location模式挖掘中，模式c={f1,f2,…,fk},模式c中某個對象fi的套間總收益等于fi的實例在table_instance(c)中不重復出現(xiàn)的個數(shù)ct、對象fi的季均收益jas(fi)和其對象作用率DZYRate(fi,c)三者的乘積，稱為套間對象總收益，用TDZSY(fi,c)表示：

TDZSY(fi,c)=ct×jas(fi)×(1+DZYRate(fi,c))

定義5在帶鄰近作用的co-location模式挖掘中，模式c={f1,f2,…,fk},模式c的套間總收益等于模式內(nèi)所有對象的套間對象總收益之和，用TJZSY(c)來表示，稱為套間總收益：

定義6模式c={f1,f2,…,fk}的原始總收益為YSZSY(c),進行套間種植，并受到鄰近影響后，模式c的套間總收益為TJZSY(c),則模式c的增益率的計算公式為：

稱ZYRate(c)為模式c的增益率。

定義7用戶給定的增益率閾值為zyr_thre,若模式c={f1,f2,…,fk}的增益率ZYRate(c)≥zyr_thre,模式c為高增益率模式，否則為非高增益率模式。

傳統(tǒng)co-location模式滿足反單調(diào)性質(zhì)，但是高增益率模式并不滿足反單調(diào)性性質(zhì)，例如：模式{fi,fj}屬于非高增益率模式，當對象fk可同時正作用率于對象fi和fj,那么模式{fi,fj,fk}可能為高增益率模式，因此高增益率模式并不滿足反單調(diào)性性質(zhì)。

4　挖掘算法

首先給出帶鄰近作用的高收益率co-location模式挖掘的基礎(chǔ)算法，然后在其基礎(chǔ)上給出有效的剪枝算法，提高算法的運行效率。

4.1　基礎(chǔ)算法NAGA

由于帶鄰近作用的高收益率co-location模式不滿足反單調(diào)性性質(zhì)，所以不能采用傳統(tǒng)co-location模式挖掘的一般算法，因此其中心思想是利用組合的方式生成對象集F={f1,f2,f3,…,fn}的所有子模式，然后計算出每個子模式的表實例，最后求出每個子模式的增益率，并與用戶給定的增益率閾值進行比較，輸出高增益率模式?；A(chǔ)算法(NAGA)描述如下：

輸入

F={f1,f2,f3,…,fn}表示有n個對象的對象集;

I={i11,i12,…,i1m,…,inm}表示有n個對象，每個對象至多有m個實例的實例集;

jas(fi)表示對象fi的季均收益;

d表示鄰近距離閾值;

zyr_thre表示增益率閾值

中間參數(shù)

Ck表示k階co-location模式的候選集;

Tab(ci)表示Ck中第i個模式的表實例;

鄰近關(guān)系集：neiR

輸出

輸出高增益率模式zyrP

算法過程

1)

k=2;

2)

zyrP=?;

3)

計算不同對象實例間的鄰近距離，將鄰近距離小于鄰近距離閾值d的實例對并入鄰近關(guān)系集neiR;

4)

whilek≤n

a)

b)

for(i=1;i≤len(Ck);i++)

i)

根據(jù)鄰近關(guān)系集neiR,計算候選模式集Ck中第i個模式ci的表實例Tab(ci);

ii)

根據(jù)模式ci表實例Tab(ci)和對象fi的季均收益jas(fi),計算出每個對象的原對象總收益，最后得到模式ci的原始總收益YSZSY(ci);

iii)

根據(jù)Z,計算模式ci中每個對象的作用率DZYRate(fi,ci);

iv)

根據(jù)模式ci表實例Tab(ci)、對象fi的季均收益jas(fi)和DZYRate(fi,ci),計算出每個對象的套間對象總收益，最后得到TJZSY(ci);

v)

最后利用YSZSY(ci)和TJZSY(ci)計算出模式ci的增益率ZYRate(ci);

vi)

ifZYRate(ci)≥zyr_thre

zyrP=zyrP∪ci;

c)

k=k+1;

5)

輸出高增益率模式zyrP

4.2　剪枝算法NAGA_JZ

剪枝算法NAGA_JZ在基礎(chǔ)算法NAGA的基礎(chǔ)上進行剪枝，以提高高增益率模式的挖掘效率。NAGA_JZ算法對NAGA算法主要進行兩個剪枝步：一個是對候選模式集Ck中的模式ci,首先計算其每個對象的作用率，如果其所有對象的作用率都小于或等于0，那么就有ZYRate(ci)≤0,則模式ci肯定為非高增益率模式；另一個是模式ci的套間總收益小于或等于原始總收益，那么ZYRate(ci)≤0,模式ci為非高增益率模式。剪枝算法NAGA_JZ與基礎(chǔ)算法NAGA的不同集中在NAGA算法的b)步內(nèi)，因此只對NAGA_JZ算法的4.2步作詳細描述：

1)

for(i=1;i≤len(Ck);i++)

i)

根據(jù)Z,計算模式ci中每個對象的作用率DZYRate(fi,ci),如果所有對象的作用率都小于或等于0，那么Ck=Ck-ci,并轉(zhuǎn)入下一次循環(huán);

ii)

根據(jù)鄰近關(guān)系集neiR,計算候選模式集Ck中第i個模式ci的表實例Tab(ci);

iii)

根據(jù)模式ci表實例Tab(ci)和對象fi的季均收益jas(fi),計算出每個對象的原對象總收益，最后得到模式ci的原始總收益YSZSY(ci);

iv)

根據(jù)模式ci表實例Tab(ci)、對象fi的季均收益jas(fi)和DZYRate(fi,ci),計算出每個對象的套間對象總收益，最后得到TJZSY(ci);

v)

ifTJZSY(ci)≤YSZSY(ci)

Ck=Ck-ci,并轉(zhuǎn)入下一次循環(huán);

vi)

最后利用YSZSY(ci)和TJZSY(ci)計算出模式ci的增益率ZYRate(ci);

vii)

ifZYRate(ci)≥zyr_thre

zyrP=zyrP∪ci;

5　實驗分析

為了評估NAGA算法的正確性、實用性以及NAGA_JZ算法的高效性等性能，本文進行了大量的對比實驗與分析。實驗的硬件平臺為Intel Core i3處理器，4 GB內(nèi)存，64位Windows 7操作系統(tǒng)，軟件編程環(huán)境為Python 2.7。實驗采用的數(shù)據(jù)集均隨機產(chǎn)生，產(chǎn)生數(shù)據(jù)集的區(qū)域為[1,100]，每個對象的實例個數(shù)、季均收益和對象間的相互作用率也隨機產(chǎn)生。

5.1　基礎(chǔ)算法與剪枝算法的效率比較

數(shù)據(jù)集中的10個對象隨機產(chǎn)生各自的實例個數(shù)，得到的實例總數(shù)分別為：344、580、803、1 102和1 414，每個實例的坐標將在[1,100]范圍內(nèi)隨機產(chǎn)生，其中，鄰近距離閾值d=5,高增益率閾值zyr_thre=0.2,算法的效率比較如圖3所示。在圖3中，NAGA_JZ算法與NAGA算法在實例總數(shù)較小時，執(zhí)行效率并沒有明顯的差距，但是隨著實例總數(shù)的不斷增大，NAGA_JZ算法的執(zhí)行效率要優(yōu)于NAGA算法，因此NAGA_JZ算法起到了一定的優(yōu)化效果。

圖3　基礎(chǔ)算法與剪枝算法執(zhí)行效率比較Fig. 3　Comparison of execution efficiency between NAGA and NAGA_JZ

5.2　實例總數(shù)對高增益率模式數(shù)的影響

與5.1節(jié)相同的參數(shù)設(shè)置下，實例總數(shù)對高增益率模式數(shù)的影響如圖4所示。由于對象個數(shù)為10，隨著對象實例數(shù)的增多，模式的行實例數(shù)會隨之增多，低階高增益模式數(shù)會增加，同時會產(chǎn)生部分高階高增益率模式，因此總的高增益率模式數(shù)會不斷增大。

圖4　實例總數(shù)對高增益率模式數(shù)的影響Fig. 4　Influence of number of instances on number of high gain rate patterns

5.3　鄰近距離閾值對算法的影響

在數(shù)據(jù)集對象數(shù)為10，實例總數(shù)為1 102，高增益率閾值zyr_thre=0.2的情況下，分別對鄰近距離閾值為1、3、5、7和9進行實驗，并統(tǒng)計挖掘出的高增益率模式數(shù)，如圖5(a)所示。隨著鄰近距離閾值的不斷增大，高增益率模式數(shù)也不斷增多，由于數(shù)據(jù)集大小一定，高增益率模式數(shù)會趨于某一值。在相同的條件下，對NAGA算法和NAGA_JZ算法的執(zhí)行效率進行對比，結(jié)果如圖5(b)所示。鄰近距離閾值會直接影響模式行實例數(shù)，隨著實例數(shù)的增大，鄰近距離閾值對算法的效率影響將更加明顯。

5.4　增益率閾值對算法的影響

在數(shù)據(jù)集對象數(shù)為10，實例總數(shù)為1 102，鄰近距離閾值d=5的情況下，分別對增益率閾值為0.1、0.15、0.2、0.25和0.3進行實驗，并統(tǒng)計高增益率模式數(shù)，如圖6(a)所示。隨著增益率閾值的不斷增大，滿足條件的高增益率模式數(shù)會不斷減少。同時，在相同條件下，對NAGA算法和NAGA_JZ算法的執(zhí)行效率進行對比，結(jié)果如圖6(b)所示。由于算法的主要耗時在于模式表實例的計算，因此增益率閾值對算法的效率幾乎沒有影響。

圖5　鄰近距離閾值對高增益率模式數(shù)和算法效率的影響Fig. 5　Influence of neighboring distance threshold on number of high gain patterns and algorithm efficiency

圖6　增益率閾值對高增益率模式數(shù)和算法效率的影響Fig. 6　Influence of gain rate threshold on number of high gain patterns and algorithm efficiency

5.5　對象個數(shù)對算法效率的影響

在實例總數(shù)為600，鄰近距離閾值d=5,高增益率閾值zyr_thre=0.25的條件下，分別對對象個數(shù)為5、10、15、20和25進行實驗，比較NAGA算法和NAGA_JZ算法在不同對象個數(shù)下的運行效率，結(jié)果如圖7所示。對象個數(shù)的不斷增加會導致模式數(shù)增加，需要計算更多模式的表實例，所以算法的執(zhí)行時間也會隨之增加。然而，算法NAGA_JZ能夠?qū)⒉糠址歉咴鲆媛誓Ｊ郊糁Γ苊庥嬎闼鼈兊谋韺嵗?，因此，其?zhí)行效率要高于NAGA算法。

圖7　對象個數(shù)對算法效率的影響Fig. 7　Influence of number of objects on algorithm efficiency

6　結(jié)語

在單個對象季均收益一定的情況下，如何將不同對象進行套間種植，利用不同對象間的相互作用，提高模式的整體收益，具有一定應(yīng)用價值。從鄰近關(guān)系中計算出每個模式的表實例，并根據(jù)增益率閾值挖掘出高增益率模式，為科學指導套間種植提供理論依據(jù)。在未來的研究工作當中，可以繼續(xù)研究高效的剪枝策略和基于top-k的高增益率co-location模式挖掘。

參考文獻:

[1]王麗珍,周麗華,陳紅梅,等.數(shù)據(jù)倉庫與數(shù)據(jù)挖掘原理及應(yīng)用[M].2版.北京:科學出版社,2009:1-19. (WANG L Z, ZHOU L H, CHEN H M, et al. The Principle and Applications of Data Warehouse and Data Mining [M]. 2nd ed. Beijing: Science Press, 2009: 1-19.)

[2]HUANG Y, SHEKHAR S, XIONG H. Discovering co-location patterns from spatial data sets: a general approach [J]. IEEE Transactions on Knowledge and Data Engineering, 2004, 16(12): 1472-1485.

[3]YOO J S, SHEKHAR S, SMITH S, et al. A partial join approach for mining co-location patterns [C]// GIS ’04: Proceedings of the 12th Annual ACM International Workshop on Geographic Information Systems. New York: ACM, 2004: 241-249.

[4]YOO J S, SHEKHAR S, CELIK M. A join-less approach for co-location pattern mining: a summary of results [C]// ICDM ’05: Proceedings of the 5th IEEE International Conference on Data Mining. Washington, DC: IEEE Computer Society, 2005: 813-816.

[5]WANG L, BAO Y, LU J, et al. A new join-less approach for co-location pattern mining [C]// CIT 2008: Proceedings of the 8th IEEE International Conference on Computer and Information Technology. Washington, DC: IEEE Computer Society, 2008: 197-202.

[6]曾新,楊健.帶時間約束的co-location模式挖掘[J].計算機科學,2016,43(2):293-296,301. (ZENG X, YANG J. Co-location patterns mining with time constraint [J]. Computer Science, 2016, 43(2): 293-296, 301.)

[7]LIU M, QU J. Mining high utility itemsets without candidate generation [C]// CIKM ’12: Proceedings of the 21st ACM International Conference on Information and Knowledge Management. New York: ACM, 2012: 55-64.

[8]KRISHNAMOORTHY S. Pruning strategies for mining high utility itemsets [J]. Expert Systems with Applications, 2015, 42(5): 2371-2381.

[9]TSENG V S, SHIE B-E, WU C-W, et al. Efficient algorithms for mining high utility itemsets from transactional databases [J]. IEEE Transactions on Knowledge and Data Engineering, 2013, 25(8): 1772-1786.

[10]FOURNIER-VIGER P, WU C W, ZIDA S, et al. FHM: faster high-utility itemset mining using estimated utility co-occurrence pruning [C]// ISMIS 2014: Proceedings of the 21st International Symposium Foundations of Intelligent System, LNCS 8502. Cham: Springer, 2014: 83-92.

[11]LIN J C-W, LI T, FOURNIER-VIGER P, et al. An efficient algorithm to mine high average-utility itemsets [J]. Advanced Engineering Informatics, 2016, 30(2): 233-243.

[12]楊世晟,王麗珍,蘆俊麗,等.空間高效用co-location模式挖掘技術(shù)初探[J].小型微型計算機系統(tǒng),2014,35(10):2302-2307. (YANG S S, WANG L Z, LU J L, et al. Primary exploration for spatial high utility co-location patterns [J]. Journal of Chinese Computer Systems, 2014, 35(10): 2302-2307.)

[13]王敬華,羅相洲,吳倩.基于效用表的快速高平均效用挖掘算法[J].計算機應(yīng)用,2016,36(11):3062-3066. (WANG J H, LUO X Z, WU Q. Fast high average-utility itemset mining algorithm based on utility-list structure [J]. Journal of Computer Applications, 2016, 36(11): 3062-3066.)

[14]江萬國,王麗珍,方圓,等.領(lǐng)域驅(qū)動的高效用co-location模式挖掘方法[J].計算機應(yīng)用, 2017, 37(2):322-328. (JIANG W G, WANG L Z, FANG Y, et al. Domain-driven high utility co-location pattern mining method [J]. Journal of Computer Applications, 2017, 37(2): 322-328.)