李校林，杜 托，劉 彪

(1.重慶郵電大學 通信新技術應用研究中心，重慶 400065； 2.重慶信科設計有限公司，重慶 400065)

(*通信作者電子郵箱dutuotuo@yeah.net)

基于B-list的快速頻繁模式挖掘算法

李校林1,2，杜 托1*，劉 彪1

(1.重慶郵電大學 通信新技術應用研究中心，重慶 400065； 2.重慶信科設計有限公司，重慶 400065)

(*通信作者電子郵箱dutuotuo@yeah.net)

針對現(xiàn)有的頻繁模式挖掘算法存在建樹復雜、挖掘效率低等問題，提出一種基于構造鏈表(B-list)的頻繁模式挖掘(BLFPM)算法。BLFPM使用一種新的數(shù)據(jù)結(jié)構B-list表示頻繁項集，通過連接兩個k-1-頻繁項集的B-list可以快速得到k-項集的支持度，避免了多次掃描數(shù)據(jù)庫；針對連接兩個B-list時間復雜度高的問題，給出了一種線性時間復雜度的連接方法，提高了BLFPM的時間效率；同時，BLFPM采用集合枚舉樹代表搜索空間，并使用子集非頻繁剪枝策略，減小了頻繁模式挖掘的搜索空間，提高了算法的執(zhí)行速度。實驗結(jié)果表明，與NSFI算法和prepost算法相比，BLFPM的時間效率提高約12%到29%，空間效率提高約10%到24%，對稀疏數(shù)據(jù)庫或稠密數(shù)據(jù)庫進行頻繁模式挖掘均可以得到良好的效果。

數(shù)據(jù)挖掘；模式挖掘；頻繁項集；遍歷構造樹；構造鏈表

0 引言

數(shù)據(jù)挖掘是從大量的數(shù)據(jù)中挖掘出隱含的、未知的、用戶可能感興趣的知識和規(guī)則的過程。關聯(lián)規(guī)則是數(shù)據(jù)挖掘中非常重要的一個研究方向，能夠找到事務之間隱含的人們可能感興趣的規(guī)則，從而為人們帶來巨大的價值。在當今大數(shù)據(jù)時代，如何在海量的數(shù)據(jù)中挖掘出有價值的關聯(lián)規(guī)則顯得尤為重要。

頻繁模式挖掘是關聯(lián)規(guī)則挖掘中最重要的一步，利用頻繁模式可以較容易地推導出關聯(lián)規(guī)則。Apriori算法是頻繁模式挖掘的經(jīng)典算法，由Agrawal等[1]于1994年提出。該算法利用逐層迭代的思想，由頻繁k-1-項集與自身進行連接、剪枝等步驟產(chǎn)生頻繁k-項集，從而挖掘出所有的頻繁模式。但是Apriori算法存在多次掃描數(shù)據(jù)庫以及產(chǎn)生大量候選項集的問題，對此學者們提出了一系列改進算法。例如，基于hash技術的直接散列剪枝(Direct Hashing and Pruning, DHP)算法[2]將產(chǎn)生的候選項集通過hash函數(shù)散列到不用的hash桶中，通過對hash桶中的項目進行計數(shù)，剔除不符合支持度要求的項目，從而得到頻繁項集。DHP算法本質(zhì)上是以空間換取時間的算法，面對大規(guī)模數(shù)據(jù)集時，算法效率將會急劇下降。基于抽樣(Sampling)技術的頻繁模式挖掘算法[3]首先從數(shù)據(jù)庫中抽取樣本數(shù)據(jù)進行運算后得到頻繁模式，然后用數(shù)據(jù)庫中剩余數(shù)據(jù)檢驗所挖掘頻繁模式的正確性。抽樣技術運行速度快，時間效率高，能夠快速挖掘出頻繁模式，但由于 Sampling 算法利用隨機抽樣法進行采樣，必然伴隨數(shù)據(jù)扭曲(data skew) 問題，導致挖掘結(jié)果具有較大的不確定性。BitTableFI算法[4]使用位表壓縮數(shù)據(jù)庫，然后使用位表數(shù)據(jù)結(jié)構及二進制的與或操作迭代挖掘頻繁項集，在產(chǎn)生候選項集及支持度計算方面均比Apriori算法更有效率。但是BitTableFI算法存在產(chǎn)生大量候選項集以及重復計算支持的問題，挖掘效率仍有待提高。趙學健等[5]提出了挖掘頻繁項集的正交鏈表算法(Orthogonal List Algorithm, OLA)。該算法首先將事務數(shù)據(jù)庫轉(zhuǎn)化為一個布爾矩陣，然后依據(jù)布爾矩陣構造正交鏈表，因此可以通過對正交鏈表進行操作來挖掘頻繁項集。除此之外，該算法優(yōu)化了連接和剪枝操作，提高了算法效率。OLA算法只需掃描數(shù)據(jù)庫一次，利用正交鏈表的優(yōu)勢可以快速挖掘出頻繁項集。雖然該算法利用正交鏈表這一能夠快速遍歷的數(shù)據(jù)結(jié)構，但是該算法在數(shù)據(jù)量較大或者項集過長時需要耗費大量的內(nèi)存，空間效率有待提高。

