顧軍華，武君艷，許馨勻，謝志堅，張素琪

(1.河北工業(yè)大學(xué) 人工智能與數(shù)據(jù)科學(xué)學(xué)院,天津 300401； 2.河北省大數(shù)據(jù)計算重點實驗室(河北工業(yè)大學(xué)), 天津 300401；3.天津商業(yè)大學(xué) 信息工程學(xué)院, 天津 300134)(*通信作者電子郵箱zhangsuqie@163.com)

0 引言

Apriori算法是挖掘頻繁項集最有影響和最具有代表性的一種算法，但該算法需要多次掃描數(shù)據(jù)庫，同時產(chǎn)生大量的候選集[1]。基于此，Han等[2]提出了一種不產(chǎn)生候選項集的頻繁模式增長(Frequent Pattern-Growth, FP-Growth)算法，通過生成的頻繁1-項集列表——F-List來構(gòu)建一棵頻繁模式樹(Frequent Pattern-Tree, FP-Tree)，繼而挖掘出所有的頻繁項集，并且在挖掘過程中只對數(shù)據(jù)庫進行兩次掃描，使得挖掘效率以及空間復(fù)雜度方面均有很大改進。當(dāng)數(shù)據(jù)量較小時，基于FP-Growth算法的改進算法[3]具有一定優(yōu)勢；隨著計算規(guī)模不斷增大，串行FP-Growth算法會因硬件資源的限制遇到內(nèi)存瓶頸或者失效的問題[4]，基于分布式計算框架的大數(shù)據(jù)平臺成為解決這一問題的一個重要途徑。

基于MapReduce計算框架的Hadoop大數(shù)據(jù)平臺，是一種用于分布式并行環(huán)境中處理大規(guī)模數(shù)據(jù)的計算模型[5]。繼Li等[6]在2008年第一次提出了基于MapReduce的FP-Growth算法——并行FP-Growth (Parallel FP-Growth, PFP)算法之后，不少學(xué)者對基于Hadoop的FP-Growth算法進行改進。文獻[5,7-8]實現(xiàn)了FP-Growth并行化算法改進，主要針對并行實現(xiàn)方式和構(gòu)建新的FP-Tree兩個方面。與Hadoop平臺相比，Spark大數(shù)據(jù)平臺是基于彈性分布式數(shù)據(jù)集(Resilient Distributed Datasets, RDD)內(nèi)存的編程框架[9]。2015年，Deng等[10]首次提出了一種基于Spark框架和改進FP-Growth算法的分布式DFP算法，通過在鏈頭表結(jié)構(gòu)中加入一張哈希表以達到快速訪問地址的目的，實驗證明，與PFP算法相比，DFP算法更高效，集群和數(shù)據(jù)伸縮性更好; 2016年，方向等[11]提出了在Spark平臺上根據(jù)不同分組的計算量進行均衡分組思想的改進算法，實驗證明優(yōu)化后的算法要比PFP效率更高; 2016年，Li等[12]通過修改支持度對高置信度數(shù)據(jù)進行過濾，并將基于Spark的改進FP-Growth算法應(yīng)用于電信網(wǎng)絡(luò)中，證明改進算法模式更有效; 2017年，張穩(wěn)等[13]提出一種基于事務(wù)中項間聯(lián)通權(quán)重矩陣的負載平衡并行頻繁模式增長算法，實驗證明該算法高效并有良好的可擴展性; 2017年，陸可等[14]基于Spark框架，通過對支持度計數(shù)和分組過程對FP-Growth算法進行改進，實驗證明經(jīng)優(yōu)化后的算法在面向大規(guī)模數(shù)據(jù)時要優(yōu)于傳統(tǒng)FP-Growth算法。

