魏恩超,張德生,安平平

1(西安理工大學(xué) 理學(xué)院,西安 710054)

2(西北師范大學(xué) 教育學(xué)院,蘭州 730070)

數(shù)據(jù)挖掘(DM,Data Mining)是近年來研究、開發(fā)和應(yīng)用最活躍的一個領(lǐng)域,它是在機器學(xué)習(xí)、神經(jīng)網(wǎng)絡(luò)和模式識別的理論基礎(chǔ)上發(fā)展而來的,其任務(wù)是從海量數(shù)據(jù)中提取隱含且用戶感興趣的知識和信息[1].

關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘中最重要的研究領(lǐng)域之一,其本質(zhì)是對頻繁模式的挖掘,最早由Agrawal 等提出[2],目的是發(fā)現(xiàn)模式之間隱含的內(nèi)在聯(lián)系,為后續(xù)問題的解決提供決策支持.關(guān)聯(lián)規(guī)則挖掘主要包含兩個子問題：一是生成頻繁模式集,其任務(wù)是根據(jù)用戶設(shè)置的最小支持度閾值生成所有頻繁模式；另一個是生成關(guān)聯(lián)規(guī)則,主要任務(wù)是從所有的頻繁模式中提取滿足最小置信度閾值的規(guī)則.

頻繁模式挖掘算法大致可分為兩類：一種是類Apriori 算法,如文獻(xiàn)[3]提出了Inter-Apriori 頻繁模式挖掘算法,該算法使用交集策略來減少掃描數(shù)據(jù)庫的次數(shù),使算法達(dá)到了較高的效率；文獻(xiàn)[4]提出了一種基于三角矩陣和差集的垂直數(shù)據(jù)格式挖掘頻繁模式的算法；文獻(xiàn)[5]提出了一種基于前綴項集的候選集存儲結(jié)構(gòu),并利用哈希表進(jìn)行快速查找,提高了經(jīng)典Apriori算法在連接步和剪枝步中的效率；文獻(xiàn)[6]提出了一種基于矩陣的改進(jìn)算法,通過事務(wù)矩陣和候選項集項目矩陣相乘的矩陣操作改進(jìn)頻繁掃描數(shù)據(jù)庫的問題,優(yōu)化了Apriori 算法的連接步與剪枝步.這些算法都是由經(jīng)典的Apriori 算法改進(jìn)而來,由于Apriori 算法的固有缺陷,使得這些算法的挖掘效率仍然不高.另一類是基于頻繁模式增長的算法,如文獻(xiàn)[7]提出了一種基于頻繁模式樹(FP-tree)的FP-growth 算法；文獻(xiàn)[8]提出了一種基于COFI-Tree 挖掘N-最有興趣項集算法,該算法采用COFI-Tree 結(jié)構(gòu),無需遞歸構(gòu)造條件子樹FPTree；文獻(xiàn)[9]提出了一種基于鄰接表的改進(jìn)FP-Growth算法,該算法使用哈希表存儲鄰接表,可以快速刪除小于最小支持閾值的模式.這類算法利用樹結(jié)構(gòu)對數(shù)據(jù)庫進(jìn)行壓縮,不產(chǎn)生候選項集,減少了數(shù)據(jù)庫的掃描次數(shù),但在對大型稠密數(shù)據(jù)集進(jìn)行挖掘時會構(gòu)造大量條件模式基和條件FP-tree,對內(nèi)存消耗非常大.

