基于Spark的并行FP-Growth算法優(yōu)化及實(shí)現(xiàn)

顧軍華，武君艷，許馨勻，謝志堅(jiān)，張素琪

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

0 引言

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

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

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

1 FP-Growth算法描述

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

1.1 基本概念

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

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

2)支持度。將一個(gè)項(xiàng)集的支持度計(jì)數(shù)與D中事務(wù)數(shù)之比稱為項(xiàng)集的支持度。

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

4)頻繁k-項(xiàng)集。有k項(xiàng)的頻繁項(xiàng)集。

5)候選項(xiàng)集。有k個(gè)項(xiàng)的集合。

1.2 構(gòu)建FP-Tree

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

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

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

1.3 FP-Tree挖掘

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

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

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

1)按照上述1.2節(jié)中步驟1)，對D進(jìn)行第一次掃描，生成的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ù)庫進(jìn)行第二次掃描，生成FP-Tree以及頭節(jié)點(diǎn)鏈表，如圖1所示。

圖1 生成的FP-Tree

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

表3 遞歸挖掘得到的所有頻繁項(xiàng)集

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

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

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

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

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

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

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

3 BFPG算法

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

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

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

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

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

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

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

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

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

(1)

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

Size=item_sup×(item_loc+1)/2

(2)

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

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

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

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

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

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

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

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

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

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

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

Time_cons=(g+1)×t+trans_len

(3)

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

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

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

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

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

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

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

實(shí)驗(yàn)所用Spark集群由5個(gè)節(jié)點(diǎn)構(gòu)成：其中1個(gè)節(jié)點(diǎn)既是主節(jié)點(diǎn)也是從節(jié)點(diǎn)，其余4個(gè)為從節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)的配置為：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)為驗(yàn)證算法有效性，實(shí)驗(yàn)取D1～D6共6個(gè)數(shù)據(jù)集，支持度設(shè)為0.05。在集群上分別執(zhí)行基于Hadoop的PFP算法、基于Spark的并行FP-Growth(FP_Growth based on Spark, SFPG)算法和BFPG算法對數(shù)據(jù)集進(jìn)行頻繁模式的挖掘，實(shí)驗(yàn)結(jié)果如圖7所示。

圖7 不同算法運(yùn)行時(shí)間對比

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

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

圖8 不同節(jié)點(diǎn)情況下算法運(yùn)行時(shí)間

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

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

Sp=t/tp

(4)

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

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

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

5 結(jié)語

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