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

安建瑞，王海鵬，張龍波，金　超，懷　浩

(山東理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，山東 淄博　255049)

?

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

安建瑞，王海鵬，張龍波，金超，懷浩

(山東理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，山東 淄博255049)

摘要：提出一種基于MapReduce的壓縮矩陣關(guān)聯(lián)規(guī)則挖掘算法FMA_Mining。該算法將數(shù)據(jù)庫映射為布爾矩陣，在矩陣映射過程中引入Flag標(biāo)識，對于連續(xù)出現(xiàn)的項(xiàng)用Flag標(biāo)識標(biāo)明，簡化矩陣元素的讀取和列向量運(yùn)算。針對大數(shù)據(jù)應(yīng)用中事務(wù)和項(xiàng)目規(guī)模較大的情況，算法引入了矩陣分割和并行化處理思想。在Hadoop平臺采用WebDocs數(shù)據(jù)集對算法性能進(jìn)行測試，從理論分析和實(shí)驗(yàn)結(jié)果兩方面證明了FMA_Mining算法的有效性。

關(guān)鍵詞：壓縮矩陣；關(guān)聯(lián)規(guī)則； MapReduce；Hadoop

關(guān)聯(lián)規(guī)則(association rule)是數(shù)據(jù)挖掘的重要研究領(lǐng)域之一，能夠通過對數(shù)據(jù)庫中頻繁項(xiàng)集的挖掘，找出不同項(xiàng)目之間的聯(lián)系。文獻(xiàn)[1]中Huang等首次提出基于矩陣的關(guān)聯(lián)規(guī)則挖掘算法，稱之為BitMatrix Algorithm。該算法把數(shù)據(jù)庫中的事務(wù)和項(xiàng)轉(zhuǎn)化為布爾矩陣，只需要掃描一次數(shù)據(jù)庫，不會產(chǎn)生大量的候選集。

文獻(xiàn)[2]中Krajca等提出了一種基于因式分解的類布爾矩陣算法，利用頻繁閉項(xiàng)集作為候選因子項(xiàng)，然后計(jì)算增量連接項(xiàng)目的剩余因素項(xiàng)。該算法能夠在保持高準(zhǔn)確度的前提下，最大限度地減少數(shù)據(jù)集的維度。文獻(xiàn)[3]中提出了基于MapReduce的矩陣算法，通過Hadoop平臺實(shí)現(xiàn)矩陣運(yùn)算的并行化，能夠處理規(guī)模較大的數(shù)據(jù)，算法執(zhí)行效率較高。

文獻(xiàn)[4]提出了一種利用壓縮矩陣的方法產(chǎn)生頻繁項(xiàng)集的算法，在原有的布爾矩陣的基礎(chǔ)上，引入了新行Vs和新列Hs，分別表示某一項(xiàng)目的支持度和某一事務(wù)中存在的項(xiàng)目個(gè)數(shù)。每次挖掘頻繁項(xiàng)集，動(dòng)態(tài)地計(jì)算Vs和Hs的值，將不滿足預(yù)先設(shè)定支持度閾值的行或列刪掉。

文獻(xiàn)[5]提出了一種NCMA矩陣算法，該算法在矩陣存儲、項(xiàng)目分類、壓縮矩陣、支持度計(jì)算和算法停止條件等方面進(jìn)行改進(jìn)，能夠減少掃描矩陣的次數(shù)，使挖掘頻繁項(xiàng)集的效率得到提高。文獻(xiàn)[6]提出了一種面向查詢擴(kuò)展的矩陣加權(quán)關(guān)聯(lián)規(guī)則算法，算法采用4種剪枝策略，使得挖掘效率得到較大提高。

