基于MapReduce的圖挖掘研究.pdf

1、圖數(shù)據(jù)挖掘作為一種重要的數(shù)據(jù)分析方法，在現(xiàn)實(shí)生活中有很多應(yīng)用。通過圖挖掘技術(shù)做相關(guān)的科學(xué)分析可以比較快速的得到有用信息，例如，在化學(xué)研究領(lǐng)域中，化學(xué)分子具有標(biāo)準(zhǔn)的圖結(jié)構(gòu)，而且它有典型的環(huán)和鏈，可以利用圖論知識(shí)對(duì)化學(xué)分子結(jié)構(gòu)圖數(shù)據(jù)進(jìn)行挖掘研究。同樣在生物學(xué)中，也有基于圖挖掘的蛋白質(zhì)群落算法。在蛋白質(zhì)的相互作用關(guān)系網(wǎng)絡(luò)中尋找感興趣的蛋白質(zhì)群落。在維普這一類的期刊文獻(xiàn)庫(kù)中，也有基于圖的文獻(xiàn)引用關(guān)系挖掘算法的研究。提出用圖挖掘解決文獻(xiàn)間相似關(guān)系

2、的衡量問題，通過以文獻(xiàn)為結(jié)點(diǎn)構(gòu)造的圖形中的結(jié)點(diǎn)和結(jié)點(diǎn)之間的相互關(guān)系，反映出文獻(xiàn)和文獻(xiàn)之間的鏈接關(guān)系，并通過被引用的次數(shù)多少得到文獻(xiàn)的權(quán)威度。目前我們?cè)谧鰣D數(shù)據(jù)挖掘算法研究的時(shí)候，所用到的圖數(shù)據(jù)規(guī)模都不是很大，一般情況下都可以一次性的全部調(diào)入內(nèi)存并運(yùn)算。然而隨著數(shù)據(jù)規(guī)模的不斷增加，傳統(tǒng)的平臺(tái)面對(duì)這些海量的圖數(shù)據(jù)時(shí)，存在諸多的不足，無法保證較高的運(yùn)行效率。而以Hadoop和MapReduce為代表的技術(shù)平臺(tái)恰好可以解決這些問題。
　　

3、本文通過研究分析基于 Apriori思想的三種并行數(shù)據(jù)挖掘算法CD算法、DD算法和CaD算法以及它們?cè)贖adoop和MapReduce的具體實(shí)現(xiàn)。雖然基于 MapReduce編程模型實(shí)現(xiàn)后，上述三種數(shù)據(jù)挖掘算法有了一定程度的性能提升，但是上述算法在進(jìn)行數(shù)據(jù)挖掘時(shí)存在不足，比如在 Map實(shí)現(xiàn)階段步驟中，算法在循環(huán)迭代進(jìn)行計(jì)算的時(shí)候產(chǎn)生了很多不必要的重復(fù)鍵值對(duì)和不必要的內(nèi)存操作，導(dǎo)致處理速度緩慢，不能充分利用 MapReduce編程模型的特

4、性，增加了不必要的工作量。本文提出了一種改進(jìn)的MapReduce_Edge_Extend算法，實(shí)現(xiàn)了基于 MapReduce編程模型平臺(tái)下的頻繁子圖挖掘算法。該算法的主要的思路仍然是基于 Apriori思想，在進(jìn)行邊擴(kuò)展生成新的頻繁子圖時(shí)，利用已經(jīng)得到的K階頻繁子圖生成K+1階的頻繁子圖，減少了不必要的重復(fù)鍵值對(duì)，提高了數(shù)據(jù)挖掘的效率。在實(shí)驗(yàn)部分，考察上述提到的各種算法分別在傳統(tǒng)單機(jī)環(huán)境和在 Hadoop與MapReduce編程平臺(tái)兩種