MRClose：一種基于MapReduce的并行閉頻繁項(xiàng)集挖掘算法

胡娟

頻繁項(xiàng)集挖掘是最重要的數(shù)據(jù)挖掘任務(wù)之一，閉頻繁模式項(xiàng)集是頻繁項(xiàng)集的一種無(wú)損壓縮形式，具有挖掘效率高、無(wú)冗余信息等優(yōu)點(diǎn)。在大數(shù)據(jù)時(shí)代，基于單機(jī)的閉頻繁項(xiàng)集挖掘算法不能適應(yīng)海量數(shù)據(jù)的挖掘需求，需要并行的算法來(lái)解決。本文分析了并行閉頻繁項(xiàng)集挖掘中搜索空間劃分、剪枝策略的策略選擇，設(shè)計(jì)了一種并行的全局閉項(xiàng)集篩選方法，提出一種基于MapReduce計(jì)算模型的并行閉頻繁項(xiàng)集挖掘算法MRClose。實(shí)驗(yàn)表明提出的算法實(shí)現(xiàn)了較好的均衡負(fù)載和低I/O量，在執(zhí)行效率和結(jié)果壓縮兩方面較并行頻繁項(xiàng)集挖掘算法具有更好的效果。

【關(guān)鍵詞】數(shù)據(jù)挖掘 并行 閉頻繁項(xiàng)集挖掘 MapReduce Hadoop

1 引言

頻繁項(xiàng)集挖掘（Frequent Itemset Mining，F(xiàn)IM）是最重要的數(shù)據(jù)挖掘任務(wù)之一，也是關(guān)聯(lián)規(guī)則、分類、聚集、關(guān)聯(lián)等眾多數(shù)據(jù)挖掘任務(wù)的基礎(chǔ)，自它被提出以來(lái)，受到了越來(lái)越多的關(guān)注。經(jīng)典的FIM算法可以分為三類：“產(chǎn)生-計(jì)數(shù)”方法如Apriori、DHP、DIC等、“模式增長(zhǎng)”方法如FP-Growth、LP-Tree、FIUT、IFP、FPL/TPL以及基于垂直數(shù)據(jù)格式的算法如Eclat等。閉頻繁項(xiàng)集（Closed Frequent Itemset，CFI）是頻繁項(xiàng)集的一種壓縮形式，在尺寸上比頻繁項(xiàng)集有較大地減少，消除了信息冗余且沒(méi)有信息丟失，有利于挖掘結(jié)果的進(jìn)一步使用。可以通過(guò)將FIM問(wèn)題轉(zhuǎn)換為CFIM問(wèn)題來(lái)提高頻繁項(xiàng)集挖掘效率。

與FIM類似，經(jīng)典的CFIM算法也可以分為三類：“產(chǎn)生-計(jì)數(shù)”方法如A-Close等、“模式增長(zhǎng)”方法如CLOSET、CLOSET+、AFOPT-Close等以及基于垂直數(shù)據(jù)格式的如CHARM等。隨著信息技術(shù)的飛速發(fā)展，人類已經(jīng)進(jìn)入了大數(shù)據(jù)時(shí)代，需要分析和挖掘的數(shù)據(jù)量呈爆炸式增長(zhǎng)，傳統(tǒng)的單機(jī)算法已經(jīng)不能滿足大數(shù)據(jù)挖掘的要求，主要挑戰(zhàn)是：?jiǎn)我挥?jì)算機(jī)無(wú)法存儲(chǔ)所需要挖掘的所有數(shù)據(jù)及挖掘過(guò)程中產(chǎn)生的中間結(jié)果；挖掘過(guò)程所需要的內(nèi)存遠(yuǎn)遠(yuǎn)超過(guò)單一機(jī)器的存儲(chǔ)量；計(jì)算時(shí)間太長(zhǎng)無(wú)法忍受等問(wèn)題。需要設(shè)計(jì)并行的CFIM算法解決上述問(wèn)題。

