改進(jìn)的頻繁模式挖掘算法①

魏恩超,張德生,安平平

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

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

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

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

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

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

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

1 問(wèn)題陳述

1.1 頻繁模式挖掘

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

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

1.2 Apriori 算法

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

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

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

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

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

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

FP-tree 中每個(gè)節(jié)點(diǎn)由4 個(gè)域組成：項(xiàng)標(biāo)識(shí)itemname、節(jié)點(diǎn)計(jì)數(shù)item-count、節(jié)點(diǎn)鏈item-link和父節(jié)點(diǎn)指針item-parent.同時(shí)為了方便對(duì)樹(shù)進(jìn)行操作,FPtree 還包含一個(gè)頻繁項(xiàng)頭表header-table,它由兩個(gè)域組成：項(xiàng)標(biāo)識(shí)item-name和項(xiàng)元鏈鏈頭node-link,其中node-link 是指向FP-tree 中具有相同項(xiàng)標(biāo)識(shí)的首節(jié)點(diǎn)指針,FP-tree 中實(shí)線是父節(jié)點(diǎn)指針,虛線是節(jié)點(diǎn)鏈.FPtree 相關(guān)概念及結(jié)構(gòu)細(xì)節(jié)見(jiàn)文獻(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 算法主要包括兩個(gè)步驟,第一步是利用FP-growth 算法中構(gòu)造樹(shù)的方法構(gòu)造FP-tree；第二步是利用Apriori 算法挖掘FP-tree.在第二步中,需要添加一個(gè)名為N Table的附加節(jié)點(diǎn)表,表中的每個(gè)項(xiàng)由兩個(gè)域組成：Item-name和Item-support.Item-name 表示在條件子樹(shù)FPTj(j=1,2,···,n)中 節(jié)點(diǎn)的名稱,I tem-support表示與頻繁1-項(xiàng)集Ij(j=1,2,···,n)一起出現(xiàn)的節(jié)點(diǎn)數(shù),即項(xiàng)的支持度計(jì)數(shù).APFT 是最早將Apriori 算法與FP-tree 結(jié)合的算法,但由于Apriori 算法與FP-tree 自身的缺陷導(dǎo)致該算法仍存在一些不足,因此本文對(duì)APFT 中的連接步與樹(shù)構(gòu)造方法進(jìn)行了改進(jìn),使算法能有效處理數(shù)據(jù)流問(wèn)題.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ù)庫(kù)掃描次數(shù)以及增強(qiáng)算法的交互式挖掘與增量挖掘的方向改進(jìn).首先,將Apriori 算法的apriori_gen()函數(shù)中的連接步進(jìn)行優(yōu)化.由于連接步需要大量比較步驟,并且會(huì)產(chǎn)生大量無(wú)用的候選項(xiàng)集,因此增加了后續(xù)剪枝步和支持度計(jì)數(shù)步的時(shí)間開(kāi)銷.其次,將CP-tree[15]進(jìn)行擴(kuò)展,提出了一個(gè)新的樹(shù)結(jié)構(gòu)ECP-tree(Extension of Compact Pattern tree).由于在構(gòu)造CP-tree 的過(guò)程中包含所有項(xiàng),不論是頻繁項(xiàng)還是非頻繁項(xiàng)都參與了樹(shù)的構(gòu)造,因此占用了大量的內(nèi)存空間,并且會(huì)影響頻繁模式的挖掘效率.在新構(gòu)造的ECP-tree 中只包含頻繁項(xiàng),刪除了非頻繁項(xiàng),并且只經(jīng)過(guò)一次數(shù)據(jù)庫(kù)掃描就可以構(gòu)造出一棵緊湊的前綴樹(shù),新構(gòu)造的樹(shù)結(jié)構(gòu)不僅支持交互式挖掘而且也支持增量挖掘.

2.2 優(yōu)化連接步

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

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

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

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

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

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

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

算法2.Pretreatment Input：頻繁k-項(xiàng)集Fk Output：滿足連接條件的頻繁-項(xiàng)集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

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

表2 所有頻繁3-項(xiàng)集

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

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

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

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

表4 頻繁3-項(xiàng)集中每個(gè)項(xiàng)計(jì)數(shù)

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

2.3 新樹(shù)的構(gòu)造

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

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

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

圖2 插入階段后的I和T

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

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

圖4 移除未排序路徑

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

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

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

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

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

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

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

表7 mushroom 上不同算法運(yùn)行時(shí)間對(duì)比

表8 T10I4D100K 上不同算法運(yùn)行時(shí)間對(duì)比

圖8 mushroom 上運(yùn)行時(shí)間對(duì)比

圖9 T10I4D100K 上運(yùn)行時(shí)間對(duì)比

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

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

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

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