MapReduce框架下改進Apriori算法的研究

楊健兵

(南通科技職業學院 信息與智能工程學院，江蘇 南通 226007)

MapReduce框架下改進Apriori算法的研究

楊健兵

(南通科技職業學院 信息與智能工程學院，江蘇 南通 226007)

MapReduce是一種編程模型，這種模型編程簡單，可以用于大規模數據集的并行計算。Apriori算法是一種發現頻繁項集的基本算法，通過該算法，可以產生關聯規則。針對Apriori的特點，研究了在MapReduce編程模型下，Apriori的實現方法。實驗結果表明：該方法在對大數據集進行頻繁項集挖掘時, 可充分利用云計算的優勢, 從而能獲得更好的時效性。

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

0 引言

隨著計算機和互聯網技術的飛速發展，海量的數據不斷地產生。數據挖掘技術是通過數據挖掘算法從海量數據中找到有意義的模式或知識，這些知識對于企業和政府決策起了很大的作用。傳統的數據挖掘算法往往在普通的計算機上運行，面對大量的數據時，在計算能力、處理速度、存儲容量、帶寬速度等多個方面往往表現出力不從心。云計算在計算機網絡的基礎上，將計算機龐大的處理程序通過云計算機平臺分解成小子程序，采取分而治之的方式加以解決。

在大規模數據集的并行運算方面，MapReduce[1]是一種用得比較多的編程模型，其主要思想是Map和Reduce，它可以在程序開發人員不會分布式并行編程的情況下，將程序運行在分布式系統上。

Hadoop[2-4]是一個由Apache基金會所開發的分布式系統基礎架構。用戶可以在不知曉分布式文件系統實現細節的環境下開發分布式程序。HDFS和MapReduce是 Hadoop的框架最重要的設計，HDFS為海量的數據存儲提供了可能，而MapReduce則為海量的數據提供了計算。通過Apache開源社區Hadoop項目[5]，程序設計人員實現了該模型，使的該模型進行分布式并行計算成為可能。

多種Apriori算法已經在云計算編程模型MapReduce上實現。本文結合各自算法的思想與MapReduce 的運行機理，提出MapReduce框架下Apriori算法的研究。在MapReduce的框架下，Apriori算法的使用范圍由單機擴展到云計算平臺，極大地減少了Apriori算法的運行時間，顯著地提高了運行的效率。

1 MapReduce編程模型

圖1 MapReduce 運行流程圖

MapReduce在海量數據進行并行計算中使用廣泛，美國的Google 公司首次開發出了該技術框架。由Map和Reduce這兩個核心步驟組成。MapReduce 接受到一個作業時，將該作業拆分成一系列任務，然后把這些任務按照一定的原則分配到不同的機器節點上去執行，當Map 處理完任務以后，將會產生一些中間文件，這些中間文件就成了Reduce的輸入數據。Reduce把前面若干個Map 產生的中間結果進行排序匯總后一并輸出。MapReduce的數據流圖如圖1 所示。

2 Apriori算法在MapReduce框架下的實現

2.1 Apriori算法

Apriori算法是一種挖掘關聯規則的頻繁項集算法。Apriori算法使用迭代方法，該迭代方法使用逐層搜索的技術，通過k項集產生(k+1)項集。首先，通過掃描整個數據庫，累計每個項的數量，計算滿足最小支持度的項，找到頻繁1項集，該集合記為L1項集。然后通過L1項集找到頻繁2項集，該集合記為L2。通過使用L2找到L3，迭代下去，直到不能再找到頻繁K項集。

定義1 頻繁項集的所有非空子集一定也是頻繁的。

證明：根據定義，如果項集I不能滿足最小支持度min_sup，則I不是頻繁的，即P(I)

Apriori的核心思想是連接步和剪枝步。連接步是自連接，原則是保證前k-2項相同，并按照字典順序連接。剪枝步是使任一頻繁項集的所有非空子集也必須是頻繁的。反之，如果某個候選的非空子集不是頻繁的，那么該候選肯定不是頻繁的，從而可以將其從CK中刪除。Apriori算法的串行計算流程如圖2所示。

圖2 Apriori算法的串行計算流程

(1)連接步

為了找出Lk，通過將Lk-1與自身連接產生候選k項集的集合。該候選項集的集合為Ck。設l1和l2是Lk-1項集。li[j]表示li的第j項。Apriori算法假定事務或者項集中的項按照字典序排列，對于(k-1)項集li，這意味著把項排序，使得li[1] < li[2]< …< li[k-1]。執行連接lk-1和lk-1，如果它們前(k-2)個項相同。即lk-1的元素l1和l2是可連接的。連接l1和l2產生的結果項集是{l1[1], l1[2]]，…，l1[k-1]，l2[k-1]}。

