□ 趙明

基于傳遞收縮剪枝策略的并行頻繁項(xiàng)集挖掘算法的研究

□ 趙明

關(guān)聯(lián)分析作為數(shù)據(jù)挖掘中探尋事物之間聯(lián)系緊密程度的方式之一，被廣泛應(yīng)用于商業(yè)，社交分析等領(lǐng)域，其中如何高效挖掘到頻繁項(xiàng)集一直都是研究重點(diǎn)。FP-growth以頻繁模式樹FP-tree為數(shù)據(jù)結(jié)構(gòu)，極大降低了I/O吞吐，且利用并行計(jì)算，提高了計(jì)算效率。但因其需要占用大量?jī)?nèi)存，使得并行規(guī)模受到限制。本文設(shè)計(jì)了基于傳遞收縮剪枝策略的FP-growth算法，通過限制FP-tree的搜索空間，及時(shí)進(jìn)行剪枝項(xiàng)合并，并將其在分布式平臺(tái)Spark并行化。通過實(shí)驗(yàn)對(duì)比證明，較Hadoop上提升25%；相比原有的FP-growth算法PFP，在Spark平臺(tái)計(jì)算提升10%左右。

FP-growth算法；頻繁項(xiàng)集挖掘；傳遞收縮剪枝策略；Spark；

關(guān)聯(lián)規(guī)則作為尋找海量數(shù)據(jù)中事物聯(lián)系緊密程度的方法之一，隨著近幾年電子商務(wù)的迅猛發(fā)展，在商業(yè)領(lǐng)域中，顯示出了強(qiáng)大的生命力。而對(duì)頻繁項(xiàng)集的挖掘，作為關(guān)聯(lián)規(guī)則的核心思想，已成為各類學(xué)者研究的焦點(diǎn)。但當(dāng)其面對(duì)互聯(lián)網(wǎng)的海量數(shù)據(jù)時(shí)，計(jì)算量和I/O量都非常大，傳統(tǒng)的串行算法已不能勝任，通過并行化頻繁項(xiàng)集挖掘算法拓展它們的使用場(chǎng)景。

頻繁項(xiàng)集挖掘算法FP-growth，雖降低了對(duì)數(shù)據(jù)庫的I/ O，但其在構(gòu)建樹形結(jié)構(gòu)時(shí)，仍占用了大量的內(nèi)存資源。雖可以使用并行化可以緩解其過高的內(nèi)存占用，但因其依賴進(jìn)程間的通信來協(xié)調(diào)樹形變化，往往導(dǎo)致并行計(jì)算效率較低、內(nèi)存開銷大且不能夠?qū)崿F(xiàn)多節(jié)點(diǎn)的橫向擴(kuò)展。對(duì)此本文提出了如下創(chuàng)新點(diǎn)：

（1）TCPFP(Transitive Compression Pruning FP-growth algorithm)算法利用了傳遞收縮剪枝策略對(duì)FP-growth頻繁項(xiàng)集的搜索空間進(jìn)行限制，通過傳遞收縮剪枝，及時(shí)進(jìn)行項(xiàng)合并，降低了內(nèi)存占用，提高算法挖掘速度。

（2）在Spark平臺(tái)上并行化了基于傳遞收縮剪枝的FP-growth算法TCPFP。利用其彈性分布式數(shù)據(jù)集及基于內(nèi)存計(jì)算模式，在對(duì)比傳統(tǒng)的FP-growth算法在Hadoop或Spark平臺(tái)的挖掘效率上，提升挖掘效率10%。

一、關(guān)聯(lián)規(guī)則挖掘算法

