面向計(jì)算機(jī)集群系統(tǒng)的ＦＰ－Ｇｒｏｗｔｈ算法的并行計(jì)算

［摘 要］FP-Growth是頻繁模式挖掘的經(jīng)典算法，能夠在不產(chǎn)生候選集的情況下生成所有的頻繁模式，效率與Apriori算法相比有巨大提高， 然而FP-Growth算法在挖掘頻繁模式過程中需要遞歸構(gòu)建大量的條件FP-tree，并分別針對(duì)這些條件FP-tree進(jìn)行挖掘，時(shí)間及空間效率不高，在實(shí)際應(yīng)用中存在很大局限性。計(jì)算機(jī)集群是由多臺(tái)普通計(jì)算機(jī)設(shè)備通過特定方式結(jié)合在一起構(gòu)成的并行處理系統(tǒng)，屬于分布式計(jì)算環(huán)境，具有計(jì)算能力強(qiáng)大、性價(jià)比高、靈活等優(yōu)勢。本文提出一種面向計(jì)算機(jī)集群的并行挖掘算法Gridify FP-Growth， 該算法以FP-Growth為基礎(chǔ)，通過任務(wù)劃分的形式，將計(jì)算任務(wù)分配到計(jì)算機(jī)集群中各個(gè)計(jì)算節(jié)點(diǎn)上執(zhí)行，充分利用各個(gè)節(jié)點(diǎn)的計(jì)算資源，最后匯總各節(jié)點(diǎn)的計(jì)算結(jié)果。實(shí)驗(yàn)證明Gridify FP-Growth算法不會(huì)犧牲計(jì)算的準(zhǔn)確性，并可以大幅度縮短計(jì)算時(shí)間，有效緩解計(jì)算大規(guī)模數(shù)據(jù)庫時(shí)的內(nèi)存壓力。

［關(guān)鍵詞］頻繁模式；FP-Growth；并行計(jì)算；計(jì)算機(jī)集群

doi:10.3969/j.issn.1673-0194.2009.15.011

［中圖分類號(hào)］TP301.6［文獻(xiàn)標(biāo)識(shí)碼］A［文章編號(hào)］1673-0194（2009）15-0036-03

頻繁模式挖掘是關(guān)聯(lián)規(guī)則［1］、相關(guān)分析［2］、序列模式［3］等數(shù)據(jù)挖掘工作的重要基礎(chǔ)。根據(jù)在挖掘過程中是否產(chǎn)生候選集，頻繁模式挖掘算法分成兩大類，前者以Apriori算法［1］為代表，需要多次掃描數(shù)據(jù)庫并產(chǎn)生大量候選集，效率低下；后者以FP-Growth算法［4］為代表，只需兩次掃描數(shù)據(jù)庫，能夠在不產(chǎn)生候選集的情況下產(chǎn)生所有的頻繁項(xiàng)集，效率比Apriori算法相比有巨大提高［4］。然而在挖掘頻繁模式時(shí)， FP-Growth算法需要遞歸生成大量條件FP-tree， 存儲(chǔ)并挖掘這些條件FP-tree，對(duì)計(jì)算系統(tǒng)的時(shí)間和空間都有較高的要求，不僅速度慢而且內(nèi)存容易溢出。所以在實(shí)際應(yīng)用中，當(dāng)面臨海量數(shù)據(jù)庫時(shí)，F(xiàn)P-Growth算法的串行算法已經(jīng)難以滿足計(jì)算需求，面向計(jì)算機(jī)集群系統(tǒng)的并行計(jì)算是解決計(jì)算速度及存儲(chǔ)壓力的有效途徑。

計(jì)算機(jī)集群是使用特定的連接方式，將多臺(tái)普通的計(jì)算機(jī)設(shè)備結(jié)合起來，提供與超級(jí)計(jì)算機(jī)性能相當(dāng)?shù)牟⑿刑幚硐到y(tǒng)。相對(duì)于共享內(nèi)存的并行計(jì)算系統(tǒng)來說，其對(duì)并行算法的要求更高，尤其面對(duì)FP-tree這樣復(fù)雜的數(shù)據(jù)結(jié)構(gòu)時(shí)，各計(jì)算節(jié)點(diǎn)之間很難協(xié)調(diào)統(tǒng)一地執(zhí)行計(jì)算任務(wù)。文獻(xiàn)［5］采用基于數(shù)據(jù)劃分的形式，分割數(shù)據(jù)庫并將其分配到集群中的各個(gè)計(jì)算節(jié)點(diǎn)分別執(zhí)行FP-Growth算法，最后匯總各計(jì)算節(jié)點(diǎn)的結(jié)果，開創(chuàng)了面向計(jì)算機(jī)集群FP-Growth并行計(jì)算的先河。但這種方法存在一個(gè)難以克服的缺點(diǎn)：數(shù)據(jù)庫內(nèi)的數(shù)據(jù)必然存在千絲萬縷的聯(lián)系，強(qiáng)行劃分?jǐn)?shù)據(jù)庫可能會(huì)犧牲結(jié)果的準(zhǔn)確性。

