基于Spark平臺的FP-Growth算法優(yōu)化與實現(xiàn)

（1.湖南省飛機維修工程技術(shù)研究中心，湖南 長沙 410124；2.長沙航空職業(yè)技術(shù)學(xué)院 航空電子設(shè)備維修學(xué)院，湖南 長沙 410124；3.中南大學(xué) 軟件學(xué)院，湖南 長沙 410075）

1 研究背景

在海量數(shù)據(jù)產(chǎn)生的今天，傳統(tǒng)單機的關(guān)聯(lián)規(guī)則挖掘算法在挖掘步驟上耗時多[1]，甚至無法進行關(guān)聯(lián)規(guī)則的挖掘。為解決這一問題，將優(yōu)化的關(guān)聯(lián)算法在Spark并行平臺上進行海量數(shù)據(jù)挖掘，提取出有規(guī)律有意義的數(shù)據(jù)信息，能進一步有效提高大數(shù)據(jù)時代海量數(shù)據(jù)分析的效率。

Apriori算法是主要針對布爾關(guān)聯(lián)規(guī)則的最經(jīng)典、最有影響力的算法。但是該算法會產(chǎn)生大量的候選集，使得復(fù)雜度急劇增大，算法效率大大降低。而且該算法還需要對頻繁項集做大量的IO掃描，耗時且耗資源，對大數(shù)據(jù)的操作缺點明顯。于是，由韓家煒等[2]提出的一種基于迭代FP樹（frequent pattentree，F(xiàn)P-Tree）生成頻繁項集的關(guān)聯(lián)規(guī)則的FPGrowth（frequent patten-growth，F(xiàn)P-Growth）算法很好地解決了Apriori算法的問題。FP-Growth算法是基于迭代FP-Tree生成頻繁項集的關(guān)聯(lián)規(guī)則算法。此算法僅進行兩次數(shù)據(jù)集掃描，遞歸迭代構(gòu)建FP-Tree（FP條件樹），當(dāng)FP-Tree中只有一個單分支時，遞歸迭代構(gòu)建結(jié)束，最終得到頻繁項集，F(xiàn)P-Growth算法在時間、空間復(fù)雜度和數(shù)據(jù)挖掘的效率上都有明顯改善，對于數(shù)據(jù)量較小的數(shù)據(jù)挖掘，F(xiàn)P-Growth改進算法[3]具有一定優(yōu)勢，但隨著數(shù)據(jù)量呈指數(shù)級增長時，這種串行的操作機制會出現(xiàn)內(nèi)存瓶頸或者數(shù)據(jù)挖掘失效等問題。因此，利用Spark平臺的并行計算框架能有效解決這一問題。

國內(nèi)外學(xué)者對關(guān)聯(lián)規(guī)則并行化操作有一定的成果。如黎丹雨等[4]構(gòu)建了一種多層數(shù)據(jù)的模型，在不同層次之間挖掘出頻繁多維序列模式，經(jīng)過協(xié)同過濾輸出TOP-N的推薦項目，但多維序列推薦模型并行挖掘的性能需加強。厙向陽等[5]在關(guān)聯(lián)規(guī)則算法中指出，基于Hadoop的負載均衡數(shù)據(jù)FP-Growth并行算法在數(shù)據(jù)處理方面還有缺陷。M.Adnan等[6]提出了一種 VMM（virtual memory manager）算法，該算法通過虛擬內(nèi)存的管理，利用虛擬內(nèi)存之間的通信實現(xiàn)并行化關(guān)聯(lián)操作，但VMM算法需要消耗很多資源。

而Spark平臺是一種高容錯性的并行計算框架，速度遠超Hadoop，能快速進行大數(shù)據(jù)的分析挖掘，因此，分析Spark平臺的FP-Growth并行化算法的優(yōu)化及該算法的應(yīng)用尤為重要。

2 Spark簡介

2.1 Spark系統(tǒng)

