付婷婷，楊世平，2（.貴州大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，貴州 貴陽 550025；2.貴州大學(xué) 明德學(xué)院，貴州 貴陽 550004）

基于MapReduce的頻繁閉項集挖掘算法改進(jìn)

付婷婷1，楊世平1，2
（1.貴州大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，貴州 貴陽 550025；2.貴州大學(xué) 明德學(xué)院，貴州 貴陽 550004）

挖掘頻繁閉項集（CFI）在許多實際應(yīng)用中起著重要的作用。傳統(tǒng)的數(shù)據(jù)挖掘算法中常用FP增長算法和Apriori算法來挖掘頻繁項集。然而，內(nèi)存需求和計算成本成為CFI挖掘算法的瓶頸，尤其是在從大型數(shù)據(jù)集中挖掘頻繁閉項集時，是一個重要和具有挑戰(zhàn)性的問題。針對上述問題，提出一種基于云計算的MapReduce框架的并行AFOPT-close算法，使MapReduce可廣泛地用于處理大型數(shù)據(jù)。此外，用于檢查頻繁項集是否為完全閉的有效并行算法也要求MapReduce平臺進(jìn)一步完善其性能。

MapReduce；頻繁閉項集；FP增長算法

0 引言

頻繁閉項集挖掘（Closed Frequent Itemset，CFI）在1999年由 Pasquier等人提出［1］。作為一種代替?zhèn)鹘y(tǒng)頻繁項集挖掘（Frequent Itemset Mining，F(xiàn)IM）的新算法，CFI挖掘的優(yōu)點在于在相同的頻繁項集挖掘效率下大大降低了冗余規(guī)則并且增加了挖掘的效率和有效性。自CFI出現(xiàn)以來一直被廣泛地研究，現(xiàn)有的CFI挖掘算法可分為兩類：候選項集生成和檢測方法［1］和模式增長方式［2-4］。

這些算法在處理小數(shù)據(jù)集或者支持度閾值較高時有良好的性能，但是當(dāng)處理大數(shù)據(jù)集或者支持度閾值變小時內(nèi)存運行開銷將大幅度增加。一些早期的工作重點在于使用PC集群運行算法來加快挖掘速度，這樣可以提高挖掘性能，但是也對諸如負(fù)載平衡、數(shù)據(jù)分區(qū)、通信成本最小化、因通信節(jié)點失效引起的錯誤等問題提出了新的挑戰(zhàn)。

為了克服上述缺點，設(shè)計了MapReduce框架來支持云計算分布式計算的計算模式，對于大型數(shù)據(jù)集而言這是一個進(jìn)行并行數(shù)據(jù)挖掘的有效平臺。為了能更好地利用MapReduce在CFI挖掘中的優(yōu)勢，本文基于 MapReduce設(shè)計并實現(xiàn)了一個并行算法［4］，這種算法是一種類似于FP增長算法的分治算法，能夠有效地挖掘頻繁閉項集。此外，也提出了一種檢查一個頻繁項集是否是完全閉的有效并行化方法，該方法能夠過濾掉冗余的頻繁項集。

1 頻繁項集挖掘改進(jìn)算法

在現(xiàn)有的研究中［3，5］已經(jīng)設(shè)計出能夠在內(nèi)存共享情況下的多線程的FP增長算法，但當(dāng)面臨大規(guī)模數(shù)據(jù)集時這些方法將遇到內(nèi)存需求嚴(yán)重不足的問題。一些研究工作也致力于解決更多細(xì)節(jié)問題，如通信開銷最小化，內(nèi)存的利用率最大化等［6-8］。例如WHANG K Y等人提出了一種在無共享環(huán)境下FP增長算法并行執(zhí)行的方法，該算法可以實現(xiàn)良好的可擴(kuò)展性，但是也存在同樣的問題。隨著云計算的發(fā)展，MapReduce平臺能夠?qū)Υ鎯υ诖笮陀嬎銠C(jī)集群上的龐大數(shù)據(jù)進(jìn)行分布式處理，具有良好的可擴(kuò)展性和魯棒容錯性。因此提出了許多基于MapReduce的頻繁項集挖掘改進(jìn)算法。例如李浩源等人基于 MapReduce提出了一種并行的FP增長算法 PFP［9］，該算法將整個挖掘任務(wù)分割成若干獨立的并行子任務(wù)，并實現(xiàn)了擬線性加速比。除了可擴(kuò)展性，PFP還讓設(shè)計基于MapReduce的模式增長方式成為可能。在以前的研究中，也有對基于MapReduce的閉頻繁項集算法的相關(guān)討論和實現(xiàn)［10］，主要通過以下 4個步驟來完成該算法，其中3個步驟是MapReduce操作。