本文提出了一種基于任務(wù)劃分的，面向計(jì)算機(jī)集群的新的頻繁模式挖掘算法——Gridify FP-Growth， 將建立FP-tree后彼此獨(dú)立的頻繁模式挖掘任務(wù)劃分到集群中所有的計(jì)算節(jié)點(diǎn)上共同執(zhí)行，不但能夠提高計(jì)算效率，而且當(dāng)數(shù)據(jù)庫規(guī)模不斷增加時(shí)該算法具有良好的延展性。

1 相關(guān)概念介紹

1.1 頻繁模式挖掘

設(shè)I = {i₁， i₂，…， i_n}是n個(gè)不同項(xiàng)目的集合。設(shè)D為事務(wù)集，其中的每個(gè)事務(wù)為T_I的項(xiàng)集，每個(gè)事務(wù)有唯一標(biāo)識(shí)，稱作TID。對(duì)于項(xiàng)目集X_I，若X_T，則認(rèn)為事務(wù)T 支持X。 X在D中的支持?jǐn)?shù)是指D中支持X的事務(wù)數(shù)。X在D中的支持度是指D中包含X的事務(wù)的百分比。如果X的支持度不小于用戶給定最小支持度閾值Min_Support， 則稱X為D中的頻繁項(xiàng)集，項(xiàng)集中項(xiàng)目的個(gè)數(shù)稱為頻繁項(xiàng)集的維數(shù)或長度。僅含有一項(xiàng)的頻繁集稱作頻繁一項(xiàng)集。頻繁模式挖掘的任務(wù)就是找出給定數(shù)據(jù)集D中支持度超過給定最小支持度閾值的所有頻繁項(xiàng)集。

1.2 FP-Growth算法

FP-Growth算法屬于深度優(yōu)先搜索，將挖掘長頻繁模式的問題轉(zhuǎn)換成遞歸地發(fā)現(xiàn)一些短模式，然后連接后綴形成。僅需要兩次掃描數(shù)據(jù)庫，第一次掃描產(chǎn)生頻繁一項(xiàng)集；第二次掃描建立全局FP-tree。從挖掘步驟來看，可以分成兩步：

第一步，建立FP-tree：把數(shù)據(jù)庫中的頻繁集壓縮進(jìn)一棵頻繁模式樹 (FP-tree)，同時(shí)保留其中的關(guān)聯(lián)信息。

第二步，對(duì)FP-tree進(jìn)行頻繁模式挖掘：由于FP-tree蘊(yùn)含了所有頻繁項(xiàng)集，所以頻繁模式挖掘的工作僅在FP-tree上進(jìn)行。根據(jù)頻繁一項(xiàng)集將FP-tree分化成一些條件模式庫，針對(duì)這些條件模式庫分別建立條件FP-tree，遞歸地進(jìn)行挖掘。

建立FP-tree 及對(duì)FP-tree 進(jìn)行挖掘的具體實(shí)現(xiàn)過程在文獻(xiàn)［4］中有詳細(xì)介紹，在此不贅述。值得注意的是，在第二步中，根據(jù)每個(gè)條件FP-tree遞歸地挖掘的過程，是彼此獨(dú)立的［5］。根據(jù)這一特點(diǎn)，可以將這些獨(dú)立的挖掘過程分配到計(jì)算機(jī)集群中不同的計(jì)算節(jié)點(diǎn)分布執(zhí)行。這是本文中將提到的并行算法的理論基礎(chǔ)。

2 計(jì)算機(jī)集群系統(tǒng)

