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

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

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

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

MapReduce；頻繁閉項(xiàng)集；FP增長(zhǎng)算法

0 引言

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

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

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

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

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

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

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

（3）并行挖掘頻繁閉項(xiàng)集。并行挖掘局部頻繁閉項(xiàng)集。

（4）并行過(guò)濾冗余項(xiàng)集。過(guò)濾局部閉而非全局閉的頻繁項(xiàng)集。

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

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

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

圖2 冗余項(xiàng)集過(guò)濾

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

2.1 算法的定義

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

定義1局部頻繁閉項(xiàng)集

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

定義2全局頻繁閉項(xiàng)集

如果頻繁項(xiàng)集X對(duì)于所有局部頻繁閉項(xiàng)集都是閉的，那么頻繁項(xiàng)集X為全局頻繁閉項(xiàng)集。用G表示全局項(xiàng)集。

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

定義3冗余項(xiàng)集

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

2.2 高效冗余項(xiàng)集過(guò)濾

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

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

for each itemset in r do

output（key，itemset）；

end for

end Procedure

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

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

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

圖4 數(shù)據(jù)庫(kù)webdocs上的實(shí)驗(yàn)結(jié)果

圖3 高效冗余過(guò)濾

算法1高效冗余項(xiàng)集過(guò)濾

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

圖5 數(shù)據(jù)庫(kù)connect上的實(shí)驗(yàn)結(jié)果

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

表1 項(xiàng)集發(fā)送次數(shù)對(duì)比表

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

表2 運(yùn)行時(shí)間對(duì)比表

4 結(jié)論

本文回顧了頻繁閉項(xiàng)集挖掘現(xiàn)存的問(wèn)題，并且提出了一種新的過(guò)濾局部閉而非全局閉頻繁項(xiàng)集的方法。實(shí)驗(yàn)結(jié)果顯示，該算法在面對(duì)大規(guī)模數(shù)據(jù)集時(shí)擁有很高的可擴(kuò)展性。當(dāng)局部閉頻繁項(xiàng)集很大，尤其是對(duì)于一些閾值非常小或者項(xiàng)集過(guò)長(zhǎng)的挖掘中，通信開(kāi)銷(xiāo)將嚴(yán)重影響算法性能。而本文所提方法能很好地解決這個(gè)問(wè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的最大頻繁項(xiàng)集挖掘算法［J］.合肥工業(yè)大學(xué)學(xué)報(bào)（自然科學(xué)版），2010，33（9）：1387-1391.

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

楊世平（1955.2-），男，博士，教授，主要研究方向：計(jì)算機(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的頻繁閉項(xiàng)集挖掘算法改進(jìn)［J］.微型機(jī)與應(yīng)用，2015，34（24）：66-69.

2015-08-28）

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