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

曾　新，李曉偉，楊　健

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

0　引言

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

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

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

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

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

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

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

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

1　相關(guān)工作

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

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

2　問題描述

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

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

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

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

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

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

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

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

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

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

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

用戶設(shè)定參與度閾值為：min_prev=0.7,從圖1中可以分析出，二階模式{F2,F4}和{F3,F4}的表實(shí)例分別為：{(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}的增益率分別為：

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

假設(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模式挖掘標(biāo)準(zhǔn)，模式{F3,F4}更讓用戶感興趣，而在傳統(tǒng)模式挖掘中，其作為非頻繁模式被丟棄。

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

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

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

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

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

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

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

圖2　空間對(duì)象及其實(shí)例Fig. 2　Spatial objects and their instances

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

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

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

定理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.2　高增益率co-location模式挖掘定義

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

稱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}屬于非高增益率模式，當(dāng)對(duì)象fk可同時(shí)正作用率于對(duì)象fi和fj,那么模式{fi,fj,fk}可能為高增益率模式，因此高增益率模式并不滿足反單調(diào)性性質(zhì)。

4　挖掘算法

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

4.1　基礎(chǔ)算法NAGA

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

輸入

F={f1,f2,f3,…,fn}表示有n個(gè)對(duì)象的對(duì)象集;

I={i11,i12,…,i1m,…,inm}表示有n個(gè)對(duì)象，每個(gè)對(duì)象至多有m個(gè)實(shí)例的實(shí)例集;

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

d表示鄰近距離閾值;

zyr_thre表示增益率閾值

中間參數(shù)

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

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

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

輸出

輸出高增益率模式zyrP

算法過程

1)

k=2;

2)

zyrP=?;

3)

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

4)

whilek≤n

a)

b)

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

i)

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

ii)

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

iii)

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

iv)

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

v)

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

1)

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

i)

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

ii)

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

iii)

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

iv)

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

v)

ifTJZSY(ci)≤YSZSY(ci)

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

vi)

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

vii)

ifZYRate(ci)≥zyr_thre

zyrP=zyrP∪ci;

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

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

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

數(shù)據(jù)集中的10個(gè)對(duì)象隨機(jī)產(chǎn)生各自的實(shí)例個(gè)數(shù)，得到的實(shí)例總數(shù)分別為：344、580、803、1 102和1 414，每個(gè)實(shí)例的坐標(biāo)將在[1,100]范圍內(nèi)隨機(jī)產(chǎn)生，其中，鄰近距離閾值d=5,高增益率閾值z(mì)yr_thre=0.2,算法的效率比較如圖3所示。在圖3中，NAGA_JZ算法與NAGA算法在實(shí)例總數(shù)較小時(shí)，執(zhí)行效率并沒有明顯的差距，但是隨著實(shí)例總數(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ù)對(duì)高增益率模式數(shù)的影響

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

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

5.3　鄰近距離閾值對(duì)算法的影響

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

5.4　增益率閾值對(duì)算法的影響

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

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

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

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

在實(shí)例總數(shù)為600，鄰近距離閾值d=5,高增益率閾值z(mì)yr_thre=0.25的條件下，分別對(duì)對(duì)象個(gè)數(shù)為5、10、15、20和25進(jìn)行實(shí)驗(yàn)，比較NAGA算法和NAGA_JZ算法在不同對(duì)象個(gè)數(shù)下的運(yùn)行效率，結(jié)果如圖7所示。對(duì)象個(gè)數(shù)的不斷增加會(huì)導(dǎo)致模式數(shù)增加，需要計(jì)算更多模式的表實(shí)例，所以算法的執(zhí)行時(shí)間也會(huì)隨之增加。然而，算法NAGA_JZ能夠?qū)⒉糠址歉咴鲆媛誓Ｊ郊糁?，避免?jì)算它們的表實(shí)例，因此，其執(zhí)行效率要高于NAGA算法。

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

6　結(jié)語

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

參考文獻(xiàn):

[1]王麗珍,周麗華,陳紅梅,等.數(shù)據(jù)倉庫與數(shù)據(jù)挖掘原理及應(yīng)用[M].2版.北京:科學(xué)出版社,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]曾新,楊健.帶時(shí)間約束的co-location模式挖掘[J].計(jì)算機(jī)科學(xué),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].小型微型計(jì)算機(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].計(jì)算機(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ū)動(dòng)的高效用co-location模式挖掘方法[J].計(jì)算機(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.)