MapReduce是一種簡(jiǎn)單易用的并行編程模型，由Google于2004年提出，因其自動(dòng)容錯(cuò)、負(fù)載均衡、伸縮性好等優(yōu)點(diǎn)，已有很多數(shù)據(jù)挖掘方法實(shí)現(xiàn)了基于MapReduce計(jì)算模型的并行化，顯示出這種計(jì)算模式適用于多種并行數(shù)據(jù)挖掘任務(wù)。MapReduce計(jì)算模型流程圖如圖1所示。

Hadoop是MapReduce的一個(gè)開(kāi)源實(shí)現(xiàn)，其核心組件是一個(gè)分布式文件系統(tǒng)HDFS及MapReduce并行編程模型。HDFS自動(dòng)將海量數(shù)據(jù)進(jìn)行分片，分別存儲(chǔ)集群中不同的節(jié)點(diǎn)上；Map方法在存儲(chǔ)數(shù)據(jù)分片的節(jié)點(diǎn)運(yùn)行，通過(guò)數(shù)據(jù)本地化、減少IO來(lái)提高運(yùn)行的效率。

陳光鵬等提出了一種基于MapReduce的CFIM并行算法，實(shí)現(xiàn)了經(jīng)典算法AFOPT-Close算法的并行化，并討論了并行化后帶來(lái)的局部閉項(xiàng)集和全局閉項(xiàng)集不一致的問(wèn)題。Wang等將上述算法進(jìn)行了改進(jìn)，主要提升了檢查局部閉項(xiàng)集是否為全局閉項(xiàng)集的效率。Gonen等實(shí)現(xiàn)了一種基于MapReduce的CFIM并行算法，算法使用了A-Close的基本思想，通過(guò)迭代產(chǎn)生G1-Gk（長(zhǎng)度1～k的generators）及其閉項(xiàng)集，每一次迭代使用一個(gè)MapReduce任務(wù)實(shí)現(xiàn)，最后對(duì)所有計(jì)算得到的閉項(xiàng)集進(jìn)行重復(fù)檢查刪去重復(fù)項(xiàng)，得到全局閉項(xiàng)集。

本文設(shè)計(jì)了一種并行的全局閉頻繁項(xiàng)集篩選方法。提出了MRClose算法，該算法基于“模式增長(zhǎng)”方法的基本思想和搜索空間劃分策略，實(shí)現(xiàn)了對(duì)局部閉頻繁項(xiàng)集的并行過(guò)濾。

2 相關(guān)研究討論

Lucchese等提出了一個(gè)基于多核CPU的并行DCI-Closed算法MT-Closed，實(shí)現(xiàn)了CFIM的并行化，但該算法基于單一計(jì)算機(jī)的多線程架構(gòu)，線程的數(shù)量是有限的，線程之間需要共享內(nèi)存，海量數(shù)據(jù)無(wú)法裝入單一計(jì)算機(jī)的內(nèi)存中進(jìn)行計(jì)算； D-Closed算法與MT-Closed類似，通過(guò)迭代搜索子樹(shù)來(lái)搜索閉頻繁項(xiàng)集，是一個(gè)分布式的并行CFIM算法，但它仍需要在不同節(jié)點(diǎn)之間共享搜索索引及候選的閉頻繁項(xiàng)集。

已有一些研究將傳統(tǒng)CFIM算法向MapReduce計(jì)算模型進(jìn)行了遷移。陳光鵬等提出了一種基于MapReduce的CFIM并行算法，實(shí)現(xiàn)了經(jīng)典算法AFOPT-Close算法的并行化。它的設(shè)計(jì)思想和基于MapReduce的FIM算法PFP十分相似，通過(guò)三個(gè)MapReduce任務(wù)完成并行挖掘。文獻(xiàn)[9]通過(guò)減少第三個(gè)任務(wù)的I/O數(shù)據(jù)量進(jìn)一步提升了上述算法的性能。Gonen等提出的基于MapReduce的CFIM算法基于A-Close算法的基本思想，通過(guò)多次迭代產(chǎn)生長(zhǎng)度1～n的等價(jià)類最小閉項(xiàng)集G1～Gi及它們的閉包?，F(xiàn)有算法主要是將CFIM的經(jīng)典算法向MapReduce計(jì)算模型進(jìn)行了遷移，沒(méi)有從并行計(jì)算的負(fù)載均衡、降低I/O數(shù)據(jù)量等重要方面考慮CFIM并行化中關(guān)鍵問(wèn)題的策略選擇問(wèn)題。

