PFPonCanTree：一種基于MapReduce的并行頻繁模式增量挖掘算法*

肖 文，胡 娟，周曉峰

(河海大學文天學院,安徽 馬鞍山 243000)

1 引言

頻繁模式挖掘是最重要的數(shù)據(jù)挖掘任務之一，也是很多數(shù)據(jù)挖掘任務的基礎性任務，自從它被提出以來[1]，受到了越來越多研究者的關注。頻繁模式挖掘的目的是發(fā)現(xiàn)事務數(shù)據(jù)中頻繁出現(xiàn)的模式，從而發(fā)現(xiàn)事物項之間存在的隱含關聯(lián)。已經提出的頻繁模式挖掘算法大致可以分為三類：第一類是通過迭代產生候選頻繁模式并對它們分別進行計數(shù)，將模式的支持度與最小支持度比較來獲得頻繁模式，典型的算法是Apriori[2]及其一系列的改進算法；第二類是不產生候選模式，通過將數(shù)據(jù)集壓縮成一種特殊的數(shù)據(jù)結構(一般為樹結構)，在特定結構上進行遍歷來直接產生頻繁模式，典型的算法有FP-Growth[3]、LP-Tree[4]、FIUT[5]、IFP[6]、FPL/TPL[7]等；第三類是將水平格式的數(shù)據(jù)集轉換成垂直格式，通過交運算來得到頻繁模式，典型的算法有Eclat等。

上述列舉的頻繁模式挖掘算法都是基于被挖掘的數(shù)據(jù)集是“靜態(tài)的、不變的”這樣一個基本的假設，以“批處理”的方式對整個數(shù)據(jù)集進行挖掘。但是，在現(xiàn)實世界中，數(shù)據(jù)集卻是始終變化的，不斷有新的事務數(shù)據(jù)插入到數(shù)據(jù)集中，導致產生新的頻繁模式，或是使原來頻繁的模式不再頻繁。對于更新后的新數(shù)據(jù)集，如果仍以批處理的方式對其進行重新挖掘，其效率十分低下。在不斷變化的數(shù)據(jù)集中進行頻繁模式挖掘，需要充分利用前一階段的挖掘結果，以“增量挖掘”的方式進行，提高挖掘效率。

為實現(xiàn)頻繁模式的增量挖掘，研究者已經提出了一些解決的方法，如基于Apriori算法的增量挖掘算法FUP(Fast Update)[8]、FUP2(Fast Update 2)[9]、UWEP(UpdateWithEarly Pruning)[10]、GSP(Generalized Sequential Patterns)[11]、Pre-Large[12]等，基于樹結構的AFPIM(Adjusting Frequent Pattern Tree Structures)[13]、FELINE(基于CATS-Tree(Compressed & Arraged Transcation Sequence Tree)結構)[14]、CanTree(Canonical-order Tree)[15]、BIT(BatchIncremental Tree)[16]算法等。基于Apriori的增量挖掘算法雖然充分利用了對原始數(shù)據(jù)庫挖掘過程中產生的所有計數(shù)和挖掘結果，但仍需要迭代產生候選模式并進行多次計數(shù)，不適合大量數(shù)據(jù)集的增量挖掘任務。基于樹的增量挖掘方法雖然在一定程度上解決了增量挖掘的問題，但需要將所有數(shù)據(jù)以樹的形式存儲在內存中，對于存儲空間需求量很大。頻繁模式挖掘是一種計算、存儲密集型計算任務，在當前大數(shù)據(jù)時代，傳統(tǒng)增量挖掘算法無法滿足海量數(shù)據(jù)挖掘的需要，主要體現(xiàn)在：在單一計算機上無法存儲所需要挖掘的所有數(shù)據(jù)及挖掘過程中產生的中間結果，所需要的內存遠遠超過單一機器的存儲量，計算時間太長無法忍受等。需要開發(fā)分布式、并行的增量關聯(lián)規(guī)則挖掘算法解決大數(shù)據(jù)中頻繁模式增量挖掘的問題。