針對Apriori算法及其改進算法存在多次掃描數(shù)據(jù)庫、算法效率不高的問題，Han等[6]提出了采用分治策略的頻繁模式增長(Frequent Pattern growth，F(xiàn)P-growth)算法。該算法使用頻繁模式樹(Frequent Pattern tree， FP-tree)代表數(shù)據(jù)庫，然后利用遞歸構建條件FP-tree來挖掘頻繁項集。由于精簡的數(shù)據(jù)結(jié)構FP-tree能夠完整代表事務數(shù)據(jù)庫中的項，因此避免了對數(shù)據(jù)庫的多次掃描，挖掘效率較Apriori算法提升明顯。但是FP-growth算法需要兩次掃描數(shù)據(jù)庫來構建FP-tree，同時在挖掘過程中需要構建條件模式基和條件模式樹，從而會帶來巨大的時間與空間開銷。針對FP-growth算法需要兩次掃描數(shù)據(jù)庫以及需要掃描不含頻繁項的事務的問題，李也白等[7]提出了一種基于改進的FP-tree的頻繁模式挖掘算法。該算法深入分析了FP-tree的性質(zhì)與特點，對FP-tree的構造過程進行了改進，同時還利用哈希表來進行輔助存儲，提高了挖掘效率；但是該算法依舊采用模式增長來挖掘頻繁模式，挖掘效率有待提高。

Eclat算法使用垂直數(shù)據(jù)結(jié)構挖掘頻繁項集，能夠利用交集運算快速求得項集的支持度，提高挖掘效率[8]。但是Eclat利用候選項集的子集產(chǎn)生新的候選項集，這種方法產(chǎn)生的候選項集數(shù)量較Apriori更多，大大影響了算法的效率。除此之外，當Tidset數(shù)量龐大時，不僅會占用大量內(nèi)存，而且其交集運算會消耗大量時間，時間與空間開銷都很大。在此基礎上，Deng等[9]提出了prepost算法。該算法使用比FP-tree更精簡的數(shù)據(jù)結(jié)構——前序后序編碼樹(Pre-order and Post-order Code tree，PPC-tree)，前序后序兩次遍歷PPC-tree后，可以得到每個節(jié)點的pre-order和post-order，從而得到其對應的N-list。通過連接兩個頻繁k-1項集的N-list可以快速挖掘出頻繁項集。但是prepost算法中PPC-tree構建復雜，沒有對搜索空間進行剪枝，算法效率仍有待提高。Vo等[10]在N-list基礎上結(jié)合包含索引對搜索空間進行剪枝操作，提出了NSFI算法。該算法較prepost算法性能有一定提升，但是在面對大型數(shù)據(jù)庫時，仍舊存在建樹復雜、挖掘效率低的問題。

針對現(xiàn)有的頻繁模式挖掘算法存在建樹復雜、挖掘效率低等問題，本文提出了一種新的頻繁模式挖掘算法——基于構造鏈表(Building list，B-list)的頻繁模式挖掘(B-list Frequent Pattern Ming，BLFPM)算法。BLFPM首先掃描一次數(shù)據(jù)庫，得到所有的頻繁1-項集，將數(shù)據(jù)庫中所有事務的項按頻繁1-項集的支持度降序進行排列；然后通過構建TB-tree得到頻繁1-項集對應的B-list，通過對B-list進行連接操作即可快速得到候選項集的支持度，避免了頻繁掃描數(shù)據(jù)庫。在B-list的連接操作中，BLFPM使用了一種線性時間復雜度算法，有效解決了連接B-list的高復雜度問題;除此之外，BLFPM使用集合枚舉樹代表搜索空間，并使用子集非頻繁策略進行剪枝操作，減小了算法的搜索空間，提高了算法的執(zhí)行速度。實驗結(jié)果表明，BLFPM可以有效提高頻繁模式挖掘的時間和空間效率。

1 相關概念

1.1 問題描述

設I={i1,i2,…,im}是事務數(shù)據(jù)庫中所有不同項目的集合，DB={T1,T2,…,Tn}是包含n個事務的數(shù)據(jù)庫，事務Tk={i1,i2,…,it}代表不同項目的集合。設事務數(shù)據(jù)庫DB如表1所示(支持度取0.3)。