3 提出算法

本文提出的算法MRClose基于“模式增長(zhǎng)”方法的基本思想和搜索空間劃分策略，算法使用FP-Tree壓縮存儲(chǔ)子搜索空間，在并行挖掘局部閉頻繁項(xiàng)集的過(guò)程中使用引理1、item skipping策略進(jìn)行剪枝，對(duì)局部挖掘結(jié)果使用引理2進(jìn)行校驗(yàn)。最后并行執(zhí)行全局閉頻繁項(xiàng)集的篩選，得到全局閉頻繁項(xiàng)集。

給定一個(gè)事務(wù)數(shù)據(jù)集D和最小支持度minsup，算法主要包含5個(gè)步驟，主要框架如下：

Step 1：數(shù)據(jù)分片及存儲(chǔ)。將數(shù)據(jù)集D分為若干個(gè)連續(xù)的分片，每個(gè)分片分別存儲(chǔ)在集群中的計(jì)算節(jié)點(diǎn)上，一個(gè)節(jié)點(diǎn)可以存儲(chǔ)一個(gè)或多個(gè)數(shù)據(jù)分片。這個(gè)過(guò)程可以由HDFS自動(dòng)完成。

Step 2：并行計(jì)數(shù)。并行計(jì)數(shù)是MapReduce計(jì)算模型的經(jīng)典用法，十分容易實(shí)現(xiàn)，可以使用一個(gè)MapReduce任務(wù)來(lái)統(tǒng)計(jì)D中所有項(xiàng)的支持度，得到頻繁項(xiàng)的集合FList。endprint

Step 3：分組頻繁項(xiàng)。若FList={I1，I2，…，In}，則整個(gè)搜索空間可以劃分為{g（I1）， g（I2），…，g（In）}n個(gè)子搜索空間。當(dāng)|FList|的值很大時(shí)，會(huì)在并行挖掘階段產(chǎn)生n個(gè)子挖掘任務(wù)，帶來(lái)極大的系統(tǒng)初始化成本、高I/O，也不利于負(fù)載均衡。為了減少子搜索空間的數(shù)量，可以將n個(gè)頻繁項(xiàng)進(jìn)行分組。設(shè)將n個(gè)頻繁項(xiàng)分成m組，第i組中有得頻繁項(xiàng)為{Ij，…，Ik}，則第i個(gè)子搜索空間為{g（Ij）∪，…，∪g（Ik）}，當(dāng)g（Ij）∩g（Ik）≠□時(shí)，可以減少子搜索空間的事務(wù)數(shù)，進(jìn)而可以減少節(jié)點(diǎn)之間的I/O數(shù)據(jù)量。為了進(jìn)一步實(shí)現(xiàn)負(fù)載均衡，可以根據(jù)頻繁項(xiàng)的支持度進(jìn)行平衡分組。

Step 4：生成子搜索空間，并行挖掘局部閉頻繁項(xiàng)集。這是算法最核心的步驟，使用一個(gè)MapReduce任務(wù)完成。Map方法輸入每一條事務(wù)數(shù)據(jù)Ti，將Ti中非頻繁項(xiàng)刪去，剩下的頻繁項(xiàng)按照FList中項(xiàng)的順序進(jìn)行排序得到Ti。若Ti中的所有項(xiàng)分屬于m個(gè)組，則針對(duì)每個(gè)組輸出<組號(hào)， Ti>，實(shí)際上生成的是所有子搜索空間。每一個(gè)Reduce處理一個(gè)組號(hào)相關(guān)的所有事務(wù)，構(gòu)造FP-Tree后，使用FP-Grwoth算法進(jìn)行挖掘，在挖掘過(guò)程中運(yùn)用剪枝策略加快挖掘過(guò)程。最后該階段得到的是所有的局部閉頻繁項(xiàng)集。

