基于Spark的并行頻繁項(xiàng)集挖掘算法

張素琪 孫云飛 武君艷 顧軍華

1(天津商業(yè)大學(xué)信息工程學(xué)院 天津 300134)2(河北工業(yè)大學(xué)人工智能與數(shù)據(jù)科學(xué)學(xué)院 天津 300401)3(河北省大數(shù)據(jù)計(jì)算重點(diǎn)實(shí)驗(yàn)室 天津 300401)

0 引 言

隨著人工智能時(shí)代的到來(lái)，基于大數(shù)據(jù)的關(guān)聯(lián)規(guī)則挖掘成為國(guó)內(nèi)外科學(xué)家研究的熱點(diǎn)方向之一，其主要任務(wù)是挖掘大數(shù)據(jù)集中潛在有用的關(guān)聯(lián)關(guān)系以及動(dòng)態(tài)數(shù)據(jù)中規(guī)則的變化規(guī)律，在很多行業(yè)和領(lǐng)域有重要的研究意義和應(yīng)用前景。隨著數(shù)據(jù)的爆炸式增長(zhǎng)，數(shù)據(jù)集中的關(guān)聯(lián)關(guān)系越來(lái)越復(fù)雜、越來(lái)越廣泛，關(guān)聯(lián)規(guī)則發(fā)現(xiàn)的復(fù)雜性和實(shí)時(shí)性需求日益強(qiáng)烈。頻繁項(xiàng)集挖掘是關(guān)聯(lián)規(guī)則挖掘的第一步也是最重要的一步。Apriori算法是挖掘頻繁項(xiàng)集最有影響和最具有代表性的一種算法，但該算法多次掃描數(shù)據(jù)庫(kù)，并且產(chǎn)生大量的候選集[1]?；诖耍琀an等[2]提出了一種不產(chǎn)生候選項(xiàng)集的FP-Growth算法，并且只對(duì)數(shù)據(jù)庫(kù)進(jìn)行兩次掃描，使得挖掘效率以及空間復(fù)雜度方面均有很大改進(jìn)。隨著計(jì)算規(guī)模不斷增大，串行FP-Growth算法會(huì)因硬件資源的限制遇到內(nèi)存瓶頸或者失效的問(wèn)題[3]?；诜植际接?jì)算框架的大數(shù)據(jù)平臺(tái)成為解決這一問(wèn)題的一個(gè)重要途徑。這些大數(shù)據(jù)平臺(tái)在處理海量數(shù)據(jù)時(shí)通過(guò)分布式計(jì)算框架可以明顯提高算法的處理效率，能更高效地引導(dǎo)人們發(fā)現(xiàn)潛在的、有利用價(jià)值的信息。

