梁璦云，袁 丁，嚴(yán) 清，劉小久

(四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，四川 成都 610101)

0 引 言

關(guān)聯(lián)規(guī)則算法是數(shù)據(jù)挖掘算法中的一個(gè)經(jīng)典算法，其目的在于從海量的、價(jià)值密度低的數(shù)據(jù)中挖掘出潛在的、高價(jià)值的關(guān)聯(lián)關(guān)系[1]，用以輔助用戶獲取有效信息。傳統(tǒng)的Apriori算法設(shè)計(jì)簡(jiǎn)單、結(jié)構(gòu)清晰、易于實(shí)現(xiàn)，盡管如此，該算法仍然有值得優(yōu)化的地方：①大量臨時(shí)形成的無(wú)效項(xiàng)集引發(fā)內(nèi)存溢出；②多次訪問(wèn)數(shù)據(jù)庫(kù)引發(fā)系統(tǒng)I/O負(fù)荷失衡，甚至系統(tǒng)宕機(jī)；③采用單機(jī)環(huán)境實(shí)現(xiàn)，執(zhí)行效率低、花耗時(shí)間長(zhǎng)、實(shí)效性低。值得注意的是，現(xiàn)有的單機(jī)串行的算法運(yùn)行模式已經(jīng)無(wú)法滿足當(dāng)前大數(shù)據(jù)時(shí)代背景下的需求。此時(shí)，MapReduce分布式并行處理框架的出現(xiàn)，正好為關(guān)聯(lián)規(guī)則算法的研究提供了新的思路和研究方向。本文主要針對(duì)關(guān)聯(lián)規(guī)則算法所存在的無(wú)效候選集多、單機(jī)運(yùn)行時(shí)間短等問(wèn)題，提出基于Spark平臺(tái)的Apriori并行優(yōu)化算法(本文簡(jiǎn)稱Apriori_MC_SP算法)，利用矩陣結(jié)構(gòu)，壓縮事務(wù)數(shù)據(jù)庫(kù)的存儲(chǔ)空間，減少了算法的掃描次數(shù)；同時(shí)利用矩陣存儲(chǔ)頻繁k項(xiàng)集，采用分組模式，直接生成局部頻繁k項(xiàng)集，簡(jiǎn)化了頻繁k+1項(xiàng)集的生成過(guò)程；利用Spark分布式計(jì)算框架實(shí)現(xiàn)并行化處理，增加系統(tǒng)的可擴(kuò)展性，提高了算法的執(zhí)行效率。

1 相關(guān)工作

隨著大數(shù)據(jù)分析技術(shù)發(fā)展越來(lái)越成熟，研究學(xué)者們開(kāi)始嘗試將關(guān)聯(lián)規(guī)則算法與并行化技術(shù)相結(jié)合，針對(duì)已有的并行Apriori算法所存在的問(wèn)題，提出了一系列的解決方案。

在國(guó)外，文獻(xiàn)[2]用MapReduce思想提出了一種的Apriori并行化算法，該算法伸縮性較好，但索引能力較差，僅適合處理小量的結(jié)構(gòu)化數(shù)據(jù)集。文獻(xiàn)[3]提出一種有效的關(guān)聯(lián)規(guī)則算法——ScadiBino，將離散化的數(shù)據(jù)集轉(zhuǎn)換為二進(jìn)制編碼，通過(guò)執(zhí)行多個(gè)Map操作和執(zhí)行一個(gè)Reduce操作，實(shí)現(xiàn)算法的并行化處理，提高算法的運(yùn)行效率。文獻(xiàn)[4]提出一種基于Spark平臺(tái)的關(guān)聯(lián)規(guī)則算法YAFIM，該算法引入HashTree概念，對(duì)候選集存儲(chǔ)進(jìn)行優(yōu)化，節(jié)省存儲(chǔ)空間，提高算法的運(yùn)算效率。