Step 5：過(guò)濾得到全局閉頻繁項(xiàng)集。該階段可以使用一個(gè)MapReduce并行執(zhí)行。Map方法讀取每一個(gè)局部閉頻繁項(xiàng)集，輸出。每一個(gè)Reduce方法處理同一支持度的所有項(xiàng)集，運(yùn)用引理2對(duì)上述所有項(xiàng)集進(jìn)行子集檢查將非全局閉項(xiàng)集刪去，可以使用前綴樹(shù)來(lái)加快子集檢查的速度。

4 實(shí)驗(yàn)結(jié)果分析

實(shí)驗(yàn)環(huán)境使用基于MapReduce計(jì)算模型的開(kāi)源系統(tǒng)Hadoop 1.2.1做為平臺(tái)搭建集群，具體方案為如下：使用1臺(tái)計(jì)算機(jī)做為Master節(jié)點(diǎn)，CPU為 i7-4790 3.60Gz 8核，內(nèi)存8G，操作系統(tǒng)為Red Hat Enterprise Linux Server 6.6，Java平臺(tái)為Java 1.6；使用6臺(tái)計(jì)算機(jī)做為Slave節(jié)點(diǎn)，CPU為 i3-4150 3.50Gz 4核，內(nèi)存4G，操作系統(tǒng)為Red Hat Enterprise Linux Server 6.6，Java平臺(tái)為Java 1.6。集群計(jì)算機(jī)之間使用百兆以太網(wǎng)相互連接。

為了適應(yīng)實(shí)驗(yàn)數(shù)據(jù)集尺寸較小，提高并行化程序以優(yōu)化集群的性能，實(shí)驗(yàn)環(huán)境將HDFS文件塊的大小設(shè)置為256KB（默認(rèn)為64MB）以增加Map任務(wù)數(shù)；將reduce任務(wù)數(shù)設(shè)置為12以充分利用每個(gè)計(jì)算節(jié)點(diǎn)的計(jì)算能力（平均每個(gè)節(jié)點(diǎn)執(zhí)行2個(gè)reduce任務(wù)）。使用Java語(yǔ)言編寫(xiě)PFP和MRClose算法，比較兩個(gè)算法的效率及結(jié)果壓縮率。使用的實(shí)驗(yàn)數(shù)據(jù)集特征如表1所示。

retail是來(lái)自于FIMI的真實(shí)數(shù)據(jù)集，是一個(gè)非常稀疏的數(shù)據(jù)集；T10I4D100K是一個(gè)使用IBM Quest Data Generator生成的合成數(shù)據(jù)，相對(duì)來(lái)說(shuō)比retail要密集一些。

4.1 實(shí)驗(yàn)結(jié)果分析

PFP和MRClose算法在retail數(shù)據(jù)集上最小支持度分別為0.01%、0.025%、0.05%時(shí)的執(zhí)行時(shí)間如圖2所示。

PFP和MRClose算法在retail數(shù)據(jù)集上最小支持度分別為0.01%、0.025%、0.05%時(shí)的結(jié)果集尺寸如圖3所示。

從圖2和圖3可以看出：

（1）MRClose算法在稀疏數(shù)據(jù)集上的加速性十分有限，主要原因在于由稀疏數(shù)據(jù)壓縮得到的FP-Tree具有分支很多、共享前綴很少的特征，運(yùn)用剪枝策略減去的搜索空間在總搜索空間中的比重很低，對(duì)算法加速性貢獻(xiàn)有限。

（2）MRClose算法在稀疏數(shù)據(jù)集上仍表現(xiàn)出了較好的結(jié)果壓縮比例，壓縮率與最小支持度呈反比。

PFP和MRClose算法在T10I4D100K數(shù)據(jù)集最小支持度分別為上1%、2%、5%時(shí)的執(zhí)行時(shí)間如圖4所示。

PFP和MRClose算法在T10I4D100K數(shù)據(jù)集最小支持度分別為上1%、2%、5%時(shí)的執(zhí)行的結(jié)果集尺寸如圖5所示。

從圖4和圖5可以看出：

