基于二階分段式的Apriori算法優(yōu)化

劉麗娜，吳新玲,2

(1.廣州工商學(xué)院 計(jì)算機(jī)科學(xué)與工程系，廣東 廣州 510850；2.廣東技術(shù)師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，廣東 廣州 510665)

0 引 言

數(shù)據(jù)挖掘模型主要有分類模型、聚類模型、回歸模型和頻繁項(xiàng)集[1]。頻繁項(xiàng)集的關(guān)聯(lián)規(guī)則算法——Apriori算法由Rakesh Agrawal和Ramakrishnan Srikant提出[2]，但后期隨著研究的不斷深入以及數(shù)據(jù)量及其復(fù)雜度的不斷增加，僅限于兩種屬性值的數(shù)據(jù)集挖掘、過(guò)多的產(chǎn)生候選頻繁項(xiàng)集和頻繁遍歷數(shù)據(jù)集導(dǎo)致內(nèi)存溢出等弊端也日益突出。

Apriori算法的改進(jìn)主要集中于減少I/O消耗和壓縮數(shù)據(jù)量。文獻(xiàn)[3]通過(guò)構(gòu)建數(shù)據(jù)集矩陣壓縮數(shù)據(jù)量提高算法執(zhí)行效率，但對(duì)數(shù)據(jù)集原型的約束較高，且對(duì)多維度多屬性值數(shù)據(jù)的挖掘模型并未說(shuō)明。文獻(xiàn)[4]Eclat算法利用數(shù)據(jù)量遠(yuǎn)大于數(shù)據(jù)集維度的特點(diǎn)提出了行與列的轉(zhuǎn)置存儲(chǔ)，壓縮數(shù)據(jù)集，但該方法不適用于分析數(shù)據(jù)集較小或事務(wù)項(xiàng)小于數(shù)據(jù)集維度的數(shù)據(jù)。文獻(xiàn)[5,6]利用Hadoop并行計(jì)算框架分散數(shù)據(jù)量，驗(yàn)證了并行計(jì)算的優(yōu)勢(shì)，但僅靠并行計(jì)算并不能讓執(zhí)行效率最大化。文獻(xiàn)[7]提出了依托Spark計(jì)算框架的Apriori改進(jìn)算法YAFIM，該算法利用哈希樹判斷候選頻繁項(xiàng)集減少I/O消耗，但因其頻繁調(diào)用算子且產(chǎn)生大量候選頻繁項(xiàng)集使得算法效率提高有限。文獻(xiàn)[8] 在文獻(xiàn)[7]的基礎(chǔ)上提出IABS算法，該算法結(jié)合文獻(xiàn)[4]行與列的轉(zhuǎn)置結(jié)構(gòu)，然后再使用YAFIM算法生成規(guī)則，雖然IABS算法的執(zhí)行效率較YAFIM算法有所提高，可擴(kuò)展性也更強(qiáng)，但YAFIM算法原有的缺陷并未消除。文獻(xiàn)[9,10]通過(guò)構(gòu)建布爾數(shù)據(jù)集矩陣壓縮數(shù)據(jù)量，同時(shí)加權(quán)減少內(nèi)存和I/O，但未分析對(duì)加權(quán)后有效規(guī)則完整性的影響。文獻(xiàn)[11]提出I-Apriori算法，該算法在YAFIM第二階段中采用布隆過(guò)濾器代替哈希存儲(chǔ)結(jié)構(gòu)減少候選頻繁項(xiàng)集生成，但在該過(guò)程中對(duì)改用布隆過(guò)濾器存儲(chǔ)數(shù)據(jù)的耗時(shí)并未加以考慮。

本文依托Spark計(jì)算框架提出一種支持多維多屬性值數(shù)據(jù)集的二階分段式Apriori算法優(yōu)化模型。一階聚類離散，降低數(shù)據(jù)擬合度提高數(shù)據(jù)差異性，二階分析形成規(guī)則。該模型先后對(duì)K-Means聚類算法和Apriori算法進(jìn)行優(yōu)化改進(jìn)，二階以一階的聚類結(jié)果作為輸入，最后通過(guò)分析和實(shí)驗(yàn)驗(yàn)證算法的執(zhí)行性能。

1 二階分段式算法實(shí)施方案

二階分段式算法采用先聚類后分析的模式，一階對(duì)聚類算法K-Means進(jìn)行并行設(shè)計(jì)，然后聚類數(shù)據(jù)集；二階對(duì)Apriori算法進(jìn)行優(yōu)化，然后將一階的聚類結(jié)果作為優(yōu)化后的Apriori算法輸入，最后分析數(shù)據(jù)集得到關(guān)聯(lián)規(guī)則。