基于MapReduce計(jì)算框架的Hadoop大數(shù)據(jù)平臺(tái)，是一種用于分布式并行環(huán)境中處理大規(guī)模數(shù)據(jù)的計(jì)算模型[4]。2008年，Li等[5]提出了基于MapReduce的并行化FP-Growth算法——PFP(Parallel FP-Growth)算法，實(shí)驗(yàn)證明該算法的挖掘效率呈線性增長(zhǎng)趨勢(shì)并且有良好的擴(kuò)展性，但是算法并未對(duì)FP-Tree挖掘以及負(fù)載均衡做出優(yōu)化。2014年，章志剛等[6]對(duì)頻繁項(xiàng)目集重新計(jì)算支持度的FPPM算法，并在Hadoop平臺(tái)上加以實(shí)現(xiàn)，實(shí)驗(yàn)證明該算法能通過(guò)減少網(wǎng)絡(luò)通信量來(lái)提高頻繁項(xiàng)集挖掘效率。2015年，馬強(qiáng)等[7]在FP-Tree節(jié)點(diǎn)中新增一個(gè)帶頻繁項(xiàng)前綴的域空間來(lái)構(gòu)建一棵新的NFP-Tree，并在Hadoop平臺(tái)進(jìn)行驗(yàn)證與分析，實(shí)驗(yàn)證明該算法效率將頻繁項(xiàng)集挖掘算法平均提高16.6%。這兩種算法都是對(duì)FP-Growth算法本身進(jìn)行改進(jìn)并在Hadoop上實(shí)現(xiàn)，并未考慮在并行實(shí)現(xiàn)方式進(jìn)行改進(jìn)。2016年，朱文飛等[4]提出基于Hadoop的數(shù)據(jù)分割以及均衡分組的HBFP算法，實(shí)驗(yàn)證明該算法比PFP算法效率提高了約12%。盡管基于Hadoop大數(shù)據(jù)平臺(tái)的改進(jìn)方法在一定程度上提高了FP-Growth算法頻繁項(xiàng)集挖掘效率，但是MapReduce編程模型中將各個(gè)步驟的中間結(jié)果存儲(chǔ)到硬盤(pán)中,在處理大規(guī)模數(shù)據(jù)時(shí)會(huì)頻繁讀取硬盤(pán)內(nèi)容，從而造成挖掘效率降低的問(wèn)題。相比于Hadoop平臺(tái)，Spark大數(shù)據(jù)平臺(tái)是基于RDD(彈性分布式數(shù)據(jù)集)的編程框架。Spark相比MapReduce框架的優(yōu)越性主要體現(xiàn)在兩點(diǎn)：第一，Spark將所有運(yùn)行中間結(jié)果均存儲(chǔ)在內(nèi)存中，減少I(mǎi)/O負(fù)載，因而更適合迭代運(yùn)算；第二，Spark豐富的算子使得通過(guò)編程實(shí)現(xiàn)算法有了更多的靈活性。2015年，Deng等[8]提出了一種基于Spark框架的改進(jìn)FP-Growth算法—DFP算法，在鏈頭表結(jié)構(gòu)中加入一張哈希表從而快速訪問(wèn)地址，實(shí)驗(yàn)證明DFP算法更高效。2016年，方向等[9]提出了基于Spark的均衡分組思想的改進(jìn)算法—IPFP-Growth算法，實(shí)驗(yàn)證明優(yōu)化后的算法要比PFP效率更高。2017年，張穩(wěn)等[10]提出一種基于項(xiàng)間聯(lián)通權(quán)重矩陣的負(fù)載平衡CWBPFP算法，實(shí)驗(yàn)證明該算法高效并有良好的可擴(kuò)展性。2017年，陸可等[11]基于Spark框架通過(guò)支持度計(jì)數(shù)和分組過(guò)程對(duì)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)化鏈頭表結(jié)構(gòu)和優(yōu)化分組策略兩方面。盡管已經(jīng)有對(duì)Spark的并行化FP-Growth進(jìn)行優(yōu)化的算法，但是在優(yōu)化分組時(shí)，僅考慮計(jì)算量對(duì)挖掘效率的影響，而并未考慮空間復(fù)雜度問(wèn)題。所以，本文提出了改進(jìn)算法——SPFPG算法：通過(guò)綜合考慮計(jì)算量和FP-Tree規(guī)模兩種因素對(duì)分組策略進(jìn)行優(yōu)化，并且運(yùn)用Spark中豐富的算子對(duì)優(yōu)化算法進(jìn)行實(shí)現(xiàn)。

1 FP-Growth算法描述

FP-Growth是對(duì)Apriori算法的改進(jìn)算法，算法使用一棵FP-Tree存儲(chǔ)數(shù)據(jù)庫(kù)中的事務(wù)，在不產(chǎn)生候選項(xiàng)集的基礎(chǔ)上生成頻繁項(xiàng)集。FP-Growth算法采用遞歸策略，并且在整個(gè)挖掘過(guò)程中，只對(duì)數(shù)據(jù)庫(kù)進(jìn)行兩次掃描。FP-Growth算法對(duì)頻繁項(xiàng)集的挖掘過(guò)程分為兩步：第一步，構(gòu)造一棵FP-Tree；第二步，對(duì)FP-Tree遞歸挖掘找出所有的頻繁項(xiàng)集。

1.1 構(gòu)建FP-Tree

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

(2) 更新數(shù)據(jù)庫(kù)D：將數(shù)據(jù)集中每條事務(wù)中的項(xiàng)按照F-List中項(xiàng)的順序進(jìn)行排序，刪除不滿足最小支持度的項(xiàng)，即數(shù)據(jù)庫(kù)更新后每條事務(wù)中的項(xiàng)都滿足最小支持度且都按照支持度降序排列。

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

1.2 FP-Tree挖掘

FP-Tree的挖掘采用自底向上的遞歸思想，如果路徑中包含頭結(jié)點(diǎn)列表中元素，那么該元素的指針會(huì)指向路徑中該元素的位置；然后基于這些路徑構(gòu)造該元素的條件模式基；最后對(duì)條件模式基進(jìn)行遞歸挖掘找出含該元素的所有頻繁項(xiàng)集。對(duì)頭節(jié)點(diǎn)列表中所有元素自底向上都執(zhí)行以上的操作，最終挖掘出所有頻繁項(xiàng)集。

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

