一種新的基于MapReduce的并行關聯(lián)規(guī)則算法

潘燕燕

(福建船政交通職業(yè)學院信息工程系，福州 350007)

關聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘中的重要研究方法之一。關聯(lián)規(guī)則是通過對數(shù)據(jù)庫里面的數(shù)據(jù)進行分析，找出數(shù)據(jù)項之間的相關信息，它的核心是通過數(shù)據(jù)項統(tǒng)計計算頻繁項目集。Apriori算法是傳統(tǒng)的關聯(lián)規(guī)則算法，缺點是要多次掃描數(shù)據(jù)庫，同時產(chǎn)生的候選項很多?；谶@些缺點已經(jīng)有很多種改進算法，羅可等人［1］提出了一種基于2次掃描數(shù)據(jù)庫的改進算法，陳自力［2］提出了一種基于冪集的改進算法，這些算法都是基于單機的。隨著數(shù)據(jù)集的迅速增長，傳統(tǒng)的算法已經(jīng)無法滿足數(shù)據(jù)增長的需要。

同時隨著云計算的發(fā)展，MapReduce模型已經(jīng)應用于關聯(lián)規(guī)則挖掘，學者們提出了很多新的高效率的算法［3］。其中張圣［4］提出利用云計算來實現(xiàn)的關聯(lián)規(guī)則 Apriori算法，提高了效率;陳方健等人［5］提出布爾矩陣的MapReduce并行化算法，將數(shù)據(jù)庫轉化為布爾矩陣進行分布式處理。本次研究筆者提出一種新的基于MapReduce的關聯(lián)規(guī)則挖掘算法，該算法經(jīng)過2次掃描數(shù)據(jù)庫，就能得到相應的頻繁集，從而提高挖掘效率。

1 Map Reduce編程模型

MapReduce編程模型是用來簡化分布式系統(tǒng)的編程，主要處理大數(shù)據(jù)集［3］。MapReduce編程模型提供2個接口函數(shù)Map和Reduce，可以利用這2個函數(shù)實現(xiàn)對大量數(shù)據(jù)進行并行處理。MapReduce編程模型首先將大數(shù)據(jù)分割，分割好的數(shù)據(jù)塊交給節(jié)點的Map函數(shù)進行處理，Map函數(shù)接收＜key，value＞形式的輸入，得到中間 ＜key，list(value)＞，Reduce函數(shù)接收中間值作為輸入進行處理，得到新的＜key，value＞，最終得到結果。

2 基于Map Reduce的改進算法

2.1 Apriori的改進算法

Apriori算法是傳統(tǒng)的關聯(lián)規(guī)則挖掘算法。首先通過掃描一次數(shù)據(jù)庫得到頻繁1——項集L1，L1進行自連接得到候選集C2，再次掃描數(shù)據(jù)庫得到L2，L2進行自連接得到C3，以此類推直到不再產(chǎn)生新的頻繁項目集［6］。Apriori算法要多次掃描數(shù)據(jù)庫，在時間和空間上面開銷大。可以采用一種只要對數(shù)據(jù)庫進行2次掃描，就得到所有的頻繁項目集的方法［1］。首先掃描一次數(shù)據(jù)庫，得到頻繁1—— 項集L1，然后根據(jù) L1產(chǎn)生所有的候選集(從2項到 k項)，第二次掃描數(shù)據(jù)庫，得到各項候選集的支持度，刪除低于最小支持度的候選集，最終得到頻繁項目集(從2項到k項)。

2.2 基于MapReduce的改進算法

MapReduce可以實現(xiàn)分布式處理大型數(shù)據(jù)，根據(jù)這個特點筆者提出一種新的基于MapReduce的關聯(lián)規(guī)則挖掘算法。

基本思路:把事務數(shù)據(jù)庫D分成獨立的數(shù)據(jù)子集，交由集群中的節(jié)點處理。節(jié)點掃描一遍數(shù)據(jù)，得到局部候選1—— 項集C1，然后根據(jù)C1得到所有的局部候選集(從2項到k項)，k≤數(shù)據(jù)子集中記錄的最大項目數(shù)，設置k可以在一定程度上減少候選集的數(shù)量;第二次掃描數(shù)據(jù)庫計算出所有局部候選集的支持度，最后發(fā)送給Reduce函數(shù)進行處理，最終得到全局頻繁項目集。具體步驟如下所示。

(1)生成數(shù)據(jù)子集:就是利用MapReduce庫將事務數(shù)據(jù)庫分割，形成多個獨立的子集合。

