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

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

?

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

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

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

摘要：提出一種基于MapReduce的壓縮矩陣關(guān)聯(lián)規(guī)則挖掘算法FMA_Mining。該算法將數(shù)據(jù)庫映射為布爾矩陣，在矩陣映射過程中引入Flag標識，對于連續(xù)出現(xiàn)的項用Flag標識標明，簡化矩陣元素的讀取和列向量運算。針對大數(shù)據(jù)應用中事務和項目規(guī)模較大的情況，算法引入了矩陣分割和并行化處理思想。在Hadoop平臺采用WebDocs數(shù)據(jù)集對算法性能進行測試，從理論分析和實驗結(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ù)庫中頻繁項集的挖掘，找出不同項目之間的聯(lián)系。文獻[1]中Huang等首次提出基于矩陣的關(guān)聯(lián)規(guī)則挖掘算法，稱之為BitMatrix Algorithm。該算法把數(shù)據(jù)庫中的事務和項轉(zhuǎn)化為布爾矩陣，只需要掃描一次數(shù)據(jù)庫，不會產(chǎn)生大量的候選集。

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

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

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

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

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

1FMA_Mining算法

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

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

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

1.2FMA_Mining算法過程描述

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

2) 在生成布爾矩陣G的過程中引入Flag標識，當某一列的第i行是“0”元素，將Flag標識定位在該列的第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個的“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ù)均占用兩個元素位置，所以默認引入Flag標識的列中“0”或“1”連續(xù)出現(xiàn)的次數(shù)應在3次以上。

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

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

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

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

1.3FMA_Mining算法偽代碼描述

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

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

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

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標識

啟動Flag標識和計數(shù)器；

}

}

if(L1-count>=Min_Sup){

//生成頻繁1-項集

L1= L1∪{A[i]}

}

}

end;

2) 生成頻繁k-項集

k=1;

do{//直到無法找出頻繁項集

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){

對形成的頻繁項集進行剪枝；

Lk+1= Lk∪{Ii∪Ij}

}

}while(Lk!=Φ)

end;

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

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

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

隨著事務和項目的不斷增長，對于FMA_Mining算法中的標識Flag，可以進行行改造，從而對生成的矩陣進行最大化壓縮，為此，做出以下定義：

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

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

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

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

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

2.2矩陣分塊算法實例

假定矩陣M是要進行壓縮的矩陣，矩陣M為：

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

對區(qū)域進行標識化處理，標識類型如下所示：

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

對各個標識的與運算結(jié)果提前存入表L中，當計算頻繁k-項集的支持度時，只需要查表即可。例如，計算M[1]與M[2]的支持度，只需要查表θ∧ν，γ∧β，α∧γ即可。

2.3對矩陣進行MapReduce并行化

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

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

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

void Map(key,value){

for 每個TID中的元素Ti

foreach(string w:value)

setNum(1);

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

foreach(int w:sum)

sum=sum+1;

if(sum

剪枝：刪掉該元素；

}

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

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

Reduce(itemSets,sum){

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

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

輸出結(jié)果文件；

}

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

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

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

圖1　算法并行性實驗結(jié)果

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

圖2　算法不同支持度下的實驗結(jié)果

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

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

4結(jié)束語

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

參考文獻：

[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]黃名選,嚴小衛(wèi),張師超.基于矩陣加權(quán)關(guān)聯(lián)規(guī)則挖掘的偽相關(guān)反饋查詢擴展[J].軟件學報，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].計算機工程與設計,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]呂桃霞,劉培玉.一種基于矩陣的強關(guān)聯(lián)規(guī)則生成算法[J].計算機應用研究,2011(4):1301-1303.

[13]胡維華,馮偉.基于分解事務矩陣的關(guān)聯(lián)規(guī)則挖掘算法[J].計算機應用,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ī)則在個性化推薦中的應用[J].科技管理研究,2015(1):183-187.

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

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

(責任編輯何杰玲)

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

文獻標識碼：A

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

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

基金項目：山東省自然科學基金資助項目(ZR2014FQ024)

收稿日期：2015-06-15

引用格式：安建瑞，王海鵬，張龍波，等.一種基于MapReduce的壓縮矩陣關(guān)聯(lián)規(guī)則挖掘算法[J].重慶理工大學學報(自然科學版)，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.