一種基于MapReduce的關(guān)聯(lián)規(guī)則挖掘算法

□周國軍

（玉林師范學(xué)院 數(shù)學(xué)與信息科學(xué)學(xué)院，廣西 玉林 537000）

一種基于MapReduce的關(guān)聯(lián)規(guī)則挖掘算法

□周國軍

（玉林師范學(xué)院 數(shù)學(xué)與信息科學(xué)學(xué)院，廣西 玉林 537000）

本文從減少I/O時間的角度出發(fā)，結(jié)合云計算Hadoop平臺的MapReduce模型，提出了一種基于MapReduce的關(guān)聯(lián)規(guī)則挖掘算法. 算法采用冪集計算候選項集，采用MapReduce模型在多個節(jié)點上并行找出所有頻繁項集，只需要掃描事務(wù)數(shù)據(jù)庫1次. 實驗結(jié)果表明：在事務(wù)的平均項長較小的情況下，算法具有很好的加速比和數(shù)據(jù)規(guī)模增長性.

關(guān)聯(lián)規(guī)則；MapReduce；云計算；Hadoop

1 引言

關(guān)聯(lián)規(guī)則挖掘是一種重要的數(shù)據(jù)挖掘方法，其目標(biāo)是從大型事務(wù)數(shù)據(jù)庫中找出隱藏的、有趣的、屬性間存在的關(guān)聯(lián)和規(guī)律[1].Agrawal等人在1994年提出的Apriori算法[2]是最有影響力的關(guān)聯(lián)規(guī)則挖掘算法，已經(jīng)有很多學(xué)者針對Apriori算法需要多次掃描數(shù)據(jù)庫、產(chǎn)生大量候選項集的缺點進(jìn)行了改進(jìn).隨著計算機技術(shù)的發(fā)展，各行業(yè)、各部門積累的數(shù)據(jù)在急劇增長，對大數(shù)據(jù)進(jìn)行關(guān)聯(lián)規(guī)則挖掘需要強大的計算能力，傳統(tǒng)的串行算法已不能滿足這個要求.隨著云計算[3]的出現(xiàn)，利用云計算技術(shù)對大數(shù)據(jù)進(jìn)行關(guān)聯(lián)規(guī)則挖掘已成為一種新的解決方法[4].

MapReduce[5]是Google提出的一種處理大數(shù)據(jù)的并行編程模型，它將復(fù)雜的數(shù)據(jù)處理過程抽象成兩個函數(shù)：Map和Reduce，Map函數(shù)和Reduce函數(shù)可以在分布式集群的大量節(jié)點上并行運行，從而達(dá)到了快速、高效地處理大數(shù)據(jù)的要求[6].Hadoop[7]是Apache軟件基金會開發(fā)的一個開源的分布式計算框架，也是一個典型的云計算平臺，它實現(xiàn)了Google的MapReduce模型，可以在大量廉價的硬件設(shè)備組成的集群上運行MapReduce應(yīng)用程序，目前已經(jīng)有一些關(guān)聯(lián)規(guī)則挖掘算法在Hadoop平臺上得到了改進(jìn)和實現(xiàn)，取得了很好的數(shù)據(jù)挖掘效果[8].

在關(guān)聯(lián)規(guī)則的挖掘過程中，對事務(wù)數(shù)據(jù)庫進(jìn)行掃描需要耗費較多的I/O時間，影響了算法執(zhí)行的效率.本文從減少I/O時間的角度出發(fā)，結(jié)合云計算Hadoop平臺的MapReduce模型，提出了一種基于MapReduce的關(guān)聯(lián)規(guī)則挖掘算法.

2 相關(guān)知識及定義

2.1 本文算法的相關(guān)知識及定義

設(shè)事務(wù)數(shù)據(jù)庫為D，事務(wù)T(T∈D)的所有項構(gòu)成的集合稱為項集，D中的所有項構(gòu)成的集合表示為I={I1，I2，…，Im}，其中Ik(1≤k≤m)是項的編號.

定義1項集A(A∩I)在事務(wù)數(shù)據(jù)庫D中出現(xiàn)的頻率稱為項集A的支持度，記為support(A)，如果A滿足預(yù)定義的最小支持度閾值，則稱A是頻繁項集.

