一種改進(jìn)的并行關(guān)聯(lián)規(guī)則增量更新算法研究

王 誠(chéng)，趙申屹

(南京郵電大學(xué) 通信與信息工程學(xué)院，江蘇 南京 210003)

0 引 言

在現(xiàn)實(shí)的挖掘過程中通常存在增量更新[1]問題。挖掘?qū)ο蟮臄?shù)據(jù)集和支持度會(huì)發(fā)生變化，使用靜態(tài)關(guān)聯(lián)挖掘方法需要反復(fù)對(duì)更新后的數(shù)據(jù)集進(jìn)行掃描，原有的挖掘結(jié)果失去作用，在面對(duì)大規(guī)模數(shù)據(jù)集時(shí)挖掘效率低下。將并行化計(jì)算框架與增量關(guān)聯(lián)算法相結(jié)合，不僅能夠提高挖掘效率，而且在海量數(shù)據(jù)挖掘中有實(shí)際意義。

增量關(guān)聯(lián)規(guī)則[2]出現(xiàn)至今，已有了眾多的研究成果。Agrawal提出了關(guān)聯(lián)規(guī)則挖掘中最著名的Apriori算法。如今的大部分增量關(guān)聯(lián)規(guī)則算法都是基于Apriori算法的改進(jìn)或擴(kuò)展。Cheung等闡述了數(shù)據(jù)集變大的增量關(guān)聯(lián)規(guī)則挖掘問題，提出了在數(shù)據(jù)集增加情況下的FUP算法[3]。該算法通過比較原始事務(wù)數(shù)據(jù)庫和新增數(shù)據(jù)庫的項(xiàng)集之間的頻繁和非頻繁關(guān)系，對(duì)頻繁項(xiàng)集進(jìn)行增量更新得到更新后事務(wù)數(shù)據(jù)庫的頻繁項(xiàng)集。由于FUP是基于Apriori算法產(chǎn)生的，需要多次掃描原始數(shù)據(jù)集并且生成大量候選項(xiàng)集，該算法仍存在挖掘效率低下的問題。文獻(xiàn)[4]基于FUP算法，提出了改進(jìn)的UWEP算法。文獻(xiàn)[5]將FUP算法思想應(yīng)用到FP-Growth算法中，提出了FUFP-tree算法。該算法在數(shù)據(jù)更新時(shí)，只需掃描原始事務(wù)數(shù)據(jù)庫中的變動(dòng)部分，無須掃描整個(gè)數(shù)據(jù)庫，從而大幅提高了挖掘效率。

針對(duì)傳統(tǒng)單機(jī)關(guān)聯(lián)挖掘方法在海量數(shù)據(jù)環(huán)境下挖掘效率低的問題，引入分布式并行處理框架[6-8]，如Hadoop、Storm、Spark等。文獻(xiàn)[9]在FUFP-tree算法基礎(chǔ)上，提出了一種基于MapReduce編程框架的并行化模式算法-PFUFP-tree。文獻(xiàn)[10]結(jié)合MapReduce和FUP算法提出了一種并行的增量關(guān)聯(lián)規(guī)則算法-MRFUP。文獻(xiàn)[11]在Apriori算法的基礎(chǔ)上，提出了一種基于Spark框架的并行化算法-AMRDD。

Spark[12]作為一個(gè)新興的大數(shù)據(jù)處理引擎，允許用戶將數(shù)據(jù)加載至內(nèi)存后重復(fù)使用。其基于內(nèi)存的計(jì)算特性使其大數(shù)據(jù)計(jì)算性能大大超過MapReduce。針對(duì)海量數(shù)據(jù)下的關(guān)聯(lián)規(guī)則挖掘和增量更新問題，基于PFP-tree算法[13]的思想，提出一種改進(jìn)的關(guān)聯(lián)規(guī)則增量更新算法(parallel updated frequent pattern growth algorithm on Spark，SPUFP)。該算法優(yōu)化了頻繁模式樹結(jié)構(gòu)和并行計(jì)算分組策略[14]，減小了時(shí)間和空間復(fù)雜度，并結(jié)合Spark編程框架[15]進(jìn)行實(shí)現(xiàn)，使其能夠高效運(yùn)行于Spark平臺(tái)，大幅提高了海量數(shù)據(jù)環(huán)境下的挖掘效率。

