陳方健 ，張明新 ，楊 昆

（1.蘇州大學(xué)，計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 蘇州 215006；2.常熟理工學(xué)院，計(jì)算機(jī)科學(xué)與工程學(xué)院，江蘇 常熟 215500；3.中國(guó)礦業(yè)大學(xué)，計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 徐州 221116）

人、機(jī)、物三元世界的高度融合引發(fā)了數(shù)據(jù)規(guī)模的爆炸式增長(zhǎng)和數(shù)據(jù)模式的高度復(fù)雜化，世界已進(jìn)入網(wǎng)絡(luò)化的大數(shù)據(jù)時(shí)代[1].這些大數(shù)據(jù)中蘊(yùn)含著潛在的、有價(jià)值的知識(shí)，但是基于傳統(tǒng)的思維和模式卻很難被發(fā)現(xiàn)并加以利用.為了擺脫這一局面，數(shù)據(jù)挖掘技術(shù)應(yīng)運(yùn)而生.Apriori算法是關(guān)聯(lián)規(guī)則挖掘中最基本也是最重要的算法之一.但在大數(shù)據(jù)時(shí)代，傳統(tǒng)的Apriori算法已經(jīng)很難滿足人們的需求.為此本文提出將Apriori算法移植到云平臺(tái)下，解決大數(shù)據(jù)對(duì)傳統(tǒng)Apriori算法帶來(lái)的缺陷.

云計(jì)算是一種融合了多種技術(shù)的計(jì)算模型，具有超大規(guī)模性、高可靠性、高可擴(kuò)展性等特點(diǎn)[2].Hadoop是一種類似于Google“云平臺(tái)”的一種開(kāi)源實(shí)現(xiàn).Hadoop上提供了基于Java的MapReduce分布式處理框架，供用戶簡(jiǎn)單實(shí)現(xiàn)分布式運(yùn)算.

本文提出將事務(wù)庫(kù)轉(zhuǎn)化為布爾矩陣以適應(yīng)MapReduce分布式處理框架分片處理大數(shù)據(jù)的特點(diǎn)，再結(jié)合Apriori算法的思想實(shí)現(xiàn)頻繁項(xiàng)集挖掘，為在大數(shù)據(jù)中獲取潛在的、有價(jià)值的知識(shí)提供快速、有效的方法.

1 MapReduce介紹

MapReduce是由Google實(shí)驗(yàn)室在2004年提出的一種分布式并行編程模式，主要用于處理基于集群的大規(guī)模數(shù)據(jù)集的分布式處理模型[3-4].MapReduce分布式處理框架將并行化計(jì)算抽象為Map和Reduce兩個(gè)接口.用戶通過(guò)實(shí)現(xiàn)Map和Reduce兩個(gè)接口以實(shí)現(xiàn)并行化，MapReduce框架將輸入的大數(shù)據(jù)文件按行分割為一系列獨(dú)立的數(shù)據(jù)塊.每個(gè)數(shù)據(jù)塊交由一個(gè)節(jié)點(diǎn)內(nèi)Map實(shí)例處理，用戶通過(guò)實(shí)現(xiàn)Map接口，在單個(gè)數(shù)據(jù)塊內(nèi)處理若干鍵值對(duì)＜key，value>，產(chǎn)生若干中間鍵值對(duì)＜key，list（value）>.Map函數(shù)處理完成后所得到的中間鍵值對(duì)＜key，list（value）>，作為Reduce函數(shù)的輸入并加以處理.用戶實(shí)現(xiàn)Reduce接口，對(duì)每一個(gè)中間鍵值對(duì)進(jìn)行自定義操作得到新的＜key，value>.最終將Reduce輸出的結(jié)果寫(xiě)入到指定文件.MapReduce處理大數(shù)據(jù)的過(guò)程如圖1所示：

2 MR_B_Apriori算法的并行化方法

2.1 傳統(tǒng)的Apriori算法

Apriori算法主要目的是找出事務(wù)數(shù)據(jù)庫(kù)中的頻繁集.主要思想[5-6]：Apriori利用了頻繁集的所有非空子集一定是頻繁集的性質(zhì).首先掃描一次數(shù)據(jù)庫(kù)D，統(tǒng)計(jì)各1-項(xiàng)集的支持度得到頻繁1-項(xiàng)集的集合L1，自連接得到候選2-項(xiàng)集的集合C2，掃描事務(wù)數(shù)據(jù)庫(kù)得到L2，如此迭代循環(huán)，通過(guò)第K次掃描得到Lk.若Lk=?，則算法結(jié)束.傳統(tǒng)Apriori算法在生成Lk的過(guò)程中需要逐次掃描事務(wù)數(shù)據(jù)庫(kù)K次，當(dāng)數(shù)據(jù)庫(kù)很大時(shí)會(huì)產(chǎn)生嚴(yán)重的I/O瓶頸使算法效率下降.