(2)Map函數(shù)的任務是對輸入的＜tid，list＞數(shù)據(jù)進行掃描，list表示各個事務的數(shù)據(jù)項，tid表示事務編號，掃描得到局部候選集C1，生成＜key1，value1＞，這里記為 ＜itemSet1，1＞，itemSet1表示 C1中的候選1項集，每個支持度為1?，F(xiàn)在的事務數(shù)據(jù)庫都很大，有可能產(chǎn)生很多相同的＜itemSet1，1＞，要對其進行合并，得到＜itemSet1，n＞。

(3)根據(jù)C1生成所有的候選集(從2項到k項)，第二次掃描數(shù)據(jù)子集，得到 ＜key2，value2＞，這里記為＜itemSetk，n＞，itemSetk表示候選k項集，n為itemSetk在數(shù)據(jù)子集的支持度，刪除 n為0的記錄。

Map函數(shù)偽代碼如下:

input:＜tid，list＞

output:＜itemSetk，n ＞

int maxLength=0，j=0

for each list do begin

for list里面的每個元素tido begin/*第一遍掃描數(shù)據(jù)庫*/

emit(＜itemSet1=ti，1 ＞)

j++

end

if(maxLength＜j)

maxLength=j/*獲得數(shù)據(jù)子集里面記錄的最大長度*/

end

combine(ti，list(1))/*對相同的1項集進行合并*/

int n=0

for each list(1)do

n=n+1

end

C1=∪ti

emit(＜itemSet1=ti，n＞)/* 得到局部候選集C1*/

for(k=2;k≤maxLength;k++)/*maxLength為數(shù)據(jù)子集里記錄的最大長度*/

get all＜itemSetk，n=0＞/*獲得2項到K項的候選集，支持度初始為0*/

for each list do begin/*掃描數(shù)據(jù)子集獲得item-Setk的支持度*/

for(k=2;k＜=maxLength;k++)

if itemSetk∈list

n=n+1

end

(4)對于 ＜itemSetk，n ＞，利用哈希函數(shù)［7］進行分區(qū)，分配到P個不同的分區(qū)，在每個分區(qū)執(zhí)行Reduce函數(shù)。

其中 r1，r2，r3，…，rk為 k項集里面的項在事務數(shù)據(jù)庫項集中的序數(shù)。根據(jù)Apriori的假定，項集或者事務里的項是按照字典排序的。

(5)執(zhí)行Reduce任務的站點，接收＜ itemSetk，n＞數(shù)據(jù)，把同一個候選集的支持度相加起來，就得到候選k項集的全局支持度。經(jīng)過和最小支持度進行比較，就可以得到全局的頻繁項目集Lk(從1項到k項)。Reduce函數(shù)偽代碼如下:

input:＜ itemSetk，n ＞

output:全局頻繁項目集

compare itemSetkfor all ＜ itemSetk，n＞/* 按itemSetk分組*/

sum_n=count(itemSetk，n)/* 計算 itemSetk的支持度n之和*/

for(k=1;k＜=maxLength;k++)

begin

if(sum_n＞=min_sup)/*如果支持度之和大于最小支持度，將itemSetk放入到Lk中*/

insert(Lk，itemSetk)

end

return∪Lk

3 算法實現(xiàn)過程

假設有事務數(shù)據(jù)庫S，如表1所示。

表1 事務數(shù)據(jù)庫S

假設最小支持度為2，M=2，P=2。

(1)將數(shù)據(jù)庫 S 分成2 個子集，S1(t1，t2，t3)，S2(t4，t5，t6)。

(2)將子集S1，S2分別發(fā)送給2個站點，執(zhí)行Map函數(shù)，得到 ＜key1，value1＞。

站點1:

