石 杰

(1.山東青年政治學(xué)院實(shí)驗(yàn)設(shè)備管理處，山東濟(jì)南250103;2.山東省高校信息安全與智能控制重點(diǎn)實(shí)驗(yàn)室，山東濟(jì)南250103)

一種快速頻繁模式挖掘算法

石 杰1，2

(1.山東青年政治學(xué)院實(shí)驗(yàn)設(shè)備管理處，山東濟(jì)南250103;2.山東省高校信息安全與智能控制重點(diǎn)實(shí)驗(yàn)室，山東濟(jì)南250103)

頻繁模式挖掘是數(shù)據(jù)挖掘領(lǐng)域中一個(gè)重要的研究方向，目前已有很多算法被用于挖掘頻繁模式.本文在研究FP-growth算法的基礎(chǔ)上，提出一種新的頻繁模式挖掘算法——QFP算法.首先對每一個(gè)頻繁項(xiàng)建立一棵QFP樹，進(jìn)而根據(jù)設(shè)定的條件對每棵樹進(jìn)行挖掘，直到找出符合條件的頻繁模式.實(shí)驗(yàn)證明該算法能夠減少條件子樹的生成數(shù)量，降低對內(nèi)存空間的依賴和CPU的計(jì)算時(shí)間，從而提高關(guān)聯(lián)規(guī)則挖掘的效率.

數(shù)據(jù)挖掘;頻繁模式;項(xiàng)集

數(shù)據(jù)挖掘一直是數(shù)據(jù)庫技術(shù)中一個(gè)活躍的研究領(lǐng)域.隨著存儲(chǔ)設(shè)備成本的降低和壓縮技術(shù)的不斷進(jìn)步，使得每一個(gè)事務(wù)都可以存儲(chǔ)到事務(wù)數(shù)據(jù)庫中成為可能.這種存儲(chǔ)解決了2個(gè)問題:第1，可以隨意訪問數(shù)據(jù);第2，這些數(shù)據(jù)可以有助于發(fā)現(xiàn)數(shù)據(jù)項(xiàng)之間的關(guān)系.發(fā)現(xiàn)不同數(shù)據(jù)項(xiàng)之間存在的關(guān)聯(lián)，以幫助提高收益，優(yōu)化存儲(chǔ).Agrawal等［1］提出的Apriori算法就是第1個(gè)被用于發(fā)現(xiàn)不同數(shù)據(jù)項(xiàng)之間是否存在關(guān)聯(lián)的算法.

一般來說，從數(shù)據(jù)中可以挖掘出許多種類的模式.例如，可以從市場購物籃分析中挖掘出關(guān)聯(lián)規(guī)則，分類可以發(fā)現(xiàn)的分類規(guī)則，聚類和異常值可以定義客戶關(guān)系管理.頻繁模式挖掘是數(shù)據(jù)挖掘研究中一個(gè)重要方向，它適用于多種類型的數(shù)據(jù)庫，如時(shí)間序列數(shù)據(jù)庫［2］、事務(wù)數(shù)據(jù)庫［3］、數(shù)據(jù)流數(shù)據(jù)庫［4］，在許多數(shù)據(jù)挖掘任務(wù)中發(fā)揮了重要作用，如挖掘關(guān)聯(lián)規(guī)則、關(guān)聯(lián)、因果關(guān)系、序列模式、多維模式，顯露模式.

1 相關(guān)知識(shí)

1.1 FP-growth算法

頻繁模式增長(FP-growth)算法，由Han等［5］提出，該算法采用分治策略［6］，在發(fā)現(xiàn)頻繁模式時(shí)不需要產(chǎn)生候選集的一種挖掘關(guān)聯(lián)規(guī)則的算法.第1步，掃描數(shù)據(jù)庫一遍得到各項(xiàng)目的頻度，根據(jù)minsup得到頻繁項(xiàng)目;對頻繁項(xiàng)目按其頻度由大到小排列(次序記為R)，并形成頭表.第2步，再次掃描數(shù)據(jù)庫，對每一條交易中的所有頻繁項(xiàng)目，按次序R組成相應(yīng)的項(xiàng)目集并插入到FP樹中.對每一頻繁項(xiàng)目對應(yīng)的條件FP樹進(jìn)行挖掘獲得所有的頻繁項(xiàng)目集.FP樹中除了根節(jié)點(diǎn)，每一個(gè)節(jié)點(diǎn)包含了項(xiàng)的名稱，支持度，一個(gè)指向鏈接在樹中具有相同名稱的節(jié)點(diǎn)［7］，這些節(jié)點(diǎn)被用于創(chuàng)造FP樹.