(2)剪枝步

Ck是Lk的超集，也就是說，Ck的成員可以是也可以不是頻繁的，但所有的頻繁k項集都包含在Ck中。掃描數據庫，確定Ck中每個候選的計數，從而確定Lk。然后Ck可能很大，因此所涉及的計算量很大。為了壓縮Ck，可以用以下辦法使用定義1。任何非頻繁的(k-1)項集都不在頻繁k項集的子集。因此，如果一個候選k項集的(k-1)項集不在Lk-1中，則該候選也不可能是頻繁的，從而可以從Ck中刪除。

2.2 Apriori算法分析

傳統的Apriori算法首先通過生成頻繁1項集，通過頻繁1項集產生頻繁2項集，依次類推。在產生頻繁項集的過程中，每產生一個頻繁項集，就需要掃描整個數據庫。但數據量比較大的時候，每次掃描數據庫需要耗費大量的時間，這種掃描數據庫過程增加了系統運行的時間，降低了系統效率。

2.3 改進的Apriori算法在MapReduce模型下實現

輸入部分：在HDFS的文件系統中存儲事務數據庫D以及最小支持度閾值min_sup。輸出部分：L,D中的頻繁項集。

①L1=find_frequent_1_itemsets(D)。

②Map過程，通過L1把每條記錄轉換成行向量，行向量記住v。

③reduce過程，生成矩陣，計算候選項集的局部支持度。

④計算全局支持度。

⑤得到關聯規則。

該算法共分為兩個階段。在第一階段，執行算法第①步查找候選項集，通過計算得到頻繁項集L1。然后把L1存放到數據庫中以備第二階段使用。在MapReduce第二階段，采用改進的Apriori算法，該改進的算法采用矩陣思想來計算候選項集的局部支持度。在reduce任務中，合并相同的key再生成矩陣，算出局部支持頻度。通過計算出來的局部支持頻度計算全局支持頻度，如果全局支持頻度大于最小支持頻度閾值，則把候選項集歸為頻繁項集。最后根據頻繁項集得到關聯規則。

2.4 算法實例分析

假定D 有9 條交易記錄，D={T100、T200、T300、T400、T500、T600、T700、T800、T900}，如表1所示，I 是項目的集合，且I={I1，I2，I3，I4，I5}。把D 上傳到HDFS 中，且其被分成兩個數據塊D1={ T100、T200、T300、T400、T500 }和D2={ T600、T700、T800、T900}。最小支持頻度閾值為3。

改進的Apriori算法在執行MapReduce第一階段任務的時候會生成頻繁1項集。以T100為例，它將產生鍵值對：、、，其他交易記錄也會產生相應的鍵值對。所以我們得到I1的支持頻度為6，它大于最小支持頻度。通過類似的方法，可以獲得L1{，，}。

表1 事務數據

改進的Apriori算法在執行MapReduce第二階段任務的時候，在Map階段，把表1的數據分成D1和D2兩個部分，將D1和D2分配給不通的Map任務進行執行。通過使用頻繁1項集L1把數據轉換成一個行向量v，向量中的元素為頻繁1項集中所對應的元素，即I1，I2，I3。如果數據中存在該向量的元素，則對應部分為‘1’，否則為‘0’。數據的行向量表示如表2和表3所示。

表2 數據塊D1向量表示

表3 數據塊D2向量表示

TIDI1I2I3T600011T700101T800111T900111

設表2數據塊D1向量用矩陣來表示，該矩陣為G1，表3數據塊D2向量用矩陣來表示為G2，設它們的轉置矩陣分別是G1’和G2’，則G1’和G2’分別如表4和表5所示。

表4 數據塊D1的轉置矩陣G1

表5 數據塊D2的轉置矩陣G2″

在Reduce階段，可以設置兩個Reduce任務，分別處理不同的key鍵值，具有相同key的都被送到同一Reduce任務進行執行。以表2為例，首先生成矩陣G1，然后再生成轉置矩陣G1′，另外一個任務也是相同的方法進行處理。

數據塊D1的轉置矩陣G1′可以看做是由一系列行向量組成的，即I1={1,0,0,1,1}，I2={1,1,1,1,0} I3={0,0,1,0,0}，由于頻繁1項集為{I1，I2，I3}，所以可以計算出候選Lk(k>=2)項集肯定是{I1，I2，I3}這幾個頻繁1項集的組合。根據G1′的實際情況，它的候選項集分別是{I1，I2}，{I1，I3}，{I2，I3}，{I1，I2，I3}。以{I1，I2}為例，它的局部支持度為{1,0,0,1,1}&{1,1,1,1,0}=1&1+0&1+0&1+1&1+1&0=2。運用相同的計算方法，{I1，I3}，{I2，I3}，{I1，I2，I3}的局部支持度分別是1，1，0。