MapReduce是一種由Google提出的易用且功能強大的并行編程模型，具有使用簡單、自動容錯、負載均衡、伸縮性好等優(yōu)點，已經有了很多將傳統(tǒng)頻繁模式挖掘算法向MapReduce模型進行遷移的研究[17 - 36]，很大程度上解決了大數(shù)據(jù)中頻繁模式挖掘的問題。在MapReduce計算模型中，一個計算任務被分為Map和Reduce兩個方法。Map方法在多個結點上運行，處理一個或多個本地的數(shù)據(jù)分片；Reduce方法處理Map方法輸出的中間結果，也可以多個Reduce方法并行執(zhí)行；所有Reduce方法的輸出合并后得到最后的結果。MapReduce計算模型流程圖如圖1所示。

Figure 1 MapReduce parallel programming model圖1 MapReduce并行編程模型

Hadoop[37]是MapReduce的一個開源實現(xiàn)，同時提供了一個分布式文件系統(tǒng)HDFS(Hadoop Distribtued File System)。HDFS是一個用來存儲超大文件的文件系統(tǒng)，可以自動地對超大文件進行分片及負載均衡。HDFS將分片存儲在不同的結點上，同時在存儲分片的結點上執(zhí)行MapReduce計算任務，通過數(shù)據(jù)本地化、減少I/O來提高運行效率。一個Hadoop集群可以運行在普通的商用計算機上，包括一個Master結點和多個Slave結點。

本文主要貢獻為：

(1)提出了PFPonCanTree算法，將傳統(tǒng)頻繁模式增量挖掘算法CanTree向MapReduce計算模型進行了遷移，實現(xiàn)了并行、分布式的頻繁模式增量挖掘。

(2)設計了并行計算中各結點的負載均衡策略，使得每個結點計算量相對平衡，提高整個算法運行效率。

(3)對算法的執(zhí)行效率進行了定量分析，并通過實驗驗證了分析結果。

本文的組織如下：第2節(jié)對有關工作進行了綜述；第3節(jié)提出基于MapReduce計算模型的并行頻繁模式增量挖掘算法PFPonCanTree，并進行了效率分析；第4節(jié)介紹了實驗環(huán)境和方案，并對實驗結果進行了分析；第5節(jié)對全文進行了總結，并對下一步工作進行了展望。

2 問題定義與相關研究

2.1 問題描述與符號定義

設I={i1,i2,…,in}為項的集合；P是一個模式，P={i1,i2,…,in}?I，包含k個項的模式稱為k-模式；一個事務T的定義為T=(tid,X)，其中tid為事務標識，X為一個模式；一個事務數(shù)據(jù)庫D是多個T的集合。

模式Y在事務數(shù)據(jù)庫D中的支持度為D中包含模式Y事務的比例。定義為：

如果一個模式被稱為是頻繁的，則其支持度不小于用戶給定的一個閾值(σ),這個閾值也稱為最小支持度(min_sup)。頻繁模式具有單調特性，即：如果一個模式是頻繁的，則其所有子模式都是頻繁的。相應地，如果一個模式不是頻繁的，則其所有的超模式都是不頻繁的。

對于頻繁模式的增量挖掘問題，定義如表1所示的符號。

Table 1 Symbol description

增量挖掘，即是要充分利用對D的已有挖掘結果，對T進行分析挖掘，提高對U進行挖掘的效率。

2.2 FELINE(CATS-Tree)

Cheung等[14]于2003年設計了一種特殊的樹結構CATS-Tree用于實現(xiàn)增量模式挖掘。構造D的CATS-Tree只需要掃描數(shù)據(jù)集一次，依次將每一條事務T中的所有項插入樹中。在插入事務T時，從root節(jié)點開始，將T中的項和當前節(jié)點的每一個孩子比較，如果相同就合并，將當前節(jié)點改變?yōu)楹喜⒌墓?jié)點，并比較下一項；如果沒有相同的項，則將T中的項做為一條新的路徑插入CATS-Tree中。如果樹中一個節(jié)點的支持度比它的祖先高，則將它與其祖先交換，保證每一個節(jié)點的支持度都不大于它的祖先。構造CATS-Tree完成后，可以使用傳統(tǒng)的FP-Growth算法在CATS-Tree上進行頻繁模式挖掘。

