基于Spark的投影樹頻繁項(xiàng)集挖掘算法

馮興杰，潘 軒

(1.中國(guó)民航大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，天津 300300； 2.中國(guó)民航大學(xué) 信息網(wǎng)絡(luò)中心，天津 300300)

0 引 言

隨著互聯(lián)網(wǎng)技術(shù)的飛速發(fā)展和大數(shù)據(jù)信息化時(shí)代的來臨，數(shù)據(jù)挖掘[1]已經(jīng)演變?yōu)橐环N集大數(shù)據(jù)量與大計(jì)算量于一體的批量式處理過程。而且為了產(chǎn)生有效的數(shù)據(jù)信息，大部分關(guān)聯(lián)規(guī)則挖掘算法需要多次使用原始數(shù)據(jù)集對(duì)候選項(xiàng)集進(jìn)行篩選處理，使得算法效率低下。然而大數(shù)據(jù)平臺(tái)這一新技術(shù)能夠處理大數(shù)據(jù)的關(guān)聯(lián)規(guī)則挖掘所遇到的諸多問題，它能夠?qū)崿F(xiàn)集群內(nèi)部資源共享、操作的透明性高、較高的可靠性、以及一定的靈活性等特點(diǎn)，可以高效地處理大規(guī)模數(shù)據(jù)。

以Hadoop環(huán)境為基礎(chǔ)，使用HDFS為底層存儲(chǔ)工具的Spark云計(jì)算平臺(tái)是近年來最為常用的大數(shù)據(jù)運(yùn)算框架。頻繁項(xiàng)集挖掘與Spark計(jì)算框架相結(jié)合有許多成功案例，Qiu H等在Spark上實(shí)現(xiàn)了Apriori算法的并行化并提出YAFIM算法，解決了串行算法在實(shí)現(xiàn)并行過程中遇到的諸多問題[3]，但該算法需重復(fù)遍歷數(shù)據(jù)集，且產(chǎn)生頻繁二項(xiàng)集時(shí)會(huì)出現(xiàn)組合爆炸問題，運(yùn)算效率有待提升；Rathee S等通過構(gòu)建一種新的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，改進(jìn)Apriori算法，并且在Spark上加以實(shí)現(xiàn)，提出了并行化的R-Apriori算法[4]，該算法僅在頻繁二項(xiàng)集的產(chǎn)生過程進(jìn)行改進(jìn)，沒有解決多次迭代原數(shù)據(jù)集的根本問題；文獻(xiàn)[5]將FP-Growth算法與Spark相結(jié)合，得到了并行化頻繁項(xiàng)集挖掘算法，但構(gòu)建FP樹產(chǎn)生較大消耗，算法效率仍需提高。

本文提出了一種基于Spark計(jì)算框架的投影樹算法(projection tree algorithm based on Spark，PTBS)，解決了重復(fù)遍歷原始數(shù)據(jù)、產(chǎn)生頻繁二項(xiàng)集的組合爆炸以及并行計(jì)算時(shí)節(jié)點(diǎn)通信量較大等問題，提高了算法在處理大數(shù)據(jù)集時(shí)的運(yùn)行效率。

1 相關(guān)技術(shù)及方法

1.1 Spark并行計(jì)算框架

Spark大數(shù)據(jù)框架因其實(shí)現(xiàn)了基于內(nèi)存的方式儲(chǔ)存數(shù)據(jù)，具備了快速迭代數(shù)據(jù)的能力，同時(shí)可以使用RDD(resilient distributed datasets)技術(shù)實(shí)現(xiàn)存儲(chǔ)的持久化和高容錯(cuò)性等優(yōu)勢(shì)，使得它更適于處理大數(shù)據(jù)集的迭代式運(yùn)算，成為大數(shù)據(jù)云計(jì)算研究者們的首選[6]。