＜t1，{A，B}＞→ ＜{A}，1 ＞，＜{B}，1 ＞;＜t2，{A，D}＞→(＜{A}，1＞，＜{D}，1＞ ;

＜t3，{A，B，D}＞→ ＜{A}，1＞，＜{B}，1＞，＜{D}，1＞;

對數(shù)據(jù)進行合并得到＜{A}，3＞，＜{B}，2＞，＜{D}，2＞。得到局部候選集{{A}，{B}，{D}}。

站點2:

＜t4，{B，C}＞→ ＜{B}，1＞，＜{C}，1＞;＜t5，{C，D}＞→ ＜{C}，1＞，＜{D}，1＞ ;

＜t6，{A，B，D}＞→ ＜{A}，1＞，＜{B}，1＞，＜{D}，1＞;

同時對數(shù)據(jù)進行合并得到＜{A}，1＞，＜{B}，2＞，＜{C}，2＞，＜{D}，2＞。得到局部候選集{{A}，{B}，{C}，{D}}。

(3)通過局部候選集生成所有的候選集(2項到k項)，并掃描數(shù)據(jù)庫，得到 ＜ key2，value2＞，這里記為 ＜itemSetk，n＞，k≤數(shù)據(jù)記錄的最大項目數(shù)。

站點1得到的所有候選集和支持度:

＜{A，B}，2 ＞，＜{A，D}，2 ＞，＜{B，D}，1 ＞，＜{A，B，D}，1 ＞ ;

站點2得到的所有候選集和支持度:

＜{A，B}，2 ＞，＜ {A，C}，0 ＞ ＜ {A，D}，1 ＞，＜{B，C}，1 ＞，＜ {B，D}，1 ＞，＜ {C，D}，1 ＞，＜{A，B，C}，0 ＞，＜ {A，B，D}，1 ＞，＜ {A，C，D}，0＞，＜{B，C，D}，0＞;刪除 n為0的記錄。

(4)對＜itemSetk，n＞(包含候選1項集)利用哈希函數(shù)進行分區(qū)Hash(key)Mod 2，分成2個不同的分區(qū)。例如{A}分到1區(qū)，{B}分到0區(qū)。

Hash({A})Mod 2=1 Mod 2=1

Hash({B})Mod 2=0 Mod 2=0

分到站點1 的候選集有:{A}，{C}，{A，B}，{A，D}，{B，D};

分到站點 0的候選集有:{B}，{D}，{B，C}，{C，D}，{A，B，D}。

(5)進行Reduce任務對候選集的支持度進行累加。

站點1的候選集和相應支持度如表2所示。

表2 站點1的候選集和相應支持度

站點0的候選集和相應支持度如表3所示。根據(jù)最小支持度為2，站點0去掉{B，C}，{C，

表3 站點0的候選集和相應支持度

D}2項。最后把2個站的滿足最小支持度的項目集結合，得到最終的頻繁項目集{{A}，{B}，{C}，

{D}，{A，B}，{A，D}，{B，D}，{A，B，D}}。

4 實驗分析

使用仿真實驗檢測算法性能，在局域網(wǎng)內配置8個站點的環(huán)境，每個站點的硬件配置一樣，2 G內存，CPU是Intel i5系列;每個站點使用千兆以太網(wǎng)卡和交換機連接;操作系統(tǒng)采用Linux，Hadoop版本是2.2.0，Java 版本1.7。實驗數(shù)據(jù)采用 IBM 數(shù)據(jù)生成器生成。根據(jù)新算法，編寫Map函數(shù)和Reduce函數(shù)。

第一組實驗分別用100 000，200 000和500 000條記錄在8個站點的環(huán)境下進行測試。實驗結果如表4所示。

表4 不同記錄數(shù)運行時間

第二組實驗采用500 000記錄，分別在2，4，6，8個站點下面進行測試。實驗結果如表5所示。

表5 不同站點數(shù)運行時間

從表4可以看出，隨著數(shù)據(jù)的增加，運行時間是線性增加的。從表5可以看出，隨著節(jié)點數(shù)的增加，算法效率也隨之提高。從2個站點到4個站點的運行時間迅速下降，當?shù)?個站點的時候運行時間下降幅度減少。

5 結語

本次研究分析了傳統(tǒng)的關聯(lián)規(guī)則算法Apriori及其改進算法的優(yōu)劣，使用 MapReduce模型對Apriori算法進行并行優(yōu)化，提出一種新的基于MapReduce的關聯(lián)規(guī)則挖掘算法，改進后的算法只需對數(shù)據(jù)庫進行2次掃描。實驗結果表明該算法能有效提高數(shù)據(jù)挖掘效率。

［1］羅可，吳杰.一種基于Apriori的改進算法［J］.計算機工程與應用，2001(2):20-22.

［2］陳自力.一種新的基于冪集的數(shù)據(jù)挖掘算法［J］.甘肅聯(lián)合大學學報(自然科學版)，2011，25(6):66-68.

［3］陳康，鄭緯民.云計算:系統(tǒng)實例與研究現(xiàn)狀［J］.軟件學報，2009(5):1337-1348.

［4］張圣.一種基于云計算的管理規(guī)則 Apriori算法［J］.通信技術，2011，44(6):141-143.

［5］陳方健，張明新，楊昆.布爾矩陣Apriori算法的MapReduce并行化實現(xiàn)［J］.常熟理工學院學報(自然科學版)，2014，28(2):98-101.

［6］毛國君，段立娟，王室，等.數(shù)據(jù)挖掘原理與算法［M］.北京:清華大學出版社，2005:64-72.

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