滑動窗口中FP-Tree的頻繁項集挖掘算法的研究

李芬田,王紅梅,潘 超

(長春工業(yè)大學(xué) 計算機科學(xué)與工程學(xué)院,長春 130012)

1 引 言

數(shù)據(jù)流[1]的應(yīng)用越來越廣泛,比如我們常見的網(wǎng)絡(luò)監(jiān)控、股票的交易、網(wǎng)絡(luò)通訊的監(jiān)控、傳感器網(wǎng)絡(luò)和天氣或環(huán)境的檢測都會生成大量的數(shù)據(jù)流.隨著數(shù)據(jù)流應(yīng)用的普及,數(shù)據(jù)流環(huán)境下的數(shù)據(jù)挖掘越來越引起人們的興趣,又因為數(shù)據(jù)流中的頻繁項集又是數(shù)據(jù)流挖掘中最基本的問題之一,所以近十幾年得到許多學(xué)者的研究,但是由于數(shù)據(jù)流具有連續(xù)、無限、快速、隨著時間變化且不可預(yù)知的等特性,從而在數(shù)據(jù)流環(huán)境下挖掘頻繁項集帶來了很大的挑戰(zhàn).近幾年來大量的數(shù)據(jù)流頻繁項集挖掘算法被學(xué)者們陸續(xù)提出[2-5].其中最典型的是Han等人提出的FP-Growth算法[6],Manku等人提出的estDec算法[7],Leung等人提出的DSTree算法[8]和Giannella等人提出的FP-stream算法[9],FP-stream算法將最近的頻繁項集保存在傾斜時間窗口里,將舊的頻繁項集以粗糙的時間粒度保存,設(shè)計了Pattern-tree來維護頻繁模式信息,進而實現(xiàn)數(shù)據(jù)流上頻繁項集的挖掘;Lee等人提出WMFP-SW算法[10]和劉學(xué)軍等人提出的DS-CFI算法[11]是在FP-Growth算法上的改進實現(xiàn)了頻繁項集的挖掘,但是這兩個算法在處理稠密數(shù)據(jù)集時動態(tài)更新的速度比較慢;李國徽等人提出的DSFPM算法[12]能動態(tài)的挖掘出滑動窗口內(nèi)的完全頻繁項集,但是DSFPM-Tree中大量的父子節(jié)點存在不頻繁的關(guān)系時,建立的DSFPM-Tree比較高,并且樹中分支多,最關(guān)鍵的是窗口在滑動時,需要頻繁的更新DSFPM-Tree,導(dǎo)致時間開銷比較大;Deypir等人提出的pWin算法[13]采用前綴樹存儲頻繁項集,用反向深度遍歷挖掘頻繁項集,但是當(dāng)有大量的事務(wù)插入或刪除時,頻繁的訪問前綴樹比較浪費時間.

本文針對以上算法的不足,提出了滑動窗口中FP-Tree的頻繁項集挖掘算法MFI-SW(A frequent itemset mining algorithm in the sliding window),MFI-SW算法將數(shù)據(jù)流分塊挖掘,采用上三角矩陣存儲,在內(nèi)存中用NCFP-Tree保存每個基本窗口中的臨界頻繁項集,窗口滑動階段只需要將舊的NCFP-Tree刪除,建立新的NCFP-Tree即可,然后采用優(yōu)化的算法挖掘每個基本窗口中臨界頻繁項集,進而挖掘出完全頻繁項集.

2 問題描述

定義1[14].(數(shù)據(jù)流):設(shè)I={I1,I2,…,In}是項的集合,Ii表示第i項(1≤i≤n),數(shù)據(jù)流DS是一組連續(xù)不斷到達的數(shù)據(jù)序列{T1,T2,…,Tn}的集合,Tj表示第j個到達的事務(wù)(1≤j≤m),對于任意Tj都有Tj?I.

