孔 明,魏 東,2,冉義兵,畢國鵬

1(北京建筑大學(xué) 電氣與信息工程學(xué)院,北京 100044)2(北京市科學(xué)技術(shù)委員會 建筑大數(shù)據(jù)智能處理方法研究北京市重點實驗室,北京 100044)3(北京聲訊電子股份有限公司,北京 100094)

1 引 言

隨著信息網(wǎng)絡(luò)的快速發(fā)展和信息技術(shù)的廣泛應(yīng)用,客戶關(guān)系管理系統(tǒng)、電子商務(wù)系統(tǒng)、監(jiān)控系統(tǒng)等各類信息系統(tǒng)得以部署,從這些系統(tǒng)中可以獲取大量的事務(wù)日志.事務(wù)日志一般包括活動內(nèi)容、執(zhí)行時間、參與者等信息[1].通過對日志信息進(jìn)行挖掘,可以發(fā)現(xiàn)在給定時間段內(nèi)經(jīng)常共同出現(xiàn)在同一地點的對象(用戶、車輛、人群等),而這些在時空上頻繁共現(xiàn)的對象,即為伴隨模式.伴隨模式通常蘊(yùn)含著事物間潛在的關(guān)系,因此伴隨模式的挖掘被廣泛應(yīng)用于各類信息系統(tǒng)中.例如,利用學(xué)生卡管理系統(tǒng)的刷卡數(shù)據(jù)推斷學(xué)生的時空共現(xiàn),有利于構(gòu)建和分析真實社會網(wǎng)絡(luò)[1];在車輛智能監(jiān)測記錄系統(tǒng)的過車數(shù)據(jù)中挖掘伴隨車輛,有利于公安部門搜尋有結(jié)伴作案的嫌疑車輛[2];基于移動通信基站IP數(shù)據(jù)的伴隨人員推薦,有利于移動運營商向潛在的用戶推薦服務(wù);基于用戶位置簽到數(shù)據(jù)的伴隨人群發(fā)現(xiàn),有利于解決所在簽到地點的資源配置和規(guī)劃決策問題[3].

現(xiàn)有伴隨模式可分為軌跡伴隨模式和頻繁伴隨模式,軌跡伴隨模式是指在設(shè)定的時間長度閾值上,具有相同或相似運動軌跡的移動對象群體;頻繁伴隨模式是指在設(shè)定時間內(nèi)頻繁出現(xiàn)在多個不同數(shù)據(jù)流上的一組對象[4].伴隨模式挖掘方法可分為軌跡相似度算法和關(guān)聯(lián)規(guī)則算法.

軌跡相似性算法一般用于挖掘軌跡伴隨模式,該算法通過構(gòu)建對象的移動序列,求得對象之間移動軌跡的最長公共子序列,當(dāng)最長公共子序列的長度達(dá)到設(shè)定閾值,則判定這些對象存在伴隨關(guān)系.趙新勇等[5]提出了基于車牌自動識別數(shù)據(jù)的最長公共子序列算法,以實現(xiàn)伴隨車輛的檢測和識別;Zheng等[6]提出了一種基于密度聚類的伴隨模式挖掘算法,用于發(fā)現(xiàn)蘊(yùn)含在軌跡數(shù)據(jù)中的伴隨模式;SHEIN等[7]提出了一種微聚類算法用于發(fā)現(xiàn)軌跡數(shù)據(jù)流中的松散伴隨模式.然而,軌跡相似度算法需要事先指定待比對的對象,才能通過其軌跡數(shù)據(jù)找出與其存在伴隨關(guān)系的其他對象.若挖掘數(shù)據(jù)中所有的伴隨模式,軌跡相似度算法會耗費大量的時間.

關(guān)聯(lián)規(guī)則算法一般用于挖掘頻繁伴隨模式,相比軌跡相似度算法,關(guān)聯(lián)規(guī)則算法能夠高效地挖掘出數(shù)據(jù)中所有的伴隨模式[8],它將一定時間范圍內(nèi)一起出現(xiàn)的對象集作為事務(wù)集(伴隨數(shù)據(jù)集),通過所設(shè)定的支持度閾值,挖掘出存在伴隨關(guān)系的頻繁項集.常用的頻繁伴隨模式挖掘方法主要是利用滑動窗口或時間切片方法,來劃定伴隨數(shù)據(jù)集,再運用關(guān)聯(lián)規(guī)則算法挖掘出伴隨模式.王齊童等[9]提出了基于時空數(shù)據(jù)的滑動窗口方法用于劃定伴隨數(shù)據(jù)集,并將剪枝算法、貪心算法與Apriori 技術(shù)相結(jié)合,對移動對象的伴隨模式進(jìn)行挖掘;朱美玲等[10]提出了基于車牌識別流數(shù)據(jù)的PlatoonFinder算法來挖掘伴隨車輛,其中利用了滑動窗口劃定伴隨數(shù)據(jù)集;Liu等[11]采用滑動窗口劃定伴隨數(shù)據(jù)集,并利用改進(jìn)SeqStream算法挖掘伴隨車輛;陳瑤等[12]通過時間切片劃定伴隨數(shù)據(jù)集,并基于Spark計算框架的矩陣剪枝頻繁項集挖掘算法發(fā)現(xiàn)伴隨車輛;劉惠惠等[8]通過時間切片劃定伴隨數(shù)據(jù)集,基于Spark計算框架的FP-Growth算法挖掘伴隨車輛.此外,還有學(xué)者采用聚類算法劃定伴隨數(shù)據(jù)集.YAO等[13]采用DBSCAN算法對軌跡數(shù)據(jù)進(jìn)行聚類,然后利用FP-Growth算法挖掘蘊(yùn)含在軌跡數(shù)據(jù)的伴隨模式;YAO等[14]采用HDBSCAN算法,解決了傳統(tǒng)DBSCAN算法在處理密度不同的聚類問題時遇到的困難,再利用FP-Growth算法挖掘伴隨模式.雖然上述學(xué)者在伴隨模式挖掘方面取得了一些成果,但是現(xiàn)有劃定伴隨數(shù)據(jù)集的方法主要應(yīng)用于軌跡數(shù)據(jù),并非事務(wù)日志數(shù)據(jù);而且上述成果尚未利用伴隨模式挖掘結(jié)果生成關(guān)聯(lián)規(guī)則,無法進(jìn)一步獲得和分析對象間潛在的關(guān)聯(lián)關(guān)系.

