基于MapReduce的Apriori算法并行化改進(jìn)

秦 軍，郝天曙，董倩倩

(1.南京郵電大學(xué) 教育科學(xué)與技術(shù)學(xué)院，江蘇 南京 210003；2.南京郵電大學(xué) 計(jì)算機(jī)學(xué)院，江蘇 南京 210003)

基于MapReduce的Apriori算法并行化改進(jìn)

秦 軍1，郝天曙2，董倩倩2

(1.南京郵電大學(xué) 教育科學(xué)與技術(shù)學(xué)院，江蘇 南京 210003；2.南京郵電大學(xué) 計(jì)算機(jī)學(xué)院，江蘇 南京 210003)

基于MapReduce的并行Apriori算法解決了傳統(tǒng)Apriori算法多次掃描數(shù)據(jù)庫(kù)的問(wèn)題，但是其候選集仍然由頻繁項(xiàng)集經(jīng)過(guò)串行自連接產(chǎn)生,并產(chǎn)生了大量的候選集中間數(shù)據(jù)。為了提高Apriori算法挖掘頻繁項(xiàng)集的效率，在基于MapReduce的Apriori算法的基礎(chǔ)上對(duì)連接步進(jìn)行并行化改進(jìn)，提出大數(shù)據(jù)環(huán)境下挖掘頻繁項(xiàng)目集的新算法—CApriori算法。新算法通過(guò)Map、Reduce過(guò)程從頻繁k-項(xiàng)集中并行得到k+1項(xiàng)候選集，使得Apriori算法產(chǎn)生頻繁項(xiàng)集的整個(gè)過(guò)程并行化，減少了迭代過(guò)程中候選集數(shù)目，節(jié)約了存儲(chǔ)空間和時(shí)間開銷。通過(guò)對(duì)時(shí)間復(fù)雜度進(jìn)行分析比較，改進(jìn)算法在處理大規(guī)模數(shù)據(jù)時(shí)會(huì)大大減少連接步的時(shí)間消耗。將CApriori算法在Hadoop平臺(tái)上進(jìn)行了實(shí)驗(yàn)，結(jié)果表明改進(jìn)算法在大數(shù)據(jù)和較小支持度環(huán)境下都具有更高的效率，且能取得優(yōu)異的加速功能。

關(guān)聯(lián)規(guī)則；數(shù)據(jù)挖掘；MapReduce；Apriori

0 引 言

關(guān)聯(lián)規(guī)則[1]挖掘用于從大量數(shù)據(jù)中挖掘出有價(jià)值的數(shù)據(jù)項(xiàng)之間的相關(guān)關(guān)系。關(guān)聯(lián)規(guī)則揭示了數(shù)據(jù)項(xiàng)間未知的依賴關(guān)系，根據(jù)所挖掘的關(guān)聯(lián)關(guān)系，可以從一個(gè)數(shù)據(jù)對(duì)象的信息來(lái)推斷另一個(gè)數(shù)據(jù)對(duì)象的信息。關(guān)聯(lián)規(guī)則最為經(jīng)典的是Apriori算法，該算法采用逐層迭代方法，通過(guò)連接和剪枝得到頻繁項(xiàng)集。其缺點(diǎn)是重復(fù)掃描數(shù)據(jù)庫(kù)，產(chǎn)生大量的候選集，算法效率較低。因此，國(guó)內(nèi)外很多學(xué)者通過(guò)布爾矩陣、哈希技術(shù)、基于事務(wù)壓縮矩陣相乘、分區(qū)技術(shù)和采樣技術(shù)等對(duì)Apriori算法進(jìn)行改進(jìn)和優(yōu)化，提出基于Apriori算法的并行算法，包括：CD、DD以及CaD算法。然而，這些算法很難處理具有大容量、多樣性、快速度、商業(yè)價(jià)值高的“4V”特征大數(shù)據(jù)。例如：基于壓縮事務(wù)矩陣相乘的改進(jìn)算法在矩陣相乘上花費(fèi)了較多時(shí)間[2]；并行算法CD、DD和CaD[3]在通信和同步方面都存在一些問(wèn)題。

