李 潔,朱洪亮,陳玉玲,辛 陽

(1.北京郵電大學(xué) 網(wǎng)絡(luò)空間安全學(xué)院,北京 100876; 2.貴州大學(xué) 貴州省公共大數(shù)據(jù)重點實驗室,貴陽 550025)

0 概述

數(shù)據(jù)挖掘是指從海量、不完整以及模糊的實際應(yīng)用數(shù)據(jù)中,提取出人們事先不知道但又可能有價值的信息和知識的過程[1]。關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘領(lǐng)域中的一個重要研究方向,其最早由AGRAWAL等人[2]針對超市購物籃問題分析提出,目的是為了發(fā)現(xiàn)超市交易數(shù)據(jù)庫中不同商品之間的關(guān)聯(lián)關(guān)系。經(jīng)典關(guān)聯(lián)規(guī)則挖掘算法包括Apriori算法[2]和FP-Growth算法[3]。Apriori算法擴展性較好,可以應(yīng)用于并行計算等領(lǐng)域,但是其多次掃描事務(wù)數(shù)據(jù)庫,每次利用候選頻繁集產(chǎn)生頻繁集,需要很大的I/O負載。FP-Growth算法利用樹形結(jié)構(gòu),無需通過候選頻繁集而直接產(chǎn)生頻繁集,大幅減少了掃描事務(wù)數(shù)據(jù)庫的次數(shù),從而提高了算法效率。目前,Apriori和FP-Growth 2種算法均廣泛應(yīng)用于市場營銷、網(wǎng)絡(luò)安全和生物信息學(xué)等領(lǐng)域。

隨著信息化時代的到來,網(wǎng)絡(luò)交互呈爆炸式增長,需要處理的數(shù)據(jù)量從GB量級增長到了PB量級,其中,非結(jié)構(gòu)化數(shù)據(jù)占數(shù)據(jù)總量的80%～90%,且其價值密度較低,這對數(shù)據(jù)挖掘算法的性能提出了更高的要求。傳統(tǒng)Apriori算法由于每計算一次候選集的支持度都需要遍歷原始事務(wù)數(shù)據(jù)庫,因此需要多次掃描數(shù)據(jù)庫,效率較低,不能滿足大數(shù)據(jù)處理的要求,對Apriori算法進行改進顯得尤為必要。

本文針對傳統(tǒng)Apriori算法運行效率低的問題,提出一種基于哈希存儲與事務(wù)加權(quán)的并行Apriori算法。利用哈希結(jié)構(gòu)對事務(wù)進行去重,同時將項目與項集的映射存儲在哈希結(jié)構(gòu)中,避免計算候選集的支持度時多次掃描事務(wù)數(shù)據(jù)庫。同時,通過多線程并行計算候選集的支持度來提高Apriori算法的運行效率。

1 關(guān)聯(lián)規(guī)則挖掘相關(guān)研究

目前,國內(nèi)外學(xué)者對關(guān)聯(lián)規(guī)則挖掘算法進行了大量研究,對挖掘算法的改進主要分為以下4類:

1)基于數(shù)據(jù)存儲結(jié)構(gòu)的改進算法。該類改進主要利用矩陣、樹和圖等數(shù)據(jù)結(jié)構(gòu)對事務(wù)信息進行存儲,以達到減少數(shù)據(jù)庫掃描次數(shù)的目的[3-5]。文獻[6]提出一種改進的Apriori算法,其通過生成布爾矩陣減少事務(wù)數(shù)據(jù)庫的遍歷次數(shù),降低了關(guān)聯(lián)規(guī)則挖掘的時間和空間復(fù)雜度,但是當(dāng)數(shù)據(jù)量較大時,該算法對內(nèi)存的要求較高。文獻[7]提出一種基于矩陣與權(quán)重向量的Apriori改進方法,該方法通過權(quán)重計算在一定程度上壓縮了數(shù)據(jù)矩陣,但當(dāng)數(shù)據(jù)量較大時,布爾矩陣的計算性能會顯著降低。文獻[8]提出一種NSFI算法以挖掘關(guān)聯(lián)規(guī)則,其通過使用哈希表來存儲與頻繁1項集相關(guān)聯(lián)的N個事務(wù),計算候選集的支持度時只需查找對應(yīng)2個列表之間的交集,從而提高了算法的運行效率和內(nèi)存使用率,但該算法取交集的效率較低,且未考慮事務(wù)重復(fù)的情況,當(dāng)事務(wù)重復(fù)較多時,其會存儲大量的冗余數(shù)據(jù),導(dǎo)致性能降低。

