Hadoop 平臺下實現關聯規則挖掘的優化算法*

潘俊輝 張 強 王 輝 王浩暢

（東北石油大學 大慶 163318）

1 引言

隨著網上資源的爆炸式增長，在給用戶帶來便利的同時，也產生了海量的數據，而如何從海量的數據中挖掘出有價值的關系和規則，在現實生活中有著非常重要的作用。目前數據挖掘技術［1］已經成功地將已有的挖掘算法移植到云計算平臺上，從而實現海量數據的挖掘。而關聯規則挖掘是實現有價值的關系和規則挖掘的一種重要技術，目前已被廣泛地應用在眾多領域，如智能推薦、氣象預測等。針對目前互聯網上的海量數據，分布式關聯規則挖掘算法的出現將會更有效地解決當前的問題，即如何在云計算平臺上通過關聯規則實現從海量數據中挖掘出有價值的規則。

目前，一些學者對傳統的關聯規則算法和云計算結合也做了相應的一些研究。Li lingjuan 等學者［2］通過改進Hadoop 平臺內部的框架以滿足關聯規則挖掘的需求，提出了一種基于云計算的關聯規則挖掘方法；Yang Xinyue等學者［3］提出了一種基于Hadoop 的MapReduce 計算框架的關聯規則算法，該算法分別使用Map 和Reduce 進行候選項集的求解和歸約統計；孫學波等［4］提出了一種基于Hadoop的Apriori 算法的研究與優化，該算法通過引入FIS-IS 算法思想對事務數據庫的掃描次數和容量的消減方向做了相應的改進。

本文針對挖掘關聯規則的基本算法Apriori［5］所具有的不足之處，提出了一種基于壓縮矩陣的優化算法。由于Hadoop 平臺具有分布式處理的能力，同時根據Hadoop 平臺在對矩陣進行處理時所具有的優點，在此基礎上進一步設計出了一種Ha?doop平臺下的用來實現關聯規則挖掘的優化算法，該算法使用MapReduce 計算模型先對事務數據庫進行分塊，然后使用改進的基于壓縮矩陣的優化算法進行挖掘，最后對挖掘的結果進行合并操作，得到頻繁項集。文中在最后通過實驗將Hadoop 平臺下的基于壓縮矩陣的關聯規則優化算法（Com?pressed Matrix Association Rule Optimization Algo?rithm in Hadoop，CMARH）與傳統的Apriori 算法進行了對比分析，實驗結果表明優化后的算法在性能上更優。

2 關聯規則及Hadoop平臺

2.1 關聯規則

設I 是項的集合，交易數據庫為D，D 中的每個事務是項集I 的非空子集，每個事務對應一個唯一的標識符TID。假設X 是I 中的一個項集，當且僅當X ?T ，稱T 包含項集X，如果X 中包含k 項，稱其為k項集。

關聯規則是形如X ?Y 的邏輯蘊含關系，其中 X ?I，Y ?I ，且 X ∩Y=φ 。對 于 關 聯 規 則X ?Y ，存在支持度和置信度兩個約束［5～6］，支持度指D 中包含X 和Y 的條數占D 中總數的比值；置信度則指包含X和Y的條數與包含X的條數的比值。

2.2 Hadoop平臺

Hadoop［7］平臺主要包括兩部分，分別是HDFS（Hadoop Distributed File System，分布式文件系統）和MapReduce編程框架。下面簡單介紹一下HDFS和MapReduce。

2.2.1 HDFS

HDFS 是一種分布式的文件系統，它包含兩類節點，分別稱之為名稱節點（NameNode）和數據節點（DataNode）。其中，NameNode由FsImage和Edit?Log 兩個核心數據結構構成，其工作是負責管理分布式文件系統的中的所有文件和元數據以及對通過日志文件記錄對文件所進行的各種操作活動。DataNode 則是HDFS 的工作節點，主要負責數據的存儲和讀取，它會根據客戶端或者NameNode 的調度來進行數據的存粗和檢索，并向NameNode 定期發送自己所存儲的塊的列表［8～10］。

