基于模式融合挖掘巨型頻繁co-location模式

袁鞏生， 王麗珍， 陳紅梅， 段江麗

(云南大學(xué) 信息學(xué)院 云南 昆明 650091)

0 引言

Apriori[1]是經(jīng)典的挖掘頻繁項(xiàng)集的算法，經(jīng)典的Join-based[2]、Join-less[3]等co-location挖掘算法便是類Apriori算法，它們通過(guò)利用先驗(yàn)原理，能夠有效挖掘出所有的頻繁co-location模式.然而，根據(jù)頻繁模式的定義，頻繁模式的任何子集都是頻繁的，那么最終可能挖掘出大量的模式.為了解決這一問(wèn)題，研究者提出了挖掘TOP-k閉模式[4]等算法，但取得的效果卻是有限的.更重要的是，在現(xiàn)實(shí)生活中，用戶更在意的是從一堆數(shù)據(jù)中能發(fā)現(xiàn)什么樣的大模式(盡可能多的含有空間特征).例如對(duì)于一個(gè)生態(tài)系統(tǒng)來(lái)說(shuō)，若系統(tǒng)的結(jié)構(gòu)越復(fù)雜，包含的物種越多(大模式)，該系統(tǒng)抵抗外界干擾的能力就越強(qiáng).相反，結(jié)構(gòu)越簡(jiǎn)單，那么它的抗干擾能力就越弱，越容易受外界的影響.因此，大模式在判斷某個(gè)生態(tài)系統(tǒng)的穩(wěn)定性和地區(qū)植被分布的多樣性等方面有著極其重要的意義.

當(dāng)需要處理的數(shù)據(jù)集不僅擁有較大的規(guī)模，而且可能包含大量的結(jié)果模式集時(shí)，為了得到結(jié)果集中那些為數(shù)不多的巨型模式，就必須找出所有的頻繁模式.也就是說(shuō)，這將浪費(fèi)大量的時(shí)間來(lái)生成中間模式.因?yàn)楝F(xiàn)有的算法大都是依據(jù)先驗(yàn)原理，通過(guò)深度或廣度優(yōu)先遍歷的策略遍歷整個(gè)搜索空間，從而驗(yàn)證每個(gè)候選模式是否是頻繁的.而在傳統(tǒng)事務(wù)數(shù)據(jù)的挖掘中，已經(jīng)有人提出了挖掘長(zhǎng)模式的算法[5-6]，且正沿著兩個(gè)方向探索：方向一是深化利用垂直數(shù)據(jù)格式，擴(kuò)充模式增長(zhǎng)的方法，處理具有大量項(xiàng)，但只有少量元組的數(shù)據(jù)集；方向二就是本文所借鑒的模式融合[7]思想.

1 相關(guān)定義

空間特征代表了空間中不同種類的事物.實(shí)例表示的是一個(gè)具體空間位置上的對(duì)象，每個(gè)實(shí)例擁有一個(gè)唯一的編號(hào)，如圖1(a)中A.1.若兩個(gè)實(shí)例滿足空間鄰近關(guān)系R，當(dāng)且僅當(dāng)它們之間的歐氏距離小于等于給定的閾值d(d>0)，而對(duì)于滿足R關(guān)系的兩個(gè)實(shí)例，我們用一條線段連接它們，如圖1(a)中A.1和B.2.團(tuán)是任意兩個(gè)不同特征的實(shí)例之間都滿足R關(guān)系的實(shí)例集，圖1(a)中{A.1,B.2,C.1,D.3}便是一個(gè)團(tuán).倘若一個(gè)團(tuán)包含了co-location模式c中的所有特征，且此團(tuán)中沒有任何一個(gè)真子集可以包含c中的所有特征，那么它就是c的一個(gè)行實(shí)例，記為row-instance(c).而c的所有行實(shí)例的集合稱為表實(shí)例，記為table-instance(c).我們使用參與率和參與度的大小來(lái)度量模式的頻繁性，且參與率和參與度隨著co-location模式階的增大單調(diào)遞減[8].