定義2[4].(滑動窗口):將數(shù)據(jù)流中的數(shù)據(jù)分成大小相等的塊,這樣的每個分塊是一個基本窗口,記作w.每塊中包含的事務(wù)個數(shù)是基本窗口的大小,記作|w|.k個連續(xù)的基本窗口組成一個滑動窗口W,記為W=〈w1,w2,…,wk〉,k值是預(yù)先固定的.滑動窗口的大小指的是每個滑動窗口中基本窗口的個數(shù),記為|W|.

支持度[14]:?X?I滑動窗口中包含項集X的事務(wù)個數(shù)稱為X的支持度計數(shù),記為S,若sup(X)=S/|w|,則sup(X)稱為X在w中的支持度.

定義3.(頻繁項集,臨界頻繁項集,非頻繁項集):對于用戶給定的最小支持度閾值為ζ和誤差因子為ε,假設(shè)|W|(|w|)表示滑動窗口W(基本窗口w)的大小.在滑動窗口W(基本窗口w)中模式A的支持度計數(shù)用fW(A)(fw(A))表示.如果滿足fW(A)≥ζ|W|(fw(A)≥ζ|w|),就稱模式A是滑動窗口W(基本窗口w)中的頻繁項集.如果滿足fW(A)≥(ζ-ε)|W|(fw(A)≥(ζ-ε)|w|),則稱為模式A是滑動窗口W(基本窗口w)中的臨界頻繁項集.如果滿足fW(A)<ε|W|(fw(A)<ε|w|),就稱模式A是滑動窗口W(基本窗口w)中的非頻繁項集.

性質(zhì)1[14].假設(shè)X是非頻繁項集,那么它的任何超集都是非頻繁項集.

性質(zhì)2.在NCFP-Tree中的父親和孩子組成的2-項集包含臨界頻繁2-項集的全部信息.

證明:因為在構(gòu)建NCFP-Tree時,只有插入節(jié)點和某個祖先節(jié)點能夠組成臨界頻繁2-項集才可以插入,否則刪除該結(jié)點.

性質(zhì)3.項目矩陣PM中包含頻繁1-項集和頻繁2-項集的全部信息.

定理1.每個基本窗口中的非頻繁項集被刪除后,盡管它們在整個滑動窗口中,是頻繁的,其中輸出支持度的誤差也不會超過ε,是可以接受的.

證明:設(shè)|w|表示一個基本窗口的寬度,|W|表示滑動窗口的長度,設(shè)定最小支持度閾值為ζ和誤差因子為ε,如果模式A在滑動窗口中是頻繁的,則滿足fW(A)≥ζ|W|,如果在基本窗口wi(1≤i≤k)中是臨界頻繁的,則滿足fwi(A)≥(ζ-ε)|wi|.如果在基本窗口wj(1≤j≤k)中是非頻繁的,則滿足fwj(A)<ε|wj|.因此,fW(A)=∑fwi(A)+∑fwj(A),所以對模式A支持度為fW(A)=∑fwi(A)=fW(A)-∑fwj(A)≥ζ|W|-∑ε|w|≥(ζ-ε)|W|.因此得證,由定理1知,僅僅保存每個基本窗口中的臨界頻繁項集,就可以滿足在誤差允許的范圍內(nèi)輸出的項集是滑動窗口中所有的頻繁項集.

3 MFI-SW算法描述

3.1 MFI-SW算法的數(shù)據(jù)結(jié)構(gòu)

該算法的數(shù)據(jù)結(jié)構(gòu)包含3種,分別是項目矩陣(PM),臨界頻繁模式樹NCFP-Tree和頻繁項集表(FI-i_List).

1)項目矩陣(PM):PM為上三角矩陣,每行或每列存儲數(shù)據(jù)庫中項的集合,其中項目矩陣中元素PM(i,j)的值表示出現(xiàn)的次數(shù).

2)臨界頻繁模式樹NCFP-Tree,由根節(jié)點(用null標(biāo)記)、臨界頻繁項集構(gòu)成的前綴子樹和臨界頻繁項頭表三部分組成.

除了根節(jié)點之外的每個節(jié)點是由5個域組成的(itemname,support,parent,child,nextnode),其中itemname表示項名,支持度計數(shù)用support表示,指向父節(jié)點的指針用parent_link表示,指向孩子節(jié)點的指針用child_link表示;指向樹中具有相同項名的下一個節(jié)點的指針用nextnode_link表示.

