一種基于hadoop平臺下的矩陣優化Apriori改進算法

梅 俊，陳建敏

(黃山職業技術學院 工貿系，安徽 黃山245000)

隨著互聯網技術的日新月異，數據增長速度迅猛。如何從海量數據中找出有用信息適應需求尤為重要，而海量數據挖掘系統[1]能夠更好地為相關應用提供決策支持，大部分挖掘系統依賴于分布式架構。Hadoop 框架[2]是由Apache 組織基金會開發的一個開源項目。Hadoop 與傳統數據處理方式不同之處在于面對海量異構數據能夠敏捷地處理，具有跨時代意義。其核心在于兩大模塊HDFS 與MapReduce。

在海量數據中尋找數據集之間隱藏的關系即為關聯規則挖掘[3]。Agrawal 等人在1994 年提出了Apriori 算法，就是一種關聯規則挖掘算法。其設計思想是通過掃描對比事務數據庫，得到支持度大于最小支持度的所有頻繁集，然后循環直到沒有最大頻繁項目集產生[4]。姚亮[5]針對Apriori不足，提出一種Apriori優化算法。對事務數據庫進行優化，將其轉化為0 或1 值的矩陣，將hash 算法應用于掃描數據庫中，直接生成頻繁2項集，為了減少連接比較次數，用共同前綴劃分的方法，在每個子空間內連接生成候選K項集。黃劍等人[6]針對Apriori 算法的頻繁生成時掃描事務數據庫需要花費大量時間，將數據中項壓縮成矩陣，通過對矩陣做運算，降低時間復雜度，并將改進算法應用于Hadoop平臺中。

1 Hadoop平臺

Hadoop 其核心在于兩大模塊HDFS[7]與MapReduce。HDFS（Hadoop Distributed File System）應用于大規模數據集存儲及訪問。而MapReduce 是以兩個函數Map（映射）和Reduce（歸約），負責對HDFS存儲的數據進行分布式運算，需將HDFS上的大數據塊分解成若干個數據塊，然后獨立執行，最終經過歸約得出結果。MapReduce的體系結構如圖1 所示，通過主節點Master 將輸入文件劃分成若干份，然后將程序復制到集群機器上，Mapper 讀取Split 中的數據，并轉換成鍵值對進行處理，將結果放進緩存中，Reducer 歸約數據，執行完成后輸出結果。

圖1 MapReduce體系結構

2 改進的矩陣優化Apriori_MR算法

2.1 算法思想

針對經典Apriori算法存在不足，如Apriori算法會多次訪問數據庫，每次生成Lk頻繁項目集需多次進行I/O 操作，且在自連接生成頻繁項集過程中產生大量候選集，存在很多冗余項，且Apriori 算法只能單線程處理，不適合并行大數據處理。在文獻[8-14]的基礎上，本文基于Hadoop平臺下，用0或1值來量化事務項，轉化為矩陣，經二次優化后減少3-項及以上的候選項目集合時間及數量，提出一種Apriori改進算法Apriori_MR。

首先，遍歷數據庫D將其事務項進行量化，用值為0或1代表當前事務項是否存在，如Dij位置為1表示第i條事務項中存在Ij項，為0則表示不存在。將其值寫入矩陣中，行列分別為每條事務、事務項。計算每列1 的個數即為各事務項的支持度，將大于最小支持度的項并入頻繁1-項目集合L1。

再對矩陣進行第一次優化，由定理[15]可知，頻繁2-項目集合L2中項不可能存在小于最小支持度事務項。因此，為了減少矩陣規模、去除生成候選集判斷時間，刪除小于最小支持度事務項所在的列。

經一次優化后，由1階-頻繁項目集L1自連接生成2 階-候選項目集C2，掃描矩陣，統計C2項的值為1的個數，例如I1I2∈C2,如果事務S1里，I1I2皆為1即個數為2，統計計數1 次，如此，統計2 階-候選項目集C2的各項支持度。將支持度大于最小支持度的2階-候選項目集C2中項目并入頻繁2-項目集合L2。

其次，對3階-候選項目集C3進行二次優化。為了減少3-項及以上的候選項目集合，縮短自連接過程中判斷時間，故統計各I 項在頻繁2-項目集合L2中出現的次數，按照次數大小降序排序，次數多的項放在前面。由自連接產生候選項目集過程可知，頻次高的項自連接生成候選項集判斷少，成為頻繁項集的可能性高，也會減少無用候選項目集產生。

由此反復直到生成的k項頻繁集的個數少于k+1時，算法終止。

2.2 并行化設計

根據算法將各個任務流程分解如下。

1.將存儲在HDFS 上輸入數據分成n 個規模相當的數據塊 inputsplit，格式為＜tid,itemset＞，每個 inputsplit分配到m個節點上。