在國(guó)內(nèi)，Guo Fangfang等[5]利用水平分割的思想，提出一種基于多叉樹(shù)的并行Apriori算法，該算法利用多叉樹(shù)生成候選項(xiàng)集，有效減少了中間節(jié)點(diǎn)產(chǎn)生候選項(xiàng)集的數(shù)量，降低了數(shù)據(jù)庫(kù)的訪問(wèn)次數(shù)以及各節(jié)點(diǎn)間的通信次數(shù)，有效地節(jié)省了數(shù)據(jù)存儲(chǔ)的空間。Wang Qing等[6]針對(duì)在Hadoop平臺(tái)下MapReduce模型處理節(jié)點(diǎn)失效、基于磁盤(pán)讀取數(shù)據(jù)緩慢等缺陷，將優(yōu)化后的Ariori算法移植到Spark平臺(tái)進(jìn)行實(shí)現(xiàn)，該優(yōu)化方法在一定程度上節(jié)省了內(nèi)存存儲(chǔ)空間，但在Map過(guò)程中產(chǎn)生的大量中間節(jié)點(diǎn)存儲(chǔ)在內(nèi)存中，造成資源浪費(fèi)。Yan Mengjie等[7]基于Spark平臺(tái)提出一種改進(jìn)算法——IABS算法，對(duì)事務(wù)數(shù)據(jù)庫(kù)的轉(zhuǎn)化過(guò)程和候選集產(chǎn)生過(guò)程進(jìn)行優(yōu)化，并與文獻(xiàn)[4]中提出的YAFIM算法進(jìn)行比較，該優(yōu)化算法的性能明顯提高。Niu Hailing等[8]提出一種AMRDD算法，利用Spark平臺(tái)基于內(nèi)存計(jì)算的優(yōu)勢(shì)，運(yùn)用局部剪枝和全局剪枝策略，縮減生成候選項(xiàng)集的數(shù)量，但該算法仍然沒(méi)有解決產(chǎn)生大量無(wú)效候選集的問(wèn)題。Xie Zhiming等[9]基于Hadoop平臺(tái)利用MapReduce框架提出一種Apriori_MMR算法，該算法結(jié)合數(shù)據(jù)劃分的思想，利用矩陣的特性，簡(jiǎn)化候選項(xiàng)集的生成過(guò)程，從而提高算法的性能。

2 基于Spark的Apriori算法的優(yōu)化改進(jìn)

2.1 關(guān)聯(lián)規(guī)則算法的相關(guān)概念

本文采用部分符號(hào)標(biāo)識(shí)及其相關(guān)定義見(jiàn)表1。

本文對(duì)關(guān)聯(lián)規(guī)則算法進(jìn)行優(yōu)化，引入了矩陣的概念，其相關(guān)定義如下：

定義1 事務(wù)布爾矩陣B，矩陣的行表示事務(wù)數(shù)據(jù)集D中的記錄，列表示所有數(shù)據(jù)集中項(xiàng)的集合[15]，其形式如式(1)所示

(1)

表1 部分?jǐn)?shù)學(xué)表達(dá)式定義

定義2 某頻繁k項(xiàng)集{Ii,Ij,…,Ip} 的內(nèi)積運(yùn)算方式，詳細(xì)定義參見(jiàn)文獻(xiàn)[15]，如式(2)所示

(2)

其中，(Ii,Ij,…,Im)?I,B(Ii)表示布爾矩陣中的某Ii列的數(shù)據(jù)。

定義3 某1項(xiàng)集{Ii}的支持度計(jì)數(shù)[14]sup_count滿足如式(3)所示

(3)

定義4 某多項(xiàng)集{Ii,Ij,…,Ip}支持度計(jì)數(shù)的求和運(yùn)算如式(4)所示

(4)

定義5 支持度sup，即項(xiàng)集Ii在整個(gè)數(shù)據(jù)庫(kù)中所得比例，詳細(xì)定義見(jiàn)參見(jiàn)文獻(xiàn)[15]，計(jì)算方式如式(5)所示

sup(Ii)=sup_count(Ii)/counts(D)

(5)

其中，counts(D)表示數(shù)據(jù)庫(kù)D的總事務(wù)數(shù)。

2.2 傳統(tǒng)Apriori算法簡(jiǎn)介

Apriori算法主要采用簡(jiǎn)單的迭代技術(shù)，利用已知的頻繁k項(xiàng)集“自連接”生成候選k+1項(xiàng)集，通過(guò)逐層搜索統(tǒng)計(jì)候選k項(xiàng)集出現(xiàn)的次數(shù)對(duì)候選項(xiàng)集進(jìn)行“剪枝”。其具體實(shí)現(xiàn)流程見(jiàn)表2。

表2 傳統(tǒng)Apriori算法的實(shí)現(xiàn)流程

