劉麗娜 姜利群

(廣州工商學(xué)院計(jì)算機(jī)科學(xué)與工程系 廣東 廣州 510850)

0 引 言

數(shù)據(jù)挖掘的概念已提出多年，其宗旨在于從海量數(shù)據(jù)中分析出對(duì)現(xiàn)階段或未來(lái)有意義的數(shù)據(jù)信息，它涉及的經(jīng)典算法分類(lèi)有頻繁項(xiàng)集生成[1]、頻繁模式增長(zhǎng)[2]和垂直格式等[3-4]。其中頻繁項(xiàng)集生成的關(guān)聯(lián)規(guī)則(Apriori)算法尤為經(jīng)典，用于挖掘數(shù)據(jù)元素之間的關(guān)系，如通過(guò)關(guān)聯(lián)規(guī)則可以得出是吃米飯的家庭離婚率高還是吃面食的家庭離婚率高[5]。關(guān)聯(lián)規(guī)則是在海量元素中找出元素之間的有趣關(guān)系。頻繁模式增長(zhǎng)的代表算法是FP-growth[6]，其基本原理是將頻繁項(xiàng)集規(guī)約至一棵模式樹(shù)中并根據(jù)條件按需挖掘。垂直格式主要針對(duì)數(shù)據(jù)維數(shù)及屬性較低的數(shù)據(jù)模型，以數(shù)據(jù)維數(shù)即列項(xiàng)作為行標(biāo)，將事務(wù)項(xiàng)作為列標(biāo)，從而達(dá)到壓縮數(shù)據(jù)庫(kù)的目的[7]。

面對(duì)數(shù)據(jù)大爆炸的信息時(shí)代，傳統(tǒng)的數(shù)據(jù)處理速率已無(wú)法應(yīng)對(duì)龐大的數(shù)據(jù)量，同時(shí)無(wú)法滿(mǎn)足人們的需求，而Spark技術(shù)的出現(xiàn)彌補(bǔ)了該缺陷。Spark是在Hadoop的基礎(chǔ)上進(jìn)一步改進(jìn)以適用于大數(shù)據(jù)分析，當(dāng)數(shù)據(jù)集全部載入內(nèi)存且條件滿(mǎn)足的情況下其速度可比Hadoop快100倍之多[8]。但軟件的更新有限，數(shù)據(jù)的增長(zhǎng)無(wú)限，劉莉萍等[4]指出，在Spark的并行處理之路上內(nèi)存及數(shù)據(jù)是未來(lái)兩大研究突破點(diǎn)。

基于上述問(wèn)題，本文在Spark的列式存儲(chǔ)技術(shù)的基礎(chǔ)上進(jìn)行不斷壓縮剪枝，接近斷層式地減少數(shù)據(jù)量加快并行處理速度，通過(guò)實(shí)驗(yàn)驗(yàn)證該算法適用于分析各種結(jié)構(gòu)化數(shù)據(jù)集。

1 相關(guān)研究

Apriori最初由Agrawal等[9]提出，后續(xù)學(xué)者為不斷提高運(yùn)行速度對(duì)其進(jìn)行了無(wú)數(shù)次改進(jìn)。Han等[10]提出較具代表性的基于FP-tree的FP-growth算法，該算法從減少數(shù)據(jù)庫(kù)遍歷次數(shù)降低I/O消耗的角度考慮，由各個(gè)元素組成節(jié)點(diǎn)，只需遍歷一次數(shù)據(jù)庫(kù)，無(wú)候選頻繁項(xiàng)集產(chǎn)生，但由于需在內(nèi)存中創(chuàng)建FP-tree拓?fù)浣Y(jié)構(gòu)消耗大量?jī)?nèi)存且只適用于分析單維類(lèi)型的大數(shù)據(jù)。文獻(xiàn)[11]最初提出的Eclat算法是從減少數(shù)據(jù)量的角度分析，該算法通過(guò)顛覆數(shù)據(jù)存放常態(tài)減少重復(fù)元素，以每行中事務(wù)項(xiàng)的列元素轉(zhuǎn)為行標(biāo)，而該列元素所出現(xiàn)的事務(wù)項(xiàng)轉(zhuǎn)為列標(biāo)從而減少元素的重復(fù)次數(shù)以便于支持度計(jì)數(shù)，但該算法的運(yùn)行效率與數(shù)據(jù)的特征息息相關(guān)，其元素個(gè)數(shù)越少事務(wù)項(xiàng)越多效率越高，在維數(shù)越多屬性值越多的多維數(shù)據(jù)中效率趨近于原始Apriori算法的效率。Yang等[12]提出通過(guò)抽取海量數(shù)據(jù)中的部分樣本減少數(shù)據(jù)執(zhí)行量的抽樣加權(quán)向量矩陣法來(lái)對(duì)Apriori算法進(jìn)行優(yōu)化，該改進(jìn)算法雖通過(guò)抽樣減少了數(shù)據(jù)量，但可能丟失一些特殊點(diǎn)規(guī)則。