計(jì)算機(jī)集群（PC Cluster）是指一組相互獨(dú)立的計(jì)算機(jī)，利用高速通信網(wǎng)絡(luò)組成的計(jì)算機(jī)系統(tǒng)，每個(gè)節(jié)點(diǎn)（即集群中的每臺(tái)計(jì)算機(jī)）都是運(yùn)行其自己進(jìn)程的一個(gè)獨(dú)立服務(wù)器，這些進(jìn)程可以彼此通信，同時(shí)集群中的各個(gè)節(jié)點(diǎn)是平等的。從某種意義上說，計(jì)算機(jī)集群形成了一個(gè)單一系統(tǒng)，可被看作是一臺(tái)計(jì)算機(jī)，協(xié)同起來向用戶提供應(yīng)用程序、系統(tǒng)資源和數(shù)據(jù)，并以單一系統(tǒng)的模式加以管理。

計(jì)算機(jī)集群不僅能夠提供強(qiáng)大處理能力，且性價(jià)比遠(yuǎn)遠(yuǎn)優(yōu)于超級(jí)計(jì)算機(jī)，最重要的是其具有很強(qiáng)的可伸縮性：在系統(tǒng)的處理能力需要增加的時(shí)候，可通過簡單地增加集群中的節(jié)點(diǎn)數(shù)，即通過向集群添加新的計(jì)算機(jī)節(jié)點(diǎn)，完成系統(tǒng)計(jì)算能力的擴(kuò)容，這在對(duì)大規(guī)模數(shù)據(jù)庫進(jìn)行頻繁模式挖掘時(shí)，具有重要的應(yīng)用價(jià)值。

3 面向計(jì)算機(jī)集群的FP-Growth算法的并行計(jì)算

本文以FP-Growth算法為基礎(chǔ)，提出了適用于計(jì)算機(jī)集群系統(tǒng)的并行算法，由于計(jì)算機(jī)集群系統(tǒng)中的各節(jié)點(diǎn)形象地構(gòu)成了一個(gè)計(jì)算網(wǎng)格，本文把算法命名為Gridify FP-Growth，簡稱GFP-Gowth算法。

3.1 GFP-Growth算法主要思想

GFP-Growth算法繼承了FP-Growth算法的第一步，即生成全局FP-tree的過程；并行計(jì)算集中在頻繁模式挖掘這一階段。

為了保證第一次建立的全局FP-tree的完整性與準(zhǔn)確性，建立全局FP-tree的過程在單機(jī)上執(zhí)行，另外實(shí)驗(yàn)證明，當(dāng)數(shù)據(jù)庫規(guī)模在10k以上時(shí)，建立全局FP-tree消耗的時(shí)間與后續(xù)頻繁模式挖掘時(shí)間相比，一般相差3個(gè)數(shù)量級(jí)以上，對(duì)整個(gè)計(jì)算時(shí)間的影響很小，所以建立全局FP-tree的過程不采用并行計(jì)算。

在頻繁模式挖掘階段，當(dāng)數(shù)據(jù)庫規(guī)模較大的時(shí)候，F(xiàn)P-Growth算法會(huì)遞歸生成海量條件模式庫，并需要根據(jù)這些條件模式庫生成一一對(duì)應(yīng)的條件FP-tree。然而，正如我們?cè)诮榻BFP-Growth算法的時(shí)候提到的，根據(jù)每個(gè)條件模式庫生成條件FP-tree，進(jìn)行頻繁模式挖掘的過程，彼此間是完全獨(dú)立的。這一互相獨(dú)立的特點(diǎn)，能夠?qū)⒋兴惴ǖ牧觿蒉D(zhuǎn)換為并行算法的優(yōu)勢：將根據(jù)每一個(gè)條件模式庫挖掘頻繁模式的過程分配到集群中的計(jì)算節(jié)點(diǎn)上分別執(zhí)行，不僅會(huì)提高計(jì)算效率，而且不會(huì)犧牲算法的精度，這是GFP-Growth算法的主要思想。

3.2 GFP-Growth算法主要步驟

計(jì)算機(jī)集群中的各節(jié)點(diǎn)之間是平等的，可以隨機(jī)指定一臺(tái)計(jì)算機(jī)為中央節(jié)點(diǎn)。首先在中央節(jié)點(diǎn)上，根據(jù)數(shù)據(jù)庫生成全局FP-tree，這一單機(jī)實(shí)現(xiàn)的過程與FP-Growth算法相同；生成FP-tree之后，中央節(jié)點(diǎn)根據(jù)頻繁一項(xiàng)集將全局FP-tree分化成一些條件模式庫，并行計(jì)算開始，主要步驟如下：