事務(wù)日志是一種大規(guī)模的歷史靜態(tài)數(shù)據(jù),由于傳統(tǒng)串行的滑動窗口算法和FP-Growth算法只能調(diào)用單一線程進(jìn)行計算,無法充分利用多核配置的加速性能,隨著數(shù)據(jù)規(guī)模的擴(kuò)張,會導(dǎo)致挖掘伴隨模式的時間急劇增加.目前計算機(jī)技術(shù)的快速發(fā)展促進(jìn)了多核處理器與并行計算框架的發(fā)展與應(yīng)用,然而現(xiàn)有的Hadoop和Spark并行計算框架不夠輕量,難以對串行的算法進(jìn)行并行化改造,不利于應(yīng)用的遷移和擴(kuò)展[15],并且通信成本、負(fù)載平衡和I/O操作會導(dǎo)致運維費用較高[16].為此,本文在共享內(nèi)存的多核平臺上,提出一種基于事務(wù)日志的伴隨模式挖掘框架,該框架以Java的并發(fā)性和Fork/Join并行計算技術(shù)為基礎(chǔ),包括劃定伴隨數(shù)據(jù)集、頻繁項集挖掘和關(guān)聯(lián)規(guī)則挖掘3部分.在劃定伴隨數(shù)據(jù)集部分,本文提出一種多核并行滑動窗口(parallel sliding window,PSW)算法,通過對事務(wù)日志數(shù)據(jù)庫進(jìn)行劃分,能夠并行地在各個子數(shù)據(jù)庫上劃定子伴隨數(shù)據(jù)集.在頻繁項集挖掘部分,本文提出一種多核并行FP-Growth(parallel FP-Growth,PFP-Growth)算法,能夠并行地在各個子伴隨數(shù)據(jù)集上構(gòu)造FP樹,從而縮短挖掘頻繁項集的時間;在關(guān)聯(lián)規(guī)則挖掘部分,本文利用支持度、置信度和提升度3個參數(shù)來挖掘伴隨模式中的關(guān)聯(lián)規(guī)則,目的是通過這些關(guān)聯(lián)規(guī)則分析出對象間的關(guān)聯(lián)關(guān)系和規(guī)律性.基于門禁刷卡數(shù)據(jù)的實驗結(jié)果表明,相比傳統(tǒng)算法,本文所提出的框架能夠挖掘出更多的伴隨模式,同時挖掘效率較高.

2 伴隨模式挖掘框架

2.1 框架結(jié)構(gòu)及問題描述

伴隨模式挖掘框架結(jié)構(gòu)如圖1所示,由劃定伴隨數(shù)據(jù)集、頻繁項集挖掘、關(guān)聯(lián)規(guī)則挖掘3部分組成.

圖1 伴隨模式挖掘框架圖Fig.1 Schematic illustration of the proposed co-occurrence pattern mining frame

在劃定伴隨數(shù)據(jù)集部分,本文首先將事務(wù)日志數(shù)據(jù)庫D劃分為n個子數(shù)據(jù)庫D1,D2,…,Di,…,Dn(1≤i≤n).D中共包含h條事務(wù)日志記錄,其中第j條事務(wù)日志記錄可表示為:

xj={oj,lj,tj}(1≤j≤h)

(1)

式中,oj表示xj所記錄的對象;lj表示oj所經(jīng)過的監(jiān)測點;tj表示oj經(jīng)過lj的時間.

給定最大時間閾值λ,?xu,xv∈Di,1≤u≤h,1≤v≤h,u≠v,若xu={ou,lu,tu},xv={ov,lv,tv}同時滿足ou≠ov、lu=lv、|tu-tv|≤λ這3個條件,則稱xu與xv在最大時間閾值內(nèi)共同出現(xiàn)一次,即兩者可能存在共現(xiàn)關(guān)系.

在此基礎(chǔ)上,本文采用將Fork/Join并行技術(shù)與滑動窗口相結(jié)合的PSW算法,以高效地從D中劃定出伴隨數(shù)據(jù)集S:

S={S1,S2,…,Si,…,Sn}

(2)

式中,Si表示從Di中劃定出的子伴隨數(shù)據(jù)集,它由若干個存在共現(xiàn)關(guān)系的項集(item set)組成,項集IS可表示為:

IS={item1,item2,itemp,…,itemr} (2≤p≤r)

(3)

式中,itemp表示由地點lp與對象op組成的項(item),該項在Di中有唯一的事務(wù)日志記錄xp={op,lp,tp}與之對應(yīng);r表示IS共包含項的個數(shù).IS可重新表示為:

IS={l1∧o1,l2∧o2,lp∧op,…,lr∧or}
(l1=l2=lp=…=lr,o1≠o2≠op≠…≠or)

(4)

其中,?itemp∈IS(p≠1),itemp={lp∧op}需滿足|t1-tp|≤λ的條件.

在頻繁項集挖掘部分,本文提出基于Fork/Join并行框架的PFP-Growth算法,該算法能夠并行地從S中挖掘出局部頻繁項集T:

T={T1,T2,…,Ti,…,Tn}

(5)

式中,Ti表示從Si中挖掘出的子局部頻繁項集,它由若干個頻繁項集(frequent itemset)組成.頻繁項集是指Si中頻繁出現(xiàn)的項集,其結(jié)構(gòu)與IS的結(jié)構(gòu)類似.若IS?Si,IS≠?并且IS滿足式(6)的條件時,則將IS稱為頻繁項集.