Spark是建立在Java虛擬機（Java virtual machine，JVM）上的開源數(shù)據(jù)平臺框架，不需要涉及操作系統(tǒng)的底層細節(jié)，只借助HDFS（Hadoop distributed file system）存儲系統(tǒng)，就可以進行基于Spark平臺的數(shù)據(jù)分析。因此，Spark平臺是一個通用性較強、成本較低的數(shù)據(jù)平臺。與Hadoop平臺相比較，Spark是基于內(nèi)存的運算框架，是一種基于MapReduce的并行分布式計算框架[7]，具有速度快、效率高等特點。

Spark的核心可以用Spark生態(tài)圈伯克利數(shù)據(jù)分析棧（Berkeley data analytics stack，BDAS）表示，如圖1所示。

圖1 Spark生態(tài)圖Fig.1 A diagram of Spark ecosystem

Spark是一種新興的、快速處理海量數(shù)據(jù)的計算框架[8]，該系統(tǒng)可提供流運算、迭代運算、圖運算等解決方案。

2.2 Spark分布式集群搭建

Spark可以在本地進行單機模式的運行計算，也可以在分布式集群上并行運算。Spark集群實現(xiàn)并行運算時，需要搭建分布式集群，常用的運行模式有Standalone、Yarn-client、Yarn-cluster 3 種。 這 3 種運行模式的不同在于有不同的資源分配方式，由不同的任務(wù)調(diào)度算法來執(zhí)行計算任務(wù)。任意一個Spark程序都有對應(yīng)的Executor進程，而每個Executor進程內(nèi)部有多個Task線程與之對應(yīng)。這種并行的資源分配、調(diào)度模式有利于不同Spark程序間的資源共享，大大提高了執(zhí)行效率。

圖2為Spark運行構(gòu)架圖。

圖2 Spark運行構(gòu)架Fig.2 Schematic diagram of Spark run-time architecture

圖2中，程序運行中通過動作觸發(fā)job，其中job構(gòu)建DAG圖是基于RDD的依賴關(guān)系的，構(gòu)建好的DAG圖再由DAGScheduler解析、構(gòu)建成不同的Stage，并計算Stage間的依賴關(guān)系。然后，由TaskScheduler調(diào)度器分配工作集TaskSet，再劃分成多個線程并行計算，同時將計算結(jié)果返回給TaskScheduler，再返回給DAGScheduler，計算結(jié)果全部完成后返回給驅(qū)動程序或者保存在外部存儲系統(tǒng)中，并將資源全部釋放。

3 基于Spark平臺的FP-Growth算法

3.1 FP-Growth算法工作流程

Apriori算法產(chǎn)生大量數(shù)據(jù)集，造成算法運行效率低下，而FP-Growth算法不用反復(fù)讀取事務(wù)集，且不會生成大量的候選項集，既節(jié)省了內(nèi)存資源又提高了讀寫效率，適合大數(shù)據(jù)量的數(shù)據(jù)挖掘[9]。

FP-Growth算法整個工作過程只進行兩次掃描事務(wù)集：進行第一次事務(wù)集掃描后，利用支持度次數(shù)遞減的規(guī)則將事務(wù)集排序，找出支持度最高的項即頻繁1-項集，將第一次排序的末次項刪除；再進行第二次掃描，過濾后將事務(wù)插入構(gòu)建的FP-Tree中；再從FP-Tree中挖掘頻繁項集后按條件迭代生成條件FPTree，直到FP-Tree中只有一個結(jié)點時結(jié)束，將挖掘出的頻繁項集合得到頻繁項集。在生成上述頻繁項集的同時，按A-B=>B的置信度大于最小置信度的原則，生成強關(guān)聯(lián)規(guī)則[10]。

3.2 基于Spark的FP-Growth算法思想

基于Spark平臺FP-Growth算法直接遞歸求得每一次排序后支持度最高的頻繁項，并將事物數(shù)據(jù)集分配給各計算節(jié)點，這種利用Spark平臺的FP-Growth算法稱為FP-Spark（FP-Growth-based-on-Spark）算法。此算法先將事物集轉(zhuǎn)換成彈性分布式數(shù)據(jù)集（resilient distributed datasets，RDD），再在各計算節(jié)點上對頻繁項集進行并行數(shù)據(jù)挖掘。FP-Spark算法設(shè)計如圖3所示。

