謝志明

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

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

中圖分類號： TP 399 文獻標志碼： A 文章編號： 1671-2153（2015）05-0076-05

0 引 言

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

如何處理異構(gòu)海量數(shù)據(jù)，選用那種高效的數(shù)據(jù)處理模式來提高運算速度并降低內(nèi)存的消耗，已成為亟待解決的問題。隨著云計算技術(shù)和大數(shù)據(jù)技術(shù)相繼提出和應(yīng)用，分布式大數(shù)據(jù)處理系統(tǒng)日漸被人們關(guān)注和研究。基于Hadoop搭建的云計算平臺具有分布式大數(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ù)集進行重復(fù)多次掃描，從中找出項與項之間所存在的并發(fā)關(guān)系，找到所需的關(guān)聯(lián)規(guī)則和判斷是否滿足用戶要求的過程，即發(fā)現(xiàn)頻繁項集和產(chǎn)生規(guī)則的過程。如圖1所示。

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

2 Apriori算法并行化描述

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

輸出：頻繁項目集L

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

3 Apriori_MR算法設(shè)計

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

3.1 Key/Value的設(shè)計

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

3.2 Map的設(shè)計

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

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

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

{

Ck= Apriori_gen（Lk）；

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

if（value中含有Ck中的項）

Ck .item的計算記錄為1；

write（Ck .item， 1）； }

}

3.3 Reduce的設(shè)計

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

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

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

IntWritable result = new IntWritable（）；

int sum = 0；

對候選集中相同的項進行計數(shù)

for （IntWritable val ： values） {

sum += val.get（）； }

if （（double） sum >= supportCount） {

result.set（sum）；

context.write（key， result）； }

}

4 Apriori_MR實驗和結(jié)果分析

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

4.1 數(shù)據(jù)對比實驗

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

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

4.2 節(jié)點對比實驗

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

Sp=Ts / Tp，

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

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

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

5 結(jié)束語

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

參考文獻：

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

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

[3] 張濱，陳吉榮，樂嘉錦. 大數(shù)據(jù)管理技術(shù)研究綜述[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ù)據(jù)挖掘原理與算法[M]. 北京：清華大學(xué)出版社，2007.

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

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

[8] 董西成. Hadoop技術(shù)內(nèi)幕-深入解析MapReduce架構(gòu)設(shè)計與實現(xiàn)原理[M]. 北京：機械工業(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]. 計算機應(yīng)用與軟件，2014，31（2）：24-28.