魏恩超,張德生,安平平

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

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

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

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

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

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

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

1 問題陳述

1.1 頻繁模式挖掘

設I={I1,I2,···,Im}是所有項的集合,不失一般性,I中的項按字典順序排列,即I1＜···＜Im.T為一個事務,每個事務都由唯一的標識符TID和與之對應的項集Item(T)(Item(T)?I)構成,所有事務構成了事務數(shù)據(jù)庫D,D中包含事務的個數(shù)稱為數(shù)據(jù)庫的大小,記為S ize(D).設X?I為一個項集,項集中包含項的個數(shù)叫做項集的長度,記為Length(X),即Length(X)=|X|,長度為k的項集稱為k-項集.事務T包含項集X,當且僅當X?Item(T),項集X的支持度計數(shù) σ (X)定 義為數(shù)據(jù)庫D中包含項集X的事務數(shù),即σ (X)=|{T|T∈D∧X?Item(T)}|,項集X的支持度sup(X) 定義為包含項集X的事務在數(shù)據(jù)庫D中所占的比例,即sup(X)=σ(X)/S ize(D).項集X為頻繁模式,當且僅當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,設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進行剪枝,生成頻繁k-項集Fk.如果候選k-項集的一個(k-1)項 子集不在Fk-1中,則該候選項集為非頻繁項集,否則需要遍歷數(shù)據(jù)庫進行支持數(shù)統(tǒng)計,進一步驗證Ck是否頻繁.

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

1.3 FP-tree 結構

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

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

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

圖1 FP-tree 結構

1.4 APFT 算法

APFT 算法[10]使用Apriori 算法挖掘基于FP-tree的頻繁模式,該算法仍采用分治策略.APFT 算法主要包括兩個步驟,第一步是利用FP-growth 算法中構造樹的方法構造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 結合的算法,但由于Apriori 算法與FP-tree 自身的缺陷導致該算法仍存在一些不足,因此本文對APFT 中的連接步與樹構造方法進行了改進,使算法能有效處理數(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 改進算法

2.1 算法改進思想

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

2.2 優(yōu)化連接步

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

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

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

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

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

反證法：假設包含項 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,可對連接步進行優(yōu)化,在連接之前進行預處理,刪除不滿足條件的Fk.預處理過程的偽代碼如下所示：

算法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)化流程,用以下示例說明具體過程.假設表2是事務數(shù)據(jù)庫產(chǎn)生的所有頻繁3-項集F3.

表2 所有頻繁3-項集

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

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

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

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

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

表5 預處理后的頻繁3-項集

2.3 新樹的構造

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

本文對分支排序方法(BSM)進行了改進,使該算法能夠適應新提出的樹結構.在改進方法中,如果路徑?jīng)]有按照新的排序順序進行排序,則將該路徑刪除,并刪除非頻繁的項,將剩余的頻繁項按排序順序排列到一個臨時數(shù)組中,最后再按順序插入樹中,重復此過程最終將得到一棵緊湊的模式樹.改進的分支排序方法(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)}

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

圖2 插入階段后的I和T

圖3 重排I 構造Isort

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

圖4 移除未排序路徑

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

3 實驗分析

為驗證所提方法的有效性,將改進方法運用到APFT 算法中來挖掘頻繁模式,且與原始APFT 算法、FP-Growth 算法以及Apriori 算法進行比較.本文算法實驗平臺為：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ù)集上進行對比試驗,每組試驗的參數(shù)都是不變的,都是通過改變最小支持度閾值從而記錄算法的運行時間,算法運行的時間越小代表算法的挖掘速度越快.

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

圖7 重構后的最終樹

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

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

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

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

圖8 mushroom 上運行時間對比

圖9 T10I4D100K 上運行時間對比

4 結束語

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

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

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