Apriori算法作為關(guān)聯(lián)規(guī)則的經(jīng)典挖掘算法之一，利用了頻繁項(xiàng)集的先驗(yàn)知識(shí)。將頻繁項(xiàng)集中任意一非空子集劃為頻繁項(xiàng)集。但其運(yùn)算過程中，需要占用巨大的I/O，拼接產(chǎn)生過多的候選集，效率不高。之后也有利用動(dòng)態(tài)項(xiàng)集計(jì)數(shù)算法DIC(Dynamic Itemset Counting)；或是采用分治法的思想來解決內(nèi)存不夠用的分塊挖掘算法(Partition)等。

相比Apriori算法，2000年提出FP-growth算法以頻繁模式樹為基礎(chǔ)，只掃描兩次數(shù)據(jù)庫，大大降低了I/O吞吐。采用深度優(yōu)先的搜索方式，提高挖掘效率。FP-growth算法有兩個(gè)主要步驟：1.頻繁模式樹FP-tree的構(gòu)造；2.對(duì)FP-tree進(jìn)行頻繁模式挖掘。FP-tree構(gòu)造時(shí)，將數(shù)據(jù)庫中所有的記錄信息壓縮進(jìn)去，保留每條交易記錄中數(shù)據(jù)項(xiàng)之間的聯(lián)系。通過掃描數(shù)據(jù)庫，計(jì)算出所有的頻繁1-項(xiàng)集，并按支持度計(jì)數(shù)排序，刪去小于最小支持度的頻繁項(xiàng)；再來插入到FP-tree中，通過共享相同的數(shù)據(jù)項(xiàng)前綴，把項(xiàng)頭表(Header table)中的每個(gè)頻繁項(xiàng)鏈接到FP-tree中去。然后，對(duì)頻繁模式進(jìn)行挖掘。若FP-tree中的含有單個(gè)路徑L，則直接抽取條件模式基；若不包含單個(gè)路徑，則對(duì)項(xiàng)頭表中每個(gè)元素生成條件模式。然后構(gòu)造其元素的條件模式基和條件模式樹，若條件模式樹不為空，則遞歸找出所有的頻繁項(xiàng)集。

傳統(tǒng)單線程遞歸挖掘頻繁項(xiàng)集，效率底下，隨著Ha?doop分布式并行執(zhí)行的思想流傳開來。國(guó)內(nèi)外學(xué)者，將頻繁項(xiàng)集挖掘與并行化結(jié)合起來，展開多方面的研究。Rion?dato等人將FP-growth算法以Hadoop框架為基礎(chǔ)研究提出了PARMA算法，主要是采用減小事務(wù)集的大小從而得到時(shí)間上的節(jié)省。或利用數(shù)據(jù)本地化的思想減少FP-growth算法在Hadoop中的網(wǎng)絡(luò)通信量。還有針對(duì)FP-tree和項(xiàng)頭表的數(shù)據(jù)結(jié)構(gòu)進(jìn)行改進(jìn)以及對(duì)單路徑問題進(jìn)行優(yōu)化，并在Spark上并行實(shí)現(xiàn)的。但因其在內(nèi)存中占用大量空間構(gòu)建樹形結(jié)構(gòu)，會(huì)使其因數(shù)據(jù)項(xiàng)過多或過深導(dǎo)致FP-tree構(gòu)造失敗，或遞歸構(gòu)建了空間復(fù)雜度過高的條件模式基。即便其利用了分布式計(jì)算平臺(tái)，也需要消耗大量?jī)?nèi)存用于維護(hù)樹形的進(jìn)程通訊，會(huì)使得分布式節(jié)點(diǎn)難以橫向拓展，并行優(yōu)勢(shì)無法徹底發(fā)揮出來。因此本文針對(duì)FP-growth算法內(nèi)存占用高，搜索空間復(fù)雜，引入傳遞收縮剪枝策略對(duì)搜索空間進(jìn)行限制，使得其在分布式平臺(tái)Spark上有著較高的挖掘效率。

二、基于傳遞收縮剪枝策略的FP-growth算法TCPFP

1.符號(hào)定義及理論證明

