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

［摘 要］FP-Growth是頻繁模式挖掘的經(jīng)典算法，能夠在不產(chǎn)生候選集的情況下生成所有的頻繁模式，效率與Apriori算法相比有巨大提高， 然而FP-Growth算法在挖掘頻繁模式過程中需要遞歸構(gòu)建大量的條件FP-tree，并分別針對這些條件FP-tree進(jìn)行挖掘，時(shí)間及空間效率不高，在實(shí)際應(yīng)用中存在很大局限性。計(jì)算機(jī)集群是由多臺普通計(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

［中圖分類號］TP301.6［文獻(xiàn)標(biāo)識碼］A［文章編號］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，對計(jì)算系統(tǒng)的時(shí)間和空間都有較高的要求，不僅速度慢而且內(nèi)存容易溢出。……