1 增量更新算法

增量關(guān)聯(lián)規(guī)則挖掘是指數(shù)據(jù)集變化或者支持度變化時(shí)的關(guān)聯(lián)規(guī)則挖掘。Cheung等提出的快速更新算法FUP，是基于Apriori的增量更新算法，把增量更新后的項(xiàng)集分成4種類型，針對(duì)數(shù)據(jù)集增大的情況進(jìn)行研究。FUP算法的第k次循環(huán)僅需掃描數(shù)據(jù)庫一次，候選項(xiàng)集生成新的頻繁項(xiàng)集前會(huì)根據(jù)在d上的支持度先進(jìn)行修剪，挖掘效率相比更新后的數(shù)據(jù)集中直接使用Apriori算法高很多。但是在對(duì)候選項(xiàng)集支持度進(jìn)行比較時(shí)，該算法仍需多次重復(fù)掃描數(shù)據(jù)集來找出所有的頻繁項(xiàng)集，會(huì)因計(jì)算量的增大導(dǎo)致計(jì)算速度緩慢，內(nèi)存消耗過大。

PFP-tree算法是基于FP-Growth的并行算法，在數(shù)據(jù)輸入前，將原始數(shù)據(jù)集劃分且存儲(chǔ)到不同的節(jié)點(diǎn)上，通過掃描數(shù)據(jù)庫，能夠并行地計(jì)算各個(gè)節(jié)點(diǎn)上項(xiàng)的支持度計(jì)數(shù)，產(chǎn)生頻繁1項(xiàng)集，降序排序生成FList。之后，將FList分成多個(gè)小組，每組包含若干個(gè)項(xiàng)，組成GList，再對(duì)每個(gè)組的事務(wù)組按照傳統(tǒng)的FP-Growth創(chuàng)建FP-tree，根據(jù)GList中的項(xiàng)對(duì)FP-tree進(jìn)行遞歸的頻繁挖掘。然而PFP-tree算法在更新樹結(jié)構(gòu)的過程中需要把更新后的數(shù)據(jù)集壓縮到頻繁模式樹中，會(huì)消耗大量的時(shí)間和存儲(chǔ)空間，當(dāng)數(shù)據(jù)增量較大時(shí)，樹的規(guī)模會(huì)非常大，導(dǎo)致挖掘效率低下。其次，PFP-tree算法在FList的分組步驟中，將FList根據(jù)并行計(jì)算的節(jié)點(diǎn)數(shù)平均分為g個(gè)組，沒有充分考慮不同事務(wù)組計(jì)算的負(fù)載量不同的問題。

2 改進(jìn)的關(guān)聯(lián)規(guī)則增量更新算法

SPUFP算法的主要思想如下：在增量更新過程中，利用已挖掘的原始數(shù)據(jù)集DB的中間結(jié)果建立更新后數(shù)據(jù)集S的頭表，僅需要將新增數(shù)據(jù)集db壓縮到頻繁模式樹中，排除了大量在db中頻繁而在S中非頻繁的項(xiàng)集，減少了挖掘時(shí)間，大幅減小了樹的規(guī)模，釋放出大量?jī)?nèi)存空間。針對(duì)并行計(jì)算中的分組問題，提出了一種優(yōu)化的分組策略，令靠前的分組對(duì)更多的項(xiàng)進(jìn)行挖掘，從而實(shí)現(xiàn)分組間的負(fù)載均衡。

2.1 算法描述

