基于MapReduce的Apriori算法并行化改進

秦 軍，郝天曙，董倩倩

(1.南京郵電大學 教育科學與技術學院，江蘇 南京 210003；2.南京郵電大學 計算機學院，江蘇 南京 210003)

基于MapReduce的Apriori算法并行化改進

秦 軍1，郝天曙2，董倩倩2

(1.南京郵電大學 教育科學與技術學院，江蘇 南京 210003；2.南京郵電大學 計算機學院，江蘇 南京 210003)

基于MapReduce的并行Apriori算法解決了傳統Apriori算法多次掃描數據庫的問題，但是其候選集仍然由頻繁項集經過串行自連接產生,并產生了大量的候選集中間數據。為了提高Apriori算法挖掘頻繁項集的效率，在基于MapReduce的Apriori算法的基礎上對連接步進行并行化改進，提出大數據環境下挖掘頻繁項目集的新算法—CApriori算法。新算法通過Map、Reduce過程從頻繁k-項集中并行得到k+1項候選集，使得Apriori算法產生頻繁項集的整個過程并行化，減少了迭代過程中候選集數目，節約了存儲空間和時間開銷。通過對時間復雜度進行分析比較，改進算法在處理大規模數據時會大大減少連接步的時間消耗。將CApriori算法在Hadoop平臺上進行了實驗，結果表明改進算法在大數據和較小支持度環境下都具有更高的效率，且能取得優異的加速功能。

關聯規則；數據挖掘；MapReduce；Apriori

0 引 言

關聯規則[1]挖掘用于從大量數據中挖掘出有價值的數據項之間的相關關系。關聯規則揭示了數據項間未知的依賴關系，根據所挖掘的關聯關系，可以從一個數據對象的信息來推斷另一個數據對象的信息。關聯規則最為經典的是Apriori算法，該算法采用逐層迭代方法，通過連接和剪枝得到頻繁項集。其缺點是重復掃描數據庫，產生大量的候選集，算法效率較低。……