基于FP-Growth關(guān)聯(lián)規(guī)則的并行算法分析及其應用研究.pdf

1、隨著現(xiàn)代科學技術(shù)的發(fā)展,計算機科學與技術(shù)的進步,數(shù)據(jù)挖掘作為一門嶄新的知識發(fā)現(xiàn)技術(shù)學科得到了快速的發(fā)展。數(shù)據(jù)挖掘(DataMining)就是從大量的、不完全的、有噪聲的、模糊的、隨機的大型數(shù)據(jù)中挖掘那些令人感興趣的、有用的、隱含的、先前未知的和可能有用的模式或知識。由于我們在科學研究以及日常事務中積累了大量的數(shù)據(jù)資料,如果不借助有用的工具去發(fā)現(xiàn)其中潛在有用的信息,即使是知識的海洋,我們也將信息貧乏,很多有用的信息也不能夠被我們發(fā)現(xiàn)。由于

2、以往的算法如:經(jīng)典算法Aprior算法需要多次掃描數(shù)據(jù)庫,產(chǎn)生大量候選項集,而FP-Growth算法需要建立龐大FP-Tree占用大量內(nèi)存,它們在效率上不高,當面臨十分龐大的數(shù)據(jù)庫時,其算法在效率上顯然不足,也不能夠適應大型數(shù)據(jù)庫的數(shù)據(jù)挖掘,效率問題成為該研究與應用的關(guān)鍵和難點。FP-Growth算法采用分而治之的策略,把數(shù)據(jù)庫中的頻繁項集壓縮到一棵頻繁模式樹(FP-tree)中,同時保留項集之間的關(guān)聯(lián)信息,再將FP-tree劃分為一些

3、條件模式庫分別進行挖掘。由于不用多次掃描數(shù)據(jù)庫,不產(chǎn)生候選項集,其效率顯然比Apriori算法高,但是該算法由于要建立FP-tree需要占用大量內(nèi)存,所以不適用于大型數(shù)據(jù)庫進行數(shù)據(jù)挖掘。ParallelAlgorithm算法是指在并行機上,將一個任務分解成多個子任務(task),分配給多個不同的處理器(process),各個處理器之間相互協(xié)同合作,并行地執(zhí)行子任務,從而達到加速求解速度或者求解應用問題規(guī)模的目的。本論文研究的是基于FP-

4、Growth關(guān)聯(lián)規(guī)則的并行算法問題,通過對當前FP-Growth和ParallelAlgorithm的一些關(guān)鍵技術(shù)的研究,提出一種基于FP-Growth關(guān)聯(lián)規(guī)則的并行算法分析及其應用研究。該算法針對以往算法的缺點和不足,在FP-Growth算法基礎上,借助并行算法的思想,將數(shù)據(jù)庫分塊以及保留數(shù)據(jù)相關(guān)性不變的FP-tree樹劃分算法,同時將任務合理分配,并將它們進行合理組合,在負載平衡,多處理器調(diào)度上做了相應的研究,使任務達到合理分配組合