（1）并行計算。統(tǒng)計數(shù)據(jù)庫中每個項目的支持度。

（2）構(gòu)建全局的F-List（鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)）。把項目按出現(xiàn)頻率遞減的順序分類并排除支持度小于最小支持度閾值的項目（用ξ表示）。

（3）并行挖掘頻繁閉項集。并行挖掘局部頻繁閉項集。

（4）并行過濾冗余項集。過濾局部閉而非全局閉的頻繁項集。

通過上面4個步驟，能夠準(zhǔn)確地挖掘頻繁閉項集。如圖1中的一個簡單例子，左邊部分是原始事務(wù)表，右邊部分給出通過步驟（1）～（4）挖掘得到的CFI，其中 ξ= 3。右邊部分每個項集的最后一項為支持度閾值。顯然，這存在一些局部閉而非全局閉的冗余項集，例如 ｛fm 4｝，｛f p c 3｝，｛f p 3｝。

圖1 源數(shù)據(jù)表和對其挖掘得到的CFI

在第（4）步中使用了并行的方法來過濾冗余項集。如圖2所示，首先，每個 mapper函數(shù)從 CFI中讀入一個項集，然后輸出n次，n為項集的長度，Key為在項集中出現(xiàn)的項目。然后，每個reducer函數(shù)接收相應(yīng)的值并且將項集按他們的長度遞減分類，這樣做是為了避免超集的檢測，接下來并行地過濾冗余項集。最后，該項集的Key為最終保存的項。這種方法雖然可行，但是也導(dǎo)致了嚴(yán)重的通信開銷和計算成本。以頻繁項集｛f p c b 3｝為例，3為該項集的支持度閾值。該方法需要發(fā)送這個項集4次：分別是｛f：f p c b 3｝、｛p：f p c b 3｝、｛c：f p c b 3｝、｛b：f p c b 3｝。顯然，這4個項集將會按不同的Key值被發(fā)送到reducer函數(shù)4次。如果ξ足夠小，將可能有許多很長的頻繁項集被反復(fù)地發(fā)送到 reducer函數(shù)。因此，這種方法的總體開銷會非常高。為了解決這個問題，本文提出了一種高效的并行CFI挖掘算法，該算法也采用了一種新穎的冗余項集過濾方法來降低通信開銷和計算成本。

圖2 冗余項集過濾

2 并行AFOPT-c l o s e算法

2.1 算法的定義

在本節(jié)中，提出了一種有效的冗余項集過濾方法，即并行AFOPT-close算法。如上所述，直接基于MapReduce采用并行化的方法挖掘頻繁閉項集會導(dǎo)致一些項集可能局部閉而非全局閉的問題。在本節(jié)中，將對局部頻繁閉項集和全局頻繁閉項集分別進(jìn)行定義。

定義1局部頻繁閉項集

如果頻繁項集X在步驟（3）中的 reducer中是閉的，那么頻繁項集X為局部頻繁閉項集，用L表示局部項集。

定義2全局頻繁閉項集

如果頻繁項集X對于所有局部頻繁閉項集都是閉的，那么頻繁項集X為全局頻繁閉項集。用G表示全局項集。

性質(zhì)：假設(shè)存在 X∈L，如果 X對于所有的項集｛Y| Y∈L and supp（X）=supp（Y）｝都是閉的，那么X∈G。

定義3冗余項集

當(dāng)且僅當(dāng)頻繁項集X∈L且X?G，那么頻繁項集X為冗余項集，用R表示冗余。

2.2 高效冗余項集過濾

在現(xiàn)有的研究中，提出了一種基本方法來過濾冗余項集，該方法因計算成本和通信開銷太高而很費時。本文基于2.1節(jié)中的定義提出了一種新的方法來解決這個問題。當(dāng)然，可以通過選出具有相同支持度的全局閉頻繁項集而輕松地實現(xiàn)一個高效冗余過濾算法。因此，把一個項集的支持度作為一個項集的關(guān)鍵，具有相同支持度的項集會被發(fā)送到同一個reducer函數(shù)。將在下面的算法1中給出這種方法的簡要代碼，該方法的開始3步與參考文獻(xiàn)［10］中提出的算法描述的一樣（Suppose X∈L）。

