劉木林，朱慶華

(南京大學(xué) 信息管理學(xué)院，江蘇 南京 210023)

基于Hadoop的關(guān)聯(lián)規(guī)則挖掘算法研究
——以Apriori算法為例

劉木林，朱慶華

(南京大學(xué) 信息管理學(xué)院，江蘇 南京 210023)

為了解決傳統(tǒng)關(guān)聯(lián)規(guī)則挖掘算法在挖掘效率、算法擴(kuò)展性等方面無(wú)法適應(yīng)大數(shù)據(jù)挖掘需求的問(wèn)題，以經(jīng)典的關(guān)聯(lián)規(guī)則挖掘算法—Apriori算法為例，首先基于Hadoop平臺(tái)和MapReduce編程模型，實(shí)現(xiàn)算法的并行化。在此基礎(chǔ)上，基于事務(wù)縮減的思想對(duì)算法進(jìn)行優(yōu)化，進(jìn)一步提高算法的挖掘效率。搭建Hadoop集群環(huán)境，對(duì)算法的挖掘結(jié)果和挖掘效率進(jìn)行實(shí)驗(yàn)。通過(guò)并行挖掘結(jié)果驗(yàn)證、串行版與并行版效率對(duì)比、挖掘時(shí)間與節(jié)點(diǎn)數(shù)目的變化關(guān)系、挖掘時(shí)間與數(shù)據(jù)量的變化關(guān)系4組實(shí)驗(yàn)，結(jié)果表明：文中實(shí)現(xiàn)的Apriori算法不僅能夠準(zhǔn)確挖掘頻繁項(xiàng)集，而且比傳統(tǒng)串行算法具有更高的挖掘性能和可擴(kuò)展性。該算法能夠更好地適應(yīng)大數(shù)據(jù)集的挖掘要求，能夠?qū)崿F(xiàn)從大規(guī)模數(shù)據(jù)集中高效挖掘頻繁項(xiàng)集和關(guān)聯(lián)規(guī)則。

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

0 引 言

關(guān)聯(lián)規(guī)則是指存在于兩個(gè)或多個(gè)變量之間的一類重要的能被發(fā)現(xiàn)的規(guī)律性，這種規(guī)律性往往對(duì)實(shí)際的生產(chǎn)生活有著重要的指導(dǎo)作用，因此關(guān)聯(lián)規(guī)則挖掘一直都是數(shù)據(jù)挖掘的一個(gè)重要方面。隨著大數(shù)據(jù)時(shí)代的來(lái)臨，傳統(tǒng)的關(guān)聯(lián)規(guī)則挖掘算法已難以滿足大數(shù)據(jù)量的挖掘需求。Hadoop平臺(tái)是在大數(shù)據(jù)背景下誕生的分布式計(jì)算平臺(tái)。Hadoop的工作方式是并行的，通過(guò)并行提高處理效率。因此將傳統(tǒng)挖掘算法的思想基于Hadoop平臺(tái)實(shí)現(xiàn)，使得傳統(tǒng)關(guān)聯(lián)規(guī)則算法能夠適應(yīng)大規(guī)模數(shù)據(jù)集的處理要求，同時(shí)借助Hadoop平臺(tái)在分布式處理方面的優(yōu)勢(shì)，獲得處理性能方面的提升無(wú)疑是很有意義的，而這也正是文中研究的目的所在。

1 關(guān)聯(lián)規(guī)則算法研究現(xiàn)狀

1993年，Agrawal提出關(guān)聯(lián)規(guī)則挖掘后，關(guān)聯(lián)規(guī)則的挖掘算法就成為了研究的一個(gè)熱點(diǎn)，相繼出現(xiàn)了很多研究成果。其中最著名的包括Agrawal提出的Apriori算法[1]，這是布爾型關(guān)聯(lián)規(guī)則挖掘的基礎(chǔ)算法，此外Han等提出的改進(jìn)算法—FP-Growth算法[2]。隨著數(shù)據(jù)量的不斷積累，串行算法越來(lái)越難以滿足需要，因此Agrawal等又在1996年創(chuàng)造性地提出了并行的挖掘算法[3]。而Hadoop平臺(tái)誕生后，也有研究將關(guān)聯(lián)規(guī)則算法通過(guò)Hadoop平臺(tái)進(jìn)行移植和改進(jìn)。