這些基于矩陣的關(guān)聯(lián)規(guī)則挖掘算法能夠減少掃描數(shù)據(jù)庫的次數(shù)，提高挖掘頻繁項(xiàng)集的效率，但是仍然存在著一些問題：① 在計(jì)算支持度的過程中需要多次掃描矩陣；② 在減少頻繁候選集數(shù)量的同時(shí)，算法計(jì)算過程變得過于復(fù)雜；③ 由于壓縮矩陣不夠充分，往往需要存儲和計(jì)算一些與產(chǎn)生頻繁項(xiàng)集無關(guān)的元素，這對于頻繁更新的事務(wù)數(shù)據(jù)和事務(wù)規(guī)模較大的情況，是不切實(shí)際的；④ 由于設(shè)計(jì)的算法過于復(fù)雜，對于高強(qiáng)度和大批量的事務(wù)數(shù)據(jù)庫，矩陣將占用大量的內(nèi)存空間，很容易引發(fā)內(nèi)存溢出的問題；⑤ 算法沒有實(shí)現(xiàn)并行化。

本文提出的基于壓縮矩陣的關(guān)聯(lián)規(guī)則算法FMA_Mining，只需要對數(shù)據(jù)庫進(jìn)行一次掃描，將數(shù)據(jù)庫映射為0-1矩陣，在矩陣映射過程中引入Flag標(biāo)識，對于連續(xù)出現(xiàn)的項(xiàng)用Flag標(biāo)識標(biāo)明，簡化矩陣元素的讀取和列向量的“與”運(yùn)算。再通過對矩陣的多次掃描和剪枝，得到頻繁項(xiàng)集。

1FMA_Mining算法

1.1算法相關(guān)定義

為了更好地說明FMA_Mining算法的過程，首先做出以下定義：

定義1布爾矩陣中，項(xiàng)Ii與Ij的支持度即Ii與Ij在同一水平列上均出現(xiàn)“1”的次數(shù)，即Ii與Ij按位相與后求和。項(xiàng)集{Ii,Ij}的支持度記為：

1.2FMA_Mining算法過程描述

1) 根據(jù)事務(wù)數(shù)據(jù)庫，產(chǎn)生布爾矩陣，進(jìn)行剪枝和計(jì)算，生成頻繁1-項(xiàng)集：若項(xiàng)目i出現(xiàn)在某一事務(wù)j中，則該布爾矩陣中第i列第j行為“1”，若沒有出現(xiàn)，則該布爾矩陣第i列第j行為“0”。布爾矩陣中，一行對應(yīng)于數(shù)據(jù)庫中的一個(gè)事務(wù)，一列表示某一項(xiàng)目在各個(gè)事務(wù)中的存在情況。通過統(tǒng)計(jì)每一列中“1”出現(xiàn)的次數(shù)，可以求出各個(gè)項(xiàng)目的支持度。將各個(gè)項(xiàng)目支持度與預(yù)定的最小支持度進(jìn)行比較，進(jìn)行剪枝操作，刪掉不滿足閾值的向量。

2) 在生成布爾矩陣G的過程中引入Flag標(biāo)識，當(dāng)某一列的第i行是“0”元素，將Flag標(biāo)識定位在該列的第i行處，繼續(xù)考察該列第i+1行元素，如果該i+1行元素依然為“0”，繼續(xù)考察第i+2行元素，直到該列結(jié)束或者該列某一行出現(xiàn)元素“1”。將該列第i行處的元素“0”用元素“F”代替，將該列第i+1行處的元素“0”用出現(xiàn)連續(xù)“0”的次數(shù)m代替，表示該列第i行開始出現(xiàn)連續(xù)m個(gè)的“0”元素；同理，元素“T”表示該列出現(xiàn)連續(xù)的“1”元素，將該列第i+1行處的元素“1”用出現(xiàn)連續(xù)“1”的次數(shù)n代替。由于“F”和“0”元素連續(xù)出現(xiàn)的次數(shù)以及“T”和“1”連續(xù)出現(xiàn)的次數(shù)均占用兩個(gè)元素位置，所以默認(rèn)引入Flag標(biāo)識的列中“0”或“1”連續(xù)出現(xiàn)的次數(shù)應(yīng)在3次以上。

在后續(xù)的矩陣運(yùn)算中，當(dāng)掃描到某一列出現(xiàn)元素“F”或者元素“T”，可以直接跳過該連續(xù)“0”元素或者“1”元素區(qū)間，減少對矩陣元素的讀操作；在挖掘頻繁k-項(xiàng)集時(shí)，進(jìn)行矩陣列向量的運(yùn)算時(shí)，只要任何一個(gè)列向量讀到標(biāo)識“F”，則列向量中與標(biāo)識“F”下連續(xù)“0”的同等數(shù)量的行可以直接剪掉。

