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

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

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

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

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