云計(jì)算為提高海量數(shù)據(jù)挖掘效率提供了新思路。MapReduce是一種編程模式，它可以產(chǎn)生并處理海量數(shù)據(jù)集。MapReduce編程模型的一個(gè)關(guān)鍵優(yōu)勢(shì)在于它能自動(dòng)處理運(yùn)行故障，隱藏很多繁瑣的細(xì)節(jié)并且可以在物理集群上實(shí)現(xiàn)并行化處理。國(guó)內(nèi)外學(xué)者應(yīng)用MapReduce思想對(duì)Apriori進(jìn)行了并行化改進(jìn)[4-7]，但是這些改進(jìn)的Apriori算法只考慮計(jì)數(shù)步，產(chǎn)生了大量的候選集中間數(shù)據(jù)，或者多次掃描全局?jǐn)?shù)據(jù)庫(kù)，以一種空間代價(jià)換取時(shí)間代價(jià)的方法來(lái)加速頻繁項(xiàng)集的產(chǎn)生。當(dāng)數(shù)據(jù)集很大而且支持度低時(shí)，將會(huì)產(chǎn)生巨大候選集，嚴(yán)重影響算法的運(yùn)行效率。

文中提出通過(guò)并行的Map，Reduce過(guò)程從頻繁k-項(xiàng)集中并行得到k+1項(xiàng)候選集Ck+1，極大減少了迭代過(guò)程中候選集數(shù)量，節(jié)約了大量的存儲(chǔ)空間和自連接結(jié)果在各個(gè)節(jié)點(diǎn)之間傳輸?shù)木W(wǎng)絡(luò)開銷、時(shí)間開銷，從而提高了算法的執(zhí)行效率。改進(jìn)算法稱之為完全并行Apriori算法，即CApriori算法。

1 基本概念

Apriori算法是挖掘關(guān)聯(lián)規(guī)則頻繁項(xiàng)集的最經(jīng)典的算法[8]，但傳統(tǒng)的關(guān)聯(lián)規(guī)則挖掘技術(shù)已經(jīng)不能滿足大數(shù)據(jù)的需求，因此云技術(shù)與數(shù)據(jù)挖掘的融合以及改進(jìn)成為當(dāng)下焦點(diǎn)。本節(jié)主要介紹Apriori算法以及MapReduce框架模型。

1.1 Apriori算法

通過(guò)反復(fù)掃描數(shù)據(jù)庫(kù)，Apriori算法逐層搜索候選項(xiàng)集，最終目的在于迭代地產(chǎn)生頻繁項(xiàng)集。Apriori算法的思想[9]為：通過(guò)k次掃描產(chǎn)生長(zhǎng)度為k的頻繁k-項(xiàng)集Lk，通過(guò)串行自連接產(chǎn)生候選項(xiàng)集Ck+1；統(tǒng)計(jì)事務(wù)集DB中所有長(zhǎng)度為k+1的候選集Ck+1的出現(xiàn)次數(shù)，直到無(wú)法再找到頻繁項(xiàng)集。可見(jiàn)，每找出一個(gè)Lk，需要掃描一次數(shù)據(jù)庫(kù)，而且產(chǎn)生的候選集也極為龐大。

Apriori算法時(shí)間主要消耗在三個(gè)方面：

(1)Apriori算法在執(zhí)行“連接-剪枝”的迭代過(guò)程中需要多次掃描數(shù)據(jù)庫(kù)，如果生成的頻繁項(xiàng)目集中含有k-項(xiàng)集，則要掃描k遍數(shù)據(jù)庫(kù)。當(dāng)k數(shù)值較大時(shí)，系統(tǒng)I/O負(fù)載非常大，每次掃描時(shí)間就會(huì)很長(zhǎng)。

(2)頻繁項(xiàng)集自身連接生成候選項(xiàng)集時(shí)，所產(chǎn)生的侯選項(xiàng)集數(shù)目龐大。若事務(wù)數(shù)據(jù)集中頻繁項(xiàng)集長(zhǎng)度為30，至少會(huì)產(chǎn)生230-1=109個(gè)候選集。

(3)當(dāng)頻繁項(xiàng)集巨大，串行自連接產(chǎn)生候選集將消耗很長(zhǎng)時(shí)間。

1.2 MapReduce編程模型