在挖掘頻繁項(xiàng)集中，我們定義葉子節(jié)點(diǎn)上的頻繁項(xiàng)y。在FP-tree上，以y為起點(diǎn)，倒序遍歷直到root的一串節(jié)點(diǎn)序列，我們稱為y的傳遞路徑R。即y和root節(jié)點(diǎn)的之間連接的一條路徑，包含y本身以及root節(jié)點(diǎn)。一般的對(duì)于頻繁項(xiàng)y，不止一條傳遞路徑R。通過對(duì)傳遞路徑進(jìn)行收縮，刪去頻繁項(xiàng)y，作為y的傳遞收縮路徑，簡(jiǎn)稱收縮路徑Rc。

Figure 1 Schematic diagram of FP-tree圖1：FP-tree示意圖

如上圖所示，假設(shè)y為I3，則有R為{I3,I2,I4,Root},{I3, I5,I4,Root},{I3,I1,I5,I4,Root}三條路徑。而對(duì)于I5來說，其傳遞路徑只有一條{I5,I6,Root}。同理，我們可以得到頻繁項(xiàng)I3的收縮路徑Rc為{I2,I4,Root}，{I5,I4,Root}，{I1,I5,I4, Root}，而I5的收縮路徑為{I6,Root}。

剪枝策略：傳遞收縮剪枝TCP。若頻繁項(xiàng)y存在多條收縮路徑Rc1到Rcn，路徑之間存在非空交集。通過提取交集，合并收縮路徑，將頻繁項(xiàng)y的支持度累加計(jì)算，收縮路徑的起點(diǎn)頻繁項(xiàng)，減去因?yàn)槭湛s合并移除的支持度。

證明：若包含頻繁項(xiàng)y的N個(gè)頻繁項(xiàng)集中存在包含關(guān)系，如A包含B。但A不包含B的任何真超集，則令A(yù)∪B形成一個(gè)閉頻繁項(xiàng)集。因此在兩個(gè)頻繁項(xiàng)集A,B中，y的收縮路徑Rc1和Rc2存在交集路徑Ry。則FP-tree在剪枝之前得到y(tǒng)的條件模式基為{{Rc1：m},{Rc2：n}}，產(chǎn)生的頻繁模式為{Ry：m+n}。FP-tree在剪枝之后得到y(tǒng)的條件模式基為{Rc1∩Rc2：m+n}，產(chǎn)生的頻繁模式為{Ry：m+n}。FP-tree在剪枝之后與剪枝前得到包含y的頻繁模式一樣。因此，下界路徑Rc2就可以剪枝合并在路徑Rc1上。

所以根據(jù)剪枝策略，對(duì)I3進(jìn)行剪枝，則有三條收縮路徑的Rc的交集為{I4,Root}，所以經(jīng)過剪枝和項(xiàng)合并之后有R{I3,I4,Root}，生成的條件模式基為{I3,I4,Root：6}。

2.算法流程設(shè)計(jì)

在建立好頻繁模式樹FP-tree之后，我們可以利用傳遞收縮剪枝策略TCP來對(duì)FP-tree進(jìn)行剪枝和挖掘，其操作步驟如下：

第一步：判斷建立好的FP-tree是否包含無分支的單路徑，若存在單路徑R，把該路徑R中每個(gè)元素和模式合并生成頻繁項(xiàng)集，條件模式基即為生成的頻繁模式記為{R：m}，m為路徑R中節(jié)點(diǎn)的支持度。

第二步：從底部開始遍歷FP-tree的項(xiàng)頭表Header ta?ble，得到每個(gè)葉子節(jié)點(diǎn)上的頻繁項(xiàng)y的傳遞路徑R，并將所有傳遞路徑按頻繁項(xiàng)統(tǒng)計(jì)出來，得到所有頻繁項(xiàng)y在FP-tree上的傳遞路徑R1～Rn。