3) 利用頻繁1-項(xiàng)集進(jìn)行自連接，對生成的兩列向量進(jìn)行與運(yùn)算，得到各候選項(xiàng)集的支持度。通過與最小支持度進(jìn)行比較，得到頻繁2-項(xiàng)集。

4) 利用定義3對得到的頻繁2-項(xiàng)集進(jìn)行裁剪。如果某個(gè)項(xiàng)目在頻繁2-項(xiàng)集出現(xiàn)的次數(shù)小于2，則刪除掉包含該項(xiàng)目的所有頻繁2-項(xiàng)集，從而得到新的頻繁2-項(xiàng)集。

5) 利用步驟4中得到的頻繁2-項(xiàng)集得到頻繁3-項(xiàng)集，依次類推，直到得到頻繁k-項(xiàng)集。

1.3FMA_Mining算法偽代碼描述

輸入：事務(wù)數(shù)據(jù)庫D，最小支持度計(jì)數(shù)值Min_Sup；

輸出：D中所有滿足最小支持度計(jì)數(shù)值的頻繁項(xiàng)集

1) 構(gòu)建布爾矩陣并剪枝，生成頻繁1-項(xiàng)集，引入Flag標(biāo)識

for(int j=0;j

L1-count=0;

for(int i=0;i

//構(gòu)造0-1矩陣

if(D[i][j]!=NULL){

L1-count++; A[i][j]=1;}

if(D[i][j]==NULL){

A[i][j]=0;

if(Flag==false){

//引入Flag標(biāo)識

啟動(dòng)Flag標(biāo)識和計(jì)數(shù)器；

}

}

if(L1-count>=Min_Sup){

//生成頻繁1-項(xiàng)集

L1= L1∪{A[i]}

}

}

end;

2) 生成頻繁k-項(xiàng)集

k=1;

do{//直到無法找出頻繁項(xiàng)集

for all ItemValue{i1,i2,…,ii}∈Lk

for all ItemValue{i1,i2,…,ij}∈Lk

if(all is 1:A[1] &&A[1]>=Min_Sup∧each A[2] &&A[2]>=Min_Sup∧…∧each A[j] &&A[j]>=Min_Sup){

對形成的頻繁項(xiàng)集進(jìn)行剪枝；

Lk+1= Lk∪{Ii∪Ij}

}

}while(Lk!=Φ)

end;

其中：D[i][j]表示數(shù)據(jù)庫中第i條事務(wù)的第j個(gè)項(xiàng)；A[j]表示布爾矩陣的第j列；∧表示按位與運(yùn)算。

2大數(shù)據(jù)集下FMA_Mining算法的改進(jìn)

2.1矩陣分塊算法的實(shí)現(xiàn)

隨著事務(wù)和項(xiàng)目的不斷增長，對于FMA_Mining算法中的標(biāo)識Flag，可以進(jìn)行行改造，從而對生成的矩陣進(jìn)行最大化壓縮，為此，做出以下定義：

定義4矩陣的壓縮閾值q，q的取值根據(jù)事務(wù)的數(shù)量規(guī)模來確定，事務(wù)數(shù)量越大，q的取值越大。

1) 根據(jù)q的值，對矩陣首先進(jìn)行壓縮，對矩陣每一列的q行進(jìn)行劃分，由于矩陣的每個(gè)元素都是“0”或“1”，每一個(gè)劃分后的小區(qū)域的類型是可控的，我們用不同的標(biāo)識代替。

例如，對于擁有9萬條事務(wù)，100個(gè)項(xiàng)目的數(shù)據(jù)庫D，可以設(shè)定矩陣壓縮閾值q為3，對數(shù)據(jù)庫D生成的矩陣進(jìn)行劃分，可以把原先9萬行、100列的矩陣劃分成3萬*100的小區(qū)域矩陣。每個(gè)小區(qū)域都是由3*1的小矩陣組成，其中小矩陣每個(gè)元素都為“0”或“1”，則小區(qū)域的類型共有8種。