設(shè)定原始事務(wù)數(shù)據(jù)庫為DB，事務(wù)集T={T1,T2,…,Tn}，候選項(xiàng)集為CD，頻繁項(xiàng)集為L(zhǎng)D，原始事務(wù)數(shù)據(jù)庫大小為|DB|；新增數(shù)據(jù)庫為db，頻繁項(xiàng)集為L(zhǎng)d，新增數(shù)據(jù)庫大小為|db|；更新后的數(shù)據(jù)庫為S，S=DB∪db，頻繁項(xiàng)集為L(zhǎng)S，支持度為sup。

輸入：原始事務(wù)數(shù)據(jù)集DB；新增事務(wù)數(shù)據(jù)集db；

輸出：更新后的數(shù)據(jù)集S的頻繁項(xiàng)集LS。

步驟1：掃描原始數(shù)據(jù)集，得到DB的候選1項(xiàng)集CD1，根據(jù)支持度得出頻繁1項(xiàng)集LD1，排序后建立FList，按照分組策略進(jìn)行分組，構(gòu)造DB的頻繁模式樹，對(duì)頻繁模式樹進(jìn)行頻繁項(xiàng)集的挖掘，得到DB的頻繁項(xiàng)集LD。

步驟2：掃描新增數(shù)據(jù)集，得到db的候選1項(xiàng)集Cd1，讀取步驟1中的CD1，合并得到更新后數(shù)據(jù)集S的候選1項(xiàng)集CS1，根據(jù)支持度得出S的頻繁1項(xiàng)集SD1，排序后建立FList’，按照分組策略進(jìn)行分組，構(gòu)造db的頻繁模式樹。

步驟3：對(duì)頻繁模式樹進(jìn)行頻繁項(xiàng)集的挖掘，同時(shí)讀取步驟1中DB的頻繁項(xiàng)集LD，對(duì)生成的每個(gè)頻繁模式k和LD做比較：若k屬于LD，則k是原數(shù)據(jù)集的頻繁項(xiàng)，將k的支持度與在LD對(duì)應(yīng)的支持度計(jì)數(shù)相加可得k在S中的支持度計(jì)數(shù)，如果總計(jì)數(shù)大于S的最小支持度計(jì)數(shù)，則加入S的部分頻繁項(xiàng)集L'，并從LD中刪除該項(xiàng)；若k不屬于LD，則k是新增數(shù)據(jù)集的頻繁項(xiàng)，不能確定在S中是否頻繁，將其加入S的候選集CS。判別LD中剩余的項(xiàng)，如果其支持度計(jì)數(shù)大于S的最小支持度計(jì)數(shù)，則加入L'。

步驟4：掃描原始數(shù)據(jù)集，讀取步驟3中S的候選集CS，判斷是否為S的頻繁項(xiàng)集，將頻繁項(xiàng)集與部分頻繁項(xiàng)集L'合并，便得到更新后數(shù)據(jù)集S的頻繁項(xiàng)集LS。

2.2 分組策略

在利用頻繁1項(xiàng)集排序建立頭表FList后，為執(zhí)行并行計(jì)算，需要將FList中的項(xiàng)目分成g個(gè)小組，把每個(gè)組分得的項(xiàng)目存入名為GList的表中，再分發(fā)至各個(gè)節(jié)點(diǎn)展開并行計(jì)算。文中分組方法如下：設(shè)定FList中的項(xiàng)目數(shù)量為M，GList中小組數(shù)量為g，指針FS和FE分別指向FList的表頭和末尾，指針GS和GE分別指向GList的表頭和末尾。

(1)如果2g≤M，則將FList中FS到FS+M/2全部的項(xiàng)目分到GList中的GS，F(xiàn)S指向FS+M/2+1，GS指向GS+1，令M=M/2，g=g-1，轉(zhuǎn)向步驟4；

(2)如果2g>M，則將FList中FE指向的項(xiàng)目分到GList中的GE，F(xiàn)E指向FE-1，GE指向GE+1，令M=M-1，g=g-1，轉(zhuǎn)向步驟4；

(3)如果g>1，返回步驟1、2；

(4)如果g=1，則將FList中剩余的項(xiàng)目全部分到GList剩余的最后一組中，分組結(jié)束。