表1總結(jié)了目前關(guān)聯(lián)規(guī)則算法研究的現(xiàn)狀。

表1 關(guān)聯(lián)規(guī)則算法研究現(xiàn)狀

從文獻(xiàn)調(diào)研中發(fā)現(xiàn)，基于Hadoop平臺(tái)實(shí)現(xiàn)關(guān)聯(lián)規(guī)則挖掘仍然主要基于Apriori和FP-Growth這兩種基礎(chǔ)算法，在實(shí)現(xiàn)并行化的基礎(chǔ)上，再采用優(yōu)化策略對(duì)算法進(jìn)行性能優(yōu)化。但是已有的研究在對(duì)算法進(jìn)行實(shí)驗(yàn)時(shí)，大都只專注于提高挖掘性能，并不注重對(duì)挖掘結(jié)果的驗(yàn)證和比較。基于這種情況，文中重點(diǎn)關(guān)注Apriori算法，首先將算法在Hadoop平臺(tái)上進(jìn)行實(shí)現(xiàn)，同時(shí)利用事務(wù)縮減思想對(duì)算法進(jìn)行改進(jìn)，在保證挖掘結(jié)果正確性的前提下，提高算法的挖掘性能和可擴(kuò)展性。

2 基于Hadoop的Apriori算法的實(shí)現(xiàn)與改進(jìn)

2.1 Hadoop平臺(tái)簡(jiǎn)介

Hadoop是基于主從結(jié)構(gòu)的架構(gòu)，集群中主要分為master節(jié)點(diǎn)和slave節(jié)點(diǎn)。整個(gè)平臺(tái)最核心的兩個(gè)部分是HDFS(Hadoop Distributed File System)和MapReduce。

HDFS是GFS(Google File System)的開(kāi)源實(shí)現(xiàn)，從架構(gòu)上看是一個(gè)主從體系結(jié)構(gòu)，以流式數(shù)據(jù)訪問(wèn)模式來(lái)存儲(chǔ)超大文件[28]。它的高容錯(cuò)性、高可擴(kuò)展性、高吞吐率與高獲得性等特點(diǎn)為大數(shù)據(jù)提供了可靠的存儲(chǔ)。而MapReduce則大大降低了并行編程的門檻，并行編程中的工作調(diào)度、負(fù)載均衡以及容錯(cuò)處理等問(wèn)題均由MapReduce框架負(fù)責(zé)。使用MapReduce框架編寫分布式并行程序時(shí)，只需要實(shí)現(xiàn)框架下的map()和reduce()函數(shù)即可。

2.2 Apriori算法的Hadoop實(shí)現(xiàn)

Apriori的Hadoop實(shí)現(xiàn)一般有兩種思路，筆者這里是通過(guò)迭代MapReduce的方法來(lái)實(shí)現(xiàn)，因?yàn)镠DFS默認(rèn)的數(shù)據(jù)分塊大小是64 MB，如果采取另一種思路來(lái)實(shí)現(xiàn)，則意味著每個(gè)節(jié)點(diǎn)都需要單獨(dú)處理64 MB的數(shù)據(jù)量，同時(shí)可能會(huì)產(chǎn)生數(shù)量龐大的局部頻繁項(xiàng)集。雖然Hadoop允許自定義文件塊的大小，但是這種更改會(huì)對(duì)Hadoop的可擴(kuò)展性、伸縮性以及并行性造成影響，并不值得提倡。實(shí)現(xiàn)后的程序流程圖見(jiàn)圖1。

圖1 并行后的程序流程圖

下面對(duì)程序?qū)崿F(xiàn)的關(guān)鍵細(xì)節(jié)進(jìn)行說(shuō)明。