2) 對矩陣行壓縮后，在計(jì)算頻繁k-項(xiàng)集的時(shí)候，只需要對項(xiàng)Ii所在列的小區(qū)域進(jìn)行與運(yùn)算，對于小區(qū)域的與運(yùn)算，可以提前進(jìn)行預(yù)計(jì)算，并存入固定表L中。當(dāng)需要得知某些小區(qū)域的計(jì)算結(jié)果，只需要進(jìn)行查表即可。這相當(dāng)于對矩陣進(jìn)行了列壓縮。

通過分別對矩陣進(jìn)行行壓縮和列壓縮，使得FMA_Mining算法在處理大規(guī)模數(shù)據(jù)集下的效率得到很大提高。

2.2矩陣分塊算法實(shí)例

假定矩陣M是要進(jìn)行壓縮的矩陣，矩陣M為：

取矩陣壓縮閾值q為3，對M矩陣進(jìn)行區(qū)域劃分后為：

對區(qū)域進(jìn)行標(biāo)識化處理，標(biāo)識類型如下所示：

引入以上標(biāo)識后，轉(zhuǎn)化后的矩陣M如下所示：

對各個(gè)標(biāo)識的與運(yùn)算結(jié)果提前存入表L中，當(dāng)計(jì)算頻繁k-項(xiàng)集的支持度時(shí)，只需要查表即可。例如，計(jì)算M[1]與M[2]的支持度，只需要查表θ∧ν，γ∧β，α∧γ即可。

2.3對矩陣進(jìn)行MapReduce并行化

對矩陣分塊能夠極大地壓縮矩陣的規(guī)模，但是在大數(shù)據(jù)環(huán)境下，數(shù)據(jù)量的規(guī)模十分龐大，序列化的單機(jī)讀取數(shù)據(jù)庫并進(jìn)行矩陣轉(zhuǎn)換將使得算法的效率大大降低。為此，將FMA_Mining算法與并行編程模型MapReduce相結(jié)合，實(shí)現(xiàn)矩陣運(yùn)算的并行化。算法執(zhí)行方法如下：

1) 利用MapReduce將原始數(shù)據(jù)劃分為大小相等的N個(gè)數(shù)據(jù)子集，將N個(gè)數(shù)據(jù)子集文件部署在N個(gè)機(jī)器節(jié)點(diǎn)上。

2) 利用Map函數(shù)生成〈key,value〉對，其中，key代表事務(wù)的編號，value代表每一事務(wù)項(xiàng)目的集合。Map函數(shù)的偽代碼如下：

void Map(key,value){

for 每個(gè)TID中的元素Ti

foreach(string w:value)

setNum(1);

for 每個(gè)元素Ti的次數(shù)

foreach(int w:sum)

sum=sum+1;

if(sum

剪枝：刪掉該元素；

}

3) 對N個(gè)數(shù)據(jù)子集文件分別應(yīng)用FMA_Mining算法，引入Flag標(biāo)識量和矩陣分塊的方法，對每個(gè)數(shù)據(jù)子集進(jìn)行關(guān)聯(lián)規(guī)則挖掘。

4)利用Reduce函數(shù)對生成的〈itemsets,frequency〉進(jìn)行合并，形成全局頻繁項(xiàng)目集和輸出文件。Reduce函數(shù)的偽代碼如下：

Reduce(itemSets,sum){

for N個(gè)數(shù)據(jù)子文件生成的關(guān)聯(lián)規(guī)則 do

合并結(jié)果，刪除不滿足Min_Sup的頻繁項(xiàng)集;

輸出結(jié)果文件；

}

3實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)采用Frequent Itemset Mining Dataset Repository的Webdocs作為數(shù)據(jù)集進(jìn)行測試，數(shù)據(jù)集Webdocs包含1 692 080條事務(wù)，大小為1.4 GB。實(shí)驗(yàn)環(huán)境上，建立6個(gè)節(jié)點(diǎn)的Hadoop集群環(huán)境，Hadoop版本為穩(wěn)定版2.2.0，其中5個(gè)節(jié)點(diǎn)作為DataNode，CPU是Intel(R) Core(TM) i3-2350M，主頻為2.3 GHz，內(nèi)存2 GB，另一節(jié)點(diǎn)是DELL R720服務(wù)器，性能較高，作為NameNode。操作系統(tǒng)均為Ubuntu 14.04，JDK版本是1.8.0.51。