雖然CATS-Tree具有構造簡單、保存了D中的所有信息、插入新事務方便等特點，但它存在兩個明顯的缺點：一是CATS-Tree的構造過程中存在搜索公共項，隨著局部支持度的變化交換和合并節(jié)點等操作，增加了額外的系統(tǒng)開銷；二是根據(jù)CATS-Tree的特點，在使用FP-Grwoth算法進行挖掘階段時從向上和向下兩個方向遍歷才能得到一個項的條件模式基，會造成大量的系統(tǒng)負載。

2.3 CanTree

為了克服CATS-Tree的缺點，Leung等[15]在2007年提出了CanTree。CanTree與CATS-Tree相同，也是將事務中的所有項都插入到樹中，但在插入事務之前，會將事務中的項按照一個預先定義的順序(可以為字典或字母表順序，也可以使用項的某一種屬性)進行排列，使得樹中的節(jié)點順序與局部支持度無關，不需要進行額外的交換操作，且大大減少了搜索公共項的系統(tǒng)消耗，并且獲得項的條件模式基只需要向上的順序進行遍歷，減小了系統(tǒng)負載。對于新插入的事務集，可使用上述方法很容易地將新事務插入樹中，實現(xiàn)增量挖掘。構造完CanTree后，也可以使用類似FP-Growth算法進行挖掘。Hoseini等在2015年提出了一種在CanTree上進行挖掘的新方法[38]，方法與FP-Growth類似，只不過在創(chuàng)建項的條件模式基時只選擇路徑上頻繁的項，減少了構造的條件樹的節(jié)點數(shù)。

從CanTree的特點來分析，它保存了D中的所有信息，插入新事務也非常方便，十分適合用于增量頻繁模式挖掘；構造CanTree只需要掃描D一次，且構造過程中沒有交換節(jié)點的額外操作，搜索公共項的效率也十分高，構造CanTree效率高；對Can-Tree挖掘的方法與FP-Growth類似，可以對所有項進行分組，將不同分組及組相關事務分發(fā)給不同的結點并行執(zhí)行，可以很方便地將CanTree的構造和挖掘移植到MapReduce計算模型及其開源實現(xiàn)平臺Hadoop上，通過并行化實現(xiàn)在大數(shù)據(jù)集中的頻繁模式增量挖掘。

2.4 PFP

Li等[24]在2010年提出了并行FP-Growth算法PFP，實現(xiàn)了將FP-Growth算法向MapReduce計算模型上的移植。PFP算法使用了三個MapReduce任務完成整個并行挖掘工作。使用HDFS將大數(shù)據(jù)進行自動分片，在第一個任務中對所有項進行并行計數(shù)，得到所有頻繁項的集合(FList)。將FList進行分組后得到組列表(GList)。第二個任務的主要目的是得到“組相關事務集”,即包含該組中項的所有事務的集合。每個Mapper啟動時，加載GList以及本結點所存儲的數(shù)據(jù)分片，輸出每一組相關聯(lián)的事務T，在Reduce階段進行合并，得到每一組相關聯(lián)的所有事務T的集合。第三個任務的Map函數(shù)對組及組相關聯(lián)事務使用傳統(tǒng)的FP-Growth算法進行挖掘，Reduce函數(shù)將所有局部頻繁項集合并得到全局頻繁項集。PFP算法執(zhí)行流程見圖2。

Figure 2 Flow chart of PFP algorithm圖2 PFP算法流程圖

PFP算法最顯著的優(yōu)點是：多個組及組相關事務之間是相互獨立的，不同的組可以在不同的計算結點上獨立運算，結點之間不需要相互等待和通信，最合適分布式運算。但是，缺點也很明顯：頻繁項的分組沒有考慮負載均衡，可能會造成有的計算結點計算任務很重，而有的結點計算任務很輕；與一個項相關聯(lián)的事務可能非常多，無法在一個計算結點上構造FP-Tree進行頻繁項集挖掘；將項和相關事務分發(fā)到單獨結點時，會產生很大的通信量。

3 PFPonCanTree算法

3.1 PFPonCanTree算法概述

給定一個原始數(shù)據(jù)集D及一批新的事務集T，PFPonCanTree算法分兩個階段分別對它們進行處理，共需要4個MapReduce任務完成并行挖掘任務。算法簡要描述如下：

