李校林，杜 托，劉 彪

(1.重慶郵電大學(xué) 通信新技術(shù)應(yīng)用研究中心，重慶 400065； 2.重慶信科設(shè)計(jì)有限公司，重慶 400065)

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

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

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

(1.重慶郵電大學(xué) 通信新技術(shù)應(yīng)用研究中心，重慶 400065； 2.重慶信科設(shè)計(jì)有限公司，重慶 400065)

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

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

數(shù)據(jù)挖掘；模式挖掘；頻繁項(xiàng)集；遍歷構(gòu)造樹；構(gòu)造鏈表

0 引言

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

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

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

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

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

1 相關(guān)概念

1.1 問題描述

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

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

定義1k-項(xiàng)集。對(duì)于集合X∈I,稱集合X為一個(gè)項(xiàng)集，包含k個(gè)項(xiàng)目的項(xiàng)集稱為k-項(xiàng)集。

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

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

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

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

1.2 TB-tree

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

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

算法1 構(gòu)建TB-tree。

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

輸出 TB-tree，L1。

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

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

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

圖1 DB對(duì)應(yīng)的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。 對(duì)于TB-tree中的每一個(gè)節(jié)點(diǎn)N,[(N.start-build，N.finish-build)，N.count]稱為節(jié)點(diǎn)N的B-info-code。

性質(zhì)2 對(duì)于兩個(gè)不同的節(jié)點(diǎn)N1和N2，當(dāng)且僅當(dāng)N1.start-buildN2.finish-build同時(shí)成立時(shí)，N1才是N2的祖先節(jié)點(diǎn)。

證明 由TB-tree構(gòu)建算法可知，祖先節(jié)點(diǎn)總是先于孩子節(jié)點(diǎn)構(gòu)建，因此，祖先節(jié)點(diǎn)對(duì)應(yīng)的start-build值總是小于孩子節(jié)點(diǎn)的start-build值；又因?yàn)樽嫦裙?jié)點(diǎn)總是晚于孩子節(jié)點(diǎn)構(gòu)建完成，因此祖先節(jié)點(diǎn)對(duì)應(yīng)的finish-build值總是大于孩子節(jié)點(diǎn)的finish-build值。

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

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

定義6 1-項(xiàng)集的B-list。對(duì)于給定的TB-tree與節(jié)點(diǎn)N，所有名為N的節(jié)點(diǎn)的所有B-info-code構(gòu)成的集合稱為其對(duì)應(yīng)的B-list，記為BLN。其中所有B-info-code按照start-build遞增順序排列。

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

表2 圖1頻繁1-項(xiàng)集的B-listTab. 2 B-list of frequent 1-items for Fig. 1

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

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

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

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

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

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

合并：對(duì)于k-項(xiàng)集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 設(shè)項(xiàng)集X的B-list為{[(s1,f1)，c1]，[(s2,f2)，c2]，…，[(sn,fn)，cn]},則項(xiàng)集X的支持?jǐn)?shù)sup(X)=c1+c2+…+cn。

證明 由于項(xiàng)集X的B-list中每一個(gè)B-info-code[(s,f)，c]均與TB-tree中名為X的節(jié)點(diǎn)相對(duì)應(yīng)，因此項(xiàng)集X的支持?jǐn)?shù)為對(duì)應(yīng)TB-tree中所有同名節(jié)點(diǎn)的count值之和，因此sup(X)=c1+c2+…+cn。

2 BLFPM算法

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

2.1 計(jì)算BL1與挖掘頻繁2-項(xiàng)集L2

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

算法2 挖掘BL1與頻繁2-項(xiàng)集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-項(xiàng)集

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

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

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

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

2.2.2 B-list連接策略

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

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

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

證畢。

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

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

2)如果[(s1i,f1i)，c1i]是[(s2j,f2j)，c2j]的祖先，則將[(s1i,f1i)，c2j]添加到項(xiàng)集XY的B-list中并進(jìn)行合并操作。如果[(s2j+1,f2j+1)，c2j+1]存在，則執(zhí)行1)，判斷[(s1i,f1i)，c1i]與[(s2j+1,f2j+1)，c2j+1]之間的祖先-后代關(guān)系；如果[(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]之間的祖先-后代關(guān)系；如果[(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]之間的祖先-后代關(guān)系;如果[(s1i+1,f1i+1)，c1i+1]不存在，則算法結(jié)束。

例如，連接項(xiàng)集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]加入項(xiàng)集AE的B-list，繼續(xù)比較[(6，9)，3]與[(9，6)，1]，發(fā)現(xiàn)[(6，9)，3]是[(9，6)，1]的祖先，因此將[(6，9)，1]加入項(xiàng)集AE的B-list，然后對(duì)AE的B-list進(jìn)行合并操作，得到項(xiàng)集AE最終的B-list為[(9，6)，2]，算法結(jié)束。

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

3 實(shí)驗(yàn)結(jié)果與分析

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

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

圖3 運(yùn)行時(shí)間對(duì)比Fig. 3 Comparison of runtime

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

4 結(jié)語

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

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] 趙學(xué)健,孫知信,袁源,等.一種正交鏈表存儲(chǔ)的改進(jìn)Apriori算法[J]. 小型微型計(jì)算機(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] 李也白,唐輝,張淳，等.基于改進(jìn)的FP-tree的頻繁模式挖掘算法[J]. 計(jì)算機(jī)應(yīng)用,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)新基金資助項(xiàng)目(CYS15166)。

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

1001- 9081(2017)08- 2357- 05

10.11772/j.issn.1001- 9081.2017.08.2357