圖3 FP-Spark算法設(shè)計Fig.3 FP-Spark algorithm design

FP-Spark算法步驟可分成如下6步。

1）生成Trans。生成彈性分布式數(shù)據(jù)集RDD數(shù)據(jù)集，利用彈性分布式數(shù)據(jù)集的鍵值對操作事務(wù)，構(gòu)成Trans 鍵值對，其中Transactions為事務(wù)，times為事務(wù)出現(xiàn)的次數(shù)。

2）生成頻繁1-項集F_list。先將Trans進行flatMap操作，把Trans中的Transactions分成一個個事務(wù)項；再利用reduceByKey操作生成鍵值對，事務(wù)項由item表示，支持度計數(shù)由support表示；然后經(jīng)過RDD的collect、toArray操作，將RDD輸出成list格式，按照sortBySupport降序排序，過濾掉最小支持度項后，得到頻繁項集F_list。

3）構(gòu)建Group_list。根據(jù)頻繁項集F_list，把Trans中的Transactions重新排序，過濾掉非頻繁項，再按一定方式分組，得到Group_list，其中id為組號，super_Trans為屬于該組的事務(wù)集。

4）生成頻繁模式序列。將Group_list中的事務(wù)分布到各節(jié)點，利用 flapMap調(diào)用FP-Growth算法，構(gòu)建FP-Tree，遞歸挖掘FP-Tree，生成頻繁模式序列。

5）合并頻繁項集。將上一步驟生成的頻繁模式序列轉(zhuǎn)碼合并，寫入HDFS。

6）生成強關(guān)聯(lián)規(guī)則。先產(chǎn)生后項是一項的關(guān)聯(lián)規(guī)則，再兩兩合并后項，由兩項的候選關(guān)聯(lián)規(guī)則生成后項，其中的強關(guān)聯(lián)規(guī)則由最小置信度閾值而得，依次反復(fù)逐層生成強關(guān)聯(lián)規(guī)則。

3.3 基于Spark的FP-Growth算法關(guān)鍵方法

基于Spark的FP-Growth算法（也叫做FPSpark算法）關(guān)鍵點是并行計算項的支持度和將事務(wù)集排序過濾后的分組策略。

3.3.1 并行計算項的支持度

按照上述6個步驟中的生成頻繁項集F_list，按照降序排序支持度和頻繁1-項集。算法1是將原始數(shù)據(jù)集轉(zhuǎn)換到彈性數(shù)據(jù)集的過程，算法2是計算支持度的過程。

算法1 原始數(shù)據(jù)集轉(zhuǎn)換到彈性數(shù)據(jù)集的過程

算法2 支持度的計算過程

3.3.2 事務(wù)分組策略

將事務(wù)集Trans進行挖掘頻繁1項集過濾得到F_list，映射map，其中Transactions表示事務(wù)項名稱，times表示在頻繁1項集中出現(xiàn)的次數(shù)，并將Trans集合利用map映射到F_map中。映射過程中，對Trans_id排序后過濾非頻繁項；其中Trans的每個事務(wù)，按F_map的將times的編碼按升序排序，刪除非頻繁項后得到Trans_list，其中每一條事務(wù)項按支持度計數(shù)遞減排序，且都大于最小支持度計數(shù)。圖4是對事務(wù)集分組的示意圖。

圖4 事務(wù)集分組示意圖Fig.4 Process of transaction grouping

FP-Spark算法分組策略依據(jù)F_list的分組情況對Trans_list進行分組。首先求出每個分組的最大個數(shù)g_size：利用F_list的長度除以節(jié)點數(shù)向下取整后加1。

然后將F_list中的項依次分到Spark集群節(jié)點上，集群節(jié)點與groupid一一對應(yīng)，成為FP-Spark算法挖掘時對應(yīng)的表頭項；再對事務(wù)集數(shù)據(jù)分組。算法3為對事務(wù)集分組的偽代碼。