MapReduce[10]模型的基本思想是將問(wèn)題分解為兩個(gè)處理階段—Map階段和Reduce階段[11]，由用戶實(shí)現(xiàn)的Map函數(shù)和Reduce函數(shù)完成大規(guī)模的并行化計(jì)算。開源的云計(jì)算平臺(tái)Hadoop實(shí)現(xiàn)了MapReduce模型。在該模型中，數(shù)據(jù)文件被切分成大小相同的多個(gè)數(shù)據(jù)分片存儲(chǔ)在Hadoop分布式文件系統(tǒng)HDFS[12]中。在input階段，MapReduce支持庫(kù)將數(shù)據(jù)分片的記錄解析為形式的鍵值對(duì)，然后由Mapper接口實(shí)現(xiàn)該Map函數(shù)。Map函數(shù)對(duì)數(shù)據(jù)分片進(jìn)行處理，產(chǎn)生一組新的對(duì)中間結(jié)果。在shuffle階段，相同key的value值被合并為values集合，把(其中key為事務(wù)編號(hào)，values為該事物所包含的項(xiàng)集，即一個(gè)項(xiàng)的列)通過(guò)Reducer接口傳遞給Reduce函數(shù)。Reduce函數(shù)對(duì)集合作進(jìn)一步處理，將最終結(jié)果輸出到HDFS中。

2 基于MapReduce的CApriori算法

通過(guò)分析基于MapReduce框架下的Apriori算法，針對(duì)其并行化存在的不足提出CApriori算法。對(duì)比MapReduce框架下的CApriori算法和Apriori算法的時(shí)間復(fù)雜度，證明CApriori算法在處理海量數(shù)據(jù)時(shí)的先進(jìn)性，并把CApriori算法移植到MapReduce框架下實(shí)現(xiàn)海量數(shù)據(jù)集的挖掘。

2.1 MapReduce框架下的Apriori算法

運(yùn)用Apriori算法掃描存儲(chǔ)海量的數(shù)據(jù)庫(kù)時(shí)將消耗大量的時(shí)間和內(nèi)存空間，這成為了Apriori算法的瓶頸。雖然對(duì)Apriori算法進(jìn)行并行優(yōu)化改進(jìn)，但是隨著數(shù)據(jù)規(guī)模的增大，傳統(tǒng)的并行方案因資源需求過(guò)大或通信消耗過(guò)多而變得低效[13]。Apriori算法利用MapReduce“分而治之”的設(shè)計(jì)思想生成頻繁項(xiàng)集：對(duì)事物數(shù)據(jù)進(jìn)行水平分割，將事務(wù)數(shù)據(jù)庫(kù)DB水平劃分為n個(gè)規(guī)模相當(dāng)?shù)臄?shù)據(jù)塊，然后把數(shù)據(jù)塊發(fā)送到m個(gè)節(jié)點(diǎn)；運(yùn)行Map程序，通過(guò)掃描每個(gè)數(shù)據(jù)塊，找出頻繁1-項(xiàng)集，再產(chǎn)生每個(gè)數(shù)據(jù)塊的局部候選k項(xiàng)集Ck，局部候選項(xiàng)集的產(chǎn)生算法與經(jīng)典Apriori算法相同，采取串行自連接的方式產(chǎn)生候選集；編寫Combine將Map階段結(jié)果進(jìn)行合并；利用Reduce函數(shù)生成全局候選頻繁項(xiàng)集；依次迭代，找出所有頻繁項(xiàng)集。

基于MapReduce的Apriori算法減少了對(duì)事物數(shù)據(jù)庫(kù)的依賴，執(zhí)行效率相對(duì)于傳統(tǒng)的Apriori算法提高顯著，但是在迭代過(guò)程中會(huì)產(chǎn)生巨大候選集數(shù)目，連接步依然由頻繁項(xiàng)集Lk-1自連接生成候選項(xiàng)集Ck，非常耗時(shí)。

2.2 Apriori算法并行化改進(jìn)

具體思路：把上一輪迭代產(chǎn)生的頻繁k-項(xiàng)集Lk分割成若干份相同的數(shù)據(jù)塊，然后調(diào)用Mapper接口對(duì)每個(gè)數(shù)據(jù)塊進(jìn)行Map函數(shù)處理。通過(guò)Map函數(shù)的處理，產(chǎn)生一組新的中間結(jié)果；把具有相同key的value值合并為values集合，通過(guò)Reducer接口把傳遞給Reduce函數(shù)。Reduce函數(shù)對(duì)集合進(jìn)行劃分，得出候選集Ck+1。

實(shí)例如圖1所示。

圖1 CApriori連接步具體實(shí)現(xiàn)

輸入的頻繁項(xiàng)集L3被分割成塊，傳送給Map函數(shù)；Map函數(shù)把頻繁{1,2,3}變換成一個(gè)鍵值對(duì){{1,2}:3}，然后具有相同鍵的鍵值對(duì)會(huì)組合起來(lái)形成{1,2,3 5 9}傳遞給Reduce函數(shù)。Reduce函數(shù)對(duì)鍵值對(duì)進(jìn)行處理，形成候選集C4。

