謝志明

摘 要： 針對目前傳統(tǒng)的Apriori算法對硬件要求較高且運(yùn)算效率低下的情形，提出將經(jīng)典的數(shù)據(jù)挖掘關(guān)聯(lián)規(guī)則算法Apriori移植到云計(jì)算平臺，并結(jié)合MapReduce機(jī)制進(jìn)行海量數(shù)據(jù)挖掘，有效地解決了傳統(tǒng)Apriori算法存在的瓶頸問題以及對硬件要求高的依賴。通過數(shù)據(jù)和節(jié)點(diǎn)對比實(shí)驗(yàn)共同驗(yàn)證了移植后的Apriori算法的運(yùn)算效率比傳統(tǒng)的Apriori算法提高了許多倍，且隨著數(shù)據(jù)量和節(jié)點(diǎn)數(shù)的增加效果愈發(fā)明顯。由于改良后的Apriori算法具有高效性和可行性，這將為解決當(dāng)前大數(shù)據(jù)挖掘問題提供了一種全新的、有效的解決方案，并且這一結(jié)論還可為其他數(shù)據(jù)挖掘算法的移植提供可靠的參考。

關(guān)鍵詞： Apriori算法； 數(shù)據(jù)挖掘； 關(guān)聯(lián)規(guī)則； 云計(jì)算； MapReduce機(jī)制

中圖分類號： TP 399 文獻(xiàn)標(biāo)志碼： A 文章編號： 1671-2153（2015）05-0076-05

0 引 言

傳統(tǒng)Apriori算法是數(shù)據(jù)挖掘中研究最成熟、最活躍的關(guān)聯(lián)規(guī)則算法之一，利用它可以發(fā)現(xiàn)數(shù)據(jù)中所蘊(yùn)含的相互關(guān)系[1]。由于傳統(tǒng)的數(shù)據(jù)挖掘算法大多是以單節(jié)點(diǎn)的機(jī)器為平臺，所處理的數(shù)據(jù)對象也主要是小到中等規(guī)模的，當(dāng)面對海量的、多維的、分散的數(shù)據(jù)集合時(shí)，現(xiàn)有的算法則往往顯得力不從心[2]。

如何處理異構(gòu)海量數(shù)據(jù)，選用那種高效的數(shù)據(jù)處理模式來提高運(yùn)算速度并降低內(nèi)存的消耗，已成為亟待解決的問題。隨著云計(jì)算技術(shù)和大數(shù)據(jù)技術(shù)相繼提出和應(yīng)用，分布式大數(shù)據(jù)處理系統(tǒng)日漸被人們關(guān)注和研究?；贖adoop搭建的云計(jì)算平臺具有分布式大數(shù)據(jù)處理能力和海量的數(shù)據(jù)存儲能力，這些都將為解決當(dāng)前異構(gòu)海量數(shù)據(jù)挖掘問題提供了一種全新的、有效的解決方案[3-4]。

1 Apriori算法描述及相關(guān)研究

Apriori算法原型是以用戶事先設(shè)置好的最小支持度（min_support）和最小可信度（min_confidence）為條件，通過對需處理的事務(wù)數(shù)據(jù)集進(jìn)行重復(fù)多次掃描，從中找出項(xiàng)與項(xiàng)之間所存在的并發(fā)關(guān)系，找到所需的關(guān)聯(lián)規(guī)則和判斷是否滿足用戶要求的過程，即發(fā)現(xiàn)頻繁項(xiàng)集和產(chǎn)生規(guī)則的過程。如圖1所示。

