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

1 研究背景

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

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

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

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

2 Spark簡(jiǎn)介

2.1 Spark系統(tǒng)

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

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ù)的計(jì)算框架[8]，該系統(tǒng)可提供流運(yùn)算、迭代運(yùn)算、圖運(yùn)算等解決方案。

2.2 Spark分布式集群搭建

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

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

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

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

3 基于Spark平臺(tái)的FP-Growth算法

3.1 FP-Growth算法工作流程

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3.1 并行計(jì)算項(xiàng)的支持度

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

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

算法2 支持度的計(jì)算過(guò)程

3.3.2 事務(wù)分組策略

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

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

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

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

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

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

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

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

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

4.1 優(yōu)化分組

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖8 OptFP-Spark算法實(shí)現(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后，將對(duì)事務(wù)集均衡分組。先將B_list轉(zhuǎn)換成Map個(gè)數(shù)，再?gòu)暮笙蚯氨闅v，事務(wù)集優(yōu)化分組偽代碼如算法5所示。

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

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

5 對(duì)比實(shí)驗(yàn)與結(jié)果分析

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

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

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

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

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

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

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

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

5.2 支持度對(duì)算法性能的影響

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

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

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

5.3 加速比對(duì)算法性能的影響

為了檢驗(yàn)算法的并行運(yùn)行效率，利用加速比（SpeedUp）這一概念進(jìn)行對(duì)比實(shí)驗(yàn)[12]。算法加速比用于測(cè)試多節(jié)點(diǎn)并行運(yùn)算與單機(jī)運(yùn)算的效率比，本質(zhì)上是通過(guò)運(yùn)行時(shí)間的比較來(lái)實(shí)現(xiàn)的。

式中：T為單機(jī)運(yùn)行時(shí)間；Tn為n個(gè)節(jié)點(diǎn)并行計(jì)算的時(shí)間。

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

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

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

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

6 結(jié)語(yǔ)

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