基于格的快速頻繁項(xiàng)集挖掘算法＊

劉彩蘋，毛建頻，毛建旭，屈衛(wèi)蘭，蔡玉武

（1.湖南大學(xué) 信息科學(xué)與工程學(xué)院，湖南 長沙 410082；2.撫州職業(yè)技術(shù)學(xué)院 信息工程系，江西 撫州 344000；3.湖南大學(xué) 電氣與信息工程學(xué)院，湖南 長沙 410082）

頻繁項(xiàng)集挖掘是數(shù)據(jù)挖掘中的一類重要挖掘問題，廣泛應(yīng)用于關(guān)聯(lián)規(guī)則挖掘、相關(guān)性分析、入侵檢測(cè)、序列挖掘、分類分析、聚類分析、Web挖掘、XML挖掘等諸多數(shù)據(jù)挖掘任務(wù).長期以來，人們對(duì)頻繁模式的挖掘進(jìn)行了大量深入的研究工作.Han等人提出了一種比Apriori算法快一個(gè)數(shù)量級(jí)的FP－growth算法[1].隨后，各國的研究者們提出了許多其他改進(jìn)算法，如Koh等人提出的基于樹的高效頻繁項(xiàng)集挖掘算法[2]，李也白等人用一種輔助存儲(chǔ)結(jié)構(gòu)提高了查詢的效率[3]，Nguyen利用矩陣提出的頻繁項(xiàng)集挖掘算法[4]，郭宇紅等人提出的反向頻繁項(xiàng)集挖掘算法[5]，Zeng等人提出了加權(quán)關(guān)聯(lián)規(guī)則挖掘算法[6].Jalan提出了一種非遞歸頻繁項(xiàng)集挖掘算法[7].Adnan提出一種自適應(yīng)的頻繁項(xiàng)集挖掘算法[8].趙強(qiáng)利提出一種快速選擇性集成算法[9].范明提出一種不生成條件FP－樹的算法[10].譚軍提出了一種單遍掃描頻繁模式算法[11].

FP－growth算法開辟了有效挖掘頻繁模式的新途徑.然而，它的時(shí)間和空間效率還不足夠高，仍需改進(jìn).FP－growth算法的主要問題是建樹過程中必須將提供頻繁項(xiàng)集的數(shù)據(jù)全部壓縮到一棵頻繁模式樹（或FP－樹），在挖掘時(shí)，由長度為1的頻繁模式（初始后綴模式）開始，遞歸的構(gòu)造條件FP－樹進(jìn)行挖掘，在建樹和挖掘過程中都需要占用大量的內(nèi)存.當(dāng)數(shù)據(jù)庫很大，或者數(shù)據(jù)庫中的頻繁1－項(xiàng)集的數(shù)目很大時(shí)，運(yùn)行速度將大為降低；更有甚者，可能由于無法構(gòu)造基于內(nèi)存的FP－樹，該算法將不能有效地工作.

本文結(jié)合大型數(shù)據(jù)庫本身的特性，在分析FP－growth算法的基礎(chǔ)上，提出了一種基于格的大型數(shù)據(jù)庫頻繁模式挖掘算法LFP－growth.實(shí)驗(yàn)和分析表明，在挖掘大型數(shù)據(jù)庫時(shí)，LFP－growth算法具有較好的時(shí)間和空間效率.

1 基本概念和問題的描述

為方便討論，以事務(wù)數(shù)據(jù)庫為背景.設(shè)I＝｛i1，i2，…，im｝為所有項(xiàng)目的集合，D＝ ｛T1，T2，…，Tn｝為事務(wù)數(shù)據(jù)庫，其中每個(gè)事務(wù)Ti（i∈[1，…，n]）有一個(gè)惟一的標(biāo)識(shí)TID.表1中的事務(wù)數(shù)據(jù)庫是本文的示例數(shù)據(jù)庫.該數(shù)據(jù)庫中事務(wù)已經(jīng)按照各項(xiàng)的支持度計(jì)數(shù)遞增地將各事務(wù)中的項(xiàng)重新排列.