從表2中可以看出，傳統(tǒng)的Apriori算法不僅會(huì)多次掃描初始數(shù)據(jù)庫(kù)，而且在頻繁k-1項(xiàng)集“連接”過(guò)程中會(huì)形成大批無(wú)用的候選k項(xiàng)集，占用內(nèi)存空間，拖慢執(zhí)行進(jìn)度。為適應(yīng)當(dāng)前大數(shù)據(jù)時(shí)代背景，設(shè)計(jì)高效的算法優(yōu)化方案是非常必要的。

2.3 Apriori優(yōu)化算法描述

本文所提出的Apriori優(yōu)化算法利用“分治”思想，將大型數(shù)據(jù)庫(kù)切割成多個(gè)均勻的數(shù)據(jù)塊，針對(duì)各個(gè)數(shù)據(jù)塊轉(zhuǎn)化為布爾矩陣。該算法主要對(duì)頻繁k(k=2)項(xiàng)集生成頻繁k+1項(xiàng)集的過(guò)程進(jìn)行優(yōu)化。算法具體實(shí)現(xiàn)流程如下：

步驟1 掃描事務(wù)數(shù)據(jù)庫(kù)D，對(duì)數(shù)據(jù)庫(kù)中的數(shù)據(jù)進(jìn)行均勻分塊，分割成n個(gè)相同大小的數(shù)據(jù)塊。

步驟2 當(dāng)k==1時(shí)，將n個(gè)數(shù)據(jù)塊轉(zhuǎn)化為n個(gè)不同的事務(wù)布爾矩陣Bi，形如式(1)所示，生成局部頻繁1項(xiàng)集l_fi1，返回n個(gè)數(shù)據(jù)(Bi,l_fi1),i取值為1,2,3…,n。

在對(duì)數(shù)據(jù)塊進(jìn)行轉(zhuǎn)化為布爾矩陣時(shí)，需注意，當(dāng)生成局部布爾矩陣Bi，對(duì)矩陣進(jìn)行簡(jiǎn)約化處理，即判斷矩陣的每行、列是否均滿足所給條件(行的求和結(jié)果不小于k，列的求和結(jié)果不小于局部支持度計(jì)數(shù))，滿足則保留，不滿足則刪除,如圖1所示。

圖1 事務(wù)布爾矩陣生成過(guò)程

步驟3 當(dāng)k==2時(shí)，連接局部頻繁1項(xiàng)集，直接生成局部頻繁項(xiàng)集l_fi2，采用矩陣進(jìn)行存儲(chǔ)，結(jié)果返回(Mi2,l_fi2)。

對(duì)頻繁1項(xiàng)集中的各項(xiàng)進(jìn)行自連接生成2項(xiàng)集的過(guò)程中，運(yùn)用式(2)、式(3)計(jì)算某2項(xiàng)集的計(jì)數(shù)是否不小于局部支持度計(jì)數(shù)，滿足條件，則將該項(xiàng)集保存到二維矩陣l_fi2中，最后將l_fi2擴(kuò)展為1維數(shù)組，去重后對(duì)分塊矩陣進(jìn)行行列篩選，形成新的矩陣。

步驟4 當(dāng)k>2時(shí)，首先將頻繁k-1項(xiàng)集進(jìn)行排序后按照前k-2項(xiàng)進(jìn)行劃分，并采用前k-2項(xiàng)屬性值作為塊標(biāo)號(hào)；其次采用下述連接方法，利用式(2)、式(4)形成頻繁k項(xiàng)集，避免無(wú)效項(xiàng)集的產(chǎn)生，占用資源，返回(Mik,l_fik)。對(duì)該步驟進(jìn)行迭代，直至滿足條件k，或出現(xiàn)頻繁項(xiàng)集為空時(shí)返回k-1時(shí)的結(jié)果值。

自連接方式主要為兩種：塊內(nèi)自連接、塊間自連接。

(1)塊內(nèi)自連接：當(dāng)塊內(nèi)項(xiàng)集的個(gè)數(shù)不小于1時(shí)，采用該連接方式執(zhí)行，如圖2所示，以標(biāo)號(hào)為“I2”的塊進(jìn)行解析，(I2,I5)， (I2,I7)連接生成(I2,I5,I7)，采用式(2)、式(3)運(yùn)算其支持度計(jì)數(shù)；滿足條件，則添加到頻繁k項(xiàng)集矩陣中。