算法3 劃分事務(wù)集

Return Group_list< groupid，該組的事務(wù)集 >

從后往前遍歷，如果T_list[i]所屬的groupid沒有出現(xiàn)過，則此事務(wù)還沒有劃分到該組，將T_list[0]到T_list[i]劃分到該組；若groupid出現(xiàn)過，則不做任何操作，跳過此項，i-1，往前遍歷，直到?jīng)]出現(xiàn)過該組。

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

基于Spark的FP-Growth算法實現(xiàn)了數(shù)據(jù)挖掘頻繁項集的并行化操作，但這種FP-Spark算法的分組策略比較簡單，且算法在進行本地挖掘時使用的項頭表結(jié)構(gòu)是數(shù)組，時間復(fù)雜度較高。針對這兩個問題，課題組提出一種優(yōu)化的均衡分組和新的項頭表結(jié)構(gòu)的FP-Spark算法（稱為OptFP-Spark算法），大大提高了大數(shù)據(jù)處理的效率和性能。

4.1 優(yōu)化分組

為了實現(xiàn)數(shù)據(jù)的均衡劃分，只需將頻繁項集在F_list的序號視為負載權(quán)值，在保證負載權(quán)重總和相差不大時，即可將數(shù)據(jù)劃分均衡化。假設(shè)分組個數(shù)是m個，從F_list的表尾往前遍歷，將m個項依次劃分到第1～m組，再往前將m個項劃分到第m～1組，S形的劃分方式將F_list分組完。優(yōu)化分組的方式如圖5所示。

圖5 優(yōu)化分組方式Fig.5 Optimized grouping

圖5所示的優(yōu)化分組方式，采用S形分組方式，分組后F_list中負載權(quán)值平均分布，從而達到均衡分組，使得Spark集群上的節(jié)點量保持相對一致，提升了整個集群的運行效率，同時也提高了FP-Spark算法的效率。

4.2 優(yōu)化項頭表結(jié)構(gòu)

項頭表結(jié)構(gòu)直接影響著算法的運行效率，因此優(yōu)化項頭表結(jié)構(gòu)能提高算法在構(gòu)造FP-Tree的遍歷效率，進而提高整個算法的效率。優(yōu)化項頭表結(jié)構(gòu)是增加一個哈希表，即利用Hash算法進行優(yōu)化，如圖6所示。

圖6 項頭表結(jié)構(gòu)優(yōu)化圖Fig.6 Optimized head-table diagram

其優(yōu)化的過程如下：

1）初始的項頭表結(jié)點原本是個數(shù)組，包含事務(wù)項和鏈表指針，優(yōu)化后將鏈表指向布爾值，是一個布爾值的指針。當(dāng)指向的布爾指針指向True時，說明屬于此次掃描的事務(wù)項，再將此事務(wù)插入FP-Tree，設(shè)置項表頭結(jié)構(gòu)的布爾值為True。繼續(xù)掃描下一事務(wù)，直至布爾值為False為止。

2）Hash表結(jié)構(gòu)是（key，value）的二元組，key為事務(wù)項編碼，value為對應(yīng)的鏈表指針，指向在FP-Tree出現(xiàn)的位置。排序時根據(jù)項目名查找哈希表，找出下標(biāo)值，且設(shè)置對應(yīng)的布爾值為True。

3）Flag標(biāo)簽有True、False兩種值。單一路徑時頻繁模式樹是True，不是單一路徑則為False。單一路徑的這種獲取頻繁項集的方式，無需遞歸操作，降低了時間和空間的復(fù)雜度，提高了算法效率。

4）優(yōu)化后的項頭表結(jié)構(gòu)也需將FP-Tree的節(jié)點做修改，優(yōu)化后的FP-Tree節(jié)點如圖7所示。

圖7 優(yōu)化前后的FP-TreeFig.7 FP-Tree before and after optimization

