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

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

中圖分類號(hào)：TP311.13

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

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

1.1 Apriori算法

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

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

1.2 Mapreduce模型

Google公司針對(duì)大數(shù)據(jù)的處理，開發(fā)了分布式模型——Mapreduce模型[3]。Mapreduce模型利用Map和Reduce來實(shí)現(xiàn)數(shù)據(jù)的并行處理，從而提升數(shù)據(jù)處理的效率。該模型的原理為：首先把一個(gè)較大的文件分割成多個(gè)相互獨(dú)立的數(shù)據(jù)文件，接著利用Map對(duì)這些文件進(jìn)行并行處理，然后利用Reduce對(duì)處理結(jié)果進(jìn)行匯聚，最后輸出所需的結(jié)果。具體來說，其處理過程可以分成兩個(gè)階段：（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ù)器對(duì)第一階段所輸出的結(jié)果進(jìn)行Reduce處理，對(duì)[key，value]所構(gòu)成的數(shù)據(jù)集進(jìn)行合并，并把合并后的結(jié)果送給輸出。

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

2 基于Mapreduce模型的Apriori算法

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

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

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

4 結(jié)束語

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

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

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