為克服前兩類算法的局限性,一些研究人員將Apriori 算法和FP-tree 結(jié)構(gòu)結(jié)合[10-14].這類算法先將整個數(shù)據(jù)庫投影到FP-tree 上,然后對FP-tree 進(jìn)行分區(qū),將數(shù)據(jù)庫劃分成若干個子數(shù)據(jù)集,最后利用Apriori 算法的候選生成-測試機制對子數(shù)據(jù)集進(jìn)行挖掘.文獻(xiàn)[10]首次將Apriori 算法與FP-tree 結(jié)合,提出了相應(yīng)的APFT 算法,該算法不需要遞歸地生成條件模式基和條件FP-tree,有效提高了挖掘效率.文獻(xiàn)[11]在FP-tree 的基礎(chǔ)上提出了壓縮頻繁模式樹(CFP-tree),并從最不頻繁的項開始劃分生成子樹,并在每棵子樹上執(zhí)行候選項集生成機制,算法避免了遞歸生成大量子樹,提高了模式挖掘速度；文獻(xiàn)[12]利用頻繁1-項集對數(shù)據(jù)庫進(jìn)行分庫,統(tǒng)計候選項集支持度計數(shù)時只掃描分庫,減少了Apriori 算法對數(shù)據(jù)庫的遍歷次數(shù)；文獻(xiàn)[13]提出了一種改進(jìn)的基于fp-tree 的Apriori 算法,該算法先用尾元將fp-tree 分區(qū),生成數(shù)據(jù)量更小的子數(shù)據(jù)集,再動態(tài)刪除冗余數(shù)據(jù)將子數(shù)據(jù)集進(jìn)一步壓縮,最后通過掃描子數(shù)據(jù)集進(jìn)行支持?jǐn)?shù)統(tǒng)計；文獻(xiàn)[14]將Apriori 算法與FP-growth 算法結(jié)合,提出了一種基于事務(wù)映射區(qū)間求交的頻繁模式挖掘算法IITM,只需掃描數(shù)據(jù)集兩次來生成FP-tree,然后掃描FP-tree 將每個項的ID 映射到區(qū)間中,通過區(qū)間求交進(jìn)行模式增長.但將FP-tree 結(jié)構(gòu)與Apriori 算法結(jié)合后仍存在以下不足：(1) Apriori算法在連接步會花費大量時間判斷項集是否滿足連接條件；(2) 構(gòu)建FP-tree 時需要對數(shù)據(jù)庫進(jìn)行兩次掃描,且不支持交互式挖掘與增量挖掘.

為解決這些問題,本文在APFT 算法的基礎(chǔ)上提出了一種改進(jìn)的頻繁模式挖掘算法.主要進(jìn)行了如下改進(jìn)：(1)在算法的連接步前加入預(yù)處理過程,減少比較次數(shù)；(2)提出了一種新的緊湊前綴樹結(jié)構(gòu),只需對數(shù)據(jù)庫進(jìn)行一次掃描就可以構(gòu)造出一棵緊湊的模式樹,且支持交互式挖掘與增量挖掘,能有效處理數(shù)據(jù)流問題.

1 問題陳述

1.1 頻繁模式挖掘

設(shè)I={I1,I2,···,Im}是所有項的集合,不失一般性,I中的項按字典順序排列,即I1＜···＜Im.T為一個事務(wù),每個事務(wù)都由唯一的標(biāo)識符TID和與之對應(yīng)的項集Item(T)(Item(T)?I)構(gòu)成,所有事務(wù)構(gòu)成了事務(wù)數(shù)據(jù)庫D,D中包含事務(wù)的個數(shù)稱為數(shù)據(jù)庫的大小,記為S ize(D).設(shè)X?I為一個項集,項集中包含項的個數(shù)叫做項集的長度,記為Length(X),即Length(X)=|X|,長度為k的項集稱為k-項集.事務(wù)T包含項集X,當(dāng)且僅當(dāng)X?Item(T),項集X的支持度計數(shù) σ (X)定 義為數(shù)據(jù)庫D中包含項集X的事務(wù)數(shù),即σ (X)=|{T|T∈D∧X?Item(T)}|,項集X的支持度sup(X) 定義為包含項集X的事務(wù)在數(shù)據(jù)庫D中所占的比例,即sup(X)=σ(X)/S ize(D).項集X為頻繁模式,當(dāng)且僅當(dāng)sup(X)≥minsup,其中minsup為給定的最小支持度閾值,長度為k的頻繁項集稱為頻繁k-項集,記為Fk.

頻繁模式挖掘定義為,在給定的數(shù)據(jù)庫D和最小支持度閾值minsup條 件下,找出所有頻繁模式FI=F1∪F2∪···∪Fl,l為頻繁模式的最大長度.