support(IS)≥minSup

(6)

式中,support(IS)表示IS的支持度,即IS在Si中出現(xiàn)的頻次,minSup表示絕對最小支持度閾值.

然后,本文通過合并Ti,得到全局頻繁項集Tglobal,即所有的頻繁k-項集.這些頻繁k-項集,既滿足伴隨模式對兩者以上的對象,在最大時間閾值內(nèi)一起出現(xiàn)在同一地點的要求,又滿足出現(xiàn)在伴隨數(shù)據(jù)集S中的支持度不小于絕對最小支持度的條件,因此本文認(rèn)為這些項集是伴隨模式.

在關(guān)聯(lián)規(guī)則挖掘部分,本文采用支持度、置信度和提升度3個參數(shù),描述從Tglobal中挖掘的關(guān)聯(lián)規(guī)則的有效性.關(guān)聯(lián)規(guī)則集V由若干關(guān)聯(lián)規(guī)則R組成,R可表示為:

R:A?B

(7)

式中,A表示規(guī)則的前件,B表示規(guī)則的后件,且A?IS,B?IS,A∩B=?,規(guī)則R表示當(dāng)A中的對象出現(xiàn)時,B中的對象也將隨之出現(xiàn),有助于用戶發(fā)現(xiàn)和分析蘊(yùn)含在伴隨模式中對象間潛在的關(guān)聯(lián)關(guān)系.

2.2 Fork/Join并行技術(shù)

Fork/Join框架是Java提供的一個用于并行執(zhí)行任務(wù)的輕量級框架,能夠充分利用多核CPU性能,提高程序的運行效率.該框架便于學(xué)習(xí)和實現(xiàn),可以簡化開發(fā)人員編寫并行程序的工作[17].

Fork/Join采用分治思想[18],通過遞歸分割大規(guī)模復(fù)雜的父任務(wù),形成多個小規(guī)模簡單的子任務(wù);然后把各個子任務(wù)分配到不同的CPU線程中開始并行計算;最后合并所有子任務(wù)的執(zhí)行結(jié)果,得到最終的任務(wù)結(jié)果.Fork/Join可以根據(jù)問題規(guī)模的閾值來控制子任務(wù)的計算規(guī)模,采用線程池對工作線程進(jìn)行統(tǒng)一管理,避免因線程的多次創(chuàng)建和關(guān)閉造成資源被不斷消耗的問題.圖2為Fork/Join 框架并行計算原理.

圖2 Fork/Join 框架并行計算原理Fig.2 Principles of Fork/Join parallel computing

工作竊取算法是Fork/Join框架中一種用來實現(xiàn)負(fù)載均衡、提高運算性能的方法,其實際上是一種工作任務(wù)的調(diào)度方法.它的基本思想是當(dāng)一個線程把自身任務(wù)隊列中全部任務(wù)執(zhí)行完畢后,該線程會從其他未執(zhí)行完畢的線程任務(wù)隊列中竊取任務(wù)執(zhí)行,避免線程處于閑置狀態(tài),從而能夠保證負(fù)載均衡,提高CPU的利用率,減少程序的處理時間.

本文基于Fork/Join并行技術(shù),采用Java語言編程實現(xiàn)了PSW和PFP-Growth算法,偽代碼如下:

1.public class ParallelTask extends RecursiveAction{ //繼承RecursiveAction類

2. @Override

3. protected void compute(){

4. if(end-start<=Threshold){//如果問題規(guī)模小于閾值

5. ComputePswPfp(start,end);}//執(zhí)行子任務(wù)

6. else{

7. int pivot =(start + end)/2;//對半分解父任務(wù)

8. ParallelTask task1 = new ParallelTask(start,pivot,Threshold);

9. ParallelTask task2 = new ParallelTask(pivot,end,Threshold);

10. invokeAll(task1,task2);}}//子任務(wù)遞歸

11. public void ComputePswPfp(start,end){

12. for(int i = start;i <= end;i++){//i表示第i個子數(shù)據(jù)庫

13. PSW(i);//從Di中劃定子伴隨數(shù)據(jù)集

14. PFP_Growth(i);}}//從Si中挖掘子頻繁項集

15. public static void main(){

16. int n = 子數(shù)據(jù)庫的總數(shù);

17. ParallelTask task = new ParallelTask(1,n,Threshold);

18. int thread = Runtime.getRuntime().availableProcessors();

19. ForkJoinPool pool = new ForkJoinPool(thread);//創(chuàng)建ForkJoin線程池

20. pool.invoke(task);//并行執(zhí)行問題

21. 匯總各子任務(wù)的計算結(jié)果;}}

為實現(xiàn)上述算法的并行,需要對Fork/Join框架進(jìn)行重構(gòu),建立可以被Fork/Join框架執(zhí)行的任務(wù)類ParallelTask,該類通過繼承Fork/Join應(yīng)用接口類java.util.concurrent.RecursiveAction得到.在ParallelTask類中,通過重寫compute()方法,可實現(xiàn)對各個子任務(wù)的計算.main()方法表示程序的主函數(shù),用于運行PSW算法和PFP-Growth算法.

在compute()方法中,首先需要判斷事務(wù)數(shù)據(jù)庫的規(guī)模是否小于閾值,本文用start與end的差值(1≤start≤n,1≤end≤n,start≠end)來表示事務(wù)日志數(shù)據(jù)庫的規(guī)模,用Threshold來表示閾值.Threshold的設(shè)定是決定Fork/Join框架執(zhí)行時間的關(guān)鍵因素,其大小需要根據(jù)經(jīng)驗或?qū)嶒灧治鰜碓O(shè)定[19],本文將Threshold設(shè)定為1.如果差值小于等于閾值,則執(zhí)行子任務(wù),即執(zhí)行ComputePswPfp方法;如果差值大于閾值,則對任務(wù)進(jìn)行第一次分解.第一次分解完成后,程序會再次進(jìn)行判定,如果start與end的差值仍大于閾值,則利用invokeAll()方法對分解后的任務(wù)進(jìn)行遞歸分解,直到滿足條件為止.