事務(wù)數(shù)據(jù)庫(kù)D如表1所示，最小支持度0.6。

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

算法挖掘流程如下:

(1) 對(duì)D進(jìn)行第一次掃描，生成的F-List列表為<(n:5),(m:4),(o:3),(p:3)>，更新后的數(shù)據(jù)庫(kù)列表如表2所示。

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

(2)對(duì)D進(jìn)行第二次掃描，生成FP-Tree以及頭結(jié)點(diǎn)列表，如圖1所示。

圖1 生成的FP-Tree

(3) 對(duì)FP-Tree遞歸挖掘得到的頻繁項(xiàng)集如表3所示。

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

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

當(dāng)數(shù)據(jù)集規(guī)模很大時(shí)，串行FP-Growth算法構(gòu)建的FP-Tree橫向或縱向維度變得很大，存儲(chǔ)FP-Tree會(huì)造成失??；同時(shí)由于挖掘過(guò)程中的遞歸次數(shù)增加，造成挖掘效率變得極低[12]。所以基于Spark的并行FP-Growth算法—SFPG算法思想是將原始數(shù)據(jù)庫(kù)劃分到不同的節(jié)點(diǎn)，然后通過(guò)構(gòu)建局部FP-Tree對(duì)各個(gè)節(jié)點(diǎn)的頻繁項(xiàng)集進(jìn)行挖掘，最后合并得到全局頻繁項(xiàng)集[13]。

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

圖2 SFPG算法流程圖

步驟一中，要將原始事務(wù)數(shù)據(jù)庫(kù)分布到RDD上，然后并行進(jìn)行不同項(xiàng)的支持度計(jì)數(shù)統(tǒng)計(jì)。首先對(duì)挖掘任務(wù)初始化，再遍歷每一條事務(wù)，對(duì)不同項(xiàng)進(jìn)行支持度計(jì)數(shù)統(tǒng)計(jì)并按照從大到小排序，最后將所有滿足最小支持度的項(xiàng)進(jìn)行結(jié)果合并然后保存在內(nèi)存中，得到F-List，同時(shí)對(duì)數(shù)據(jù)庫(kù)進(jìn)行更新，即刪除每條事務(wù)中不滿足支持度的項(xiàng)并按照支持度計(jì)數(shù)進(jìn)行排序。

步驟二中，對(duì)更新后的數(shù)據(jù)庫(kù)進(jìn)行分組，首先將F-List劃分為g個(gè)分組，生成group-list，這個(gè)列表中的元素包括item以及該項(xiàng)對(duì)應(yīng)的group-id，然后將數(shù)據(jù)庫(kù)中的每條事務(wù)根據(jù)group-list列表劃分到不同的分區(qū)中。在劃分之后得到Group-list,其存儲(chǔ)分區(qū)號(hào)和劃分到該分區(qū)的分事務(wù)組以及各個(gè)事務(wù)出現(xiàn)的次數(shù)。數(shù)據(jù)庫(kù)進(jìn)行劃分采用將相同group-id的分事務(wù)分布到相同分組的方法，實(shí)現(xiàn)在后續(xù)進(jìn)行頻繁項(xiàng)集挖掘的過(guò)程中挖掘結(jié)果的完整性和準(zhǔn)確性。

步驟三中，對(duì)劃分到每個(gè)分區(qū)的分事務(wù)進(jìn)行頻繁項(xiàng)集挖掘，實(shí)現(xiàn)并行化挖掘。在本步驟中，每個(gè)分組只對(duì)劃分到該分區(qū)的事務(wù)組包含的項(xiàng)進(jìn)行逐項(xiàng)遍歷，這樣避免了頻繁項(xiàng)集的重復(fù)挖掘。

步驟四中，將所有頻繁項(xiàng)集進(jìn)行合并，并將結(jié)果轉(zhuǎn)換成所需格式。

3 基于Spark的FP-Growth優(yōu)化算法——SPFPG算法

在第2節(jié)的敘述中可以看出，步驟二對(duì)整個(gè)并行算法執(zhí)行效率起著關(guān)鍵作用。在這一步驟中執(zhí)行對(duì)F-List進(jìn)行分組操作以及數(shù)據(jù)庫(kù)的劃分操作。本文對(duì)算法的改進(jìn)主要體現(xiàn)在分組策略的優(yōu)化，并且運(yùn)用了Spark豐富的算子對(duì)優(yōu)化算法進(jìn)行實(shí)現(xiàn)。