(1)初始化過(guò)程。

挖掘頻繁項(xiàng)集首先需要確定實(shí)際的支持度計(jì)數(shù)，這要根據(jù)事務(wù)總數(shù)和輸入的支持度百分比來(lái)確定，但實(shí)驗(yàn)中是以文件代替數(shù)據(jù)庫(kù)來(lái)存儲(chǔ)事務(wù)集，因此需要通過(guò)一個(gè)單獨(dú)的Job來(lái)完成事務(wù)總數(shù)的統(tǒng)計(jì)，統(tǒng)計(jì)完成后再計(jì)算出最小支持度計(jì)數(shù)，并放入全局配置對(duì)象中。

(2)挖掘頻繁1項(xiàng)集。

挖掘頻繁1項(xiàng)集的過(guò)程類似于單詞計(jì)數(shù)過(guò)程，不同的是需要Reducer判斷每個(gè)條目的計(jì)數(shù)是否滿足最小支持度，并將滿足最小支持度的條目輸出，這個(gè)過(guò)程同樣需要主進(jìn)程新建一個(gè)Job。

(3)迭代挖掘頻繁k項(xiàng)集。

這一步是整個(gè)算法實(shí)現(xiàn)的核心。首先需要讀入上一步得出的頻繁1項(xiàng)集，進(jìn)行連接后產(chǎn)生候選2項(xiàng)集，由于候選2項(xiàng)集的產(chǎn)生無(wú)法進(jìn)行剪枝，因此只需要進(jìn)行連接步即可，然后再進(jìn)行候選2項(xiàng)集的支持度計(jì)數(shù)與篩選。隨后Mapper從全局配置對(duì)象中獲取候選2項(xiàng)集的路徑，然后將文件中的條目讀入放到內(nèi)存中。隨后在map函數(shù)中按行讀入每一條事務(wù)，并將包含于事務(wù)中的候選2項(xiàng)集輸出至Combiner中。Combiner先對(duì)本地相同key值的條目進(jìn)行匯總，將本地匯總結(jié)果輸出至Reducer中，Reducer對(duì)全部的結(jié)果進(jìn)行最終匯總，并且判斷條目的支持度計(jì)數(shù)是否滿足最小支持度計(jì)數(shù)，如果滿足，則將條目及其支持度輸出至HDFS。主進(jìn)程在Job完成之后，到對(duì)應(yīng)的上一次頻繁項(xiàng)集的輸出路徑中讀取k-1項(xiàng)頻繁項(xiàng)集，并且判斷k-1項(xiàng)頻繁項(xiàng)集是否為空，如果是，則結(jié)束挖掘，如果否，則對(duì)讀入的k-1項(xiàng)頻繁項(xiàng)集進(jìn)行自連接，并利用先驗(yàn)性質(zhì)進(jìn)行剪枝，隨后開(kāi)始一個(gè)Job對(duì)候選頻繁項(xiàng)集進(jìn)行支持度計(jì)數(shù)，并且不斷迭代這個(gè)過(guò)程，直到產(chǎn)生的頻繁項(xiàng)集為空。

2.3 基于事務(wù)縮減的算法改進(jìn)策略

