潘燕燕

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

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

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

1 Map Reduce編程模型

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

2 基于Map Reduce的改進(jìn)算法

2.1 Apriori的改進(jìn)算法

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

2.2 基于MapReduce的改進(jìn)算法

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

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

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

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

(3)根據(jù)C1生成所有的候選集(從2項(xiàng)到k項(xiàng))，第二次掃描數(shù)據(jù)子集，得到 ＜key2，value2＞，這里記為＜itemSetk，n＞，itemSetk表示候選k項(xiàng)集，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里面的每個(gè)元素tido begin/*第一遍掃描數(shù)據(jù)庫*/

emit(＜itemSet1=ti，1 ＞)

j++

end

if(maxLength＜j)

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

end

combine(ti，list(1))/*對(duì)相同的1項(xiàng)集進(jìn)行合并*/

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項(xiàng)到K項(xiàng)的候選集，支持度初始為0*/

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

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

if itemSetk∈list

n=n+1

end

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

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

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

input:＜ itemSetk，n ＞

output:全局頻繁項(xiàng)目集

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

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

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

begin

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

insert(Lk，itemSetk)

end

return∪Lk

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

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

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

假設(shè)最小支持度為2，M=2，P=2。

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

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

站點(diǎn)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＞;

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

站點(diǎn)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í)對(duì)數(shù)據(jù)進(jìn)行合并得到＜{A}，1＞，＜{B}，2＞，＜{C}，2＞，＜{D}，2＞。得到局部候選集{{A}，{B}，{C}，{D}}。

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

站點(diǎn)1得到的所有候選集和支持度:

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

站點(diǎn)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)對(duì)＜itemSetk，n＞(包含候選1項(xiàng)集)利用哈希函數(shù)進(jìn)行分區(qū)Hash(key)Mod 2，分成2個(gè)不同的分區(qū)。例如{A}分到1區(qū)，{B}分到0區(qū)。

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

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

分到站點(diǎn)1 的候選集有:{A}，{C}，{A，B}，{A，D}，{B，D};

分到站點(diǎn) 0的候選集有:{B}，{D}，{B，C}，{C，D}，{A，B，D}。

(5)進(jìn)行Reduce任務(wù)對(duì)候選集的支持度進(jìn)行累加。

站點(diǎn)1的候選集和相應(yīng)支持度如表2所示。

表2 站點(diǎn)1的候選集和相應(yīng)支持度

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

表3 站點(diǎn)0的候選集和相應(yīng)支持度

D}2項(xiàng)。最后把2個(gè)站的滿足最小支持度的項(xiàng)目集結(jié)合，得到最終的頻繁項(xiàng)目集{{A}，{B}，{C}，

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

4 實(shí)驗(yàn)分析

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

第一組實(shí)驗(yàn)分別用100 000，200 000和500 000條記錄在8個(gè)站點(diǎn)的環(huán)境下進(jìn)行測(cè)試。實(shí)驗(yàn)結(jié)果如表4所示。

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

第二組實(shí)驗(yàn)采用500 000記錄，分別在2，4，6，8個(gè)站點(diǎn)下面進(jìn)行測(cè)試。實(shí)驗(yàn)結(jié)果如表5所示。

表5 不同站點(diǎn)數(shù)運(yùn)行時(shí)間

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

5 結(jié)語

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

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

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

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

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

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

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

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