第三步：將傳遞路徑進(jìn)行收縮，在對(duì)應(yīng)頻繁項(xiàng)路徑集合中，刪去該頻繁項(xiàng)y，獲得收縮路徑Rc1到Rcn。

第四步：尋找每個(gè)頻繁項(xiàng)的收縮路徑中是否存在交集，若存在提取交集，剪枝合并，將支持度疊加的同時(shí)減去上一級(jí)的支持度。

第五步：檢查FP-tree經(jīng)過剪枝合并后，判斷頻繁項(xiàng)是否存在多條傳遞路徑，若是回到第一步，如果不是則繼續(xù)向下執(zhí)行第六步。

第六步：對(duì)項(xiàng)頭表中的每個(gè)頻繁項(xiàng)y，生成頻繁模式記為{Ry：m}，該模式中的m等于y的支持度。

根據(jù)算法TCPFP，圖1中的FP-tree有I3和I1作為葉子節(jié)點(diǎn)上的頻繁項(xiàng)，其收縮路徑存在交集，其中I3提取交集之后其路徑R為{I3,I4,Root}，I1為{I1,Root}。在進(jìn)行項(xiàng)合并時(shí)，與I3直連枝干節(jié)點(diǎn)，支持度會(huì)降低。所以可以看到，原有的I2,I5會(huì)因I3合并，支持度分別將至0和1。剪去支持度為0的枝干，構(gòu)成新的FP-tree如圖2。

Figure 2 The FP-tree after pruning圖2：經(jīng)修剪之后的FP-tree

三、Spark并行化

Spark作為分布式并行數(shù)據(jù)處理框架，利用了MapRe?duce計(jì)算思想，將job基于內(nèi)存模式進(jìn)行并行計(jì)算，省去了Hadoop中大量的磁盤上的I/O。對(duì)于FP-growth算法的并行化，主要通過并行投影的方式對(duì)數(shù)據(jù)庫進(jìn)行劃分，再對(duì)每個(gè)投影數(shù)據(jù)庫進(jìn)行FP-growth處理。按照MapReduce的計(jì)算思想，操作分為三步。

第一步：數(shù)據(jù)切分與并行計(jì)數(shù)。這里不同的分布式計(jì)算平臺(tái)會(huì)有著不同的方案，Hadoop會(huì)利用HDFS設(shè)定的block（通常為64MB）來切分存儲(chǔ)在不同的DataNode的節(jié)點(diǎn)磁盤上；Spark會(huì)利用彈性式數(shù)據(jù)分布集RDD將數(shù)據(jù)庫中的數(shù)據(jù)序列化后引入內(nèi)存。然后，我們可以通過Mapper方法將每個(gè)投影數(shù)據(jù)庫中的項(xiàng)并行統(tǒng)計(jì)，得到形如＜key=”items”，value=”sum”＞的鍵值對(duì)；通過Reducer方法對(duì)所有鍵值對(duì)按照value值排序，刪除不滿足最小支持度的鍵值對(duì)。

第二步：均衡分組。將每個(gè)投影數(shù)據(jù)庫中的頻繁項(xiàng)gid均衡分組，使得分布式處理能力相差不大，并將分組情況寫到一個(gè)頻繁項(xiàng)分組表Glist中去。

第三步：FP-growth挖掘。利用多個(gè)job在不同的主機(jī)上分別處理不同的投影數(shù)據(jù)庫。Mapper端根據(jù)Glist來產(chǎn)生互不依賴的事務(wù)記錄。Reducer端對(duì)這些來自不同分組的數(shù)據(jù)庫建立FP-tree進(jìn)行頻繁項(xiàng)集挖掘。

算法TCPFP在Spark上面并行化的時(shí)，會(huì)在第三步操作有所不同，即頻繁項(xiàng)集的挖掘。其具體操作：