首先，測試FMA_Mining算法的并行性能。依次將算法運(yùn)行在1到6個(gè)節(jié)點(diǎn)上，考察FMA_Mining算法的運(yùn)行時(shí)間，發(fā)現(xiàn)隨著節(jié)點(diǎn)數(shù)目的增加，算法的執(zhí)行時(shí)間明顯下降。實(shí)驗(yàn)結(jié)果如圖1所示。

圖1　算法并行性實(shí)驗(yàn)結(jié)果

再次，把Webdocs數(shù)據(jù)集平均分配到6個(gè)節(jié)點(diǎn)，在支持度分別為0.15，0.2，0.25，0.3，0.35的情況下，分別考察Apriori與FMA_Mining在不同支持度下的運(yùn)行時(shí)間，結(jié)果如圖2所示。

圖2　算法不同支持度下的實(shí)驗(yàn)結(jié)果

最后，取定支持度為0.3，依次選取100 000，300 000，500 000，700 000條事務(wù)，分別考察Apriori與FMA_Mining在不同數(shù)據(jù)集規(guī)模下的運(yùn)行時(shí)間，結(jié)果圖3所示。

圖3　算法不同數(shù)據(jù)集規(guī)模下的實(shí)驗(yàn)結(jié)果

4結(jié)束語

FMA_Mining算法的時(shí)間復(fù)雜度為O(IkJ)，其中，I為布爾矩陣的行數(shù)，J為布爾矩陣的列數(shù)，k為頻繁項(xiàng)集的階數(shù)。算法只需要掃描1次數(shù)據(jù)庫，在掃描過程中生成的布爾矩陣置于內(nèi)存。引入Flag標(biāo)識后，減少了矩陣的讀操作和矩陣列向量的運(yùn)算，大大減少了系統(tǒng)I/O操作的次數(shù)，并且不會產(chǎn)生大量的候選集；基于MapReduce的并行化操作和矩陣分塊處理，進(jìn)一步提升了算法的執(zhí)行效率。實(shí)驗(yàn)結(jié)果表明：這種算法降低了算法運(yùn)行時(shí)間，穩(wěn)定性高，能夠提高關(guān)聯(lián)規(guī)則在頻繁項(xiàng)集上的挖掘效率。

參考文獻(xiàn)：

[1]HUANG L S,CHEN H P,WANG X,et al.A Fast Algorithm for Mining Association Rules[J].Journal of Computer Science and Technology,2000,15(6):619-624.

[2]KRAJCA P,OUTRATA J,VYCHODIL V.Using frequent closed itemsets for data dimensionality reduction[C]//11th IEEE International Conference on Data Mining,Institute of Electrical and Electronics Engineers Inc,Vancouver,2011:1128-1133.

[3]YANG X Y,ZHEN L,FU Y.MapReduce as a programming model for association rules algorithm on Hadoop[C]//3rd International Conference on Information Sciences and Interaction Sciences,IEEE Computer Society.Chengdu:IEEE,2010:99-102.

[4]SIHUI SHU.A New Association Rule Mining Algorithm Based on Compression Matrix[J].Computer Engineering and Networking Lecture Notes in Electrical Engineering,2014,277:281-289.

[5]TAOSHEN LI,DAN LUO.A New Improved Apriori Algorithm Based on Compression Matrix[J].Advanced Data Mining and Applications Lecture Notes,2014,8933:1-15.

[6]黃名選,嚴(yán)小衛(wèi),張師超.基于矩陣加權(quán)關(guān)聯(lián)規(guī)則挖掘的偽相關(guān)反饋查詢擴(kuò)展[J].軟件學(xué)報(bào)，2009(7)：1854-1865.

[7]MOHANTY A K,SENAPATI M,BEBERTA S,et al.Mass classification method in mammograms using correlated association rule mining[J].Neural Computing and Applications,2013:232.

[8]陳俊明.基于布爾矩陣的空間關(guān)聯(lián)規(guī)則提取方法研究[J].測繪與空間地理信息,2014(5):123-126.