(2)塊間自連接：當(dāng)總塊數(shù)不小于1時(shí)，采用該連接方式執(zhí)行，圖2中以(I2,I5)為例(此處k=3)，采用后1個(gè)項(xiàng)作為查找依據(jù)，即“I5”去查找對(duì)應(yīng)的分塊標(biāo)號(hào)，然后連接生成(I2,I5,I7)、 (I2,I5,I8)兩個(gè)項(xiàng)集，在進(jìn)行自連接的同時(shí)，需判斷該項(xiàng)集是否存在于l_fck中，若不存在，則需對(duì)矩陣中的相應(yīng)列進(jìn)行相關(guān)運(yùn)算，運(yùn)算結(jié)果滿足條件則保留至二維矩陣l_fck中。如圖3所示，當(dāng)k=4時(shí)，劃分頻繁3項(xiàng)集后，應(yīng)采用前兩項(xiàng)作為塊表示，后兩項(xiàng)作為連接依據(jù)。

圖2 生成局部頻繁3項(xiàng)集

圖3 局部頻繁4項(xiàng)集的形成過(guò)程

步驟5 根據(jù)相同的“健”(即局部頻繁項(xiàng)集)進(jìn)行“值”(即局部頻繁項(xiàng)集的求和結(jié)果)相加，合并所有分塊的局部頻繁項(xiàng)集，生成全局候選頻繁項(xiàng)集fk，再根據(jù)最小支持度計(jì)數(shù)，進(jìn)行全局剪枝。

2.4 Spark平臺(tái)下的Apriori_MC算法基本思想

Spark框架是專為大規(guī)模數(shù)據(jù)處理所設(shè)計(jì)的通用并行框架，引入彈性分布式數(shù)據(jù)集[10](resilient distributed dataset，RDD)概念，RDD是一個(gè)具有容錯(cuò)性的數(shù)據(jù)集合，該數(shù)據(jù)被分成多個(gè)分片，存儲(chǔ)在集群的各個(gè)節(jié)點(diǎn)的內(nèi)存中，當(dāng)內(nèi)存容量不夠時(shí)，這些數(shù)據(jù)會(huì)自動(dòng)寫(xiě)入磁盤(pán)。RDD具有兩種類(lèi)型的操作模式：transformation(轉(zhuǎn)換)和action(動(dòng)作)，前者的主要目的是從現(xiàn)有的RDD數(shù)據(jù)對(duì)象中重新創(chuàng)建或重新計(jì)算，從而獲得一個(gè)新的RDD數(shù)據(jù)對(duì)象，例如map()、flatMap()、filter()、distinct()、groupByKey()等。這些轉(zhuǎn)換操作具有惰性，即在對(duì)RDD進(jìn)行轉(zhuǎn)換操作時(shí)，該操作并不會(huì)立即執(zhí)行，僅僅記住這些操作；后者則通過(guò)某種特定的方法將多個(gè)RDD對(duì)象進(jìn)行合并，生成一個(gè)最終結(jié)果，如count()、collect()、foreach()、reduce()等函數(shù)。在程序執(zhí)行過(guò)程中，當(dāng)RDD調(diào)用Action函數(shù)時(shí)，才會(huì)執(zhí)行相關(guān)的Transformation函數(shù)進(jìn)行計(jì)算。

Spark系統(tǒng)以MapReduce框架為核心，主要針對(duì)Hadoop存在的問(wèn)題而設(shè)計(jì)的一套框架[11]，具有使用簡(jiǎn)單、自動(dòng)容錯(cuò)、負(fù)載均衡、擴(kuò)展性強(qiáng)、可靠性高等特點(diǎn)[1]，相較于Hadoop框架，它主要有以下優(yōu)勢(shì)：

(1)Spark實(shí)時(shí)性強(qiáng)，擅長(zhǎng)處理流數(shù)據(jù)，而Hadoop則擅長(zhǎng)處理批量數(shù)據(jù)。當(dāng)隨機(jī)訪問(wèn)數(shù)據(jù)時(shí)，Hadoop執(zhí)行效率明顯低于Spark。

(2)Spark最大的優(yōu)勢(shì)在于面向內(nèi)存進(jìn)行計(jì)算[12]。Hadoop平臺(tái)面向磁盤(pán)存儲(chǔ)數(shù)據(jù)，在調(diào)用數(shù)據(jù)時(shí)，Hadoop需要先將數(shù)據(jù)從磁盤(pán)中調(diào)入內(nèi)存進(jìn)行運(yùn)算，而Spark直接在內(nèi)存中進(jìn)行計(jì)算，無(wú)需進(jìn)行磁盤(pán)I/O操作，相比之下，內(nèi)存處理速度明顯高于磁盤(pán)速度。