3 基于Spark并行計(jì)算實(shí)現(xiàn)

3.1 Spark編程模型

針對(duì)傳統(tǒng)的增量關(guān)聯(lián)規(guī)則算法在面對(duì)海量數(shù)據(jù)集時(shí)挖掘效率低的問題，借助Spark并行計(jì)算框架對(duì)算法進(jìn)行改進(jìn)，提高增量更新效率。

Spark是一個(gè)通用的大規(guī)模數(shù)據(jù)快速處理引擎，將分布式數(shù)據(jù)抽象為彈性分布式數(shù)據(jù)集RDD。RDD是Spark計(jì)算的基礎(chǔ)，支持并行操作，允許用戶將數(shù)據(jù)加載至內(nèi)存中重復(fù)地使用，一個(gè)RDD代表一個(gè)分區(qū)里的數(shù)據(jù)集。每個(gè)RDD的數(shù)據(jù)都以Block的形式存儲(chǔ)于多臺(tái)機(jī)器上。Spark的RDD存儲(chǔ)架構(gòu)如圖1所示。

圖1 RDD存儲(chǔ)架構(gòu)

Spark支持兩種RDD的基本操作(見表1)：轉(zhuǎn)換Transformation和動(dòng)作Action。轉(zhuǎn)換操作屬于延遲計(jì)算，將一個(gè)數(shù)據(jù)集轉(zhuǎn)換成新的數(shù)據(jù)集，當(dāng)一個(gè)RDD轉(zhuǎn)換成另一個(gè)RDD時(shí)并沒有立即進(jìn)行轉(zhuǎn)換，僅僅是記住了數(shù)據(jù)集的邏輯操作。動(dòng)作操作對(duì)數(shù)據(jù)集進(jìn)行計(jì)算并將計(jì)算結(jié)果返回給驅(qū)動(dòng)程序，觸發(fā)Spark作業(yè)的運(yùn)行，真正觸發(fā)轉(zhuǎn)換算子的計(jì)算。Spark中基于RDD的所有轉(zhuǎn)換并不會(huì)即刻被執(zhí)行，而是直到出現(xiàn)動(dòng)作操作請(qǐng)求返回結(jié)果時(shí)，轉(zhuǎn)換操作才被執(zhí)行，減少了不必要的計(jì)算和返回。另外，RDD支持內(nèi)容的持久化，把內(nèi)容保存在各節(jié)點(diǎn)的內(nèi)存中，不會(huì)被覆蓋或者刪除，這樣下次調(diào)用RDD時(shí)就不必創(chuàng)建新的RDD，加快了計(jì)算速度。

表1 RDD基本操作

Spark的結(jié)構(gòu)與MapReduce類似，由一個(gè)Master節(jié)點(diǎn)和若干個(gè)worker組成。用戶通過編寫程序Driver與Master進(jìn)行交互，將所有定義好的RDD操作提交到Master，Master再把接受的RDD操作分發(fā)給各個(gè)worker。worker收到操作后，根據(jù)數(shù)據(jù)分塊的信息，選擇相應(yīng)數(shù)據(jù)進(jìn)行操作，生成新的RDD。

3．2 基于Spark的增量頻繁模式樹算法

文中的關(guān)聯(lián)增量更新算法基于Spark并行計(jì)算框架實(shí)現(xiàn)，算法主要分為兩個(gè)階段。第一階段，對(duì)原始數(shù)據(jù)集DB進(jìn)行并行挖掘并保留計(jì)算結(jié)果；第二階段，在新增數(shù)據(jù)庫db中，通過使用原數(shù)據(jù)庫DB的挖掘結(jié)果完成更新后數(shù)據(jù)庫S的頻繁項(xiàng)挖掘。

3.2.1 對(duì)原始數(shù)據(jù)庫的挖掘