第一階段：對D進行并行挖掘。

Setp1D-分片。將數(shù)據(jù)集D分割為i個連續(xù)部分，并分別存儲在p個計算結點上，每一個部分稱為一個數(shù)據(jù)分片。這個過程可以通過將數(shù)據(jù)集D存儲在Hadoop的分布式文件系統(tǒng)HDFS上，由HDFS自動完成。

Setp2D-并行計數(shù)。使用一個MapReduce任務來統(tǒng)計D中所有的項及其支持度。每個Mapper輸入一個或多個本結點上存儲的數(shù)據(jù)分片，分片中的所有項以〈item,1〉的鍵值對形式發(fā)送給Reducer，Reducer匯總相同項的計數(shù)，得到D中所有項的集合I及其支持度。

Setp3I-平衡分組。將I中的所有項根據(jù)支持度降序排列后，將I分成Q組。設Ii是I中的第i個項，Qi為Ii的組號，使用負載均衡的分組策略：

很顯然，支持度越高的項其相關聯(lián)的事務也越多。將項根據(jù)其支持度進行均衡分組，使得每一個組的相關事務集的數(shù)量相對均衡，有利于在分布式構造CanTree及挖掘時實現(xiàn)負載均衡。平衡分組可以在一個計算結點上完成，保存每個項及其組號的對應關系。

Setp4D-并行挖掘。這個步驟是第一階段的關鍵步驟。這一階段使用一個MapReduce任務來完成。Map階段根據(jù)項的分組情況，生成本地數(shù)據(jù)分片中的組相關事務，根據(jù)組號發(fā)送給對應計算節(jié)點。Reduce階段構造組相關事務的CanTree，并在CanTree上使用傳統(tǒng)的FP-Growth算法進行挖掘。Reduce階段構造的組相關CanTree及HeaderTable在挖掘完畢后存儲在計算結點中，作為下一步增量挖掘的基礎。有關實驗表明，由于樹的構造是一種遞歸計算任務，基于樹的頻繁模式挖掘算法構造樹的時間要遠遠大于在樹上進行遍歷挖掘的時間，因此在增量挖掘階段復用已經構造的樹可以大大減少挖掘的時間，免去重新構造樹的系統(tǒng)開銷。

Setp5D-聚集。如有需要，將Step 4中每個Reduce產生的頻繁模式進行匯總，輸出數(shù)據(jù)集D的頻繁模式。

至此，第一階段對原始數(shù)據(jù)集D的并行頻繁模式挖掘就結束了。可以看到，這一階段的執(zhí)行與PFP算法十分相似，區(qū)別在于三點：一是對項的分組考慮到了負載均衡的要求，依據(jù)項的支持度進行分組；二是在構造組相關事務集的樹時，構造的是CanTree而不是FP-Tree；三是挖掘結束后，CanTree和對應的HeaderTable并不丟棄，而是做為下一階段增量挖掘的基礎。

第二階段：對T進行并行增量挖掘。

Setp6T-分片。將新事務集T分割為i個連續(xù)部分，將數(shù)據(jù)分片存儲在p個計算節(jié)點上。這個過程同樣可以由HDFS自動完成。

Setp7T-并行計數(shù)。使用一個MapReduce任務來統(tǒng)計T中所有的項及其支持度。每個Mapper輸入一個或多個本節(jié)點上存儲的T的數(shù)據(jù)分片，分片中的項以〈item,1〉的鍵值對形式發(fā)送給Reducer，Reducer匯總相同項的計數(shù)，得到T中所有項的集合I′及其支持度。

Setp9U-并行挖掘：該步驟是第二階段的關鍵步驟。這一階段使用一個MapReduce任務來完成。Map階段根據(jù)U-項分組信息和計算結點的對應關系，將T的組相關事務發(fā)送給相應的計算結點。Reduce階段將新的事務更新到原CanTree上，更新完畢后使用FP-Growth算法進行挖掘。傳統(tǒng)的FP-Growth算法從HeaderTable的最后一項(即支持度最低的項)開始構造條件模式基礎，由于CanTree中存儲了所有項的信息，有些項可能并不頻繁，因此在挖掘過程中可以稍加改進，只需要考慮支持度大于min_sup的項即可。