（1）MRClose算法在密集數(shù)據(jù)集上的加速性比在稀疏數(shù)據(jù)集上有所提高，加速性與數(shù)據(jù)集的密集程度呈正比，與最小支持度也成正比，主要原因在于由密集數(shù)據(jù)壓縮得到的FP-Tree具有更多的共享前綴，共享前綴越多，運(yùn)用剪枝策略減去的子搜索空間也越大，對(duì)算法加速性貢獻(xiàn)越大。

（2）數(shù)據(jù)集越密集，|L|和|G|之間的差值則越小，算法壓縮率與最小支持度呈反比。

（3）從圖2和圖4可以看到，由于MRClose算法采用了均衡分組的策略，實(shí)現(xiàn)了較好的負(fù)載均衡。但在并行計(jì)算中，對(duì)算法效率有決定性影響的已不在是單個(gè)節(jié)點(diǎn)的計(jì)算效率，負(fù)載均衡、I/O數(shù)據(jù)量有更加顯著的影響。在挖掘L時(shí)雖然運(yùn)用了剪枝策略，但對(duì)整個(gè)算法的效率提升作用仍是比較有限的。

5 總結(jié)

本文討論了并行CFIM算法在搜索空間劃分、剪枝策略、全局閉頻繁檢查這三個(gè)關(guān)鍵方面的策略選擇，提出了一種基于MapReduce計(jì)算模型的并行CFIM算法，算法MRClose基于“模式增長(zhǎng)”方法的基本思想和搜索空間劃分策略，采用FP-Tree壓縮存儲(chǔ)子搜索空間，在并行挖掘局部閉頻繁項(xiàng)集的過(guò)程中進(jìn)行了剪枝，對(duì)局部挖掘結(jié)果進(jìn)行了并行篩選。實(shí)驗(yàn)驗(yàn)證了MRClose算法在負(fù)載均衡、算法加速、全局結(jié)果集篩選等方面的有效性。算法持續(xù)改進(jìn)可以從兩個(gè)方面來(lái)考慮：

（1）子搜索空間劃分采用更加有效的數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)，提高并行挖掘L的效率（特別是針對(duì)稀疏數(shù)據(jù)集提高剪枝策略的效率）；

（2）從L中并行篩選G時(shí)進(jìn)一步考慮負(fù)載均衡的問(wèn)題。

參考文獻(xiàn)

[1]Han Jiawei，Kamber M.Data Mining： Concepts and Techniques[M].London，UK： Morgan Kaufmann，2006.

[2]N.Pasquier，Y.Bastide，R.Taouil，and L. Lakhal，Discovering frequent closed itemsets for association rules， Database Theory-ICDT99，1999，398-416.

[3]Pei Jian，Han Jiawei，Mao Runying. CLOSET：an efficient algorithm for mining frequent closed itemsets[C].Proc of the ACM SIG-MOD International Workshop on Data Mining and Knowledge Dis-covery.Dallas，USA，2000：21-30.

[4]Wang Jianyong，Han Jiawei，Pei Jian.CLOSET +：Searching for the best strategies for mining frequent closed itemsets[C].Proc of the 9th ACM SIGKDD International Conference on Knowledge Dis-covery and Data Min-ing.Washington，USA，2003：236-245.

[5]M.J.Zaki and C.Hsiao.CHARM：An efficient algorithm for closed itemset mining.Technical Report 99-10，Rensselaer Polytechnic Institute，1999.

[6]Liu Guimei，Lu Hongjun，Xu Yabo，et al.Ascending frequency ordered prefixtree：efficient mining of frequent patterns[C].Proc of the 8th International Conference on Database Systems for AdvancedApplica-tions.Kyoto，Japan，2003：65-72.

[7]Welcome to ApacheHadoop！[EB/OL].[2017-01-10].http：//hadoop.apache.org/.

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

[9]Wang S Q，Yang Y B，Chen G P，et al.MapReduce-based closed frequent itemset mining with efficient redundancy filtering[C].Proc of IEEE，International Conference on Data Mining Workshops.IEEE Computer Society，2012：449-453.

[10]C.Lucchese，S.Orlando，and R.Perego， Parallel mining of frequent closed patterns：harnessing modern computer architectures in DataMining[C]//Proc of ICDM 2007.Seventh IEEE International Conference on.IEEE，2007，pp.242-251.

作者單位

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