Spark能夠?qū)崿F(xiàn)基于內(nèi)存計(jì)算的基礎(chǔ)，是其實(shí)現(xiàn)了一種分布式的內(nèi)存抽象—RDD。RDD支持在數(shù)據(jù)集上的應(yīng)用，同時(shí)也具備了數(shù)據(jù)流的特點(diǎn)，即：位置感知性調(diào)度、良好的伸縮性以及自動(dòng)容錯(cuò)的能力[7]。此外，Spark還為RDD提供了豐富的內(nèi)置操作，能夠通過某一組操作將指定的一個(gè)RDD轉(zhuǎn)化為另一個(gè)RDD，這是Spark數(shù)據(jù)處理的具體操作方式。但是，Spark實(shí)現(xiàn)的最主要的突破，是完成了數(shù)據(jù)的可持久化操作[8]。持久化(或緩存)一個(gè)數(shù)據(jù)集在內(nèi)存中，每一個(gè)節(jié)點(diǎn)都會(huì)將其數(shù)據(jù)分塊中的計(jì)算結(jié)果保存于節(jié)點(diǎn)內(nèi)存，并在對(duì)數(shù)據(jù)集后續(xù)的操作中對(duì)持久化的數(shù)據(jù)進(jìn)行重用。這也是Spark實(shí)現(xiàn)快速迭代的關(guān)鍵所在。

從宏觀上講，Spark的算法構(gòu)造和物理執(zhí)行都是以Pipeline(任務(wù)管道)為核心，基于Pipeline的思想，數(shù)據(jù)被使用時(shí)才開始計(jì)算(如Transformation算子的Lazy模式),不會(huì)產(chǎn)生中間結(jié)果，而在此之前，所有的操作都只是記錄dataSet的轉(zhuǎn)換過程。從數(shù)據(jù)流動(dòng)的角度來說，是數(shù)據(jù)流動(dòng)到了計(jì)算的位置。所以模式構(gòu)建中要最大化Pipeline，這樣既有利于并發(fā)，也利于數(shù)據(jù)的復(fù)用，會(huì)極大地提高運(yùn)算效率,Spark的運(yùn)行模式如圖1所示。

圖1 Spark運(yùn)行模式

1.2 廣播變量

在關(guān)聯(lián)規(guī)則挖掘算法實(shí)現(xiàn)并行化的過程中，需要在工作節(jié)點(diǎn)共享一些數(shù)據(jù)。為了實(shí)現(xiàn)這一目標(biāo)，需在工作開始之前將數(shù)據(jù)廣播到所有節(jié)點(diǎn)。Spark默認(rèn)將所需的數(shù)據(jù)打包并發(fā)送到集群中從節(jié)點(diǎn)的每一個(gè)Task(執(zhí)行任務(wù)的邏輯單元)中。然而，這將導(dǎo)致主節(jié)點(diǎn)的帶寬成為運(yùn)算過程的瓶頸，降低了算法的運(yùn)行效率，直接限制了算法的可擴(kuò)展性。與此同時(shí)，在處理海量數(shù)據(jù)的過程當(dāng)中，分布式文件系統(tǒng)讀取數(shù)據(jù)的I/O消耗也非常大[9]。為了緩解這一問題，采用Spark先進(jìn)的功能--廣播變量(broadcast)，它允許程序員發(fā)送一個(gè)全局只讀的變量到從節(jié)點(diǎn)的內(nèi)存中，從節(jié)點(diǎn)的所有Task共享該變量，而不是為每一個(gè)Task傳輸變量。這樣可以極大地減少網(wǎng)絡(luò)傳輸，節(jié)省內(nèi)存空間，也隱形地提高了CPU的工作效率[10]。廣播變量的作用方式如圖2所示。

圖2 廣播變量工作模式

1.3 頻繁項(xiàng)集挖掘算法