綜上，基于Hadoop的FP-Growth算法改進主要體現(xiàn)在FP-Tree挖掘方式和并行化實現(xiàn)兩個方面；基于Spark的FP-Growth算法改進主要針對優(yōu)化F-List結(jié)構(gòu)和負載均衡兩方面。盡管已經(jīng)有一些基于Spark的并行化FP-Growth優(yōu)化算法，但是在優(yōu)化F-List分組時，考慮了計算量和不同項之間權(quán)重對挖掘效率的影響而并未考慮空間復(fù)雜度問題，同時也沒有考慮數(shù)據(jù)集進行劃分時的時間復(fù)雜度問題。本文提出了基于Spark的改進算法——BFPG(Better Frequent Pattern-Growth)算法：首先，通過綜合考慮不同分區(qū)計算量和FP-Tree規(guī)模大小兩種因素對F-List分組策略做了優(yōu)化；然后，對數(shù)據(jù)集劃分策略進行改進，通過減少遍歷次數(shù)從而降低時間復(fù)雜度；最后，運用Spark中豐富的算子對優(yōu)化算法進行實現(xiàn)。

1 FP-Growth算法描述

FP-Growth是針對Apriori算法效率瓶頸提出的改進算法，用一棵FP-Tree存儲數(shù)據(jù)庫中的事務(wù)，在不產(chǎn)生候選項集的基礎(chǔ)上生成頻繁項集。算法通過生成頻繁1-項集列表——F-List構(gòu)建FP-Tree，同時采用遞歸策略對FP-Tree進行挖掘。在整個挖掘過程中，只對數(shù)據(jù)集進行兩次掃描。FP-Growth算法挖掘頻繁項集的過程分為兩步：首先構(gòu)造一棵FP-Tree，然后對FP-Tree遞歸挖掘找出所有的頻繁項集。

1.1 基本概念

設(shè)I= {i1,i2,…，im}是一個集合，im稱為項，I稱為項集。每個事務(wù)T是項的集合，T?I。

1)支持度計數(shù)。項集在事務(wù)數(shù)據(jù)集D的出現(xiàn)次數(shù)就是D中包含該項集的個數(shù)，稱為此項集的支持度計數(shù)。

2)支持度。將一個項集的支持度計數(shù)與D中事務(wù)數(shù)之比稱為項集的支持度。

3)頻繁項集。當(dāng)一個項集的支持度大于等于某個給定值時，此項集稱為頻繁項集，這個給定值叫作最小支持度。

4)頻繁k-項集。有k項的頻繁項集。

5)候選項集。有k個項的集合。

1.2 構(gòu)建FP-Tree

1)對數(shù)據(jù)集D進行第一次掃描，計算出所有項的支持度計數(shù)，找出滿足最小支持度的項，即頻繁項，并把這些項按支持度遞減排序生成F-List。

2)更新數(shù)據(jù)集D，將每條事務(wù)中的項按照支持度計數(shù)從大到小排列，并刪除不滿足最小支持度的項，只保留頻繁項。

3)對數(shù)據(jù)集D進行第二次掃描，根據(jù)D中每條事務(wù)出現(xiàn)的頻繁項順序構(gòu)造一棵FP-Tree。創(chuàng)建樹的根節(jié)點null，并將每個事務(wù)出現(xiàn)的頻繁項添加到FP-Tree的一個分支。為了更好地遍歷FP-Tree，創(chuàng)建包含頭節(jié)點的列表，列表中每個元素對應(yīng)F-List中的頻繁項，且每個元素通過一個節(jié)點鏈指向它在FP-Tree中出現(xiàn)的位置。

1.3 FP-Tree挖掘

對FP-Tree進行挖掘時，采用自底向上的遞歸思想，根據(jù)頭節(jié)點列表中元素的指針指向?qū)⑺邪撛氐穆窂饺空页?；然后根?jù)這些路徑構(gòu)造該元素的條件模式基；最后對該條件模式基進行遞歸挖掘找出包含該元素的所有頻繁項集。對列表中所有元素自底向上都執(zhí)行該操作，最終挖掘出所有頻繁項集。

1.4 FP-Growth算法挖掘?qū)嵗?/h3>

假設(shè)事務(wù)數(shù)據(jù)集D如表1所示，最小支持度設(shè)為0.6。算法挖掘流程如下:

1)按照上述1.2節(jié)中步驟1)，對D進行第一次掃描，生成的F-List列表為〈(n:5),(m:4),(o:3),(p:3)〉，并按照1.2節(jié)中步驟2)更新后的數(shù)據(jù)庫列表如表2所示。

表1 事務(wù)數(shù)據(jù)集D

表2 更新后的事務(wù)數(shù)據(jù)集

