王金偉， 吳少華， 瞿治國

南京信息工程大學計算機與軟件學院，南京210044

近年來，隨著大數(shù)據(jù)處理技術的快速發(fā)展，對數(shù)據(jù)流的模式挖掘已成為該領域的一個研究熱點.但是數(shù)據(jù)流的數(shù)據(jù)量大且需要實時處理，使得數(shù)據(jù)流挖掘面臨著一些固有的挑戰(zhàn)[1-3]：1）每個數(shù)據(jù)元素流只能被處理一次；2）盡管數(shù)據(jù)元素是連續(xù)產(chǎn)生的，但是存儲空間是有限的；3）數(shù)據(jù)元素的高速流動需求更加快捷地處理這些數(shù)據(jù)；4）數(shù)據(jù)流挖掘的準確度必須控制在允許的誤差范圍內(nèi).

近年來，研究者已提出多種挖掘數(shù)據(jù)流頻繁項模式的算法.基于數(shù)據(jù)流處理所采用的不同的處理模型，數(shù)據(jù)流頻繁項集挖掘算法大致可以分為3 類：界標窗口模型、滑動窗口模型、衰減窗口模型.在界標窗口模型中，用戶將一個開始時間指定為界標，挖掘范圍是從界標時間到當前時間的所有數(shù)據(jù)；在滑動窗口模型中，窗口大小由用戶指定，并且挖掘范圍是該窗口中最近的事務；在衰減模型中，根據(jù)流動順序對每個事務執(zhí)行遞減授權，先前流動的事務權重較小，而最近流動的事務權重最大.文獻[4]基于界標窗口模型提出了sticky-sampling 和lossy-counting 兩種數(shù)據(jù)流頻繁項集挖掘算法.其中，lossy-counting 算法能夠基于3 個buffertrie-setgen 模型來挖掘離線數(shù)據(jù)流中的頻繁項集.文獻[5]提出的基于前綴樹的DSM-FI（data stream mining for frequent itemsets）算法可以利用界標模型挖掘數(shù)據(jù)流中的頻繁項集.文獻[6]提出的DSM-MFI（data stream mining for maximal frequent itemset）算法能夠挖掘數(shù)據(jù)流中最大的頻繁項集.文獻[7]提出的FDPM（frequent data stream pattern mining）算法使用界標窗口模型來挖掘高速事務數(shù)據(jù)流中的頻繁項集.文獻[8]提出了FP-CDS 算法，該算法使用了界標模式挖掘數(shù)據(jù)流中的頻繁閉項集.

文獻[9]提出了基于時間衰減模型的estDec 算法，該算法主要針對數(shù)據(jù)流中可能的頻繁項集進行挖掘.文獻[10]進一步提出了采用衰減窗口模型的estMax 算法，主要針對數(shù)據(jù)流中信息價值更大的最大頻繁項集進行挖掘.文獻[11]提出了與前綴樹不同的數(shù)據(jù)結構CP-tree來挖掘數(shù)據(jù)流中的頻繁項集.效率對比測試表明，具有CP-tree 結構的esDec 算法遠高于原始的esDec 算法.隨后文獻[12]提出了一種利用滑動窗口挖掘在線數(shù)據(jù)流中的頻繁項集算法.文獻[13]則基于Apriori 算法[14]并結合滑動窗口模型進一步提出了基于事務滑動窗口的頻繁項挖掘（mining frequent itemsets-transaction sliding window,MFI-TransSW）算法，該算法用于挖掘數(shù)據(jù)流中的頻繁項集.文獻[6]提出了基于DSM-MFI 的DSM-RMFI 算法，該算法利用滑動窗口模型來挖掘離線數(shù)據(jù)流中最大的頻繁項集.文獻[15]則利用滑動窗口模型提出了挖掘數(shù)據(jù)流中最大頻繁項集的Max-FISM（maximal-frequent itemset mining）算法，當有新的事務更新進入到窗口時，代表新事務的最大項集被插入到最大集用來參與最大頻繁項集的處理，從而提高了挖掘效率.文獻[16]對數(shù)據(jù)庫進行掃描將其轉換為垂直數(shù)據(jù)格式，然后通過生成位表的形式來優(yōu)化尋找頻繁項集.文獻[17]提出了一種改進的FP-growth 算法及分布式并行實現(xiàn)技術，該算法先對構造的完備模式樹進行剪枝，然后采用頻繁閉模式項集策略減少空間搜索，從而達到提高算法挖掘效率的目的.文獻[18]基于集合枚舉樹排序提出了多最小支持度的頻繁模式挖掘算法，引入集合枚舉樹結構并在枚舉樹中使用多最小支持度來解決挖掘過程中時間和內(nèi)存消耗過大的問題.