投影樹算法：投影樹算法利用投影樹數(shù)據(jù)結(jié)構(gòu)表示所有項(xiàng)目集，該投影樹的實(shí)質(zhì)是一個(gè)字典樹。投影樹中的每一個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)特定的項(xiàng)目集合，項(xiàng)目集的長(zhǎng)度則對(duì)應(yīng)于該節(jié)點(diǎn)在投影樹中所處的層數(shù)。對(duì)于每一個(gè)節(jié)點(diǎn)，分別有一個(gè)動(dòng)態(tài)項(xiàng)目表與之對(duì)應(yīng)(因投影樹以字典序排列，故動(dòng)態(tài)項(xiàng)目表即對(duì)應(yīng)節(jié)點(diǎn)的兄弟節(jié)點(diǎn)所對(duì)應(yīng)項(xiàng)目集的最后一項(xiàng))，表中每一個(gè)項(xiàng)目可與當(dāng)前節(jié)點(diǎn)所對(duì)應(yīng)的項(xiàng)目集連接，生成新的候選項(xiàng)集。產(chǎn)生候選項(xiàng)集的同時(shí)，會(huì)生成一個(gè)新的孩子節(jié)點(diǎn)代表這個(gè)候選項(xiàng)集。當(dāng)對(duì)應(yīng)于頻繁項(xiàng)目集候選項(xiàng)集的節(jié)點(diǎn)生成時(shí)，使用數(shù)據(jù)集在投影樹上投影的方式，在第(k-1)層的父節(jié)點(diǎn)對(duì)原事務(wù)數(shù)據(jù)集進(jìn)行投影，篩選出全部數(shù)據(jù)集中與之對(duì)應(yīng)的事務(wù)，并進(jìn)行計(jì)數(shù)，依次來決定在算法的第k次迭代過程中所產(chǎn)生的候選項(xiàng)目集的支持度。之后以廣度優(yōu)先的方式對(duì)生成樹進(jìn)行擴(kuò)展，相應(yīng)于樹中的每一個(gè)可擴(kuò)展節(jié)點(diǎn)，同樣保留一張動(dòng)態(tài)項(xiàng)目表，將表中每個(gè)項(xiàng)目依次連接于該節(jié)點(diǎn)項(xiàng)目集，生成新的子節(jié)點(diǎn)項(xiàng)目，并用數(shù)據(jù)集進(jìn)行投影、計(jì)數(shù)，篩選出新的頻繁項(xiàng)集。

2 基于Spark的投影樹頻繁項(xiàng)集挖掘算法—PTBS

為了充分利用Spark計(jì)算框架，需要將投影樹算法進(jìn)行改進(jìn)。首先把串行投影樹算法實(shí)現(xiàn)并行化，改變?cè)袛?shù)據(jù)結(jié)構(gòu)，以解決重復(fù)遍歷數(shù)據(jù)集帶來的損耗；然后針對(duì)頻繁二項(xiàng)集的產(chǎn)生進(jìn)行改進(jìn)，降低運(yùn)算量，減少集群節(jié)點(diǎn)間通信的消耗；最后將Apriori先驗(yàn)性質(zhì)添加到候選項(xiàng)集的篩選過程中，以減少節(jié)點(diǎn)間的通信量。下面，就對(duì)算法進(jìn)行詳細(xì)地分析。

(1)將存儲(chǔ)于HDFS中的數(shù)據(jù)導(dǎo)入Spark RDD中，以便進(jìn)行下一步操作。而后，使用map方法對(duì)數(shù)據(jù)進(jìn)行過濾和處理，使之成為規(guī)律的，以行的形式存儲(chǔ)的數(shù)據(jù)。其中，事務(wù)都以代表該事務(wù)的事務(wù)序號(hào)以及在事務(wù)序列中所包含的事務(wù)項(xiàng)組成。根據(jù)原算法思路，得出頻繁項(xiàng)集需反復(fù)投影原始數(shù)據(jù)，為提高算法運(yùn)行效率，我們?cè)谠撎幖右愿倪M(jìn)。