臨界頻繁項頭表ID_List中每個元組包含2個域(It_id,link),其中It_id表示基本窗口中臨界頻繁1-項集的項名,link表示鏈頭指針,指向NCFP-Tree中有相同項名的第一個節(jié)點,需降序排列每個基本窗口中項的支持度計數(shù).

3)FI-i_List():一種數(shù)組結(jié)構(gòu),包括k+2個域(Item,F1,F2,…,Fk,F),其中Item表示項名,Fi表示第i個基本窗口挖掘的臨界頻繁項集的支持度計數(shù),F表示滑動窗口中項集的支持度計數(shù)的和.為了提高時間效率,將挖掘出來的臨界頻繁項集分開存儲,臨界頻繁i-項集存儲在FI-i_List中,其中(1≤i≤n).該表起始狀態(tài)為空,將挖掘的基本窗口中臨界頻繁項集存儲在對應(yīng)的表中,關(guān)鍵的步驟是當(dāng)窗口滑動時,將挖掘的新本窗口中的項集直接覆蓋舊基本窗口中對應(yīng)的項集即可.

3.2 NCFP-Tree的構(gòu)造方法

它由根(用“NULL”標(biāo)記)、臨界頻繁項集構(gòu)成的前綴子樹和臨界頻繁項頭表三部分組成,創(chuàng)建NCFP-Tree的根結(jié)點,對DS中的每個事務(wù)進行如下處理:

1)選擇Ti中的臨界頻繁項,并將它們按臨界頻繁項頭表順序排列,第一次掃描項集,設(shè)排序后的臨界頻繁項集列表為[p|P],其中p是第一個項目,而P是剩余的項目列表.

2)調(diào)用insert_tree([p|P],T).

注意:函數(shù)insert_tree([p|P],T)執(zhí)行如下:

在插入節(jié)點之前,掃描項目矩陣PM,首先判斷插入結(jié)點與祖先節(jié)點組成的2-項集是否為臨界頻繁2-項集,如果有一個祖先節(jié)點M與該節(jié)點組合成的2-項集滿足臨界頻繁2-項集,則該節(jié)點可以作為M的孩子節(jié)點插入,如果不滿足臨界頻繁2-項集,那么一層一層的向根部搜索,直到有一節(jié)點q,它和插入節(jié)點組成的二項集的支持度滿足臨界頻繁項集的條件.但如果一直到根節(jié)點NULL都沒有節(jié)點與該節(jié)點能組合為臨界頻繁2-項集,那么剪掉該節(jié)點.如果能找到該節(jié)點,插入時需要進行下列操作:判斷T是否有子女,如果T有子女N使N.item=p,N的計數(shù)就加1,否則需要創(chuàng)建一個新的節(jié)點N,將item設(shè)置為p,sup設(shè)置為1,鏈接到它的父節(jié)點,并通過節(jié)點鏈Node_link鏈接到具有相同項名的節(jié)點上.

3)如果P不為空,遞歸調(diào)用insert_tree(P,p).

3.3 MFI-SW算法描述

1.窗口初始階段

輸入:數(shù)據(jù)流DS,滑動窗口W的大小為m,基本窗口大小為|w|,最小誤差因子ε

輸出:項目矩陣PM,每個基本窗口對應(yīng)的NCFP-Tree

1)滑動窗口中含m個基本窗口,基本窗口大小為|w|

2)for(i=1,i<=m,i++){

3)調(diào)用函數(shù)Creat_PM生成項目矩陣PM

4)調(diào)用算法Creat_NCFP-Tree,生成m個NCFP-Tree樹}

函數(shù)Creat_PM如下://項目矩陣的構(gòu)造

1)PM[i,j]=0 //初始化矩陣PM,n為項的個數(shù)

2)for each Ti in DS //掃描事務(wù)數(shù)據(jù)庫,構(gòu)建PM矩陣

3)for each ei in Ti

4)for each ej in Ti

5)if j>=i