1.2 Apriori 算法

Apriori 算法[2]最早由Agrawal 等提出,該算法使用先驗性質(zhì)壓縮搜索空間,并使用一種逐層搜索的迭代方法,其中k-項集用于探索(k+1)-項集.Apriori 算法主要包含以下3 個步驟：

連接步：這一步主要是為了生成候選k-項集Ck,設(shè)l1和l2是頻繁(k-1)項 集Fk-1中 的項集,記號li[j]表示li的第j項,項集中的項按字典順序排列,如果有(l1[1]=l2[1])∧···∧(l1[k-2]=l2[k-2])∧(l1[k-1]＜l2[k-1]),則連接l1和l2生成候選k-項集Ck,其中Ck={l1[1],l1[2],···,l1[k-1],l2[k-1]}.

剪枝步：利用頻繁項集的反單調(diào)性對候選k-項集Ck進(jìn)行剪枝,生成頻繁k-項集Fk.如果候選k-項集的一個(k-1)項 子集不在Fk-1中,則該候選項集為非頻繁項集,否則需要遍歷數(shù)據(jù)庫進(jìn)行支持?jǐn)?shù)統(tǒng)計,進(jìn)一步驗證Ck是否頻繁.

統(tǒng)計支持度計數(shù)：掃描數(shù)據(jù)庫D,對候選k-項集Ck在數(shù)據(jù)庫中出現(xiàn)的次數(shù)進(jìn)行累加,根據(jù)給定的最小支持度閾值minsup生成頻繁k-項集.

1.3 FP-tree 結(jié)構(gòu)

為克服Apriori 算法的缺陷,韓家煒等提出了基于FP-tree 的FP-Growth 算法[7],該算法只需對數(shù)據(jù)庫進(jìn)行兩次掃描,且不產(chǎn)生候選項集,FP-tree 結(jié)構(gòu)能對數(shù)據(jù)庫進(jìn)行有效壓縮.

FP-tree 中每個節(jié)點由4 個域組成：項標(biāo)識itemname、節(jié)點計數(shù)item-count、節(jié)點鏈item-link和父節(jié)點指針item-parent.同時為了方便對樹進(jìn)行操作,FPtree 還包含一個頻繁項頭表header-table,它由兩個域組成：項標(biāo)識item-name和項元鏈鏈頭node-link,其中node-link 是指向FP-tree 中具有相同項標(biāo)識的首節(jié)點指針,FP-tree 中實線是父節(jié)點指針,虛線是節(jié)點鏈.FPtree 相關(guān)概念及結(jié)構(gòu)細(xì)節(jié)見文獻(xiàn)[1].使用表1中的示例數(shù)據(jù)生成的FP-tree 如圖1所示,設(shè)最小支持度閾值minsup=3.

表1 樣例數(shù)據(jù)集

圖1 FP-tree 結(jié)構(gòu)

1.4 APFT 算法

APFT 算法[10]使用Apriori 算法挖掘基于FP-tree的頻繁模式,該算法仍采用分治策略.APFT 算法主要包括兩個步驟,第一步是利用FP-growth 算法中構(gòu)造樹的方法構(gòu)造FP-tree；第二步是利用Apriori 算法挖掘FP-tree.在第二步中,需要添加一個名為N Table的附加節(jié)點表,表中的每個項由兩個域組成：Item-name和Item-support.Item-name 表示在條件子樹FPTj(j=1,2,···,n)中 節(jié)點的名稱,I tem-support表示與頻繁1-項集Ij(j=1,2,···,n)一起出現(xiàn)的節(jié)點數(shù),即項的支持度計數(shù).APFT 是最早將Apriori 算法與FP-tree 結(jié)合的算法,但由于Apriori 算法與FP-tree 自身的缺陷導(dǎo)致該算法仍存在一些不足,因此本文對APFT 中的連接步與樹構(gòu)造方法進(jìn)行了改進(jìn),使算法能有效處理數(shù)據(jù)流問題.APFT 算法的偽代碼如算法1 所示.