文獻(xiàn)[5]中說到Apriori算法在掃描數(shù)據(jù)庫時(shí)需經(jīng)過自連接、剪枝生成頻繁項(xiàng)集，并采用逐層迭代法直到無法產(chǎn)生新的頻繁項(xiàng)集時(shí)才停止掃描。文獻(xiàn)[6]解釋了在處理大規(guī)模數(shù)據(jù)時(shí)，當(dāng)設(shè)置的最小支持度偏小且產(chǎn)生的頻繁項(xiàng)也較多時(shí)，發(fā)現(xiàn)該算法效率低下。隨著研究的不斷深入和擴(kuò)大，人們發(fā)現(xiàn)在大規(guī)模數(shù)據(jù)量下傳統(tǒng)Apriori算法的優(yōu)勢越來越不明顯；相反，在實(shí)際應(yīng)用中很多時(shí)候還達(dá)不到用戶的要求。于是許多專家學(xué)者對該算法做了一些專門的改良實(shí)驗(yàn)，如文獻(xiàn)[7]中提出了一種基于數(shù)據(jù)劃分的思想用于提高Apriori算法處理海量數(shù)據(jù)挖掘的效率等。鑒于此，本文將結(jié)合分布式大數(shù)據(jù)處理系統(tǒng)Hadoop，對移植到云計(jì)算平臺的Apriori算法進(jìn)行實(shí)驗(yàn)驗(yàn)證，證明是否能有效提高數(shù)據(jù)挖掘效率。

2 Apriori算法并行化描述

Hadoop平臺有自己的分布式文件系統(tǒng)（HDFS），它是Hadoop的核心子項(xiàng)目之一，能對海量數(shù)據(jù)進(jìn)行存儲和管理。當(dāng)數(shù)據(jù)上傳到HDFS上后，由命名節(jié)點(diǎn)（Namenode）統(tǒng)一管理對各個(gè)節(jié)點(diǎn)文件的訪問。上傳來的大文件將會被分割成一個(gè)或多個(gè)塊（block），這些block存儲在數(shù)據(jù)節(jié)點(diǎn)（Datanode）集合里，并由Datanode負(fù)責(zé)調(diào)用Map（）函數(shù)[8]。Hadoop平臺中的Map（）函數(shù)負(fù)責(zé)處理局部的數(shù)據(jù)，對候選項(xiàng)集做本地統(tǒng)計(jì)后，然后把統(tǒng)計(jì)信息傳到主節(jié)點(diǎn)，最后啟動Reduce程序，它負(fù)責(zé)把Map（）函數(shù)局部統(tǒng)計(jì)統(tǒng)計(jì)結(jié)果匯總，然后判斷那些是滿足要求的候選項(xiàng)集，即形成頻繁項(xiàng)集[9]。MapReduce Apriori（簡稱Apriori_MR）算法偽代碼如下：

輸入：D（HDFS上的數(shù)據(jù)）， min_support

（1）L1=find_frequent_1-itemsets（D）；

（2）for（k=2；Lk-1≠Φ；k++） {

（3）Map1（key，value，Lk-1，X.count），

Map2（key，value，Lk-1，X.count），……，

Mapi（key，value，Lk-1，X.count）

（4）Lk=Reduce（Lk-1，X.count，Lk-1，K.support）}

（5）return L=LUkLk；

輸出：頻繁項(xiàng)目集L

MapReduce Apriori算法處理過程如圖2所示。

3 Apriori_MR算法設(shè)計(jì)

該算法在MapReduce編程模式中是以鍵值對（Key/Value）的形式進(jìn)行計(jì)算的，計(jì)算完畢后也是以鍵值對的形式輸出。在進(jìn)行MapReduce處理的過程中，Map（）函數(shù)和Reduce（）函數(shù)是最為關(guān)鍵的兩個(gè)函數(shù)。如需要實(shí)現(xiàn)某些特定功能，可以通過改寫Map（）和Reduce（）函數(shù)來完成。

3.1 Key/Value的設(shè)計(jì)

