[摘 要]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)存容易溢出。……