上節(jié)敘述了Apriori算法在Hadoop平臺(tái)上實(shí)現(xiàn)的基本思路，在這一思路中將數(shù)據(jù)庫(kù)的掃描過(guò)程實(shí)現(xiàn)了并行化，而數(shù)據(jù)庫(kù)掃描是Apriori算法的主要瓶頸之一。在基本實(shí)現(xiàn)的基礎(chǔ)上，還可以對(duì)算法的實(shí)現(xiàn)進(jìn)行改進(jìn)。表1中分析了Apriori算法的兩處性能瓶頸，對(duì)于問(wèn)題二，文中算法在主程序產(chǎn)生候選項(xiàng)集的過(guò)程中應(yīng)用了先驗(yàn)剪枝，對(duì)于候選項(xiàng)集的數(shù)量產(chǎn)生了限制作用。而對(duì)于問(wèn)題一，文中進(jìn)一步采用事務(wù)縮減的思想來(lái)減少數(shù)據(jù)庫(kù)事務(wù)的掃描次數(shù)。事務(wù)縮減思想同樣基于頻繁項(xiàng)集的一種性質(zhì)即：不包含任何k-1項(xiàng)頻繁集的事務(wù)不可能包含k項(xiàng)頻繁集，因此在數(shù)據(jù)庫(kù)掃描過(guò)程中可以將這些事務(wù)進(jìn)行標(biāo)記，從而減少需要掃描的事務(wù)數(shù)目，提高挖掘效率。而文中利用了與此相似的另外一種性質(zhì)即：不包含任何候選k項(xiàng)集的事務(wù)不可能包含任何k項(xiàng)頻繁集。

基于事務(wù)縮減的算法改進(jìn)策略需要解決的第一個(gè)問(wèn)題就是如何唯一地標(biāo)識(shí)每一條事務(wù)記錄。在HDFS中，每個(gè)文件都會(huì)以64MB的塊為單位進(jìn)行存儲(chǔ)，每個(gè)塊都有一個(gè)唯一的URL。此外，在MapReduce執(zhí)行過(guò)程中，每個(gè)Mapper都需要單獨(dú)處理一個(gè)split(split與HDFS中的block是相對(duì)應(yīng)的)，采用按行讀入事務(wù)記錄的方式時(shí)，key值為該行記錄在文件中的偏移字節(jié)數(shù)，對(duì)于該記錄而言，此key值可以作為其在該split中的唯一標(biāo)識(shí)。這樣，由split的URL加該事務(wù)記錄的key值便可以將其唯一地標(biāo)識(shí)出來(lái)。按照該策略，改進(jìn)的重點(diǎn)就在Mapper的執(zhí)行邏輯中。即Mapper首先需要獲取split的URL，存入Mapper中的一個(gè)成員變量。同時(shí)根據(jù)split的URL，根據(jù)約定的路徑找到存儲(chǔ)其剔除列表的文件，并將剔除列表讀入一個(gè)HashSet中。map函數(shù)對(duì)候選項(xiàng)集計(jì)數(shù)時(shí)，如果發(fā)現(xiàn)該條事務(wù)不包含任何候選項(xiàng)集，則將其加入最新的剔除列表。最后在Mapper的cleanup函數(shù)中將新的剔除列表附加到剔除文件中，以供下一次掃描時(shí)使用。

筆者在測(cè)試中發(fā)現(xiàn)，采用事務(wù)縮減進(jìn)行改進(jìn)后，在挖掘頻繁3項(xiàng)集時(shí)可以剔除約5%的事務(wù)，4項(xiàng)集時(shí)可以剔除約10%的事務(wù)，5項(xiàng)集時(shí)可以剔除約17%的事務(wù)，6項(xiàng)集時(shí)可以剔除約25%的事務(wù)。因此，隨著挖掘的不斷進(jìn)行，剔除的事務(wù)量會(huì)不斷增多，挖掘效率的提升也更加明顯。

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

3.1 Hadoop分布式環(huán)境搭建

為了進(jìn)行實(shí)驗(yàn)，筆者搭建了一個(gè)小型的集群環(huán)境，包括1個(gè)master節(jié)點(diǎn)和2個(gè)slave節(jié)點(diǎn)(節(jié)點(diǎn)計(jì)算機(jī)配置如表2所示)，namenode、jobtracker均位于master節(jié)點(diǎn)，datanode、tasktracker均位于slave節(jié)點(diǎn)，3個(gè)節(jié)點(diǎn)統(tǒng)一使用JDK1.7.0_45版本，Hadoop版本則為1.2.1。

表2 集群節(jié)點(diǎn)配置情況

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