定義2關(guān)聯(lián)規(guī)則表示為“A=＞B”的蘊涵式，其中A∩I，B∩I，A∩B=φ，A稱為規(guī)則的前件，B稱為規(guī)則的后件.D中同時包含A和B的事務(wù)數(shù)與包含A的事務(wù)數(shù)的百分比稱為關(guān)聯(lián)規(guī)則“A=＞B”的置信度，其計算公式為：

如果A∪B滿足最小支持度閾值，confidence(A=＞B)滿足最小置信度閾值，則稱關(guān)聯(lián)規(guī)則“A=＞B”是強關(guān)聯(lián)規(guī)則.

定義3對于任意一個非空集合X，X的全部子集作為元素構(gòu)成的集合ρ(X)稱為X的冪集[9].

定義4對于任意集合X和Y，且X是Y的一個真子集，由Y中所有不屬于X的元素構(gòu)成的集合稱為集合X在Y中的補集.

2.2 Hadoop平臺的MapReduce模型

Hadoop采用分布式文件系統(tǒng)（簡稱HDFS）存儲數(shù)據(jù)，一個大數(shù)據(jù)集被劃分多個較小的數(shù)據(jù)塊，這些數(shù)據(jù)塊分別存儲在集群內(nèi)的多個節(jié)點上.Hadoop的MapReduce框架采用主/從式結(jié)構(gòu)：主節(jié)點稱為JobTracker節(jié)點，負(fù)責(zé)將計算任務(wù)分配給各個從節(jié)點；從節(jié)點稱為TaskTracker節(jié)點，負(fù)責(zé)執(zhí)行具體的計算任務(wù).

MapReduce程序使用鍵/值對來處理數(shù)據(jù)，在一個程序中可以有多個MapReduce任務(wù)，每個MapReduce任務(wù)都需要創(chuàng)建并啟動一個Job去執(zhí)行，Job通過執(zhí)行Map函數(shù)和Reduce函數(shù)來完成計算和數(shù)據(jù)處理任務(wù)，一般的執(zhí)行過程如下：

（1）Hadoop把數(shù)據(jù)塊的記錄解析成鍵/值對，輸出到Map函數(shù).Map函數(shù)對表示的數(shù)據(jù)進(jìn)行計算或處理，把產(chǎn)生的結(jié)果以list的形式輸出到多個節(jié)點的Reduce函數(shù).

（2）Redcue函數(shù)接收表示的數(shù)據(jù)，然后對數(shù)據(jù)進(jìn)行計算或處理，最后將產(chǎn)生的結(jié)果以list的形式輸出到HDFS中.

一般的MapReduce數(shù)據(jù)流如圖1所示[10].

圖1 MapReduce的數(shù)據(jù)流

Map函數(shù)輸出的數(shù)據(jù)量往往很大，為了減少Map與Reduce之間傳輸?shù)臄?shù)據(jù)量，可以定義一個用于將Map輸出的中間結(jié)果進(jìn)行合并的Combine函數(shù)[11].在MapReduce模型中添加Combine函數(shù)后，Map函數(shù)產(chǎn)生的結(jié)果就輸出到本地的Combine函數(shù)，Combine函數(shù)對key相同的value進(jìn)行合并或處理，并將產(chǎn)生的結(jié)果以list的形式輸出到多個節(jié)點的Reduce函數(shù).可見，使用Combine函數(shù)可以提高M(jìn)apReduce任務(wù)的執(zhí)行效率.

在一個節(jié)點上可以啟動1個或多個Map（Reduce）進(jìn)程去執(zhí)行Map（Reduce）函數(shù)，Map或Combine進(jìn)程產(chǎn)生的結(jié)果輸出到哪一個Reduce進(jìn)程是由Partition分區(qū)函數(shù)決定的，分區(qū)函數(shù)返回值一般定義為：hash(key) % nReduce，其中nReduce是集群中Reduce進(jìn)程的總個數(shù).

3 算法的基本思想及描述

3.1 算法的基本思想