在事務(wù)數(shù)據(jù)庫中挖掘頻繁項(xiàng)集的問題可以描述為：給定事務(wù)數(shù)據(jù)庫D和最小支持度閾值minsup，挖掘所有的頻繁項(xiàng)集.

定義1[12]設(shè)（A，≤）為一個(gè)偏序集，如果對(duì)任意的x，y∈A，都存在x，y的上確界和下確界，則稱A關(guān)于偏序“≤”構(gòu)成一個(gè)格，并稱“≤”是A上的一個(gè)格序.

定義2[12]設(shè)P（k）是格P的子格，如果對(duì)任意的x，y?P（k），且x∪y∈P（k）且x∩y?P（k），則稱P（k）是格P的一個(gè)子格.

表1 事務(wù)數(shù)據(jù)庫Tab.1 Transaction databaseD

圖1中利用等價(jià)關(guān)系將P（I）劃分為互不相交的P（a），P（e），P（b），P（d），P（c）5個(gè)子網(wǎng)格（等價(jià)類），并且是有序的.LFP－growth算法采用的是基于前綴的分類，即P（k）子格表示所有前綴為k的項(xiàng)集構(gòu)成的子網(wǎng)格.如，P（e）＝ ｛｛ebdc｝｛ed｝｛edc｝｝.

圖中實(shí)線圈起的項(xiàng)集表示在樣例數(shù)據(jù)庫中有該事務(wù)，虛線圈起的項(xiàng)集表示沒有該事務(wù).

圖1 格P（I）的劃分Fig.1 Partition of latticeP（I）

定義3 令α表示I上的約束表達(dá)式，項(xiàng)集約束表達(dá)式α以合取范式（CN F）的形式，即k1∧k2∧…∧ki（ki∈I，即每一合取項(xiàng)要么是I中的一個(gè)項(xiàng)目，要么是I中一個(gè)項(xiàng)目的補(bǔ)項(xiàng).α＝（a∧e∧?b），該約束表達(dá)式表示，該集合是包含了｛ae｝但不包含｛b｝的項(xiàng)集集合.

2 LFP－growth算法

2.1 算法基本思想

令L（P（k）｜α）（k∈I）表示在格P（k）上滿足約束表達(dá)式α的頻繁項(xiàng)集，令擴(kuò)充格P（k）＾（k∈I）表示在P（I）中所有包含項(xiàng)目k的項(xiàng)集.

定理1α合取式（k1∧k2∧ …∧ki）（ki∈I）的首項(xiàng)ki是P（I）的第t個(gè)等價(jià)類，則滿足約束表達(dá)式α的頻繁集必在集中P（I）的前t個(gè)子格中.

證明 由等價(jià)類的性質(zhì)，可推出P（I）＝P（a）∪P（e）∪…∪P（c），而且子格之間項(xiàng)集互不相交，則P（（I）｜α）＝L（P（a）｜α）∪L（P（e）｜α）∪…∪L（P（c）｜α），假設(shè)α合取項(xiàng)的首項(xiàng)ki1為b，b是P（I）的第3個(gè)等價(jià)類，由于位于第4和第5位的P（d）和P（c）中不含b項(xiàng)目，即L（P（d）｜α）＝Φ，L（P（d）｜α）＝Φ，滿足α的頻繁集必在該P(yáng)（I）的前3個(gè)等價(jià)類中.同理可證，當(dāng)α合取項(xiàng)的首項(xiàng)ki1為其他項(xiàng)時(shí)也是如此.

由定理1可推出以下公式，圖2為擴(kuò)展格P（e）＾.

LFP－growth算法按項(xiàng)集支持度由小到大依次處理每一個(gè)子網(wǎng)格，在對(duì)每一個(gè)子網(wǎng)格進(jìn)行處理時(shí)采用了迭代分解的方法，即將一個(gè)較大的格分解成較小的子格，將分解后子格分別迭加到相應(yīng)的子格中，依次進(jìn)行約束項(xiàng)挖掘直到求出所有的頻繁集.下面的定理給出了迭加項(xiàng)集數(shù)的大小，所謂迭加項(xiàng)集數(shù)是指完成對(duì)P（k）的挖掘后，從P（k）子格迭加到后續(xù)子格的項(xiàng)集總數(shù).

