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

石 杰

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

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

石 杰1，2

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

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

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

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

一般來說，從數(shù)據(jù)中可以挖掘出許多種類的模式.例如，可以從市場購物籃分析中挖掘出關(guān)聯(lián)規(guī)則，分類可以發(fā)現(xiàn)的分類規(guī)則，聚類和異常值可以定義客戶關(guān)系管理.頻繁模式挖掘是數(shù)據(jù)挖掘研究中一個重要方向，它適用于多種類型的數(shù)據(jù)庫，如時間序列數(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)知識

1.1 FP-growth算法

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

procedure FP-growth(Tree，α)

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

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

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

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

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

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

(7)if Tree β≠? then

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

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

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

關(guān)系數(shù)據(jù)庫以二維表的形式存儲數(shù)據(jù)，在數(shù)據(jù)庫中事務(wù)以這種方式存儲對于決定關(guān)聯(lián)規(guī)則挖掘算法效率的高低起著重要的作用.大多數(shù)現(xiàn)代關(guān)系數(shù)據(jù)庫都是事務(wù)型數(shù)據(jù)庫.一個數(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ù)庫太大以至于不容易裝進內(nèi)存時，F(xiàn)P-growth算法的性能下降得很快.畢竟，數(shù)據(jù)挖掘面對的是海量的數(shù)據(jù)，將這樣大量的數(shù)據(jù)在內(nèi)存中組織有時是一個太高的要求.針對FP-growth算法的不足之處，本文提出了一種新的算法——快速頻繁模式(Quick Frequent Pattern，QFP)算法，利用該算法建立、挖掘QFP-tree，提高掃描數(shù)據(jù)庫速度的同時降低了反復(fù)構(gòu)建條件頻繁模式樹以及條件模式基的數(shù)量，降低了算法計算的復(fù)雜度和對內(nèi)存空間的占用，提高了頻繁模式挖掘的速度，適合對大型數(shù)據(jù)庫挖掘的要求.

首先給出QFP-tree的定義:

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

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

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

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

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

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

QFP算法的主要步驟.

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

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

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

2.3 QFP-tree的建立

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

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

如表1是事務(wù)數(shù)據(jù)庫的一部分，其頻繁項為{I1，I2，I3，I4，I5，I6}，假定I1的頻繁度最高，I6的頻繁度最低.首先我們以I6項為根建立一棵QFP-tree.如圖2，所有頻繁度大于或等于I6且和I6屬于同一個事務(wù)的項作為節(jié)點參與了樹的建立.圖2包括了2個節(jié)點.根節(jié)點I6和它的孩子節(jié)點I2.從表1中我們可以看到I2和I6同屬于一個事務(wù)，且I6 I2在表1的數(shù)據(jù)庫中只出現(xiàn)了2次.與此相同的是以I5為根的QFP-tree，I5 I1也在同一個事務(wù)中，且只出現(xiàn)了2次，如圖3.而項I3同時與3個項出現(xiàn)，分別為I1，I2和I4.所以以I3為根的QFP-tree存在2個分支，如圖4.即I3I2I1和I3I4I1.從表1中我們可以得到分支I3I2I1的頻繁度為4，分支I3I4I1的頻繁度為1.而此時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項為根的QFP-treeFig.2 I6 is the root of the QFP-tree

圖3 I5項為根的QFP-treeFig.3 I5 is the root of the QFP-tree

圖4 I3項為根的QFP-treeFig.4 I3 is the root of the QFP-tree

圖5 I4項為根的QFP-treeFig.5 I4 is the root of the QFP-tree

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

圖6 I2項為根的QFP-treeFig.6 I2 is the root of the QFP-tree

2.4 QFP-tree的挖掘

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

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

在挖掘以I3為根節(jié)點的QFP-tree時，我們從樹中頻繁度最高的節(jié)點開始，即從節(jié)點I1開始.I1存在于分支I1I2I3(I1∶4，I2∶5，I3∶8)和分支I1I4I3(I1∶1，I4∶3，I3∶8)中.每一個分支的頻繁度為第1個項的sup減去它的cou值.項I1在分支I1I2I3中，其sup值為4，cou的初始值為0，因此模式I1I2I3的頻繁度為4，同時分支I1I2I3中所有節(jié)點的cou值加4.在第1個模式I1I2I3∶4中，生成包含項I3的所有子模式，即I1I3∶4，I2I3∶4.在I1所屬的第2個分支I1I4I3中，I1的sup值為1，cou的初始值為0，所以模式I1I4I3的頻繁度為1，同時分支I1I4I3中所有節(jié)點的cou值加1.在第2個模式I1I4I3中，生成包含I3項的子模式，即I4I3∶1和I1I3∶1.由于在模式I1I2I3也生成了模式I1I3，其頻繁度為4，即I1I3∶4.所以更新模式I1I3的頻繁度為5(=4+1)，即I1I3∶5.此時處理完節(jié)點I1.順著分支向上，得到第2個頻繁項I2，項I2存在于分支I2I3(I2∶5，I3∶8)中.模式I2I3的頻繁度為項I2的sup值5減去其cou的值4，即I2I3∶1，同時分支I2I3中所有節(jié)點的cou值加1.此前已經(jīng)生成了模式I2I3∶4，所以要更新模式I2I3的頻繁度為5(=4+1)，即I2I3∶5.樹中最后一個節(jié)點I4存在于分支I4I3(I4∶3，I3∶8)中，其sup值為3，cou值為1.所以模式I4I3的頻繁度為2(=3-1)，同時分支I4I3中所有節(jié)點的cou值加2.此前已經(jīng)生成了模式I4I3∶1，所以更新模式I4I3的頻繁度為3(=2+1)，即I4I3∶3.此時以項I3為根節(jié)點的FP-tree挖掘完畢，根據(jù)sup，我們刪除包含項I3的不頻繁模式，保留頻繁模式，同時刪除此樹生成、挖掘下一個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找到第一個頻繁項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ù)庫中讀入包含頻繁項的子事務(wù)，然后依次為每個頻繁項建立獨立的QFP-tree.這樣的QFP-tree樹型結(jié)構(gòu)的規(guī)模較小，需要的存儲空間很小，從而能夠降低計算的復(fù)雜度和對內(nèi)存空間的占用.在挖掘過程中按照QFP-tree的生成順序，每建立一棵QFP-tree樹，就對其進行挖掘，當(dāng)挖掘完成后立即刪除QFP-tree，接著建立下一棵QFP-tree，然后再挖掘再刪除，直到生成所有的頻繁模式為止.這樣做的好處是能夠在挖掘過程中最大限度的減少候選項集產(chǎn)生的數(shù)量并且不用遞歸的建立條件子樹.該算法與FP-growth算法相比，能夠有效的降低計算的復(fù)雜度和對內(nèi)存空間的要求，從而能夠適應(yīng)對大型數(shù)據(jù)庫挖掘的要求.

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

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

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

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

4 結(jié)束語

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

［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］石杰，劉希玉.山東省計算機學(xué)會信息技術(shù)與信息化研討會論文集［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é)基金資助項目(ZR2013FM010).

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