2)基于多種算法相結(jié)合的改進算法。將關(guān)聯(lián)規(guī)則算法與其他算法相結(jié)合的改進方式[9],可以發(fā)揮關(guān)聯(lián)規(guī)則算法與其他算法的優(yōu)勢。文獻[10]提出一種基于遺傳算法來尋找頻繁項集的GNA算法,其結(jié)合Apriori算法和遺傳算法的特點,設(shè)計k步挖掘過程,利用交叉算子產(chǎn)生候選項集和變異算子從而篩選頻繁項集,在避免多次掃描數(shù)據(jù)庫的同時減少冗余。文獻[11]提出一種Apriori算法和遺傳算法相結(jié)合的方法,其采用支持度、置信度和覆蓋度作為規(guī)則的評價指標,與傳統(tǒng)Apriori算法相比,該方法可以在相同的支持度下找到更多滿足用戶期望的規(guī)則,并減少無用規(guī)則的生成。文獻[12]將Apriori算法和圖形計算相結(jié)合,提出一種圖形計算方法ANG來進行頻繁項集挖掘。當(dāng)k很小時,使用Apriori算法計算k項候選集的支持度,當(dāng)k增大時,使用圖形計算方法計算k項候選集的支持度,并給出公式來確定何時從Apriori算法轉(zhuǎn)換到圖形計算方法。相較于傳統(tǒng)Apriori算法和圖形計算方法,ANG方法在性能上有很大提升。但是,基于多種算法相結(jié)合的改進算法大多計算過程復(fù)雜,且混合算法中的參數(shù)容易受到數(shù)據(jù)集的影響。

3)基于MapReduce[13]等并行處理技術(shù)的改進算法。該類改進算法主要利用并行處理技術(shù),對頻繁集的查找過程做并行計算,從而縮短算法的運行時間。文獻[14]提出一種并發(fā)關(guān)系關(guān)聯(lián)規(guī)則挖掘(CRAR)方法,該方法利用并發(fā)性有效縮短了挖掘關(guān)聯(lián)規(guī)則的時間,但是其縮放效率和并行運算效率不高,還需進一步優(yōu)化。文獻[15-17]利用開源框架Hadoop中的MapReduce并行處理技術(shù),將數(shù)據(jù)集按事務(wù)進行分組,利用分布式計算的優(yōu)勢使各節(jié)點并行地完成候選項集生成與剪枝操作,從而提高Apriori算法的性能,但是此類改進算法采用HDFS(Hadoop Distributed File System)存儲系統(tǒng),每次計算的中間結(jié)果都會寫入磁盤,造成很多不必要的I/O負載,降低了算法的執(zhí)行效率。針對上述問題,文獻[18]將關(guān)聯(lián)規(guī)則算法FP-Growth與Spark框架進行結(jié)合,計算的中間結(jié)果不再寫入磁盤,并針對挖掘頻繁項集過程中分組不均衡的問題給出解決方案,提高了FP-Growth算法的并行運算效率,但此類改進算法并行計算的效果參差不齊且不穩(wěn)定,容易受數(shù)據(jù)分組算法的影響,且應(yīng)用框架不夠輕量,不利于應(yīng)用的遷移和擴展。