定義1與階數(shù)較小的模式相比，我們發(fā)現(xiàn)階數(shù)較大的空間co-location模式常常攜帶更重要的信息，稱這種空間co-location模式為巨型co-location模式.

在給出具體空間co-location模式的模式距離之前，我們先設(shè)Ec(f)=πf(table_instance(c))，它表示空間co-location模式c的表實(shí)例中所含的特征f(f∈c)的不同實(shí)例個(gè)數(shù).

圖1 空間特征和空間實(shí)例Fig.1 Spatial features and spatial instances

定義2給定兩個(gè)co-location模式c和c′，設(shè)f為模式c和c′的共有空間特征，也就是說(shuō)，f∈c∩c′，那么關(guān)于模式c和c′的共有空間特征f的特征距離[9]被定義為：

(1)

定義3給定空間co-location模式c和c′，那么c和c′的模式距離[9]定義為：

(2)

對(duì)于一個(gè)空間co-location模式c，將其所有空間co-location核模式的集合記為Cc.

定理1若c′∈Cc，f∈c，那么c′∪f(wàn)∈Cc.

定理2對(duì)于滿足(d,τ)-魯棒的空間co-location模式c，|Cc|≥2d.

證明見文獻(xiàn)[7].

由于魯棒性的存在，巨型co-location模式往往會(huì)含有大量的空間核模式.又因?yàn)榫扌湍Ｊ脚c它對(duì)應(yīng)的空間核模式之間的魯棒性關(guān)系可擴(kuò)展多層，這樣便有了空間co-location核后代的概念.

定義6對(duì)于給定的co-location模式c和c′，若存在一個(gè)序列ci，1≤i≤k，k≥1使對(duì)于所有的0≤i≤k，都能讓c=c0，c′=ck和ci∈Cci+1滿足，則c是c′的空間co-location核后代，簡(jiǎn)稱為空間核后代.

2 基于模式融合思想的挖掘算法與算法評(píng)估模型

模式融合方法首先生成一個(gè)具有較小階數(shù)的頻繁co-location模式的完全集.若它包含的模式的數(shù)量大于K個(gè)，就從集合中隨機(jī)挑選出K個(gè)，否則就返回這K個(gè)模式作為結(jié)果集交給用戶.根據(jù)定義可知，對(duì)于隨機(jī)選取到的K模式中每個(gè)模式c來(lái)說(shuō)，它很可能是某個(gè)巨型模式c′的空間核后代.那么，在這K個(gè)模式中，先識(shí)別出c′的所有空間核后代，再一一合并它們.通過(guò)此方式將會(huì)產(chǎn)生c′的更長(zhǎng)的空間核后代，這使算法在生成c′的過(guò)程中可跳躍前進(jìn).以此類推，通過(guò)每次在產(chǎn)生較長(zhǎng)的空間核后代的集合中再選擇K個(gè)模式作為初始池，用于下次迭代.

從給出的方法中可以看出，需要先識(shí)別出c′的所有空間核后代，然后才能合并它們.接下來(lái)將探討當(dāng)隨機(jī)選取到c′的一個(gè)空間核后代c后，該如何找出c′的其他空間核后代.

證明因?yàn)閏，c′∈Cα，所以根據(jù)空間co-location模式的特征距離，可得

通過(guò)定理3知道c的所有的空間核模式都將存在于一個(gè)直徑為r(τ)的球形度量空間中.即，若一個(gè)空間核模式c′∈Cc，那么在當(dāng)前池中可通過(guò)范圍查詢的方式找到池中所有c的空間核模式.但定理3的逆定理是不成立的.也就是說(shuō)，即使c′∈Cc且D(β,c′)≤r(τ)成立，但并不能確定β∈Cc.