算法 1的處理過程如下：首先，每個 mapper函數(shù)一行一行地從第（3）步中讀取輸出結(jié)果并且輸出＜key，value＞對和＜supp（X），X＞。這樣，具有相同支持度的項集會被發(fā)送到相同的 reducer函數(shù)中并壓縮成一棵樹。然后，冗余項集會被并行地過濾掉。如圖1所示，只需要把每個項集發(fā)送到局部頻繁閉項集中一次（如圖1的左半部分），而已有的方法［10］需要發(fā)送每個項集至少 3次，如圖3所示。對于具有n個項集的數(shù)據(jù)庫，每個項集的長度是｛m1，m2，…，mn｝。在傳統(tǒng)方法［10］中，項集需要發(fā)送m1+m2+…+mn次，也就是說，該方法約節(jié)約了（m1+m2+…+mn）/n（即項集的平均長度）倍的通信成本。

for each itemset in r do

output（key，itemset）；

end for

end Procedure

3 性能仿真與結(jié)果分析

為了驗證該方法的效率和有效性，將在兩個下載的真實的數(shù)據(jù)庫connect和webdocs中做實驗。實驗在6臺裝有Hadoop0.21.0的計算機(jī)組成的計算機(jī)群上進(jìn)行，計算機(jī)配置為 Intel 4核處理器，4 GB內(nèi)存和 500 GB硬盤，裝有 Ubuntu10.10。其中一個節(jié)點被設(shè)為主節(jié)點，負(fù)責(zé)安排執(zhí)行不同節(jié)點之間的任務(wù)；其他節(jié)點負(fù)責(zé)運行。算法用Java實現(xiàn)，JDK版本為openjdk-6-jdk。

圖4顯示了在webdocs數(shù)據(jù)庫上實驗的結(jié)果。當(dāng)ξ= 650 000時，該算法擁有最大的斜率值。因為當(dāng) ξ越大，對于在第（3）步中的每個reducer函數(shù)而言，本地數(shù)據(jù)庫越小，所以在第（3）步和第（4）步中耗費的時間越短，而在第（1）步和第（2）步中消耗的時間依然保持不變。

圖4 數(shù)據(jù)庫webdocs上的實驗結(jié)果

圖3 高效冗余過濾

算法1高效冗余項集過濾

Procedure：Map（key，value=supp（X）+X）

for each value do

output（supp（X），X）；

end for

end Procedure

Procedure：Reduce（key，Iterable values）

Define and initialize a tree：r；

Sort the itemsets by their lengths in descending order；

for each itemset in values do

if itemset is closed in r then

Insert the itemset into r；

end if

end for

圖5顯示了在connect數(shù)據(jù)庫上實驗的結(jié)果。由于該數(shù)據(jù)庫比較小，速度上的提高不如圖4的明顯。從圖5可以看出，用4臺電腦比用5臺電腦更能提高速度。原因在于對于每個節(jié)點而言，數(shù)據(jù)集太小，導(dǎo)致通信成本遠(yuǎn)高于計算成本。實驗結(jié)果表明，該算法對于大規(guī)模的數(shù)據(jù)集擁有良好的可擴(kuò)展性，對于小規(guī)模數(shù)據(jù)集則不然。

圖5 數(shù)據(jù)庫connect上的實驗結(jié)果

對上述新冗余過濾算法和傳統(tǒng)算法［10］在項集發(fā)送次數(shù)上作對比，結(jié)果如表1所示。例如數(shù)據(jù)集connect，如果不適用新的冗余過濾算法，如果數(shù)據(jù)集過大勢必使計算成本和通信開銷變得很高。根據(jù)表1，顯然當(dāng)ξ=24 000時，傳統(tǒng)算法［10］與上述算法在項集發(fā)送次數(shù)的對比中可以看出新的冗余過濾算法的優(yōu)越性。但是，該方法在webdocs數(shù)據(jù)庫上卻沒有明顯優(yōu)勢，原因在于在第（3）步中產(chǎn)生的項集的平均長度過短。由此可見，新算法對于長項集而言比短項集具有更高的效率。

表1 項集發(fā)送次數(shù)對比表

對上述算法與傳統(tǒng)算法［10］作運行時間上的對比，如表2所示。實驗在5臺負(fù)責(zé)運行的計算機(jī)組成的計算機(jī)群上進(jìn)行，用兩個相同的數(shù)據(jù)集但是閾值不同。從表2可以看出，由于局部閉頻繁項集比源數(shù)據(jù)集要大而且項集自身的平均長度也很長，因此上述算法對于 connect數(shù)據(jù)庫而言更高效。綜上所述，該算法的運行速度更快。但是對于 webdocs，當(dāng) ξ取 350 000、500 000和 650 000時該算法沒有優(yōu)勢，主要是由于第（3）步輸出的結(jié)果太小。然而當(dāng)ξ=200 000時，該算法比傳統(tǒng)算法快得多，這是因為第（3）步的輸出結(jié)果足夠大并且具有更多長項集。