2.3 劃定伴隨數(shù)據(jù)集

本文采用滑動窗口掃描事務(wù)日志數(shù)據(jù)庫以劃定出伴隨數(shù)據(jù)集,其中伴隨數(shù)據(jù)集由滿足共現(xiàn)關(guān)系的項集組成.

2.3.1 滑動窗口

由于事務(wù)日志并非實質(zhì)上的事務(wù)數(shù)據(jù),本文不能直接將其作為關(guān)聯(lián)規(guī)則挖掘算法的輸入,需要將事務(wù)日志數(shù)據(jù)轉(zhuǎn)換為伴隨數(shù)據(jù)集.考慮到事務(wù)日志是按照時間順序?qū)?shù)據(jù)進(jìn)行記錄,此處適合采用滑動窗口[20](sliding window,SW)找出所有可能存在共現(xiàn)關(guān)系的項集,實現(xiàn)伴隨數(shù)據(jù)集的劃定.

滑動窗口SW可由m個連續(xù)的基本窗口組成,SW可表示為:

SW={SW1,…,SWd,…,SWm}(1≤d≤m)

(8)

式中,SWd可表示為:

SWd={x1,…,xs,…,xw}(1≤s≤w)

(9)

式中,w表示滑動窗口的寬度.

本文將SWd作為一個包含了w條事務(wù)日志記錄的隊列,隊列的長度固定為w.通過將SWd向前滑動一條事務(wù)日志記錄,同時將這條新記錄放入隊尾,并扔掉原來位于隊首的記錄,可得到SWd+1(d+1≤m).

SW算法的計算對象不再是當(dāng)前的整個事務(wù)日志數(shù)據(jù)庫,而是事務(wù)日志數(shù)據(jù)庫的子集,因此可以在每個SWd內(nèi)判斷事務(wù)日志記錄之間是否存在共現(xiàn)關(guān)系,以提高劃定伴隨數(shù)據(jù)集的效率,并減少所需的內(nèi)存.

2.3.2 PSW算法

本文對串行SW算法進(jìn)行了改進(jìn),所提出的PSW算法采用基于分治策略的Fork/Join并行技術(shù),能夠并行地劃定Di上的子伴隨數(shù)據(jù)集Si,以解決串行SW算法對事務(wù)日志這種大規(guī)模的歷史靜態(tài)數(shù)據(jù)處理效率低的問題.

在執(zhí)行PSW算法前,本文需要先對事務(wù)日志數(shù)據(jù)庫進(jìn)行劃分,得到n個具有一定規(guī)模的子數(shù)據(jù)庫Di.然而,將事務(wù)日志數(shù)據(jù)庫劃分為若干個不相交的子數(shù)據(jù)庫,可能會造成各子數(shù)據(jù)庫失去與其相鄰子數(shù)據(jù)庫的聯(lián)系,從而使計算結(jié)果與不采用數(shù)據(jù)庫劃分的串行SW算法不同.因此,本文在子數(shù)據(jù)庫最后一條事務(wù)日志記錄的時間上,額外增加時間長度為最大時間閾值的數(shù)據(jù),從而為每個子數(shù)據(jù)庫增加了冗余數(shù)據(jù)空間,以保留不同子數(shù)據(jù)庫之間的關(guān)聯(lián)性[21].

PSW算法具體流程如下:

1)首先遍歷D中的Di,利用哈希映射(HashMap)中鍵的唯一性,將出現(xiàn)在相同地點的事務(wù)日志記錄分為一組,從而減少程序的冗余計算.本文將Di的分組數(shù)據(jù)稱為dMap,其鍵值對(key-value)中的key存儲地點,value存儲所有出現(xiàn)在該地點的事務(wù)日志記錄.

2)然后,本文采用滑動窗口處理dMap,在每個基本窗口SWd中,判斷位于隊首的事務(wù)日志記錄與隊列中其他記錄是否滿足時間差TD小于等于λ的條件,同時判斷兩者的對象是否相同.若TD=|t1-ts|≤λ且o1≠os,則根據(jù)式(4)將這些事務(wù)日志記錄轉(zhuǎn)換為一個項集ISd;若TD=|t1-ts|>λ且o1≠os,則中斷后續(xù)判斷,因為隊列中的記錄是按照時間順序排列的,顯然隊列中剩余的記錄均不滿足TD≤λ的條件.

3)最后,為避免當(dāng)前窗口SWd產(chǎn)生的ISd是上一個窗口SWd -1產(chǎn)生的ISd-1的子集,算法需要判斷ISd-1是否包含ISd,以及ISd包含項的個數(shù)r是否大于1.若ISd?ISd-1且r>1,則將ISd存入子伴隨數(shù)據(jù)集Si中.

基于Java編程語言實現(xiàn)的 PSW算法流程如算法1所示.

算法1.PSW算法

輸入:數(shù)據(jù)數(shù)據(jù)庫D,滑動窗口寬度w,最大時間閾值λ

輸出:伴隨數(shù)據(jù)集S

1.for eachDiinD//開啟多線程并行計算

2. 初始化Si

3.dMap=groupByPlace(Di)//根據(jù)地點對Di中的數(shù)據(jù)進(jìn)行分組

4. for eachdListindMap.values()

5.start=0,end=dList.size(),初始tempSWList//tempSWList存儲項集ISd-1

6. while(start!=end)

7. 初始化SWList//SWList存儲項集ISd

8.SWList.add(dList.get(start).getPlace()+dList.get(start).getObject())

