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

劉麗娜，吳新玲,2

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

0 引 言

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

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

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

1 二階分段式算法實施方案

二階分段式算法采用先聚類后分析的模式，一階對聚類算法K-Means進(jìn)行并行設(shè)計，然后聚類數(shù)據(jù)集；二階對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ù)項Ii={vi1,vi2,…,vim|1≤i≤n，m≥1}， n為事務(wù)項總數(shù)，m為數(shù)據(jù)集的維度數(shù)。假設(shè)第j個維度對應(yīng)的值域為Aj，則vij∈Aj。

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

1.1.1 K-Means算法介紹

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

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

(1)

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

(2)

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

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

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

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

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

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

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

(3)

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

(4)

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

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

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

(4) forc=1 tok

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

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

(7) end for

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

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

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

(11) end for

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

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

(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算子， 計算各點的歐幾里得距離d(Ii,Ic)′， 對各點進(jìn)行聚類

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

(22) end for

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

1.2.1 Apriori算法介紹

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

(5)

(6)

其中，i為事務(wù)項中的某一項，1≤i≤n，n為數(shù)據(jù)集D中的事務(wù)項總數(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ù)集分析，而對多維度多屬性值的數(shù)據(jù)集研究較少，或未明確說明。針對以上問題提出了KIApriori(improved Apriori algorithm combined with K-Means)，該優(yōu)化算法以改進(jìn)后的SK-Means算法聚類結(jié)果作為輸入，同時設(shè)計字典表存儲多維多屬性值數(shù)據(jù)集以達(dá)到壓縮數(shù)據(jù)量的目的，之后對各事務(wù)項進(jìn)行滾動“與”操作并統(tǒng)計支持度等數(shù)據(jù)，減少了數(shù)據(jù)集的掃描次數(shù)。

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

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

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

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

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

(7)

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

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

(8)

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

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

(9)

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

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

算法2： KIApriori算法

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

輸出： 頻繁項集、 支持度和置信度

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

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

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

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

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

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

(7) ID++;

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

(9) if(vij=j)

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

(11) else

(12)vij=0;

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

(14)Cφj=Oper(Ij&Ij-1); // Oper函數(shù)執(zhí)行事務(wù)項之間“與”操作， 如φ結(jié)果為0則Count(i)計數(shù)進(jìn)行自減，否則存儲二維候選頻繁項集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)行支持度與置信度計算

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

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

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

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

(21) end for

(22) end for

(23)end for

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

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

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

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

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

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

2.2 一階聚類離散

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

2.3 二階分析

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

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

表3 字典

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

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

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

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

3 算法及實驗結(jié)果分析

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

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

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

(10)

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

(11)

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

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

(12)

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

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

(13)

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

為驗證改進(jìn)后的KIApriori算法優(yōu)勢，以式(12)減式(13)進(jìn)行驗證。假設(shè)最差情況所有的候選項集沒有剪枝，即 |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， 否則屬性值會在第一次掃描計算剪枝時被剪掉，故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時，KIApriori算法的優(yōu)勢不明顯，但當(dāng)數(shù)據(jù)量越大時算法優(yōu)勢正比增長。

3.2 實驗結(jié)果分析

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

(1)SK-Means算法實驗結(jié)果分析

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

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

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

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

(2)KIApriori算法實驗結(jié)果分析

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

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

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

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

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

4 結(jié)束語

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