由圖7可知，優(yōu)化后的項頭表結(jié)構(gòu)將傳統(tǒng)算法的時間復(fù)雜度由原來的O(n2)降低到O(n)，算法效率有很大提升；增加的flag標(biāo)志位能減少遞歸所占用的資源，雖然空間復(fù)雜度有所消耗，但是在可以接受的范圍內(nèi)。優(yōu)化了項頭表結(jié)構(gòu)后，大大提高了整個算法的運行效率。

4.3 OptFP-Spark算法實現(xiàn)步驟

基于Spark平臺的優(yōu)化FP-Growth算法，也稱OptFP-Spark算法。它既對分組策略進行了優(yōu)化，又對項頭表結(jié)構(gòu)實現(xiàn)了優(yōu)化。其優(yōu)化步驟如下：

1）生成Trans。首先將事物集轉(zhuǎn)換成彈性數(shù)據(jù)集RDD，在彈性數(shù)據(jù)集RDD上對事務(wù)進行map和reduceByKey操作，構(gòu)成Trans鍵值對，其中Transactions是事務(wù)，times是事務(wù)出現(xiàn)的次數(shù)。

2）生成F_list列表。在Trans集合上進行下列flatMap、reduceByKey、collect、toArray和map操作，構(gòu)成頻繁1-項集，把Trans中的Transactions分成一個個事務(wù)項；再利用reduceByKey生成鍵值對；然后經(jīng)過RDD的collect、toArray操作，將RDD輸出成list格式，按照sortBySupport降序排序，過濾掉最小支持度項后，得到頻繁1-項集F_list。

3）構(gòu)建Group_list。根據(jù)頻繁項集F_list，把Trans中的Transaction重新排序，過濾掉非頻繁項，再按優(yōu)化分組的策略將事務(wù)集均衡分組。

①在排序過濾后的F_list分組基礎(chǔ)上，根據(jù)前面提到的優(yōu)化分組策略，進行S形分組，得到新的分組B_list。

②在B_list中實現(xiàn)對Trans事務(wù)集分組，得到Group_list：。其中，groupid為組號，super_Trans為屬于該組的事務(wù)集。

4）并行生成頻繁模式序列。在各worker節(jié)點并行頻繁模式樹挖掘。將Group_list中的事務(wù)分布到各節(jié)點，再在各worker節(jié)點利用優(yōu)化的項頭表結(jié)構(gòu)并行挖掘，生成頻繁模式序列。

5）合并頻繁項集。將上一步驟生成的頻繁模式序列轉(zhuǎn)換格式合并后寫入到HDFS。

6）強關(guān)聯(lián)規(guī)則的產(chǎn)生。在逐層生成頻繁模式序列時，逐層生成強關(guān)聯(lián)規(guī)則。

對OptFP-Spark算法的優(yōu)化，重點是對上述步驟中的第3步和第4步進行，即利用S型的分組策略均衡分組后，再實現(xiàn)優(yōu)化的項表頭結(jié)構(gòu)的并行頻繁模式樹的挖掘，從而得到頻繁模式序列集。OptFPSpark算法的實現(xiàn)過程如圖8所示。

圖8 OptFP-Spark算法實現(xiàn)圖Fig.8 Optimized FP-Spark algorithm diagram

利用S形的優(yōu)化分組算法如算法4所示，將F_list轉(zhuǎn)換成B_list。

算法4F_list優(yōu)化分組

在輸出B_list后，將對事務(wù)集均衡分組。先將B_list轉(zhuǎn)換成Map個數(shù)，再從后向前遍歷，事務(wù)集優(yōu)化分組偽代碼如算法5所示。

算法5 事務(wù)集優(yōu)化分組

在均衡分組輸出Group_list后，利用優(yōu)化的項表頭結(jié)構(gòu)并行頻繁模式序列的挖掘，生成的FP-Tree的子結(jié)點數(shù)組增加hash表。最終生成強關(guān)聯(lián)規(guī)則合并輸出結(jié)果。

5 對比實驗與結(jié)果分析

優(yōu)化的OptFP-Spark算法和FP-Spark算法在兩個大型數(shù)據(jù)集上做對比實驗，考查數(shù)據(jù)規(guī)模和支持度對數(shù)據(jù)挖掘的影響。