9. for(right=start+1;right

10.TD=dList.get(right).getTD(dList.get(start))//TD表示兩條記錄間的時間差

11. if(TD≤λ)

12.SWList.add(dList.get(right).getPlace()+dList.get(right).getObject())

13. else

14. break

15. if(SWList.size()>1&&tempSWList.containsAll(SWList))

16.Si.add(SWList)

17.tempSWList=SWList

18.start++,w++

19.S.add(Si)

20.returnS

在算法1中,第1行開啟基于Fork/Join框架的多線程并行計算,并行地對每個Di劃定伴隨數(shù)據(jù)集;groupByPlace()函數(shù)用于根據(jù)地點對Di進(jìn)行分組,并將分組數(shù)據(jù)存入dMap中;getPlace()和getObject()方法用于獲取當(dāng)前記錄的地點和對象.

對于參數(shù)w的確定,可采用簡單的搜索法,先從一個較小的w(例如w=2)開始執(zhí)行PSW算法,然后逐漸增大w,記錄S的變化,直到S的大小不再改變,此時的w為最佳的w.因為這個w能夠使滑動窗口包含較少數(shù)量的事務(wù)日志記錄,同時使滑動窗口劃定出的S盡可能大.至于參數(shù)λ,需要用戶根據(jù)業(yè)務(wù)需求自行確定,一般在1～5min的范圍內(nèi).

為了更好地描述PSW算法,本文以圖1中劃定伴隨數(shù)據(jù)集部分為實例來說明該算法.在該實例中,w=5,λ=5min.由于Di中所有記錄的地點均為La,本文省略了PSW算法中分組的步驟.已知SW1={x1,x2,x3,x4,x5},雖然x1,x2,x3,x4,x5所記錄的對象各不相同,但只有x1與x2、x1與x3滿足TD≤5min的條件.因此,根據(jù)式(4)得到SW1產(chǎn)生的項集IS1={LaΛOa,LaΛOb,LaΛOc}.同理,可得到SW2產(chǎn)生的IS2={LaΛOb,LaΛOc},SW3產(chǎn)生的IS3={LaΛOc,LaΛOd,LaΛOe}.最后,由于IS2?IS3而IS2?IS1,Si只存儲了IS1和IS3.

2.4 頻繁項集挖掘

頻繁項集挖掘是指在伴隨數(shù)據(jù)集中尋找滿足最小支持度閾值的所有項集,目的是發(fā)現(xiàn)在給定時間段內(nèi)頻繁的共同出現(xiàn)在同一地點的對象.

2.4.1 傳統(tǒng)FP-Growth算法

目前常用的關(guān)聯(lián)規(guī)則算法有Apriori[22]和FP-Growth[23]算法.Apriori算法需要多次掃描事務(wù)集,利用候選頻繁項集來產(chǎn)生頻繁項集,具有I/O負(fù)載較高和算法效率較低的缺點.FP-Growth算法只需要掃描事務(wù)集兩次,通過樹形結(jié)構(gòu)產(chǎn)生頻繁項集,與Apriori算法相比,能夠提高挖掘頻繁項集的效率.

傳統(tǒng)FP-Growth算法挖掘頻繁項集的方法為掃描伴隨數(shù)據(jù)集,獲得每個項的頻次,去除不滿足最小支持度的項,將剩余項存入項頭表,并按照支持度的大小將各項按照降序排列(次序記為Seq);然后再次掃描伴隨數(shù)據(jù)集,按次序Seq組成相應(yīng)的項集以將其插入到FP樹中,并構(gòu)建節(jié)點鏈表以連接項頭表與FP樹;最后,對每一個頻繁項目對應(yīng)的條件模式基進(jìn)行挖掘,從而得到所有能夠滿足最小支持度約束的頻繁k-項集[24].其流程如圖1中頻繁項集挖掘部分所示.

然而,當(dāng)對大型的伴隨數(shù)據(jù)集進(jìn)行挖掘時,FP-Growth算法會顯著增加時間和空間的消耗,甚至還有可能使內(nèi)存無法完全容納一個完整的FP樹.另外,當(dāng)設(shè)定較小的支持度閾值時,即使數(shù)據(jù)庫規(guī)模不大,FP-Growth算法仍需要遞歸地產(chǎn)生大量的條件FP樹,使得算法運行速度較慢,占用內(nèi)存較大.

2.4.2 PFP-Growth算法

文獻(xiàn)[25]從理論上證明,對每個子事務(wù)數(shù)據(jù)庫構(gòu)造FP樹,再通過合并局部頻繁項集,能夠得到全局頻繁項集.基于此,本文采用基于Fork/Join框架的PFP-Growth算法,以解決當(dāng)事務(wù)數(shù)據(jù)庫規(guī)模較大或支持度閾值較小時,傳統(tǒng)的串行FP-Growth算法時空效率不高的問題.

PFP-Growth算法具體流程如下:

1)首先通過式(10)計算出子伴隨數(shù)據(jù)集Si上的局部的絕對最小支持度minSupi.

(10)

式中,minSup表示伴隨數(shù)據(jù)集S上的全局的絕對最小支持度;符號‖·‖用于獲取相應(yīng)數(shù)據(jù)集中含有的項集總數(shù).

2)在求取minSupi后,PFP-Growth算法開始在各個Si上構(gòu)造FP樹,以挖掘出子局部頻繁項集Ti.然后,算法開始遍歷Ti中的頻繁項集IS,并判斷全局頻繁項集Tglobal中是否已經(jīng)存在與IS相同的頻繁項集ISexist,若存在,則更新ISexist的支持度(ISexist在S中出現(xiàn)的頻次),ISexist更新后的支持度等于ISexist未更新前的支持度與IS的支持度(IS在Si中出現(xiàn)的頻次)相加;若不存在,則將IS存入Tglobal中,同時記錄IS的支持度.

3)當(dāng)并行計算完成后,PFP-Growth算法需要遍歷Tglobal中的項集ISglobal,若ISglobal的支持度低于全局的絕對最小支持度,即support(ISglobal)