（1）map。讀取Glist到內(nèi)存中，刪掉不在其投影上的頻繁項(xiàng)，并根據(jù)出現(xiàn)順序，將事務(wù)T中的前n項(xiàng)作為一個(gè)事務(wù)保留到gid的分組中去。生成形如＜key=“gid”，value= {t1,t2,…,tn}＞的鍵值對(duì)。

（2）combiner。將上一步并行分組后的互不依賴的事務(wù)記錄，利用Combiner將鍵值對(duì)中key值一樣的進(jìn)行合并。方便后期生成FP-tree。

（3）reduceByKey。根據(jù)事務(wù)組中的記錄，創(chuàng)建本地FP-tree。利用基于傳遞收縮剪枝策略的FP-growth算法限制搜索空間進(jìn)行頻繁項(xiàng)的挖掘。輸出形如＜key=“num”，value=“itemsets”＞的鍵值對(duì)。

圖3為整個(gè)FP-growth在Spark上并行化的流程示意圖。通過從HDFS中讀取數(shù)據(jù)庫信息之后，Spark將整個(gè)計(jì)算過程包括中間結(jié)果都運(yùn)行在內(nèi)存上。降低了頻繁的I/O。

Figure3 The process of FP-growth algorithm parallel exe?cution on Spark圖3：FP-growth算法在Spark上并行執(zhí)行的流程

相比于Hadoop將每一步的中間結(jié)果都會(huì)輸出到HDFS中進(jìn)行存儲(chǔ)，一般HDFS都是由位于機(jī)架上的磁盤陣列構(gòu)成，這個(gè)讀取寫入會(huì)占用大量的時(shí)間，降低處理效率。Spark利用了基于內(nèi)存的讀寫模式，使得整體計(jì)算挖掘效率大幅提高。

四、實(shí)驗(yàn)結(jié)果及分析

為了驗(yàn)證TCPFP算法的有效性，本文設(shè)計(jì)了在分布式并行計(jì)算的環(huán)境下對(duì)比，原有的PFP（FP-growth）算法與TCPFP算法，以及TCPFP在Spark以及Hadoop平臺(tái)上的不同。

實(shí)驗(yàn)利用了4臺(tái)主機(jī)搭建而成的Hadoop集群，統(tǒng)一安裝ubuntu14.04運(yùn)行Hadoop2.6和Saprk1.5.2。使用JDK版本為1.8，Scala2.11.7。通過局域網(wǎng)將集群連接起來。采用電子商務(wù)網(wǎng)站的訂單數(shù)據(jù)集總計(jì)400W條，通過復(fù)制拷貝增加數(shù)據(jù)集量。其四臺(tái)主機(jī)的節(jié)點(diǎn)分布具體配置如表1.

Table 1 Experimental environment configuration表1 實(shí)驗(yàn)環(huán)境配置

通過配置不同的數(shù)據(jù)集大小，我們獲得如圖4中的測(cè)試結(jié)果?？梢詫?duì)比看出原有的PFP算法在Spark上運(yùn)行時(shí)間，以及TCPFP在Hadoop和Spark上面運(yùn)行時(shí)間的對(duì)比。

Figure4 The mining time of PFP and TCPFP on distribut?ed platforms圖4：PFP及TCPFP在各分布式平臺(tái)上的挖掘時(shí)間

可以很明顯地看出Spark在對(duì)比Hadoop時(shí)有明顯效率提升，約為25%以上的提升。利用了收縮剪枝策略的TCP?FP，比傳統(tǒng)的頻繁項(xiàng)集挖掘算法快10%左右。另外，我們?cè)跀?shù)據(jù)集拷貝4份達(dá)2000W條時(shí)，設(shè)立一組PFP與TCPFP的對(duì)比試驗(yàn)。針對(duì)性的分析對(duì)比其在各個(gè)Spark中各個(gè)階段的用時(shí)長(zhǎng)短。

Figure5 The comparison of operation time between PFP and TCPFP on Spark platform圖5：Spark平臺(tái)上PFP與TCPFP各階段運(yùn)算時(shí)間比較