對(duì)于空間特征實(shí)例f.i∈S(實(shí)例集合)，該實(shí)例的鄰居事務(wù)集[3]是一個(gè)包含f.i和所有與特征實(shí)例f.i具有鄰居關(guān)系的其他空間特征實(shí)例的集合，即NT(f.i)={f.i,g.j∈S|R(f.i,g.j)=trueandf≠g}，其中f.i被稱為參考示例.表1給出了圖1(a)中所有實(shí)例的鄰居事務(wù)集.當(dāng)只考慮鄰居事務(wù)集中的空間特征，不再具體細(xì)化到實(shí)例時(shí)，就得到了特征鄰居事務(wù)集[3]，如表1所示.

另外，本文使用字典序前綴樹結(jié)構(gòu)[4]來(lái)存儲(chǔ)特征鄰近事務(wù)集.該結(jié)構(gòu)的優(yōu)點(diǎn)在于，當(dāng)需要判斷通過(guò)模式融合生成的候選模式c是否擁有完整的團(tuán)關(guān)系時(shí)，可以提前刪除那些不會(huì)頻繁的候選模式，從而起到剪枝作用.例如圖2給出了表1中特征鄰近事務(wù)集的字典序前綴樹.在前綴樹中，所有的子節(jié)點(diǎn)都與根節(jié)點(diǎn)具有鄰近關(guān)系.通過(guò)前綴樹可得到c的候選星型模式c′，還可得到c′中每個(gè)特征的上界參與率，從而得到c的上界參與度值.根據(jù)上界參與度值的大小，就可以進(jìn)行剪枝了.

給定一個(gè)n階巨型co-location模式c和一個(gè)包含了c所有k階子模式的選取池，那么由下面的定理4就可知道,從這個(gè)選取池中隨機(jī)選取多少個(gè)模式才能在一個(gè)高概率下覆蓋住c.

定理4[7]當(dāng)均勻地隨機(jī)選取m*=(enlnn)個(gè)模式的時(shí)候，就能在至少1-1/n2概率下覆蓋住c中所有的空間特征.

證明見文獻(xiàn)[7].

若集合S是c的一個(gè)空間核模式互補(bǔ)集，且其出現(xiàn)在挖掘算法的迭代過(guò)程中，倘若S中的任一模式被抽選到，那么S中的其他空間核模式很可能將會(huì)在“球形”空間被找到.那么通過(guò)融合S中的模式便能生成c.所以集合Γc越大，那么生成c的可能性也就越大.而由定理2得出的引理1將給出模式的魯棒性與Γc的大小有著極其密切的關(guān)聯(lián).

引理1一個(gè)滿足(d,τ)-魯棒性的空間co-location模式c至少擁有2d-1-1個(gè)空間核模式互補(bǔ)集，也就是說(shuō)，|Γc|≥2d-1-1.

表1 關(guān)于圖1(a)中所給數(shù)據(jù)的鄰居事務(wù)集和特征鄰居事務(wù)集

圖2 關(guān)于圖1(a)中數(shù)據(jù)集的字典序前綴樹Fig.2 Lexicographic prefix-tree of features of the data set in Fig.1(a)

這一引理說(shuō)明，因?yàn)榫扌湍Ｊ奖鹊碗A模式擁有更強(qiáng)的魯棒性，所以模式融合方法能夠在很高的概率下生成巨型模式.當(dāng)然，會(huì)有一些低階但卻擁有很強(qiáng)魯棒性的模式被挖掘出來(lái).但是當(dāng)我們從當(dāng)前池隨機(jī)選取K個(gè)種子模式開始新一輪的迭代時(shí)，這些低階模式被隨機(jī)選中的概率也僅為K/|S|，其中S是當(dāng)前池.即經(jīng)過(guò)多次迭代后，很大概率上低階模式被淘汰出局.算法過(guò)程如下.

輸入：

F={f1,f2,…,fn}為空間特征集； min_prev為最小參與度閾值； d為空間鄰近距離閾值；