(3)Spark改進(jìn)了shuffle過(guò)程，提升了Spark的運(yùn)行速度。Shuffle是Map階段和Reduce階段交流的紐帶，在Hadoop平臺(tái)上，shuffle過(guò)程強(qiáng)制要求數(shù)據(jù)按key值進(jìn)行排序后分發(fā)到Reducer上，而Spark平臺(tái)上的shuffle過(guò)程則是用戶在有需求的情況下才會(huì)對(duì)結(jié)果數(shù)據(jù)進(jìn)行排序(即調(diào)用sortBy()或sortByKey())。兩者相比，Spark的設(shè)計(jì)更加合理有效。

基于以上幾點(diǎn)，本文將改進(jìn)后的Apriori_MC算法移植到Spark平臺(tái)，通過(guò)執(zhí)行k個(gè)Map操作以及一個(gè)Reduce操作過(guò)程，實(shí)現(xiàn)算法的并行化處理。在Map階段，Spark將數(shù)據(jù)分成多個(gè)分塊(分塊數(shù)個(gè)數(shù)視集群情況而定)，將各個(gè)分塊分別部署到不同的工作階段中去，按照第2.3節(jié)中描述的Apriori_MC算法的執(zhí)行流程進(jìn)行部署實(shí)現(xiàn)；在Reduce階段，將在Map階段產(chǎn)生的分塊結(jié)果按照鍵值進(jìn)行求和，獲得全局候選k項(xiàng)集；最后將通過(guò)filter()函數(shù)對(duì)全局候選項(xiàng)集進(jìn)行篩選過(guò)濾，從而獲得全局頻繁k項(xiàng)集。整個(gè)算法的流程如圖4所示。

Apriori_MC_SP算法核心偽代碼如下：

圖4 Apriori_MC_SP算法執(zhí)行流程

輸入： 存儲(chǔ)路徑path， 最小支持度min_sup， 所求頻繁項(xiàng)集數(shù)k， 分塊數(shù)n

輸出： 頻繁k項(xiàng)集fk

(1)某事務(wù)數(shù)據(jù)庫(kù)被存儲(chǔ)在path路徑下的文件中， Master工作節(jié)點(diǎn)利用textfile()讀取文件， 讀取后創(chuàng)建一個(gè)新的RDD， 該RDD中的數(shù)據(jù)包含n個(gè)數(shù)據(jù)塊。

rdd←sc.textfile(path, n)

(2)Map階段：

for t←1 to k do:

if t==1 then :

rdd← rdd. mapPartitions( fc1(split, min_sup, k))

if t==2 then :

rdd← rdd.map( fc2(split, min_sup, k))

if t>2then :

rdd←rdd.map( fcn(split, min_sup, k))

(3)Reduce階段：

fk←rdd.flatMap(_).reduceByKey(_+_).filter(_>= min_sup_count)

上述過(guò)程中主要涉及以下3個(gè)函數(shù)：

(1)函數(shù)fc1(split, min_sup, k)：

該函數(shù)目的是構(gòu)造簡(jiǎn)約化布爾矩陣M1， 生成頻繁1項(xiàng)集f1， 返回結(jié)果(M1,f1)， 相關(guān)實(shí)現(xiàn)如下：

begin

L1←sorted( unique ( flatten ( split) ) )

#擴(kuò)展數(shù)據(jù)庫(kù)為1維數(shù)組， 同時(shí)進(jìn)行去重、 排序

w ← len(split) # w為分片長(zhǎng)度

h ← len(L1) # h為L(zhǎng)1長(zhǎng)度

sup_count←min_sup * w

MatrixM←zero(size=(w, h) ); #構(gòu)建零矩陣

for m←0 to h do :

for m←0 to w do :

if L1[m] in split[n] then :M[m, n] ←1

for m←0 to h do :

sums←sum(M[:,m]) #對(duì)矩陣每列進(jìn)行求和

if sums >=sup_count then: f1.add(L1[m])

M1← Mat_process (M,f1, k)

# 調(diào)用Mat_process為篩選行/列的函數(shù)

return (M1,f1)

end

(2)函數(shù)fc2(split, min_sup, k)：