算法1.APFT Input: FP-tree,minsup Output: all frequent patterns L 1) L=L1；Ij 2) for each item in header table,in top down order LI j=Apriori-mining(Ij)3)；L=L∪LI1∪LI2∪···∪LIn 4) return；Apriori-mining(Ij)Pseudocode 1) Find item p in the header table which has the same name with；q=p.tablelink I j 2)；3) while q is not null 4) for each node qj!=root on the prefix path of q 5) if NTablehas a entry N such that N.Item-name=qj.item-name N.Item-support=N.Item-support+q.count 6)；7) else NTable 8) add an entry N to the；N.Item-name=q j.item-name 9)；N.Item-support=q.count 10)；q=q.tablelink 11)；k=1 12)；Fk={i|i∈NTable∧i.item-support≥minsup}13) 14) repeat k=k+1 15)；Ck=apriori-gen(Fk-1)16)；q=p.tablelink 17)；18) while q is not null t of q 19) find prefix path Ct=subset(Ck,t)20)；c∈Ct 21) for each c.support=c.support+q.count 22)；q=q.tablelink 23)；Fk={c|c∈Ck∧c.support≥min_S up}24) 25) until Fk=? 26) return LIi=Ii∪F1∪F2∪···∪Fk

2 改進(jìn)算法

2.1 算法改進(jìn)思想

為了提高基于FP-tree 的Apriori 算法的挖掘效率,從進(jìn)一步縮減數(shù)據(jù)庫掃描次數(shù)以及增強算法的交互式挖掘與增量挖掘的方向改進(jìn).首先,將Apriori 算法的apriori_gen()函數(shù)中的連接步進(jìn)行優(yōu)化.由于連接步需要大量比較步驟,并且會產(chǎn)生大量無用的候選項集,因此增加了后續(xù)剪枝步和支持度計數(shù)步的時間開銷.其次,將CP-tree[15]進(jìn)行擴(kuò)展,提出了一個新的樹結(jié)構(gòu)ECP-tree(Extension of Compact Pattern tree).由于在構(gòu)造CP-tree 的過程中包含所有項,不論是頻繁項還是非頻繁項都參與了樹的構(gòu)造,因此占用了大量的內(nèi)存空間,并且會影響頻繁模式的挖掘效率.在新構(gòu)造的ECP-tree 中只包含頻繁項,刪除了非頻繁項,并且只經(jīng)過一次數(shù)據(jù)庫掃描就可以構(gòu)造出一棵緊湊的前綴樹,新構(gòu)造的樹結(jié)構(gòu)不僅支持交互式挖掘而且也支持增量挖掘.

2.2 優(yōu)化連接步

在給出優(yōu)化思想之前,首先了解兩個關(guān)于集合的性質(zhì).

性質(zhì)1.包含k個不同項的k-項集有k個不同的(k-1)項子集；

性質(zhì)2.假設(shè)I 為k-項集中的一個項,根據(jù)性質(zhì)1 可得,在k個子集中必有(k-1)個子集包含項I.

在Apriori 算法的apriori_gen()函數(shù)的連接步中,需要進(jìn)行多次前(k-1)項的比較,這大大增加了算法的時間開銷.經(jīng)研究發(fā)現(xiàn),存在這樣一個性質(zhì)：

性質(zhì)3.假設(shè)I 為頻繁k-項集Fk中的一個項,如果包含I 的頻繁k-項集還能產(chǎn)生頻繁(k+1)- 項集,則包含I 的頻繁k-項集的總數(shù)不小于k.如果項集總數(shù)小于k,那么Fk就不用參與后續(xù)的連接步.證明過程如下：

反證法：假設(shè)包含項 I的Fk參與了后續(xù)的連接步,那么就會生成包含項I 的候選(k+1)-項集Ck+1.如果候選項集Ck+1不 被刪除,則必須滿足Ck+1的k+1 個k項子集必須都是頻繁的,即這k+1 個k項子集必須在頻繁k-項集中,根據(jù)性質(zhì)2 可得,在k+1 個k項子集中有k 個子集包含項I,也就是說包含項I 的項集總數(shù)不小于k.反之,如果包含項I 的項集總數(shù)小于k,那么連接生成的Ck+1必然會被剪掉.