表1 事務數(shù)據(jù)庫DBTab. 1 An transaction database DB

定義1k-項集。對于集合X∈I,稱集合X為一個項集，包含k個項目的項集稱為k-項集。

定義2 支持度。對于給定的事務數(shù)據(jù)庫DB, 項集X的支持度是指DB中包含X的事務數(shù)與事務總數(shù)之比，記為σ(X)。設事務總數(shù)為|DB|,包含項集X的事務數(shù)為sup(X)，則X的支持度σ(X)=sup(X)/|DB|。

定義3 頻繁k-項集。對于給定的事務數(shù)據(jù)庫DB,min-sup為用戶給定的最小支持度，如果sup(X)≥min-sup×|DB|,則稱X為頻繁項集。如果X為k-項集，則稱為頻繁k-項集。

性質(zhì)1 頻繁項集的子集一定是頻繁項集；非頻繁項集的超集一定是非頻繁項集。

有了上述定義與性質(zhì)，頻繁模式挖掘問題就可以描述為利用性質(zhì)1找出事務數(shù)據(jù)庫中所有滿足用戶最小支持度的項集問題。

1.2 TB-tree

針對現(xiàn)有的頻繁模式挖掘算法使用的FP-tree[5]、PPC-tree[9]等數(shù)據(jù)結(jié)構挖掘效率低、建樹復雜等問題，本文算法采用了一種構造遍歷樹(Traversal when Building， TB-tree)結(jié)構[11]。TB-tree由root節(jié)點和項目的前綴子樹構成。項目的前綴子樹的每個節(jié)點包含五個部分： item-name代表項目名稱；count代表經(jīng)過這一節(jié)點的事務數(shù)目；parent-pointer指向當前節(jié)點的父節(jié)點；start-build代表此節(jié)點開始構造順序；finish-build代表此節(jié)點結(jié)束構造的順序。

同F(xiàn)P-tree相比,TB-tree不僅不需要指向具有相同節(jié)點名稱的指針node-link和存儲頻繁項集的頭表header table，而且TB-tree主要用于構建B-list，在構建完成B-list之后，可以從內(nèi)存中刪除。因此，使用TB-tree進行頻繁模式挖掘，不僅比使用FP-tree具有更快的建樹速度，而且內(nèi)存占用少，時間與空間開銷都更少。與PPC-tree相比，TB-tree的節(jié)點中不含pre-order和post-order，不需要通過前序和后序兩次遍歷得到每個節(jié)點的pre-order和post-order。TB-tree使用start-build與finish-build代替pre-order和post-order，其值能夠依據(jù)節(jié)點在TB-tree的構建順序得到，因此TB-tree可以在一次構建中完成，不需要額外的遍歷操作，比PPC-tree的建立具有更高的時間效率。文獻[11]利用TB-tree對數(shù)據(jù)庫進行壓縮，然后在此基礎上使用動態(tài)支持度閾值和包含索引策略來挖掘top-rank-k頻繁模式，而本文主要在TB-tree的基礎上通過采取有效的連接與剪枝策略來挖掘頻繁模式，給出了一種快速頻繁模式挖掘算法。TB-tree的構建算法如算法1所示。

算法1 構建TB-tree。

輸入 事務數(shù)據(jù)庫DB；

輸出 TB-tree，L1。

1) 掃描DB,得到頻繁1-項集L1，將其按項目支持度降序排列,將DB中的事務的項按L1的順序排列,創(chuàng)建root節(jié)點，初始化全局變量start=0,finish=0;p與q為數(shù)據(jù)庫中的項目，Node為TB-tree的節(jié)點

2) for each different first itempinDBdo

3) Call BuildTree(p,Node)

4) end for

5) end

function BuildTree(p,parent)

a) LetTPbe a list of transactions inDBwhich contain prefixp

b) Creat nodeN:

N.item-name=item-nameof the last item inp

N.count=count of transactions inTP

N.parent=parent

c)N.start-build=++start

d) for each different first itemqinTPdo

e) Call buildTree(p∪q,N)

f) end for

g)N.finish-build=++finish

end function

應用算法1構建表1所示數(shù)據(jù)庫的TB-tree如圖1所示。

圖1 DB對應的TB-treeFig. 1 TB-tree of the DB

1.3 B-list

依據(jù)TB-tree，本節(jié)給出B-list的定義與性質(zhì)。為了定義B-list，首先給出B-info-code的定義。

定義4 B-info-code。 對于TB-tree中的每一個節(jié)點N,[(N.start-build，N.finish-build)，N.count]稱為節(jié)點N的B-info-code。

性質(zhì)2 對于兩個不同的節(jié)點N1和N2，當且僅當N1.start-buildN2.finish-build同時成立時，N1才是N2的祖先節(jié)點。