關(guān)聯(lián)規(guī)則的挖掘過程可以概括為兩個步驟：第一步是從事務(wù)數(shù)據(jù)庫中找出所有頻繁項集，第二步是根據(jù)最小置信度閾值由頻繁項集產(chǎn)生強關(guān)聯(lián)規(guī)則[10].

在第一步的過程中，為了減少算法執(zhí)行所需的I/O時間，本文采用冪集求候選項集，只需要掃描事務(wù)數(shù)據(jù)庫1次便可找出所有頻繁項集.方法如下：對事務(wù)T的項集Ik求冪集ρ(Ik)，ρ(Ik)中除之外的其他元素即是候選項集.例如：一個事務(wù)T的項集Ik={I1,I3,I5}，Ik的冪集ρ(Ik)={φ,{I1},{I3},{I5},{I1,I3},{I1,I5}, {I3,I5},{I1,I3,I5}}，則事務(wù)T包含的所有候選項集為：{I1},{I3},{I5},{I1,I3},{I1,I5},{I3,I5}, {I1,I3,I5}.接下來，Map函數(shù)計算候選項集的局部支持度，Reduce函數(shù)對局部支持度求和，得到全局支持度，然后根據(jù)最小支持度閾值，輸出頻繁項集及其支持度.

在第二步的過程中，采用冪集和補集求出所有關(guān)聯(lián)規(guī)則.方法如下：對頻繁項集l的項集Ik求冪集ρ(Ik)，ρ(Ik)中除φ和Ik之外的其他元素即是關(guān)聯(lián)規(guī)則的前件A，對中除和Ik之外的其他元素求其在Ik中的補集Ic，Ic便是關(guān)聯(lián)規(guī)則的后件B.根據(jù)最小置信度閾值，就可以得到所有“A=＞B”的強關(guān)聯(lián)規(guī)則.例如：頻繁項集l的項集Ik={I1,I2,I4}，Ik的冪集ρ(Ik)={φ,{I1},{I2},{I4},{I1,I2},{I1,I4},{I2,I4},{I1,I2,I4}}，求關(guān)聯(lián)規(guī)則的過程如下：A={I1}，A在Ik中的補集B={I1,I2,I4}{I1}={I2,I4}，則得到一條關(guān)聯(lián)規(guī)則I1=＞I2∧I4.相應(yīng)的可以求出其他關(guān)聯(lián)規(guī)則：I2=＞I1∧I4，I4=＞I1∧I2，I1∧I2=＞I4，I1∧I4=＞I2，I2∧I4=＞I1.

3.2 算法描述

（1）將事務(wù)數(shù)據(jù)庫D分成多個數(shù)據(jù)子集Di，事務(wù)T(T∈Di)解析成 <事務(wù)Tid，項集Ik> 鍵/值對輸入Map函數(shù).Map函數(shù)計算事務(wù)T的候選項集c，將候選項集c及其支持度計數(shù)1以鍵/值對形式輸出到Combine函數(shù)，偽代碼如下：

（3）定義一個分區(qū)函數(shù)Partition：hash(c) % nReduce，其中hash(c)返回候選項集c在候選項集集合中的字典順序編號，nReduce是集群中Reduce進(jìn)程的總個數(shù).

（4）Reduce函數(shù)計算候選項集c的全局支持度support，如果c滿足最小支持度閾值，則將c及其支持度以 鍵/值對輸出到HDFS文件中，偽代碼如下：

（5）主函數(shù)從HDFS輸出文件中逐一讀取頻繁項集l及其支持度計數(shù)support，并將l添加到鏈表L的表尾，將support添加到鏈表S的表尾，使l在L中的索引號與support在S中的索引號一致，以便獲取l的支持度support.接下來，使用冪集計算關(guān)聯(lián)規(guī)則的前件A，使用補集計算關(guān)聯(lián)規(guī)則的后件B，最后輸出滿足最小置信度的強關(guān)聯(lián)規(guī)則，偽代碼如下：

4 實驗及結(jié)果分析

4.1 實驗環(huán)境與實驗數(shù)據(jù)

使用8臺計算機搭建了一個Hadoop集群，其中1臺作為JobTracker節(jié)點，其余7臺作為TaskTracker節(jié)點.計算機的硬件和軟件配置相同，硬件配置是：Intel Core2 Duo CPU（主頻為2.93GHz）、2GB內(nèi)存、320GB硬盤、100M網(wǎng)卡，安裝的軟件是：Ubuntu 12.04 LTS（32位）、Hadoop 1.2.1、JDK 1.7.0_51.