4)基于約束條件的改進算法。該類改進算法主要針對關(guān)聯(lián)規(guī)則挖掘算法中的頻繁集補充約束條件,降低無意義的候選頻繁集產(chǎn)生。文獻[19]提出一種基于SET-PSO的正負關(guān)聯(lián)規(guī)則挖掘方法,其通過粒子群優(yōu)化從數(shù)據(jù)庫中生成關(guān)聯(lián)規(guī)則,同時考慮屬性的正相關(guān)性和負相關(guān)性,從而減少候選頻繁集的產(chǎn)生,提升Apriori算法的運行效率,但是該算法生成正負關(guān)聯(lián)規(guī)則的相關(guān)系數(shù)往往需要人工確定。文獻[20]針對序列數(shù)據(jù)邊界難以確定的問題,提出一種基于模糊關(guān)聯(lián)規(guī)則挖掘(DOFARM)的新型參數(shù)和度量動態(tài)優(yōu)化方法,其通過使用一定范圍內(nèi)的分界值平滑地分離2個連續(xù)的分區(qū),并為原始數(shù)據(jù)集生成模糊集制定相應(yīng)的隸屬函數(shù),有效解決了連續(xù)數(shù)據(jù)的分組問題,同時對分組參數(shù)進行動態(tài)優(yōu)化,在實驗數(shù)據(jù)集上取得了較好的效果?；诩s束條件的改進算法多數(shù)是針對某種情況下的特定問題而提出。

2 并行Apriori改進算法

2.1 傳統(tǒng)Apriori算法

關(guān)聯(lián)規(guī)則挖掘算法主要用來查找和分析隱藏在項集之間的類似X?Y的規(guī)則,Apriori算法[2]是該領(lǐng)域的最經(jīng)典算法之一,用來查找海量數(shù)據(jù)中有價值的隱藏關(guān)聯(lián)知識。Apriori算法的經(jīng)典應(yīng)用是通過對超市交易數(shù)據(jù)的關(guān)聯(lián)分析,發(fā)現(xiàn)“尿布”和“啤酒”之間的關(guān)聯(lián)關(guān)系,從而使超市獲得了可觀的經(jīng)濟收益。Apriori算法中的相關(guān)概念[21]如下:

1)項目和項集。設(shè)I={i1,i2,…,im}為項的集合,即項集。項集中的每個ik(k=1,2,…,m)稱為項目(item)。項集的長度就是項集I含有的項目數(shù)量,長度為k的項集在本文中稱為k-項集(k-itemset)。

2)事務(wù)和事務(wù)數(shù)據(jù)庫。每個事務(wù)(transaction)都是項集I的一個子集,記為T,即T?I。本文使用事務(wù)ID來區(qū)分不同的事務(wù),以方便頻繁集的查找和計數(shù)。事務(wù)數(shù)據(jù)庫D是全部事務(wù)的集合,本文用|D|來表示D中包含的事務(wù)個數(shù)。

3)項集的支持度。對于項集X,X?I,本文使用count(X?T)表示數(shù)據(jù)庫D中包含X的事務(wù)數(shù)量,則項集X的支持度定義為:

(1)

4)項集的最小支持度和頻繁集。在查找關(guān)聯(lián)規(guī)則的過程中,項集要滿足一個指定的支持度閾值,這個指定的支持度閾值就是項集的最小支持度,記為supmin。當(dāng)一個項集的支持度不低于supmin時,稱該項集為頻繁項集,即頻繁集;不滿足此條件的項集,稱為非頻繁集。k-項集的支持度若不低于supmin,通常稱為k-頻繁集,記作Lk。

5)關(guān)聯(lián)規(guī)則。本文定義關(guān)聯(lián)規(guī)則的形式如下:

R:X?Y

(2)

其中,X?I,Y?I,且X∩Y=?。規(guī)則R表示當(dāng)一個事務(wù)中出現(xiàn)X時,在某一概率下該事務(wù)中也會出現(xiàn)Y。本文稱X為規(guī)則R的條件,Y為規(guī)則R的結(jié)果。關(guān)聯(lián)規(guī)則R:X?Y反映了如下規(guī)律:當(dāng)X中的項目出現(xiàn)時,Y中的項目也會隨之出現(xiàn)。

6)關(guān)聯(lián)規(guī)則的支持度。對于關(guān)聯(lián)規(guī)則R:X?Y,X?I,Y?I,且X∩Y=?,事務(wù)數(shù)據(jù)庫中同時包含X和Y的事務(wù)個數(shù)與所有事務(wù)個數(shù)之比為規(guī)則R的支持度,記為support(X?Y),表示為:

(3)

7)關(guān)聯(lián)規(guī)則的可信度。對于規(guī)則R:X?Y,X?I,Y?I,且X∩Y=?,其可信度是指同時包含X和Y的事務(wù)個數(shù)與包含X的事務(wù)個數(shù)的比值,記為confidence(X?Y)?？尚哦确从沉巳羰聞?wù)中出現(xiàn)X則事務(wù)中同時出現(xiàn)Y的概率,表達式如下:

(4)

8)連接和剪枝。當(dāng)2個長度相同的頻繁項集只有一個項不同時,將它們連接在一起產(chǎn)生候選頻繁集的過程稱為連接。根據(jù)Apriori算法的性質(zhì)“頻繁集的任一子集都是頻繁的”來修剪候選頻繁集的過程稱為剪枝。

傳統(tǒng)Apriori算法是一個迭代挖掘頻繁模式的過程[22],挖掘過程中會不斷地產(chǎn)生候選頻繁集,然后計算候選集的支持度,由候選集產(chǎn)生頻繁集,再由頻繁集經(jīng)過連接、剪枝步驟生成新的候選集,如此重復(fù),直到無法產(chǎn)生新的頻繁集則算法終止。對于項集X,X?I,若support(X)≥supmin,則X為頻繁集。傳統(tǒng)Apriori算法流程如圖1所示。傳統(tǒng)Apriori算法每次計算候選頻繁集的支持度,都需要遍歷一次事務(wù)數(shù)據(jù)庫,存在掃描數(shù)據(jù)庫頻繁、產(chǎn)生候選項集多、耗時較長等問題,在實際應(yīng)用中往往運行效率較低。本文針對Apriori算法的不足,提出一種基于哈希存儲與事務(wù)加權(quán)的并行Apriori改進算法,以提升傳統(tǒng)Apriori算法的性能。

圖1 傳統(tǒng)Apriori算法流程

2.2 Apriori算法改進

本文利用哈希存儲的去重特性對事務(wù)進行去重,在一定程度上壓縮事務(wù)集,同時將項集與事務(wù)集的映射存儲在HashMap中,計算支持度時只需計算項集對應(yīng)事務(wù)集的權(quán)重,從而減少事務(wù)數(shù)據(jù)庫的掃描次數(shù)。然后利用MapReduce編程思想開啟多個線程,并行計算候選頻繁集的支持度,從而提高算法的運行效率。

2.2.1 算法描述

原始Apriori算法每計算一次候選集的支持度,都需要遍歷一次原始事務(wù)數(shù)據(jù)庫,因此需要多次掃描原始事務(wù)數(shù)據(jù)庫,當(dāng)數(shù)據(jù)庫較大時,會進行大量的I/O操作,導(dǎo)致算法性能下降。對此,本文采用以下改進方式:

1)遍歷原始事務(wù)數(shù)據(jù)庫,利用HashSet的去重特性來存儲事務(wù)集,并對重復(fù)的事務(wù)進行計數(shù),將其記為該事務(wù)的權(quán)重。當(dāng)事務(wù)列表重復(fù)項較多時,該步驟能大幅壓縮事務(wù)數(shù)據(jù)庫。

2)在遍歷項集時統(tǒng)計當(dāng)前項目(item)對應(yīng)的所有事務(wù)集合(transactions),對事務(wù)集合的權(quán)重進行累加即可快速獲得支持度計數(shù)。

3)在迭代計算n項集對應(yīng)的事務(wù)集時,對組成它的n-1項集對應(yīng)的事務(wù)集直接做交集操作。此處不需要遍歷原始數(shù)據(jù)庫,只對項集對應(yīng)的事務(wù)集合進行操作,從而有效減小了遍歷長度。最后對事務(wù)集合(transactions)的事務(wù)權(quán)重進行累加即可快速獲得支持度計數(shù)。為了提高取交集操作的速度,本文采用數(shù)據(jù)庫視圖的思想,不直接操作原始數(shù)據(jù),而是先生成一個集合視圖,集合視圖是對原始集合的一系列邏輯操作,通過集合視圖可以快速獲取交集是否為空、交集大小是否符合要求等信息。若符合要求,再遍歷集合視圖,這樣可以過濾掉大部分取交集的耗時操作,大幅提升取交集的效率。由于事務(wù)集合采用HashMap存儲,2個集合取交集時,只需遍歷其中一個集合,然后直接通過哈希映射判斷當(dāng)前事務(wù)是否存在另一個集合中,保證取交集的遍歷操作能在Ο(n)的時間復(fù)雜度內(nèi)完成。同時,由于集合視圖只是一系列邏輯運算,因此大幅減少了內(nèi)存占用。