圖2 擴(kuò)展格P（e）＾Fig.2 Extended latticeP（e）＾

定理2 按上述方法對(duì)子格空間進(jìn)行迭加，P（k）的項(xiàng)集迭加總數(shù)為（n―t）×2n－t－1，n為I中子格的數(shù)，t為P（k）在P（I）中的排序.

證

設(shè)P（k）是P（I）中第t個(gè)子格，P（k）子格中參加迭加的項(xiàng)集總數(shù)為（n－t）×2n－t－1.

推論1 按k的支持度由小到大依次處理每一個(gè)子格P（k），可使參與“迭加”的事務(wù)最少.

證 由定理2可知，越早處理的子格迭加項(xiàng)集數(shù)越多，子格P（k）對(duì)應(yīng)的k的支持度越小，其子搜索空間對(duì)應(yīng)的事務(wù)越少，參加迭加的事務(wù)也越少.因此LFP－growth算法在將P（I）劃分為若干個(gè)較小的子格后，按項(xiàng)集支持度由小到大依次處理每一個(gè)子格，目的是使參與“迭加”的事務(wù)最少.

由推理1可知，按k的支持度大小依次處理子格P（k）比隨機(jī)選擇P（k）進(jìn)行處理效率更高，速度更快.

定理3L（P（I））＝L（P（a）＾｜a）∪L（P（e）＾｜e）∪…∪L（P（c）＾｜c(diǎn)）.

證P（k）＾（k∈I）表示在P（I）中包含項(xiàng)集k的項(xiàng)集，即P（k）＾?P（I），且P（k）＾中包含了P（I）中所有含項(xiàng)目k的項(xiàng)集，因此格P（k）上挖掘滿足約束表達(dá)式α＝k的頻繁項(xiàng)集等同于格P（I）上挖掘滿足該表達(dá)式的頻繁項(xiàng)集，即L（P（I）｜a）＝L（P（a）＾｜a），則有：

由定理3得到以下結(jié)論，對(duì)網(wǎng)格P（I）的頻繁項(xiàng)集挖掘轉(zhuǎn)化為對(duì)多個(gè)子網(wǎng)格的并集進(jìn)行的約束頻繁項(xiàng)集的挖掘，不會(huì)影響頻繁項(xiàng)集完全集的正確輸出.

2.2 算法步驟

實(shí)現(xiàn)LFP－growth算法的關(guān)鍵是子格（子搜索空間）所對(duì)應(yīng)的事務(wù)的迭加，如果復(fù)制所有的子格對(duì)應(yīng)的事務(wù)進(jìn)行迭加，時(shí)間和空間的效率會(huì)非常低.為此，可以借鑒Christian Borgelt教授在研究Recursive elimination算法時(shí)提出的事務(wù)鏈表（transaction list array）來實(shí)現(xiàn)迭加.

事務(wù)鏈表是由一組單向數(shù)據(jù)鏈表組成，每一個(gè)單向數(shù)據(jù)鏈記錄一個(gè)子格P（k）所對(duì)應(yīng)的事務(wù)集（以下簡稱為P（k）事務(wù)集）的信息，每一個(gè)單向數(shù)據(jù)鏈都包括一個(gè)計(jì)數(shù)器（support counter）和一個(gè)指針.計(jì)數(shù)器的值表示P（k）事務(wù)集的總數(shù)，指針則用于保存P（k）事務(wù)集的關(guān)聯(lián)信息.將所有單向數(shù)據(jù)鏈表按P（k）處理的順序排列，便組成了事務(wù)鏈表.樣例數(shù)據(jù)庫的事務(wù)鏈表組如圖3所示.

圖3 事 務(wù)鏈表組Fig.3 Transaction list array

定理4L（P（a）＾′｜a）∪L（P（e）＾′｜e）∪…∪L（P（c）＾′｜c(diǎn)）＝L（P（I））.