設(shè)數(shù)據(jù)集D={I1,I2,…,In|n≥1}， 其中事務(wù)項(xiàng)Ii={vi1,vi2,…,vim|1≤i≤n，m≥1}， n為事務(wù)項(xiàng)總數(shù)，m為數(shù)據(jù)集的維度數(shù)。假設(shè)第j個(gè)維度對(duì)應(yīng)的值域?yàn)锳j，則vij∈Aj。

1.1 構(gòu)建K-Means算法優(yōu)化模型

1.1.1 K-Means算法介紹

K-Means是一種基于劃分無(wú)監(jiān)督型算法，該算法可以將相似的數(shù)據(jù)進(jìn)行聚類重組[12]，其原理分為3個(gè)階段。第一階段先確定數(shù)據(jù)集質(zhì)心Ic及其聚類數(shù)量k，然后通過(guò)計(jì)算各個(gè)數(shù)據(jù)點(diǎn)Ii到質(zhì)心Ic的歐幾里得距離[13]d (Ii,Ic) (其中Ii≠Ic且Ii、Ic∈Dc，Dc為以Ic為質(zhì)心的數(shù)據(jù)集，Dc?D)， 數(shù)據(jù)點(diǎn)Ii根據(jù)就近原則分配到相應(yīng)的質(zhì)心堆中直至所有數(shù)據(jù)點(diǎn)分配完畢；第二階段則是重新計(jì)算各個(gè)堆中的均值以調(diào)整質(zhì)心，然后重新分配數(shù)據(jù)點(diǎn)；第三階段不斷重復(fù)計(jì)算調(diào)整質(zhì)心Ic，最后通過(guò)誤差平方和函數(shù)[14]φSSE衡量聚類的擬合度。

歐幾里得距離d(Ii,Ic) 的計(jì)算公式如式(1)所示

(1)

聚類收斂性衡量指標(biāo)誤差平方和函數(shù)φSSE的計(jì)算公式如式(2)所示

(2)

式(1)和式(2)中， 1≤i≤n，Dc為以Ic為質(zhì)心的數(shù)據(jù)集，Ii為事務(wù)項(xiàng)，即聚類點(diǎn)。

1.1.2 K-Means算法優(yōu)化原理

傳統(tǒng)的K-Means算法一般多為分析只有兩種屬性值的數(shù)據(jù)集，且均在單機(jī)進(jìn)行，受數(shù)據(jù)多樣性約束，算法在計(jì)算調(diào)整質(zhì)心時(shí)容易造成內(nèi)存溢出等問(wèn)題。本文依托基于內(nèi)存的Spark計(jì)算框架提出結(jié)合Spark和K-Means的優(yōu)化算法——SK-Means(K-means algorithm based on Spark)對(duì)原K-Means算法進(jìn)行并行化設(shè)計(jì)?；趦?nèi)存的Spark計(jì)算框架可以分布計(jì)算質(zhì)心點(diǎn)，然后通過(guò)manager節(jié)點(diǎn)調(diào)整質(zhì)心減少內(nèi)存溢出風(fēng)險(xiǎn)，K-Means算法的迭代計(jì)算利用Spark計(jì)算框架各節(jié)點(diǎn)的并行計(jì)算能提升執(zhí)行效率，且在設(shè)計(jì)上增加考慮了數(shù)據(jù)的多維度多屬性值因素。

該優(yōu)化算法以“總-分-總-分”的模型對(duì)SK-Means算法進(jìn)行設(shè)計(jì)，如圖1所示。首先，確定k的取值與質(zhì)心點(diǎn)，計(jì)算聚類的誤差平方和φSSE′，根據(jù)手肘法[15]選取最優(yōu)聚類數(shù)k，隨著聚類數(shù)k的增大誤差平方和φSSE′會(huì)逐漸下降形成類似于手肘的弧度，當(dāng)曲率最高時(shí)k的取值最佳；然后選取初始質(zhì)心Ic={I1,I2,…,Ik|1≤c≤k}， 并將其存儲(chǔ)為全局變量，由于每個(gè)數(shù)據(jù)點(diǎn)與質(zhì)心點(diǎn)的歐幾里得距離是單獨(dú)計(jì)算的，因此，可以采用IClass算子計(jì)算各數(shù)據(jù)點(diǎn)到質(zhì)心點(diǎn)的歐幾里得距離d(Ii,Ic)′， 以就近原則將該數(shù)據(jù)點(diǎn)分配到所屬聚類集Dc中，Dc={D1,D2,…,Dk|1≤c≤k}， 直至所有數(shù)據(jù)點(diǎn)聚類結(jié)束；最后，以KCount算子重新計(jì)算每個(gè)聚類堆Dc的質(zhì)心I′c， 替換原全局質(zhì)心變量，重復(fù)以上過(guò)程對(duì)數(shù)據(jù)點(diǎn)進(jìn)行重新計(jì)算聚類直至聚類質(zhì)心I′c≈Ic或達(dá)到迭代閾值，輸出聚類結(jié)果。