近幾年并行處理興起，Hadoop的MapReduce框架僅通過(guò)Map函數(shù)和Reduce函數(shù)即可分布執(zhí)行Apriori，數(shù)據(jù)量越大節(jié)點(diǎn)加入越多執(zhí)行效率越高，Hadoop的MapReduce框架處理的簡(jiǎn)單性既是優(yōu)點(diǎn)又是缺點(diǎn)，只需執(zhí)行Map算子和Reduce算子卻不能滿(mǎn)足現(xiàn)如今數(shù)據(jù)處理的復(fù)雜性以及人機(jī)交互的高要求。因此，Spark應(yīng)運(yùn)而生，內(nèi)存模型、快速的迭代處理優(yōu)勢(shì)、更支持交互查詢(xún)等諸多優(yōu)點(diǎn)使其迅速崛起。黃劍等[13]在2017年提出基于Hadoop平臺(tái)的改進(jìn)算法，該改進(jìn)算法減少了候選集的產(chǎn)生，以布爾矩陣的模式壓縮數(shù)據(jù)集進(jìn)行并行處理，從而多方面加快數(shù)據(jù)的處理速度，但該算法并未表明可以處理多維多屬性的數(shù)據(jù)，且有一定量的候選頻繁項(xiàng)集產(chǎn)生，存在一定的約束性。閆夢(mèng)潔等[14]在2017年提出了基于Spark的Apriori優(yōu)化算法IABS，實(shí)驗(yàn)表明在同等條件下Spark執(zhí)行Apriori比Hadoop的效率更高，且其采用YAFIM將候選頻繁項(xiàng)集存進(jìn)哈希樹(shù)加速候選頻繁項(xiàng)集的查詢(xún)，讓算法的效率得到進(jìn)一步的提高。但I(xiàn)ABS算法在第一階段產(chǎn)生的候選頻繁項(xiàng)集及查詢(xún)自連接操作的復(fù)雜性一定程度上約束了算法的效率，同時(shí)該算法在處理數(shù)據(jù)的維度屬性的一般性及特殊性上并未做相應(yīng)說(shuō)明。由于篇幅有限，本文不再贅述，詳細(xì)研究見(jiàn)參考文獻(xiàn)[15-19]。

隨著數(shù)據(jù)量劇增、I/O消耗及有限內(nèi)存的約束，算法的運(yùn)行代價(jià)與日俱增，減少其數(shù)據(jù)量與降低內(nèi)存耗費(fèi)是未來(lái)丞待解決的兩大難題。本文依托Spark計(jì)算框架，從處理多維多屬性數(shù)據(jù)集的角度，消除候選頻繁項(xiàng)集，最大限度減低算法自連接時(shí)間提升Apriori算法的執(zhí)行效率，提出IApriori算法(improved Apriori algorithm)。

2 構(gòu)建關(guān)聯(lián)規(guī)則算法優(yōu)化模型

2.1 算法介紹

Apriori算法分為剪枝和連枝兩個(gè)步驟。首先從候選集Ci中統(tǒng)計(jì)支持度，根據(jù)最小支持度SupMin剪去不合規(guī)格的元素e或連枝后的事務(wù)集t得到頻繁項(xiàng)集Li，再?gòu)念l繁項(xiàng)集Li∞Li連枝得到新的候選集Ci+1，如此循環(huán)迭代直到候選集為?，由此得到所有的規(guī)則。