D為空間數(shù)據(jù)集； τ為核比率； K為挖掘出巨型頻繁空間co-location模式的最大數(shù)量.

輸出：

滿足min_prev的巨型頻繁co-location模式集S.

變量：

Pk為k階頻繁空間co-location模式集； k為空間co-location的階(size)； N為鄰居實(shí)例對(duì)；

NT為鄰居事務(wù)集； ENT為特征鄰居事務(wù)集； InitPool為初始池；

Begin

1 N=find_neighbor_pairs(D,d);

2 (NT, ENT)=gen_neighbor_transactions(N);

3 for i=1 to n //遍歷空間特征

4 Treei=build_prefix-tree(fi, ENT);

因此，對(duì)于那些微課制作水平不高，對(duì)于教學(xué)的重難點(diǎn)把握不好的教師，一方面可以自我學(xué)習(xí)微課的制作技術(shù)做到精通，還要精心研究教材，認(rèn)真?zhèn)湔n，從而真正掌握每堂課的教學(xué)重難點(diǎn)；另一方面可以根據(jù)教學(xué)的實(shí)際需要，從互聯(lián)網(wǎng)上下載一些需要的微課，認(rèn)真學(xué)習(xí)和研究，分析他們的課程結(jié)構(gòu)，分析他們的呈現(xiàn)方式，分析他們的授課內(nèi)容等.這樣可以改變自身制作和教學(xué)中存在的不足，進(jìn)而很快提高老師的微課制作水平

5 P1=F; k=2;

6 Pk=gen_prevalent_colocation(Pk-1);

8 InitPool ← Pk;

9 while | InitPool | > K{

10 S ← φ; TmpInitPool ← φ;

11 for i=1 to K{

12 Randomly draw a seed c from InitPool;

13 TmpInitPool ←c∪ TmpInitPool;}

15 for each c∈ InitPool

16 for each c′ ∈ InitPool

17 if D(c, c′)≤ r(τ)

18 c″=c∪ c′ //模式融合生成新模式c″

19 if clique(c″)==ture

20 if calculate_PI(c″) ≥ min_prev

21 then S← S ∪ {c″};

22 InitPool ← S;

23 }

24 return S;

END

此算法主要包含了3個(gè)部分.第1～4行是第1部分，對(duì)于給定的D和d,找到所有的鄰居實(shí)例對(duì).然后，通過(guò)分組每個(gè)實(shí)例的鄰居實(shí)例對(duì)，生成NT.再根據(jù)NT生成ENT.接下來(lái)就可以基于ENT中每個(gè)特征fi的ENT生成fi的前綴樹Treei，其中i=1,2,…,n.

第5～8行是第2部分，生成2階頻繁空間co-location模式完全集作為模式融合的初始池.

第9～23行是第3部分，是用來(lái)生成最終的巨型co-location模式集S.第9行用來(lái)控制循環(huán)，也是算法終止條件，若得到的結(jié)果集S(InitPool)中包含的模式數(shù)量大于K就繼續(xù)運(yùn)行算法的第3部分，直到滿足條件為止.第11～13行用來(lái)從初始池中隨機(jī)選取K個(gè)模式.第15～21行對(duì)目前初始池中的每個(gè)模式c進(jìn)行檢測(cè)，判斷模式c′是否處于c的球形空間.如果成立，就融合c和c′，從而生成新的較長(zhǎng)的模式c″，然后通過(guò)前綴樹判斷這個(gè)候選模式是否符合團(tuán)關(guān)系，若符合，在第20行中通過(guò)NT生成該模式的表實(shí)例，進(jìn)而計(jì)算其真實(shí)參與度值.若c″的PI值大于等于min_prev，那就把c″添加到S中.其中，在第19行判斷c″是否滿足團(tuán)關(guān)系使用的是前綴樹方法，并通過(guò)上界參與率來(lái)剪枝掉一些不滿足條件的模式，從而提高算法效率.

定義8空間co-location模式c和c′的編輯距離[7]Edit(c,c′)被定義為