文獻[19]首次提出了利用滑動窗口挖掘數(shù)據(jù)流中頻繁閉項集的Moment 算法，在閉枚舉樹（closed enumeration tree,CET）數(shù)據(jù)結構中存儲了4 種節(jié)點：非頻繁節(jié)點、無望節(jié)點、中間節(jié)點和封閉節(jié)點.這4 種節(jié)點類型涵蓋了窗口滑動過程中節(jié)點變化的所有類型，因此CET能夠覆蓋挖掘過程中的所有必要信息.當新的事務被添加到窗口或從當前窗口刪除時，該算法遍歷并更新CET 中的相應部分；當窗口尺寸設置得太小且概念漂移過于頻繁時，項集添加到窗口或從窗口中移除均涉及到許多節(jié)點的更改.文獻[20]使用直接更新（direct update,DIU）數(shù)據(jù)結構來存儲頻繁閉項集的數(shù)據(jù)流.文獻[21]基于CET 數(shù)據(jù)結構提出了NewCET 數(shù)據(jù)結構，只保存可能的頻繁閉項集，并進一步提出了NewMoment 算法，采用位操作技術來高效計算頻繁閉項集的支持度.文獻[22]提出了AFPCFI-DS 算法，根據(jù)每個窗口的FP-tree 檢查頻繁項集的頻繁閉項集[23].當處理新窗口時，該算法首先檢查頭表，然后根據(jù)頭表中項目的變化更新FP-樹.文獻[24]提出的TMmoment 算法挖掘滑動窗口中的頻繁閉項集，并使用TCET 數(shù)據(jù)結構來存儲事務和關閉窗口中的頻繁項集.

本文提出了一種新型的用于挖掘數(shù)據(jù)流頻繁閉項集的CFMoment 算法.該算法使用滑動窗口模型和滑動窗口的特征來挖掘窗口中的事務.實驗結果證明，該算法比Moment 算法更有效，占用內(nèi)存也較小.

1 預備知識

1.1 基礎定義

假設I={i1,i2,··· ,im}是一個項目的集合，事務T=(tid,x1,x2,··· ,xn)，xi ∈I，是一個項集.其中，m表示項目的大小，n表示事務的大小，tid為事務的編號.大小為k的項集稱為k-項集.TDS={T1,T2,··· ,Tn}是一個事務流，其中Tn為最新流入事務，編號為n.當前滑動窗口TSWn-w+1=[Tn-w+1,Tn-w+2,··· ,Tn]，其中w表示窗口的大小，n-w+1 是當前事務滑動窗口（transaction sliding window,TSW）的id 編號.在同一窗口中，top =Tn-w+1表示該窗口中存在的最陳舊事務，即在時間序列中最先進入窗口的事務；bottom=Tn則表示當前窗口所存在的最新事務，即在時間序列中最后進入窗口中的事務.假設下一個流入事務是bottom+1=Tn+1，則用bottom+1 來表示窗口滑動時下一個流入的事務.項集X的支持度表示為sup(X)，即項集X在TSW 中出現(xiàn)的次數(shù).

定義1如果項集X滿足條件sup(X) ≥s，那么稱這個項集X為頻繁項集.其中，s是用戶自定義的最小支持度閾值.

定義2如果不存在具有與項集X相同的支持計數(shù)的超集，則X是一個封閉的項目集.

1.2 問題的提出

給定滑動窗口和最小支持度閾值s，研究如何在數(shù)據(jù)流最近的w個事務中挖掘頻繁閉項集，如圖1所示.

圖1 滑動窗口Figure1 Sliding window

2 CFMoment 算法