設(shè)定原始事務(wù)數(shù)據(jù)庫為DB，事務(wù)集T={T1,T2,…,Tn}，候選項(xiàng)集為CD，頻繁項(xiàng)集為L(zhǎng)D，原始事務(wù)數(shù)據(jù)庫大小為|DB|；新增數(shù)據(jù)庫為db，頻繁項(xiàng)集為L(zhǎng)d，新增數(shù)據(jù)庫大小為|db|；更新后的數(shù)據(jù)庫為S，S=DB∪db，頻繁項(xiàng)集為L(zhǎng)S，支持度為sup。

輸入：原始數(shù)據(jù)集DB；

輸出：原始數(shù)據(jù)集DB的頻繁項(xiàng)集LD。

步驟1：將原始數(shù)據(jù)集DB存儲(chǔ)到分布式文件系統(tǒng)HDFS中，數(shù)據(jù)集會(huì)被分割成若干個(gè)數(shù)據(jù)塊，分發(fā)到各個(gè)工作節(jié)點(diǎn)上，每個(gè)數(shù)據(jù)分塊都分別由多個(gè)事務(wù)Ti={item1,item2,…,itemn}組成。通過textfile讀取數(shù)據(jù)并存入RDD中，對(duì)每個(gè)數(shù)據(jù)分塊進(jìn)行flatmap操作，過程中遍歷所有事務(wù)Ti中的項(xiàng)，以itemi為鍵，1為值，輸出(item,1)形式的鍵值對(duì)。再利用reduceByKey操作累計(jì)項(xiàng)目數(shù)，將擁有相同鍵的值進(jìn)行累加，輸出(item, count)的鍵值對(duì)，count表示對(duì)應(yīng)項(xiàng)的總計(jì)數(shù)，得到原始數(shù)據(jù)集DB的候選1項(xiàng)集CD1。

步驟2：以步驟1的結(jié)果作為輸入，通過filter操作，過濾掉總計(jì)數(shù)低于最小支持度的項(xiàng)，剩下的項(xiàng)即為頻繁1項(xiàng)集LD1。讀取LD1，把所有項(xiàng)根據(jù)計(jì)數(shù)count降序排列存入FList，再根據(jù)并行計(jì)算的節(jié)點(diǎn)數(shù)量分成m個(gè)組，得到GList。通過broadcast操作將GList轉(zhuǎn)換成全局共享變量，以緩存形式分發(fā)到各個(gè)節(jié)點(diǎn)。

步驟3：GList以哈希表的形式存儲(chǔ)，以項(xiàng)為鍵，項(xiàng)所在的分組號(hào)g為值。讀取每個(gè)事務(wù)Ti，然后對(duì)事務(wù)中的每個(gè)項(xiàng)item取出Glist中的分組號(hào)g，輸出(g，(item1,item2,…，itemn))的鍵值對(duì)。通過groupByKey操作，將擁有相同分組號(hào)的鍵值對(duì)合并，發(fā)送到同一個(gè)工作節(jié)點(diǎn)，輸出得到(g,Dg)，Dg為各分組號(hào)對(duì)應(yīng)的事務(wù)組。利用foreach操作，對(duì)每個(gè)分組g，讀取其在GList中對(duì)應(yīng)的部分，掃描事務(wù)組Dg，創(chuàng)建根節(jié)點(diǎn)為null的FP-tree。最后調(diào)用growth方法，掃描各個(gè)節(jié)點(diǎn)對(duì)應(yīng)的GList部分，輸出以pattern為鍵，支持度為值的鍵值對(duì)，得到原始數(shù)據(jù)集的頻繁項(xiàng)集LD，保存到HDFS中。

3.2.2 增量更新

輸入：原始數(shù)據(jù)集DB的頻繁項(xiàng)集LD；新增數(shù)據(jù)集db；

輸出：更新后數(shù)據(jù)集S的頻繁項(xiàng)集LS。

