肖 文，胡 娟，周曉峰

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

1 引言

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

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

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

MapReduce是一種由Google提出的易用且功能強(qiáng)大的并行編程模型，具有使用簡單、自動容錯、負(fù)載均衡、伸縮性好等優(yōu)點(diǎn)，已經(jīng)有了很多將傳統(tǒng)頻繁模式挖掘算法向MapReduce模型進(jìn)行遷移的研究[17 - 36]，很大程度上解決了大數(shù)據(jù)中頻繁模式挖掘的問題。在MapReduce計算模型中，一個計算任務(wù)被分為Map和Reduce兩個方法。Map方法在多個結(jié)點(diǎn)上運(yùn)行，處理一個或多個本地的數(shù)據(jù)分片；Reduce方法處理Map方法輸出的中間結(jié)果，也可以多個Reduce方法并行執(zhí)行；所有Reduce方法的輸出合并后得到最后的結(jié)果。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)，可以自動地對超大文件進(jìn)行分片及負(fù)載均衡。HDFS將分片存儲在不同的結(jié)點(diǎn)上，同時在存儲分片的結(jié)點(diǎn)上執(zhí)行MapReduce計算任務(wù)，通過數(shù)據(jù)本地化、減少I/O來提高運(yùn)行效率。一個Hadoop集群可以運(yùn)行在普通的商用計算機(jī)上，包括一個Master結(jié)點(diǎn)和多個Slave結(jié)點(diǎn)。

本文主要貢獻(xiàn)為：

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

(2)設(shè)計了并行計算中各結(jié)點(diǎn)的負(fù)載均衡策略，使得每個結(jié)點(diǎn)計算量相對平衡，提高整個算法運(yùn)行效率。

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

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

2 問題定義與相關(guān)研究

2.1 問題描述與符號定義

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

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

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

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

Table 1 Symbol description

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

2.2 FELINE(CATS-Tree)

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

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

2.3 CanTree

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

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

2.4 PFP

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

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

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

3 PFPonCanTree算法

3.1 PFPonCanTree算法概述

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

第一階段：對D進(jìn)行并行挖掘。

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

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

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

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

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

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

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

第二階段：對T進(jìn)行并行增量挖掘。

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

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

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

Setp10U-聚集：將Step 9中每個Reduce產(chǎn)生的頻繁模式進(jìn)行匯總，作為最終的結(jié)果。

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

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

3.2 PFPonCanTree效率分析

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

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

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

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

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

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

在構(gòu)造樹結(jié)構(gòu)階段，PFP需要重新構(gòu)造FP-Tree，而PFPonTree算法只需要將新的事務(wù)更新到原有的CanTree上去。由于CanTree中存儲事務(wù)所有的項而非只有頻繁的項，因此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 實驗方案結(jié)果分析

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

Table 2 Specific attributes of experimental data sets

4.1 負(fù)載均衡實驗

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

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

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

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

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

Q=p*r

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

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

設(shè)計三組實驗，使用PFP算法對更新數(shù)據(jù)集進(jìn)行批處理挖掘，使用PFPonCanTree算法對增量數(shù)據(jù)進(jìn)行增量挖掘，最低支持度為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ù)運(yùn)行時間

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

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

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

5 結(jié)束語

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

附中文參考文獻(xiàn)：

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

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

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

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

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