設(shè)數(shù)據(jù)庫(kù)D={t1，t2，…，tm|m>0且m∈N}，每項(xiàng)事務(wù)t={e1，e2，…，en|n>0且n∈N}，e為事務(wù)項(xiàng)里包含的元素。

2.2 構(gòu)建Spark計(jì)算框架

Hadoop雖提供同樣的分布式處理模式，但其只支持Map和Reduce兩個(gè)算子，限制了復(fù)雜場(chǎng)景的數(shù)據(jù)分析能力。Spark計(jì)算框架作為Hadoop計(jì)算框架的繼任[8]，提供了更為豐富的API，且其能將中間結(jié)果寫(xiě)入內(nèi)存的特性減少了數(shù)據(jù)的I/O，加速數(shù)據(jù)的分布處理。本文中Spark計(jì)算框架的搭建相對(duì)復(fù)雜，第一階段以R在RStudio平臺(tái)上分別在master節(jié)點(diǎn)和slave節(jié)點(diǎn)中安裝JDK，配置Hadoop及其環(huán)境變量，然后配置YARN、HDFS、HBase、Hive等，及其他組件和依賴(lài)包，配置完成后啟動(dòng)Hadoop集群；第二階段配置Spark、配置環(huán)境變量及相關(guān)依賴(lài)包；第三階段采用Java運(yùn)行改進(jìn)的關(guān)聯(lián)規(guī)則代碼，Spark讀取HBase形成RDD，存入Hive。

本文所依托的Spark計(jì)算框架采用了主從節(jié)點(diǎn)結(jié)構(gòu)的計(jì)算模型，如圖1所示。主節(jié)點(diǎn)master對(duì)從節(jié)點(diǎn)slave進(jìn)行任務(wù)調(diào)度分布，slave節(jié)點(diǎn)在執(zhí)行完job后將結(jié)果再返回master進(jìn)行匯總，模型同時(shí)采用R結(jié)合Java對(duì)環(huán)境進(jìn)行配置和算法執(zhí)行。

圖1 Spark計(jì)算模型

2.3 字典表壓縮存儲(chǔ)多維多屬性并行方案

以往的Apriori優(yōu)化基本以清洗轉(zhuǎn)化后的單維度布爾值為研究數(shù)據(jù)，而一般情況下，海量數(shù)據(jù)分為結(jié)構(gòu)化數(shù)據(jù)與非結(jié)構(gòu)化數(shù)據(jù)，且結(jié)構(gòu)化數(shù)據(jù)不僅多維更兼多屬性。在數(shù)據(jù)預(yù)處理轉(zhuǎn)換為布爾矩陣時(shí)不僅前期需耗費(fèi)大量的時(shí)間，且清洗之后的每個(gè)屬性值會(huì)根據(jù)占比消耗大部分的空間用于存儲(chǔ)“0”值。

假設(shè)有100條事務(wù)，每條事務(wù)有5個(gè)維度，每個(gè)維度有3個(gè)屬性值，原本的存儲(chǔ)空間為500(100×5)，而轉(zhuǎn)換為布爾矩陣之后的空間為1 500(100×(5×3))，則存儲(chǔ)空間的耗費(fèi)量為原先的3倍，屬性值的個(gè)數(shù)x與空間耗費(fèi)率為原本存儲(chǔ)空間η的x倍，即xη。

2.3.1基于HBase的行轉(zhuǎn)列式存儲(chǔ)

1) 常規(guī)行存儲(chǔ)模式。常規(guī)行存儲(chǔ)模式如圖2所示。行存儲(chǔ)的遍歷思想如下：從事務(wù)項(xiàng)的第一行自左到右遍歷至第一行結(jié)束，再?gòu)牡诙幸灾暗哪Ｊ奖闅v，以此類(lèi)推直至遍歷完所有數(shù)據(jù)。按照上述遍歷思想可得到如下一般形式：

圖2 行存儲(chǔ)模式

e11,e12,…，e1i;e21,e22,…，e2j;…;em1,em2,…，emk

(1)

式中：m表示有m行；i、j、k表示列，i、j、k的取值可等或不等。

結(jié)合圖2，其步驟可以描述如下：

第一步訪(fǎng)問(wèn)第一行，可獲取信息(e11,e12,…，e1i)。