第一步，對(duì)任務(wù)進(jìn)行劃分。

中央節(jié)點(diǎn)根據(jù)眾多條件模式庫將統(tǒng)一計(jì)算任務(wù)Task劃分為多個(gè)子任務(wù)Jobs，每一個(gè)條件模式庫對(duì)應(yīng)一個(gè)子任務(wù)，即根據(jù)每一個(gè)條件模式庫進(jìn)行頻繁模式挖掘的工作就是一個(gè)Job。

第二步，對(duì)任務(wù)進(jìn)行分配。

由中央節(jié)點(diǎn)將Jobs分配到集群中的各個(gè)計(jì)算節(jié)點(diǎn)（包括它自身在內(nèi)），每個(gè)節(jié)點(diǎn)需要負(fù)責(zé)一至幾個(gè)Jobs；在計(jì)算過程中根據(jù)各節(jié)點(diǎn)的計(jì)算能力進(jìn)行負(fù)載動(dòng)態(tài)調(diào)整。

第三步，分別執(zhí)行任務(wù)，集群中的每個(gè)計(jì)算節(jié)點(diǎn)分別執(zhí)行分配給自己的子任務(wù)Jobs。

對(duì)Jobs對(duì)應(yīng)的各條件模式庫建立相應(yīng)的條件FP-tree，遞歸地對(duì)每個(gè)條件FP-tree進(jìn)行頻繁模式挖掘。

第四步，對(duì)結(jié)果進(jìn)行匯總。

計(jì)算節(jié)點(diǎn)完成Jobs之后，需將計(jì)算結(jié)果傳遞給中央節(jié)點(diǎn)。

這里采用異構(gòu)的通訊方式，即各個(gè)節(jié)點(diǎn)不是同時(shí)開始通訊的，而是每當(dāng)有節(jié)點(diǎn)完成計(jì)算任務(wù)，立刻會(huì)向中央節(jié)點(diǎn)提交運(yùn)算結(jié)果。由中央節(jié)點(diǎn)將全部的計(jì)算結(jié)果匯總，并輸出統(tǒng)一計(jì)算結(jié)果。

4 算法實(shí)現(xiàn)與比較

為了驗(yàn)證集群計(jì)算的靈活性與便利性，實(shí)驗(yàn)所用設(shè)備為3臺(tái)普通PC機(jī)，且配置不同，CPU和內(nèi)存分別為1.73 GHz（雙核）， 2.87 GB ；1.60 GHz（雙核），1.87 GB；2.39 GHz（雙核）， 2.99 GB。采用一般的無線網(wǎng)絡(luò)來連接計(jì)算節(jié)點(diǎn)，帶寬54 Mbps；編程工具和運(yùn)行環(huán)境為JDK 1.6。選擇配置中等的計(jì)算機(jī)1.73 GHz（雙核）， 2.87 GB為中央節(jié)點(diǎn)。兩臺(tái)計(jì)算機(jī)的實(shí)驗(yàn)，所采用的計(jì)算機(jī)為1.73 GHz（雙核）， 2.87 GB ；1.60 GHz（雙核），1.87 GB。

4.1 算法有效性實(shí)驗(yàn)

數(shù)據(jù)集采用http://archive.ics.uci.edu/ml/datasets.html上提供的Mushroom相對(duì)密集型的蘑菇數(shù)據(jù)庫來進(jìn)行實(shí)驗(yàn)。該數(shù)據(jù)庫有8 124條記錄，記錄了蘑菇的23種屬性，雖然是一個(gè)很小的數(shù)據(jù)庫，卻非常稠密，項(xiàng)集之間的相關(guān)性很強(qiáng)，即使在最小支持度閾值較大時(shí)，也存在大量頻繁模式，并且隨著支持度的減小存在嚴(yán)重的組合爆炸問題［6］ 。

實(shí)驗(yàn)設(shè)定頻繁項(xiàng)集長度為15，從圖2看出隨著最小支持度的增大，GFP-Growth算法的速度較FP-Growth算法有顯著提高，在支持度小于2%的情況下，在3臺(tái)計(jì)算機(jī)上實(shí)現(xiàn)的GFP-Growth算法執(zhí)行時(shí)間少于FP-Growth算法的1/3。