procedure FP-growth(Tree，α)

(1)if Tree含單個(gè)路徑P then

(2)for路徑P中結(jié)點(diǎn)的每個(gè)組合(記作β)

(3)產(chǎn)生模式β∪α，其支持度support=β中結(jié)點(diǎn)的最小支持度;

(4)else for each ai在Tree的頭部{

(5)產(chǎn)生一個(gè)模式β=ai∪α，其支持度support =ai.support;

(6)構(gòu)造β的條件模式基，然后構(gòu)造β的條件FP樹Treeβ;

(7)if Tree β≠? then

(8)調(diào)用FP-growth(Tree β，β);}

2 數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)與QFP算法

2.1 數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)

關(guān)系數(shù)據(jù)庫以二維表的形式存儲(chǔ)數(shù)據(jù)，在數(shù)據(jù)庫中事務(wù)以這種方式存儲(chǔ)對于決定關(guān)聯(lián)規(guī)則挖掘算法效率的高低起著重要的作用.大多數(shù)現(xiàn)代關(guān)系數(shù)據(jù)庫都是事務(wù)型數(shù)據(jù)庫.一個(gè)數(shù)據(jù)庫的布局方式能夠描述數(shù)據(jù)的表示方法.目前有2種常用的布局方式，水平布局方式［8，10-11］垂直布局方式［9-10］，如垂直位圖表示法［12］、倒排矩陣表示法［13］.水平布局方式應(yīng)用較多，垂直布局方式應(yīng)用較少［14］.

2.2 QFP算法

FP-growth算法的執(zhí)行過程中需要重復(fù)遞歸地生成條件FP子樹，這對空間的要求非常高.當(dāng)數(shù)據(jù)庫太大以至于不容易裝進(jìn)內(nèi)存時(shí)，F(xiàn)P-growth算法的性能下降得很快.畢竟，數(shù)據(jù)挖掘面對的是海量的數(shù)據(jù)，將這樣大量的數(shù)據(jù)在內(nèi)存中組織有時(shí)是一個(gè)太高的要求.針對FP-growth算法的不足之處，本文提出了一種新的算法——快速頻繁模式(Quick Frequent Pattern，QFP)算法，利用該算法建立、挖掘QFP-tree，提高掃描數(shù)據(jù)庫速度的同時(shí)降低了反復(fù)構(gòu)建條件頻繁模式樹以及條件模式基的數(shù)量，降低了算法計(jì)算的復(fù)雜度和對內(nèi)存空間的占用，提高了頻繁模式挖掘的速度，適合對大型數(shù)據(jù)庫挖掘的要求.

首先給出QFP-tree的定義:

一棵QFP-tree為滿足以下3個(gè)條件的樹型結(jié)構(gòu).

(1)它由一個(gè)頻繁度最低項(xiàng)作為樹的根節(jié)點(diǎn)，作為根節(jié)點(diǎn)的孩子的項(xiàng)目前綴子樹集合，以及頻繁項(xiàng)目頭表組成.

(2)樹中每一個(gè)節(jié)點(diǎn)有項(xiàng)名(item-name)，支持度(sup)，計(jì)數(shù)器(cou)，其中，item-name記錄項(xiàng)目名，sup記錄每一個(gè)頻繁項(xiàng)的支持度，cou記錄每一個(gè)頻繁模式的頻繁度(初始為0).其功能是在樹的挖掘過程中用于臨時(shí)記錄中間模式的頻繁度，避免對模式的重復(fù)計(jì)算，降低計(jì)算開銷.