6)PM[i,j]++

7)for i=1 to n // n代表基本窗口的平均長度

8){count=0

9)for j>=i+1 to n

10)if PM[i,j]<ε|w|

11)delete ei

12)// ei是不頻繁項,刪除支持度不符合條件的項}

2.窗口滑動階段

輸入:新基本窗口中的事務(wù)數(shù)據(jù)流,最小誤差因子ε,滑動窗口W的大小為m

輸出:更新的項目矩陣PM和新基本窗口的NCFP-tree

1)調(diào)用函數(shù)Creat_PM建立新基本窗口的項目矩陣

2)調(diào)用Creat_NCFP-Tree生成新基本窗口的NCFP-Tree樹

3)調(diào)用函數(shù)Update_FI-i_List更新頻繁項集表

對表都進行更新,函數(shù)Update_FI-i_List如下:

1)int column = t%m //t表示第t個窗口

2)for each ej in FI-i_List{

//ej表示在NCFP-Tree樹中挖掘的臨界頻繁項集

3)Fej=Fej+num //num是臨界頻繁項集ej的支持度計數(shù)

4)else

5)creat ej

6)Fej=num}

3.頻繁項集產(chǎn)生階段

輸入:滑動窗口中每個基本窗口的NCFP-Tree,最小支持度閾值min_sup,滑動窗口W的大小m

輸出:完全頻繁項集

1)按照臨界頻繁項頭表的順序取項目ei

2)for each ei in ID_List{

3)挖掘NCFP-Tree中所有包含ei的臨界頻繁項集,存在對應(yīng)的FI-i_List中}

4)for each ei in FI-i_List{

5)if Fei>=min_sup

6)輸出項集ei和它的支持度計數(shù)并存儲在FI_List中;

7)else

8)輸出?

9)輸出完全頻繁項集FI_List}

3.4 MFI-SW算法的執(zhí)行過程

以表1所示的事務(wù)數(shù)據(jù)流為例介紹算法的每步執(zhí)行過程,設(shè)滑動窗口的大小為2(也就是說一個滑動窗口包含2個基本窗口),最小支持min_sup=0.4,ε=0.1.

表1 事務(wù)數(shù)據(jù)流
Table 1 Transaction data stream

PanTID項集預(yù)處理項集W1T1 b c d e f gb c d f e gT2b c db c dT3a c h ic aT4b c d e fb c d f eT5b c d eb c d eT6a d f hd a fT7b c f g ib c f gT8a b c d fb c d a fT9a b e gb a e gT10a bb aW2T11a b d e f gb f d a e gT12b c d fb f d cT13a b c e fb f a c eT14b d fb f dT15b c f ib f cT16a d e g hd a e gT17b db dT18a b eb a eT19a b c fb f a cT20b c d f gb f d c g

1.窗口初始階段

數(shù)據(jù)流流入滑動窗口時,以基本窗口為單位,首先建立第一個基本窗口對應(yīng)的項目矩陣PM1,如表2所示,為了節(jié)省時間和空間,先把不頻繁的h和i兩項過濾掉.然后根據(jù)項目矩陣PM1對臨界頻繁項頭表進行降序排列,即bcdafeg,進而將數(shù)據(jù)壓縮存儲在NCFP-Tree樹中.

表2 項目矩陣PM1
Table 2 Project Matrix PM1

abcdefghia532212121b86544301c7534212d634110e42200f5211g301h21i2

掃描表1中預(yù)處理數(shù)據(jù),建立對應(yīng)的NCFP-Tree1,每插入一個節(jié)點,都要掃描項目矩陣PM1,查看該節(jié)點能否與祖先節(jié)點構(gòu)成臨界頻繁2-項集,如果能,則該節(jié)點插入在該祖先的孩子節(jié)點上,如果沒有,繼續(xù)向根部搜索,假設(shè)到達根節(jié)點NULL都不能找到與該節(jié)點組成臨界頻繁2-項集的祖先節(jié)點,那么剪掉該結(jié)點.如圖1所示是第一個基本窗口對應(yīng)的NCFP-Tree1.