[9]黃治國,王淼.基于決策矩陣的可信關(guān)聯(lián)規(guī)則挖掘方法[J].計(jì)算機(jī)工程與設(shè)計(jì),2014(8):2890-2895.

[10]Al-DHARHANI G S,OTHMAN Z A,BAKAR A A.A Graph-Based Ant Colony Optimization for Association Rule Mining[J].Arabian Journal for Science and Engineering,2014:396.

[11]ZHANG Lihua,WANG Miao,ZHAI Zhengjun,et al.Mining Closed Strong Association Rules by Rule-growth in Resource Effectiveness Matrix[J].Journal of Software,2014:99.

[12]呂桃霞,劉培玉.一種基于矩陣的強(qiáng)關(guān)聯(lián)規(guī)則生成算法[J].計(jì)算機(jī)應(yīng)用研究,2011(4):1301-1303.

[13]胡維華,馮偉.基于分解事務(wù)矩陣的關(guān)聯(lián)規(guī)則挖掘算法[J].計(jì)算機(jī)應(yīng)用,2014(S2):113-116.

[14]MARGHNY H.MOHAMMED M,DARWIEESH A B,et al.Advanced Matrix Algorithm (AMA):reducing number of scans for association rule generation[J].IJBIDM,2011:6.

[15]朱清香,侯會茹,劉晶,等.基于矩陣多源加權(quán)關(guān)聯(lián)規(guī)則在個(gè)性化推薦中的應(yīng)用[J].科技管理研究,2015(1):183-187.

[16]張偉豐,楊麗華.基于矩陣的多段支持度關(guān)聯(lián)規(guī)則挖掘算法[J].湖北汽車工業(yè)學(xué)院學(xué)報(bào),2014(2):72-76.

[17]唐冰,陸春芽.一種基于反區(qū)分矩陣的多維關(guān)聯(lián)規(guī)則挖掘方法[J].廣西民族大學(xué)學(xué)報(bào)(自然科學(xué)版),2013(1):62-65.

(責(zé)任編輯何杰玲)

A Compression Matrix Algorithm for Mining Association Rules Based on Mapreduce

AN Jian-rui, WANG Hai-peng, ZHANG Long-bo, JIN Chao, HUAI Hao

(College of Computer Science and Technology,Shandong University of Technology, Zibo 255049, China)

Abstract:An association rules mining algorithm, FMA_Mining, was proposed based on MapReduce and compression matrix. In this algorithm, databases were mapped into Boolean matrices. In the process of matrix mapping, a flag was introduced to identify the consecutive elements, thus simplifying the reading of matrix elements and operating of column vectors. For the big scale of affairs and projects in big data applications, matrix partition and parallel processing were introduced in the FMA_Mining algorithm. In the Hadoop platform, the performance of the algorithm was tested by using WebDocs data set, and the validity of the FMA_Mining algorithm was proved by both theoretical analysis and experimental results.

Key words:compression matrix; association rule; MapReduce; Hadoop

文章編號：1674-8425(2016)02-0095-06

中圖分類號：TP391

文獻(xiàn)標(biāo)識碼：A

doi:10.3969/j.issn.1674-8425(z).2016.02.017

作者簡介：安建瑞(1990—)，男，碩士研究生，主要從事數(shù)據(jù)挖掘研究；王海鵬(1980—)，男，博士，講師，主要從事數(shù)據(jù)挖掘、生物信息學(xué)研究；通訊作者 張龍波(1968—)，男，博士，教授，主要從事數(shù)據(jù)庫理論與應(yīng)用、數(shù)據(jù)挖掘研究。

基金項(xiàng)目：山東省自然科學(xué)基金資助項(xiàng)目(ZR2014FQ024)

收稿日期：2015-06-15

引用格式：安建瑞，王海鵬，張龍波，等.一種基于MapReduce的壓縮矩陣關(guān)聯(lián)規(guī)則挖掘算法[J].重慶理工大學(xué)學(xué)報(bào)(自然科學(xué)版)，2016(2):95-100.

Citation format：AN Jian-rui, WANG Hai-peng, ZHANG Long-bo, et al.A Compression Matrix Algorithm for Mining Association Rules Based on Mapreduce[J].Journal of Chongqing University of Technology(Natural Science)，2016(2):95-100.