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

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

1 研究背景

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

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

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

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

2 Spark簡介

2.1 Spark系統(tǒng)

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

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

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

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

2.2 Spark分布式集群搭建

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

圖2為Spark運行構架圖。

圖2 Spark運行構架Fig.2 Schematic diagram of Spark run-time architecture

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

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

3.1 FP-Growth算法工作流程

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

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

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

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

圖3 FP-Spark算法設計Fig.3 FP-Spark algorithm design

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

1）生成Trans。生成彈性分布式數據集RDD數據集，利用彈性分布式數據集的鍵值對操作事務，構成Trans 鍵值對，其中Transactions為事務，times為事務出現的次數。

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

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

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

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

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

3.3 基于Spark的FP-Growth算法關鍵方法

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

3.3.1 并行計算項的支持度

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

算法1 原始數據集轉換到彈性數據集的過程

算法2 支持度的計算過程

3.3.2 事務分組策略

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

圖4 事務集分組示意圖Fig.4 Process of transaction grouping

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

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

算法3 劃分事務集

Return Group_list< groupid，該組的事務集 >

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

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

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

4.1 優(yōu)化分組

為了實現數據的均衡劃分，只需將頻繁項集在F_list的序號視為負載權值，在保證負載權重總和相差不大時，即可將數據劃分均衡化。假設分組個數是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中負載權值平均分布，從而達到均衡分組，使得Spark集群上的節(jié)點量保持相對一致，提升了整個集群的運行效率，同時也提高了FP-Spark算法的效率。

4.2 優(yōu)化項頭表結構

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

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

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

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

2）Hash表結構是（key，value）的二元組，key為事務項編碼，value為對應的鏈表指針，指向在FP-Tree出現的位置。排序時根據項目名查找哈希表，找出下標值，且設置對應的布爾值為True。

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

4）優(yō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)化后的項頭表結構將傳統(tǒng)算法的時間復雜度由原來的O(n2)降低到O(n)，算法效率有很大提升；增加的flag標志位能減少遞歸所占用的資源，雖然空間復雜度有所消耗，但是在可以接受的范圍內。優(yōu)化了項頭表結構后，大大提高了整個算法的運行效率。

4.3 OptFP-Spark算法實現步驟

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

1）生成Trans。首先將事物集轉換成彈性數據集RDD，在彈性數據集RDD上對事務進行map和reduceByKey操作，構成Trans鍵值對，其中Transactions是事務，times是事務出現的次數。

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

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

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

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

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

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

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

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

圖8 OptFP-Spark算法實現圖Fig.8 Optimized FP-Spark algorithm diagram

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

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

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

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

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

5 對比實驗與結果分析

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

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

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

表1 數據集表Table1 Table of data sets

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6 結語

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