基于 Java編程語言實現(xiàn)的PFP-Growth算法流程如算法2所示.

算法2.PFP-Growth算法

輸入:伴隨數(shù)據(jù)集S,最小支持度minSup

輸出:全局頻繁項集Tglobal

1.for eachSiinS//開啟多線程并行計算

2. 根據(jù)式(10)計算出minSupi

3.Ti=FP_Growth(Si,minSupi)

4. for eachISinTi

5.countIS=Ti.get(IS)//countIS表示IS的支持度

6. if(Tglobal.hasExist(IS)==false)

7.Tglobal.put(IS,countIS)//將IS與countIS存入Tglobal的鍵值對中

8. else

9.countIS=countIS+Tglobal.get(IS)

10.Tglobal.put(IS,countIS)

11.for eachISglobalinTglobal

12. if(Tglobal.get(ISglobal)

13.Tglobal.remove(ISglobal)

14.returnTglobal

算法從第1行到第10行利用Fork/Join技術(shù)并行地對每個Si進(jìn)行頻繁項集挖掘.其中FP_Growth(Si,minSupi)函數(shù)表示根據(jù)minSupi,對Si調(diào)用FP-Growth算法;Ti和Tglobal采用Hash結(jié)構(gòu)存儲,兩者的鍵值對相同,key用于存儲頻繁項集,value用于存儲頻繁項集的支持度;Tglobal.hasExist(IS)用于判斷Tglobal中是否已經(jīng)存在與IS相同的項集.

2.5 關(guān)聯(lián)規(guī)則挖掘

關(guān)聯(lián)規(guī)則是一個非監(jiān)督的學(xué)習(xí)過程,數(shù)據(jù)并不被特別標(biāo)識,學(xué)習(xí)模型是為了推斷出數(shù)據(jù)的一些內(nèi)在結(jié)構(gòu).對于關(guān)聯(lián)規(guī)則而言,判斷其產(chǎn)生的規(guī)則是否有效,一般看它的支持度、置信度是否滿足最小支持度、最小置信度閾值,如果大于閾值則為有用的、正確的規(guī)則,否則為無用的規(guī)則.除支持度和置信度指標(biāo)之外,為去除具有誤導(dǎo)性的冗余規(guī)則,本文引入提升度來描述規(guī)則的相關(guān)性,以有效發(fā)現(xiàn)伴隨式所蘊(yùn)含的內(nèi)在規(guī)律,提煉對象之間的內(nèi)在聯(lián)系.

2.5.1 支持度指標(biāo)

支持度表示項集在伴隨數(shù)據(jù)集中的頻繁程度,關(guān)聯(lián)規(guī)則A?B的支持度定義為:

(11)

式中,count(A∪B)表示由A與B組成的項集在伴隨數(shù)據(jù)集中出現(xiàn)的頻次.值得一提的是,關(guān)聯(lián)規(guī)則中的支持度是指相對支持度而非絕對支持度,相對支持度表示絕對支持度與伴隨數(shù)據(jù)集中項集總數(shù)的比值,絕對支持度表示項集在伴隨數(shù)據(jù)集中出現(xiàn)的頻次.

2.5.2 置信度指標(biāo)

置信度表示出現(xiàn)規(guī)則前件后再出現(xiàn)規(guī)則后件的條件概率,關(guān)聯(lián)規(guī)則A?B的置信度定義為:

(12)

式中,count(A)表示A在伴隨數(shù)據(jù)集中出現(xiàn)的頻次.置信度越大說明出現(xiàn)A后再出現(xiàn)B的可能性越大.

2.5.3 提升度指標(biāo)

提升度表示先出現(xiàn)規(guī)則前件對出現(xiàn)規(guī)則后件的概率的提升作用,關(guān)聯(lián)規(guī)則A?B的提升度定義為:

(13)

其中,如果lift>1,表示A和B為正相關(guān)性;如果lift=1,表示A與B無相關(guān)性;如果lift<1,表示A和B為負(fù)相關(guān)性.

2.5.4 產(chǎn)生規(guī)則

本文將Tglobal中所有的頻繁k-項集(k=2,3,…)分解成由子項集組成的前件和后件.然后根據(jù)式(11)、式(12)、式(13)計算由前件和后件組成的規(guī)則的支持度、置信度、提升度.若規(guī)則滿足支持度閾值、置信度閾值、提升度閾值,則按文獻(xiàn)[26]提出的用于關(guān)聯(lián)規(guī)則可視化的數(shù)據(jù)結(jié)構(gòu),將規(guī)則存入關(guān)聯(lián)規(guī)則集V中,V可表示為:

V={{A1,B1,θ1},{A2,B2,θ2},…,{Az,Bz,θz}}

(14)

式中θ表示規(guī)則的度量(例如規(guī)則的支持度、置信度、提升度),z表示規(guī)則的總數(shù).

基于Java編程語言實現(xiàn)的產(chǎn)生規(guī)則的算法流程如算法3所示.

算法3.產(chǎn)生規(guī)則的算法

輸入:支持度閾值minSupport,置信度閾值minConfidence,提升度閾值minLift,全局頻繁項集Tglobal

輸出:關(guān)聯(lián)規(guī)則集V

1.for eachISinTglobal

2. if(IS.size()>1)//如果IS的項數(shù)大于1

3.countA∪B=Tglobal.get(IS)

4. for(i=1;i

5.combination=getCombi(IS,i)

6. for eachAincombination

7.B=getleft(IS,A)

8.countA=Tglobal.get(A)

9. 根據(jù)式(11)計算規(guī)則的支持度

10. 根據(jù)式(12)計算規(guī)則的置信度

11. 根據(jù)式(13)計算規(guī)則的提升度

12. if(support>=minSupport&& confidence>=minConfiedence&& lift>=minLift)

13.V.add(A,B,support,confidence,lift)

14.returnV

算法中g(shù)etCombi(IS,i)函數(shù)用于從IS中獲取所有項數(shù)為i的子項集組合;getleft(IS,A)函數(shù)表示排除IS中的A后,所留下的子項集.關(guān)于生成規(guī)則的參數(shù)一般可以通過經(jīng)驗與用戶的業(yè)務(wù)需求來確定,還可通過關(guān)聯(lián)規(guī)則的可視化結(jié)果來確定.

3 實驗研究

3.1 實驗配置

本文基于某城市某社區(qū)門禁刷卡數(shù)據(jù)進(jìn)行實驗,以2020年4月-9月全天采集到的門禁刷卡數(shù)據(jù)作為數(shù)據(jù)集,數(shù)據(jù)集共包含12萬余條事務(wù)日志記錄,涉及930位對象,14個地點,實驗前已對數(shù)據(jù)進(jìn)行了清洗和隱私處理.實驗在單臺計算機(jī)上進(jìn)行,處理器為Intel Core i7-6700 3.40GHz(4核8線程),內(nèi)存大小為8GB,操作系統(tǒng)為64位Windows10,JDK版本為1.8,采用MySQL數(shù)據(jù)庫存儲事務(wù)日志記錄.

3.2 實驗內(nèi)容和結(jié)果分析

3.2.1 數(shù)據(jù)規(guī)模和并行度對算法性能的影響

本文利用Fork/Join技術(shù)對基于密度的DBSCAN算法[27]、時間切片[12]、Apriori進(jìn)行了并行化改造,并將改進(jìn)算法分別命名為PDBSCAN(parallel DBSCAN)、PTS(parallel time slice)和PApriori(parallel Apriori).

為了驗證本文所提出算法的時間復(fù)雜度,本文在不同數(shù)據(jù)規(guī)模下,使用PDBSCAN、PTS、PSW算法對事務(wù)日志數(shù)據(jù)進(jìn)行劃定伴隨數(shù)據(jù)集實驗,以及采用PApriori算法、PFP-Growth算法對伴隨數(shù)據(jù)集進(jìn)行頻繁項集挖掘?qū)嶒?實驗結(jié)果如圖3所示.在未標(biāo)明參數(shù)的情況下,默認(rèn)各算法的參數(shù)如表1所示.本文使用時間差來度量PDBSCAN算法中兩個對象之間的距離(相似性),因此表中PDBSCAN算法的鄰域半徑單位為分鐘.

表1 各算法的參數(shù)設(shè)置Table 1 Parameter setting of each algorithm

從圖3可知,PDBSCAN算法的運行時間高于其他算法,這是因為PDBSCAN算法在聚類過程中需要訪問原始數(shù)據(jù)中的所有對象,并且有些對象可能需要重復(fù)訪問多次,導(dǎo)致算法的計算量較大.其中當(dāng)事務(wù)日志記錄數(shù)為107186條時,PSW算法比PDBSCAN算法節(jié)省了35.5%的時間,與PTS算法相比兩者運算時間較為接近.因此PSW算法適合處理海量的事務(wù)日志數(shù)據(jù).

從圖3還可發(fā)現(xiàn),PApriori算法的運行時間遠(yuǎn)高于PFP-Growth算法,這是因為在頻繁k-1-項集生成候選頻繁k-項集時,需要進(jìn)行連接與剪枝操作,以及在驗證候選頻繁k-項集時,需要對整個事務(wù)數(shù)據(jù)庫進(jìn)行掃描,增加了算法的計算量和運行時間.其中當(dāng)事務(wù)日志記錄數(shù)為107186條時,PFP-Growth算法比PApriori算法節(jié)省了98.9%的時間.

圖3 不同數(shù)據(jù)集下的算法運行時間Fig.3 Algorithm executing time under different data sizes

綜上所述,相較于傳統(tǒng)算法,本文所提出的融合了數(shù)據(jù)庫劃分和Fork/Join并行計算技術(shù)的伴隨模式挖掘框架能夠有效減少算法的計算量,提高挖掘伴隨模式的運行效率.

為了探究并行度對本文所提出算法的影響,本文對算法在同一臺計算機(jī)上的CPU可運行線程數(shù)進(jìn)行了限制,以測試在同一記錄數(shù)(記錄數(shù)為107186條)、不同并行度下算法運行時間,實驗結(jié)果如圖4所示.由圖4可知,隨著線程數(shù)的增加,PSW算法、PFP-Growth算法的運行時間均不斷降低.因此對于計算規(guī)模較大的任務(wù),較多的可運行線程數(shù)將可以更加顯著地提高本文所提出的改進(jìn)算法的效率.

圖4 不同并行度下的算法運行時間Fig.4 Algorithm executing time under different parallelism degrees

3.2.2 最大時間閾值和支持度對算法性能的影響

本文通過調(diào)整最大時間閾值和全局最小支持度這兩個參數(shù),使算法能夠發(fā)現(xiàn)不同時間段內(nèi)共同出現(xiàn)在同一地點的對象,以及不同頻繁程度的伴隨模式,從而提高伴隨模式挖掘的靈活性.

如表2和圖5所示,本文統(tǒng)計了不同最大時間閾值對PDBSCAN、PTS、PSW算法運行時間,以及伴隨數(shù)據(jù)集劃定結(jié)果的影響,其中實驗的事務(wù)日志記錄數(shù)為107186條.由表2和圖5可知,隨著最大時間閾值的增加,所有算法生成伴隨數(shù)據(jù)集的數(shù)量均不斷增加,這是因為在較大的時間段內(nèi)可能會有更多的對象出現(xiàn)在同一地點,增加了算法所挖掘出伴隨數(shù)據(jù)集的數(shù)量.此外,在PDBSCAN算法中可能會存在類內(nèi)第一個對象與最后一個對象間時間差大于最大時間閾值λ的情況,使得PDBSCAN算法產(chǎn)生的伴隨數(shù)據(jù)集的數(shù)量較小,這是因為第一個對象和最后一個對象不滿足直接密度可達(dá)的條件.雖然PTS算法均滿足切片內(nèi)第一個對象與最后一個對象間時間差不大于λ,但是出現(xiàn)在某時某地的對象只能屬于一個切片,無法同PSW算法一樣,可以屬于不同的滑動窗口,因此時間切片產(chǎn)生的伴隨數(shù)據(jù)集的數(shù)量不及PSW算法.可見PSW算法能夠更加充分地挖掘出伴隨數(shù)據(jù)集,并縮短所需的挖掘時間.

表2 不同最大時間閾值對算法運行時間的影響Table 2 Effects of different time thresholds on the algorithm executing time

圖5 不同最大時間閾值對伴隨數(shù)據(jù)集的影響Fig.5 Effects of different time thresholds on the CP dataset

如表3和圖6所示,本文統(tǒng)計了不同全局最小支持度對PApriori算法、PFP-Growth算法的運行時間和頻繁項集挖掘結(jié)果的影響,其中輸入數(shù)據(jù)為圖5中PSW算法在最大時間閾值為5min時生成的伴隨數(shù)據(jù)集.由表3和圖6可知,當(dāng)全局最小支持度不斷增加時,各算法的運行時間和頻繁項集的大小不斷減少,這是因為頻繁程度高的伴隨模式比頻繁程度低的伴隨模式更少,造成運行時間和頻繁項集大小減少.此外,在相同的全局最小支持度下,PFP-Growth算法生成頻繁項集的大小不僅與PApriori算法相同,而且運行時間更少.

圖6 不同全局最小支持度對頻繁項集的影響Fig.6 Effects of different global support on the frequent itemsets

表3 不同全局最小支持度對算法運行時間的影響Table 3 Effects of different global support on the algorithm executing time

3.3 關(guān)聯(lián)規(guī)則可視化展示

為了幫助用戶直觀地從大量規(guī)則中篩選出有效的強(qiáng)關(guān)聯(lián)規(guī)則,并分析出項與項之間的關(guān)聯(lián)關(guān)系,本文利用SpringBoot技術(shù)設(shè)計了一個基于HTML與Echarts的動態(tài)數(shù)據(jù)顯示前端,使其成為關(guān)聯(lián)規(guī)則挖掘結(jié)果可視化的承載體,關(guān)聯(lián)規(guī)則的散點圖和網(wǎng)圖如圖7和圖8所示.實驗中規(guī)則的支持度閾值設(shè)置為0.0001,置信度閾值設(shè)置為30%,提升度閾值設(shè)置為10,共生成502條規(guī)則.支持度閾值很小的原因是本文頻繁項集在伴隨數(shù)據(jù)集中出現(xiàn)的頻次一般很小.

在圖7中,x軸表示置信度,y軸表示支持度,點的明暗表示規(guī)則的支持度計數(shù),點的大小表示提升度.由圖7可以看出所有規(guī)則在散點圖中的分布,其中支持度和置信度較低,而提升度較高的規(guī)則集中于散點圖的底部,這有助于用戶調(diào)整支持度閾值、置信度閾值和提升度閾值,以篩選出相關(guān)性更高的規(guī)則.

圖7 關(guān)聯(lián)規(guī)則的散點圖Fig.7 Scatterplot of association rules

圖8只截取了關(guān)聯(lián)規(guī)則可視化網(wǎng)圖的一部分,沒有包含所有的關(guān)聯(lián)規(guī)則.圖中圓點表示項,較大的圓形表示規(guī)則,圓形的大小表示規(guī)則的支持度計數(shù),箭頭表示規(guī)則內(nèi)部項與項的關(guān)系.從圖8可以看出不同規(guī)則之間如何共享一個前件,并可發(fā)現(xiàn)哪個前件是網(wǎng)圖的中心,這有利于用戶直觀地發(fā)現(xiàn)規(guī)則中項與項之間一對一、一對多、多對多的關(guān)系.

圖8 關(guān)聯(lián)規(guī)則的網(wǎng)圖Fig.8 Network diagram of association rules

4 總 結(jié)

隨著事務(wù)日志的數(shù)據(jù)規(guī)模不斷擴(kuò)大,傳統(tǒng)基于滑動窗口的伴隨數(shù)據(jù)集劃定方法,以及傳統(tǒng)FP-Growth算法,無法充分利用計算機(jī)的多核性能,導(dǎo)致挖掘伴隨模式的時間急劇增加,為此本文提出基于Fork/Join并行技術(shù)的伴隨模式挖掘框架.該框架包括劃定伴隨數(shù)據(jù)集、頻繁項集挖掘和關(guān)聯(lián)規(guī)則挖掘3部分.首先,本文提出了基于Fork/Join的PSW算法,以并行地從事務(wù)日志數(shù)據(jù)庫中劃定伴隨數(shù)據(jù)集;然后,本文提出了PFP-Growth算法,以并行地在伴隨數(shù)據(jù)集上構(gòu)造FP樹,縮短挖掘頻繁項集的時間;最后,本文利用支持度、置信度和提升度來挖掘伴隨模式中的關(guān)聯(lián)規(guī)則,以進(jìn)一步分析對象間的關(guān)聯(lián)關(guān)系和規(guī)律性.基于門禁刷卡數(shù)據(jù)的實驗結(jié)果表明,相比傳統(tǒng)算法,本文所提出的框架能夠挖掘出更多的伴隨模式,同時挖掘效率較高.

本文所提出的伴隨模式挖掘框架目前僅適用于靜態(tài)歷史的事務(wù)日志數(shù)據(jù).下一步本文將研究如何實時地從事務(wù)日志數(shù)據(jù)流中挖掘伴隨模式,擬利用分布式計算框架對數(shù)據(jù)流進(jìn)行切片,并改進(jìn)滑動窗口和關(guān)聯(lián)規(guī)則算法,以滿足實時挖掘伴隨模式的需求.