第二步訪(fǎng)問(wèn)第二行，可獲取信息(e21,e22,…，e2j)。

以此類(lèi)推，第m步訪(fǎng)問(wèn)第m行，可獲取信息(em1,em2,…，emk)。

2) 行轉(zhuǎn)列式存儲(chǔ)模式。Spark是在Hadoop計(jì)算框架的基礎(chǔ)上進(jìn)行了擴(kuò)展，行轉(zhuǎn)列式存儲(chǔ)模式如圖3所示?；贖Base的行轉(zhuǎn)列式存儲(chǔ)的遍歷思想如下：從事務(wù)項(xiàng)的第一列自上而下遍歷至第一列結(jié)束，再?gòu)牡诙幸灾暗哪Ｊ奖闅v，以此類(lèi)推直至遍歷完所有數(shù)據(jù)。按照上述遍歷思想可得到如下一般形式：

圖3 HBase列存儲(chǔ)模式

e11,e21,…，em1;e12,e22,…,em2;…;e1i,e2j,…,emk

(2)

式中：m表示有m行，n表示最長(zhǎng)的列數(shù)；i、j、k表示列，i、j、k的取值可等或不等。

第一步訪(fǎng)問(wèn)第一列，可獲取信息(e11,e21,…，em1)。

第二步訪(fǎng)問(wèn)第二列，可獲取信息(e12,e22,…，em2)。

以此類(lèi)推，第m步訪(fǎng)問(wèn)第n列，可獲取信息(e1i,e2j,…，emk)。

2.3.2字典表數(shù)據(jù)壓縮

首先，統(tǒng)計(jì)每一行的支持度σ，當(dāng)支持度σ≤SupMin時(shí)，進(jìn)行第一輪的剪枝，得到頻繁一項(xiàng)集。為便于理解，數(shù)據(jù)表中的元素e代入具體實(shí)例進(jìn)行演示(限于篇幅，假設(shè)實(shí)例數(shù)據(jù)已進(jìn)行過(guò)第一輪剪枝)。將表中對(duì)應(yīng)的屬性值按ID及列的方式存儲(chǔ)為字典表，將屬性值轉(zhuǎn)換為占內(nèi)存較少的整型數(shù)值(或字符)，如圖4所示。

圖4 字典表數(shù)據(jù)壓縮

在該步驟中，根據(jù)元素的n個(gè)維度構(gòu)建n個(gè)字典表，字典表由ID號(hào)及維度屬性值構(gòu)成，不同的屬性值對(duì)應(yīng)該表中唯一的ID號(hào)。如該實(shí)例中薪酬級(jí)別維度字典表中“H2”屬性值對(duì)應(yīng)的字典表ID號(hào)為“1”，平均成績(jī)維度字典表中“良”屬性值對(duì)應(yīng)的字典表ID為“2”。在構(gòu)建完字典表之后，根據(jù)維度字典表屬性值對(duì)應(yīng)的ID號(hào)將數(shù)據(jù)集替換壓縮為整型數(shù)值表。該方法能在有效壓縮數(shù)據(jù)集的同時(shí)，便于為下一步的“與”操作鋪墊。

2.3.3基于字典表壓縮的連枝剪枝設(shè)計(jì)

將2.3.2節(jié)的頻繁一項(xiàng)集進(jìn)行字典表對(duì)應(yīng)壓縮后，執(zhí)行行轉(zhuǎn)列式存儲(chǔ)，將原存儲(chǔ)的行事務(wù)項(xiàng)t轉(zhuǎn)為列，而元素維度轉(zhuǎn)為行，如圖5所示。同時(shí)統(tǒng)計(jì)每個(gè)維度字典表中各個(gè)屬性值的計(jì)數(shù)，為計(jì)算置信度ξ做數(shù)據(jù)準(zhǔn)備。列式存儲(chǔ)在操作時(shí)只有涉及到計(jì)算的列會(huì)被讀取，減少I(mǎi)/O消耗加速算法執(zhí)行數(shù)據(jù)分析。