圖1 SK-Means并行設(shè)計(jì)原理

數(shù)據(jù)點(diǎn)Ii(vi1,vi2,…,vim) 和質(zhì)心點(diǎn)Ic(vc1,vc2,…,vcm) 的歐幾里得距離d(Ii,Ic)′ 的一般性計(jì)算如式(3)所示，而多維多屬性值誤差平方和φSSE′的一般性計(jì)算則如式(4)所示。

多維度多屬性值的歐幾里得距離推導(dǎo)公式

(3)

多維多屬性值誤差平方和的推導(dǎo)公式

(4)

在式(3)和式(4)中，其中，m為數(shù)據(jù)集維度， 1≤j≤m，c為質(zhì)心點(diǎn)所在行數(shù)，i為任意點(diǎn)所在行數(shù)，vij為事務(wù)項(xiàng)中的屬性值。Dc為以Ic為質(zhì)心的數(shù)據(jù)集，Ic為質(zhì)心點(diǎn)。

1.1.3 SK-Means算法實(shí)現(xiàn)

RStudio為R語(yǔ)言提供免費(fèi)開源的跨平臺(tái)集成開發(fā)環(huán)境，具有大量圖形類型繪制和統(tǒng)計(jì)方法支持語(yǔ)法編程的多種特色功能。SK-Means算法利用R語(yǔ)言在RStudio平臺(tái)調(diào)用IClass算子計(jì)算距離進(jìn)行聚類和KCount算子計(jì)算聚類質(zhì)心，均值質(zhì)心不斷迭代生成RDD。算法首先確定最佳聚類數(shù)k，如未確定k則直接進(jìn)入算法輸出1至n(n為事務(wù)項(xiàng)總數(shù))個(gè)聚類點(diǎn)下的φSSE′值，即遍歷計(jì)算最佳聚類數(shù)k，輸出最佳聚類數(shù)，算法往下計(jì)算聚類結(jié)果；若已確定最佳k值并輸入，則輸出聚類結(jié)果，算法主要偽代碼如下：

算法1： SK-Means算法

輸入： 數(shù)據(jù)集D和k或直接回車 //如已確定最佳聚類數(shù)k則輸入k值， 未確定k則直接按回車

輸出： 已聚類的數(shù)據(jù)集Di

(1)ifk==null //如果k值為空

(2) fork=1 to n

(3) 從D中選取k個(gè)質(zhì)心：I1,I2,…,Ik;

(4) forc=1 tok

(5)Dc=?; //初始化聚類集

(6) IClass(Ic); //執(zhí)行IClass算子， 計(jì)算各點(diǎn)的歐幾里得距離d(Ii,Ic)′， 對(duì)各點(diǎn)進(jìn)行聚類

(7) end for

(8) forx=1 to m //維度遍歷

(9) fory=1 to n //屬性值遍歷

(10)I′c=∑vcxy/n; //重新計(jì)算質(zhì)心

(11) end for

(12) KCount(I′c); //執(zhí)行KCount算子， 如果質(zhì)心I′c與原質(zhì)心Ic不等或未達(dá)到閾值則更新， 相等則跳過(guò)

(13) Count φSSE′; //計(jì)算多維多屬性值誤差平方和

(14) Output φSSE′andk;//輸出誤差平方和及最優(yōu)聚類數(shù)

(15) end for

(16) end for

(17) else

(18) forc=1 tok

(19)Dc=?;

(20) IClass(); //執(zhí)行IClass算子， 計(jì)算各點(diǎn)的歐幾里得距離d(Ii,Ic)′， 對(duì)各點(diǎn)進(jìn)行聚類

(21) OutputDc; //輸出聚類結(jié)果

(22) end for

1.2 構(gòu)建Apriori算法優(yōu)化模型

1.2.1 Apriori算法介紹

當(dāng)頻繁項(xiàng)集中的規(guī)則同時(shí)滿足最小支持度Sup_Min和最小置信度Conf_Min則該規(guī)則為強(qiáng)規(guī)則，規(guī)則R(vix→viy) 的支持度Sup和置信度Conf的計(jì)算公式如式(5)和式(6)所示

(5)

(6)

其中，i為事務(wù)項(xiàng)中的某一項(xiàng)，1≤i≤n，n為數(shù)據(jù)集D中的事務(wù)項(xiàng)總數(shù)， R(vix→viy) 為屬性值vix推出viy的規(guī)則，x、y屬于自然數(shù)x≠y且x、y≤m， m為數(shù)據(jù)集的維度總數(shù)。