F-List分組作為整個(gè)并行挖掘的一個(gè)重要環(huán)節(jié)，為了使每個(gè)分區(qū)的挖掘任務(wù)均衡，應(yīng)該改進(jìn)對(duì)F-List的分組策略。由于在對(duì)頻繁項(xiàng)集進(jìn)行并行挖掘的時(shí)間取決于最后一個(gè)分區(qū)完成的時(shí)間，所以在進(jìn)行分組時(shí)應(yīng)該盡量使每個(gè)分區(qū)的挖掘時(shí)間相等?；贛apReduce編程框架的PFP算法采用的分組策略并未考慮負(fù)載均衡問(wèn)題，在集群進(jìn)行頻繁模式挖掘任務(wù)時(shí)，會(huì)造成節(jié)點(diǎn)與節(jié)點(diǎn)挖掘負(fù)載相差很大。PFP算法分組策略：首先根據(jù)F-List中的元素個(gè)數(shù)和分組數(shù)g求出劃分到每個(gè)組的最小元素個(gè)數(shù)為items_num，然后對(duì)已經(jīng)按照支持度降序的F-List從后向前遍歷，將其中(i%items_num+1)到(i+1)×items_num(i:0～g-1)的項(xiàng)劃分到第i組。根據(jù)第1節(jié)中介紹，在構(gòu)建FP-Tree時(shí)，從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)支持度逐漸降低。由于支持度越低時(shí)，根據(jù)該項(xiàng)構(gòu)建的條件模式樹(shù)越高，遞歸次數(shù)越多，相應(yīng)的挖掘任務(wù)負(fù)載越大，而在PFP算法中將支持度相對(duì)較大的項(xiàng)和支持度相對(duì)較小的項(xiàng)劃分到不同組中，會(huì)造成不同分組之間的挖掘時(shí)間有很大差別，故造成負(fù)載不均衡。

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

CAL=lg(L(item,F-List))

(1)

FP-Tree規(guī)模是由項(xiàng)在F-List中的位置和該項(xiàng)的支持度計(jì)數(shù)進(jìn)行度量。假設(shè)項(xiàng)的支持度計(jì)數(shù)為sup，項(xiàng)在F-List中的位置為loc。FP-Tree的規(guī)?？勺魅缦鹿烙?jì)：

Size=sup×(loc+1)/2

(2)

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

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

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

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

從圖4可以看出，第1組負(fù)載最高，第3組負(fù)載最低，造成挖掘任務(wù)負(fù)載不均衡從而影響挖掘效率。按照本文提出的優(yōu)化策略的分組示意圖如圖5所示。

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

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

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

為了驗(yàn)證本文所提出的SPFPG算法的有效性，實(shí)驗(yàn)選取數(shù)據(jù)集retail.dat，該數(shù)據(jù)集取自Frequent ItemSet Mining DataSet Repository[14]，該網(wǎng)站提供的數(shù)據(jù)集常用于頻繁項(xiàng)集的研究。webdocs.dat數(shù)據(jù)集大小為1.48 GB，有1 692 082條事務(wù)和一共5 267 656個(gè)屬性。從webdocs.dat數(shù)據(jù)集中隨機(jī)選取事務(wù)生成五個(gè)測(cè)試數(shù)據(jù)集，記為{D1,D2,D3,D4,D5}，每個(gè)數(shù)據(jù)集中事務(wù)數(shù)依次為10萬(wàn)條、20萬(wàn)條、30萬(wàn)條、40萬(wàn)條、50萬(wàn)條。