根據(jù)性質(zhì)3,可對連接步進(jìn)行優(yōu)化,在連接之前進(jìn)行預(yù)處理,刪除不滿足條件的Fk.預(yù)處理過程的偽代碼如下所示：

算法2.Pretreatment Input：頻繁k-項集Fk Output：滿足連接條件的頻繁-項集Fi∈Fk kLk 1) for each items 2) for each item I∈Fk I∈Fi 3) if 4) I.count++5) for each item I.count＜k I∈Fi 6) if 7) delete from Lk FiFk 8) return

為了說明優(yōu)化流程,用以下示例說明具體過程.假設(shè)表2是事務(wù)數(shù)據(jù)庫產(chǎn)生的所有頻繁3-項集F3.

表2 所有頻繁3-項集

在原始Apriori 算法中,保留所有頻繁3-項集進(jìn)入連接步,連接產(chǎn)生的候選4-項集C4(未剪枝的候選項集)如表3所示.

如表3所示,表2中的12 個頻繁3-項集連接后共產(chǎn)生16 個候選4-項集,根據(jù)剪枝原理,剪枝后剩下的候選4-項集只有{I2,I3,I4,I10}.只有這一個候選4-項集進(jìn)入支持度計數(shù)步.連接步的預(yù)處理過程如下所示：

第一步：計算表2中12 個頻繁3-項集中每一個項的計數(shù),結(jié)果如表4所示.

第二步：由表4可知,項I1、I5、I6、I7、I8、I9的計數(shù)小于k(即,3),因此對所有包含項I1、I5、I6、I7、I8、I9的頻繁3-項集F3進(jìn)行剪枝,剪枝后的頻繁3-項集L3如表5所示.預(yù)處理后只剩4 個頻繁3-項集,按照連接規(guī)則將這4 個頻繁項集進(jìn)行連接,生成一個候選4-項集{I2,I3,I4,I10},對這個候選項集進(jìn)行剪枝操作,沒有被剪掉,進(jìn)入支持度計數(shù)步.預(yù)處理后的結(jié)果與原始Apriori 算法結(jié)果相同,故預(yù)處理步驟是合理的.

表4 頻繁3-項集中每個項計數(shù)

表5 預(yù)處理后的頻繁3-項集

2.3 新樹的構(gòu)造

新樹的構(gòu)造主要包括兩個階段：1)插入階段；2)重構(gòu)階段.在插入階段,通過逐一掃描數(shù)據(jù)庫中的事務(wù)項集,根據(jù)項在事務(wù)中出現(xiàn)的先后順序?qū)⑺鼈儾迦霕渲?由于將事務(wù)插入樹中時,它維護(hù) I-list 并更新I -list中各個項的支持度計數(shù),因此,在插入所有事務(wù)后,樹結(jié)構(gòu)在I -list中具有數(shù)據(jù)庫中所有項的支持度計數(shù).在重構(gòu)階段,根據(jù)項的支持度計數(shù)以降序方式重新排列I-list,只保留頻繁項,即支持度大于等于用戶指定的最小支持度閾值的項,并根據(jù)新排列的I -list重新構(gòu)造樹節(jié)點.在樹重構(gòu)中,使用分支排序方法(BSM,Branch Sorting Method)[15],該方法逐一對未排序的路徑進(jìn)行排序并按項的支持度計數(shù)降序排列I -list實現(xiàn)重構(gòu).

本文對分支排序方法(BSM)進(jìn)行了改進(jìn),使該算法能夠適應(yīng)新提出的樹結(jié)構(gòu).在改進(jìn)方法中,如果路徑?jīng)]有按照新的排序順序進(jìn)行排序,則將該路徑刪除,并刪除非頻繁的項,將剩余的頻繁項按排序順序排列到一個臨時數(shù)組中,最后再按順序插入樹中,重復(fù)此過程最終將得到一棵緊湊的模式樹.改進(jìn)的分支排序方法(IBSM,Improve Branch Sorting Method)的偽代碼如算法3 所示.