1.2.2 Apriori算法優(yōu)化原理

Apriori算法執(zhí)行效率低且在以往的優(yōu)化中大部分集中考慮維度只有兩種屬性值的數(shù)據(jù)集分析，而對(duì)多維度多屬性值的數(shù)據(jù)集研究較少，或未明確說(shuō)明。針對(duì)以上問(wèn)題提出了KIApriori(improved Apriori algorithm combined with K-Means)，該優(yōu)化算法以改進(jìn)后的SK-Means算法聚類結(jié)果作為輸入，同時(shí)設(shè)計(jì)字典表存儲(chǔ)多維多屬性值數(shù)據(jù)集以達(dá)到壓縮數(shù)據(jù)量的目的，之后對(duì)各事務(wù)項(xiàng)進(jìn)行滾動(dòng)“與”操作并統(tǒng)計(jì)支持度等數(shù)據(jù)，減少了數(shù)據(jù)集的掃描次數(shù)。

KIApriori算法與SK-Means算法同處于Spark計(jì)算框架進(jìn)行，數(shù)據(jù)存儲(chǔ)依賴于HBase，一般多維多屬性值數(shù)據(jù)存儲(chǔ)模式見表1。

表1 多維多屬性數(shù)據(jù)集存儲(chǔ)模式

KIApriori算法中二階Apriori算法的優(yōu)化原理分為兩個(gè)環(huán)節(jié)。第一個(gè)環(huán)節(jié)是構(gòu)建字典表，首先統(tǒng)計(jì)各元素在數(shù)據(jù)集中的計(jì)數(shù)，之后將數(shù)據(jù)集字典表化，字典表的構(gòu)建根據(jù)數(shù)據(jù)集的維度按1∶1建字典表中的列，即一個(gè)維度在字典表建一列，字典表包含一個(gè)維度的所有屬性值，并且所有屬性值在字典表中唯一。其中，字典表中的ID為整型數(shù)據(jù)，ID在所在維度字典表中唯一，但在各維度中不唯一。第二個(gè)環(huán)節(jié)是“與”計(jì)算，該環(huán)節(jié)類似于地球的“公轉(zhuǎn)”與“自轉(zhuǎn)”執(zhí)行數(shù)據(jù)集的“與”操作，“公轉(zhuǎn)”即執(zhí)行操作時(shí)由1至字典表最大ID值IDMAX將事務(wù)項(xiàng)中與ID值相同的屬性值替換為“1”，其它值替換為“0”進(jìn)行向下滾動(dòng)式 “與”操作?！白赞D(zhuǎn)”則是在ID值第一輪“1”替換后，事務(wù)項(xiàng)向下進(jìn)行“與”滾動(dòng)。在每一次“與”操作時(shí)設(shè)置計(jì)數(shù)器自增，最后根據(jù)計(jì)數(shù)與項(xiàng)集數(shù)得出頻繁項(xiàng)集，即關(guān)聯(lián)規(guī)則。

1.2.3 KIApriori算法建模設(shè)計(jì)及實(shí)現(xiàn)

KIApriori算法的支持度KSup設(shè)計(jì)如式(7)所示

(7)

其中，Count為事務(wù)項(xiàng) “與”操作的計(jì)數(shù)，n為事務(wù)項(xiàng)總數(shù)。

KIApriori算法的置信度KConf設(shè)計(jì)如式(8)所示

(8)

式(8)中，Count(R(vix→viy)) 為規(guī)則R(vix→viy) 的“與”操作計(jì)數(shù)，Count(vix) 是數(shù)據(jù)集字典表化前屬性值vix的計(jì)數(shù)。

定義1 項(xiàng)集數(shù)：項(xiàng)集數(shù)φ為頻繁項(xiàng)集中關(guān)聯(lián)的屬性值個(gè)數(shù)。頻繁φ項(xiàng)集Lφ中的項(xiàng)集數(shù)φ計(jì)算如式(9)所示

(9)

其中， 0≤i≤(m-1)， m為數(shù)據(jù)集維度總數(shù)，AND[i] 為存放事務(wù)項(xiàng)“與”操作的結(jié)果的數(shù)組。

該算法依托Spark計(jì)算框架，以SK-Means優(yōu)化算法的聚類結(jié)果作為輸入，主要算法設(shè)計(jì)如下：

算法2： KIApriori算法

輸入： 已聚類的數(shù)據(jù)集D， 最小支持度Sup_Min， 最小置信度Conf_Min

輸出： 頻繁項(xiàng)集、 支持度和置信度

(1)fori=1 to n //遍歷所有事務(wù)項(xiàng)

(2) forj=1 to m //遍歷所有維度