表2 運行時間對比表

4 結(jié)論

本文回顧了頻繁閉項集挖掘現(xiàn)存的問題，并且提出了一種新的過濾局部閉而非全局閉頻繁項集的方法。實驗結(jié)果顯示，該算法在面對大規(guī)模數(shù)據(jù)集時擁有很高的可擴(kuò)展性。當(dāng)局部閉頻繁項集很大，尤其是對于一些閾值非常小或者項集過長的挖掘中，通信開銷將嚴(yán)重影響算法性能。而本文所提方法能很好地解決這個問題。今后，將繼續(xù)改進(jìn)該算法，使之有更高的效率和更廣的使用面。

［1］廖寶魁，孫雋楓.基于MapReduce的增量數(shù)據(jù)挖掘研究［J］.微型機(jī)與應(yīng)用，2014，33（1）：67-70.

［2］Wang Jianyong，Han Jiawei，Pei Jian.CLOSET+：searching for the best strategies for mining frequent closed itemsets［C］.Proceedings of the ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，ACM，2003：236-245.

［3］FELDMAN R，DAGAN I.Knowledge discovery in textual databases（KDT）［C］.Proceedings of 1stInternational Conference on Knowledge Discovery and Data Mining，Montreal，Canada，1995：112-117.

［4］ZANE O，EL-HAJJ M，LU P.Fast parallel association rule mining without candidacy generation［C］.Proceedings of IEEE International Conference on Data Mining，ICDM 2001，2001：665-668.

［5］Liu Li，Li E，Zhang Yimin，et al.Optimization of frequent itemset mining on multiple-core processor［C］.Proceedings of the 33rd International Conference on Very Large Data Bases，VLDB Endowment，2007：1275-1285.

［6］MADRIA K，BHOWMICK S.Research issue in web data mining［C］.First International Proceedings of Data Warehousing and Knowledge Discovery，1999：303-312.

［7］PRAMUDIONO I，KITSUREGAWA M.Parallel fp-growth on pc cluster［J］.Advances in Knowledge Discovery and Data Mining，2003，2637：467-473.

［8］BUEHRER G，PARTHASARATHY S，TATIKONDA S，et al.Toward terabyte pattern mining：an architecture conscious solution［C］.Proceedings of the 12th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming，ACM，2007：2-12.

［9］蔣翠清，胡俊妍.基于 FP-tree的最大頻繁項集挖掘算法［J］.合肥工業(yè)大學(xué)學(xué)報（自然科學(xué)版），2010，33（9）：1387-1391.

［10］陳光鵬，楊育彬，高陽，等.一種基于 MapReduce的頻繁閉項集挖掘算法［J］.模式識別與人工智能，2012，25（2）：220-224.

楊世平（1955.2-），男，博士，教授，主要研究方向：計算機(jī)網(wǎng)絡(luò)與信息安全。

Improvement of closed frequent item set m ining algorithm based on MapReduce

Fu Tingting1，Yang Shiping1，2
（1.College of Computer Science and Technology，Guizhou University，Guiyang 550025，China；2.College of Mingde，Guizhou University，Guiyang 550004，China）

Closed frequent itemset（CFI）mining is very crucial in many data mining works.In traditional data mining algorithms，F(xiàn)P-tree and Apriori are often applied to mine frequent itemsets.But memory requirement and computational cost become the vital problems.Especially，while mining closed frequent itemsets from large datasets，the problem will become significant and fill of challenge.To solve the problem，a parallelized algorithm based on MapReduce is presented，and it makes MapReduce extensively be used to compute big data.Besides，the algorithm goes to check whether the frequent itemstes are closed also needs MapReduce do further improvement.

MapReduce；closed frequent itemset；FP-tree algorithm

TP3-0

A

1674-7720（2015）24-0066-04

付婷婷，楊世平.基于MapReduce的頻繁閉項集挖掘算法改進(jìn)［J］.微型機(jī)與應(yīng)用，2015，34（24）：66-69.

2015-08-28）

付婷婷（1990-），女，碩士研究生，主要研究方向：網(wǎng)絡(luò)系統(tǒng)與信息安全。