Edit(c,c′)=|c∪c′|-|c∩c′|.

(3)

若給定兩個(gè)空間co-location模式集合P和Q，其中P指的是通過(guò)模式融合思想挖掘到近似集，Q指的是完整的結(jié)果集，有了上述3個(gè)定義，便可以使用Δ(P,πQ)來(lái)評(píng)估P和Q之間的近似程度.也就是說(shuō)，平均最大近似誤差值越小，集合P越接近集合Q.

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

本實(shí)驗(yàn)的軟件平臺(tái)是：MyEclipse Professional 2014，32 位的 Windows 7操作系統(tǒng)，硬件平臺(tái)是：Intel(R) Core(TM)2 Duo CPU T6570@2.10 GHz，2G內(nèi)存聯(lián)想筆記本.

表2給出了兩個(gè)算法的運(yùn)行時(shí)間.從整體而言，隨著空間特征數(shù)目N的增大，與基于全連接算法相比，基于模式融合的算法運(yùn)行所需要的時(shí)間要少得多.實(shí)驗(yàn)所用數(shù)據(jù)是通過(guò)在60×60的空間區(qū)域范圍內(nèi)，對(duì)于N個(gè)空間特征，每個(gè)特征隨機(jī)進(jìn)行生成0～100個(gè)實(shí)例得到的，并把min_prev設(shè)為0.25，R關(guān)系距離閾值設(shè)為5，τ設(shè)為0.5，K設(shè)為4.表3中實(shí)驗(yàn)所用數(shù)據(jù)是“云南省三江并流”區(qū)域植物分布的真實(shí)數(shù)據(jù).通過(guò)表中的數(shù)據(jù)可以看出，對(duì)于同一組數(shù)據(jù)，在相同距離閾值、不同最小參與率閾值下，模式融合算法比全連接算法運(yùn)行時(shí)間要少很多.

表2 合成數(shù)據(jù)上的運(yùn)行時(shí)間Tab.2 Running time about synthesized data ms

表3 真實(shí)數(shù)據(jù)上的運(yùn)行時(shí)間Tab.3 Running time about real data ms

圖3給出當(dāng)其他參數(shù)不變，只增大K值時(shí)，對(duì)于同一組數(shù)據(jù)整體而言，基于模式融合策略所提出的模式挖掘算法運(yùn)行所需時(shí)間是逐漸增大的.其中，縱軸的時(shí)間單位是ms.圖4給出當(dāng)其他參數(shù)不變，只增大K值的時(shí)候，對(duì)于同一組數(shù)據(jù)整體而言，基于模式融合策略所提出的模式挖掘算法挖掘出來(lái)的模式質(zhì)量是逐步提高的.其中，縱軸表示是平均最大近似誤差.圖3和圖4實(shí)驗(yàn)所用數(shù)據(jù)都是通過(guò)在60×60的空間區(qū)域范圍內(nèi)，對(duì)于28個(gè)空間特征，每個(gè)特征隨機(jī)進(jìn)行生成0～100個(gè)實(shí)例得到的，其中min_prev設(shè)為0.25，R關(guān)系距離閾值設(shè)為5，τ設(shè)為0.5.

圖3 關(guān)于K值變換的算法運(yùn)行時(shí)間Fig.3 Running time of algorithm about different K

圖4 關(guān)于K值變換的平均最大近似誤差Fig.4 Maximum approximation error about different K

之后工作可以先把2階模式的完全集視為初始池，再進(jìn)行處理.但是，因模式的數(shù)量很多，可能導(dǎo)致時(shí)間復(fù)雜性不會(huì)很低.而且，此方法也會(huì)受到隨機(jī)選取過(guò)程的影響，需考慮如何合理地選取空間核模式.另外，還可以嘗試模糊思想來(lái)挖掘.按照模糊論的知識(shí)進(jìn)行發(fā)散思維，看是否能夠使用模糊思想來(lái)挖掘巨型模式.