2.生成1 階頻繁項集L1。掃描每個數據塊＜tid,itemset＞,Map 階段計算出各自分塊的所有1-項候選集C1，Reduce階段對所有Mapper結果進行合并即相同的項值累加，即為該項的總支持度，確定支持度不少于最小支持度的1 階-頻繁項目集合L1。構建向量矩陣，進行一次優化，刪除支持度低于最小支持度的列，以減少矩陣規模。

3.根據1 階頻繁集L1生成2 階候選項目集C2。將L1保存在HDFS，自連接生成2 階候選項目集C2，分配到各個節點上。在節點上先求局部支持度，map 函數產生＜項集，支持度＞鍵值對，使用combine函數合并所有mapper 生成新的＜項集，支持度＞,將支持度大于最小支持度的鍵值對并入局部頻繁2階項集，其他節點步驟相同，合并所有局部頻繁2階項集，得出全局頻繁2階項集L2。

4.自連接成3 階候選項目集C3。二次優化，先統計各項在頻繁2 階項集L2出現的次數，按從大到小順序重新排序頻繁2 階項集L2，快速自連接生成C3候選項目集，減少判斷時間。

5.重復第三步，統計支持度，確定全局頻繁3階項集L3。

6.重復第四步，自連接成4階候選項目集C4，按照第四步的步驟排序，重復第五步步驟。當生成的k項頻繁集的個數少于k+1時，算法終止。

2.3 算法實例

為了更好地說明Apriori_MR 算法，以下面的實例說明執行過程。

已知條件見表1。

表1 事務數據信息

每條事務中包含的事務項見表2。

表2 事務項包含項信息

1.量化事務。用0或1值簡化項集表示，轉化為矩陣。表3為事務量化表，行列分別為事務、項。

表3 事務量化表

2.優化矩陣，刪除不可能是頻繁集的事務項。由最后一列計數，可得出I6事務項支持度小于3，不可能是頻繁集，刪除I6項。

3.將事務矩陣劃分成2 個數據塊分配到2 個節點 上 D1={S1,S2,S3,S4},D2={S5,S6,S7,S8,S9}，Map 計算出各自分塊的所有1-項候選集C1，Reduce累加各自支持度，D1中{I1,I2,I3,I4,I5}支持度分別是{2,4,3,1,2},D2中{I1,I2,I3,I4,I5}支持度為{3,2,3,3,4},使用combine函數將所有mapper 函數的合并支持度為{5,6,6,4,6}與最小支持度相比較，得出頻繁集L1={I1,I2,I3,I4,I5}。

4.自連接L1生成2階候選項目集C2，生成2階候選項目集C2={I1I2,I1I3,I1I4,I1I5,I2I3,I2I4,I2I5,I3I4,I3I5,I4I5},Map計算出各自分塊的所有2-項候選集C2支持度，D1中C2支持度為{2,2,0,1,3,1,2,0,1,1},D2中C2支持度為{0，1，2,2,2,1,2,1,3,2},combine 函數合并總支持度為{2,3,2,3,5,2,4,1,4,3},最后得出L2={I1I3,I1I5,I2I3,I2I5,I3I5,I4I5}。

5.二次優化，優化三階候選項目集。在L2頻繁項集中對每個項出現的次數統計結果為{I1：2,I2：2,I3：3,I4：1,I5：4}，并將 L2頻繁項目集按照單項支持度降序排序{I5I3,I5I1,I5I2,I5I4,I3I1,I3I2},自連接快速生成C3候選項目集{I5I3I1,I5I3I2,I3I1I2}，減少自連接次數。而未經處理的L2頻繁項集自連接生成C3候選項目集為{I1I3I5,I1I3I2,I1I5I2,I1I5I4,I2I3I5,I2I4I5,I3I5I4}，產生了許多無用候選項目集。由C3候選項目集{I5I3I1,I5I3I2,I3I1I2},同上步驟在兩個節點中分別統計支持度，最后combine 函數合并得出3 階候選項目集支持度{2,3,2}，所以L3={I5I3I2}。

3 實驗驗證

3.1 平臺搭建

Hadoop集群環境搭建見表4。

表4 Hadoop集群環境配置表

3.2 實驗結果分析

實驗采用FIMI Repository(Frequent Item-set Mining Implementations Repository)數據集Webdocs.data，在該數據的基礎上，抽取其中100M,200M,300M,400M,500M。最小支持度為10%，15%，20%時，算法運行效率測試結果如圖2所示。

圖2 算法運行效率測試結果

實驗結果顯示，當支持度高時算法運行速度快，與支持度增加會造成頻繁集合減少的算法規律一致，驗證了Apriori_MR 算法的有效性。另一方面，當增加節點時，運行效率越高，證明算法的并行處理性能良好。

4 結束語

本文在深入研究Apriori算法和Hadoop平臺后，提出一種Apriori_MR 算法。該算法采用了事務壓縮矩陣，故不需要多次掃描事務數據庫，此外，由于算法采用二次優化，減少候選項目集產生，縮短候選項目集生成預判時間，并將改進算法結合Hadoop框架進行并行化實現。實驗證明，該算法的有效性與并行性良好，適用于大數據挖掘。