實驗采用Spark集群，一個Master主節(jié)點，4個Slave從節(jié)點。實驗數(shù)據(jù)源自數(shù)據(jù)倉庫[11]中下載，D1數(shù)據(jù)集和D2數(shù)據(jù)集的事務(wù)項和事務(wù)是網(wǎng)站真實交易的數(shù)據(jù)，如表1所示，有1.48 GB數(shù)據(jù)量，包括160多萬條事務(wù)，500多萬事務(wù)項。

利用以上數(shù)據(jù)集特征從數(shù)據(jù)規(guī)模、支持度兩個方面對比FP-Spark算法和OptFP-Spark算法的性能。

表1 數(shù)據(jù)集表Table1 Table of data sets

5.1 數(shù)據(jù)規(guī)模對算法性能的影響

將支持度定為0.8，節(jié)點數(shù)量保持不變，測試數(shù)據(jù)規(guī)模對比算法的運行時間。對比實驗選取了D1和D2兩個數(shù)據(jù)集，分別在20萬～100萬事務(wù)集上進行比較，由于D1數(shù)據(jù)集較小，增加了D1數(shù)據(jù)集的拷貝來進行實驗，實驗結(jié)果如圖9所示。

圖9 數(shù)據(jù)規(guī)模對性能的影響Fig.9 The impact of data size on performance

由圖9所示實驗結(jié)果可以得知，隨著數(shù)據(jù)量的增大，優(yōu)化的OptFP-Spark算法的性能明顯提高。因此均衡的分組策略和項頭表結(jié)構(gòu)hash表的優(yōu)化都有利于算法的數(shù)據(jù)挖掘，OptFP-Spark算法的挖掘效率有了明顯提升。

5.2 支持度對算法性能的影響

在節(jié)點數(shù)量不變，支持度分別取不同值時，對比兩個算法的數(shù)據(jù)挖掘性能，得到不同的實驗結(jié)果，如圖10所示。

圖10 支持度對算法性能的影響Fig.10 The influence of support degree on algorithm performance

由圖10所示的實驗結(jié)果可以得知，隨著支持度的增加，數(shù)據(jù)挖掘的時間復(fù)雜度減少，但優(yōu)化的OptFP-Spark算法的性能更優(yōu)，因此均衡的分組策略和項頭表結(jié)構(gòu)hash表的優(yōu)化在數(shù)據(jù)量越大的情況下，性能提升越明顯。

5.3 加速比對算法性能的影響

為了檢驗算法的并行運行效率，利用加速比（SpeedUp）這一概念進行對比實驗[12]。算法加速比用于測試多節(jié)點并行運算與單機運算的效率比，本質(zhì)上是通過運行時間的比較來實現(xiàn)的。

式中：T為單機運行時間；Tn為n個節(jié)點并行計算的時間。

算法保持支持度為0.8，D1和D2數(shù)據(jù)集的兩個算法的對比結(jié)果如圖11所示。

圖11 加速比對算法性能的影響Fig.11 The effect of acceleration ratio on algorithm performance

由圖11所示的實驗結(jié)果可以得知，隨著節(jié)點數(shù)的增加，加速比逐步增加，但OptFP-Spark算法較FP-Spark算法加速比增加的效率更明顯，說明進行優(yōu)化分組策略和項頭表結(jié)構(gòu)后的OptFP-Spark算法性能更優(yōu)。

對比實驗分別從數(shù)據(jù)規(guī)模、支持度和算法的加速比3個方面進行比較，結(jié)果表明，優(yōu)化的OptFPSpark算法具備更好的并行挖掘效果和更高的效率。

6 結(jié)語

本文首先介紹了研究背景和Spark的系統(tǒng)框架，闡述了基于Spark平臺的FP-Growth算法思想及過程，再對該算法在分組策略和項表頭結(jié)構(gòu)上進行優(yōu)化。最后的實驗結(jié)果證明，優(yōu)化的OptFP-Spark算法具有更高的并行運算加速比、更好的并行挖掘效果及更高的效率。