2)按照1.2節(jié)中步驟3)，對數(shù)據(jù)庫進行第二次掃描，生成FP-Tree以及頭節(jié)點鏈表，如圖1所示。

圖1 生成的FP-Tree

3)按照1.2節(jié)中的步驟3)，繼續(xù)對FP-Tree進行遞歸挖掘得到的頻繁項集如表3所示。

表3 遞歸挖掘得到的所有頻繁項集

基于Spark的并行FP-Growth算法思想是將原始數(shù)據(jù)集劃分到不同的分區(qū)，然后按照如上述步驟在各個分區(qū)構(gòu)建局部FP-Tree并且分別進行頻繁項集的挖掘，最后綜合各個分區(qū)得到全局頻繁項集。

2 基于Spark的FP-Growth算法實現(xiàn)

隨著數(shù)據(jù)集規(guī)模的增大，F(xiàn)P-Growth算法構(gòu)建的FP-Tree橫向和縱向維度都會逐漸增大，存儲大規(guī)模的FP-Tree會出現(xiàn)失??；同時由于挖掘FP-Tree過程中的遞歸次數(shù)增加，造成挖掘效率變得極低[15]。基于Spark的并行FP-Growth算法通過構(gòu)建局部FP-Tree對各個節(jié)點的頻繁項集進行挖掘，最后合并得到全局頻繁項集。

Hadoop分布式文件系統(tǒng)(Hadoop Distributed File System, HDFS)的作用是存儲大數(shù)據(jù)平臺上數(shù)據(jù)集文件, 并且提供統(tǒng)一的命名空間定位文件。Spark平臺將數(shù)據(jù)抽象為RDD，不僅有很強的容錯性和可并行的特點，同時提供了豐富的算子進行不同的操作。

FP-Growth算法在Spark上的并行實現(xiàn)主要分為4個步驟：1)從HDFS上讀取原始數(shù)據(jù)集，對數(shù)據(jù)集進行更新并且產(chǎn)生F-List；2)對數(shù)據(jù)集進行劃分，按照一定規(guī)則將數(shù)據(jù)集中的每條事務(wù)劃分到不同的分區(qū)中；3)對每個分區(qū)按照第1章所介紹的串行FP-Growth算法進行頻繁項集的挖掘；4)將步驟3)中的每一個分區(qū)中的頻繁項集挖掘結(jié)果進行合并，得到整個數(shù)據(jù)集的挖掘結(jié)果并將結(jié)果輸出。算法主要實現(xiàn)過程如圖2所示。

圖2 Spark上實現(xiàn)FP-Growth算法流程

從圖2可以看出，對F-List進行分組是整個并行挖掘任務(wù)的重要環(huán)節(jié)，直接影響后面步驟中FP-Growth算法挖掘效率；同時，數(shù)據(jù)集采取何種劃分策略也會影響并行FP-Growth算法執(zhí)行效率。

3 BFPG算法

本文提出一種新的基于Spark的FP-Growth算法——BFPG算法: 首先綜合考慮不同分區(qū)計算量和FP-Tree規(guī)模大小兩種因素對F-List分組策略進行優(yōu)化；然后通過減少遍歷次數(shù)對數(shù)據(jù)集劃分策略進行改進；最后運用Spark中豐富的算子進行實現(xiàn)。

3.1 F-List分組策略優(yōu)化

F-List分組是整個并行挖掘的重要環(huán)節(jié)。由于對頻繁項集進行并行挖掘的時間取決于最后一個分區(qū)完成的時間，所以在進行分組時應(yīng)該盡量使每個分區(qū)的挖掘時間相等，使每個分區(qū)的挖掘任務(wù)盡可能均衡，因此F-List的分組策略十分關(guān)鍵。

已有的并行FP-Growth算法中F-List分組策略[16]：首先根據(jù)F-List中的元素個數(shù)和分組數(shù)g求出劃分到每個分區(qū)的最小元素個數(shù)為num，然后對已經(jīng)按照支持度降序的F-List從后向前遍歷，將其中(i%num+1)到(i+1)*num(i:0～g-1)的項劃分到第i組。

假設(shè)F-List中的元素個數(shù)為9，分別用9，8，7，6，5，4，3，2，1(用數(shù)字代表支持度的降序排列)表示，分區(qū)個數(shù)為3。未優(yōu)化的分組策略示意圖如圖3所示。