為了提高窗口滑動時的挖掘速度，在算法CFMoment 中建立表rela_table 用于存儲頻繁非閉項集與頻繁閉項集之間的關系.此外，算法還采用了基于前綴樹的擴展閉環(huán)枚舉樹（extend closed enumeration tree,ECET）存儲數(shù)據(jù)流中的w個交易的閉合頻繁項目集和相關信息，進一步提高了挖掘效率，降低了內(nèi)存消耗.

2.1 建立ECET樹

ECET 樹是一種基于前綴樹的數(shù)據(jù)結構，由4 部分組成：

1）Fre_item_list：該表主要用于保存挖掘到的當前窗口中所有包含項數(shù)為1 的頻繁1-項集；

2）代表項集的3 種類型節(jié)點：非頻繁項集節(jié)點、頻繁但非閉的項集節(jié)點和頻繁閉項集節(jié)點；

3）Hash_table：該表主要用于檢查所挖掘出的項集是否為閉項集，它保存并映射閉項集為某個具體值.其中，閉項集的頻繁支持度sup、該閉項集的所有事務標識以及tid_sum 聯(lián)合形成該節(jié)點的鍵值；

4）Rela_table：該表主要記錄并保存ECET 樹中頻繁非閉項集與頻繁閉項集之間的相互關系.

與prefix-tree 所用結構類似的是，ECET 樹中的每個節(jié)點ni都代表了一個項集I，而子節(jié)點nj則是在項集I添加新的項集后得到的.

BuildTree 是一個深度優(yōu)先程序，它通過項集的字典順序來處理項集.在算法1 的第1～3行中，如果一個長度為1 的項集很頻繁，則將該項集添加到fre_item_list 中.在第4～6 行中，如果發(fā)現(xiàn)ni因某些字典序列很小而沒有通過封閉檢查，則ni判定為無望節(jié)點，并且節(jié)點ni的項集I和使項集無法通過封閉檢查的項集均存儲在rela_table 中.函數(shù)leftcheck 使用ni的支持以及包括項集I和tid_sum 的事務標識作為散列鍵用于封閉檢查.當一個節(jié)點是頻繁的但沒有無望節(jié)點時，BuildTree 將檢查它的后代節(jié)點，如算法1 中的第8～12 行所示.然后通過程序中的第13～18 行可以判斷節(jié)點ni是中間節(jié)點還是封閉節(jié)點.

算法1BuildTree(nI,w,s)

圖2是BuildTree 運行后建立的ECET 樹.在圖2中，虛線圓圈表示不頻繁的網(wǎng)關節(jié)點，如節(jié)點D.虛線矩形代表無望的網(wǎng)關節(jié)點，如B.圖中的A 和AB 是中間節(jié)點.實線矩形表示封閉的節(jié)點，如ABC 和AC.

圖2 TSW1 的ECET 樹Figure2 TSW1's ECET tree

2.2 窗口滑動過程

由于滑動窗口大小事先確定并保持不變，當窗口滑動時，能夠對ECET 結構產(chǎn)生影響的過程有最舊事務top 的刪除操作以及在窗口中引入最新事務bottom+1 的添加操作.因此，本文的CFMoment 算法充分利用這一特點，通過一致的集合運算高效地更新ECET 在窗口滑動時產(chǎn)生的變化.

算法2Sliding(top,bottom+1)