利用同樣的方法,建立第二個基本窗口的項目矩陣PM2和它對應(yīng)的NCFP-Tree2.

2.窗口滑動階段

窗口滑動以后,采用最新的基本窗口的項目矩陣覆蓋最舊的基本窗口對應(yīng)的項目矩陣,釋放最舊基本窗口對應(yīng)的NCFP-Tree.同時用同樣的方法建立最新的基本窗口對應(yīng)的NCFP-Tree,頻繁項集表FI-i_List也要隨之更新,這里采用新基本窗口挖掘出來的頻繁項集直接覆蓋最舊的基本窗口挖掘的對應(yīng)項集.

圖1 第一個基本窗口的NCFP-Tree1Fig.1 First basic window NCFP-Tree1

3.頻繁項集產(chǎn)生階段

根據(jù)性質(zhì)3可知,項目矩陣PM中包含頻繁1-項集和頻繁2項集的全部信息,因此可以通過掃描事務(wù)矩陣PM1得到臨界頻繁1-項集FI-1_List={a:5,b:8,c:7,d:6,e:4,f:5,g:3}和臨界頻繁2-項集FI-2_List={ab:3,bc:6,bd:5,be:4,bf:4,bg:3,cd:5,ce:3,cf:4,de:3,df:4},通過利用改進的挖掘臨界頻繁項集技術(shù)挖掘每個基本窗口對應(yīng)的NCFP-Tree的所有臨界頻繁項集,得到FI-3_List={bce:3,bde:3,cde:3,bcf:4,bdf:3,cdf:3,bcd:5}和臨界頻繁4-項集FI-4_List={bcdf:3,bcde:3}.用同樣的方法可以挖掘第二個基本窗口,可得臨界頻繁1-項集FI-1_List={a:5,b:9,c:5,d:6,e:4,f:7,g:3},臨界頻繁2-項集為FI-2_List={ab:4,ae:4,af:3,bc:5,bd:5,be:3,bf:7,cf:5,df:4,dg:3},臨界頻繁3-項集FI-3_List={bdf:4,abf:3,bcf:5},最終輸出FI-i_List中的完全頻繁項集的挖掘結(jié)果FI_List={a:10,b:17,c:12,d:12,e:8,f:12,bf:11,cf:8,df:8,bd:10,bc:11,bcf:9}.

4 MFI-SW算法分析

實驗環(huán)境是操作系統(tǒng)為64位window7,3.20GHzCPU和安裝內(nèi)存是8.00GB,算法實現(xiàn)語言是C語言,實驗數(shù)據(jù)流的數(shù)據(jù)集[15]采用的是IBM data generator生成的模擬數(shù)據(jù).分別有稀疏集T7I4D100K,T10I4D100K和稠密集T40I10D100K,其中T表示的是事務(wù)的平均長度,I表示的是項集的平均最大長度,D表示的是總的事務(wù)項目.滑動窗口包含的基本窗口數(shù)為3,每個基本窗口包含10000條事務(wù),設(shè)支持度為ζ,取允許誤差因子ε固定為0.1ζ(ζ為最小支持度閾值).以下就算法的響應(yīng)時間和查全率、查準(zhǔn)率對MFI-SW算法和pWin算法、DSFPM算法進行實驗對比分析.

4.1 算法響應(yīng)時間

如圖2所示,新算法MFI-SW和DSFPM算法和pWin算法在三種不同的數(shù)據(jù)集上的處理時間,最小支持度閾值為0.5%,實驗結(jié)果標(biāo)明MFI-SW算法隨著平均長度的增加,時間消耗越大,在稠密數(shù)據(jù)集中的運行時間遠高于稀疏集,主要是因為稠密數(shù)據(jù)集中的事務(wù)的平均長度和項集的平均最大長度比較長,在滑動窗口中,更新數(shù)據(jù)和挖掘頻繁項集的過程比較消耗時間,所以該算法更合適稀疏數(shù)據(jù)集.

圖2 不同數(shù)據(jù)集上的運行時間比較Fig.2 Runtime comparison on different datasets