算法3.IBSM Input：T和I Output：僅包含頻繁項的Tsort和Isort 1) Compute Isort from I in frequency-descending order using merge sort technique 2) for each branch Bi in T 3) for each unprocessed path Pj in Bi 4) if Pj contains only frequent items in order according to Isort 5) Process_Branch(Pj)6) else Sort_path(Pj)7) Terminate when all the branches are sorted and output Tsort ang Isort.8) Process_Branch(P){9) for each branching node nb in P from the leafP node≠10) for each sub-path from the leafk with k p 11) if item ranks of all nodes between nb and leafk are greater than that of nb 12) P=sub-path from nb to leafk 13) if P is contains only frequent items in order according to Isort 14) Process_Branch(P)15) else P=path from the root to leafk 16) Sort_path(P)17) }18) Sort_ path(Q){19) Reduce the count of all node of Q by the value of leafQcount 20) Delete all nodes contains infrequent items and sort remaining nodes in an array according to Isort order 21) Delete all nodes having count zero from Q 22) Insert sorted Q into T at the location from where it was taken 23)}

為了更好地理解改進(jìn)樹重構(gòu)方法的工作原理,使用表1給出的樣例數(shù)據(jù)庫進(jìn)行詳細(xì)說明,設(shè)最小支持度閾值minsup=3.圖2為插入階段后的樹結(jié)構(gòu)T和項列表I,此過程與原始分支排序方法中的插入階段略有不同.由于項列表I和前綴樹T 沒有按項的支持度計數(shù)降序排列,因此,為了使用IBSM 以項的降序重構(gòu)樹,首先對I 進(jìn)行排序以生成只包含頻繁項的新列表Isort,如圖3所示.重構(gòu)從樹的第一個分支開始,即最左邊的分支,從圖2所示樹的根節(jié)點開始.由于分支的第一個路徑 {f:1,a:1,c:1,d:1,g:1,i:1,m:1,p:1}是一個未排序的路徑,因此將該路徑從樹中移除,移除后的樹如圖4所示,將移除的路徑存放在一個臨時數(shù)組中并按Isort中項的順序?qū)τ嘞碌念l繁項進(jìn)行重新排列,排序后的路徑為{ f:1,c:1,a:1,m:1,p:1},如圖5所示.然后再按順序插入樹中,圖6顯示了第一個路徑排序完成后的樹結(jié)構(gòu).重復(fù)此過程,直到所有路徑都完成排序,圖7顯示了重構(gòu)后的最終樹.

圖2 插入階段后的I和T

圖3 重排I 構(gòu)造Isort

新提出的樹結(jié)構(gòu)只需對數(shù)據(jù)庫進(jìn)行一次掃描,就可以構(gòu)造出一棵與FP-tree 完全相同的樹.新的樹結(jié)構(gòu)支持交互式挖掘,在交互式挖掘中,用戶可以為同一個數(shù)據(jù)庫更改指定的最小支持度閾值.在這種情況下,我們可以在插入所有事務(wù)后保存樹,然后根據(jù)用戶指定的最小支持度閾值重構(gòu)樹,在I -list中保存著所有項的總支持度計數(shù),可以根據(jù)不同的最小支持度閾值只保留頻繁項,而不需要重新掃描數(shù)據(jù)庫.因此,新提出的樹結(jié)構(gòu)不需要像FP-tree 那樣重新掃描數(shù)據(jù)庫以實現(xiàn)交互式挖掘.新的樹結(jié)構(gòu)也支持增量挖掘,在增量挖掘中,可以對原始數(shù)據(jù)庫中的事務(wù)進(jìn)行添加和/或刪除.在這種情況下,我們可以在原始數(shù)據(jù)庫中插入所有事務(wù)后保存樹,當(dāng)添加新事務(wù)和/或刪除一些舊事務(wù)時,可以在樹中添加新事務(wù)的分支并且刪除那些被刪除的事務(wù)分支,重構(gòu)樹不需要像FP-tree 那樣再次掃描原始數(shù)據(jù)庫.