圖1 MapReduce處理大數(shù)據(jù)的過(guò)程

2.2 事務(wù)數(shù)據(jù)庫(kù)的布爾矩陣表示

對(duì)于任一給定的事務(wù)數(shù)據(jù)庫(kù)D[7]，令

其中 ：R=f(D)=(rij)n×m，n為事務(wù)的個(gè)數(shù) ，m為項(xiàng)目的個(gè)數(shù)，事務(wù)集 Ti（i∈n），項(xiàng)目集 Ij（j∈m），

i=1,2,…,n;j=1,2,…,m,于是，事務(wù)數(shù)據(jù)庫(kù)D經(jīng)一次掃描后，就可在f的作用下映射成布爾矩陣R，如圖2所示.

由以上分析可知，對(duì)任何一個(gè)事務(wù)數(shù)據(jù)庫(kù)掃描一次，即可得到與該事務(wù)數(shù)據(jù)庫(kù)相對(duì)應(yīng)的布爾矩陣.由于布爾矩陣中包含挖掘頻繁項(xiàng)集所需要的全部信息，故對(duì)事務(wù)數(shù)據(jù)庫(kù)的關(guān)聯(lián)規(guī)則挖掘問(wèn)題可順利轉(zhuǎn)化為對(duì)其布爾矩陣的分析操作.

圖2 事務(wù)數(shù)據(jù)庫(kù)D映射一個(gè)布爾矩陣R

2.3 MR_B_Apriori的并行化方法

基本思路：根據(jù)MapReduce分布式處理大型數(shù)據(jù)的特點(diǎn)，可將掃描事務(wù)數(shù)據(jù)庫(kù)一次所得到的布爾矩陣按行（保證事務(wù)的完整性）分塊，將此大矩陣分解為若干小矩陣.每個(gè)小矩陣做轉(zhuǎn)置后交由集群中的節(jié)點(diǎn)存儲(chǔ)，供每次迭代時(shí)Map任務(wù)使用.Map任務(wù)在單個(gè)矩陣中計(jì)算候選K-項(xiàng)集的局部頻度，然后在Reduce階段合并融合得出候選K-項(xiàng)集的支持度.并根據(jù)給出的最小支持度得出頻繁K-項(xiàng)集.MapReduce分布式處理框架能夠完成大文件的按行分塊.我們只要完成Map函數(shù)和Reduce函數(shù)的設(shè)計(jì)就可完成我們的并行化要求.

Map函數(shù)的設(shè)計(jì)：

Map函數(shù)的任務(wù)是為了統(tǒng)計(jì)每個(gè)分塊矩陣內(nèi)候選K-項(xiàng)集的局部頻度.其輸入為＜key，value>對(duì)，key為代表候選K-項(xiàng)集集合的字符串?dāng)?shù)組，每個(gè)候選K-項(xiàng)集由字符串x-x-…-x表示（x為1，2…與I1，I2…對(duì)應(yīng)），value為分割后的小矩陣.根據(jù)候選K-項(xiàng)集的字符串，在矩陣內(nèi)對(duì)應(yīng)的k個(gè)行向量之間做邏輯與運(yùn)算.將運(yùn)算結(jié)果各位上的數(shù)相加得到關(guān)于候選相集的局部支持度，若為0則直接丟棄.形成新的＜key，value>對(duì)，新的key表示候選K-項(xiàng)的字符串，新的value則為該候選K-項(xiàng)集的局部頻度.

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

Reduce函數(shù)的設(shè)計(jì)：

Reduce函數(shù)的任務(wù)是合并融合Map任務(wù)所得到候選K-項(xiàng)集的局部頻度，得到候選K-項(xiàng)集的支持度.其輸入為＜key，value>對(duì)，將key相同的＜key，value>對(duì)的value值相加得到新的＜key，value>對(duì). 這里的key值保持不變，value值為候選相的支持度.選擇出滿足最小支持度的＜key，value>對(duì)，輸出至指定文件得到頻繁項(xiàng)集.

Reduce函數(shù)偽代碼如下：

3 實(shí)例分析

為了清楚直觀地說(shuō)明算法運(yùn)行的過(guò)程，這里以圖2所示的事物數(shù)據(jù)庫(kù)D為例.其轉(zhuǎn)化的布爾矩陣為R.給出的最小支持度Minsup=2.

第一步，由Hadoop框架將關(guān)于事務(wù)數(shù)據(jù)庫(kù)的布爾矩陣R按行分塊，得到split0、split1、split2三個(gè)分塊矩陣.