Apriori算法連接步的時(shí)間復(fù)雜度是O(|Lk|2)。CApriori算法的連接步時(shí)間復(fù)雜度由三部分組成，即Map，Reduce階段以及在Map函數(shù)和Reduce函數(shù)通信時(shí)間，具體如式(1)所示。

Tc=Tmap+Tcomm+Treduce

(1)

其中，Tc表示總時(shí)間；Tmap表示Map階段消耗時(shí)間；Tcomm表示兩個(gè)函數(shù)的通信時(shí)間；Treduce表示Reduce階段消耗時(shí)間。

(2)

其中，Vkey(i)為i-1項(xiàng)事務(wù)集；num為事務(wù)個(gè)數(shù)；n為Reduce函數(shù)個(gè)數(shù)。

在MapReduce并行框架下，數(shù)據(jù)集的大小對(duì)通信時(shí)間影響輕微，定義通信時(shí)間為t。然后，可以算出CApriori連接步的時(shí)間復(fù)雜度，如式(3)所示。

(3)

基于MapReduce的CApriori算法產(chǎn)生頻繁項(xiàng)集的具體實(shí)現(xiàn)流程如下：

(1)對(duì)事物數(shù)據(jù)進(jìn)行水平分割。InputFormat將事務(wù)數(shù)據(jù)庫(kù)DB水平劃分為n個(gè)規(guī)模相當(dāng)?shù)臄?shù)據(jù)塊，并將n個(gè)數(shù)據(jù)塊格式化為對(duì)(key為事務(wù)編號(hào)，value為該事務(wù)所包含的項(xiàng)集)，然后把數(shù)據(jù)塊發(fā)送到m個(gè)節(jié)點(diǎn)。

(2)運(yùn)行Map程序，通過(guò)掃描每個(gè)數(shù)據(jù)塊，將輸入的鍵值對(duì)轉(zhuǎn)換成<項(xiàng)，支持度>格式。Map函數(shù)先找出頻繁1-項(xiàng)集。

(3)為了減少節(jié)點(diǎn)間的通信量，編寫Combiner[14]將Map階段本地輸出的不同數(shù)據(jù)塊有相同候選集的支持度進(jìn)行合并，減少輸出中間結(jié)果的數(shù)據(jù)量，降低網(wǎng)絡(luò)延時(shí)，增加傳輸效率。

(4)利用Reduce函數(shù)把滿足最小支持度的局部頻繁項(xiàng)集合并，對(duì)不滿足最小支持度的項(xiàng)進(jìn)行剪枝操作，生成全局候選頻繁項(xiàng)集。

(5)通過(guò)Reduce階段得到的頻繁項(xiàng)集并行產(chǎn)生候選集。把頻繁項(xiàng)集分割成若干份相同的數(shù)據(jù)塊，然后調(diào)用Mapper接口對(duì)每個(gè)數(shù)據(jù)塊進(jìn)行Map函數(shù)處理。通過(guò)Map函數(shù)對(duì)數(shù)據(jù)塊的處理，把頻繁項(xiàng)集變換成鍵值對(duì)，Map函數(shù)獨(dú)自處理輸入的數(shù)據(jù)塊；然后具有相同鍵的鍵值對(duì)會(huì)組合起來(lái)并將(key,values)傳遞給Reduce函數(shù)。每個(gè)Reduce函數(shù)得到的是從所有Map節(jié)點(diǎn)傳過(guò)來(lái)的具有相同的鍵的鍵值對(duì)。Reduce函數(shù)把鍵與值分開生成候選集。

(6)頻繁項(xiàng)集為空時(shí)停止整個(gè)過(guò)程，否則k=k+1循環(huán)步驟(3)～(5)。

3 實(shí) 驗(yàn)

3.1 實(shí)驗(yàn)環(huán)境

選取11臺(tái)計(jì)算機(jī)在Linux環(huán)境下建立Hadoop集群，Hadoop平臺(tái)版本為2.2，操作系統(tǒng)均采用Ubuntu12.04，JDK版本為Sun JDK1.7。一臺(tái)計(jì)算機(jī)作為Master和JobTracker服務(wù)節(jié)點(diǎn)，其他10臺(tái)計(jì)算機(jī)作為Slave TaskTracker服務(wù)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)的處理器為Intel酷睿i5，4 GB內(nèi)存。使用某超市銷售數(shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù)集，共1 025 840條事務(wù)，有50個(gè)不同的項(xiàng)，其中最長(zhǎng)的事務(wù)有40項(xiàng)。基于MapReduce對(duì)CApriori算法和Apriori算法在數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)操作，通過(guò)實(shí)驗(yàn)數(shù)據(jù)說(shuō)明了CApriori算法性能的優(yōu)越性。