表1為定義的Key/Value類型情況。表1中，Map（）函數(shù)是以Key/Value鍵值對輸入的，期間會產(chǎn)生一系列Key/Value鍵值對并作為中間結(jié)果輸出寫入到本地磁盤。MapReduce框架則按照Key值自動聚集原則將具有相同的Key值統(tǒng)一交給Reduce（）函數(shù)處理。Reduce（）函數(shù)將這些具有相同的Key進(jìn)行合并得到相應(yīng)的Value值，最終產(chǎn)生一個(gè)全新的系列Key/Value鍵值對并將結(jié)果寫入到HDFS中。

3.2 Map的設(shè)計(jì)

在Hadoop中，用遠(yuǎn)程過程調(diào)用（RPC，Remote Procedures Call）的方式來實(shí)現(xiàn)各個(gè)節(jié)點(diǎn)的通信[8]。RPC協(xié)議主要作用是將消息編碼為二進(jìn)制流，該過程是通過序列化方式實(shí)現(xiàn)的。在MapReduce編程模型中，用戶的輸入與輸出數(shù)據(jù)要求Key和Value都必須是序列化的。

Hadoop的序列化核心是Writable，它提供了兩個(gè)接口方法來實(shí)現(xiàn)二進(jìn)制格式數(shù)據(jù)流的寫入和讀出，其特點(diǎn)是快速和緊湊。MapReduce的數(shù)據(jù)路徑傳遞中最重要的就是Writables，通過重新定義該接口能控制二進(jìn)制值表示和排序等功能。當(dāng)使用這個(gè)經(jīng)重新定義過的擴(kuò)展Writables接口的Frequent類，可以把每次生成的頻繁Lk存儲到類Frequent里面，然后通過算法Apriori_gen（Lk）得到候選項(xiàng)集Ck，最后可以掃描局部的數(shù)據(jù)得到各個(gè)候選項(xiàng)項(xiàng)集Ck中各個(gè)項(xiàng)的個(gè)數(shù)。其偽代碼如下：

map（key， value， Lk， X.count）

{

Ck= Apriori_gen（Lk）；

for（i=1；i<=Ck .size（）；i++） {

if（value中含有Ck中的項(xiàng)）

Ck .item的計(jì)算記錄為1；

write（Ck .item， 1）； }

}

3.3 Reduce的設(shè)計(jì)

Reduce的主要工作是將由Map過程所生成的候選項(xiàng)集中每一項(xiàng)的計(jì)數(shù)通過Reduce函數(shù)將相同項(xiàng)的局部計(jì)數(shù)進(jìn)行相加，并把滿足用戶最小支持度的那部分寫入到文件中的過程，如圖3所示。

由圖3可以看出，Map（）函數(shù)在處理數(shù)據(jù)的過程時(shí)，它首先統(tǒng)計(jì)每個(gè)項(xiàng)的數(shù)量，再對每個(gè)存在的項(xiàng)記錄一次；而Reduce（）函數(shù)則僅用于匯總候選集項(xiàng)的數(shù)量，其偽代碼為：

public void reduce（Candidate key， Iterablevalues， Context context） throws IOException， InterruptedException {

IntWritable result = new IntWritable（）；

int sum = 0；

對候選集中相同的項(xiàng)進(jìn)行計(jì)數(shù)

for （IntWritable val ： values） {

sum += val.get（）； }

if （（double） sum >= supportCount） {

result.set（sum）；

context.write（key， result）； }

}

4 Apriori_MR實(shí)驗(yàn)和結(jié)果分析

以下所用到的實(shí)驗(yàn)數(shù)據(jù)是由人工數(shù)據(jù)合成工具（IBM Quest Market-Basket Synthetic Data Generator）生成的，它是關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘?qū)嶒?yàn)中經(jīng)常用到的工具。通過數(shù)據(jù)對比實(shí)驗(yàn)和節(jié)點(diǎn)對比實(shí)驗(yàn)來驗(yàn)證該算法是否具有高效性。

4.1 數(shù)據(jù)對比實(shí)驗(yàn)