（1）色彩管理系統(tǒng)（CMS）與數(shù)碼打樣色彩管理是CTP 系統(tǒng)中較為關(guān)鍵的技術(shù)，也是用于地圖印刷質(zhì)量控制的核心。它將創(chuàng)建了顏色的色彩空間與要輸出該色的色彩空間進(jìn)行比較，使要處理的地圖文件在流程中的各個(gè)輸出端（如屏幕顯示、打樣、印刷）上顯示的顏色盡可能保持一致。因此就要在數(shù)據(jù)輸入、處理、輸出時(shí)進(jìn)行RGB 模式到CMYK 模式的轉(zhuǎn)換，由可校色的高質(zhì)量顯示器近似模擬印刷效果，打樣輸出采用國(guó)際通用的ICC 標(biāo)準(zhǔn)，配備專(zhuān)業(yè)數(shù)碼打樣軟件輸出數(shù)碼樣張，經(jīng)過(guò)色彩管理后的數(shù)碼打樣，能夠完全模擬印刷機(jī)的色彩曲線(xiàn)，輸出與印刷品感官色彩完全一樣的數(shù)碼樣張，提供客戶(hù)做印前檢查，印前可即時(shí)進(jìn)行修改，且色彩穩(wěn)定。

圖5 基于字典表壓縮的連枝設(shè)計(jì)

該步驟從第一列開(kāi)始，逐列進(jìn)行讀取，對(duì)每列的每個(gè)字典表ID值從“1”到“n”進(jìn)行查詢(xún)，并逐一轉(zhuǎn)換為布爾值。如第一次查詢(xún)到第一列存在字典表ID 數(shù)值為“1”，則將其替換為布爾值“1”，其他值替換為布爾值“0”，第二列執(zhí)行同樣操作，之后第一列與第二列執(zhí)行“與”操作，將結(jié)果計(jì)算得出頻繁項(xiàng)集、支持度σ及置信度ξ，再替換回原來(lái)的值，列與列依次讀取并執(zhí)行“與”操作直至存在值為“1”的最后一列；第二次查詢(xún)第一列字典表ID數(shù)值為“2”，則將“2”替換為布爾值“1”，其他值替換為布爾值“0”，第二列執(zhí)行同樣操作，之后第一列與第二列執(zhí)行“與”操作，將結(jié)果計(jì)算得出頻繁項(xiàng)集、支持度σ及置信度ξ，再替換回原來(lái)的值，涉及操作的列與列依次讀取并執(zhí)行 “與”操作直至存在值為“2”的最后一列；依次操作，直到替換完字典表最大ID值n，完成所有維度屬性值的“與”操作。該步驟的遍歷操作順序如圖5所示，詳細(xì)的實(shí)例替換操作如圖6所示。

圖6 字典表壓縮的剪枝設(shè)計(jì)

本文取實(shí)例中第二次查詢(xún)替換維度屬性值“2”為例，如圖6所示，將學(xué)號(hào)“01”列中找到所有字典表ID數(shù)值為“2”的單元，并將其轉(zhuǎn)換為布爾值“1”，其他維度屬性值替換為布爾值“0”。根據(jù)該思想，本例中學(xué)號(hào)“01”列的原值為(2,1,2)，替換之后值為(1,0,1)，而實(shí)例中學(xué)號(hào)“02”列原值為(3,3,3)(見(jiàn)圖5中的實(shí)例列表)，對(duì)比該列無(wú)可替換值，無(wú)“與”操作價(jià)值，因而可跳過(guò)該列執(zhí)行下一列，學(xué)號(hào)“03”列的原值為(2,2,2)，替換之后值為(1,1,1)，可與“01”列執(zhí)行“與”操作，即(1,0,1)&(1,1,1)=(1,0,1)，計(jì)數(shù)器加1；計(jì)算支持度σ=1/5=0.2(第一次“與”操作計(jì)數(shù)，此時(shí)計(jì)數(shù)器為1，總列數(shù)為5)；假設(shè)最小支持度、置信度為SupMin=ConfMin=0.2，符合最小支持度， 則頻繁項(xiàng)集Lφ頻繁項(xiàng)數(shù)φ等于“與”操作結(jié)果中所有布爾值為“1”的和，即φ=1+0+1=2；“與”結(jié)果布爾值為“1”對(duì)應(yīng)元素下標(biāo)為關(guān)聯(lián)規(guī)則元素，即頻繁二項(xiàng)集的L2={[e1]2，[e3]2}，其中：規(guī)則([e1]2→[e3]2)置信度ξ=1/3=0.33(第一次“與”操作計(jì)數(shù)，此時(shí)計(jì)數(shù)器為1，在每個(gè)維度字典表中各個(gè)屬性值的計(jì)數(shù)中e1列中屬性值字典表ID值為“2”的計(jì)數(shù)值為3)，置信度ξ=0.33>ConfMin，符合要求；頻繁二項(xiàng)集L2={[e1]2，[e3]2}對(duì)應(yīng)第一行及第三行的維度名，{[平均成績(jī)]2，[薪酬級(jí)別]2 },方括號(hào)后的“2”為替換維度屬性值“2”，對(duì)應(yīng)字典表ID值為“2”的屬性值從而得到頻繁項(xiàng)集L2={平均成績(jī).良，薪酬級(jí)別.H2}；將“與”操作完的列“01”及“02”還原為原來(lái)值。

