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

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

0 引 言

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

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

1 FP-Growth算法描述

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

1.1 構建FP-Tree

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

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

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

1.2 FP-Tree挖掘

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

1.3 FP-Growth算法挖掘實例

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

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

算法挖掘流程如下:

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

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

(2)對D進行第二次掃描，生成FP-Tree以及頭結點列表，如圖1所示。

圖1 生成的FP-Tree

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

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

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

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

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

圖2 SFPG算法流程圖

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

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

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

步驟四中，將所有頻繁項集進行合并，并將結果轉換成所需格式。

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

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

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

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

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

(1)

FP-Tree規(guī)模是由項在F-List中的位置和該項的支持度計數(shù)進行度量。假設項的支持度計數(shù)為sup，項在F-List中的位置為loc。FP-Tree的規(guī)?？勺魅缦鹿烙嫞?/p>

Size=sup×(loc+1)/2

(2)

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

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

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

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

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

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

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

4 實驗結果分析

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

實驗所用Spark集群由三個節(jié)點構成：一個主節(jié)點和三個從節(jié)點(其中一個節(jié)點既是主節(jié)點也是從節(jié)點)，每個節(jié)點的配置為：CPU核數(shù)為4，內存為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ù)據(jù)量、集群節(jié)點個數(shù)對SFPG以及SPFPG算法挖掘效率的影響，同時對SPFPG算法有效性進行了驗證。

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

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

圖6 webdocs.dat數(shù)據(jù)集實驗結果

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

4.2 挖掘時間與集群節(jié)點個數(shù)之間的關系

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

圖7 挖掘時間與集群節(jié)點個數(shù)關系圖

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

4.3 算法有效性驗證

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

(3)

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

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

圖8 SPFPG算法加速比

5 結 語

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