Setp10U-聚集：將Step 9中每個Reduce產生的頻繁模式進行匯總，作為最終的結果。

兩階段完成后，U可以被看做是下一次增量挖掘的D。當有新的事務集T′到來時，重復算法的第二階段即可實現(xiàn)對新加入的T′進行挖掘，得到整個更新數(shù)據(jù)集U′的頻繁模式。兩階段流程圖如圖3所示。

Figure 3 Flow chart of PFPonCanTree algorithm圖3 PFPonCanTree算法流程圖

3.2 PFPonCanTree效率分析

將提出的算法與批處理并行算法PFP進行比較分析。設有數(shù)據(jù)集為D，新事務集為T，更新后的數(shù)據(jù)集為U，|D|=d，|T|=t，|U|=u，u=d+t；每條事務包含項的平均數(shù)為n，D被分為i個分片存儲在p個計算結點上，T被分為j個分片存儲在p個節(jié)結上，平均頻繁項的比例為s。PFP不是增量挖掘算法，當T加入D更新得到U后，只能對U重新進行并行挖掘，其執(zhí)行時間主要由6部分組成：

tPFP=t分片+t并行計數(shù)+t項分組+t分布式挖掘+t數(shù)據(jù)傳輸

而若使用PFPonCanTree算法，對T可以進行增量挖掘，增量挖掘除第一次挖掘外，其余只執(zhí)行算法的第二階段，則增量挖掘的執(zhí)行時間也主要由6部分組成：

數(shù)據(jù)分片由HDFS自動完成，項分組都是簡單操作，因此兩個算法這兩部分差異較小，可以忽略其差異。兩個算法的執(zhí)行時間主要取決于項并行計數(shù)、分布式挖掘兩個環(huán)節(jié)及數(shù)據(jù)傳輸?shù)臅r間。由于對數(shù)據(jù)的操作時間要遠遠低于數(shù)據(jù)傳輸?shù)臅r間，特別是在分布式計算的條件下，數(shù)據(jù)傳輸?shù)臅r間對算法效率更有顯著的影響。在相同集群條件下，數(shù)據(jù)傳輸時間的差異即是需要傳輸數(shù)據(jù)量的差異。

(1)對并行計數(shù)環(huán)節(jié)來說，兩個算法都需要一個MapReduce任務，使用相同的方式進行。兩者的差別在于需要處理的事務數(shù)及需要在Map和Reduce之間傳輸?shù)捻椀臄?shù)量。很明顯，PFP算法需要處理u個事務，而PFPonCanTree算法需要處理t個事務；u個事務會產生u*n個需要傳輸?shù)捻棧鳳FPonCanTree算法為t*n個。這一階段的加速比為：

(2)對分布式挖掘環(huán)節(jié)來說，兩個算法都需要一個MapReduce任務，使用類似的方式進行。該環(huán)節(jié)主要包含三個階段：生成組相關事務、構造樹結構、使用FP-Growth算法進行挖掘。由于挖掘使用的方法一致(都是使用FP-Growth算法)，挖掘的對象一致(都是U的CanTree)，因此兩個算法效率的差別主要在第一和第二階段。PFP算法最多需要傳輸|I|*u條事務，而PFPonCanTree最多需要傳輸|I′|*t條事務。

在構造樹結構階段，PFP需要重新構造FP-Tree，而PFPonTree算法只需要將新的事務更新到原有的CanTree上去。由于CanTree中存儲事務所有的項而非只有頻繁的項，因此CanTree比FP-Tree需要更多的存儲空間。這一階段的加速比為：

S分布式挖掘=|I|*u/(|I′|*t)≈(u/t)2

從上述分析可以看到，伴隨著數(shù)據(jù)集的不斷增長，u和t的差值會越來越大，PFPonCanTree會越來越體現(xiàn)出更好的效率，由于增量挖掘的特性，提出的算法只需要處理新增的T即可，比重新開始挖掘U數(shù)據(jù)集有明顯的性能優(yōu)勢。

4 實驗方案結果分析

