CFMoment:挖掘數(shù)據(jù)流頻繁閉項(xiàng)集算法

王金偉， 吳少華， 瞿治國(guó)

南京信息工程大學(xué)計(jì)算機(jī)與軟件學(xué)院，南京210044

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

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

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

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

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

1 預(yù)備知識(shí)

1.1 基礎(chǔ)定義

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

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

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

1.2 問(wèn)題的提出

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

圖1 滑動(dòng)窗口Figure1 Sliding window

2 CFMoment 算法

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

2.1 建立ECET樹(shù)

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

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

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

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

4）Rela_table：該表主要記錄并保存ECET 樹(shù)中頻繁非閉項(xiàng)集與頻繁閉項(xiàng)集之間的相互關(guān)系.

與prefix-tree 所用結(jié)構(gòu)類似的是，ECET 樹(shù)中的每個(gè)節(jié)點(diǎn)ni都代表了一個(gè)項(xiàng)集I，而子節(jié)點(diǎn)nj則是在項(xiàng)集I添加新的項(xiàng)集后得到的.

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

算法1BuildTree(nI,w,s)

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

圖2 TSW1 的ECET 樹(shù)Figure2 TSW1's ECET tree

2.2 窗口滑動(dòng)過(guò)程

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

算法2Sliding(top,bottom+1)

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

算法3relacheck(I,Boolean,SupSet)

2.3 算法示例

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

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

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

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

圖3 TSW3 的ECET 樹(shù)Figure3 TSW3's ECET tree

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

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

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

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

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

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

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

4 結(jié) 語(yǔ)

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