(3)Count(i);//計(jì)算每個(gè)屬性值的統(tǒng)計(jì)數(shù)

(4) if(Count(i)<=Sup_Min)

(5) deletevij;//對(duì)于統(tǒng)計(jì)數(shù)小于最小支持度的屬性值進(jìn)行第一輪剪枝

(6) if(vij!=v(i-1)j) //構(gòu)建字典表T

(7) ID++;

(8) T(ID)=vij; //存儲(chǔ)字典表值

(9) if(vij=j)

(10)vij=1; //涉及 “與” 操作事務(wù)項(xiàng)轉(zhuǎn)換為布爾值

(11) else

(12)vij=0;

(13)φ=Sum(Ij&Ij-1)；//構(gòu)建函數(shù)， 計(jì)算與結(jié)果中所有值為“1”的和

(14)Cφj=Oper(Ij&Ij-1); // Oper函數(shù)執(zhí)行事務(wù)項(xiàng)之間“與”操作， 如φ結(jié)果為0則Count(i)計(jì)數(shù)進(jìn)行自減，否則存儲(chǔ)二維候選頻繁項(xiàng)集Cφj，j等于字典表中的ID標(biāo)記sign， 以便還原屬性值原內(nèi)容

(15) fork=0 to IDMAX-1 // IDMAX為字典表最大的ID值

(16) if(((i/n)>=Sup_Min)&&((i/Count(j))>=Conf_Min)) //檢查符合最小支持度和置信度并進(jìn)行支持度與置信度計(jì)算

(17)Supφ=i/n;Confφ=i/Count(j); //分別用Supφ，Confφ存儲(chǔ)頻繁項(xiàng)集的支持度與置信度

(18)Lφ=Match(Cφj,k);// 還原頻繁項(xiàng)集

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

(20) 輸出SupφandConfφ; //輸出支持度及置信度

(21) end for

(22) end for

(23)end for

2 應(yīng)用實(shí)現(xiàn)

2.1 數(shù)據(jù)預(yù)處理

本文結(jié)合工作實(shí)際，以廣東若干高等院校2014屆至2018屆共5屆的畢業(yè)生為研究對(duì)象，收集教務(wù)管理系統(tǒng)、學(xué)生就業(yè)信息、校外考證數(shù)據(jù)、學(xué)生選課系統(tǒng)、圖書管理數(shù)據(jù)和校園一卡通管理系統(tǒng)中的相關(guān)數(shù)據(jù)構(gòu)建數(shù)據(jù)集。為了提高挖掘規(guī)則的魯棒性，需對(duì)數(shù)據(jù)進(jìn)行清洗和概化[16]，實(shí)驗(yàn)采用“數(shù)據(jù)選擇-數(shù)據(jù)清洗-數(shù)據(jù)轉(zhuǎn)換-數(shù)據(jù)集成”的流程對(duì)數(shù)據(jù)進(jìn)行預(yù)處理。

本實(shí)驗(yàn)收集的數(shù)據(jù)記錄共151 107條，除去中途休學(xué)退學(xué)的63個(gè)學(xué)生，該部分?jǐn)?shù)據(jù)占總數(shù)的0.04%，亦屬于離群噪點(diǎn)，去除之后對(duì)數(shù)據(jù)整體的有效性及完整性的影響幾乎可忽略。此外，對(duì)部分?jǐn)?shù)據(jù)進(jìn)行降維，例如成績(jī)的區(qū)間為[0,100]，概化為不及格[0,60)，及格[60,70)，中等[70,80)，良好[80,90)和優(yōu)秀[90,100]這5個(gè)級(jí)別以消除多余屬性對(duì)挖掘結(jié)果的影響。

本實(shí)驗(yàn)數(shù)據(jù)經(jīng)過(guò)清洗后得到約15萬(wàn)個(gè)往屆畢業(yè)生的數(shù)據(jù)記錄，涉及37個(gè)維度，通過(guò)數(shù)據(jù)概化后得到148種屬性，總大小約16 MB，選取部分已預(yù)處理的數(shù)據(jù)集見表2。

表2 多維多屬性數(shù)據(jù)集實(shí)例

2.2 一階聚類離散

實(shí)驗(yàn)數(shù)據(jù)集屬性值多且構(gòu)成復(fù)雜，直接對(duì)其進(jìn)行分析可能存在挖掘效果擬合高穩(wěn)定性低等問(wèn)題。因此對(duì)數(shù)據(jù)集進(jìn)行聚類離散有利于增強(qiáng)數(shù)據(jù)特征差異性和發(fā)現(xiàn)魯棒性強(qiáng)規(guī)則，同時(shí)提高規(guī)則形成效率。

2.3 二階分析