使用基于MapReduce計算模型的開源系統(tǒng)Hadoop 1.2.1做為平臺搭建實驗集群，具體方案如下：使用1臺計算機做為Master結點,CPU為 i7-4790 3.60 GHz 8核，內存8 GB，操作系統(tǒng)為Red Hat Enterprise Linux Server 6.6，Java平臺為Java 1.6；使用6臺計算機做為Slave結點，CPU為 i3-4150 3.50 GHz 4核，內存4 GB，操作系統(tǒng)為Red Hat Enterprise Linux Server 6.6，Java平臺為Java 1.6。集群計算機之間使用百兆以太網相互連接；使用Java語言編寫PFP和PFPonCanTree算法，將兩個算法效率進行對比。所使用的實驗數(shù)據(jù)集具體屬性如表2所示。

Table 2 Specific attributes of experimental data sets

4.1 負載均衡實驗

算法的負載均衡主要取決于分布式挖掘階段各計算結點的處理數(shù)據(jù)量。使用來自Frequent Itemset Mining Dataset Repository[39]中的Mushroom數(shù)據(jù)集做為實驗數(shù)據(jù)集，使用算法Step 3負載均衡項分組策略，將所有項依次分為6、12、18組，每一組的組獨立事務數(shù)量如圖4～圖6所示。

Figure 4 Number of related transactions in each group when all items are divided into 6 groups圖4 將所有項分為6組時每個組相關事務集數(shù)量

Figure 5 Number of related transactions in each group when all items are divided into 12 groups圖5 將所有項分為12組時每個組相關事務集數(shù)量

Figure 6 Number of related transactions in each group when all items are divided into 18 groups圖6 將所有項分為18組時每個組相關事務集數(shù)量

從圖4～圖6可以看出，本文提出的項分組策略取得了很好的效果，使得在分布式挖掘階段每一個計算結點所處理的數(shù)據(jù)量十分接近，實現(xiàn)了較好的負載均衡。另外還可以看出，隨著分組數(shù)的不斷增加，每一組所包含的事務數(shù)隨之減少，因此可以通過盡可能地擴大分組數(shù)，使分布式挖掘階段啟動更多的Reduce方法，提高并行化程度。設集群中有p個計算結點，每個結點能夠運行的最大Reduce方法數(shù)為r，則最大分組數(shù)Q可以由以下公式計算得到：

Q=p*r

這樣可以充分利用每一個計算結點的計算能力，同時也可以使Map方法的輸出發(fā)送到更多的結點，有利于實現(xiàn)網絡通信的負載均衡。

4.2 算法執(zhí)行效率實驗

設計三組實驗，使用PFP算法對更新數(shù)據(jù)集進行批處理挖掘，使用PFPonCanTree算法對增量數(shù)據(jù)進行增量挖掘，最低支持度為0.025%，三組實驗數(shù)據(jù)如表3所示。

Table 3 Three groups of experimental data

三組實驗的執(zhí)行時間如圖7所示。

Figure 7 Run time of three groups of experimental data圖7 三組實驗數(shù)據(jù)運行時間

從實驗結果可以發(fā)現(xiàn)：

(1)增量挖掘算法實現(xiàn)了較好的效率提高，其執(zhí)行時間減少主要是因為兩點：一是增量挖掘階段不用重新生成D的組相關事務，大大減少了分布式挖掘階段Map方法的輸出和網絡上的I/O傳輸數(shù)據(jù)量；二是構造樹是一種遞歸計算，需要大量的計算資源。增量挖掘階段更新原CanTree要遠遠快于重新構造更新數(shù)據(jù)集U的CanTree，提高了效率。

(2)提出的PFPonCanTree算法具有較好的線性加速度，適合于進行進一步擴展。

5 結束語

本文提出了一種基于MapReduce計算模型的并行頻繁模式增量挖掘算法PFPonCanTree。算法基于傳統(tǒng)的增量挖掘CanTree數(shù)據(jù)結構及并行頻繁模式挖掘算法PFP的基本思想，使用均衡負載對項進行了平衡分組，減少了增量挖掘階段I/O數(shù)據(jù)量及構造CanTree的計算量。實驗結果表明，提出的算法在負載均衡及執(zhí)行效率上都有較好的表現(xiàn)。下一步的工作可以進一步優(yōu)化Hadoop運行環(huán)境，提高分布式挖掘階段Map方法的并行度，進一步提高算法的執(zhí)行效率。