圖4 移除未排序路徑

圖5 在臨時數(shù)組中對路徑排序

3 實驗分析

為驗證所提方法的有效性,將改進(jìn)方法運用到APFT 算法中來挖掘頻繁模式,且與原始APFT 算法、FP-Growth 算法以及Apriori 算法進(jìn)行比較.本文算法實驗平臺為：Intel Core i7-4790 CPU 3.6 GHz 處理器和8 GB 內(nèi)存,Windows 10 64 位操作系統(tǒng),開發(fā)軟件為Matlab R2014a.實驗所用的數(shù)據(jù)集有兩個,mushroom數(shù)據(jù)庫和T10I4D100K 數(shù)據(jù)庫,均可從http：//fimi.ua.ac.be/data/.下載,數(shù)據(jù)集的特征如表6所示.本文分別在這兩種數(shù)據(jù)集上進(jìn)行對比試驗,每組試驗的參數(shù)都是不變的,都是通過改變最小支持度閾值從而記錄算法的運行時間,算法運行的時間越小代表算法的挖掘速度越快.

圖6 將排序后的路徑插入T 中

圖7 重構(gòu)后的最終樹

表6 數(shù)據(jù)庫特征

在相同條件下,算法獨立實驗10 次,取其運行時間的均值作為算法最終結(jié)果.兩個數(shù)據(jù)集在不同算法和不同最小支持度閾值下的運行時間對比如表7和表8所示,單位為秒(即,s).從表中可以看出,本文改進(jìn)算法在運行時間上明顯優(yōu)于其他幾個算法,說明本文改進(jìn)算法有效提高了頻繁模式的挖掘速度.從圖8和圖9中可以看出本文改進(jìn)算法比原始APFT 算法更高效,主要原因有兩個：1)在算法的apriori_gen()函數(shù)前加入了連接預(yù)處理步驟,對進(jìn)入連接步的頻繁k-項集進(jìn)行剪枝,減少了兩兩頻繁項集前(k-1)項的比較次數(shù),因此減小了連接步的時間消耗,并且候選項集的數(shù)量也減少了,減小了剪枝步的時間開銷；2)新提出的樹構(gòu)只需對數(shù)據(jù)庫進(jìn)行一次掃描就可以構(gòu)造出一顆緊湊的模式樹,雖然增加了樹重構(gòu)過程但這一過程基本上不會花費太多時間,并且在挖掘過程中不需要額外的空間,因此本文改進(jìn)算法具有更好的空間可擴(kuò)展性.

表7 mushroom 上不同算法運行時間對比

表8 T10I4D100K 上不同算法運行時間對比

圖8 mushroom 上運行時間對比

圖9 T10I4D100K 上運行時間對比

4 結(jié)束語

本文針對傳統(tǒng)頻繁模式挖掘算法存在的固有缺陷,提出了一種基于APFT 算法的改進(jìn)頻繁模式挖掘算法.首先,在算法的連接步前加入預(yù)處理過程,對參與連接的頻繁k-項集進(jìn)行有效剪枝,大大減少了連接步與剪枝步的時間開銷；其次,對CP-tree 進(jìn)行擴(kuò)展提出了一種新的樹結(jié)構(gòu)ECP-tree,新的樹結(jié)構(gòu)是一棵緊湊的前綴模式樹；然后,再將改進(jìn)點與APFT 算法結(jié)合用于頻繁模式挖掘；最后,利用實驗驗證了改進(jìn)算法的有效性.

為了有效對頻繁模式進(jìn)行挖掘,本文將改進(jìn)點與APFT 算法結(jié)合,由于新提出的連接預(yù)處理方法與緊湊樹結(jié)構(gòu)具有較好的可移植性,因此改進(jìn)點可與其它類似算法結(jié)合,且并不影響挖掘效率,相應(yīng)地還能增強原始算法處理數(shù)據(jù)流問題的能力.

下一步的研究工作包括：1)繼續(xù)完善算法,往并行計算方向擴(kuò)展；2)將該算法的思想擴(kuò)展到最大、閉頻繁模式的挖掘領(lǐng)域.