基于MapReduce的并行頻繁項(xiàng)集挖掘算法研究.pdf

1、關(guān)聯(lián)規(guī)則一直是數(shù)據(jù)挖掘領(lǐng)域中一個(gè)研究熱點(diǎn)，被廣泛的應(yīng)用于各個(gè)領(lǐng)域。隨著web2.0時(shí)代的到來，特別是以用戶為主導(dǎo)產(chǎn)生互聯(lián)網(wǎng)內(nèi)容的社交網(wǎng)絡(luò)的興起，數(shù)據(jù)積累呈現(xiàn)出指數(shù)級(jí)的增長趨勢(shì)。在面對(duì)海量的數(shù)據(jù)集時(shí)高效地使用關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘的重要任務(wù)。
　　本文對(duì)FP-Growth算法的并行化進(jìn)行了研究，在已有PFP算法基礎(chǔ)上，設(shè)計(jì)了一種新的并行FP-Growth算法。之所以要并行化，是因?yàn)橐诿鎸?duì)大規(guī)模數(shù)據(jù)處理時(shí)，傳統(tǒng)的FP-Growth算法是

2、基于單機(jī)的內(nèi)存消耗算法，因此會(huì)出現(xiàn)內(nèi)存不足或者執(zhí)行時(shí)間過長等問題?，F(xiàn)有的并行FP-Growth算法已經(jīng)解決了如劃分?jǐn)?shù)據(jù)庫事務(wù)集這一問題，可以保證劃分后的事務(wù)集彼此之間相獨(dú)立，但單節(jié)點(diǎn)在FP-tree挖掘過程中還是存在迭代次數(shù)過多，效率低下的問題，并且主節(jié)點(diǎn)向子節(jié)點(diǎn)劃分?jǐn)?shù)據(jù)集時(shí)也沒有考慮負(fù)載均衡。因此，實(shí)現(xiàn)高效率并且負(fù)載均衡的并行FP-Growth算法是本文要解決的問題。本文在PFP這種原有的基于MapReduce的并行FP-Growth

3、算法之上運(yùn)用剪枝策略，通過合并FP-tree中滿足條件的非頻繁路徑從而減少了其部分分支的迭代次數(shù)，加快了挖掘效率。另外，在主節(jié)點(diǎn)向子節(jié)點(diǎn)分配計(jì)算數(shù)據(jù)集時(shí)使用負(fù)載均衡策略，首先由Flist進(jìn)行各頻繁項(xiàng)的負(fù)載估計(jì)，然后通過負(fù)載均衡算法將頻繁項(xiàng)分組得到Glist。通過這兩種策略的結(jié)合，本文設(shè)計(jì)了一種新的并行FP-Growth算法，并設(shè)計(jì)實(shí)驗(yàn)證明該算法相對(duì)原算法在執(zhí)行效率上的提升。
　　本文將并行FP-Growth算法應(yīng)用在微博好友推薦上

4、，設(shè)計(jì)了一種基于關(guān)聯(lián)則的微博好友推薦算法。以往的社交網(wǎng)絡(luò)好友推薦往往是基于用戶之間的共同好友，但是微博除了具有社交網(wǎng)絡(luò)的屬性外，更加注重的是新鮮事的傳播，因此具有潛在好友關(guān)系的用戶不僅會(huì)關(guān)注相同的人，更加會(huì)關(guān)注相同的事（以用戶對(duì)微博的轉(zhuǎn)發(fā)或者評(píng)論體現(xiàn)）。本文將這兩點(diǎn)結(jié)合，利用新浪微博的開放API接口獲取用戶之間的關(guān)注數(shù)據(jù)和用戶對(duì)微博的關(guān)注數(shù)據(jù)，將這里的“關(guān)注”看成一條交易，用戶看成交易項(xiàng)，所有交易的集合看作交易數(shù)據(jù)庫。在此基礎(chǔ)上進(jìn)行并行