證明 由TB-tree構建算法可知，祖先節(jié)點總是先于孩子節(jié)點構建，因此，祖先節(jié)點對應的start-build值總是小于孩子節(jié)點的start-build值；又因為祖先節(jié)點總是晚于孩子節(jié)點構建完成，因此祖先節(jié)點對應的finish-build值總是大于孩子節(jié)點的finish-build值。

性質(zhì)2還表明TB-tree中每一個節(jié)點與其B-info-code是一一對應的：一個節(jié)點對應唯一的B-info-code，一個B-info-code亦對應唯一的節(jié)點。因此節(jié)點的孩子祖先關系亦能由其對應的B-info-code來表示，給出如下定義。

定義5 B-info-code的孩子祖先關系。設X1：[(s1,f1)，c1]為節(jié)點N1的B-info-code，X2：[(s2,f2)，c2]為節(jié)點N2的B-info-code，當且僅當s1f2同時成立時，X1是X2的祖先。

定義6 1-項集的B-list。對于給定的TB-tree與節(jié)點N，所有名為N的節(jié)點的所有B-info-code構成的集合稱為其對應的B-list，記為BLN。其中所有B-info-code按照start-build遞增順序排列。

通過遍歷構建完成的TB-tree，可以得到所有頻繁1-項集的B-list。遍歷圖1所示TB-tree得到的所有頻繁1-項集的B-list如表2所示。

表2 圖1頻繁1-項集的B-listTab. 2 B-list of frequent 1-items for Fig. 1

定義7 2-項集的B-list。對于頻繁1-項集L1中不同的項i1，i2，i1在i2之前，i1對應的B-list為{[(s11,f11)，c11]，[(s12,f12)，c12]，…，[(s1n,f1n)，c1n]},i2對應的B-list為{[(s21,f21)，c21]，[(s22,f22)，c22]，…，[(s2m,f2m)，c2m]}，則i1i2的B-list可由如下計算-合并規(guī)則確定：

計算：對于任意[(s1i,f1i)，c1i](1≤i≤n)，判斷其是否為[(s2j,f2j)，c2j] (1≤j≤m)的祖先:如果是，將[(s1i,f1i)，c2j]添加到i1i2的B-list中;如果不是，則進行下一次判斷。經(jīng)過此步驟可以得到i1i2的B-list。

合并:對于i1i2的B-list中具有相同start-build與finish-build值的B-info-code{[(s1,f1)，c1],[(s1,f1)，c2], …,[(s1,f1)，cn]},將其合并為[(s1,f1)，c1+c2+…+cn]。

例如，連接項集C與D的B-list，首先比較[(3，10)，5]與[(4，4)，2]，發(fā)現(xiàn)[(3，10)，5]是[(4，4)，2]的祖先，則將[(3，10)，2]加入項集CD的B-list。同時[(3，10)，5]也是[(10，7)，1]的祖先，將[(3，10)，1]也加入到CD的B-list中，然后對CD的B-list進行合并操作，得到CD的B-list為[(3，10)，3]。

定義8k-項集的B-list。對于頻繁k-1-項集X=ixi1i2…ik-2與Y=iyi1i2…ik-2，其中k≥3。項集X對應的B-list為{[(s11,f11)，c11]，[(s12,f12)，c12]，…[(s1n,f1n)，c1n]},項集Y對應的B-list為{[(s21,f21)，c21]，[(s22,f22)，c22]，…，[(s2m,f2m)，c2m]}，則ixiyi1i2…ik-2的B-list可由如下計算-合并規(guī)則確定。

計算：對于任意[(s1i,f1i)，c1i](1≤i≤n)，判斷其是否為[(s2j,f2j)，c2j] (1≤j≤m)的祖先：如果是，將[(s1i,f1i)，c2j]添加到k-項集ixiyi1i2…ik-2的B-list中；如果不是，則進行下一次判斷。經(jīng)過此步驟可以得到k-項集ixiyi1i2…ik-2的B-list。

合并：對于k-項集ixiyi1i2…ik-2的B-list中具有相同start-build與finish-build的{ [(s1,f1)，c1],[(s1,f1)，c2], …,[(s1,f1)，cn]},將其合并為[(s1,f1)，c1+c2+…+cn]。

性質(zhì)3 設項集X的B-list為{[(s1,f1)，c1]，[(s2,f2)，c2]，…，[(sn,fn)，cn]},則項集X的支持數(shù)sup(X)=c1+c2+…+cn。

證明 由于項集X的B-list中每一個B-info-code[(s,f)，c]均與TB-tree中名為X的節(jié)點相對應，因此項集X的支持數(shù)為對應TB-tree中所有同名節(jié)點的count值之和，因此sup(X)=c1+c2+…+cn。