證P（k）＾′是P（k）＾的過濾子集，它濾去了之前已挖掘過的冗余項(xiàng).顯然在過濾后的投影數(shù)據(jù)庫上進(jìn)行約束挖掘等同于在投影數(shù)據(jù)庫上進(jìn)行約束挖掘，即L（P（k）＾｜k）＝L（P（k）＾′｜k）.因此，L（P（a）＾′｜a）∪L（P（e）＾′｜e）∪…∪L（P（c）＾′｜c(diǎn)）＝L（P（a）＾｜a）∪L（P（e）＾｜e）∪…∪L（P（c）＾｜c(diǎn)）.由定理3可知，L（P（a）＾′｜a）∪L（P（e）＾′｜e）∪…∪L（P（c）＾′｜c(diǎn)）＝L（P（I））.證畢.

算法1 格P（I）的分解和迭加

輸入：P（I）對(duì)應(yīng)的事務(wù)數(shù)據(jù)庫D；最小支持度閾值minisup

輸出：D中頻繁項(xiàng)集

方法

子格P（a）中事務(wù)的迭加如圖4所示.

圖4 將P（a）中事務(wù)分解到其他子格Fig.4 The transaction ofP（a）was decomposed to other sublattices

算法2 約束頻繁項(xiàng)集挖掘算法

輸入：擴(kuò)展子格P（k）＾對(duì)應(yīng)的數(shù)據(jù)庫子集Dk＾；最小支持度閥值minisup；約束表達(dá)式k；

輸出：滿足約束表達(dá)式lk的頻繁項(xiàng)集Li

定理5P（k）＾（k∈I）是格.

證P（k）＾＝（P（a）｜k）∪（P（e）｜k）…∪（P（c）｜k）.

（P（a）｜k）為格P（I）中包含項(xiàng)目｛ak｝的項(xiàng)集.設(shè)X，Y? （P（a）｜k），則X∩Y，X∪Y? （P（a）｜k）.用反證法，如果X∩Y，X∪Y? （P（a）｜k），則X，Y中必有一項(xiàng) ? （P（a）｜k），與假設(shè)矛盾，因此，X∩Y，X∪Y? （P（a）｜k）.由定義2可知（P（a）｜k）是一個(gè)格，同理可證（P（e）｜k），…，（P（c）｜k）都是格，而（P（a）｜k）∪（P（e）｜k）…∪（P（c）｜k）也是格.證畢.

性質(zhì)1 LFP－growth算法具有良好的可擴(kuò)展性.

當(dāng)數(shù)據(jù)庫為海量數(shù)據(jù)庫時(shí)，可將它分解迭加成多個(gè)P（k）＾進(jìn)行挖掘，而當(dāng)某個(gè)P（k）＾對(duì)應(yīng)的事務(wù)很多，依然無法在內(nèi)存中構(gòu)造Fp－樹時(shí)，挖掘就難以順利進(jìn)行.根據(jù)定理5可知P（k）＾是格，因此我們可將P（k）＾再次進(jìn)行迭加分解，如果分解后擴(kuò)展子格依然無法在內(nèi)存中構(gòu)造Fp－樹時(shí)，就再繼續(xù)分解直到可以在內(nèi)存中構(gòu)造擴(kuò)展子格的Fp－樹為止.

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

3.1 實(shí)驗(yàn)結(jié)果

本節(jié)對(duì)LFP－growth算法和FP－growth算法進(jìn)行比較，程序代碼均用Visual C＋＋實(shí)現(xiàn).實(shí)驗(yàn)在PetiumⅣ2.8G，內(nèi)存512M，硬盤80G的PC機(jī)上運(yùn)行.實(shí)驗(yàn)結(jié)果如圖5～圖7所示.

圖5是采用accidents數(shù)據(jù)庫進(jìn)行實(shí)驗(yàn)，該數(shù)據(jù)庫大小為33.6M，是比利時(shí)國家統(tǒng)計(jì)院提供的1991－2000年期間Flanders地區(qū)的交通事故數(shù)據(jù)庫.由圖5可知，當(dāng)最小支持度大于等于0.5%時(shí)，F(xiàn)P－growth算法的運(yùn)行速度比LFP－growth算法略快.但是，當(dāng)最小支持度小于0.5%時(shí)，LFP－growth算法的運(yùn)行速度比FP－growth算法快.而且隨著支持度的減少，差別越明顯.