該函數(shù)的目的在于生成頻繁2項(xiàng)集， 返回結(jié)果(M2,f2)， 相關(guān)描述如下：

begin

f2,f1,M← [], split [1], split [0]

for m←0 to len(f1)-1 do :

for n←m+1 to len(f1) do:

sums←sum(M[:,m]&M[:,n] )

l←[ [f1[m] ,f1[n]] , sums] #二維數(shù)組

if sums>=sup_count and l not inf2then:

f2.add( l)

M←Mat_process(M,f2, k)

return (M,f2)

end

(3)函數(shù)fcn(split, min_sup, k)：

該函數(shù)主要針對(duì)當(dāng)k>2時(shí)， 采用塊內(nèi)自連接和塊間自連接兩種方式， 返回結(jié)果(Mn,fn)， 相關(guān)描述如下：

begin

f,M, result ,fn←split [1][:,0], split [0], 1, []

gid=unique(f[:,0:k-2]) #對(duì)二維矩陣進(jìn)行分塊標(biāo)記

for each id in gid do :

group← select(f2[:,0:k-2]=id)

for each i←0 to len(gid)-1 do:

#塊內(nèi)連接

for each p←i+1 to len(group) do:

l←sorted(group[i,:] ∪group[p,:])

for u in A:result*=M[:,u]

if sums(result)>sup_count then :

fn.add( [l, sums(result)])

#塊間連接

dev ← group[i][-(k-2):]

Group←select(f2[:,0:k-2]= dev)

for ecah item in Group do:

l← sorted( group[i,:]∪item )

for u in l: result*=M[u]

sums←sum(result)

if(sums>= sup_count) and [l,sums] not infn:

fn.add([l, sums(result) ])

M← Mat_process (M,fn,k)

return (M,fn)

end

2.5 時(shí)間復(fù)雜度

假設(shè)在Spark平臺(tái)上單個(gè)分塊的事務(wù)數(shù)為D,其中事物項(xiàng)集的數(shù)量為M，共N個(gè)這樣的分片。

在單個(gè)分片中，采用傳統(tǒng)的Apriori算法，掃描一次數(shù)據(jù)庫(kù)以及獲得頻繁1項(xiàng)集的耗時(shí)O(MD)，在頻繁k-1項(xiàng)集生成候選k項(xiàng)集的“自連接”過(guò)程中，所需耗時(shí)O(Lk-1*(Lk-1-1)),“剪枝”生成頻繁k項(xiàng)集所需耗時(shí)O(Ck)。遍歷整個(gè)數(shù)據(jù)庫(kù)計(jì)算候選頻繁項(xiàng)集Ck所需耗時(shí)O(Ck*D)，傳統(tǒng)的Apriori算法平均情況下，所需的時(shí)間復(fù)雜度為

(6)

對(duì)Apriori_MC算法來(lái)說(shuō)，當(dāng)k==1時(shí)，其轉(zhuǎn)換矩陣以及生成頻繁1項(xiàng)集所耗時(shí)O(MD)；當(dāng)k==2時(shí)，“自連接”步驟直接生成頻繁k項(xiàng)集所耗時(shí)O(Lk-1*(Lk-1-1))；當(dāng)k>=3時(shí)，對(duì)頻繁二項(xiàng)集進(jìn)行分組操作，在最壞的情況下，其時(shí)間復(fù)雜度為O(Lk-1*(Lk-1-1))，則該算法在最壞的情況下所需的時(shí)間復(fù)雜度為

(7)

對(duì)比式(6)與式(7)，明顯傳統(tǒng)Apriori算法的時(shí)間復(fù)雜度高于Apriori_MC算法的時(shí)間復(fù)雜度。其原因是Apriori_MC算法掃描數(shù)據(jù)庫(kù)操作僅進(jìn)行一次，忽略了局部“剪枝”過(guò)程，減少中間結(jié)果的產(chǎn)生，釋放部分內(nèi)存，縮短了算法的時(shí)間復(fù)雜度。

3 實(shí)驗(yàn)分析

3.1 實(shí)驗(yàn)數(shù)據(jù)

本實(shí)驗(yàn)部分將采用兩種數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)測(cè)試，數(shù)據(jù)集特征見(jiàn)表3。

(1)數(shù)據(jù)來(lái)源于頻繁項(xiàng)集挖掘數(shù)據(jù)集知識(shí)庫(kù)[13]的數(shù)據(jù)集：Connect。