3.2 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)一：首先設(shè)置支持度為0.5%，數(shù)據(jù)集大小為1 025 840條事務(wù)，觀察CApriori算法和Apriori算法在不同數(shù)目節(jié)點(diǎn)上運(yùn)行的時(shí)間，如圖2所示。

圖2 兩種算法在不同節(jié)點(diǎn)下的運(yùn)行時(shí)間

從圖2中可以看出：當(dāng)計(jì)算機(jī)節(jié)點(diǎn)數(shù)目相同時(shí)，CApriori算法比Apriori算法運(yùn)行時(shí)間短，體現(xiàn)了CApriori算法的優(yōu)越性。當(dāng)計(jì)算機(jī)節(jié)點(diǎn)數(shù)目增加時(shí)，計(jì)算所需的時(shí)間減少。這是因?yàn)镸apReduce把數(shù)據(jù)劃分成片分布到不同的服務(wù)器節(jié)點(diǎn)上，并行執(zhí)行算法，提高了運(yùn)行效率。但是隨著節(jié)點(diǎn)數(shù)的增加，再增加節(jié)點(diǎn)數(shù)對(duì)減少運(yùn)行時(shí)間已沒(méi)有多大幫助，最終會(huì)使系統(tǒng)性能達(dá)到瓶頸。

實(shí)驗(yàn)二：在10臺(tái)計(jì)算機(jī)集群上處理1 025 840條事務(wù)集，設(shè)置支持度為0.4，0.5，0.6，0.7，結(jié)果如圖3所示。

從圖3中可以看出，支持度越小，CApriori算法比Apriori算法的效率越高。這是由于支持度越小挖掘過(guò)程中會(huì)產(chǎn)生更多候選集，Apriori算法自連接消耗更多時(shí)間。在數(shù)據(jù)集很大且支持度很低的情況下，傳統(tǒng)并行Apriori算法會(huì)出現(xiàn)死機(jī)現(xiàn)象。

圖3 兩種算法在不同支持度下的運(yùn)行時(shí)間

實(shí)驗(yàn)三：為了便于觀察實(shí)驗(yàn)改進(jìn)效果，選取十萬(wàn)個(gè)數(shù)據(jù)集為基數(shù)，設(shè)置支持度為0.5%，在10臺(tái)計(jì)算機(jī)集群上挖掘不同大小數(shù)據(jù)塊，結(jié)果如圖4所示。

圖4 兩種算法在不同數(shù)量集下的運(yùn)行時(shí)間

從圖4中可以看出，在數(shù)據(jù)規(guī)模較小時(shí)，CApriori算法的平均效率低于傳統(tǒng)并行Apriori算法。這是由于剪枝步分布式計(jì)算中對(duì)節(jié)點(diǎn)的管理和分配增加了額外的計(jì)算開銷，在事務(wù)規(guī)模較小的時(shí)候這個(gè)開銷占了主要運(yùn)行時(shí)間。隨著項(xiàng)目集的增加，傳統(tǒng)并行Apriori算法的時(shí)間消耗迅速上升，遠(yuǎn)大于CApriori算法，體現(xiàn)了CApriori算法的優(yōu)越性。這是因?yàn)閭鹘y(tǒng)并行Apriori算法在計(jì)算候選項(xiàng)集時(shí)使用串行自連接方法，尤其在處理海量數(shù)據(jù)集時(shí)，自連接產(chǎn)生的候選集的數(shù)量非常大，大大增加了MapReduce處理時(shí)間。而CApriori算法，通過(guò)并行的Map，Reduce過(guò)程來(lái)產(chǎn)生下一輪的候選集，其大大減少了MapReduce處理時(shí)間。

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

文中提出一種基于MapReduce的Apriori算法的并行化改進(jìn)算法CApriori。在現(xiàn)有的并行Apriori算法的基礎(chǔ)上，頻繁k-項(xiàng)集Ck通過(guò)并行的Map，Reduce過(guò)程來(lái)得出下一輪的候選集Ck+1。實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)Apriori算法計(jì)算頻繁項(xiàng)集執(zhí)行時(shí)間相比，CApriori執(zhí)行速度快，明顯提高了挖掘效率。