步驟1：通過textfile將新增數(shù)據(jù)集db構(gòu)成RDD，db同樣被分布在各個(gè)工作節(jié)點(diǎn)中。類似3.1中的步驟，通過flatmap操作遍歷事務(wù)中所有項(xiàng)得到(item,1)形式的鍵值對(duì)，再通過reduceByKey操作累計(jì)項(xiàng)目數(shù)得到(item, count)的鍵值對(duì)，即為新增數(shù)據(jù)集db的候選1項(xiàng)集Cd1。讀取DB的候選1項(xiàng)集CD1，將結(jié)果與之合并，得到更新后數(shù)據(jù)集S的候選1項(xiàng)集CS1。

步驟2：以S的候選1項(xiàng)集CS1作為輸入，通過filter操作，過濾掉總計(jì)數(shù)低于最小支持度的項(xiàng)，剩下的項(xiàng)即為S的頻繁1項(xiàng)集SD1，按支持度計(jì)數(shù)降序排序后生成FList’，按計(jì)算節(jié)點(diǎn)數(shù)分組得到GList’。讀取DB的分組GList，將在DB中非頻繁而更新后頻繁的項(xiàng)加入分組；將在DB中頻繁而更新后非頻繁的項(xiàng)從分組中刪除，得到處理后的GList*。通過broadcast操作將GList*轉(zhuǎn)換成全局共享變量。通過foreach，對(duì)每個(gè)分組g，讀取原始數(shù)據(jù)集DB在該分組的頻繁項(xiàng)集LD，掃描新增數(shù)據(jù)集在分組中的事務(wù)組dg，創(chuàng)建FP-tree。調(diào)用growth方法進(jìn)行挖掘，過程中掃描DB相應(yīng)分組的頻繁項(xiàng)集LD，對(duì)產(chǎn)生的每個(gè)鍵值對(duì)k，若k屬于LD，則k是原數(shù)據(jù)集的頻繁項(xiàng)，將k的支持度與在LD對(duì)應(yīng)的支持度計(jì)數(shù)相加可得k在S中的支持度計(jì)數(shù)，通過filter操作過濾掉總計(jì)數(shù)低于最小支持度的項(xiàng)，剩下的項(xiàng)為S的部分頻繁項(xiàng)集L'；若k不屬于LD，則k是新增數(shù)據(jù)集的頻繁項(xiàng)，不能確定在S中是否頻繁，將其加入S的候選集CS。

步驟3：讀取原始數(shù)據(jù)集DB，對(duì)每個(gè)數(shù)據(jù)分塊，根據(jù)GList*將DB發(fā)送到相應(yīng)的分組中。對(duì)于每個(gè)分組g，讀取該分組的候選項(xiàng)集CS，掃描原始數(shù)據(jù)集DB在該分組的事務(wù)組，根據(jù)最終生成的支持度計(jì)數(shù)，與最小支持度進(jìn)行比較，得到候選項(xiàng)集CS中包含的S的頻繁項(xiàng)集。將結(jié)果與步驟2中的部分頻繁項(xiàng)集L'相加，即為更新后數(shù)據(jù)集S的頻繁項(xiàng)集LS。

4 實(shí) 驗(yàn)

實(shí)驗(yàn)所用主機(jī)為Intel(R)Core(TM)i3,主頻2 GHz，內(nèi)存2 GB，操作系統(tǒng)為Ubuntu16.04 32位,1臺(tái)為Master節(jié)點(diǎn)，4臺(tái)為worker節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)的配置差異很小。軟件環(huán)境為Hadoop2.7.0，JDK1.8，Spark2.1.0，scala2.12。

實(shí)驗(yàn)數(shù)據(jù)來自http://fimi.ua.ac.be/data/的webdocs.dat.gz數(shù)據(jù)集，容量約為1 450 MB。

4.1 單機(jī)環(huán)境下的算法性能分析

實(shí)驗(yàn)僅在Master節(jié)點(diǎn)上將數(shù)據(jù)集平均分成大小相同的10組，每組包括145 MB數(shù)據(jù)。分別將2組、4組、6組、8組數(shù)據(jù)作為原始數(shù)據(jù)集DB，標(biāo)記為D1、D2、D3、D4,2組數(shù)據(jù)作為更新數(shù)據(jù)集db，最小支持度設(shè)為10%，對(duì)SPUFP算法和PFP-tree算法、傳統(tǒng)FUP算法的運(yùn)行時(shí)間進(jìn)行比較，如圖2所示。