實(shí)驗(yàn)采用的數(shù)據(jù)為FIMI Repository(Frequent Itemset Mining Implementations Repository，該網(wǎng)站提供大量IEEE國(guó)際數(shù)據(jù)挖掘大會(huì)上關(guān)于頻繁項(xiàng)集挖掘方面的數(shù)據(jù)集、論文、實(shí)驗(yàn)結(jié)果等資料)提供的一份webdocs事務(wù)數(shù)據(jù)集，該數(shù)據(jù)是由意大利國(guó)家研究理事會(huì)的Claudio Lucchese等通過(guò)Web爬蟲爬取了170萬(wàn)Web文檔后，通過(guò)初步清理(取出html標(biāo)簽)和分詞，并通過(guò)詞干提取算法，獲得了出現(xiàn)在文檔中的所有單詞的事務(wù)集(同一個(gè)文檔中一個(gè)單詞只計(jì)1次，并將相應(yīng)的單詞轉(zhuǎn)換為數(shù)字id來(lái)表示)。文件大小為1.4 GB，包含169萬(wàn)條事務(wù)集，其中最長(zhǎng)的事務(wù)集約包含7萬(wàn)個(gè)條目。為了方便實(shí)驗(yàn)的進(jìn)行，在原文件的基礎(chǔ)上，將文件分割成50 MB，100 MB，150 MB，200 MB，250 MB，300 MB，500 MB，750 MB，1 GB，1.4 GB等分塊。另外，筆者利用Java語(yǔ)言實(shí)現(xiàn)了單機(jī)串行版的Apriori算法(以下簡(jiǎn)稱串行版)，并將串行版與并行算法的效率進(jìn)行對(duì)比，其中串行版程序都運(yùn)行在slave1節(jié)點(diǎn)上，實(shí)驗(yàn)共分為3組進(jìn)行，每次實(shí)驗(yàn)都運(yùn)行3次取平均值。

(1)并行挖掘結(jié)果驗(yàn)證。

挖掘結(jié)果的驗(yàn)證主要通過(guò)串行程序與并行程序挖掘結(jié)果的對(duì)比來(lái)展示，如果并行程序的挖掘結(jié)果與串行程序的一致，則說(shuō)明筆者實(shí)現(xiàn)的并行算法是可靠的，反之則說(shuō)明并行算法的設(shè)計(jì)與實(shí)現(xiàn)存在問(wèn)題，無(wú)法得出正確的挖掘結(jié)果。

表3顯示了150 M文件的挖掘結(jié)果；表4顯示了250 M文件的挖掘結(jié)果(FIM1代表頻繁項(xiàng)集1項(xiàng)集，其他的依此類推)。

表3 150 M文件挖掘結(jié)果

表4 250 M文件挖掘結(jié)果

從表中可以看出，串行算法與并行算法挖掘出的頻繁項(xiàng)集的數(shù)目是一致的，另外，筆者對(duì)比了從頻繁1項(xiàng)集到頻繁5項(xiàng)集的具體挖掘結(jié)果，均完全一致。因此，文中提出的并行挖掘算法是可靠的，能夠準(zhǔn)確挖掘出滿足最小支持度的頻繁項(xiàng)集。

(2)串行版與并行版效率對(duì)比。

分別利用串行版程序與并行版程序?qū)Υ笮?0 MB，100 MB，150 MB，200 MB，250 MB，300 MB，350 MB，400 MB，450 MB，500 MB的數(shù)據(jù)進(jìn)行挖掘，最小支持度設(shè)為0.25，實(shí)驗(yàn)結(jié)果見(jiàn)圖2。

圖2 串行版與并行版效率對(duì)比