在第二階段中，設(shè)最小支持度Sup_Min=0.4, 首先計(jì)算每一數(shù)據(jù)集中各維度屬性值的計(jì)數(shù)，然后根據(jù)式(7)將各計(jì)數(shù)結(jié)果除以事務(wù)項(xiàng)總數(shù)7對(duì)比支持度剪去低于支持度的事務(wù)項(xiàng)從而壓縮數(shù)據(jù)集。

在表2中剪去不符合支持度的事務(wù)項(xiàng)，然后將符合條件的數(shù)據(jù)集字典表化，字典表中的ID唯一，每一個(gè)維度的每一個(gè)屬性值都對(duì)應(yīng)一個(gè)ID。該實(shí)例中字典表的構(gòu)建見表3。

表3 字典

剪枝后的數(shù)據(jù)集根據(jù)字典表3進(jìn)行轉(zhuǎn)換實(shí)現(xiàn)數(shù)據(jù)集的再次壓縮，將屬性值對(duì)應(yīng)字典表轉(zhuǎn)換結(jié)果見表4，即將符合支持度計(jì)數(shù)的各個(gè)維度的屬性值替換成字典表中對(duì)應(yīng)的ID號(hào)。

表4 數(shù)據(jù)集字典表轉(zhuǎn)換

該步驟中第一次從“1”開始替換第一行，即第一行中的所有“1”替換為“1”，其它值替換為“0”，記錄標(biāo)志sign=1，sign標(biāo)記所替換的值以便于規(guī)則表達(dá)式還原。該實(shí)例中，事務(wù)項(xiàng)的第一行“16001”(1,1,1,1)被替換之后為“16001”(1,1,1,1)，然后將第二行“16002”(- -,- -,2,2)取出并替換，替換后為“16002”(0,0,0,0)，然后執(zhí)行事務(wù)項(xiàng)“16001”和“16002”的“與”操作，結(jié)果為“16001”&“16002”(0,0,0,0)，然后取出“16003”(1,1,1,1)，替換之后為“16003”(1,1,1,1)，再和替換后的第一行“16001”(1,1,1,1)“與”結(jié)果為“16001”&“16003”(1,1,1,1)，然后再和“16004”執(zhí)行“與”操作，結(jié)果為“16001”&“16004”，以此類推，“16001”再與“16005”、“16006”和“16007”進(jìn)行“與”操作，然后將“與”結(jié)果再一一向下進(jìn)行“與”操作直至最后一項(xiàng)，如“16001”&“16003”(1,1,1,1) 和“16004”執(zhí)行“與”操作結(jié)果為“16001”&“16003”&“16004”(1,1,1,0)。同理，“16002”與之后的記錄進(jìn)行同樣滾動(dòng)“與”操作。然后執(zhí)行“公轉(zhuǎn)”，即將“2”替換為“1”其它值替換為“0”進(jìn)行向下滾動(dòng)執(zhí)行，記錄標(biāo)志sign=2，以此類推直至最大ID值IDMAX。

在進(jìn)行一次“與”操作時(shí)，如“與”結(jié)果為0(即φ為0)則計(jì)數(shù)器Count減1否則加1，若 (Count/n)≥Sup_Min， 則依次可得到各項(xiàng)頻繁項(xiàng)集。頻繁φ項(xiàng)集Lφ中的項(xiàng)集數(shù)φ等于“與”結(jié)果中所有值的和。例如，計(jì)數(shù)器Count=3，記錄標(biāo)志sign=1，而事務(wù)總數(shù)n=7，則 (3/7)>0.4 (最小支持度)，“16001”&“16003”&“16004”(1,1,1,0)，則項(xiàng)集數(shù)φ=1+1+1+0=3， 即頻繁3項(xiàng)集L3={1,1,1,0}[sign=1]， 一一對(duì)應(yīng)各維度為L(zhǎng)3={“平均成績(jī)”*1,“圖書瀏覽記錄”*1,“一卡通消費(fèi)”*1,“職業(yè)類型”*0}={“平均成績(jī)”,“圖書瀏覽記錄”,“一卡通消費(fèi)”}， 標(biāo)記sign=1對(duì)應(yīng)字典表中ID=1的元素，因此，頻繁3項(xiàng)集L3={“平均成績(jī)”.“優(yōu)”,“圖書瀏覽記錄”.“頻繁”, “一卡通消費(fèi)”.“消費(fèi)級(jí)別3”}， 由此得到頻繁項(xiàng)集。

3 算法及實(shí)驗(yàn)結(jié)果分析

3.1 算法復(fù)雜度分析

K-Means算法的時(shí)間復(fù)雜度如式(10)所示

TCK-Means=O(k*n*Iteratetime*Td(Ii,Ic))