算法2 給出了Sliding 算法的具體執(zhí)行步驟.從算法中可知，Sliding 算法主要有兩個參數(shù)，即top 和bottom+1，分別表示滑動窗口最舊事務的刪除操作，以及滑動窗口中添加新事務操作.在Sliding 算法的第1～2 行中，如果新添加的項集與待移除的項集相等，則新窗口中的ECET 樹不必進行更新而保持不變.在Sliding 算法的3～4 行中，當top∩bottom+1 ={x1,x2,··· ,xm}（{x1,x2,··· ,xm}可以為空集）時，將top-{x1,x2,··· ,xm}的所有子集加入sup_minus，將bottom+1-{x1,x2,··· ,xm}的所有子集加入sup_plus.當執(zhí)行到Sliding算法第6～9 行時，調(diào)用函數(shù)itemcheck 分別對sup_minus 和sup_plus 中的1-項集進行檢查更新.引入itemcheck 的目的是對1-項集進行基礎頻繁性檢查，從而有效提高對sup_minus和sup_plus 中是否包含對應頻繁和非頻繁性質(zhì)發(fā)生轉換的1-項集的檢查效率.具體來說，如果sup_minus 中某個單項在頻繁次數(shù)減少后由頻繁單項變?yōu)榉穷l繁單項，則原所有包含它的頻繁閉項集都將在新的頻繁閉項集合中被去除；反之則原所有包含它的頻繁閉項集不會因窗口滑動而在新的頻繁閉項集合中發(fā)生變化.同理，如果sup_minus 中某個單項在頻繁次數(shù)增加后由非頻繁單項變?yōu)轭l繁單項，則可能存在新的包含該單項的頻繁閉項集出現(xiàn)；反之則原所有包含它的頻繁閉項集不會因窗口滑動而在新的頻繁閉項集合中發(fā)生變化.在該算法的第10 行中，將sup_minus 和sup_plus 的剩余項集添加到服從字典順序和長度的遞減順序的candidate_set 中.算法的第11～17 行是對candidate_set 的項集進行逐一檢查.如果項集運行函數(shù)supcheck=false，則該項集false 和candidate_set 將作為函數(shù)relacheck 的參數(shù)進行運算.簡單理解如下：supcheck 函數(shù)是為了檢查相應參數(shù)項集是否頻繁，而relacheck 的功能是查找rela_table 中的項集記錄作為參數(shù)，在rela_table 中確定它的類別并以此進行不同的處理，加速找出封閉節(jié)點.relacheck 函數(shù)的偽代碼如下：

算法3relacheck(I,Boolean,SupSet)

2.3 算法示例

為了便于理解本文所提的相關算法，本文結合圖1中所給出的具體示例進一步演示CFMoment 算法的執(zhí)行過程.

根據(jù)圖1可知，窗口TSW1的初始條件為top=T1，而相對應的是bottom+1 代表即將進入滑動窗口的最新事務，即bottom+1 =T5.在這一初始條件下，當窗口進行滑動時，將自動調(diào)用Sliding 算法.此時，因為top=T1=CD 且top+1=T5=CD，即退出窗口的舊事務與加入窗口的新事務相等，則不執(zhí)行算法的更新操作，運行結束.此時窗口從TSW1滑動到TSW2，ECET 不變，TSW2的閉項集與TSW1的閉項集相同.

在窗口TSW2中，top =T2，bottom+1 =T6.當窗口從TSW2滑到TSW3時，調(diào)用Sliding 算法.此時top =T1= AC，bottom+1 = BD.CFMoment 算法的第4～5 行是在sup_minus 中加入項集A、C 和AC，在sup_plus 中加入項集D 和BD.第6～7 行是在sup_minus 中的1-項集調(diào)用itemcheck 函數(shù)，此時A 和C 的頻繁次數(shù)為sup=sup-1，但它們?nèi)匀粷M足頻繁條件且為單個頻繁項集，繼續(xù)存儲在sup_minus 中.第8～9 行是在sup_plus 中的1-項集調(diào)用了函數(shù)itemcheck，運行后sup_plus 中還剩B 和D.將sup_minus 和sup_plus合并形成candidate_set，此時candidate_set={AC,A,B,C,D}.在算法的第11～17 行中，分開執(zhí)行candidate_set 中的所有項目集.因為supercheck(AC)=true，所以對于AC 則執(zhí)行relacheck(AC,true,candidate,set).

當執(zhí)行relacheck(AC,true,candidate,set)時，由于ABC 是包含AC 的超集，且其自身是閉項集，所以AC 不是閉項集.但是可以發(fā)現(xiàn)，AC 同時存在于rela_table 和close_node中，A 也同時存在于no_closed_node 和candidate_set 中，由于AC 是閉項集，則A 也不是閉項集.當AC 和A 從candidate_set 中被移除時，candidate_set={B,C,D}.進而檢查B則有supercheck(B)=true，在rela_table 的closed_node 中沒有記錄B，所以B 為閉項集，將B 插入hash_table 中.同理可求得C 與D 也為閉項集.