2.2.2 MapReduce

MapReduce是Google公司的核心計算模型，它的核心是Map 函數和Reduce 函數，這兩個函數都是以＜key，value＞作為輸入，按一定的映射規則轉換成另一個或一批＜key，value＞進行輸出。在Ma?pReduce 中，其中Map 任務負責將分解后的數據進行并行化的處理，而其計算所得結果會被作為Re?duce 的輸入，然后由Reduce 負責計算輸出并將結果寫入HDFS［8～10］。

3 Hadoop 平臺下實現關聯規則挖掘的優化算法

由于Hadoop 平臺具有分布式處理的能力，同時根據Hadoop 平臺在對矩陣進行處理時所具有的優點，本文設計出了一種Hadoop 平臺下實現關聯規則挖掘的優化算法，該算法主要通過使用Ma?pReduce 計算模型先對事務數據庫進行分塊，然后分別進行Map 端和Reduce 端的操作，最后給出了CMARH算法和流程圖。

3.1 基于壓縮矩陣的關聯規則挖掘算法流程

在介紹Hadoop 平臺下實現關聯規則挖掘的優化算法之前，先來介紹一下基于壓縮矩陣的關聯規則挖掘算法的具體實現流程。

Step 1：設minsup，k=1。初始化數組A，A 用于存儲矩陣中每列1的數量［11～12］。將D轉換為與其對應的布爾矩陣M。

Step 2：掃描M，計算得到每行的支持度大小sup。比較每行的sup 與minsup 的關系，刪除小于minsup 的行向量，而將大于minsup 的行向量所對應的頻繁項組成1 項集L1，并根據L1中各項sup 的大小排序得到一個新的矩陣M1［13～14］。

Step 3：將M1的行與行按順序分別進行向量的內積運算，運算后將結果不小于minsup 的行向量組成2 項集L2并獲得矩陣M2。同時對不小于min?sup的行向量按位累加到A中，令k=2［13～14］。

當k 不小于2 時按照Step 4、Step 5、Step 6 循環進行操作。

Step 4：掃描Mk，刪除Lk中不能和其相鄰的項集進行連接的行向量，然后將A 值進行修改，最后對刪除后保留的行向量組合得到矩陣Mk［14］。

Step 5：掃描A，刪除A 中其值小于1 的列向量，然后將保留的列向量組合得到矩陣Mk［14］。

Step 6：清空A。將Mk中的可相互連接的那些項集分別進行內積運算，滿足minsup 的行向量構成k+1 項集Lk+1，同時形成矩陣Mk+1，并對滿足min?sup 的行向量按位累加到A 中。比較Mk+1的行數與k+2的大小，如小于k+2，算法結束，否則k=k+1［14］。

3.2 數據分塊

由于CMARH 算法是要利用MapReduce 計算模型來實現上述的基于壓縮矩陣的關聯規則的挖掘，在了解基于壓縮矩陣的關聯規則挖掘算法之后，接下來要進行的工作是要進行事務數據庫的數據分塊工作。在對事務數據庫進行分塊的過程中，數據塊的大小對算法的執行效率有很大的影響，如果每塊數據過小將會增加數據傳輸的時間，而過大則會造成節點的運算壓力增加。因此本文采用并行分割的方法，并行計算獲得每個結點的頻繁項目集，然后將各個節點的頻繁項集進行統計以得到全局的頻繁項集［15］。

3.3 Map端實現

如下給出了CMARH 算法Map 端實現的偽代碼描述。

Input：DBi（i=1，2…，n）

Output：各結點的局部Lk和c.sup

偽代碼描述的算法：

1）L1=Sear_fre1_itemsets（DBi）；//對分割后的局部數據塊進行掃描，得到頻繁1項集

2）調用基于壓縮矩陣的關聯規則挖掘算法 //調用算法產生局部頻繁項集

3）for each c in Ci｛

4）sup+1

