基于MapReduce的頻繁閉項集挖掘算法改進

付婷婷，楊世平，2（.貴州大學 計算機科學與技術學院，貴州 貴陽 550025；2.貴州大學 明德學院，貴州 貴陽 550004）

基于MapReduce的頻繁閉項集挖掘算法改進

付婷婷1，楊世平1，2
（1.貴州大學 計算機科學與技術學院，貴州 貴陽 550025；2.貴州大學 明德學院，貴州 貴陽 550004）

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

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

0 引言

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

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

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

1 頻繁項集挖掘改進算法

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

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

（2）構建全局的F-List（鏈式數據結構）。把項目按出現頻率遞減的順序分類并排除支持度小于最小支持度閾值的項目（用ξ表示）。

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

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

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

圖1 源數據表和對其挖掘得到的CFI

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

圖2 冗余項集過濾

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

2.1 算法的定義

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

定義1局部頻繁閉項集

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

定義2全局頻繁閉項集

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

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

定義3冗余項集

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

2.2 高效冗余項集過濾

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

算法 1的處理過程如下：首先，每個 mapper函數一行一行地從第（3）步中讀取輸出結果并且輸出＜key，value＞對和＜supp（X），X＞。這樣，具有相同支持度的項集會被發(fā)送到相同的 reducer函數中并壓縮成一棵樹。然后，冗余項集會被并行地過濾掉。如圖1所示，只需要把每個項集發(fā)送到局部頻繁閉項集中一次（如圖1的左半部分），而已有的方法［10］需要發(fā)送每個項集至少 3次，如圖3所示。對于具有n個項集的數據庫，每個項集的長度是｛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 性能仿真與結果分析

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

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

圖4 數據庫webdocs上的實驗結果

圖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數據庫上實驗的結果。由于該數據庫比較小，速度上的提高不如圖4的明顯。從圖5可以看出，用4臺電腦比用5臺電腦更能提高速度。原因在于對于每個節(jié)點而言，數據集太小，導致通信成本遠高于計算成本。實驗結果表明，該算法對于大規(guī)模的數據集擁有良好的可擴展性，對于小規(guī)模數據集則不然。

圖5 數據庫connect上的實驗結果

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

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

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

表2 運行時間對比表

4 結論

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

［1］廖寶魁，孫雋楓.基于MapReduce的增量數據挖掘研究［J］.微型機與應用，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è)大學學報（自然科學版），2010，33（9）：1387-1391.

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

楊世平（1955.2-），男，博士，教授，主要研究方向：計算機網絡與信息安全。

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，FP-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］.微型機與應用，2015，34（24）：66-69.

2015-08-28）

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