[1] Agrawal R, Imielinski T, Swami A N. Mining association rules between sets of items in large databases[C]∥Proc of the ACMSIGMOD Conference on Management of Data,1993:207-216.

[2] Agrawal R,Srikant R.Fast algorithm for mining association rules in large databases[C]∥Proc of the 20th International Conference on Very Large Data Bases,1994:487-499.

[3] Han Jia-wei,Pei Jian,Yin Yi-wen,et al.Mining frequent patterns without candidate generation: A frequent-pattern treeapproach[J].Data Mining and Knowledge Discovery,2004,8(1):53-87.

[4] Pyuna G, Yun U, Ryu K H.Efficient frequent pattern mining based on linear prefix tree[J].Knowledge-Based Systems,2014,55:125-139.

[5] Tsay Y J, Hsu T J, Yu J R. FIUT:A new method for mining frequent itemsets[J].Information Sciences,2009,179(11):1724-1737.

[6] Lin Ke-chung,Liao I-en,Chen Zhi-sheng.An improved frequent pattern growth method for mining association rules[J].Expert Systems with Applications,2011,38(5):5154-5161.

[7] Tseng Fan-chen. An adaptive approach to mining frequent itemsets efficiently[J].Expert Systems with Applications,2012,39(39):13166-13172.

[8] Cheung D W,Han J,Ng V T,et al.Maintenance of discovered association rules in large databases: An incremental updating approach[C]∥Proc of the 20th IEEE International Conference on Data Engineering,1996:106-114.

[9] Cheung D W, Lee S D,Kao B.A general incremental technique for maintaining discovered association rules[C]∥Proc of International Conference on Databases Systems for Advanced Applications,1997:185-194.

[10] Ayan N F,Tansel A U, Arkun E. An efficient algorithm to update large itemsets with early pruning[C]∥Proc of Acm-sigkdd International Conference on Knowledge Discovery & Data Mining,1999:287-291.

[11] Srikant R,Agrawal R.Mining sequential patterns: Generalizations and performance improvements[C]∥Proc of the 5th Conference on Extending Database Technology,1996:3-17.

[12] Hong T P,Wang C Y,Tao Y H.A new incremental data mining algorithm using pre-large itemsets[J].Intelligent Data Analysis,2001,5(2):111-129.

[13] Koh J L,Shieh S F.An efficient approach for maintaining association rules based on adjusting FP-tree structures[M]∥Database Systems for Advanced Applications.Berlin:Springer Berlin Heidelberg,2004:417-424.

[14] Cheung W, Za?ane O R. Incremental mining of frequent-patterns without candidate gneration or support constraint[C]∥Proc of the 2003 International Database Engineering and Applications Symposium,2003:111-116.

[15] Leung K S，Khan Q I，Hoque T.Cantree: A tree structure for efficient incremental mining of frequent patterns[C]∥Proc of the 5th IEEE International Conference on Data Mining,2005:8.

[16] Totad S G, Geeta R B G, Reddy P P.Batchprocessing for incremental fp-tree construction[J].International Journal of Computer Applications,2010,5(5):28-32.

[17] Li N,Zeng L,He Q,et al.Parallel implementation of apriori algorithm based on mapreduce[C]∥Proc of Acis International Conference on Software Engineering,Artificial Intelligence,Networking and Parallel & Distributed Computing,2012:236-241.

[18] Huang Li-qin,Liu Yan-huang.Research on improved parallel Apriori with MapReduce[J].Journal of Fuzhou University(Natural Science Edition),2011,39(5):680-685.(in Chinese)

[19] Sun Zhao-xu,Xie Xiao-lan,Zhou Guo-qing,et al.Implemention of Apriori based on Hadoop[J].Journal of Guilin University of Technology,2014,34(3):584-588.(in Chinese)

[20] Zhou X,Huang Y.An improved parallel association rules algorithm based on mapreduce framework for big data[C]∥Proc of the 2014 10th International Conference on Natural Computation,2014:284-288.

[21] Zhou Guo-jun,Gong Yu-tong.Frequent item sets mining algorithm based on MapReduce and matrix[J].Microelectronics & Computer,2016,33(5):119-123.(in Chinese)