4.2 算法伸縮性實(shí)驗(yàn)

分別采用1 000條、2 000條、3 000、4 000、5 000、10 000條事務(wù)數(shù)據(jù)集來實(shí)驗(yàn)，項(xiàng)目數(shù)為200，平均事務(wù)長度為50，最小支持度為4%，頻繁項(xiàng)集長度為4。實(shí)驗(yàn)結(jié)果如圖3所示，在數(shù)據(jù)量相等的情況下， GFP-Growth算法無論在2臺(tái)或3臺(tái)計(jì)算機(jī)上的執(zhí)行時(shí)間始終少于FP-Growth算法，且在3臺(tái)計(jì)算機(jī)上實(shí)現(xiàn)的GFP-Growth算法執(zhí)行時(shí)間少于2臺(tái)計(jì)算機(jī)上實(shí)現(xiàn)的GFP-Growth算法，差距隨數(shù)據(jù)量增大而增大，說明集群系統(tǒng)具有良好的伸縮性。

5 結(jié) 論

本文提出了一種基于FP-Growth的頻繁模式挖掘并行算法——GFP-Growth，能夠在計(jì)算機(jī)集群系統(tǒng)中實(shí)現(xiàn)并行計(jì)算。從算法的角度來看，GFP-Growth算法能夠有效地提高計(jì)算速度并具有良好的伸縮性。從計(jì)算環(huán)境來看，計(jì)算機(jī)集群系統(tǒng)價(jià)格低廉，卻具有大型服務(wù)器的計(jì)算功能，并具有很強(qiáng)的延展性。實(shí)驗(yàn)證明，數(shù)據(jù)庫規(guī)模越大，利用計(jì)算機(jī)集群進(jìn)行并行計(jì)算的優(yōu)勢越明顯。

主要參考文獻(xiàn)

［1］ R Agrawal and R Srikant. Fast Algorithms for Mining Association Rules［C］//In Proceedings of the 20th International Conference on VLDB， 1994： 487-499.

［2］ S Brin， R Motwani， C Silverstein. Beyond Market Basket: Gener-alizing Association Rules to Correlations［C］// Proc of 1997 ACM-SIGMOD Int’l Conf on Management of Data， Tucson， AZ: ACM Press， 1997: 265-276.

［3］ R Agrawal， R Srikant. Mining sequential patterns［C］// ICDE’95， Taipei， Taiwan: IEEE Computer Society Press， 1995: 3-14.

［4］ J Han， Pei ，Y Yin.Mining Frequent Patterns Without Candidate Generation［C］//Proc ACM-SIGMOD， Dallas， TX， 2000.

［5］ Iko Pramudiono and Masaru Kitsuregawa.Parallel FP-Growth on PC Cluster［C］//Proc of the International Conference on Internet Computing， 2003.

［6］ Artur Bykowski， Christophe Rigotti. A Condensed Representationto Find Frequent Patterns［C］//Proc of the 20th ACM SIGACT-SIGMOD-SIGART Symp on Principles of Database System ( PODS 2001)， Santa Barbara， CA: ACM Press， 2001: 267-273.

Parallel FP-Growth Algorithm on PC Cluster

CHEN Min

(School of Economics and Management，University of Science and Technology Beijing，Beijing 100083，P.R.China）

Abstract: FP-Growth is the most popular algorithm for frequent patterns mining， which can produce all frequent patterns without generating candidate item sets. FP-Growth has better performance than previously reported algorithms such as Apriori. Nevertheless， the great amount of conditional pattern base and conditional FP-tree recursively generated during mining frequent patterns limits practical feasibility of FP-Growth algorithm when facing large scale data warehouse. Further performance improvement can be expected from parallel execution. PC cluster is a group of PC connected together through definite ways. It is a distributed computing environment and has some advantages such as great computing ability， flexibility and so on. We propose a new parallel algorithm named Gridify FP-Growth to implement on PC cluster. Gridify FP-Growth is based on FP-Growth algorithm， by allocating jobs to the nodes within the cluster to take full advantage of computing resource of each node. After that， the sub-result from each node will be combined to a total result. Experimental results show that Gridify FP-Growth can dramatically reduce the execution time as well as relieve the space pressure.

Key words: Frequent Patterns; FP-Growth; Parallel Execution; PC Cluster