4)哈希函數(shù)的選取。為了避免哈希函數(shù)的沖突,本文使所有項集的每個字符均參與哈希計算,首先將項集轉(zhuǎn)為字符串,然后取其中每個字符的值作累加并左移5位,獲得哈希值,這樣可以盡量避免沖突。同時,為了減少重復(fù)計算,使每個項集緩存計算的哈希值。

5)在每次迭代計算項集的支持度時,開啟多個線程并行計算。并行運算屬于CPU密集型的運算,CPU核數(shù)越多,并行度越高,計算速度越快。并行計算示意圖如圖2所示,Apriori改進算法流程如圖3所示。

圖2 并行計算示意圖

圖3 Apriori改進算法流程

Apriori改進算法描述如下:

算法1Apriori_improve算法

輸入事務(wù)數(shù)據(jù)庫D,最小支持度閾值supmin

輸出所有頻繁集L

1.掃描事務(wù)數(shù)據(jù)庫D,記錄項集C1、事務(wù)集transactionList以及項集到事務(wù)集的映射transMap,同時對重復(fù)事務(wù)T計數(shù),記為權(quán)重w

2.根據(jù)映射transMap以及w,并行計算C1中的項目支持度,得到1-頻繁集L1

3.若L1==?,無頻繁集,算法結(jié)束

4.for(k=2;Lk-1≠?;k++){

5.Ck,transMap=Apriori_gen(Lk-1,transMap);//根據(jù)//k-1頻繁集產(chǎn)生k候選集

6.for each c∈Ck{//開啟多線程并行計算

7.localTrans = transMap.get(c);

8.for each transaction∈localTrans{

9.supportCount+=weightMap.get(transaction) ;

10.}

11.support=supportCount/Len(transactionList)//計算c//的支持度

12.if(support>=supmin){

13.Lk= Lk∪c

14.}

15.}

16.}

17.return L=L∪Lk

Apriori_gen算法的主要功能是對候選頻繁集進行連接和剪枝,描述如下:

算法2Apriori_gen算法

輸入上一次循環(huán)掃描的結(jié)果Lk-1,transMap

輸出候選頻繁集Ck,transMap

1.for each l1∈Lk-1

2.for each l2∈Lk-1

3.if(l1[1]==l2[1]&&…&& l1[k-2]==l2[k-2]&&l1[k-1]==l2[k-1]){

4.c=l1?l2//將只差一項的2個項集連接在一起

5.trans1=transMap.get(l1)

6.trans2=transMap.get(l2)

7.trans=trans1∩trans2

8.transMap.add(c,trans)

9.if 存在c的子集不在Lk-1中//剪枝

10.delete c;

11.else Ck=Ck∪{c}

12.}

13.return Ck

本文提出的Apriori改進算法通過掃描原始事務(wù)數(shù)據(jù)庫,獲取事務(wù)集以及項目到事務(wù)集的映射關(guān)系(Map),并將其存儲在哈希映射(HashMap)中,同時記錄事務(wù)重復(fù)出現(xiàn)的次數(shù)并開啟多個線程,并行計算候選頻繁集的支持度。哈希存儲具有以下優(yōu)勢:

1)自動去重,減少程序運行所需要的空間,降低算法的空間復(fù)雜度。

2)由于改進算法存儲了項目與事務(wù)之間的映射關(guān)系,在計算項目的支持度時,無需重新遍歷原始數(shù)據(jù)庫,只需取對應(yīng)的事務(wù)集并做交集運算即可,有效提高了計算速度。