采用Java語言編程實現(xiàn)本文算法，使用IBM數(shù)據(jù)生成器生成9個數(shù)據(jù)集，如表1所示，其中平均項長是事務(wù)包含項的平均個數(shù)，總項數(shù)是事務(wù)數(shù)據(jù)庫中不同項的總個數(shù)，數(shù)據(jù)集db4、db5、db6、db7、db8、db9的事務(wù)條數(shù)（數(shù)據(jù)規(guī)模）分別是數(shù)據(jù)集db3的2、3、4、5、6、7倍.

表1 實驗數(shù)據(jù)集

4.2 實驗結(jié)果與分析

使用兩組實驗分別測試算法的加速比和數(shù)據(jù)規(guī)模增長性，算法的加速比計算公式如下：

seedup(m)=t1/tm，式中t1、tm分別表示在1個TaskTracker節(jié)點、m個TaskTracker節(jié)點上運行算法所用的時間[12].

算法的數(shù)據(jù)規(guī)模增長性計算公式如下：

sizeup(DB,m)=tm×DB/tDB，式tm×DB中表示對規(guī)模為m×DB的數(shù)據(jù)集運行算法所用的時間，tDB表示對規(guī)模為DB的數(shù)據(jù)集運行算法所用的時間[12].

（1）加速比實驗

使用實驗數(shù)據(jù)集db1、db2測試算法的加速比，最小支持度閾值為30%，最小置信度閾值為50%.算法的運行時間如表2所示，算法的加速比如圖2所示.

表2 算法的運行時間

圖2 算法的加速比

從圖2可以看出，算法對db1、db2都有較好的加速比.從表2可以看出，在事務(wù)數(shù)相同的情況下，事務(wù)的平均項長增長，算法的運行時間也大大增加.這是因為事務(wù)的項長增加，則采用冪集求出的候選項集的數(shù)量大大增加，計算時間和內(nèi)存開銷也隨之增大，可見本文算法適合對平均項長較小的數(shù)據(jù)集挖掘關(guān)聯(lián)規(guī)則.

（2）數(shù)據(jù)規(guī)模增長性實驗

使用7個TaskTracker節(jié)點，對數(shù)據(jù)集db3、db4、db5、db6、db7、db8、db9測試算法的數(shù)據(jù)規(guī)模增長性，最小支持度閾值為30%，最小置信度閾值為50%，實驗結(jié)果如圖3所示.

圖3 數(shù)據(jù)規(guī)模增長性實驗結(jié)果

從圖3可以看出，在平均項長不變、總項數(shù)不變的情況下，隨著數(shù)據(jù)規(guī)模的成倍增長，算法的運行時間并沒有成倍增長.由于本文算法對數(shù)據(jù)集一次掃描便可求出所有頻繁項集，所需的I/O時間很少，對于大數(shù)據(jù)集能取得更好的運行效率.可見本文算法有較好的數(shù)據(jù)規(guī)模增長性，能適用于對大數(shù)據(jù)集進(jìn)行關(guān)聯(lián)規(guī)則挖掘.

5 結(jié)語

對大數(shù)據(jù)進(jìn)行掃描需要耗費大量的I/O時間，本文從減少I/O時間的角度出發(fā)，提出了一種基于MapReduce的關(guān)聯(lián)規(guī)則挖掘算法.本文算法在找出所有頻繁項集的過程中只需要掃描事務(wù)數(shù)據(jù)庫1次，所需的I/O時間很小，能取得較高的運行效率.采用MapReduce模型在多個節(jié)點上并行地找出所有頻繁項集，縮短了計算時間，能以較快的速度從大數(shù)據(jù)集中挖掘出所有關(guān)聯(lián)規(guī)則.實驗結(jié)果表明：在平均項長較小的情況下，本文算法具有很好的加速比和數(shù)據(jù)規(guī)模增長性.但是，算法也存在缺點：在平均項長較大的情況下，性能下降很快，這是下一步要解決的問題. ■