從圖中可以看出，在數(shù)據(jù)量較小時(shí)，并行算法由于在工作調(diào)度等方面的開(kāi)銷，并沒(méi)有體現(xiàn)出挖掘效率的優(yōu)勢(shì)。而隨著數(shù)據(jù)量的不斷積累，并行算法的優(yōu)勢(shì)逐漸體現(xiàn)出來(lái)，挖掘時(shí)間也大大少于串行算法。更重要的是，串行算法在挖掘500 MB以上的數(shù)據(jù)量時(shí)，內(nèi)存不足等方面的限制會(huì)導(dǎo)致運(yùn)行失敗，除非繼續(xù)改進(jìn)單機(jī)的配置，否則無(wú)法繼續(xù)挖掘更大的數(shù)據(jù)，而并行算法則不存在這樣的問(wèn)題。

(3)挖掘時(shí)間與節(jié)點(diǎn)數(shù)目的變化關(guān)系。

筆者搭建的集群共有3臺(tái)計(jì)算機(jī)，其中配置較好的一臺(tái)即作為NameNode、JobTracker，也作為DataNode、TaskTracker。分別將集群調(diào)整為1個(gè)節(jié)點(diǎn)、2個(gè)節(jié)點(diǎn)、3個(gè)節(jié)點(diǎn)，并對(duì)300 M的數(shù)據(jù)進(jìn)行挖掘，設(shè)最小支持度為0.25，實(shí)驗(yàn)結(jié)果見(jiàn)圖3。

圖3 挖掘時(shí)間與節(jié)點(diǎn)數(shù)目的變化關(guān)系

從圖中可以看出，計(jì)算節(jié)點(diǎn)的增大能夠明顯提高挖掘效率，這也是分布式計(jì)算可擴(kuò)展性方面的最大優(yōu)勢(shì)之一，即通過(guò)節(jié)點(diǎn)的靈活配置，可以很輕松地應(yīng)對(duì)大數(shù)據(jù)的處理。

(4)挖掘時(shí)間與數(shù)據(jù)量的變化關(guān)系。

采用并行版程序分別挖掘大小為100 MB，200 MB，300 MB，400 MB，500 MB，600 MB，700 MB，800 MB，900 MB，1 000 MB，1 100 MB，1 200 MB，1 300 MB，1 400 MB的數(shù)據(jù)集，設(shè)置最小支持度為0.25，觀察隨著數(shù)據(jù)量的增加挖掘時(shí)間的變化情況，實(shí)驗(yàn)結(jié)果如圖4所示。

圖4 挖掘時(shí)間與數(shù)據(jù)量的變化關(guān)系

從圖中可以看出，隨著挖掘數(shù)據(jù)量的不斷增長(zhǎng)，挖掘時(shí)間的增長(zhǎng)速度低于線性增長(zhǎng)速度，并且接近于對(duì)數(shù)增長(zhǎng)速度，而圖3中的普通串行算法的挖掘時(shí)間會(huì)因數(shù)據(jù)量的增加而迅速增長(zhǎng)，說(shuō)明文中算法對(duì)于數(shù)據(jù)量的增長(zhǎng)有著更好的適應(yīng)性。如果結(jié)合計(jì)算節(jié)點(diǎn)的適當(dāng)擴(kuò)展，完全能夠適應(yīng)更大數(shù)據(jù)量的挖掘要求。

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