故選擇對(duì)數(shù)據(jù)存儲(chǔ)的組織結(jié)構(gòu)加以改進(jìn)。原始數(shù)據(jù)是將事務(wù)序列與事務(wù)項(xiàng)按照鍵值對(duì)的形式保存于RDD當(dāng)中。開始，在map階段將事務(wù)中的事務(wù)項(xiàng)進(jìn)行分離，并分別與該事務(wù)的編號(hào)形成多個(gè)鍵值對(duì)，之后，在reduce階段將具備相同事務(wù)編號(hào)的項(xiàng)合并。對(duì)特定事務(wù)編號(hào)所對(duì)應(yīng)的序列進(jìn)行統(tǒng)計(jì)計(jì)數(shù)，得出頻繁一項(xiàng)集，存儲(chǔ)結(jié)構(gòu)的轉(zhuǎn)換如圖3所示。

圖3 數(shù)據(jù)結(jié)構(gòu)轉(zhuǎn)換過程

改進(jìn)后實(shí)現(xiàn)的RDD血統(tǒng)如圖4所示。首先，以flatMap()將數(shù)據(jù)按行讀入，然后再利用flatMap()方法，將數(shù)據(jù)以Item項(xiàng)為單位分隔。分割完畢，用map()方法將每個(gè)Item項(xiàng)轉(zhuǎn)換為(Item,Tid)鍵值對(duì)。之后再使用reduceByKey()方法將相同Item項(xiàng)的Tid進(jìn)行連接，生成(Item,TidSet)鍵值對(duì)，并使用filter()把候選項(xiàng)集中頻度小于最小支持度的項(xiàng)過濾，得到頻度大于最小支持度的(Item,TidSet)對(duì)，而后采用map()的方式，收集對(duì)應(yīng)鍵值對(duì)的鍵值，得到所有頻繁一項(xiàng)集。此后，利用頻繁一項(xiàng)集對(duì)原數(shù)據(jù)集進(jìn)行過濾，剔除不包含頻繁一項(xiàng)集的事務(wù)序列，算法1為獲取頻繁一項(xiàng)集所使用的算法。

算法1：獲取頻繁一項(xiàng)集

Foreach transaction t(Tid,Items) in T

flatMap(line,t)

Foreach item I in t

out(I,Tid)

End Foreach

End flatMap

End Foreach

ReduceByKey(I,Tid)

TidSet =“”

While(Item I in partition)

TidSet+=Tid

End While

If(TidSet.size>=support)

L1+=(I,TidSet)

End if

End reduceByKey

(2)按照投影樹的思想，頻繁二項(xiàng)集應(yīng)當(dāng)使用頻繁一項(xiàng)集兩兩組合，基于第一步對(duì)數(shù)據(jù)結(jié)構(gòu)的改進(jìn)，可以將遍歷數(shù)據(jù)集求項(xiàng)集出現(xiàn)次數(shù)改進(jìn)為將兩個(gè)對(duì)應(yīng)的TidSet求交來產(chǎn)生，但因頻繁二項(xiàng)候選集的組合爆炸以及頻繁一項(xiàng)集對(duì)應(yīng)TidSet數(shù)據(jù)量較大，會(huì)產(chǎn)生疊加效應(yīng)，使得這一部分產(chǎn)生巨大的計(jì)算量。故需對(duì)該步驟進(jìn)行改良。

圖5 第二階段RDD血統(tǒng)

算法2: 頻繁二項(xiàng)集的生成和篩選

T’=T.filter(include k1)

Read L1 from RDD

Foreach Ii in k1

Foreach Ij in k1

