在數(shù)據(jù)挖掘中一種基于Mapreduce模型的Apriori算法研究

摘 要：由于傳統(tǒng)Aprioir算法的運(yùn)算效率及擴(kuò)展性較差的缺陷，使得其難以勝任海量數(shù)據(jù)的挖掘，因此本文提出了一種基于Mapreduce模型的Apriori算法。仿真表明，該算法能夠大大地縮短挖掘時間，從而提高了Apriori算法的運(yùn)算效率。

關(guān)鍵詞：數(shù)據(jù)挖掘；關(guān)聯(lián)規(guī)則；Mapreduce；Aprioir

中圖分類號：TP311.13

當(dāng)前，數(shù)據(jù)挖掘在各個領(lǐng)域都得到了越來越廣泛地使用[1]。而關(guān)聯(lián)規(guī)則挖掘是其中的一個重要分支。其通過對數(shù)據(jù)庫中的海量數(shù)據(jù)進(jìn)行分析，從而發(fā)掘出數(shù)據(jù)之間的關(guān)聯(lián)關(guān)系。Apriori算法是常用的一種關(guān)聯(lián)規(guī)則挖掘算法。但是該算法在進(jìn)行數(shù)據(jù)分析的時候，該算法不僅需要對數(shù)據(jù)庫多次的遍歷，而且還會生成很多的候選集，從而造成該算法的計算開銷較大，并且擴(kuò)展性也比較差。因此，本文采用Mapreduce模型來對Apriori算法進(jìn)行改進(jìn)，以實(shí)現(xiàn)算法運(yùn)算效率及擴(kuò)展性的提升。

1 相關(guān)概念介紹

1.1 Apriori算法

Arpriori算法的處理流程為[2]：（1）通過對數(shù)據(jù)庫的遍歷來構(gòu)造頻繁集，該集合的階數(shù)為1；（2）利用（1）中的頻繁項(xiàng)集來生成候選集，該候選集的階數(shù)為2；（3）再次對數(shù)據(jù)庫進(jìn)行遍歷以實(shí)現(xiàn)對候選集的計數(shù)，從而去除庫中的非頻繁項(xiàng)，剩下的則為二階頻繁集；（4）重復(fù)進(jìn)行上述過程，直至候選集的階數(shù)沒法再增加，或者頻繁集的長度達(dá)到了所設(shè)置的最大值。

從上述分析可以看出，Arpriori算法需要頻繁地遍歷數(shù)據(jù)庫，而數(shù)據(jù)庫的遍歷需要消耗很多的時間，因此如果能夠減少數(shù)據(jù)庫遍歷次數(shù)，那么，Arpriori算法的運(yùn)行效率將得到大大地提升。

1.2 Mapreduce模型

Google公司針對大數(shù)據(jù)的處理，開發(fā)了分布式模型——Mapreduce模型[3]。Mapreduce模型利用Map和Reduce來實(shí)現(xiàn)數(shù)據(jù)的并行處理，從而提升數(shù)據(jù)處理的效率。該模型的原理為：首先把一個較大的文件分割成多個相互獨(dú)立的數(shù)據(jù)文件，接著利用Map對這些文件進(jìn)行并行處理，然后利用Reduce對處理結(jié)果進(jìn)行匯聚，最后輸出所需的結(jié)果。具體來說，其處理過程可以分成兩個階段：（1）在第一階段，首先把待挖掘數(shù)據(jù)分成N份較小的數(shù)據(jù)塊，接著這N份數(shù)據(jù)塊將被分配到不同的主機(jī)的Map進(jìn)程進(jìn)行Map處理，在處理的過程中，數(shù)據(jù)以[key，value]的形式來進(jìn)行呈現(xiàn)；（2）在第二階段，服務(wù)器對第一階段所輸出的結(jié)果進(jìn)行Reduce處理，對[key，value]所構(gòu)成的數(shù)據(jù)集進(jìn)行合并，并把合并后的結(jié)果送給輸出。

Mapreduce模型的并行處理能力減少了算法的時間開銷，而且該模型把程序開發(fā)人員從并行過程的細(xì)節(jié)處理中解脫出來，從而大大地縮短了程序的開發(fā)。