取學(xué)號(hào)“04”列的原值為(2,1,2)，替換之后值為(1,0,1)，和“01&03”的“與”結(jié)果值(1,0,1)做再次“與”操作，即(1,0,1)&(1,0,1)=(1,0,1)，計(jì)數(shù)器加1；計(jì)算支持度σ=2/5=0.4(第二次“與”操作計(jì)數(shù)，此時(shí)計(jì)數(shù)器為2，總列數(shù)為5)，支持度σ=0.4>SupMin，符合要求，則頻繁項(xiàng)集Lφ頻繁項(xiàng)數(shù)φ等于“與”操作結(jié)果中所有布爾值為“1”的和，即φ=1+0+1=2；“與”結(jié)果布爾值為“1”對(duì)應(yīng)元素下標(biāo)為關(guān)聯(lián)規(guī)則元素，即頻繁二項(xiàng)集的L2={[e1]2，[e3]2}，其中：規(guī)則([e1]2→[e3]2)置信度ξ=2/3=0.66(第二次“與”操作計(jì)數(shù)，此時(shí)計(jì)數(shù)器為2，e1列中屬性值字典表ID值為“2”的計(jì)數(shù)值為3)，置信度ξ=0.66>ConfMin，符合要求；頻繁二項(xiàng)集L2={[e1]2，[e3]2}對(duì)應(yīng)第一行及第三行的屬性名，{[平均成績(jī)]2，[薪酬級(jí)別]2 },其中方括號(hào)后的“2”為替換維度屬性值“2”，對(duì)應(yīng)字典表ID值為“2”的屬性值從而得到頻繁二項(xiàng)集L2={平均成績(jī).良，薪酬級(jí)別.H2}；將“與”操作完的“04”列還原為原來(lái)值。

基于以上思想，假設(shè)σ≥SupMin且ξ≥ConfMin，則存儲(chǔ)計(jì)算結(jié)果的“行”下標(biāo)，且“行”下標(biāo)所記的元素及e及循環(huán)次數(shù)i可以得到頻繁φ項(xiàng)集Lφ，而無(wú)須產(chǎn)生候選集。因此，Lφ={[ek]i,[ek+1]i,…,[en]i}，其中i為外層循環(huán)計(jì)數(shù)器，即替換值，根據(jù)元素下標(biāo)及字典表得到相應(yīng)的頻繁項(xiàng)集。

定義3en為存放“與”操作結(jié)果的數(shù)組，頻繁φ項(xiàng)集Lφ，其中φ的值等于“與”操作后“1”的和，從而得到一般形式下頻繁項(xiàng)集Lφ的項(xiàng)集數(shù)φ的計(jì)算式為：

(3)

定義4Counter為“與”次數(shù)計(jì)時(shí)器，從而得到一般形式下頻繁φ項(xiàng)集Lφ的支持度σ和規(guī)則(ei→ej)的置信度ξ計(jì)算公式分別如下：

(4)

(5)

式中：Counter(ei→ej)為規(guī)則(ei→ej)的“與”計(jì)數(shù)；Count(ei)為元素屬性值ei在數(shù)據(jù)庫(kù)中的統(tǒng)計(jì)數(shù)。

