李芬田,王紅梅,潘 超

(長(zhǎng)春工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院,長(zhǎng)春 130012)

1 引 言

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

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

2 問(wèn)題描述

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

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

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

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

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

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

證明:因?yàn)樵跇?gòu)建NCFP-Tree時(shí),只有插入節(jié)點(diǎn)和某個(gè)祖先節(jié)點(diǎn)能夠組成臨界頻繁2-項(xiàng)集才可以插入,否則刪除該結(jié)點(diǎn).

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

定理1.每個(gè)基本窗口中的非頻繁項(xiàng)集被刪除后,盡管它們?cè)谡麄€(gè)滑動(dòng)窗口中,是頻繁的,其中輸出支持度的誤差也不會(huì)超過(guò)ε,是可以接受的.

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

3 MFI-SW算法描述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3 MFI-SW算法描述

1.窗口初始階段

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

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

1)滑動(dòng)窗口中含m個(gè)基本窗口,基本窗口大小為|w|

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

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

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

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

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

2)for each Ti in DS //掃描事務(wù)數(shù)據(jù)庫(kù),構(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代表基本窗口的平均長(zhǎng)度

8){count=0

9)for j>=i+1 to n

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

11)delete ei

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

2.窗口滑動(dòng)階段

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

輸出:更新的項(xiàng)目矩陣PM和新基本窗口的NCFP-tree

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

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

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

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

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

2)for each ej in FI-i_List{

//ej表示在NCFP-Tree樹中挖掘的臨界頻繁項(xiàng)集

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

4)else

5)creat ej

6)Fej=num}

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

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

輸出:完全頻繁項(xiàng)集

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

2)for each ei in ID_List{

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

4)for each ei in FI-i_List{

5)if Fei>=min_sup

6)輸出項(xiàng)集ei和它的支持度計(jì)數(shù)并存儲(chǔ)在FI_List中;

7)else

8)輸出?

9)輸出完全頻繁項(xiàng)集FI_List}

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

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

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

PanTID項(xiàng)集預(yù)處理項(xiàng)集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ù)流流入滑動(dòng)窗口時(shí),以基本窗口為單位,首先建立第一個(gè)基本窗口對(duì)應(yīng)的項(xiàng)目矩陣PM1,如表2所示,為了節(jié)省時(shí)間和空間,先把不頻繁的h和i兩項(xiàng)過(guò)濾掉.然后根據(jù)項(xiàng)目矩陣PM1對(duì)臨界頻繁項(xiàng)頭表進(jìn)行降序排列,即bcdafeg,進(jìn)而將數(shù)據(jù)壓縮存儲(chǔ)在NCFP-Tree樹中.

表2 項(xiàng)目矩陣PM1
Table 2 Project Matrix PM1

abcdefghia532212121b86544301c7534212d634110e42200f5211g301h21i2

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

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

2.窗口滑動(dòng)階段

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

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

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

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

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

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

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

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

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

圖3 不同支持度的運(yùn)行時(shí)間比較Fig.3 Comparison of run time with different support

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

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

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

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

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

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

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

5 結(jié)束語(yǔ)

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