3)使用哈希運算獲得局部鎖,可以提升算法在計算過程中的并行性能。當(dāng)數(shù)據(jù)庫中重復(fù)的事務(wù)較多時,計算事務(wù)權(quán)重能夠大幅壓縮事務(wù)集,從而提高計算速度。

4)針對關(guān)聯(lián)規(guī)則挖掘問題,對哈希函數(shù)進行優(yōu)化,降低了哈希沖突的概率,同時對已計算出的項集對應(yīng)的哈希值進行緩存,避免了重復(fù)計算。在優(yōu)化取交集運算時,利用數(shù)據(jù)庫視圖的思想,利用集合視圖能夠快速獲取交集是否為空、交集大小是否符合要求等信息,避免了直接操作原始數(shù)據(jù),在大幅減少耗時操作的同時又避免了數(shù)據(jù)的復(fù)制,降低了內(nèi)存的使用。在計算候選集的支持度時,開啟多個線程并行計算支持度,這樣能夠充分發(fā)揮硬件設(shè)備的性能,并且在事務(wù)量足夠大時提高算法的運行效率。

2.2.2 算法分析

本文對并行Apriori改進算法的正確性和運算效率進行理論分析,分析基于以下假設(shè):

事務(wù)數(shù)據(jù)庫為D,項集為I={i1,i2,…,im},項目為ik(k=1,2,…,m),事務(wù)為T,事務(wù)個數(shù)為|D|,事務(wù)權(quán)重為w={w1,w2,…,wm},其中,Ti的權(quán)重為wi,重復(fù)事務(wù)數(shù)與總事務(wù)數(shù)的比值記為重復(fù)率δ,T=w1T1+w2T2+…+wmTm,關(guān)聯(lián)規(guī)則R:X?Y,其中,X?I,Y?I,且X∩Y=?。

對于項集X,X?I,X的支持度為:

(5)

關(guān)聯(lián)規(guī)則R:X?Y的支持度為:

(6)

關(guān)聯(lián)規(guī)則R:X?Y的可信度為:

(7)

Apriori改進算法的正確性得證。

傳統(tǒng)Apriori算法總的訪問次數(shù)為:

(8)

因此,傳統(tǒng)Apriori算法的時間復(fù)雜度為O(mq2nb)。

Apriori改進算法的總訪問次數(shù)為:

(9)

根據(jù)以上分析可以看出,本文提出的Apriori改進算法比原始Apriori算法效率至少提高(1-δ)p2倍,且重復(fù)事務(wù)越多,并行度越高,效率提升效果越明顯。

2.2.3 Apriori改進算法的應(yīng)用框架

在解決實際的數(shù)據(jù)挖掘問題時,先要對歷史數(shù)據(jù)進行預(yù)處理以及特征提取,然后利用本文提出的Apriori改進算法對訓(xùn)練數(shù)據(jù)實現(xiàn)關(guān)聯(lián)規(guī)則挖掘,找出頻繁集,建立規(guī)則庫,最后將待測數(shù)據(jù)與規(guī)則庫中的規(guī)則進行模式匹配,并根據(jù)新信息動態(tài)更新所建立的模型。Apriori改進算法的總體應(yīng)用框架如圖4所示。

圖4 Apriori改進算法的應(yīng)用框架

3 實驗分析與驗證

本文通過實驗來驗證Apriori改進算法的有效性,實驗數(shù)據(jù)集采用360日志數(shù)據(jù),該數(shù)據(jù)集是2019年奇虎360公司舉辦的網(wǎng)絡(luò)攻防比賽所用數(shù)據(jù),其中的日志數(shù)據(jù)包括Web警告信息、IP基礎(chǔ)信息、日常訪問行為信息和終端行為信息等多個維度的網(wǎng)絡(luò)行為數(shù)據(jù)。360日志數(shù)據(jù)集共包含2018年12月份31天的日志信息,每天的日志信息量大小為11.0 M～1.7 G。實驗環(huán)境:處理器為Intel?Core i7-9700K 3.60 GHz 8核,內(nèi)存為32 GB,硬盤為1 T,操作系統(tǒng)為Ubuntu 18.04.3 LTS,運行環(huán)境為JDK 13。