(2)數(shù)據(jù)有IBM數(shù)據(jù)生成器隨機(jī)生成數(shù)據(jù)。

表3 數(shù)據(jù)集特征

3.2 實(shí)驗(yàn)環(huán)境

本文采用的實(shí)驗(yàn)環(huán)境：6臺(tái)CPU Inter Core4、4G內(nèi)存、1T、磁盤(pán)ubuntu14.04的操作系統(tǒng)的臺(tái)式計(jì)算機(jī)，每臺(tái)計(jì)算機(jī)通過(guò)交換機(jī)構(gòu)建小型局域網(wǎng)，并利用操作系統(tǒng)提供的SSH服務(wù)進(jìn)行免密通信。在搭建Spark Standalone集群的過(guò)程中，需要JDK1.8、Scala2.10、Hadoop2.6以及Spark1.6等軟件包的支持，本文實(shí)驗(yàn)主要采用Python3.5進(jìn)行實(shí)現(xiàn)，其依賴Pyspark、Numpy等庫(kù)文件。

3.3 實(shí)驗(yàn)結(jié)果分析

本文實(shí)驗(yàn)部分將采用3種不同的Apriori方案進(jìn)行驗(yàn)證：傳統(tǒng)的Apriori算法、來(lái)自文獻(xiàn)[14]的優(yōu)化方案、以及前文設(shè)計(jì)的Apriori_MC方案，將這3種方案移植到Spark平臺(tái)部署實(shí)現(xiàn)，分別命名為：Apriori_SP、MApriori_SP、以及Apriori_MC_SP算法。

實(shí)驗(yàn)1：支持度閾值的設(shè)定對(duì)算法的影響

支持度閾值的設(shè)置對(duì)關(guān)聯(lián)規(guī)則算法的執(zhí)行速度和頻繁項(xiàng)集的數(shù)量會(huì)帶來(lái)一定的影響。若支持度閾值設(shè)定過(guò)高，產(chǎn)生頻繁項(xiàng)集數(shù)量過(guò)少，則無(wú)法更好展現(xiàn)算法的執(zhí)行效果；若支持度閾值設(shè)置的過(guò)低，生成的頻繁項(xiàng)集過(guò)多，容易造成集群的中間節(jié)點(diǎn)運(yùn)行失敗后再次計(jì)算，增加了集群的工作量。本實(shí)驗(yàn)主要目的在于驗(yàn)證支持度發(fā)生變化時(shí)不同方案的執(zhí)行效率驗(yàn)證以及輸出結(jié)果。該實(shí)驗(yàn)采用Connect數(shù)據(jù)集進(jìn)行驗(yàn)證，輸出結(jié)果要求返回頻繁3項(xiàng)集，3種方案的執(zhí)行效率見(jiàn)表4，頻繁3項(xiàng)集的數(shù)據(jù)見(jiàn)表5。

表4 支持度變化時(shí)3種方案的性能對(duì)比

表5 支持度變化時(shí)3種方案的輸出結(jié)果對(duì)比

在表4中可以得出，在數(shù)據(jù)集一直地情況下，隨著支持度的減小，3種方案的執(zhí)行時(shí)間隨之增加。在表4中，傳統(tǒng)Apriori算法的執(zhí)行時(shí)間最長(zhǎng)，運(yùn)行效率最低。將MApriori_SP與Apriori_MC_SP方案進(jìn)行對(duì)比，當(dāng)支持度sup>=0.4時(shí)，兩種方案的執(zhí)行時(shí)間相差不大；當(dāng)sup<0.4時(shí)，Apriori_MC_SP算法的運(yùn)行效率明顯優(yōu)于MApriori_SP方案。

從表5中可以得出，隨著支持度的降低，頻繁項(xiàng)集的數(shù)量也相應(yīng)增加；同時(shí)，本文提出的Apriori_MC_SP方案與傳統(tǒng)的Apriori算法的頻繁項(xiàng)集在數(shù)量上保持一致。

因此，支持度的選擇是影響關(guān)聯(lián)規(guī)則算法執(zhí)行效率的一個(gè)重要因素。

實(shí)驗(yàn)2：不同數(shù)據(jù)集下算法的執(zhí)行效率對(duì)比實(shí)驗(yàn)