對于轉置矩陣G2’可以同樣計算出{I1，I2}，{I1，I3}，{I2，I3}，{I1，I2，I3}的局部支持度為2，3，3，2。

在執行完MapReduce第二階段任務后，把候選項集所對應的局部支持度累加起來，就可以生成全局支持度計數，進而可以生成頻繁項集。由于在本實例中設定的最小支持度閾值為3，根據規則可以生成頻繁項集為{I1}，{I2}，{I3}，{I1，I2}，{I1，I3}，{I2，I3}。

2.5 改進的Apriori算法分析

改進的Apriori算法在計算頻繁項集的過程中，對數據庫僅需要兩次掃描。同時利用MapReduce模型，可以在大量數據的情況下進行平行計算。這種模型的使用降低了空間復雜度和時間復雜度，高效利用了平行的優勢。特別是在數據量非常大的情況下，能夠提高系統效率，節省時間。

3 實驗結果

通過實驗，改進的Apriori算法在MapReduce框架下實現效果進行了展示和評估。

3.1 實驗環境

本實驗在南京工業大學云平臺進行實驗。該平臺由一系列IBM服務器構建。其中管理節點1個，計算機節點16個，網絡采用萬兆網絡，操作系統采用RedHat Linux。在硬件配置上，每一個節點的CPU 采用Intel Xeon 2.0GCPU，8G內存，100G硬盤，軟件配置Hadoop 。

3.2 實驗數據

實驗數據來自于某大型超市數據庫交易記錄信息，在進行數據分析之前，我們對數據進行了預處理，包括數據的清理、集成、變換等。為了便于實驗，對這些文件進行了多次備份并進行了合并以得到不同大小的文件。數據集規模大小如圖表6所示。

表6 預處理后數據集

3.3 實驗結果

圖3 兩種不同算法數據分析圖

在處理大數據的過程中，在MapReduce框架下改進Apriori算法所使用的時間明顯要大于在MapReduce框架下改進的Apriori算法。并且從圖3中可以看出，在數據量由10百萬條增加到40百萬條的時候，傳統的Apriori算法用時明顯增加，而MapReduce框架下改進的Apriori算法所消耗的時間增加不是太多，這說明MapReduce框架下改進的Apriori算法在處理大規模數據集的時候擁有更大的加速比，更適合處理大量的數據。

4 結語

隨著互聯網業務的不斷發展，每天都有大量的數據產生，對于產生的數據用數據挖掘的方法對它進行分析并提取有益的信息已經成為大家關注的對象。在源源不斷的數據產生以后，我們可以通過在MapReduce框架下改進的Apriori算法進行關聯規則分析，從而產生對現實有意義的知識。

本文提出了一個思路，在面對大量數據的時候如何使用MapReduce框架去處理這些數據。實驗表明，該解決方法在面對大量數據的時候可以極大地提高運行速度、縮短運行時間、提高運行效率。

[1] Dean j,Ghemawat S. MapReduce simplified data processing on large cluster[J].Communication of the ACM,2006,51(1):107-113.

[2] Dean Jeffrey,Ghemawat Sanjay.Mapreduce:simplified data processing on large clusters[J]．Communications of the ACM,2005,51(1):107-113.

[3] 劉騫，陳明．基于改進的Map/Reduce及模式空間劃分的數據挖掘[J]．微電子學與計算機，2011(08)：140-142.

[4] 李建江，崔健，王聃，等.Mapreduce并行編程模型研究綜述[J].電子學報，2011(11)：2635-2642.

[5] Apache Hadoop. Hadoop[EB/OL].[2011-02-15].http://hadoop.apache.org.

責任編輯：程艷艷

Research of Improved Apriori Algorithm under MapReduce Framework

YANG Jianbing

(Department of Information and Intelligence Engineering,Nantong Vocational College of Science and Technology, Nantong 226007, China)

MapReduce is a programming model, which is simple, can be used for parallel computing of large-scale data sets. Apriori algorithm is a basic algorithm to discover frequent item sets, and association rules are generated from it. In view of the characteristics of Apriori, this paper analyzes the realization method of Apriori under MapReduce programming model. Experimental results show that the proposed method can make full use of the advantages of cloud computing in the frequent item sets mining on large data sets, having better effectiveness.

Apriori; data mining; association rule; MapReduce

2016-09-02

楊健兵(1976-)，江蘇海門人，講師，碩士，主要從事數據挖掘和人工神經網絡方面研究。

TP301

A

1009-3907(2016)08-0040-04