2.3.4改進(jìn)算法IApriori實(shí)現(xiàn)

Spark的優(yōu)勢(shì)是能在內(nèi)存保存job的中間結(jié)果，降低I/O提高執(zhí)行效率。該算法利用HBase列式存儲(chǔ)的特點(diǎn)，通過(guò)調(diào)用f算子轉(zhuǎn)存、g算子運(yùn)算及h算子迭代生成RDD，算法實(shí)現(xiàn)步驟見(jiàn)算法1。

算法1IApriori算法

輸入：數(shù)據(jù)庫(kù)D。

輸入：最小支持度SupMin，最小置信度ConfMin。

1. for 1 tom

//m為事務(wù)項(xiàng)數(shù)

//計(jì)算每個(gè)維度屬性值ej的統(tǒng)計(jì)數(shù)

3. if(σj≤SupMin) deleteσi;//在列維度中，先進(jìn)行每

//一列的支持度σ統(tǒng)計(jì)，如σ≤SupMin則先進(jìn)行第一輪的剪枝

4. end for

5.f(ti，ej)=g(ej，ti);//構(gòu)造函數(shù)，對(duì)事務(wù)項(xiàng)ti、事務(wù)項(xiàng)維

//度數(shù)ei進(jìn)行行轉(zhuǎn)列式預(yù)處理

6. 抽取字典表T;

7. for 1 ton

//遍歷元素值“1”至“n”

8. fore1toen

//遍歷事務(wù)項(xiàng)的屬性值

9. if(ej=j)ej=1;

//轉(zhuǎn)換為布爾值

10. elseej=0;

11.φ=h(ei&e(i-1));

//構(gòu)造函數(shù)，“與”操作后計(jì)算“1”的和

12. if(ti=1)a[k]=ti;

//構(gòu)造數(shù)列a存儲(chǔ)“位”為1的行標(biāo)

13. if(((i/n)>SupMin)&&((i/σj)>ConfMin))

14.σ=i/n;ξ=i/σj;Lφ={a[k]};

//σ為支持度，ξ為置信度

15.Lφ={a[k]};

//與字典表匹配

16.輸出Lφ頻繁項(xiàng)集;

17.輸出σ和ξ;

//輸出支持度及置信度

18. end for

19. end for

3 算法性能評(píng)估

3.1 分布式計(jì)算環(huán)境配置和部署

本實(shí)驗(yàn)在青軟大數(shù)據(jù)平臺(tái)下的虛擬機(jī)中完成，本實(shí)驗(yàn)采用1個(gè)master、4個(gè)slave共5個(gè)節(jié)點(diǎn)組建集群。每個(gè)節(jié)點(diǎn)采用CentOS 7版本64位操作系統(tǒng)，內(nèi)存(RAM)3.88 GB可用，主頻2.60 GHz，軟件環(huán)境采用Hadoop2.6+Spark2.1+JDK1.8+SparkR、R、Java。首先以R語(yǔ)言部署安裝JDK，Hadoop及其環(huán)境變量并依次配置YARN、HDFS、HBase、Hive等及組件和相關(guān)依賴(lài)包，配置完成后啟動(dòng)Hadoop集群。然后在Hadoop集群中以不同數(shù)據(jù)量和不同節(jié)點(diǎn)執(zhí)行Apriori算法。最后再以R語(yǔ)言部署安裝Spark、配置環(huán)境變量及相關(guān)依賴(lài)包，在該環(huán)境中執(zhí)行Apriori算法和列陣壓縮改進(jìn)的IApriori算法。

實(shí)驗(yàn)數(shù)據(jù)集取近十年若干個(gè)高校的學(xué)生信息約15萬(wàn)條，為驗(yàn)證算法的性能拷貝模擬數(shù)據(jù)至200萬(wàn)條，數(shù)據(jù)量大小為146 MB，數(shù)據(jù)共有79列。

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