2 BLFPM算法

結(jié)合第1章的 TB-tree與B-list結(jié)構，本章提出一種新的頻繁模式挖掘算法——BLFPM算法。BLFPM使用B-list表示頻繁項集，通過對B-list進行操作可以快速挖掘出所有的頻繁項集。針對Apriori算法在計算候選項集支持度時需要多次掃描數(shù)據(jù)庫的問題，BLFPM通過連接對應項集的B-list，可以直接得到候選項集的支持度，不需要對數(shù)據(jù)庫進行掃描；針對B-list連接的高復雜度問題，BLFPM給出了一種線性時間復雜度的連接方法，大大提高了算法時間效率；對于搜索空間大的問題，BLFPM使用集合枚舉樹代表搜索空間并使用子集非頻繁剪枝策略，有效減小了候選項集的搜索空間，提高了算法的執(zhí)行速度。BLFPM主要包含四個步驟：1)掃描數(shù)據(jù)庫，得到頻繁1-項集L1，構建TB-tree；2)遍歷TB-tree,得到頻繁1-項集L1對應的B-listBL1;3)挖掘出所有的頻繁2-項集L2；4)挖掘出所有的頻繁k-項集(k>2)。其中步驟1的算法已由第1章給出，本章主要介紹后面三個步驟。

2.1 計算BL1與挖掘頻繁2-項集L2

按照start-build順序遍歷TB-tree，便可得到所有頻繁1-項集L1的B-list。文獻[12]表明，基于Apriori算法改進的頻繁模式挖掘算法在挖掘頻繁2-項集時，由于需要連接頻繁1-項集，從而會產(chǎn)生大量的候選2-項集，時間和空間開銷都很大，會嚴重影響算法的時間和空間效率。因此，本節(jié)提出了一種基于TB-tree的頻繁2-項集快速挖掘算法并將其應用到BLFPM算法中。該算法按照start-build的順序遍歷TB-tree，對于每一個節(jié)點N,設NA為其祖先節(jié)點，只需要將其與其祖先進行連接，便可得到相應的候選2-項集NNA。使用這種方法不需要產(chǎn)生沒有祖先-孩子關系的候選2-項集，減少了候選2-項集的數(shù)量，提高了算法的時間效率。將所有候選2-項集的支持度與用戶給定的支持度進行比較，刪除不符合支持度要求的2-項集，就可以得到所有的頻繁2-項集L2。為了提高BLFPM算法的執(zhí)行效率，將其步驟2與步驟3在同一次遍歷TB-tree中完成，如算法2所示。

算法2 挖掘BL1與頻繁2-項集L2。

輸入 TB-tree，L1;

輸出BL1，L2。

1) Creatarray=int [L1.length][L1.length],

L1[k].sequence=k

2) for each nodeNof TB-tree accessed by start-build traversal do

3) if(N.item-name=L1[k]) then

4) insert [(N.start-build,N.finish-build),N.count] into

BL1[k]

5) end if

6) for each nodeNA， ancestor ofNdo

7)array[N.sequence][NA.sequence]+=N.count

8) end for

9) end for

10) for each element inarraydo

11) if(array[i][j]≥min_sup×|DB|) then

12)

insertL1[i] ∪L1[j] intoL2

13) end if

14) end for

2.2 挖掘頻繁k-項集

在挖掘頻繁k-項集的過程中，首先需要連接兩個頻繁k-1-項集得到候選k-項集，然后計算候選k-項集的支持度是否符合用戶設定的最小支持度要求，進而得到頻繁k-項集。由于這種方式連接復雜且會產(chǎn)生很多無用的候選k-項集，BLFPM使用集合枚舉樹來代表搜索空間，直接遍歷集合枚舉樹便可得到候選k-項集。與此同時，BLFPM利用性質(zhì)1，使用子集非頻繁剪枝策略對集合枚舉樹進行剪枝操作，大大減小了頻繁模式挖掘的搜索空間，提高了算法的執(zhí)行速度。利用集合枚舉樹得到候選k-項集之后，BLFPM需要對相應的頻繁k-1-項集的B-list進行連接操作，從而得到k-項集的B-list，因此B-list的連接效率會直接影響算法最終的挖掘效率。針對此問題，本節(jié)提出了一種高效的B-list連接策略并將其應用到BLFPM中，能大大提高BLFPM算法的效率。

2.2.1 集合枚舉樹及其剪枝策略