圖3 未優(yōu)化分組結(jié)果示意圖

根據(jù)第1章中介紹，在構(gòu)建FP-Tree時，從根節(jié)點到葉子節(jié)點支持度逐漸降低，由于支持度越低時，根據(jù)該項構(gòu)建的條件模式樹越高，遞歸次數(shù)越多，相應(yīng)的挖掘任務(wù)負載越大，因而將支持度相對較大的項和支持度相對較小的項劃分到不同分區(qū)中，會造成不同分區(qū)之間的挖掘時間有很大差別，故造成負載不均衡。從圖3可以看出，第1組負載最高，第3組負載最低，造成挖掘任務(wù)負載不均衡從而影響挖掘效率。

已有的優(yōu)化算法在分組策略上的改進主要是根據(jù)不同分區(qū)的計算量，注重時間復(fù)雜度。本文增加FP-Tree規(guī)模這一參考標(biāo)準(zhǔn)，即考慮各個分區(qū)中FP-Tree的橫向和縱向維度。通過綜合考慮時間復(fù)雜度和空間復(fù)雜度，得出負載均衡的分組策略，從而更好地對F-List進行分組。具體求出不同分組的計算量非常復(fù)雜，但是基于上段的分析，計算量主要體現(xiàn)在不同項所處路徑的長度，而這是由該項item在F-List列表中具體位置決定的，據(jù)此對分區(qū)挖掘頻繁項集計算量Calculation可以用式(1)進行估計：

Calculation=Log(L(item,F-List))

(1)

FP-Tree規(guī)模是由項在F-List中的位置和該項的支持度計數(shù)進行度量。假設(shè)項的支持度計數(shù)為item_sup，項在F-List中的位置為item_loc。FP-Tree的規(guī)?？捎檬?2)進行估計：

Size=item_sup×(item_loc+1)/2

(2)

式(2)中:item_sup越大，對應(yīng)的item_loc也越大，即這兩個變量有相同的變化趨勢，所以可以得出樹的規(guī)模主要由item_loc決定。在確定了兩個度量標(biāo)準(zhǔn)之后，可以將分組策略優(yōu)化示意圖表示出來，如圖4所示。假設(shè)F-List中元素個數(shù)為18，分區(qū)數(shù)為3，圖4中橫軸代表項item在F-List列表中的位置，圖4(a)中實線和虛線分別代表未優(yōu)化分組時的計算量和FP-Tree規(guī)模大小，優(yōu)化分組之后如圖4(b)所示。

虛線a與經(jīng)過對稱變換的曲線的交點所對應(yīng)原曲線的x軸坐標(biāo)，即為優(yōu)化之后的每個分區(qū)中的元素。采用這樣的劃分可以保證在某一時刻總是將較大計算量和局部FP-Tree規(guī)模較大的那個后綴模式項放在計算量和局部FP-Tree較小的那個分區(qū)中，保證分區(qū)與分區(qū)之間的計算量和FP-Tree存儲規(guī)模大致相同，實現(xiàn)負載均衡。

圖4 分組策略優(yōu)化示意圖

仍假設(shè)F-List中的元素個數(shù)為9，分別用9，8，7，6，5，4，3，2，1(用數(shù)字代表支持度的降序排列)表示，分區(qū)個數(shù)為3。優(yōu)化后的F-List分組策略示意圖如圖5所示。

圖5 優(yōu)化分組結(jié)果示意圖

從圖5可以看出，優(yōu)化分組策略使得剩余頻繁項中負載最大的項劃分到當(dāng)前分區(qū)中負載最小的分組中，達到不同分區(qū)之間的負載均衡。

3.2 數(shù)據(jù)庫劃分策略優(yōu)化

