馮興杰，潘 軒

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

0 引 言

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

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

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

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

1.1 Spark并行計算框架

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

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

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

圖1 Spark運行模式

1.2 廣播變量

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

圖2 廣播變量工作模式

1.3 頻繁項集挖掘算法

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

2 基于Spark的投影樹頻繁項集挖掘算法—PTBS

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

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

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

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

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

算法1：獲取頻繁一項集

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

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

算法2: 頻繁二項集的生成和篩選

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項集產(chǎn)生頻繁(k+1)項集。因為投影樹中所有項目均按字典序排列，故動態(tài)項目表即對應(yīng)節(jié)點的兄弟節(jié)點所對應(yīng)項目集的最后一項，所以在具體操作時，可利用該節(jié)點項目集依次與兄弟節(jié)點的項目集進行連接，產(chǎn)生子節(jié)點對應(yīng)的候選項目集，即在頻繁k項集集合Fk中將前(k-1)項相同的兩個頻繁k項集進行自連接，以模擬投影樹的頻繁項集連接動態(tài)項生成候選項集的過程。針對產(chǎn)生的候選項集，植入Apriori的先驗性質(zhì)加以改進，檢驗候選項集的所有子集是否是頻繁的，這樣可以極大地縮小候選項集的數(shù)量，不僅減少了集群節(jié)點間通信消耗，也減少了后續(xù)的運算量。

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

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

算法3：生成頻繁k+1項集

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項集

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

if(has_infrequent_subset(ItemSet , Lk ))

//驗證是否滿足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)實驗與分析

實驗室的分布式計算平臺由9臺計算機搭建而成，其中主節(jié)點配置為i5處理器，4 GB內(nèi)存，2 TB硬盤。計算節(jié)點配置為奔騰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

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

3.1 加速比測試

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

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

圖6 加速比測試

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

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

3.2 數(shù)據(jù)的可擴展性測試

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

圖7 數(shù)據(jù)可擴展性測試

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

3.3 節(jié)點的可擴展性測試

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

圖8 節(jié)點可擴展性測試

4 結(jié)束語

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