文中通過(guò)Hadoop平臺(tái)實(shí)現(xiàn)了Apriori算法的并行化，通過(guò)事務(wù)集的并行掃描大大提高了算法的執(zhí)行效率，同時(shí)為了減少數(shù)據(jù)庫(kù)的掃描消耗，運(yùn)用事務(wù)縮減思想優(yōu)化算法實(shí)現(xiàn)，進(jìn)一步提高了算法效率。經(jīng)過(guò)一系列的實(shí)驗(yàn)表明，文中實(shí)現(xiàn)的并行Apriori算法在保證挖掘結(jié)果準(zhǔn)確的前提下，比普通串行挖掘具有更少的時(shí)間消耗，能夠更快速地挖掘出頻繁項(xiàng)集，同時(shí)從實(shí)驗(yàn)中看出，并行算法對(duì)數(shù)據(jù)量的不斷增長(zhǎng)有著更好的適應(yīng)能力，對(duì)于大文件也有著很好的挖掘性能。此外，實(shí)驗(yàn)結(jié)果還表明，計(jì)算節(jié)點(diǎn)的增加同樣能夠提高挖掘效率，這也是分布式集群系統(tǒng)的最大威力所在。綜合來(lái)看，文中的研究能夠?yàn)榇髷?shù)據(jù)條件下關(guān)聯(lián)規(guī)則的高效挖掘提供借鑒意義。當(dāng)然，目前也還存在一些不足，比如最小支持度的變化對(duì)算法性能的影響比較明顯，特別在頻繁2項(xiàng)集的挖掘上，因?yàn)橄闰?yàn)剪枝無(wú)法對(duì)候選2項(xiàng)集的產(chǎn)生進(jìn)行限制，同時(shí)文中提出的事務(wù)縮減思想同樣也無(wú)法提高頻繁2項(xiàng)集的挖掘效率。因此，下一步的研究重點(diǎn)主要是如何利用哈希散列的方式來(lái)限制候選2項(xiàng)集的產(chǎn)生，進(jìn)一步提高算法的效率。

[1] Agrawal R,Srikant R.Fast algorithms for mining association rules[C]//Proceedings of the 20th VLDB conference.Santiago,Chile:[s.n.],1994:487-499.

[2] Han J,Pei J,Yin Y.Mining frequent patterns without candidate generation[J].ACM SIGMOD Record,2000,29(2):1-12.

[3] Agrawal R,Shafer J C.Parallel mining of association rules[J].IEEE Transactions on Knowledge and Data Engineering,1996,8(6):962-969.

[4] Zaki M J.Scalable algorithms for association mining[J].IEEE Transactions on Knowledge and Data Engineering,2000,12(3):372-390.

[5] Park J S,Chen M S,Yu P S.An effective hash-based algorithm for mining association rules[J].ACM SIGMOD Record,1995,24(2):175-186.

[6] Sarasere A,Omiecinsky E,Navathe S.An efficient algorithm for mining association rules in large databases[C]//Proc of 21st international conference on very large databases.Zurich,Switzerland:[s.n.],1995.

[7] Toivonen H. Sampling large databases for association rules[C]//Proc of conference on very large data bases.[s.l.]:[s.n.],1999:134-145.

[8] 孫逢嘯,倪世宏,謝 川.一種基于矩陣的Apriori改進(jìn)算法[J].計(jì)算機(jī)仿真,2013,30(8):245-249.

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

[10] 高海洋,沈 強(qiáng),張軒溢,等.一種基于數(shù)據(jù)壓縮的Apriori算法[J].計(jì)算機(jī)工程與應(yīng)用,2013,49(14):117-120.

[11] 楊 云,羅艷霞.FP-Growth算法的改進(jìn)[J].計(jì)算機(jī)工程與設(shè)計(jì),2010,31(7):1506-1509.

[12] 張玉芳,熊忠陽(yáng),耿曉斐,等.Eclat算法的分析及改進(jìn)[J].計(jì)算機(jī)工程,2010,36(23):28-30.

[13] 馮培恩,劉 嶼,邱清盈,等.提高Eclat算法效率的策略[J].浙江大學(xué)學(xué)報(bào):工學(xué)版,2013,47(2):223-230.

[14] Za?ane O R,El-Hajj M,Lu P.Fast parallel association rule mining without candidacy generation[C]//Proceedings IEEE international conference on data mining.[s.l.]:IEEE,2001:665-668.

[15] Park J S,Chen M S,Yu P.Efficient parallel data mining for association rules[C]//Pissinou N,Silberschatz A,Park E K,et al.Proceedings of the fourth international conference on information and knowledge management.New York,NY,USA:ACM,1995:31-36.

[16] Cheung D W,Han J,Ng V T,et al.A fast distributed algorithm for mining association rules[C]//Proc of fourth international conference on parallel and distributed information systems.[s.l.]:IEEE,1996:31-42.