本實(shí)驗(yàn)通過(guò)彈性分析算法在不同數(shù)據(jù)量及節(jié)點(diǎn)數(shù)的執(zhí)行指標(biāo)來(lái)評(píng)價(jià)改進(jìn)算法IApriori的性能。通過(guò)對(duì)數(shù)據(jù)進(jìn)行隨機(jī)取樣，在數(shù)據(jù)集不同，最小支持度SupMin=0.05的情況下的時(shí)間運(yùn)行對(duì)比如圖7所示。IApriori算法在相同的數(shù)據(jù)集不同節(jié)點(diǎn)數(shù)上的運(yùn)行時(shí)間對(duì)比如圖8所示。

圖7 不同算法運(yùn)行時(shí)間對(duì)比

圖8 不同算法在不同節(jié)點(diǎn)個(gè)數(shù)時(shí)的執(zhí)行時(shí)間

由圖7可見(jiàn)，在Hadoop計(jì)算框架中執(zhí)行Apriori算法的效率要明顯低于基于內(nèi)存運(yùn)算的Spark框架。同時(shí)可以看出改進(jìn)算法IApriori在數(shù)據(jù)量較少時(shí)執(zhí)行效率較低，因?yàn)楦倪M(jìn)的算法采用的存儲(chǔ)方式需執(zhí)行附加的步驟。但隨著數(shù)據(jù)量不斷加大，其執(zhí)行效率高于同在Spark執(zhí)行的Apriori傳統(tǒng)算法(SApriori)，而隨著節(jié)點(diǎn)數(shù)不斷增加，改進(jìn)算法IApriori的執(zhí)行效率顯著提高。

在不同節(jié)點(diǎn)數(shù)的彈性的對(duì)比分析中(如圖8所示)，在節(jié)點(diǎn)數(shù)分別為2、3、4和5時(shí)，Hadoop框架由于數(shù)據(jù)I/O消耗時(shí)間及Apriori算法本身產(chǎn)生過(guò)多的候選頻繁項(xiàng)集而拉低了算法的執(zhí)行效率，在同一節(jié)點(diǎn)數(shù)執(zhí)行相同數(shù)據(jù)集總比Spark計(jì)算框架耗時(shí)；而改進(jìn)后的IApriori算法的效率優(yōu)于原來(lái)的Apriori算法，但由于附加了行轉(zhuǎn)列式存儲(chǔ)時(shí)間及對(duì)數(shù)據(jù)字典表的加工時(shí)間而拉低了整體的效率，而未加改進(jìn)的Apriori算法在執(zhí)行數(shù)據(jù)前需增加大量的情況，則認(rèn)為其清洗轉(zhuǎn)換工作并未包含在算法執(zhí)行時(shí)間內(nèi)。因而，改進(jìn)算法IApriori與原算法Apriori在數(shù)據(jù)集的執(zhí)行效率表現(xiàn)中優(yōu)勢(shì)差距不非常明顯。

4 結(jié) 語(yǔ)

針對(duì)Apriori算法存在產(chǎn)生大量候選頻繁項(xiàng)集和多次遍歷數(shù)據(jù)庫(kù)增加I/O消耗的缺陷，本文在基于Spark多節(jié)點(diǎn)分布式執(zhí)行算法的基礎(chǔ)之上提出了一種改進(jìn)的算法。本文算法在Spark計(jì)算框架上采用HBase列式存儲(chǔ)，構(gòu)建數(shù)據(jù)字典表，在計(jì)算過(guò)程中壓縮原本龐大的數(shù)據(jù)量，同時(shí)簡(jiǎn)化連枝剪枝只需進(jìn)行“與”操作，結(jié)合Spark分布式計(jì)算的特點(diǎn)使改進(jìn)算法的執(zhí)行效率在數(shù)據(jù)量不斷增大的模型下得到有效提高。通過(guò)實(shí)驗(yàn)對(duì)比Hadoop計(jì)算框架下執(zhí)行Apriori算法、Spark計(jì)算框架下執(zhí)行Apriori算法及本文改進(jìn)的算法，結(jié)果表明本文算法能分析多維多屬性值的數(shù)據(jù)集，一定程度上節(jié)省了數(shù)據(jù)處理前清洗及轉(zhuǎn)化工作，“與”操作后消除候選頻繁項(xiàng)集的產(chǎn)生約省了內(nèi)存計(jì)算時(shí)間及空間，在Spark基于內(nèi)存的分布式處理框架下改進(jìn)算法IApriori的執(zhí)行效率得到有效提高。