(10)

其中，k為聚類數(shù)，n為事務(wù)項(xiàng)總數(shù)，Iteratetime為算法迭代次數(shù)， Td(Ii,Ic) 為計(jì)算點(diǎn)Ii到點(diǎn)Ic的距離所花費(fèi)的時(shí)間。而并行設(shè)計(jì)后的SK-Means算法在多個(gè)節(jié)點(diǎn)運(yùn)行，若Spark中的節(jié)點(diǎn)數(shù)為Num，每個(gè)節(jié)點(diǎn)完成的IClass算子次數(shù)為Times，則SK-Means算法的時(shí)間復(fù)雜度如式(11)所示

(11)

從時(shí)間復(fù)雜度上分析，SK-Means算法比原K-Means算法在執(zhí)行時(shí)間上具有明顯優(yōu)勢(shì)。

Apriori算法復(fù)雜度如式(12)所示

(12)

其中，n*m為第一次掃描數(shù)據(jù)庫(kù)各事務(wù)項(xiàng)計(jì)數(shù)花費(fèi)的時(shí)間，第一次剪枝花費(fèi)時(shí)間亦為n*m，故有2n*m， |Lφ-1| 為生成候選頻繁φ項(xiàng)集Cφ的連枝時(shí)間， n*|Cφ| 為計(jì)算Cφ各項(xiàng)計(jì)數(shù)的時(shí)間， |Cφ|2為Cφ的剪枝時(shí)間。

KIApriori算法復(fù)雜度如式(13)所示

(13)

其中，第一次計(jì)算掃描數(shù)據(jù)集和剪枝所花費(fèi)的時(shí)間與原算法同為2n*m，而構(gòu)建字典表和數(shù)據(jù)集轉(zhuǎn)換的時(shí)間復(fù)雜度為n*m*IDMAX，算法滾動(dòng)“與”操作生成頻繁項(xiàng)集的時(shí)間復(fù)雜度為n*m*IDMAX，最后對(duì)比字典表還原頻繁項(xiàng)集的時(shí)間復(fù)雜度為m*IDMAX*|Lφ|。

為驗(yàn)證改進(jìn)后的KIApriori算法優(yōu)勢(shì)，以式(12)減式(13)進(jìn)行驗(yàn)證。假設(shè)最差情況所有的候選項(xiàng)集沒有剪枝，即 |Cφ|≈|Lφ|≈|Lφ-1|≈n則TCApriori-TCKIApriori=(L12+…+Lm-12)+n(C2+…+Cm)+(C22+…+Cm2)-2n*m*IDMAX-m*IDMAX(L1+…+Lm-1)-TCSK-Means=3n3-2n*IDMAX*m-m*IDMAX* n2-TCSK-Means=n2(3n-2m-m*IDMAX-k)。

n、m、IDMAX及k的大小決定KIApriori算法的適用情況，特別是數(shù)據(jù)量， (n/IDMAX)/n>Sup_Min， 否則屬性值會(huì)在第一次掃描計(jì)算剪枝時(shí)被剪掉，故IDMAX<(1/Sup_Min)?n， 聚類數(shù)k亦然，一般情況下數(shù)據(jù)集維度數(shù)m?n， TCApriori-TCKIApriori>0， 而當(dāng)數(shù)據(jù)量較小，即n≤(2 m+m*IDMAX+k)/3時(shí)，KIApriori算法的優(yōu)勢(shì)不明顯，但當(dāng)數(shù)據(jù)量越大時(shí)算法優(yōu)勢(shì)正比增長(zhǎng)。

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

本實(shí)驗(yàn)依托青島青軟實(shí)訓(xùn)教育科技股份有限公司合作平臺(tái)提供的虛擬機(jī)，采用一個(gè)主節(jié)點(diǎn)5個(gè)從節(jié)點(diǎn)構(gòu)建集群。Master節(jié)點(diǎn)和slave節(jié)點(diǎn)均用64位的CentOS7操作系統(tǒng)，主頻2.66 GHz四核，內(nèi)存4 GB軟件環(huán)境組合Hadoop2.6+Spark2.1+JDK1.8+SparkR。為驗(yàn)證算法的執(zhí)行性能，本實(shí)驗(yàn)將數(shù)據(jù)集拷貝至5*107條，數(shù)據(jù)維度及屬性不變，得到總大小約5 GB的數(shù)據(jù)集。分兩個(gè)階段對(duì)優(yōu)化后的SK-Means 和KIApriori算法進(jìn)行分析。

(1)SK-Means算法實(shí)驗(yàn)結(jié)果分析