FP-Growth算法的并行挖掘是將數(shù)據(jù)集劃分為一系列分數(shù)據(jù)集，從而構(gòu)建一系列局部FP-Tree，最后挖掘所有頻繁項集。數(shù)據(jù)集的劃分是要將每條事務(wù)劃分到不同的分區(qū)。劃分規(guī)則如下：數(shù)據(jù)集中某條事務(wù)Ti劃分到不同的分區(qū)時，會將Ti從后向前進行遍歷，如果項ai對應(yīng)的分區(qū)在遍歷ai之前是第一次出現(xiàn)，則將ai以及ai之前的所有項全部寫入ai對應(yīng)的分區(qū)中，否則不做任何操作，繼續(xù)向前遍歷。對數(shù)據(jù)集中每條事務(wù)都執(zhí)行此操作可以將數(shù)據(jù)集劃分到不同的分區(qū)中，繼而進行并行化頻繁項集挖掘，同時也保證了最終挖掘出的頻繁項集具有完整性。

在數(shù)據(jù)集劃分過程中，事務(wù)中的每一項都進行遍歷，所以本文提出在劃分數(shù)據(jù)集之前，構(gòu)造一個與group-list相同的列表P-List,構(gòu)造該列表的作用是減少對group-list的遍歷次數(shù)從而提高數(shù)據(jù)集劃分效率。在對一條事務(wù)進行遍歷時，為了判斷某元素所在分區(qū)的分區(qū)號是否出現(xiàn)過，需要對group-List進行遍歷，如果沒有出現(xiàn)過則對事務(wù)進行劃分，否則繼續(xù)遍歷。若遍歷事務(wù)的每一項都把該項對應(yīng)的分區(qū)里的所有元素從P-List中刪除，只對列表中已有元素執(zhí)行劃分操作，無需再對相同分組的項進行判斷。

通過創(chuàng)建P-List，將出現(xiàn)在相同分區(qū)的項刪除，在對事務(wù)進行遍歷時就不會遇到相同分區(qū)的情況。相比遍歷group-list，這一過程能降低時間復(fù)雜度。

假設(shè)有g(shù)個分區(qū)，group-list中有t個元素，事務(wù)長度為trans_len,則未創(chuàng)建P-List時數(shù)據(jù)集劃分的時間耗費為trans_len*t，加入P-List之后，數(shù)據(jù)集劃分的時間耗費包括三部分：在P-List中遍歷相同分區(qū)數(shù)的元素的時間耗費(g*t)，判斷元素的分區(qū)數(shù)的時間耗費為t以及遍歷整條事務(wù)的時間耗費trans_len，數(shù)據(jù)集時間耗費可用式(3)表示:

Time_cons=(g+1)×t+trans_len

(3)

由于在挖掘過程中t和trans_len要比g大得多，所以比較改進前后時間耗費，可以看出創(chuàng)建P-List列表會大幅減少劃分數(shù)據(jù)集的時間耗費，從而降低時間復(fù)雜度，提高挖掘效率。

為清晰表達該優(yōu)化策略，本文對數(shù)據(jù)庫中的一條事務(wù)〈Ti: a f c m p〉進行劃分舉例。優(yōu)化過程如圖6所示。

圖6 數(shù)據(jù)庫劃分優(yōu)化結(jié)果示意圖

未創(chuàng)建P-List時，遍歷事務(wù)每一項都會對group-list進行一次掃描，對事務(wù)進行兩次劃分操作①、②；對劃分過程進進行優(yōu)化后，也對事務(wù)進行同樣兩次劃分操作，但是，在每進行一次劃分之后都會對P-List進行相同分區(qū)的元素進行刪除，這樣當(dāng)遍歷到事務(wù)某一項, 若該項是當(dāng)前P-List中的元素，則進行劃分操作，否則繼續(xù)向前遍歷。

4 實驗與結(jié)果

為了驗證本文所提出的BFPG算法的有效性，實驗選取元數(shù)據(jù)集retail.dat[7]，該數(shù)據(jù)集取自Frequent ItemSet Mining DataSet Repository[17]，該網(wǎng)站提供的數(shù)據(jù)集常用于頻繁項集研究。對retail.dat數(shù)據(jù)集擴展事務(wù)數(shù)生成6個測試數(shù)據(jù)集，記為{D1,D2,D3,D4,D5,D6}，各數(shù)據(jù)集的特征統(tǒng)計信息如表4所示。

表4 數(shù)據(jù)集特征信息統(tǒng)計