(3)頻繁項(xiàng)目頭表的每一個(gè)表項(xiàng)只包含一個(gè)域:item-name.

(4)樹中父節(jié)點(diǎn)與子節(jié)點(diǎn)之間，頻繁項(xiàng)目表與節(jié)點(diǎn)之間用單箭頭連接.樹型結(jié)構(gòu)如圖1.

圖1 QFP-tree模型Fig.1 Quick Frequent Pattern-tree model

QFP算法的主要步驟.

(1)掃描數(shù)據(jù)庫，根據(jù)支持度找到頻繁項(xiàng).

(2)針對給定事務(wù)中的頻繁項(xiàng)建立QFP-tree結(jié)構(gòu).

(3)挖掘QFP-tree，生成頻繁模式.

2.3 QFP-tree的建立

QFP-tree的建立的原則是:選擇事務(wù)中頻繁度最低的項(xiàng)作為樹的根節(jié)點(diǎn)，為每一個(gè)頻繁項(xiàng)建立相應(yīng)的QFP-tree.在建立過程中，事務(wù)中每一個(gè)頻繁項(xiàng)作為其相應(yīng)QFP-tree的根節(jié)點(diǎn)建樹.下面用一個(gè)實(shí)例來介紹QFP-tree的建立和挖掘過程.

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

如表1是事務(wù)數(shù)據(jù)庫的一部分，其頻繁項(xiàng)為{I1，I2，I3，I4，I5，I6}，假定I1的頻繁度最高，I6的頻繁度最低.首先我們以I6項(xiàng)為根建立一棵QFP-tree.如圖2，所有頻繁度大于或等于I6且和I6屬于同一個(gè)事務(wù)的項(xiàng)作為節(jié)點(diǎn)參與了樹的建立.圖2包括了2個(gè)節(jié)點(diǎn).根節(jié)點(diǎn)I6和它的孩子節(jié)點(diǎn)I2.從表1中我們可以看到I2和I6同屬于一個(gè)事務(wù)，且I6 I2在表1的數(shù)據(jù)庫中只出現(xiàn)了2次.與此相同的是以I5為根的QFP-tree，I5 I1也在同一個(gè)事務(wù)中，且只出現(xiàn)了2次，如圖3.而項(xiàng)I3同時(shí)與3個(gè)項(xiàng)出現(xiàn)，分別為I1，I2和I4.所以以I3為根的QFP-tree存在2個(gè)分支，如圖4.即I3I2I1和I3I4I1.從表1中我們可以得到分支I3I2I1的頻繁度為4，分支I3I4I1的頻繁度為1.而此時(shí)I3的頻繁度應(yīng)變?yōu)?(=4+1).在表1中I3I4的頻繁度為2，但是I3 I4屬于分支I3I4I1，所以只更新I3和I4的頻繁度，即I3的頻繁度變?yōu)?(=5+2)，I4的頻繁度變?yōu)?(=2+1).同理I3 I2也屬于分支I3I2I1，I3I2的頻繁度為1，所以也只更新I3和I2的頻繁度，即I3的頻繁度為8(= 7+1)，I2的頻繁度為5(=4+1).剩下的分別以I4和I2為根與頻繁度最高的I1構(gòu)成QFP-tree如圖5，圖6.

圖2 I6項(xiàng)為根的QFP-treeFig.2 I6 is the root of the QFP-tree

圖3 I5項(xiàng)為根的QFP-treeFig.3 I5 is the root of the QFP-tree

圖4 I3項(xiàng)為根的QFP-treeFig.4 I3 is the root of the QFP-tree

圖5 I4項(xiàng)為根的QFP-treeFig.5 I4 is the root of the QFP-tree

在建樹的過程中，所有頻繁項(xiàng)的QFP-tree不是同時(shí)建立的，而是在前一棵QFP-tree被建立、挖掘、刪除后才建立的.這樣就避免產(chǎn)生大量的或無用的QFP-tree對內(nèi)存空間的占用.