本研究使用了集群里的9個(gè)節(jié)點(diǎn)做數(shù)據(jù)測試，數(shù)據(jù)記錄以文件的形式進(jìn)行存放，其最小支持度均設(shè)為70%，在計(jì)算節(jié)點(diǎn)不變而數(shù)據(jù)量變化的情況下進(jìn)行多組實(shí)驗(yàn)后兩種算法的對照結(jié)果如圖4所示。

由圖4可以看出，當(dāng)數(shù)據(jù)量在一百萬條記錄期間時(shí)，基于MapReduce框架的Apriori算法和經(jīng)典的Apriori算法所用時(shí)間相差不大，然而，隨著數(shù)據(jù)量的增加，程序運(yùn)行的時(shí)間差距逐漸拉大。產(chǎn)生這種現(xiàn)象的主要原因是，當(dāng)數(shù)據(jù)量較少時(shí)，通信開銷所占總運(yùn)行時(shí)間比例相對較大，隨著數(shù)據(jù)量的增多，處理數(shù)據(jù)的時(shí)間占總運(yùn)行時(shí)間比例上升，通信開銷則可以忽略不計(jì)。而且在集群環(huán)境下可以并發(fā)處理數(shù)據(jù)，加快了數(shù)據(jù)處理速度。根據(jù)數(shù)據(jù)對比實(shí)驗(yàn)可以得出以下結(jié)論：Apriori_MR比傳統(tǒng)的Apriori更適合處理海量數(shù)據(jù)，且隨著數(shù)據(jù)量的增加相對單機(jī)的優(yōu)勢愈發(fā)顯得明顯。

4.2 節(jié)點(diǎn)對比實(shí)驗(yàn)

在此實(shí)驗(yàn)中以加速比（Speedup）作為一個(gè)重要的衡量標(biāo)準(zhǔn)。加速比，指的是運(yùn)用單處理器系統(tǒng)和并行處理器系統(tǒng)來處理同一任務(wù)所消耗時(shí)間的比對關(guān)系，并通過這一對比結(jié)果衡量出串行系統(tǒng)與并行系統(tǒng)的性能差。加速比Sp定義如下：

Sp=Ts / Tp，

式中：Ts為串行處理時(shí)間；Tp為并行處理時(shí)間。在實(shí)驗(yàn)中把單一節(jié)點(diǎn)機(jī)上運(yùn)行的時(shí)間看做Ts，多個(gè)節(jié)點(diǎn)機(jī)上運(yùn)行的時(shí)間看做Tp。根據(jù)文獻(xiàn)[10]所提到的MapReduce所具有優(yōu)點(diǎn)之一是Hadoop集群有很好的伸縮性，能非常方便的將具有計(jì)算能力的PC機(jī)接入到集群。本實(shí)驗(yàn)將通過改變計(jì)算節(jié)點(diǎn)來測試移植后的Apriori_MR算法在進(jìn)行等量數(shù)據(jù)挖掘的時(shí)間差，分析其加速比情況。圖5顯示了1000萬條記錄在不同節(jié)點(diǎn)數(shù)集群上的測試情況，測試中數(shù)據(jù)量與支持度一直保持不變。

由圖5可以看出，當(dāng)節(jié)點(diǎn)數(shù)小于等于3時(shí)，消耗時(shí)間的差距不大，主要原因是要考慮到集群的通信開銷。然而，隨著節(jié)點(diǎn)數(shù)的增加，所花費(fèi)的時(shí)間越來越少，加速比之間的差距也越來越小，按照這種趨勢，加速比曲線會慢慢趨于平穩(wěn)上升并保持下去。根據(jù)節(jié)點(diǎn)對比實(shí)驗(yàn)可以得出如下結(jié)論：在數(shù)據(jù)量不變的情況下，當(dāng)數(shù)據(jù)節(jié)點(diǎn)大于一定數(shù)量時(shí)，節(jié)點(diǎn)數(shù)越多，處理速度越快，效率越高。