從圖5中可以看出，將TCPFP與PFP算法分步驟比較時(shí)，map和combiner階段區(qū)別不大，其主要就是reduce?ByKey階段，說明算法TCPFP能通過及時(shí)項(xiàng)合并與剪枝，減少了約12%的挖掘時(shí)間。

五、總結(jié)

針對(duì)原有頻繁項(xiàng)集挖掘中的迭代次數(shù)多運(yùn)算量，本文利用了Spark分布式平臺(tái)，將原PFP算法進(jìn)行并行計(jì)算。面對(duì)并行計(jì)算中的樹規(guī)模變大導(dǎo)致的內(nèi)存占用大，效率下降等問題，設(shè)計(jì)了基于傳遞收縮剪枝策略的TCPFP算法，實(shí)驗(yàn)對(duì)比了Hadoop平臺(tái)中TCPFP，以及Spark平臺(tái)中PFP的運(yùn)算結(jié)果，證明TCPFP算法相比于PFP在Saprk平臺(tái)上提升了挖掘效率10%左右。

[1]孟小峰，慈祥.大數(shù)據(jù)管理：概念、技術(shù)與挑戰(zhàn)[J].計(jì)算機(jī)研究與發(fā)展，2013，50（1）.

[2]LAMINE M，NHIEN L，TAHAR M.Distributed Fre?quent Itemsets Mining in Heterogeneous Platforms[J]. Journal of Engineering，Computing and Architecture，2007，1(2)：1-12.

[3]Agrawal R，Srikant R.Fast algorithms for mining asso?ciation rules.20[J].Proc.int.conf.very Large Databases Vldb，1994，23(3)：21-30.

[4]Brin S，Motwani R，Ullman J D，et al.Dynamic itemset counting and implication rules for market basket data [J].Acm Sigmod Record，2001，26(2)：255-264.

[5]Savasere A，Omiecinski E，Navathe S B.An Efficient Algorithm for Mining Association Rules in Large Data?bases[J].Vldb Journal，1995：432-444.

[6]Han J，Pei J，Yin Y.Mining frequent patterns without candidate generation[J].Acm Sigmod Record，2000，29 (2)：1-12.

[7]馬月坤，劉鵬飛，張振友,等.改進(jìn)的FP-Growth算法及其分布式并行實(shí)現(xiàn)[J].哈爾濱理工大學(xué)學(xué)報(bào)，2016，(2).

[8]Riondato M，Debrabant J A，F(xiàn)onseca R，et al.PAR?MA：A Parallel Randomized Algorithm for Approxi?mateAssociationRulesMininginMapReduce[C]// Proceedingsofthe21stACMInternationalConfer?enceonInformationandKnowledgeManagement (CIKM 2012).2012：85-94.

[9]章志剛,吉根林.一種基于FP-Growth的頻繁項(xiàng)目集并行挖掘算法[J].計(jì)算機(jī)工程與應(yīng)用，2014，（2）.

[10]鄧玲玲，婁淵勝，葉楓.FP-growth算法改進(jìn)與分布式Spark研究[J].微型電腦應(yīng)用，2016，32（5）.

[11]HAN Jiawei，KAMBER Micheline.數(shù)據(jù)挖掘：概念與技術(shù)[M].北京：機(jī)械工業(yè)出版社，2013.

[12]謝朋峻.基于MapReduce的頻繁項(xiàng)集挖掘算法的并行化研究[D].南京：南京大學(xué)，2012.

[13]Duong Q H，Liao B，F(xiàn)ournier-Viger P，et al.An effi?cient algorithm for mining the top-k，high utility itemsets，usingnovelthresholdraisingandpruning strategies[J].Knowledge-Based Systems，2016，104：106-122.

責(zé)任編輯：夏曉暢

湖北省咸寧市公安局。

TP392

A

2095-5103（2016）20-0079-04

10.11907/rjdk.1511517