第二步，將分塊矩陣轉(zhuǎn)置后存于群集內(nèi)的節(jié)點(diǎn).

第三步，進(jìn)行Map任務(wù)，以計(jì)算頻繁2-相集為例.所得的結(jié)果為：

第四步，Reduce任務(wù)將 Map任務(wù)得到＜key，value>對(duì)作為輸入，將具有相同key值的value值相加得到相集的全局支持度，如圖3所示.

第五步，將所得結(jié)果相集送至Map進(jìn)行迭代運(yùn)算直至候選（K+1）-相集為空集時(shí)迭代結(jié)束.

圖3 Reduce過(guò)程計(jì)算全局支持度

4 算法的有效性分析

設(shè)|D|為事務(wù)庫(kù)D的事務(wù)數(shù)，T為最大交易長(zhǎng)度.分析Apriori算法可知[8]，第一遍掃描事務(wù)庫(kù)D需要O（T|D|），以后每次掃描，連接步驟需要O（ ||Lk-1× ||Lk-1），修剪步驟需要O（ ||Ck），遍歷事務(wù)庫(kù)D對(duì)候選集進(jìn)行統(tǒng)計(jì)需要O（ ||D× ||Ck），因此最壞情況下Apriori算法的時(shí)間復(fù)雜度為

分析MR_B_Apriori算法的并行化實(shí)現(xiàn)過(guò)程可知，第一遍掃描事務(wù)庫(kù)D得到布爾矩陣R需要O(T | D | ) ，連接步驟需要O（| Lk-1|× | Lk-1|），修剪步驟需要(O | Ck|)，設(shè)將R分割為m個(gè)小矩陣，每個(gè)小矩陣有一個(gè)Map任務(wù)處理則對(duì)候選集進(jìn)行統(tǒng)計(jì)需要的時(shí)間為O(| D |/m× | Ck|).

因此最壞情況下，MR_B_Apriori的時(shí)間復(fù)雜度為

比較（1）式和（2）式可見(jiàn)，式（2）中將候選集統(tǒng)計(jì)時(shí)間除以因子m說(shuō)明MR_B_Apriori算法每次迭代都會(huì)節(jié)省O((m-1) ||D/m ||Ck)的時(shí)間，可見(jiàn)事務(wù)庫(kù)越大、集群數(shù)越多節(jié)省的時(shí)間就越明顯.

5 結(jié)束語(yǔ)

本文結(jié)合MapReduce分布式處理框架的這種“分而治之”思想和Apriori算法的思想，利用多臺(tái)機(jī)器協(xié)同并行處理大數(shù)據(jù)集，降低了Apriori算法得到頻繁相集的時(shí)間復(fù)雜度.可見(jiàn)將Apriori算法移植至MapReduce分布式處理框架下，對(duì)基于云平臺(tái)的大數(shù)據(jù)挖掘具有指導(dǎo)意義.

[1]李國(guó)杰，程學(xué)旗.大數(shù)據(jù)研究：未來(lái)科技及經(jīng)濟(jì)社會(huì)發(fā)展的重大戰(zhàn)略領(lǐng)域——大數(shù)據(jù)的研究現(xiàn)狀與科學(xué)思考[J].中國(guó)科學(xué)院院刊，2012，27（6）：647-657.

[2]張石磊，武裝.一種基于Hadoop云計(jì)算平臺(tái)的聚類算法優(yōu)化的研究[J].計(jì)算機(jī)科學(xué)，2012，39（10）：115-118.

[3]楊代慶，張智雄.基于Hadoop的海量共現(xiàn)矩陣生成方法[J].現(xiàn)代圖書(shū)情報(bào)術(shù)，2009，30（4）：23-26.

[4]李玉林，董晶.基于Hadoop的MapReduce模型的研究與改進(jìn)[J].計(jì)算機(jī)工程與設(shè)計(jì)，2012，33（8）：3110-3116.

[5]劉敏嫻，馬強(qiáng)，寧以風(fēng).基于頻繁矩陣的Apriori算法改進(jìn)[J].計(jì)算機(jī)工程與設(shè)計(jì)，2012，33（11）：4235-4239.

[6]饒正嬋，范年柏.關(guān)聯(lián)規(guī)則挖掘Apriori算法研究綜述[J].計(jì)算機(jī)時(shí)代，2012，30（9）：11-13.

[7]劉以安，羊斌.關(guān)聯(lián)規(guī)則挖掘中對(duì)Apriori算法的一種改進(jìn)研究[J].計(jì)算機(jī)應(yīng)用，2007，27（2）：418-420.

[8]王鋒，李勇華，毋國(guó)慶.基于矩陣的改進(jìn)的Apriori算法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2009，30（10）：2435-24.