實驗所用Spark集群由5個節(jié)點構(gòu)成：其中1個節(jié)點既是主節(jié)點也是從節(jié)點，其余4個為從節(jié)點，每個節(jié)點的配置為：CPU核數(shù)為4，內(nèi)存為8 GB，操作系統(tǒng)Centos 6.8，Hadoop版本：hadoop-2.6.2，Spark版本為spark-1.6.1-bin-hadoop2.6.2，JDK版本為JDK 1.7.0_79，Scala版本為Uscala-2.10.5。

1)為驗證算法有效性，實驗取D1～D6共6個數(shù)據(jù)集，支持度設(shè)為0.05。在集群上分別執(zhí)行基于Hadoop的PFP算法、基于Spark的并行FP-Growth(FP_Growth based on Spark, SFPG)算法和BFPG算法對數(shù)據(jù)集進行頻繁模式的挖掘，實驗結(jié)果如圖7所示。

圖7 不同算法運行時間對比

從圖7可以看出，隨著數(shù)據(jù)量的不斷增大，PFP算法的增長趨勢要明顯大于BFPG和SFPG算法，這是因為基于MapReduce模型框架的算法要頻繁地將中間結(jié)果存儲在內(nèi)存中以及本身迭代性能不足，從而導(dǎo)致算法執(zhí)行時間以幾乎線性方式增長；隨著數(shù)據(jù)量的不斷增大，BFPG算法由于其自身實現(xiàn)負載均衡以及數(shù)據(jù)庫劃分策略優(yōu)化，所以其執(zhí)行效率要高于SFPG算法。實驗結(jié)果表明，面對海量數(shù)據(jù)集，BFPG算法更有利于提高頻繁模式挖掘效率。

2)在算法可擴展性的表現(xiàn)性能上進行如下實驗：保持支持度不變，集群節(jié)點數(shù)從1～5遞增，分別執(zhí)行SFPG和BFPG算法對D6數(shù)據(jù)集進行頻繁模式挖掘，實驗結(jié)果如圖8所示。

圖8 不同節(jié)點情況下算法運行時間

從圖8可以看出，隨著節(jié)點數(shù)的不斷增加，兩種算法運行同一數(shù)據(jù)集的時間不斷減少，整個集群處理效率更高，但是BFPG算法相比SFPG算法執(zhí)行效率更高。實驗結(jié)果表明，BFPG算法有良好的擴展性。

3)實驗通過改變數(shù)據(jù)集的大小，分析Spark平臺在不同節(jié)點數(shù)目下BFPG算法所需的時間，計算加速比來驗證算法的并行性。加速比可以用式(4)表示:

Sp=t/tp

(4)

其中:Sp代表算法加速比，t為使用1個節(jié)點時實驗執(zhí)行的時間，tp為使用p個節(jié)點時實驗執(zhí)行的時間。

實驗取3個數(shù)據(jù)集D2、D4和D6，分別測試在不同節(jié)點數(shù)目下的BFPG算法的加速比，實驗結(jié)果如圖9所示。從圖9中可以看出，在三個不同數(shù)據(jù)集下，算法加速比與節(jié)點數(shù)目的增加近似成正比的關(guān)系。實驗可以得出，BFPG算法處理數(shù)據(jù)集具有較好的并行性。

圖9 BFPG在不同節(jié)點數(shù)下的加速比

5 結(jié)語

基于Spark的FP-Growth算法主要存在兩個問題：F-List分組策略未充分考慮負載均衡問題；數(shù)據(jù)集劃分時遍歷次數(shù)太多造成時間復(fù)雜度很高?；诖?，本文提出了一種新的基于Spark的并行FP-Growth算法——BFPG算法，算法首先綜合考慮不同分區(qū)內(nèi)FP-Tree規(guī)模大小和計算量兩方面對F-List 分組策略進行改進，然后通過構(gòu)造一個新的分組列表P-List對數(shù)據(jù)集劃分策略進行優(yōu)化，最后對算法進行實現(xiàn)。結(jié)果表明，BPFP算法提高了基于Spark的并行FP-Growth算法對頻繁項集的挖掘效率；隨著集群節(jié)點數(shù)目增加，算法執(zhí)行效率不斷提高，驗證了算法具有良好的擴展性；隨著節(jié)點數(shù)目增加，算法加速比近似呈線性增加，驗證了算法具有良好的并行性。