圖6是采用bio＿train數(shù)據(jù)庫進(jìn)行實(shí)驗(yàn)，該數(shù)據(jù)庫是KDD Cup 2004所提供的關(guān)于蛋白質(zhì)同源性的訓(xùn)練數(shù)據(jù)庫.該數(shù)據(jù)庫有145 751行，每行包含有1個(gè)塊號(hào)、1個(gè)試驗(yàn)號(hào)和74個(gè)特征值.圖6是在事務(wù)數(shù)據(jù)庫大小為66.4M條件下，最小支持度從3%減少到0.05%的兩種算法運(yùn)行時(shí)間的比較，由圖6可知，當(dāng)最小支持度等于3%時(shí)，F(xiàn)P－growth算法的運(yùn)行速度比LFP－growth算法快.但是，當(dāng)最小支持度小于等于1%時(shí)，LFP－growth算法的運(yùn)行速度比FP－growth算法快.而且隨著支持度的減少，差別越大.

圖5 在accidents上的運(yùn)行時(shí)間Fig.5 Runtime on database accidents

圖6 在bio＿train上的運(yùn)行時(shí)間Fig.6 Runtime on database bio＿train

圖7是在最小支持度固定在15%條件下，事務(wù)數(shù)據(jù)庫從300M增加到600M時(shí)兩種算法運(yùn)行時(shí)間的比較，由圖7可知：隨著事務(wù)數(shù)據(jù)庫規(guī)模的增加，兩種算法的運(yùn)行時(shí)間都在不斷增加.但是FP－growth算法運(yùn)行時(shí)間的增長要遠(yuǎn)大于LFP－growth算法，甚至當(dāng)事務(wù)數(shù)據(jù)庫規(guī)模大于等于450M時(shí)，F(xiàn)P－growth算法因?yàn)閮?nèi)存空間不夠無法運(yùn)行，而LFP－growth算法卻能正常運(yùn)行.

圖7 在WebDocs（支持度15%）上的運(yùn)行時(shí)間Fig.7 Runtime on database WebDocs（min－sup 15%）

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

FP－growth算法要將事務(wù)數(shù)據(jù)庫中所有產(chǎn)生頻繁項(xiàng)集的數(shù)據(jù)壓縮到一棵FP－樹中，該樹中存儲(chǔ)的關(guān)聯(lián)信息從建樹開始到挖掘完畢都完整地保存在內(nèi)存里，挖掘時(shí)又通過遞歸創(chuàng)建條件FP－tree生成頻繁模式，條件FP－tree個(gè)數(shù)等于頻繁模式數(shù)，所以建樹挖掘的時(shí)間和空間開銷都很大，尤其是隨著數(shù)據(jù)庫規(guī)模的增加或支持度閾值的減少而導(dǎo)致頻繁模式的數(shù)量以指數(shù)形式增長時(shí)，F(xiàn)P－growth算法無法構(gòu)造基于內(nèi)存的FP－樹，從而導(dǎo)致挖掘失敗.而LFP－growth算法雖然多次迭加子格，但它是在擴(kuò)展格中構(gòu)造FP－tree，規(guī)模比原始的FP－tree要小，而且挖掘過程比FP－growth算法簡單，時(shí)間消耗遠(yuǎn)小于FP－growth算法.

本文算法不僅時(shí)間效率明顯優(yōu)于FP－growth算法，而且空間效率也明顯優(yōu)于FP－growth算法.因?yàn)?，LFP－growth算法構(gòu)建的是基于擴(kuò)展格的FP－樹，其規(guī)模遠(yuǎn)遠(yuǎn)小于在整體事務(wù)數(shù)據(jù)庫上構(gòu)建的FP－樹，而且由以上運(yùn)行時(shí)間效率實(shí)驗(yàn)和分析已表明，LFP－growth可以在更小的支持度閥度水平上運(yùn)行，而FP－growth算法常因耗盡物理內(nèi)存而無法運(yùn)行.

4 結(jié) 論

提出了一種基于格的快速頻繁項(xiàng)集挖掘算法LFP－growth.這種算法不僅減少了對(duì)內(nèi)存的需求，也較大地提高了挖掘效率，尤其適合挖掘大型數(shù)據(jù)庫的頻繁項(xiàng)集.本文的實(shí)驗(yàn)結(jié)果很好地證明了這一點(diǎn).