根據(jù)上述兩個(gè)對比實(shí)驗(yàn)，在數(shù)據(jù)量的持續(xù)增加和節(jié)點(diǎn)數(shù)擴(kuò)展過程中，Apriori_MR算法在數(shù)據(jù)處理效率和擴(kuò)展方面表現(xiàn)出良好的性能以及良好的外延性。因此，可以得出如下結(jié)論，將傳統(tǒng)的Apriori算法移植到云計(jì)算平臺上進(jìn)行大數(shù)據(jù)挖掘處理不僅是高效的而且也是行得通的。

5 結(jié)束語

云計(jì)算目前已經(jīng)是全球最具有發(fā)展?jié)摿Φ男畔㈩惣夹g(shù)之一，如何高效地將傳統(tǒng)的數(shù)據(jù)挖掘算法移植到云計(jì)算平臺上，已成為時(shí)下最流行研究的核心領(lǐng)域之一。本文從分析經(jīng)典的Apriori算法基礎(chǔ)入手，結(jié)合云計(jì)算平臺和大數(shù)據(jù)分布式處理技術(shù)對該算法加以改進(jìn)并移植，能有效地解決傳統(tǒng)意義上Apriori算法在數(shù)據(jù)挖掘過程中遇到的諸多客觀問題。并通過實(shí)驗(yàn)數(shù)據(jù)、圖形分析證實(shí)了Apriori_MR算法要比傳統(tǒng)的Apriori算法在性能上優(yōu)越許多，該算法的成功移植還進(jìn)一步為移植更高效的數(shù)據(jù)挖掘算法提供了可靠的參考。

參考文獻(xiàn)：

[1] 習(xí)慧丹. 關(guān)聯(lián)規(guī)則挖掘優(yōu)化方法研究[J]. 計(jì)算機(jī)與數(shù)字工程，2012，40（5）：31-33.

[2] 涂新莉，劉波，林偉偉. 大數(shù)據(jù)研究綜述[J]. 計(jì)算機(jī)應(yīng)用研究，2014，31（6）：1612-1616，1623.

[3] 張濱，陳吉榮，樂嘉錦. 大數(shù)據(jù)管理技術(shù)研究綜述[J]. 計(jì)算機(jī)應(yīng)用與軟件，2014，31（11）：1-5，11.

[4] GONCALVES C，ASSUNCAO L，CUNHA J. Data analytics in the cloud with flexible MapReduce workflows[C]//Proceeding of the 2012 IEEE 4th International Conference on Cloud Computing Technology and Science. Taipei：[s.n.]，2012：427-434.

[5] 毛國君，段立娟，王實(shí)，等. 數(shù)據(jù)挖掘原理與算法[M]. 北京：清華大學(xué)出版社，2007.

[6] 劉麗. 基于關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘技術(shù)綜述[J]. 現(xiàn)代計(jì)算機(jī)，2011，32（7）：25-27.

[7] 段艷明，肖輝輝. 改進(jìn)Apriori算法處理海量數(shù)據(jù)的研究[J]. 電腦與信息技術(shù)，2013，21（1）：22-24.

[8] 董西成. Hadoop技術(shù)內(nèi)幕-深入解析MapReduce架構(gòu)設(shè)計(jì)與實(shí)現(xiàn)原理[M]. 北京：機(jī)械工業(yè)出版社，2013.

[9] KOVACS F，ILLES J.Frequent itemset mining on hadoop[C]//Proceeding of the 2013 IEEE 9th International Conference on Computational Cybernetics. Tihany，Hungary，2013：241-245.

[10] 丁祥武，李清炳，樂嘉錦. 使用MapReduce構(gòu)建列存儲數(shù)據(jù)的索引[J]. 計(jì)算機(jī)應(yīng)用與軟件，2014，31（2）：24-28.