本實(shí)驗(yàn)將采用100萬(wàn)條的隨機(jī)數(shù)據(jù)集中分別提取20萬(wàn)、40萬(wàn)、60萬(wàn)、80萬(wàn)以及100萬(wàn)條數(shù)據(jù)集進(jìn)行測(cè)試，由于該數(shù)據(jù)集的事務(wù)數(shù)量過(guò)大，為避免結(jié)果產(chǎn)生的頻繁項(xiàng)集過(guò)少的情況，將最小支持度閾值設(shè)置為0.1，挖掘頻繁3項(xiàng)集，在數(shù)據(jù)集量不同的情況下，3種方案的執(zhí)行效果如圖5所示。

圖5 不同數(shù)據(jù)規(guī)模下3種方案的性能對(duì)比

在圖5中可以得出，隨著事務(wù)數(shù)據(jù)集的規(guī)模逐步擴(kuò)大，算法的執(zhí)行時(shí)間也隨之增長(zhǎng)，同時(shí)也反映出傳統(tǒng)Apriori算法比其它兩種方案的執(zhí)行時(shí)間長(zhǎng)，并不滿足當(dāng)前大數(shù)據(jù)時(shí)代對(duì)數(shù)據(jù)分析的要求。當(dāng)數(shù)據(jù)集的數(shù)據(jù)量小于40萬(wàn)時(shí)，Apriori_MC_SP與MApriori_SP方案的執(zhí)行時(shí)間相差較小，但當(dāng)數(shù)據(jù)量越來(lái)越小時(shí)，Apriori_MC_SP方案的執(zhí)行效率則快于MApriori_SP算法。

實(shí)驗(yàn)3：Spark集群的工作節(jié)點(diǎn)數(shù)對(duì)算法的影響

該實(shí)驗(yàn)的目的是驗(yàn)證集群的工作節(jié)點(diǎn)是否影響算法的運(yùn)行效率。該實(shí)驗(yàn)選取隨機(jī)生成的60萬(wàn)條數(shù)據(jù)作為驗(yàn)證對(duì)象，最小支持度閾值設(shè)置為0.1，分別驗(yàn)證不同工作節(jié)點(diǎn)下Apriori_MP_SP方案的執(zhí)行狀況，實(shí)驗(yàn)結(jié)果如圖6所示。

圖6 不同工作節(jié)點(diǎn)下的執(zhí)行效率

從圖6中可以得出，在數(shù)據(jù)集不變的情況下，工作節(jié)點(diǎn)增加，集群可使用的內(nèi)存資源加大，使得集群處理大數(shù)據(jù)量的能力加強(qiáng)，從而加快了算法的執(zhí)行時(shí)間。圖中，當(dāng)工作節(jié)點(diǎn)數(shù)大于等于3時(shí)，執(zhí)行效率下降的速度明顯減緩。

綜上所述，支持度的設(shè)定、數(shù)據(jù)規(guī)模、Spark集群規(guī)模均會(huì)影響算法的執(zhí)行效率。本文提出Apriori_MC_SP方案在保證輸出結(jié)果與傳統(tǒng)Apriori算法一致地情況下，在很大程度上提升了關(guān)聯(lián)規(guī)則算法的執(zhí)行效率，且該算法更適用于大數(shù)據(jù)量的關(guān)聯(lián)規(guī)則提取。

4 結(jié)束語(yǔ)

本文提出的Apriori_MC算法，運(yùn)用分治思想，基于Spark集群框架，實(shí)現(xiàn)了關(guān)聯(lián)規(guī)則算法的并行化計(jì)算，有效解決了數(shù)據(jù)庫(kù)掃描次數(shù)多、系統(tǒng)I/O負(fù)載量大、無(wú)效的中間局部頻繁項(xiàng)集多等問(wèn)題，提高了關(guān)聯(lián)規(guī)則算法的運(yùn)行效率。當(dāng)然，在算法的實(shí)現(xiàn)過(guò)程中仍然存在一些缺陷，在實(shí)驗(yàn)過(guò)程中，隨著數(shù)據(jù)量的增長(zhǎng)，算法產(chǎn)生的中間結(jié)果越多，在采用Spark集群進(jìn)行測(cè)試的過(guò)程中，未充分考慮實(shí)驗(yàn)過(guò)程中數(shù)據(jù)傾斜所帶來(lái)的問(wèn)題，造成各工作節(jié)點(diǎn)運(yùn)行時(shí)間不穩(wěn)定的現(xiàn)象。后期將著重對(duì)這些問(wèn)題進(jìn)行深層次的研究，以期獲得更理想的效果。