[17] Yang X Y,Liu Z,Fu Y.MapReduce as a programming model for association rules algorithm on Hadoop[C]//Proc of 3rd international conference on information sciences and interaction sciences.[s.l.]:IEEE,2010:99-102.

[18] Li N,Zeng L,He Q,et al.Parallel implementation of Apriori algorithm based on MapReduce[C]//Proc of 13th ACIS international conference on software engineering,artificial intelligence,networking and parallel & distributed computing.[s.l.]:IEEE,2012:236-241.

[19] Lin M Y,Lee P Y,Hsueh S C.Apriori-based frequent itemset mining algorithms on MapReduce[C]//Proceedings of the 6th international conference on ubiquitous information management and communication.[s.l.]:ACM,2012.

[20] Li L,Zhang M.The strategy of mining association rule based on cloud computing[C]//Proc of international conference on business computing and global informatization.[s.l.]:IEEE,2011:475-478.

[21] Woo J.Apriori-Map/Reduce algorithm[C]//Proc of the 2012 international conference on parallel and distributed processing techniques and applications.Las Vegas:[s.n.],2012.

[22] 章志剛,吉根林.基于迭代式MapReduce的Apriori算法設(shè)計(jì)與實(shí)現(xiàn)[J].華中科技大學(xué)學(xué)報(bào):自然科學(xué)版,2012(S1):9-12.

[23] 黃立勤,柳燕煌.基于MapReduce并行的Apriori算法改進(jìn)研究[J].福州大學(xué)學(xué)報(bào):自然科學(xué)版,2011,39(5):680-685.

[24] 范燕燕.基于MapReduce的分布式關(guān)聯(lián)規(guī)則挖掘算法研究[D].哈爾濱:哈爾濱工程大學(xué),2013.

[25] Yong W,Zhe Z,Fang W.A parallel algorithm of association rules based on cloud computing[C]//Proc of 8th international ICST conference on communications and networking in China.[s.l.]:IEEE,2013:415-419.

[26] Zhou L,Zhong Z,Chang J,et al.Balanced parallel FP-growth with MapReduce[C]//Proc of IEEE youth conference on information computing and telecommunications.Beijing:IEEE,2010:243-246.

[27] 周詩(shī)慧.基于Hadoop的改進(jìn)的并行Fp-Growth算法[D].濟(jì)南:山東大學(xué),2013.

[28] White T.Hadoop:the definitive guide[M].3rd ed.USA:O'Reillv Media,2012.

Research on Association Rules Mining Algorithm Based on Hadoop—Taking Apriori as an Example

LIU Mu-lin，ZHU Qing-hua

(School of Information Management，Nanjing University，Nanjing 210023，China)

In order to solve the problem that the traditional association rules mining algorithm has been unable to meet the mining needs of large amount of data in the aspect of efficiency and scalability,take Apriori as an example,the algorithm is realized in the parallelization based on Hadoop framework and MapReduce model.On the basis,it is improved using the transaction reduce method for further enhancement of the algorithm’s mining efficiency.The experiment,which consists of verification of parallel mining results,comparison on efficiency between serials and parallel,variable relationship between mining time and node number and between mining time and data amounts,is carried out in the mining results and efficiency by Hadoop clustering.Experiments show that the paralleled Apriori algorithm implemented is able to accurately mine frequent item sets,with a better performance and scalability.It can be better to meet the requirements of big data mining and efficiently mine frequent item sets and association rules from large dataset.

data mining;association rules;Hadoop;Apriori

2015-08-13

2015-11-18

時(shí)間：2016-06-22

國(guó)家自科基金面上項(xiàng)目(71473114)

劉木林(1991-)，男，碩士研究生，通訊作者，研究方向?yàn)榛ヂ?lián)網(wǎng)用戶行為分析；朱慶華，教授，博士生導(dǎo)師，研究方向?yàn)榫W(wǎng)絡(luò)信息資源管理、信息用戶行為、信息政策分析、決策咨詢服務(wù)等。

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

TP393

A

1673-629X(2016)07-0001-05

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