圖6 I2項(xiàng)為根的QFP-treeFig.6 I2 is the root of the QFP-tree

2.4 QFP-tree的挖掘

對每棵QFP-tree的挖掘過程是獨(dú)立的.目的是找出每棵樹的根節(jié)點(diǎn)所在的所有頻繁k-項(xiàng)集模式.而其他的子模式的頻繁度可以從它們的父模式中得到，無需再計(jì)算它們在數(shù)據(jù)庫中的出現(xiàn)次數(shù).我們以圖4中的QFP-tree為例，通過挖掘以I3為根節(jié)點(diǎn)的QFP-tree發(fā)現(xiàn)包含I3的頻繁模式，過程如圖7.

假設(shè)支持度sup＞3.在挖掘過程中，我們要使用到每個(gè)節(jié)點(diǎn)的支持度(sup)和計(jì)數(shù)器(cou)，同時(shí)把得到的候選頻繁模式存儲(chǔ)在一個(gè)臨時(shí)表中.在處理完每棵樹的所有分支后根據(jù)sup的值刪除不頻繁的模式，從而生成符合條件的頻繁模式.

在挖掘以I3為根節(jié)點(diǎn)的QFP-tree時(shí)，我們從樹中頻繁度最高的節(jié)點(diǎn)開始，即從節(jié)點(diǎn)I1開始.I1存在于分支I1I2I3(I1∶4，I2∶5，I3∶8)和分支I1I4I3(I1∶1，I4∶3，I3∶8)中.每一個(gè)分支的頻繁度為第1個(gè)項(xiàng)的sup減去它的cou值.項(xiàng)I1在分支I1I2I3中，其sup值為4，cou的初始值為0，因此模式I1I2I3的頻繁度為4，同時(shí)分支I1I2I3中所有節(jié)點(diǎn)的cou值加4.在第1個(gè)模式I1I2I3∶4中，生成包含項(xiàng)I3的所有子模式，即I1I3∶4，I2I3∶4.在I1所屬的第2個(gè)分支I1I4I3中，I1的sup值為1，cou的初始值為0，所以模式I1I4I3的頻繁度為1，同時(shí)分支I1I4I3中所有節(jié)點(diǎn)的cou值加1.在第2個(gè)模式I1I4I3中，生成包含I3項(xiàng)的子模式，即I4I3∶1和I1I3∶1.由于在模式I1I2I3也生成了模式I1I3，其頻繁度為4，即I1I3∶4.所以更新模式I1I3的頻繁度為5(=4+1)，即I1I3∶5.此時(shí)處理完節(jié)點(diǎn)I1.順著分支向上，得到第2個(gè)頻繁項(xiàng)I2，項(xiàng)I2存在于分支I2I3(I2∶5，I3∶8)中.模式I2I3的頻繁度為項(xiàng)I2的sup值5減去其cou的值4，即I2I3∶1，同時(shí)分支I2I3中所有節(jié)點(diǎn)的cou值加1.此前已經(jīng)生成了模式I2I3∶4，所以要更新模式I2I3的頻繁度為5(=4+1)，即I2I3∶5.樹中最后一個(gè)節(jié)點(diǎn)I4存在于分支I4I3(I4∶3，I3∶8)中，其sup值為3，cou值為1.所以模式I4I3的頻繁度為2(=3-1)，同時(shí)分支I4I3中所有節(jié)點(diǎn)的cou值加2.此前已經(jīng)生成了模式I4I3∶1，所以更新模式I4I3的頻繁度為3(=2+1)，即I4I3∶3.此時(shí)以項(xiàng)I3為根節(jié)點(diǎn)的FP-tree挖掘完畢，根據(jù)sup，我們刪除包含項(xiàng)I3的不頻繁模式，保留頻繁模式，同時(shí)刪除此樹生成、挖掘下一個(gè)QFP-tree，產(chǎn)生相應(yīng)的頻繁模式.

圖7 QFP-tree挖掘過程Fig.7 The mining process of QFP-tree

QFP算法描述:

輸入:事務(wù)數(shù)據(jù)庫D;最小支持度閾值minsup.

輸出:頻繁模式.

(1)按以下步驟構(gòu)造QFP-tree

1.1 掃描事務(wù)數(shù)據(jù)庫D，根據(jù)min-sup找到第一個(gè)頻繁項(xiàng)A;

1.2 A=Frequency Item at transaction;

1.3 Creat a root node for the(A)-QFP-tree with sup and cou=0;

1.4 While(node-fre-transaceion＜Frequency of item A)

B=item from transaction;

Follow the chain of item B to produce subtransacion C;

Items on C form a prefix of the(A)-QFP-tree;

If the prefix is new then;

Set sup=1 and cou=0 for all nodes in the path;

Else

Adjust the pointer of the Header list if needed;

Increment node-of-QFP-tree;

Goto1.4;

(2)Mine QFP-tree(A)

1.node A=select-node;

2.While there are nodes do

2.1 Set of nodes from node A to the root;

2.2 F=sup-cou of node A;

2.3 Generate all Candididate patterns X from items in D.Patterns that do not have A will be discarded;

2.4 Patterns in X that do not exist in the A-Candidate List will be added to it with frequency=F.otherwise just increment their frequency with F;

2.5 Increment the value of cou by F for all node in D;

2.6 node A=select-node

2.7 Goto 2;

3.Base on min-support remove non-frequent patterns from A Candidate list;

3 算法性能分析

QFP算法生成頻繁模式的過程中，首先從事務(wù)數(shù)據(jù)庫中讀入包含頻繁項(xiàng)的子事務(wù)，然后依次為每個(gè)頻繁項(xiàng)建立獨(dú)立的QFP-tree.這樣的QFP-tree樹型結(jié)構(gòu)的規(guī)模較小，需要的存儲(chǔ)空間很小，從而能夠降低計(jì)算的復(fù)雜度和對內(nèi)存空間的占用.在挖掘過程中按照QFP-tree的生成順序，每建立一棵QFP-tree樹，就對其進(jìn)行挖掘，當(dāng)挖掘完成后立即刪除QFP-tree，接著建立下一棵QFP-tree，然后再挖掘再刪除，直到生成所有的頻繁模式為止.這樣做的好處是能夠在挖掘過程中最大限度的減少候選項(xiàng)集產(chǎn)生的數(shù)量并且不用遞歸的建立條件子樹.該算法與FP-growth算法相比，能夠有效的降低計(jì)算的復(fù)雜度和對內(nèi)存空間的要求，從而能夠適應(yīng)對大型數(shù)據(jù)庫挖掘的要求.

為了進(jìn)一步驗(yàn)證QFP算法的性能，在Windows XP，CPU為Celeron 2.4GHz，內(nèi)存256，VC++6.0的環(huán)境下對QF算法和FP-growth算法在性能上進(jìn)行了比較.實(shí)驗(yàn)數(shù)據(jù)集為濟(jì)南快速公交車系統(tǒng)采集的乘客乘車記錄，如表2.我們從中選取8 000條記錄，記錄了公交車的線路、站點(diǎn)、上車和下車人數(shù)、時(shí)間等信息.實(shí)驗(yàn)結(jié)果如圖8.

表2 乘車記錄表Tab.2 Travel record table

圖8 算法性能比較Fig.8 Algorithm performance comparison

從圖8中可以看到，QFP算法在運(yùn)行時(shí)間上要優(yōu)于FP-growth算法，當(dāng)支持度改變時(shí)，其曲線平緩得多，說明其計(jì)算性能穩(wěn)定.

4 結(jié)束語

本章提出了一種新的的頻繁模式挖掘算法——QFP算法.分別從算法的思想、設(shè)計(jì)步驟、特點(diǎn)、實(shí)例分析和性能分析幾方面進(jìn)行了說明，并和經(jīng)典的FP-growth進(jìn)行性能上的比較，實(shí)驗(yàn)結(jié)果表明新算法較FP-growth算法具有良好的時(shí)間和空間性能.