以傳統(tǒng)的K-Means算法對(duì)比優(yōu)化后的SK-Means算法，取UCI數(shù)據(jù)庫(kù)中的wine、heart、Iris、letter和pima數(shù)據(jù)集的準(zhǔn)確率和執(zhí)行時(shí)間對(duì)比衡量算法性能，如圖2、圖3所示。

圖2 SK-Means與K-Means算法準(zhǔn)確率對(duì)比

圖3 SK-Means與K-Means算法執(zhí)行時(shí)間對(duì)比

由圖2對(duì)比可以看出，SK-Means算法不但沒有消減原K-Means算法的聚類效果且聚類準(zhǔn)確率更高，SK-Means算法的準(zhǔn)確率平均值比原K-Means算法高約32%。在圖3中，SK-Means算法與原算法在不同數(shù)據(jù)量，不同質(zhì)心k值的運(yùn)行時(shí)間上，由于SK-Means算法受多維多屬性數(shù)據(jù)集的多樣性約束，在數(shù)據(jù)量較少時(shí)其優(yōu)勢(shì)不明顯，但在分布式并行計(jì)算框架下隨著數(shù)據(jù)量和聚類數(shù)的增加其聚類速度明顯提高。

(2)KIApriori算法實(shí)驗(yàn)結(jié)果分析

該階段的實(shí)驗(yàn)首先以Spark計(jì)算框架執(zhí)行原Apriori算法，然后執(zhí)行無(wú)K-Means算法加持但字典表化的Apriori優(yōu)化算法，即不以SK-Means的聚類結(jié)果作為輸入，直接執(zhí)行二階的優(yōu)化后的Apriori算法(簡(jiǎn)稱IApriori算法)，最后執(zhí)行KIApriori算法。當(dāng)最小支持度和置信度Sup_Min=Conf_Min=0.05時(shí)，在相同測(cè)試條件下彈性執(zhí)行Apriori、IApriori和KIApriori這3種算法以對(duì)比評(píng)估其性能，各算法的執(zhí)行時(shí)間不同節(jié)點(diǎn)數(shù)執(zhí)行時(shí)間對(duì)比如圖4、圖5所示。

圖4 不同算法執(zhí)行時(shí)間對(duì)比

圖5 不同算法不同節(jié)點(diǎn)數(shù)執(zhí)行時(shí)間對(duì)比

從圖4可以看出未優(yōu)化的Apriori算法隨著數(shù)據(jù)量遞增其運(yùn)行效率明顯低于優(yōu)化后的IApriori算法，執(zhí)行時(shí)間幾乎是IApriori算法的兩倍。同比無(wú)K-Means加持的IApriori算法和有K-Means加持的KIApriori算法，因KIApriori算法在一階時(shí)耗費(fèi)一部分的時(shí)間執(zhí)行SK-Means聚類，因此在處理數(shù)據(jù)量較少的情況下其運(yùn)行效率不高，此時(shí)適用IApriori算法。但隨著數(shù)據(jù)量的不斷增加，其執(zhí)行效率優(yōu)勢(shì)逐漸突出，在該實(shí)驗(yàn)后期，當(dāng)數(shù)據(jù)量達(dá)到3 G的“拐點(diǎn)”時(shí)，KIApriori算法相對(duì)于IApriori算法執(zhí)行效率提高47%以上。

而在不同節(jié)點(diǎn)數(shù)相同數(shù)據(jù)量的對(duì)比圖5中，Apriori算法執(zhí)行時(shí)間明顯高于其它兩種算法。對(duì)比IApriori和KIApriori 算法，因?yàn)楣?jié)點(diǎn)數(shù)較少，使得前期聚類優(yōu)勢(shì)不明顯，當(dāng)節(jié)點(diǎn)數(shù)越接近聚類數(shù)時(shí)KIApriori算法的執(zhí)行效率越高。

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

本文在基于內(nèi)存計(jì)算的Spark并行計(jì)算框架下，提出了二階分段式KIApriori算法模型，一階聚類離散去除離群點(diǎn)壓縮數(shù)據(jù)集增強(qiáng)數(shù)據(jù)差異性提高算法的規(guī)則生成效率，二階構(gòu)建字典表再次壓縮數(shù)據(jù)集，“與”操作簡(jiǎn)化連枝剪枝去候選頻繁項(xiàng)集降低I/O和內(nèi)存消耗。該改進(jìn)算法適用于分析各種結(jié)構(gòu)化大數(shù)據(jù)集，數(shù)據(jù)量越大算法優(yōu)勢(shì)越明顯。通過(guò)算法分析及彈性實(shí)驗(yàn)分析結(jié)果表明，KIApriori算法在大數(shù)據(jù)分析中有較高的分析效率和良好的可伸縮性。下一步將研究分析該算法中“拐點(diǎn)”出現(xiàn)的一般規(guī)律。