if(Ii

C2=Ii +Ij

End if

End Foreach

End Foreach

Foreach transaction t in T′

flatMap(line offeset, t)

Foreach candidate c in ct

out(c,Tid)

End Foreach

End flatMap

End foreach

reduceByKey (c , Tid)

TidSet =“”

While(Item c in partition)

TidSet+=Tid

End While

If(TidSet.size>=Support)

L2+=(c,TidSet)

End If

End reduceByKey

(3)在這一階段，將以投影樹的方式，按照寬度優(yōu)先，迭代地以頻繁k項(xiàng)集產(chǎn)生頻繁(k+1)項(xiàng)集。因?yàn)橥队皹渲兴许?xiàng)目均按字典序排列，故動(dòng)態(tài)項(xiàng)目表即對(duì)應(yīng)節(jié)點(diǎn)的兄弟節(jié)點(diǎn)所對(duì)應(yīng)項(xiàng)目集的最后一項(xiàng)，所以在具體操作時(shí)，可利用該節(jié)點(diǎn)項(xiàng)目集依次與兄弟節(jié)點(diǎn)的項(xiàng)目集進(jìn)行連接，產(chǎn)生子節(jié)點(diǎn)對(duì)應(yīng)的候選項(xiàng)目集，即在頻繁k項(xiàng)集集合Fk中將前(k-1)項(xiàng)相同的兩個(gè)頻繁k項(xiàng)集進(jìn)行自連接，以模擬投影樹的頻繁項(xiàng)集連接動(dòng)態(tài)項(xiàng)生成候選項(xiàng)集的過程。針對(duì)產(chǎn)生的候選項(xiàng)集，植入Apriori的先驗(yàn)性質(zhì)加以改進(jìn)，檢驗(yàn)候選項(xiàng)集的所有子集是否是頻繁的，這樣可以極大地縮小候選項(xiàng)集的數(shù)量，不僅減少了集群節(jié)點(diǎn)間通信消耗，也減少了后續(xù)的運(yùn)算量。

在算法的第二步中，數(shù)據(jù)在結(jié)構(gòu)上已經(jīng)被轉(zhuǎn)換為鍵值對(duì)的形式，故在搜索頻繁項(xiàng)集的過程當(dāng)中，我們可以將支持度計(jì)數(shù)的過程改進(jìn)為使用已知的自連接事務(wù)的事務(wù)序列求交集來得到包含候選項(xiàng)集的事務(wù)編號(hào)。得到的序列便是由包含該特定項(xiàng)集的事務(wù)編號(hào)所組成的，而無關(guān)事務(wù)編號(hào)將會(huì)被自動(dòng)刪除。在這個(gè)過程中，利用集合求交的快速運(yùn)算代替遍歷數(shù)據(jù)集求候選項(xiàng)的頻數(shù)，既能節(jié)省大量時(shí)間，還可以消除遍歷無關(guān)事務(wù)帶來的損耗，最終得到包含候選項(xiàng)集的事務(wù)序列。之后對(duì)新的TidSet進(jìn)行統(tǒng)計(jì)計(jì)數(shù)，并使用最小支持度計(jì)數(shù)進(jìn)行判別，如果大于最小支持度，我們就將新生成的頻繁項(xiàng)集和包含該項(xiàng)集的TidSet組成的鍵值對(duì)，存入F(k+1)當(dāng)中。

該階段實(shí)現(xiàn)流程如下，首先將滿足條件的頻繁k項(xiàng)集自連接，產(chǎn)生候選(k+1)項(xiàng)集，然后使用subsetOf()方法鑒別候選項(xiàng)集是否滿足Apriori性質(zhì)，若檢驗(yàn)為真，則將自連接時(shí)所使用的兩個(gè)項(xiàng)集的TidSet集合交叉計(jì)算，并利用候選項(xiàng)集和交叉計(jì)算得到的結(jié)果組成新的(ItemSet,TidSet)。之后，再使用filter()方法，將TidSet事務(wù)編號(hào)數(shù)小于最小支持度的項(xiàng)過濾，產(chǎn)生頻繁(k+1)項(xiàng)集。利用這種方法，可以將遍歷原數(shù)據(jù)集轉(zhuǎn)換為快速的集合求交運(yùn)算，并刪除了無關(guān)事務(wù)，極大地提高了運(yùn)算效率，算法3是第三階段所采用算法的偽代碼。

算法3：生成頻繁k+1項(xiàng)集

Read L(k) from RDD

Foreach li in L(k)

Foreach lj in L(k)