為了驗證本文所提算法的時間復(fù)雜度和空間復(fù)雜度,選取數(shù)據(jù)集中某5天的日志數(shù)據(jù),使用傳統(tǒng)Apriori算法、FP-Growth算法和本文Apriori改進算法對實驗數(shù)據(jù)進行關(guān)聯(lián)規(guī)則挖掘,并統(tǒng)計和比較以上算法的運行時間和內(nèi)存占用情況,結(jié)果如圖5、圖6所示。

圖5 不同數(shù)據(jù)集大小下的算法運行時間對比

圖6 不同數(shù)據(jù)集大小下的算法內(nèi)存占用對比

圖5、圖6所示分別為最小支持度為0.15、改進Apriori算法線程數(shù)為8時,不同事務(wù)數(shù)情況下3種算法運行時間和內(nèi)存占用的對比情況。從中可以看出,相較于傳統(tǒng)Apriori算法,本文Apriori改進算法性能提升明顯。在算法運行時間上,Apriori改進算法取得了與FP-Growth算法相近的效果,同時又避免了FP-Growth算法內(nèi)存占用過大的問題。FP-Growth算法需要遞歸生成條件FP-tree,內(nèi)存開銷較大,本文Apriori改進算法采用哈希存儲與集合視圖相結(jié)合的改進方案,有效降低了算法的內(nèi)存開銷。

為了驗證本文所提算法的穩(wěn)定性并探究并行度對該算法的影響,針對不同的支持度和并行度進行實驗,并統(tǒng)計和對比算法的運行時間,結(jié)果如圖7、圖8所示。

圖7 不同支持度下的算法運行時間對比

圖8 不同并行度下的算法運行時間

圖7所示為數(shù)據(jù)集大小為11 M、最小支持度分別取0.02～0.30情況下算法的運行時間對比情況。從圖7可以看出,支持度越小,挖掘頻繁項集所需時間越長,相較于傳統(tǒng)Apriori算法,本文Apriori改進算法的運行時間隨支持度的變化幅度較小,算法較為穩(wěn)定。

圖8所示為數(shù)據(jù)集大小為91 M、最小支持度設(shè)置為0.15時改進算法的運行時間隨并行度的變化情況。從圖8可以看出,在線程數(shù)小于8時,Apriori改進算法的運行時間隨并行度的增加而降低,在線程數(shù)為8時,Apriori改進算法的運行效率達到最優(yōu),在線程數(shù)大于8時,Apriori改進算法的運行效率基本保持平穩(wěn)狀態(tài)。

4 結(jié)束語

本文針對傳統(tǒng)Apriori算法運行效率低的問題,提出一種基于哈希存儲與事務(wù)加權(quán)的并行Apriori改進算法。利用哈希存儲減少對原始事務(wù)數(shù)據(jù)庫的掃描次數(shù),記錄事務(wù)的權(quán)重,對事務(wù)進行去重和壓縮,并通過記錄項目所在事務(wù)的ID建立映射關(guān)系,從而減少冗余計算。開啟多個線程,并行計算候選頻繁集的支持度,使硬件設(shè)備的性能得到充分發(fā)揮,從而提升算法的運行效率。選取360網(wǎng)絡(luò)攻防大賽數(shù)據(jù)集進行驗證,結(jié)果表明,該算法能夠大幅降低關(guān)聯(lián)規(guī)則挖掘所需的時間以及內(nèi)存占用,有效提升傳統(tǒng)Apriori算法的性能,在運行時間上取得與FP-Growth算法相近效果的同時又避免了FP-Growth算法內(nèi)存占用過大的問題,在處理海量數(shù)據(jù)時,該算法能夠大幅降低設(shè)備成本。

相較于分布式并行計算框架,本文并行Apriori改進算法更加輕量,易于移植,可擴展性較高,但并行計算所帶來的性能提升受限于硬件設(shè)備CPU的核數(shù),且線程數(shù)并非越多越好,線程切換會導(dǎo)致一定的時間開銷。下一步將在硬件條件一定的情況下研究最佳并行度的確定方法,以提升本文算法的性能。