集合枚舉樹是Burdick等[13]于2005年提出來的。利用集合枚舉樹可以完整地描述所有可能出現(xiàn)的頻繁項集。由性質(zhì)1可知，所有非頻繁子集的超集都是非頻繁項集，利用此性質(zhì)可以對集合枚舉樹進行剪枝操作，從而減小搜索空間，提高算法效率。得到頻繁k-項集之后，利用k-項集刪除集合枚舉樹中代表非頻繁項集及其超集的節(jié)點，可以大大簡化集合枚舉樹。本文例子利用頻繁2-項集L2進行剪枝操作后的集合枚舉樹如圖2所示。從圖中可以看出，候選頻繁3-項集只有CAB、CAE兩項，遠遠小于由頻繁2-項集連接產(chǎn)生的候選3-項集的數(shù)量。

圖2 利用L2剪枝后的集合枚舉樹Fig. 2 Set-enumeration tree pruned by L2

2.2.2 B-list連接策略

連接兩個B-list理論上具有O(m×n)復雜度，通過研究發(fā)現(xiàn)性質(zhì)4，可以將其復雜度降為O(m+n)。

性質(zhì)4 設項集X對應的B-list為{[(s11,f11)，c11]，[(s12,f12)，c12]，…，[(s1n,f1n)，c1n]},項集Y對應的B-list為{[(s21,f21)，c21]，[(s22,f22)，c22]，…，[(s2m,f2m)，c2m]}，如果[(s1i,f1i)，c1i](1≤i≤n)是[(s2j,f2j)，c2j](1≤j≤m)的祖先，則項集X中其余的B-info-code都不是[(s2j,f2j)，c2j]的祖先。

證明 如果[(s1i,f1i)，c1i]是[(s2j,f2j)，c2j]的祖先，設N1是[(s1i,f1i)，c1i]所代表的節(jié)點，N2是[(s2j,f2j)，c2j]所代表的節(jié)點，N為[(s1k,f1k)，c1k](k≠i)所代表的節(jié)點，易知N1是N2的祖先。假設N為N2的祖先，則N1與N必定存在孩子祖先關系。由于[(s1i,f1i)，c1i]與[(s1k,f1k)，c1k]均為項集X所對應的B-info-code，因此N1與N所代表節(jié)點具有相同的項目名稱，由TB-tree的構建算法可知，具有相同項目名稱的節(jié)點不可能存在孩子祖先關系，因此假設不成立，[(s1k,f1k)，c1k]不可能是[(s2j,f2j)，c2j]的祖先。

證畢。

利用性質(zhì)4連接兩個B-list的方法如下(以性質(zhì)4中項集X和Y為例)。

1)首先判斷[(s1i,f1i)，c1i]與[(s2j,f2j)，c2j]之間的祖先-后代關系

2)如果[(s1i,f1i)，c1i]是[(s2j,f2j)，c2j]的祖先，則將[(s1i,f1i)，c2j]添加到項集XY的B-list中并進行合并操作。如果[(s2j+1,f2j+1)，c2j+1]存在，則執(zhí)行1)，判斷[(s1i,f1i)，c1i]與[(s2j+1,f2j+1)，c2j+1]之間的祖先-后代關系；如果[(s2j+1,f2j+1)，c2j+1]不存在，則算法結(jié)束。

3)如果[(s1i,f1i)，c1i]不是[(s2j,f2j)，c2j]的祖先，則存在兩種情況，s1i大于s2j或s1i小于s2j。

如果s1i大于s2j，則判斷[(s2j+1,f2j+1)，c2j+1]是否存在:如果存在則執(zhí)行1)，判斷[(s1i,f1i)，c1i]與[(s2j+1,f2j+1)，c2j+1]之間的祖先-后代關系；如果[(s2j+1,f2j+1)，c2j+1]不存在，則算法結(jié)束。

如果s1i小于s2j，則判斷[(s1i+1,f1i+1)，c1i+1]是否存在:如果存在則執(zhí)行1)，判斷[(s1i+1,f1i+1)，c1i+1]與[(s2j,f2j)，c2j]之間的祖先-后代關系;如果[(s1i+1,f1i+1)，c1i+1]不存在，則算法結(jié)束。

例如，連接項集A與E的B-list，首先比較[(1，2)，1]與[(5，3)，1]，發(fā)現(xiàn)[(1，2)，1]不是[(5，3)，1]的祖先且1﹤5，則比較[(6，9)，3]與[(5，3)，1]，比較得知[(6，9)，3]不是[(5，3)，1]的祖先且6﹥5，則轉(zhuǎn)向比較[(6，9)，3]與[(7，5)，1]，發(fā)現(xiàn)[(6，9)，3]是[(7，5)，1]的祖先，因此將[(6，9)，1]加入項集AE的B-list，繼續(xù)比較[(6，9)，3]與[(9，6)，1]，發(fā)現(xiàn)[(6，9)，3]是[(9，6)，1]的祖先，因此將[(6，9)，1]加入項集AE的B-list，然后對AE的B-list進行合并操作，得到項集AE最終的B-list為[(9，6)，2]，算法結(jié)束。