2 基于Mapreduce模型的Apriori算法

為了提升Apriori算法的效率，本文利用Mapredcue模型來改造Apriori算法，使得新算法能夠進(jìn)行并行處理，從而大大地減少了計算開銷。給出了基于Mapreduce模型的Apriori算法的處理流程圖，其過程為：首先通過數(shù)據(jù)庫的遍歷來構(gòu)造布爾矩陣，接著刪除矩陣中的重復(fù)內(nèi)容，就得到了壓縮布爾矩陣M，接下來使用Mapreduce模型來把M分成多個子矩陣，并把子矩陣分給集群中的多臺計算機(jī)中的Map進(jìn)程來實(shí)現(xiàn)并行處理，從而得到每個子矩陣的候選集，然后利用Reduce對所有的候選集進(jìn)行合并處理，從而得到全局K候選集。

3 仿真分析

為了驗(yàn)證算法在關(guān)聯(lián)規(guī)則關(guān)系挖掘中的性能，本文把一組銀行交易數(shù)據(jù)用作實(shí)驗(yàn)數(shù)據(jù)，分別利用Apriori算法與基于Mapreduce模型的Apriori算法來尋找交易之間的關(guān)聯(lián)關(guān)系。

利用三臺安裝了Unix系統(tǒng)的服務(wù)器來搭建實(shí)驗(yàn)環(huán)境。服務(wù)器的硬件配置為：CPU為Intel Xeon E5-2650，內(nèi)存大小為16GB。Apriori算法運(yùn)行在任意一臺服務(wù)器上，而基于Mapreduce模型的Apriori算法運(yùn)行在三臺服務(wù)器所構(gòu)成的分布式系統(tǒng)上。圖2給出了兩種算法的計算開銷。

基于Mapreduce模型的Apriori算法的計算開銷明顯小于Apriori算法的。并且隨著記錄數(shù)的增加，Apriori算法的計算開銷出現(xiàn)較快的增長，而基于Mapreduce模型的Apriori算法的計算開銷的增長幅度并不是很明顯。由于基于Mapreduce模型的Apriori算法使用三臺服務(wù)器來進(jìn)行數(shù)據(jù)的處理，因此，圖2也給出了運(yùn)行基于Mapreduce模型的Apriori算法的三臺服務(wù)器所用時間的累加值，其累加值仍然要小于Apriori算法的。這是因?yàn)锳priori算法牽涉到很多的I/O操作，而由于硬件本身的限制，其中一部分I/O操作將會被掛起直到有系統(tǒng)資源分配給它，從而造成了運(yùn)行時間的增加。而基于Mapreduce模型的Apriori算法通過Map與Reduce，大大地縮短了讀寫時間，從而能夠縮短算法的運(yùn)行時間。

4 結(jié)束語

為了解決Aprioir算法在面對海量數(shù)據(jù)進(jìn)行挖掘的時候，其計算開銷較大的問題。本文提出了基于Mapreduce模型的Apriori算法。該算法通過Mapreduce模型的使用提升了Apriori算法并行處理能力，從而縮短了挖掘時間，提高了數(shù)據(jù)挖掘的效率。

參考文獻(xiàn)：

[1]Witten I H，F(xiàn)rank E.Data Mining：Practical machine learning tools and techniques[M].Morgan Kaufmann，2005.

[2]Liu Y.Study on application of apriori algorithm in data mining[C].Computer Modeling and Simulation，2010.ICCMS'10.Second International Conference on.IEEE，2010（03）：111-114.

[3]Dean J，Ghemawat S.MapReduce：a flexible data processing tool[J].Communications of the ACM，2010（01）：72-77.

作者簡介：姜凱強(qiáng)（1993.01-），男，山東濰坊人，本科，學(xué)生，研究方向：云計算；馮霄月（1993.04-），女，山東德州人，本科，學(xué)生，研究方向：數(shù)據(jù)統(tǒng)計。

作者單位：山東科技大學(xué)，山東青島 266510