［1］Han Jiawei，Kamber M.Data Mining Concept and Techniques［M］.San Francisco:Morgan Kaufmann Publishers，2001.

［2］Eltabakh M Y，Ouzzani M，Khalil M A，et al.Incremen-tal mining for frequent patterns in evolving time series database［J］.IEEE Transactions on Knowledge and Data Engineering，2008，7(2):158-165.

［3］Pei Jian，Han Jiawei，Lu Hongjun，et al.H-mine:Fast and space preserving frequent pattern mining in large database［J］.Data Mining and Knowledge Discovery，2001，11(2):53-87.

［4］Lin C H，Chiu D Y，Wu Y H，et al.Mining frequent itemsets from data stream with a time-sensitive sliding window［C］//Proc of 5th SIAM International on Data Mining，Newport Beach:SIAM Press，2005.

［5］Han Jiawei，Pei Jian，Yin Yiwen.Mining frequent patterns without candidate generation［C］//Proc of ACMSIGMOD Int’1 Conference on Management of Data.New York:ACM Press，2000.

［6］Sathish K.Efficient tree based distributed data mining algorithms for mining frequent patterns［J］.International Journal of Computer Applications，2010，11(10):233-242.

［7］Rahul M.Comparative analysis of apriori algorithm and frequent pattern algorithm for frequent pattern mining in web log data［J］.International Journal of Computer Science and Information Technologies，2012，3(4):4662-4665.

［8］Han Jiawei，Pei Jian，Yin Yiwen.Mining frequent patterns without candidate generation:a frequent-pattern tree approach［J］.Data Mining and Knowledge Discovery，2004，8(1): 53-87.

［9］Kantarcioglu M，Clifton C.Privacy-preserving distributed mining of association rules on horizontally Partitioned Data［J］. IEEE Transaction on Knowledge and Data Engineering，2004，16 (9):1026-1037.

［10］Shenoy P，Hartisa JR，Sudarshan S.Turbo-charging vertical mining of large database［C］//Proc of ACM SIGMOD Int’t Conf.on Management of Data.New York:ACM Press，2000.

［11］Han Jiawei，Pei Jian，Yin Yiwen.Mining Frequent Patterns Without Candidate Generation［C］//Proc of the ACM SIGMOD Conf on Management of Data.Dallas:ACM Press，2000.

［12］Burdic D，Calimlim，Gehrke J.A maximal frequent itemset algorithm for transaction database［C］//Proc of the Int＇1 Conf on Data Engineering.Heidelberg:ICDE Press，2001.

［13］Gouda K，Zaki M J.Mining maximal frequent itemsets［C］//Proc of the 1st IEEE Int＇1 Conf on Data Mining.Piscataway:IEEE Press，2001.

［14］石杰，劉希玉.山東省計(jì)算機(jī)學(xué)會(huì)信息技術(shù)與信息化研討會(huì)論文集［C］//山東:山東科學(xué)出版社，2005.

A Fast Algorithm for Mining Frequent Patterns

SHI Jie1，2
(1.Laboratory And Equipment Management Office，Shandong Youth University of Political Science 250103，China;2.Key Laboratory of Information Security and Intelligent Control in Universities of Shandong Youth，Jinan 250103，China)

A new algorithm，Quick Frequency Pattern(QFP)，is presented for the frequent pattern on the basis of studying FP-growth.Firstly，a QFP-tree is made for every frequent item set，and then every tree is being mined according to the configured conditions until the pattern is found.It is proved that QFP can reduce the amount of the sub-trees，the requirement for the RAM space and the calculating time of the CPU，the efficiency of data mining related with the association rules can be improved accordingly.

data mining;frequent pattern;itemset

TP311

A

(責(zé)任編輯 蘇曉東)

1004-8820(2015)02-0113-06

10.13951/j.cnki.37-1213/n.2015.02.007

2014-08-23

山東省自然科學(xué)基金資助項(xiàng)目(ZR2013FM010).

石杰(1980-)，山東濟(jì)南人，講師，碩士，主要研究方向:人工智能、數(shù)據(jù)挖掘等.