同prepost算法和NSFI算法相比，BLFPM不需要兩次遍歷TB-tree來得到B-list，而是在TB-tree的構建過程中完成B-list的構建，節(jié)約了兩次遍歷TB-tree的時間開銷；BLFPM利用集合枚舉樹對候選項集進行剪枝，減少了候選項集的產(chǎn)生，減少了產(chǎn)生大量候選項集的時間與空間開銷。由于BLFPM采用的TB-tree結(jié)構可以大量壓縮稠密數(shù)據(jù)庫的數(shù)據(jù)量，使其能夠快速挖掘稠密數(shù)據(jù)庫中的頻繁模式，又因為其采用的剪枝策略，對稀疏數(shù)據(jù)庫進行挖掘也有較高的效率，因此BLFPM不僅適用于稠密數(shù)據(jù)庫，在稀疏數(shù)據(jù)庫中也有良好的表現(xiàn)。

3 實驗結(jié)果與分析

為了驗證算法的性能，將本文算法BLFPM與prepost和NSFI算法從運行時間和內(nèi)存占用兩個方面進行對比。實驗環(huán)境為Intel Core i5 3.1 GHz CPU,2 GB內(nèi)存，Windows 7操作系統(tǒng)。所有算法均用Java語言實現(xiàn)，在同一臺機器上運行，保證了實驗結(jié)果的公平性。實驗所用數(shù)據(jù)集為兩個常用數(shù)據(jù)集，分別為Accidents、Retail。實驗通過改變最小支持度進行頻繁模式挖掘，記錄算法運行時間和內(nèi)存占用情況，其中運行時間實驗結(jié)果如圖3所示，內(nèi)存占用實驗結(jié)果如圖4所示。

在同一數(shù)據(jù)集條件下，將BLFPM算法的挖掘結(jié)果與prepost算法和NSFI算法的挖掘結(jié)果進行比較分析，發(fā)現(xiàn)在最小支持度相同時，挖掘出的頻繁模式的數(shù)量和內(nèi)容完全一致，表明本文算法是正確的。由圖3(a)與圖3(b)可以看出，隨著最小支持度的增大，三種算法運行時間都隨之降低，但是BLFPM始終比prepost和NSFI運行速度快，表明本文算法具有較高的時間效率。由圖4(a)與圖4(b)可以看出，本文算法的內(nèi)存消耗始終小于prepost和NSFI，表明本文算法也具有較高的空間效率。造成這種結(jié)果的原因是BLFPM建樹簡單且采用集合枚舉樹代表搜索空間，同時使用高效的子集非頻繁剪枝策略縮小了搜索空間，從而加快了算法執(zhí)行，減小了內(nèi)存消耗。理論分析和實驗結(jié)果表明，BLFPM算法不僅適用于挖掘稠密數(shù)據(jù)庫中的頻繁模式，在挖掘稀疏數(shù)據(jù)庫中的頻繁模式時也有良好表現(xiàn)。

圖3 運行時間對比Fig. 3 Comparison of runtime

圖4 內(nèi)存消耗對比Fig. 4 Comparison of memory usage

4 結(jié)語

本文提出了一種新的頻繁模式挖掘算法——BLFPM。該算法使用B-list代表頻繁項集，采用集合枚舉樹與子集非頻繁剪枝策略縮減搜索空間，使用高效的B-list連接策略，從而可以快速挖掘出頻繁項集。實驗結(jié)果表明BLFPM算法優(yōu)于現(xiàn)有效率較高的prepost算法與NSFI算法。在當前大數(shù)據(jù)環(huán)境下，將 BLFPM與Hadoop結(jié)合，研究出能夠并行處理大數(shù)據(jù)的頻繁模式挖掘算法，將會是下一步的研究方向。

References)

[1] AGRAWAL R, SRIKANT R. Fast algorithms for mining association rules [C]// VLDB 1994: Proceedings of the 20th VLDB International Conference on Very Large Data Bases. San Francisco, CA: Morgan Kaufmann Publishers Inc., 1994: 487-499.

[2] SAHOO J, DAS KUMAR A, GOSWAMI A. An efficient approach for mining association rules from high utility itemsets [J]. Expert Systems with Applications, 2015, 42(13): 5754-5778.

[3] CAMPAGNA A, PAGH R. Finding associations and computing similarity via biased pair sampling [C]// ICDM ’09: Proceedings of the 2009 Ninth IEEE International Conference on Data Mining. Washington, DC: IEEE Computer Society, 2009: 61-70.

[4] ATTEYA W A, DAHAL K, HOSSAIN M A. Distributed BitTable multi-Agent association rules mining algorithm [C]// KES ’11: Proceedins of the 15th International Conference on Knowledge-Based and Intelligent Information and Engineering Systems, LNCS 6881. Berlin: Springer-Verlag, 2011: 151-160.