實(shí)驗(yàn)所用Spark集群由三個(gè)節(jié)點(diǎn)構(gòu)成：一個(gè)主節(jié)點(diǎn)和三個(gè)從節(jié)點(diǎn)(其中一個(gè)節(jié)點(diǎn)既是主節(jié)點(diǎn)也是從節(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。實(shí)驗(yàn)分別比較了數(shù)據(jù)量、集群節(jié)點(diǎn)個(gè)數(shù)對(duì)SFPG以及SPFPG算法挖掘效率的影響，同時(shí)對(duì)SPFPG算法有效性進(jìn)行了驗(yàn)證。

4.1 挖掘時(shí)間與數(shù)據(jù)量之間的關(guān)系

本文設(shè)置支持度為20%。首先用未優(yōu)化的基于Spark的FP-Growth算法對(duì)六個(gè)測(cè)試數(shù)據(jù)集進(jìn)行頻繁項(xiàng)集挖掘，然后再用本文提出的SPFPG算法對(duì)測(cè)試數(shù)據(jù)集分別進(jìn)行頻繁項(xiàng)集的挖掘，最后對(duì)兩個(gè)算法的運(yùn)行時(shí)間進(jìn)行比較。實(shí)驗(yàn)結(jié)果如圖6所示。

圖6 webdocs.dat數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

圖6中橫坐標(biāo)表示事務(wù)數(shù)大小，縱坐標(biāo)表示算法運(yùn)行時(shí)間，兩條曲線分別表示兩個(gè)算法運(yùn)行時(shí)間的變化趨勢(shì)。從圖6可以看出，當(dāng)事務(wù)數(shù)據(jù)量不大時(shí)，優(yōu)化前后的算法挖掘時(shí)間相差不大，SPFPG算法并沒(méi)有體現(xiàn)出明顯優(yōu)勢(shì)。隨著數(shù)據(jù)量的不斷增大，可以看出SPFPG算法挖掘效率要明顯高于SPFG算法。實(shí)驗(yàn)說(shuō)明，面對(duì)海量數(shù)據(jù)集，SPFPG算法更有利于提高頻繁模式挖掘效率。

4.2 挖掘時(shí)間與集群節(jié)點(diǎn)個(gè)數(shù)之間的關(guān)系

針對(duì)webdocs.dat數(shù)據(jù)集，在支持度保持不變條件下，集群節(jié)點(diǎn)數(shù)從1遞增到3，通過(guò)SFPG算法和SPFPG算法對(duì)數(shù)據(jù)集中頻繁項(xiàng)集進(jìn)行挖掘。實(shí)驗(yàn)結(jié)果如圖7所示。

圖7 挖掘時(shí)間與集群節(jié)點(diǎn)個(gè)數(shù)關(guān)系圖

圖7中橫坐標(biāo)表示集群中的節(jié)點(diǎn)個(gè)數(shù)，縱坐標(biāo)表示算法運(yùn)行時(shí)間，曲線分別表示兩種算法運(yùn)行時(shí)間的變化趨勢(shì)。從圖7可以看出，隨著Spark集群節(jié)點(diǎn)數(shù)的增加，SFPG和SPFPG算法對(duì)頻繁項(xiàng)集挖掘時(shí)間都會(huì)減少，但SPFPG算法效率優(yōu)勢(shì)更明顯，說(shuō)明本文提出的分組策略能大大提高挖掘效率。

4.3 算法有效性驗(yàn)證

通過(guò)改變實(shí)驗(yàn)數(shù)據(jù)集的大小，分析Spark平臺(tái)在不同節(jié)點(diǎn)數(shù)目下SPFPG算法所需的時(shí)間，計(jì)算加速比來(lái)驗(yàn)證算法的并行性。加速比的公式如下：

(3)

式中：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í)間。

SPFPG算法在兩個(gè)測(cè)試數(shù)據(jù)集D3和D5上不同節(jié)點(diǎn)個(gè)數(shù)情況下的加速比如圖8所示。圖8中橫坐標(biāo)表示集群中節(jié)點(diǎn)個(gè)數(shù)，縱坐標(biāo)表示加速比，兩條曲線分別表示不同數(shù)據(jù)集對(duì)應(yīng)的加速比變化趨勢(shì)。從圖中可以看出，在兩個(gè)不同數(shù)據(jù)集下，算法加速比與節(jié)點(diǎn)數(shù)目的增加近似成正比的關(guān)系?？梢?jiàn)，SPFPG算法處理數(shù)據(jù)集具有較好的并行性。

圖8 SPFPG算法加速比

5 結(jié) 語(yǔ)

為了解決Spark下頻繁項(xiàng)集挖掘過(guò)程中的分組不均衡問(wèn)題，本文提出基于Spark的SPFPG算法。該算法在進(jìn)行分組時(shí)，通過(guò)綜合考慮不同節(jié)點(diǎn)的計(jì)算量和FP-Tree規(guī)模來(lái)實(shí)現(xiàn)均衡分組。實(shí)驗(yàn)結(jié)果表明，SPFPG算法提高了頻繁項(xiàng)集的挖掘效率，且算法具有良好的并行性和擴(kuò)展性。