基于哈希存儲(chǔ)與事務(wù)加權(quán)的并行Apriori改進(jìn)算法

李 潔,朱洪亮,陳玉玲,辛 陽(yáng)

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

0 概述

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

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

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

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

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

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

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

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

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

2 并行Apriori改進(jìn)算法

2.1 傳統(tǒng)Apriori算法

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

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

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

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

(1)

4)項(xiàng)集的最小支持度和頻繁集。在查找關(guān)聯(lián)規(guī)則的過(guò)程中,項(xiàng)集要滿足一個(gè)指定的支持度閾值,這個(gè)指定的支持度閾值就是項(xiàng)集的最小支持度,記為supmin。當(dāng)一個(gè)項(xiàng)集的支持度不低于supmin時(shí),稱該項(xiàng)集為頻繁項(xiàng)集,即頻繁集;不滿足此條件的項(xiàng)集,稱為非頻繁集。k-項(xiàng)集的支持度若不低于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)一個(gè)事務(wù)中出現(xiàn)X時(shí),在某一概率下該事務(wù)中也會(huì)出現(xiàn)Y。本文稱X為規(guī)則R的條件,Y為規(guī)則R的結(jié)果。關(guān)聯(lián)規(guī)則R:X?Y反映了如下規(guī)律:當(dāng)X中的項(xiàng)目出現(xiàn)時(shí),Y中的項(xiàng)目也會(huì)隨之出現(xiàn)。

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

(3)

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

(4)

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

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

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

2.2 Apriori算法改進(jìn)

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

2.2.1 算法描述

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

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

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

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

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

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

圖2 并行計(jì)算示意圖

圖3 Apriori改進(jìn)算法流程

Apriori改進(jìn)算法描述如下:

算法1Apriori_improve算法

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

輸出所有頻繁集L

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

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

3.若L1==?,無(wú)頻繁集,算法結(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{//開啟多線程并行計(jì)算

7.localTrans = transMap.get(c);

8.for each transaction∈localTrans{

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

10.}

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

12.if(support>=supmin){

13.Lk= Lk∪c

14.}

15.}

16.}

17.return L=L∪Lk

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

算法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//將只差一項(xiàng)的2個(gè)項(xiàng)集連接在一起

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

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

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

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

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

2.2.2 算法分析

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

事務(wù)數(shù)據(jù)庫(kù)為D,項(xiàng)集為I={i1,i2,…,im},項(xiàng)目為ik(k=1,2,…,m),事務(wù)為T,事務(wù)個(gè)數(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=?。

對(duì)于項(xiàng)集X,X?I,X的支持度為:

(5)

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

(6)

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

(7)

Apriori改進(jìn)算法的正確性得證。

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

(8)

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

Apriori改進(jìn)算法的總訪問(wèn)次數(shù)為:

(9)

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

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

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

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

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

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

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

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

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

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

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

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

圖8 不同并行度下的算法運(yùn)行時(shí)間

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

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

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

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

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