如圖3所示,在稀疏集T10I4D100K下對MFI-SW算法與DSFPM算法、pWin算法在不同最小支持度閾值下的處理時間進行了比較.實驗結(jié)果表明在最小支持度閾值從0.5%到1%變化的過程中,三個算法的時間開銷的變化趨勢都是隨著支持度閾值的增加,每個基本窗口挖掘出來的臨界頻繁項集數(shù)目減少,因此時間開銷也隨著減小,但是MFI-SW算法的時間性能略高于另外兩個算法.

圖3 不同支持度的運行時間比較Fig.3 Comparison of run time with different support

圖4 不同的窗口大小、算法運行時間的比較Fig.4 Different window sizes、comparison of algorithm run time

如圖4所示,為了顯示窗口大小對所有算法的時間使用的影響,在稀疏集T10I4D1000K中測試不同窗口大小的情況下,MFI-SW算法與DSFPM算法、pWin算法的時間開銷,取最小支持度閾值ζ=0.5%.實驗結(jié)果表明滑動窗口越大,算法的時間開銷越大,MFI-SW算法隨著滑動窗口的增加,時間開銷變化較穩(wěn)定,其他兩個算法pWin和DSFPM在滑動窗口增加的情況下,因為它們都需要頻繁的更新樹結(jié)構(gòu),所以時間開銷變化較大.

4.2 算法的查準(zhǔn)率和查全率

在算法中最大誤差是一個非常重要的剪枝參數(shù),查準(zhǔn)率指的是算法挖掘出來的實際頻繁項集的數(shù)量與算法挖掘出來的輸出數(shù)量的百分比,而查全率則指的是算法挖掘出來的實際頻繁項集的數(shù)量值與真實數(shù)量的百分比.一般情況下,在數(shù)據(jù)集中挖掘頻繁項集以最大的誤差值作為剪枝參數(shù),在挖掘過程中更新樹結(jié)構(gòu)時對算法的查全率和查準(zhǔn)率有很大的影響,圖5和圖6測試了IBM合成數(shù)據(jù)流中的前三條數(shù)據(jù)流[16]中不同誤差值對算法的查準(zhǔn)率和查全率的影響.假定誤差值分別為0.0002,0.0008,0.0014和0.002時,觀察測試結(jié)果.

圖5 不同的誤差因子、算法查準(zhǔn)率的比較Fig.5 Different error factors、comparison of algorithm precision

從圖5和圖6中不難看出,在誤差值逐漸變大的過程中,MFI-SW算法的查準(zhǔn)率和查全率高于pWin和DSFPM兩個算法.因為當(dāng)誤差值逐漸增大的過程中,挖掘出來的頻繁項集的數(shù)量變少,于是用戶指定的誤差值越大,挖掘出來的頻繁項集數(shù)量就越少,挖掘多條數(shù)據(jù)流中的頻繁項集的準(zhǔn)確率和查全率就會越高.

圖6 不同的誤差因子、算法查全率的比較Fig.6 Different error factors、comparison of algorithm recall rate

5 結(jié)束語

本文提出了滑動窗口中FP-Tree的頻繁項集挖掘算法MFI-SW,該算法采用上三角矩陣的存儲方式,每個基本窗口建立一個NCFP-Tree來壓縮存儲數(shù)據(jù)信息,在相同節(jié)點個數(shù)的情況下,NCFP-Tree較FP-Tree的深度低,分支少,因為NCFP-Tree中的父子節(jié)點保留臨界頻繁2-項集的全部信息,窗口滑動時,將舊基本窗口的NCFP-Tree釋放,建立新基本窗口的NCFP-Tree,整個過程中保證每棵樹都按基本窗口中的1-項集的支持度計數(shù)的降序排列,有效的提高了MFI-SW算法的壓縮效率,并為頻繁項集的輸出帶來方便,通過與經(jīng)典的算法比較證明,MFI-SW算法具有良好的時間性能.在此基礎(chǔ)上還需研究以二項集為根,建立樹結(jié)構(gòu),這樣使樹結(jié)構(gòu)更矮,挖掘效率更高.