[5] 趙學健,孫知信,袁源,等.一種正交鏈表存儲的改進Apriori算法[J]. 小型微型計算機系統(tǒng),2016,37(10):2291-2295. (ZHAO X J, SUN Z X, YUAN Y, et al. An improved apriori algorithm based on orthogonal storage [J]. Journal of Chinese Computer Systems, 2016, 37(10): 2291-2295.)

[6] HAN J, PEI J, YIN Y. Mining frequent patterns without candidate generation [J]. ACM SIGMOD Record, 2000, 29(2): 1-12.

[7] 李也白,唐輝,張淳，等.基于改進的FP-tree的頻繁模式挖掘算法[J]. 計算機應用,2011,31(1):101-103. (LI Y B, TANG H, ZHANG C, et al. Frequent pattern mining algorithm based on improved FP-tree [J]. Journal of Computer Applications, 2011, 31(1): 101-103.)

[8] MA Z, YANG J, ZHANG T, et al. An improved eclat algorithm for mining association rules based on increased search strategy [J]. International Journal of Database Theory and Application, 2016, 9(5): 251-266.

[9] DENG Z, WANG Z, JIANG J. A new algorithm for fast mining frequent itemsets using N-lists [J]. SCIENCE CHINA Information Sciences, 2012, 55(9): 2008-2030.

[10] VO B, LE T, COENEN F, et al. Mining frequent itemsets using the N-list and subsume concepts [J]. International Journal of Machine Learning and Cybernetics, 2016, 7(2): 253-265.

[11] DAM T-L, LI K, FOURNIER-VIGER P, et al. An efficient algorithm for mining top-rank-kfrequent patterns [J]. Applied Intelligence, 2016, 45(1): 96-111.

[12] MOHAMED M H, DARWIEESH M M. Efficient mining frequent itemsets algorithms [J]. International Journal of Machine Learning and Cybernetics, 2014, 5(6): 823-833.

[13] BURDICK D, CALIMLIM M, FLANNICK J, et al. MAFIA: a maximal frequent itemset algorithm [J]. IEEE Transactions on Knowledge and Data Engineering, 2005, 17(11): 1490-1504.

This work is partially supported by the Chongqing Postgraduate Research Innovation Fund (CYS15166).

LIXiaolin, born in 1968, M. S., senior engineer. His research interests include mobile communication, big data.

DUTuo, born in 1993, M. S. candidate. His research interests include big data, data mining.

LIUBiao, born in 1991, M. S. candidate. His research interests include distributed computing, data mining.

FastalgorithmforminingfrequentpatternsbasedonB-list

LI Xiaolin1,2, DU Tuo1*, LIU Biao1

(1.InstituteofAppliedCommunicationTechnology,ChongqingUniversityofPostsandTelecommunications,Chongqing400065,China；2.ChongqingInformationTechnologyDesigningCompanyLimited,Chongqing400065,China)

In order to solve the problems in the existing frequent pattern mining algorithms, such as complex tree building and low mining efficiency, a high-performance algorithm for mining frequent patterns was proposed, namely B-List Frequent Pattern Mining (BLFPM). A new data structure of Building list (B-list) was employed to represent frequent itemsets, and the frequent patterns were directly discovered by intersecting two B-lists without scanning the database. Aiming at the high time complexity of connecting two B-lists, a linear time complexity connection method was proposed to improve the time efficiency of BLFPM. Besides, set-enumeration search tree and an efficient pruning strategy were adopted to greatly reduce the search space and speed up the execution. Compared to N-list and Subsume-based algorithm for mining Frequent Itemsets (NSFI) and prepost algorithm, the time efficiency of BLFPM was improved by about 12% to 29%, and the space efficiency of BLFPM was improved by about 10% to 24%. The experimental results show that BLFPM has good performance for both sparse database and intensive database.

data mining; pattern mining; frequent itemset; Traversal when Building tree (TB-tree); Building list (B-list)

TP311.13

A

2016- 12- 13;

2017- 03- 03。

重慶市研究生科研創(chuàng)新基金資助項目(CYS15166)。

李校林(1968—)，男，江西寧都人，正高級工程師，碩士，主要研究方向：移動通信、大數(shù)據(jù)； 杜托(1993—)，男，河南三門峽人，碩士研究生，主要研究方向：大數(shù)據(jù)、數(shù)據(jù)挖掘； 劉彪(1991—)，男，河南南陽人，碩士研究生，主要研究方向：分布式計算、數(shù)據(jù)挖掘。

1001- 9081(2017)08- 2357- 05

10.11772/j.issn.1001- 9081.2017.08.2357