Abstract:From the viewpoint of reducing I/O time, according to MapReduce of Hadoop platform of cloud computing, this paper presents an algorithm for mining association rules based on MapReduce. The algorithm uses power set to compute candidate itemsets, and finds all frequent itemsets in parallel with MapReduce model, which scan the transaction database only once. Experimental result shows that the algorithm can achieve a good speedup and data sizeup under the condition that the length of itemset in transaction is not very longer.

Keywords:association rules, MapReduce, cloud computing, Hadoop

[1]王平水.關(guān)聯(lián)規(guī)則挖掘算法研究[J].計算機工程與應(yīng)用，2014,46（30）：115-116.

[2]Agrawal R,Srikant R. Fast Algorithms for Mining Association Rules [C]//Proc. of the 20th Intl. Conf. on Very Large Data Bases (VLDB’94) . Santiago,Chile,1994:4 87-499.

[3]Armbrust M,Fox A,Griffith R,et al. Above the Clouds: A Berkeley View of Cloud Computing[R/OL]. UC Berkeley,RAD Laboratory,2009 [2014-07-05]. http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/ EECS-2009-28.html.

[4]李玲娟，張敏.云計算環(huán)境下關(guān)聯(lián)規(guī)則挖掘算法的研究[J].計算機技術(shù)與發(fā)展, 2011，21(2)：43-46.

[5]Dean J,Ghemawat S. MapReduce:Simplified Data Processing on Large Clusters[C]//Proc. of the 6th Symposium on Operating System Design and Implementation. San Francisco, California, 2004: 137-150.

[6]應(yīng)毅，劉亞軍. MapReduce并行計算技術(shù)發(fā)展綜述[J].計算機系統(tǒng)應(yīng)用，2014，23(4)：1-6.

[7]Apache Hadoop[EB/OL]. The Apache Software Foundation, 2014[2014-07-05]. http://hadoop.apache. org/.

[8]郝曉飛，譚躍生，王靜宇. Hadoop平臺上Apriori算法并行化研究與實現(xiàn)[J].計算機與現(xiàn)代化，2013，211(3)：1-4.

[9]陳自力.一種新的基于冪集的數(shù)據(jù)挖掘算法[J].甘肅聯(lián)合大學(xué)學(xué)報：自然科學(xué)版，2011,25（6）：65-67.

[10]黃立勤,柳燕煌.基于MapReduce并行的Apriori算法改進(jìn)研究[J].福州大學(xué)學(xué)報:自然科學(xué)版，2011，39(5)：680-685.

[11]周麗娟，王翔.云環(huán)境下關(guān)聯(lián)規(guī)則算法的研究[J].計算機工程與設(shè)計，2014，35（2）：499-503.

[12]楊勇，王偉.一種基于MapReduce的并行FP-growth算法[J].重慶郵電大學(xué)學(xué)報：自然科學(xué)版，2013，25(5)：651-657.

【責(zé)任編輯 謝明俊】

A Algorithm of Mining Association Rules Based on MapReduce

ZHOU Guo-jun
( College of Maths & Information Science, Yulin Normal University, Yulin, Guangxi 537000)

From the viewpoint of reducing I/O time, according to MapReduce of Hadoop platform of cloud computing, this paper presents an algorithm for mining association rules based on MapReduce. The algorithm uses power set to compute candidate itemsets, and finds all frequent itemsets in parallel with MapReduce model, which scan the transaction database only once. Experimental result shows that the algorithm can achieve a good speedup and data sizeup under the condition that the length of itemset in transaction is not very longer .

association rules; MapReduce; cloud computing; Hadoop

An Algorithm of Mining Association Rules Based on MapReduce

ZHOU Guo-jun
(College of Maths & Information Science, Yulin Normal University, Yulin, Guangxi 537000)

TP311

A

1004-4671（2014）05-0128-07

2014-07-11

廣西教育廳2014年度廣西高校科學(xué)技術(shù)研究項目（項目編號：LX2014300）。

周國軍（1975～），男，湖南寧遠(yuǎn)人，碩士，玉林師范學(xué)院數(shù)學(xué)與信息科學(xué)學(xué)院講師，研究方向：數(shù)據(jù)挖掘。