if(li[1]==lj[1] & li[2]==lj[2] & li[3]==lj[3]……li[k]

//篩選滿足自連接條件的頻繁k項(xiàng)集

ItemSet=(li[1],li[2],li[3]…li[k-1],li[k],lj[k])

if(has_infrequent_subset(ItemSet , Lk ))

//驗(yàn)證是否滿足Apriori性質(zhì)

TidSet = li._2 ∩ lj._2

If(TidSet.size>=support)

L(k+1)+=(ItemSet,TidSet)

End If

End If

End If

End Foreach

End Foreach

3 相關(guān)實(shí)驗(yàn)與分析

實(shí)驗(yàn)室的分布式計(jì)算平臺(tái)由9臺(tái)計(jì)算機(jī)搭建而成，其中主節(jié)點(diǎn)配置為i5處理器，4 GB內(nèi)存，2 TB硬盤。計(jì)算節(jié)點(diǎn)配置為奔騰e2140處理器，1 GB內(nèi)存，500 GB硬盤,Spark集群的環(huán)境參數(shù)如下所示：

(1)Ubuntu:14.04

(2)Hadoop version:2.4.0

(3)Spark version:1.6.1

為了驗(yàn)證PTBS算法的正確性，使用數(shù)據(jù)集T10I4D100K、Pumsb_star和chess與同類型關(guān)聯(lián)規(guī)則挖掘算法YAFIM進(jìn)行比對(duì)，在得到計(jì)算結(jié)果并進(jìn)行簡(jiǎn)要分析之后，發(fā)現(xiàn)實(shí)驗(yàn)結(jié)果基本是一致的。

3.1 加速比測(cè)試

為了對(duì)PTBS算法的運(yùn)算效率以及擴(kuò)展性加以考量，我們首先要是用自己生成的數(shù)據(jù)集對(duì)算法進(jìn)行測(cè)試。在生成數(shù)據(jù)時(shí)，選擇將項(xiàng)目數(shù)定位60，且為形成對(duì)比實(shí)驗(yàn)的效果，分別生成10 G、20 G、30 G大小不一的3組數(shù)據(jù)，用作進(jìn)一步的實(shí)驗(yàn)。

加速比是指相同的任務(wù)量，使用單一處理器進(jìn)行運(yùn)算所使用的時(shí)間與使用多個(gè)處理器運(yùn)算所使用的時(shí)間的比值。是一個(gè)被用作判斷算法并行是否有效的重要標(biāo)準(zhǔn)。應(yīng)用之前生成的3組人工數(shù)據(jù)分別對(duì)算法進(jìn)行檢驗(yàn)。為提高實(shí)驗(yàn)的可參考性，我們使用3個(gè)數(shù)據(jù)集在包含4個(gè)節(jié)點(diǎn)、6個(gè)節(jié)點(diǎn)以及8個(gè)節(jié)點(diǎn)的不同實(shí)驗(yàn)環(huán)境下進(jìn)行數(shù)據(jù)處理，實(shí)驗(yàn)結(jié)果如圖6所示。為使效果圖更為明顯，在折線圖中加入了線性加速比結(jié)果。

圖6 加速比測(cè)試

從圖6可以看出，在處理相同數(shù)據(jù)集的情況下，在增加節(jié)點(diǎn)數(shù)之后，算法的運(yùn)算效率是有明顯提高的，而且運(yùn)算速率的增加是趨近于線型增長(zhǎng)的。但與標(biāo)準(zhǔn)線型增長(zhǎng)相比較，還是有一定的差別。其原因在于：節(jié)點(diǎn)增加之后，各節(jié)點(diǎn)之間協(xié)調(diào)工作變得更加頻繁，故數(shù)據(jù)的傳輸與節(jié)點(diǎn)通信數(shù)據(jù)量會(huì)大幅度增加，所以效率的增加要比理想值低。在對(duì)比不同數(shù)據(jù)量的加速比時(shí)我們發(fā)現(xiàn)，隨著數(shù)據(jù)量的增長(zhǎng)，加速比效率隨著節(jié)點(diǎn)數(shù)的提高更為明顯，原因在于：數(shù)據(jù)量的增長(zhǎng)使得數(shù)據(jù)傳輸時(shí)間與運(yùn)算時(shí)間的比值越來越大，最終趨近于無窮小。

實(shí)驗(yàn)數(shù)據(jù)表明，PTBS具備了一定的可擴(kuò)展性。

3.2 數(shù)據(jù)的可擴(kuò)展性測(cè)試

為了進(jìn)一步驗(yàn)證算法的數(shù)據(jù)可擴(kuò)展性，對(duì)PTBS算法與YAFIM算法進(jìn)行了對(duì)比實(shí)驗(yàn)，以評(píng)估算法的運(yùn)行效率。為保證實(shí)驗(yàn)的客觀性，特使用公共測(cè)試數(shù)據(jù)集T10I4D100K、Pumsb_star和chess。其中，T10I4D100K包含100 000個(gè)事務(wù)，每個(gè)事務(wù)包含870個(gè)項(xiàng)；Pumsb_star包含事物數(shù)49 049，每個(gè)事務(wù)有2113個(gè)項(xiàng)；chess包含實(shí)物數(shù)3196，每個(gè)事務(wù)包含75個(gè)項(xiàng)。為了確保實(shí)驗(yàn)結(jié)果的精確性，圖中的值為算法運(yùn)行10次的平均值。

圖7 數(shù)據(jù)可擴(kuò)展性測(cè)試

為了檢驗(yàn)PTBS算法的數(shù)據(jù)擴(kuò)展性能，將集群的運(yùn)算節(jié)點(diǎn)數(shù)設(shè)置為8個(gè)，使用原始數(shù)據(jù)生成實(shí)驗(yàn)所需要的多個(gè)數(shù)據(jù)集，分別將數(shù)據(jù)復(fù)制2、3、4、5、6倍，形成大小不一的4個(gè)數(shù)據(jù)集，再進(jìn)行多次對(duì)比實(shí)驗(yàn)，以驗(yàn)證PTBS算法的擴(kuò)展性。實(shí)驗(yàn)的數(shù)據(jù)結(jié)果以折線圖的形式表示，如圖7(a)、圖7(b)、圖7(c)所示。其中X軸表示所使用的數(shù)據(jù)集為原數(shù)據(jù)的數(shù)據(jù)量倍數(shù)，Y軸表示處理數(shù)據(jù)所花費(fèi)的時(shí)間。從圖7中的3個(gè)折線圖可以得出結(jié)論，隨著數(shù)據(jù)量的不斷增加，兩個(gè)算法完成任務(wù)的耗時(shí)均呈緩慢的態(tài)勢(shì)逐漸增長(zhǎng)，而PTBS算法耗時(shí)曲線的增長(zhǎng)相對(duì)更為平緩一些。在針對(duì)T10I4D100K(最小支持度為0.25%)的實(shí)驗(yàn)中，相對(duì)于YAFIM運(yùn)行效率的提升，PTBS的運(yùn)行效率提高從開始的22%攀升到最終的32%，可見隨著數(shù)據(jù)集的不斷擴(kuò)大，算法效率的提高愈發(fā)明顯。而在數(shù)據(jù)集Pumsb_star(最小支持度為65%)的實(shí)驗(yàn)中，數(shù)據(jù)未復(fù)制時(shí)，YAFIM執(zhí)行時(shí)間為16 s，PTBS執(zhí)行時(shí)間13 s，效率提高12%。在數(shù)據(jù)不斷擴(kuò)增的情況下，PTBS的運(yùn)算效率提高分別為15%、12%(可能由于數(shù)據(jù)集本身的屬性特征提高不大)、30%、32.5%、36.4%，效率提高的百分比也在不斷地增長(zhǎng)。在最后一個(gè)關(guān)于數(shù)據(jù)集chess(最小支持度為85%)的實(shí)驗(yàn)中，也可以發(fā)現(xiàn)，PTBS運(yùn)算效率與YAFIM相比，從最初的提升17.8%到最終提升28.5%，算法效率的提升會(huì)隨著數(shù)據(jù)量的增加而增加。分析原因，YAFIM的每一次迭代都需要遍歷整個(gè)數(shù)據(jù)集，而PTBS通過改變數(shù)據(jù)組織結(jié)構(gòu)的方式，把遍歷數(shù)據(jù)集計(jì)數(shù)轉(zhuǎn)化為兩個(gè)TidSet求交然后再計(jì)數(shù)，利用集合的求交操作代替了重復(fù)遍歷數(shù)據(jù)集的過程，同時(shí)也避免了對(duì)大量無關(guān)事物的遍歷，提高了運(yùn)算效率,減少了節(jié)點(diǎn)間的網(wǎng)絡(luò)通信量。所以，可以得到結(jié)論：相較于YAFIM而言，PTBS算法具有更高的數(shù)據(jù)可擴(kuò)展性。

3.3 節(jié)點(diǎn)的可擴(kuò)展性測(cè)試

為了檢驗(yàn)PTBS算法的節(jié)點(diǎn)可擴(kuò)展性，我們選用3個(gè)公共數(shù)據(jù)集T10I4D100K、Pumsb_star和chess對(duì)算法進(jìn)行測(cè)試，在測(cè)試的過程中，我們還需要不斷地將集群的運(yùn)算節(jié)點(diǎn)調(diào)整為4、6、8個(gè)，以形成對(duì)照，而在此期間，實(shí)驗(yàn)所使用的數(shù)據(jù)集保持不變。在不同環(huán)境下記錄算法處理完成數(shù)據(jù)所使用的時(shí)間，實(shí)驗(yàn)結(jié)果以折線圖的形式表示，如圖8(a)、圖8(b)、圖8(c)所示。其中X軸表示集群當(dāng)中運(yùn)算節(jié)點(diǎn)的個(gè)數(shù)，Y軸代表PTBS完成數(shù)據(jù)處理所消耗的時(shí)間。由多個(gè)實(shí)驗(yàn)圖對(duì)比分析可知，在增加運(yùn)算節(jié)點(diǎn)數(shù)之一變量后，PTBS算法處理等量數(shù)據(jù)所消耗的時(shí)間逐次遞減，且遞減的趨勢(shì)近似于線型，結(jié)果表明，該算法具有良好的節(jié)點(diǎn)可擴(kuò)展性。

圖8 節(jié)點(diǎn)可擴(kuò)展性測(cè)試

4 結(jié)束語

頻繁項(xiàng)集挖掘是一門從數(shù)據(jù)集中提取知識(shí)的重要技術(shù)，針對(duì)互聯(lián)網(wǎng)普及所帶來的數(shù)據(jù)井噴式的增長(zhǎng)，我們把原有的串行投影樹算法進(jìn)行了多方面的優(yōu)化改進(jìn)，再根據(jù)Spark云數(shù)據(jù)計(jì)算框架的技術(shù)特性加以完善并最終實(shí)現(xiàn)，成功地將原有算法與大數(shù)據(jù)技術(shù)相融合，實(shí)現(xiàn)了對(duì)海量數(shù)據(jù)關(guān)聯(lián)規(guī)則挖掘技術(shù)的突破，與此同時(shí)也為后續(xù)的算法改進(jìn)提供了有意義的解決算法并行化的方式，諸如如何解決重復(fù)遍歷原始數(shù)據(jù)集，如何處理產(chǎn)生頻繁二項(xiàng)集時(shí)因組合爆炸帶來的大量的交叉計(jì)算等問題。最終使用多組對(duì)比實(shí)驗(yàn)，驗(yàn)證了我們對(duì)于算法并行化改進(jìn)的操作是有效的，并且在數(shù)據(jù)量不斷增大的過程當(dāng)中，算法改進(jìn)所帶來的運(yùn)算效率的提升會(huì)有更為顯著的效果。