5）｝

6）生成each c 的支持度

7）返回合并集的支持度＜c，c.sup＞

3.4 Reduce端實現

Reduce 端的主要工作是對合并頻繁項目集后與設定的minsup 比較，如果不小于全局支持度，最后得到全局頻繁項集。如下給出了CMARH 算法Reduce端實現的偽代碼描述。

Input：＜c，c.sup＞

Output：全局的頻繁1項集到K項集

偽代碼描述的算法：

1）Combine all ＜c，c.sup＞

2）num=sum_each（c，s_sum） //對計數進行統計

3）if（num ≥minsup）

4） Insert（Lk，c） //加入得到的該頻繁k項集

5）end if

6）return 并集Lk//得到全局頻繁項集/

3.5 CMARH算法描述

針對上述的介紹，下面就來介紹一下Hadoop平臺下關聯規則挖掘的優化算法CMARH 的具體實現過程，圖1給出了該算法的流程圖。

Step 1：將事務數據庫D 進行水平分割，將分割得到n個的data block發送到集群的m個節點，開始進行Map端的工作。

Step 2：數據發送到m個不同節點之后，將它們依次轉換成對應的布爾矩陣。然后掃描獲得頻繁1項集，同時生成局部頻繁矩陣。

Step 3：分別對矩陣進行行和列的壓縮，具體行和列的壓縮過程已經在基于壓縮矩陣的關聯規則挖掘算法中介紹過。

Step 4：把每個節點上得到的壓縮矩陣進一步轉化為局部頻繁項集。

Step 5：合并具有相同key 的鍵值對＜c，c.sup＞，然后統計局部支持度，將其與設定的最小支持度進行比較，如果不小于，那么就將其加入到頻繁k 項集中。最終構成并集Lk。

Step 6：根據置信度大小的比較，循環計算得到最終符合要求的關聯規則。

圖1 算法CMARH的流程圖

4 應用實例

本文對Hadoop 平臺下的基于壓縮矩陣的關聯規則優化算法CMARH與傳統的挖掘算法

Apriori 進行了實驗和實驗結果的對比分析。本實驗的進行通過采用了7臺VMWare虛擬機實現對Hadoop 平臺集群的搭建，其中使用1 臺機器作為集群中的主節點，剩下的6 臺機器則用來作為從節點。實驗中第一組采用條數不同、大小不同的事務數據庫，第二組則采用同一大小的事務數據庫，但針對不同的支持度進行對比分析。表1 和表2分別給出了兩組不同數據下的實驗對比分析結果。

表1 不同條數的事務數據庫實驗對比分析結果

由表1 可得，CMARH 算法在運行時間上遠小于Apriori 傳統算法，而且隨著事務條數的增加，雖然CMARH 算法運行時間也在增加，但是兩者的差距也在逐漸變大，當數據量越大時，CMARH算法的優勢越明顯。同時在表中可以看出當數據量達到100 萬條時，傳統的Apriori 算法由于時間過大，已經無法把執行時間顯示在表中。

表2 同一事務數據庫設置不同支持度的實驗對比分析結果

由表2 可得，這兩種算法的運行時間隨著支持度的增加都在減少，但CMARH 算法所用時間遠小于Apriori 算法，而支持度越小，兩種算法在運行時間上的差距就越大，由此可見CMARH 算法在挖掘支持度較小的關聯規則時運算效率更高。

5 結語

本文首先介紹了關聯規則和Hadoop 開源云平臺中的HDFS 分布式文件存儲及MapReduce 分布式編程的相關知識，針對傳統Apriori算法的不足和Hadoop 平臺在對矩陣進行處理時所具有的優點，提出并設計出了一種Hadoop 平臺下的基于壓縮矩陣的關聯規則優化算法CMARH，然后詳細介紹了該算法的具體實現過程和詳細流程，最后通過兩組實驗對CMARH 算法和Apriori 算法進行了對比分析，實驗結果均表明CMARH 算法在運算時間上有極大的提高。