圖3 TSW3 的ECET 樹Figure3 TSW3's ECET tree

3 實驗分析

本節(jié)主要分析算法CFMoment 和Moment 的執(zhí)行效率.測試數(shù)據(jù)來自IBM 數(shù)據(jù)生成器，其中所包含的事務總數(shù)由參數(shù)H表示，每個事務的平均長度由T表示，最大潛在的頻繁項集平均長度則為I，商品類別為N.這里利用生成的數(shù)據(jù)和T10.I10.N1000.D200K 數(shù)據(jù)進行實驗來比較兩種算法的效率.

本實驗使用的硬件平臺是Intel Pentium G60 處理器2.6 GHz，4 G 內(nèi)存，采用Windows 7操作系統(tǒng).算法由Java 實現(xiàn)，編譯器為Oracle JDK 7.0.

在這個實驗中，支持閾值可以在[0.05,1.00]范圍內(nèi)變化，并且窗口大小的變化規(guī)則是從20 kB 變化到100 kB.圖4顯示了這兩種算法隨窗口大小變化的操作時間圖，當窗口設置為20 kB 時，算法Moment 和CFMoment 的操作時間分別為285 ms 和98 ms.隨著窗口的擴大，Moment 和CFMoment 的操作時間不斷增加.當窗口大小達到100 kB 時，Moment 算法和CFMoment 算法的操作時間分別為476 ms 和412 ms.可以看出，當窗口大小設置為20 kB 時，CFMoment 算法的執(zhí)行速度明顯快于Moment 算法，這是因為當項集被添加或取消時，CFMoment 算法并不修改ECET 樹，而只是確定ECET 樹的哪些節(jié)點將受到最新項集和最舊項集的交操作影響，從而完成對ECET 樹的一次修改.而對于Moment 算法，只要有新的項集添加進來，CET 樹就會被修改.當樹被修改時，執(zhí)行刪除最舊項集的操作.因此，這種方式會導致窗口滑動時算法Moment 會連續(xù)修改CET 樹，從而大大降低算法的效率.從圖4還可以看出，當窗口接近最大值100 kB 時，這兩種算法的運行速度幾乎相同，這是因為當窗口大小為100 kB 時，兩種算法幾乎只要構建一次樹結構就可以完成閉合頻繁項集的挖掘.由于沒有滑動過程，CFMoment 算法和Moment 算法的執(zhí)行速度幾乎相同.

圖5顯示了這兩種算法在具有不同支持度閾值時的內(nèi)存消耗，當支持度閾值為0.05時，CFMoment 算法和Moment 算法的內(nèi)存消耗分別為88 MB 和277 MB.當支持度閾值接近1 時，兩種算法的內(nèi)存消耗均較低，但CFMoment 算法的整體內(nèi)存不會有太大變化，這是因為當支持度閾值變小時會有更多的頻繁閉項集.當Moment 算法尋找頻繁閉項集時，必須連續(xù)修改CET 樹.CET 樹修改越頻繁，內(nèi)存消耗就越多.在CFMoment 算法中，雖然在支持度閾值較低的情況下可以挖掘相同數(shù)量的頻繁閉項集，但在窗口滑動期間不必經(jīng)常改變ECET 樹，因此內(nèi)存消耗很小.然而，當支持度閾值增加時，頻繁閉項集的數(shù)量也減少，但此時Moment 仍然需要連續(xù)修改CET 樹，因此其內(nèi)存消耗必然大于CFMoment 算法.

圖4 執(zhí)行時間Figure4 Running time

圖5 內(nèi)存消耗Figure5 Memory consumption

4 結 語

本文提出的CFMoment 算法可以有效挖掘數(shù)據(jù)流中的頻繁閉項集.在該算法中，ECET樹用于記錄當前窗口中的頻繁閉項集，同時通過分析最新項目集和最舊項目集之間的關系來快速確定受影響項集的位置，并有效修改ECET 樹.實驗比較證明，CFMoment 算法的運行速度比Moment 更快，并且在數(shù)據(jù)流中挖掘頻繁閉項集時所占用的內(nèi)存資源更少.