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

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

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

0 引言

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

當需要處理的數據集不僅擁有較大的規模，而且可能包含大量的結果模式集時，為了得到結果集中那些為數不多的巨型模式，就必須找出所有的頻繁模式.也就是說，這將浪費大量的時間來生成中間模式.因為現有的算法大都是依據先驗原理，通過深度或廣度優先遍歷的策略遍歷整個搜索空間，從而驗證每個候選模式是否是頻繁的.而在傳統事務數據的挖掘中，已經有人提出了挖掘長模式的算法[5-6]，且正沿著兩個方向探索：方向一是深化利用垂直數據格式，擴充模式增長的方法，處理具有大量項，但只有少量元組的數據集；方向二就是本文所借鑒的模式融合[7]思想.

1 相關定義

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

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

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

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

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

(1)

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

(2)

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

定理1若c′∈Cc，f∈c，那么c′∪f∈Cc.

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

證明見文獻[7].

由于魯棒性的存在，巨型co-location模式往往會含有大量的空間核模式.又因為巨型模式與它對應的空間核模式之間的魯棒性關系可擴展多層，這樣便有了空間co-location核后代的概念.

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

2 基于模式融合思想的挖掘算法與算法評估模型

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

從給出的方法中可以看出，需要先識別出c′的所有空間核后代，然后才能合并它們.接下來將探討當隨機選取到c′的一個空間核后代c后，該如何找出c′的其他空間核后代.

證明因為c，c′∈Cα，所以根據空間co-location模式的特征距離，可得

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

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

另外，本文使用字典序前綴樹結構[4]來存儲特征鄰近事務集.該結構的優點在于，當需要判斷通過模式融合生成的候選模式c是否擁有完整的團關系時，可以提前刪除那些不會頻繁的候選模式，從而起到剪枝作用.例如圖2給出了表1中特征鄰近事務集的字典序前綴樹.在前綴樹中，所有的子節點都與根節點具有鄰近關系.通過前綴樹可得到c的候選星型模式c′，還可得到c′中每個特征的上界參與率，從而得到c的上界參與度值.根據上界參與度值的大小，就可以進行剪枝了.

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

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

證明見文獻[7].

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

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

表1 關于圖1(a)中所給數據的鄰居事務集和特征鄰居事務集

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

這一引理說明，因為巨型模式比低階模式擁有更強的魯棒性，所以模式融合方法能夠在很高的概率下生成巨型模式.當然，會有一些低階但卻擁有很強魯棒性的模式被挖掘出來.但是當我們從當前池隨機選取K個種子模式開始新一輪的迭代時，這些低階模式被隨機選中的概率也僅為K/|S|，其中S是當前池.即經過多次迭代后，很大概率上低階模式被淘汰出局.算法過程如下.

輸入：

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

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

輸出：

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

變量：

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

NT為鄰居事務集； ENT為特征鄰居事務集； 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);

因此，對于那些微課制作水平不高，對于教學的重難點把握不好的教師，一方面可以自我學習微課的制作技術做到精通，還要精心研究教材，認真備課，從而真正掌握每堂課的教學重難點；另一方面可以根據教學的實際需要，從互聯網上下載一些需要的微課，認真學習和研究，分析他們的課程結構，分析他們的呈現方式，分析他們的授課內容等.這樣可以改變自身制作和教學中存在的不足，進而很快提高老師的微課制作水平

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個部分.第1～4行是第1部分，對于給定的D和d,找到所有的鄰居實例對.然后，通過分組每個實例的鄰居實例對，生成NT.再根據NT生成ENT.接下來就可以基于ENT中每個特征fi的ENT生成fi的前綴樹Treei，其中i=1,2,…,n.

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

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

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

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

(3)

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

3 實驗分析

本實驗的軟件平臺是：MyEclipse Professional 2014，32 位的 Windows 7操作系統，硬件平臺是：Intel(R) Core(TM)2 Duo CPU T6570@2.10 GHz，2G內存聯想筆記本.

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

表2 合成數據上的運行時間Tab.2 Running time about synthesized data ms

表3 真實數據上的運行時間Tab.3 Running time about real data ms

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

圖3 關于K值變換的算法運行時間Fig.3 Running time of algorithm about different K

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

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