今后的工作在于進(jìn)一步的研究如何精簡事務(wù)數(shù)據(jù)鏈表組的結(jié)構(gòu)，進(jìn)一步提高現(xiàn)有算法的效率，減少對(duì)內(nèi)存的需求.同時(shí)考慮可將本文格迭加分解的策略和已有的各種分布式頻繁模式挖掘算法結(jié)合起來，設(shè)計(jì)新的基于分布式數(shù)據(jù)庫的頻繁模式挖掘算法.

[1] HAN J，PEI J，YIN Y.Mining frequent patterns without candidate generation[C]／／Proceedings of the ACM SIGMOD International Conference on Management of Data.New York：ACM Press，2000：1－12.

[2] KOH J L，TU Y L.A tree－based approach for efficiently min－ing approximate frequent itemsets[C]／／Proceedings of the Fourth International Conference on Research Challenges in Information Science（RCIS）.Nice，F(xiàn)rance：2010：1349－1357.

[3] 李也白，唐輝，張淳，等.基于改進(jìn)的FP－tree的頻繁模式挖掘算法[J].計(jì)算機(jī)應(yīng)用，2011，31（1）：101－103.LI Ye－bai，TANG Hui，ZHANG Chun，etal.Frequent pattern mining algorithm based on improved FP－tree[J].Journal of Computer Applications，2011，31（1）：101－103.（In Chinese）

[4] NGUYEN T T.An improved algorithm for frequent patterns mining problem[C]／／Proceedings of the International Symposium on Computer Communication Control and Atomation.Tainan，2010：503－507.

[5] 郭宇紅，童云海，唐世渭.基于FP－Tree的反向頻繁項(xiàng)集挖掘[J].軟件學(xué)報(bào)，2008，19（2）：338－350.GUO Yu－h(huán)ong，TONG Yun－h(huán)ai，TANG Shi－wei.Inverse frequent itemset mining based on FP－tree[J].Journal of Software，2008，19（2）：338－350.（In Chinese）

[6] ZENG B，JIANG X L，ZHAO W.The improvement of weighted association rules arithmetic based on FP－tree[C]／／Proceedings of the 3rd International Conference on Advanced Computer Theory and Engineering.Chengdu，2010：549－552.

[7] JALAN S，SRIVASTAVA A，SHARMA G K.A non－recursive approach for FP－tree based frequent pattern generation[C]／／2009IEEE Student Conference on Research and Development（SCOReD）.UPM Serdang，2009：160－163.

[8] ADNAN M，ALHAJJ R.A bounded and adaptive memorybased approach to mine frequent patterns from very large databases[J].IEEE Transactions on Systems，Man，and Cybernetics，Part B：Cybernetics，2011，41（1）：154－172.

[9] 趙強(qiáng)利，蔣艷凰，徐明.基于FP－Tree的快速選擇性集成算法[J].軟件學(xué)報(bào)，2011，22（4）：709－720.ZHAO Qiang－li，JIANG Yan－h(huán)uang，XU Ming.Fast ensemble pruning algorithm based on FP－tree[J].Journal of Software，2011，22（4）：709－720.（In Chinese）

[10] 范明，李川.在FP－樹中挖掘頻繁模式而不生成條件FP－樹[J].計(jì)算機(jī)研究與發(fā)展，2003，40（8）：1216－1222.FAN Ming，LI Chuan.Mining frequent patterns in an FP－tree without conditional FP－tree generation[J].Journal of Computer Research and Development，2003，40（8）：1216－1222.（In Chinese）

[11] 譚軍，卜英勇，楊勃.一種單遍掃描頻繁模式樹結(jié)構(gòu)[J].計(jì)算機(jī)工程，2010，36（14）：32－33.TAN Jun，BU Ying－yong，YANG Bo.Single－pass frequent pattern tree structure[J].Computer Engineering，2010，36（14）：32－33.（In Chinese）

[12] 郭耀煌，劉家誠，劉常青，等.格序決策[M].上海：上海科學(xué)技術(shù)出版社，2003.