胡娟

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

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

1 引言

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

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

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

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

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

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

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

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

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

3 提出算法

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

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

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

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

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

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

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

4 實驗結(jié)果分析

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

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

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

4.1 實驗結(jié)果分析

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

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

從圖2和圖3可以看出：

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

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

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

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

從圖4和圖5可以看出：

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

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

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

5 總結(jié)

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

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

（2）從L中并行篩選G時進一步考慮負載均衡的問題。

參考文獻

[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]陳光鵬，楊育彬，高陽等.一種基于MapReduce的頻繁閉項集挖掘算法[J].模式識別與人工智能，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.

作者單位

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