圖2 不同算法運(yùn)行時(shí)間比較

從圖2可以看出，當(dāng)數(shù)據(jù)量較小時(shí)，基于并行計(jì)算框架的算法和傳統(tǒng)的單機(jī)算法的耗時(shí)差別不大。隨著更新數(shù)據(jù)集的增加，兩者計(jì)算的時(shí)間差開始增大，并行算法的挖掘效率明顯提高且保持穩(wěn)定。當(dāng)更新數(shù)據(jù)量繼續(xù)增長(zhǎng)后，SPUFP算法比基于MapReduce[16-17]的PFP-tree算法有了較大的優(yōu)勢(shì)。這是因?yàn)樵谔幚頂?shù)據(jù)量較小時(shí)，并行算法調(diào)度操作的時(shí)間占用算法運(yùn)行總時(shí)間的比例較大；當(dāng)更新數(shù)據(jù)量逐步增大，此比例開始減小，并行算法效率開始優(yōu)于傳統(tǒng)算法；而隨著數(shù)據(jù)集進(jìn)一步增大，由于Spark能夠?qū)⒂?jì)算的中間結(jié)果緩存在內(nèi)存中，節(jié)省了大量I/O操作消耗的時(shí)間，所以效率較MapReduce算法又有了明顯提升。

4.2 分布式集群環(huán)境下的算法性能分析

用多個(gè)參數(shù)相同的節(jié)點(diǎn)搭建Spark集群環(huán)境測(cè)試算法的可擴(kuò)展性，將數(shù)據(jù)集平均分成大小相同的10組，每組包括145 MB數(shù)據(jù)。分別將2組、4組、6組、8組數(shù)據(jù)作為原始數(shù)據(jù)集DB，標(biāo)記為D1、D2、D3、D4，2組數(shù)據(jù)作為更新數(shù)據(jù)集db，最小支持度設(shè)置為10%。分別使用1到4個(gè)worker節(jié)點(diǎn)測(cè)試SPUP算法的運(yùn)行時(shí)間，如圖3所示。

圖3 不同節(jié)點(diǎn)數(shù)運(yùn)行時(shí)間比較

從圖3可以看出，在數(shù)據(jù)量相同條件下，文中并行算法的運(yùn)行時(shí)間隨著worker節(jié)點(diǎn)數(shù)量的增加不斷減少，且更新后的數(shù)據(jù)總量越大，時(shí)間減少的幅度越大，說明SPUFP算法在數(shù)據(jù)集較大的環(huán)境下有良好的可擴(kuò)展性。另一方面，隨著節(jié)點(diǎn)個(gè)數(shù)的增加，不同容量的數(shù)據(jù)集的運(yùn)行時(shí)間差別逐漸變小，這是因?yàn)楣?jié)點(diǎn)增加會(huì)導(dǎo)致集群內(nèi)節(jié)點(diǎn)間通信開銷增大。

5 結(jié)束語

基于頻繁模式樹的思想，提出了一種改進(jìn)的并行關(guān)聯(lián)規(guī)則增量更新算法，優(yōu)化了頻繁模式樹結(jié)構(gòu)和并行計(jì)算分組策略，有效減少了挖掘時(shí)間和存儲(chǔ)空間。實(shí)驗(yàn)結(jié)果表明，Spark靈活的并行計(jì)算框架具備良好的可擴(kuò)展性，其基于內(nèi)存的計(jì)算特點(diǎn)在大規(guī)模數(shù)據(jù)環(huán)境下效率高于Hadoop。在今后的研究中，可以通過Spark等云計(jì)算平臺(tái)對(duì)更多傳統(tǒng)數(shù)據(jù)挖掘算法進(jìn)行改進(jìn)，提高海量數(shù)據(jù)下的挖掘效率。