[22] 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,2011:475-478.

[23] Yu R M,Lee M G,Huang Y S,et al.An efficient frequent patterns mining algorithm based on mapreduce framework[C]∥Proc of International Conference on Software Intelligence Technologies and Appliations,2014:1-5.

[24] Mao W,Guo W. An improved association rules mining algorithm based on power set and hadoop[C]∥Proc of International Conference on Information Science and Cloud Computing Companion,2013:236-241.

[25] Liu S H,Liu S J,Chen S X,et al.IOMRA—A high efficiency frequent itemset mining algorithm based on the MapReduce computation model[C]∥Proc of IEEE International Conference on Computational Science and Engineering,2014:1290-1295.

[26] Yahya O,Hegazy O,Ezat E.An efficient implementation of Apriori algorithm based on hadoop-mapreduce model[J].International Journal of Reviews in Computing,2012,12:59-63.

[27] Farzanyar Z,Cercone N.Efficient mining of frequent itemsets in social network data based on mapreduce framework[C]∥Proc of 2013 International Conference on Advances in Social Networks Analysis and Mining (ASONAM),2013:1183-1188.

[28] Farzanyar Z, Cercone N. Accelerating frequent itemsets mining on the cloud: A mapreduce-based approach[C]∥Proc of IEEE International Conference on Data Mining Workshops,2013:592-598.

[29] Huang D,Song Y,Routray R,et al.Smartcache: An optimized MapReduce implementation of frequent itemset mining[C]∥ Proc of IEEE International Conference on Cloud Engineering,2015:16-25.

[30] Viana S. Matrix apriori: Speeding up the search for frequent patterns[C]∥Proc of Iasted International Conference on Databases and Applications,2006:75-82.

[31] Li H,Wang Y,Zhang D,et al.Pfp:Parallel fp-growth for query recommendation[C]∥Proc of ACM Conference on Recommender Systems,2008:107-114.

[32] Yang Yong, Wang Wei.A parallel FP-growth algorithm based on Mapreduce[J].Journal of Chongqing University of Posts and Telecommunications(Natural Science Edition),2013,25(5):651-657.(in Chinese)

[33] Zhou L,Zhong Z,Chang J,et al.Balanced parallel fp-growth with mapreduce[C]∥Proc of 2010 IEEE Youth Conference on Information Computing and Telecommunications (YC-ICT),2010:243-246.

[34] Yong W,Zhe Z,Fang W.A parallel algorithm of association rules based on cloud computing[C]∥Proc of International ICST Conference on Communications and Networking in China,2013:415-419.

[35] Chen Xing-shu, Zhang Shuai,Tong Hao,et al.FP-growth algorithm based on Boolean matrix and MapReduce[J].Journal of South China University of Technology (Natural Science Edition),2014,42(1):135-141.(in Chinese)

[36] Xun Y,Zhang J,Qin X.Fidoop: Parallel mining of frequent itemsets using MapReduce[J].IEEE Transactions on Systems Man & Cybernetics Systems,2015,46(3):1.

[37] Welcome to ApacheHadoop![EB/OL].[2017-01-10].http:∥hadoop.apache.org/.

[38] Hoseini M S, Shahraki M N,Neysiani B S.A new algorithm for mining frequent patterns in CAN tree[C]∥Proc of International Conference on Knowledge-Based Engineering and Innovation,2015.

[39] Frequent itemset mining dataset repository[EB/OL].[2016-12-01].http:∥fimi.ua.ac.be/data/.

附中文參考文獻：

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

[19] 孫趙旭,謝曉蘭,周國清,等.基于Hadoop的Apriori算法與實現(xiàn)[J].桂林理工大學學報,2014,34(3):584-588.

[21] 周國軍,龔榆桐.基于MapReduce和矩陣的頻繁項集挖掘算法[J].微電子學與計算機,2016,33(5):119-123.

[32] 楊勇,王偉.一種基于MapReduce的并行FP-growth算法[J].重慶郵電大學學報(自然科學版),2013,25(5):651-657.

[35] 陳興蜀,張帥,童浩,等.基于布爾矩陣和MapReduce的FP-Growth算法[J].華南理工大學學報(自然科學版),2014,42(1):135-141.