[1]HippJ,GüntzerU,NakhaeizadehG.Algorithmsforassociationrulemining-ageneralsurveyandcomparison[J].ACMSIGKDDExplorationsNewsletter,2000,2(1):58-64.

[2] 羅 丹,李陶深.一種基于壓縮矩陣的Apriori算法改進(jìn)研究[J].計(jì)算機(jī)科學(xué),2013,40(12):75-80.

[3]AgrawalR,ShaferJC.Parallelminingofassociationrules[J].IEEETransactionsonKnowledge&DataEngineering,1996,8(6):962-969.

[4] 劉 鵬.云計(jì)算[M].第2版.北京:北京工業(yè)大學(xué)出版社,2011.

[5]LiL,ZhangM.Thestrategyofminingassociationrulebasedoncloudcomputing[C]//Internationalconferenceonbusinesscomputingandglobalinformatization.Shanghai:IEEE,2011:475-478.

[6] 張 圣.一種基于云計(jì)算的關(guān)聯(lián)規(guī)則Apriori算法[J].通信技術(shù),2011,44(6):141-143.

[7] 朱安柱.基于Hadoop的Apriori算法改進(jìn)與移植的研究[D].武漢:華中科技大學(xué),2012.

[8]AgrawalR,ImielinskiT,SwamiA.Databasemining:aperformanceperspective[J].IEEETransactionsonKnowledgeandDataEngineering,1993,5(6):914-925.

[9] 張 震,汪斌強(qiáng),陳庶樵,等.基于多維計(jì)數(shù)型布魯姆過(guò)濾器的大流檢測(cè)機(jī)制[J].電子與信息學(xué)報(bào),2010,32(7):1608-1613.

[10] 張建勛,古志民,鄭 超.云計(jì)算研究進(jìn)展綜述[J].計(jì)算機(jī)應(yīng)用研究,2010,27(2):429-433.

[11] 孫芬芬.海量數(shù)據(jù)并行挖掘技術(shù)研究[D].北京:北京交通大學(xué),2014.

[12] 章志剛.云計(jì)算環(huán)境下頻繁項(xiàng)目集挖掘算法研究[D].南京:南京師范大學(xué),2014.

[13] 王 鄂,李 銘.云計(jì)算下的海量數(shù)據(jù)挖掘研究[J].現(xiàn)代計(jì)算機(jī),2009(11):22-25．

[14] 李玲娟,張 敏.云計(jì)算環(huán)境下關(guān)聯(lián)規(guī)則挖掘算法的研究[J].計(jì)算機(jī)技術(shù)與發(fā)展,2011,21(2):43-46.

Parallel Improvement of Apriori Algorithm Based on MapReduce

QIN Jun1,HAO Tian-shu2,DONG Qian-qian2

(1.College of Education Science & Technology,Nanjing University of Posts and Telecommunications,Nanjing 210003,China;2.College of Computer,Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

The parallel Apriori algorithm based on the MapReduce solves the problem that the traditional Apriori algorithm scans database for many times,but the candidates are still generated from the connection of serial by the frequent itemsets and generate a large number of data.In order to improve the efficiency of mining frequent itemsets for Apriori,an improved parallel Apriori algorithm named CApriori is proposed in large data environment,which realizes parallel candidate generation steps under MapReduce framework.The new algorithm generates thek+1candidateitemsetsfromkfrequentitemsetsthroughtheprocessofMapandReduce,whichmakesthewholeprocessofgeneratingfrequentitemsetsinparallel,reducingthenumberofcandidatesets,savingstoragespaceandtimeoverhead.OnanalysisofthetimecomplexityofCApriorialgorithmandApriorialgorithm,itindicatesthatCApriorialgorithmreducesthetimeconsumedwhenconnectedindealingwithlarge-scaledata.CAprioriisexecutedonHadoopplatformandtheresultsshowthattheimprovedalgorithminbigdataenvironmentandsmallersupportismoreefficient,andcanobtainexcellentacceleration.

association rules;data mining;MapReduce;Apriori

2016-04-27

2016-08-17

時(shí)間：2017-02-17

江蘇省自然科學(xué)基金項(xiàng)目(BK20130882)

秦 軍(1955-)，女，教授，研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)技術(shù)、多媒體技術(shù)、數(shù)據(jù)庫(kù)技術(shù)；郝天曙(1991-)，男，碩士研究生，研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)技術(shù)、云計(jì)算。

http://www.cnki.net/kcms/detail/61.1450.TP.20170217.1632.070.html

TP

A

1673-629X(2017)04-0064-05

10.3969/j.issn.1673-629X.2017.04.015