基于鄰接表存儲(chǔ)與哈希表的頻繁項(xiàng)集挖掘算法

吳 昊 劉 釗 顧進(jìn)廣

(武漢科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 湖北 武漢 430065)(武漢科技大學(xué)大數(shù)據(jù)科學(xué)與工程研究院 湖北 武漢 430065)(湖北省智能信息處理與實(shí)時(shí)工業(yè)系統(tǒng)重點(diǎn)實(shí)驗(yàn)室 湖北 武漢 430065)

0 引 言

頻繁項(xiàng)集[1]是從數(shù)據(jù)資源中挖掘具有潛在價(jià)值的信息,頻繁項(xiàng)挖掘的經(jīng)典算法是Apriori算法,但是該算法存在明顯的不足:算法的計(jì)算時(shí)間花費(fèi)較大和內(nèi)存空間占用較高。近年來(lái),研究者們根據(jù)Apriori算法不足之處提出了改進(jìn)方法。例如,文獻(xiàn)[2]提出了利用數(shù)據(jù)結(jié)構(gòu)優(yōu)化預(yù)剪枝步驟,結(jié)合Spark支持的細(xì)粒度計(jì)算模型的特征,將事務(wù)數(shù)據(jù)庫(kù)水平劃分為n個(gè)塊,分配到m個(gè)節(jié)點(diǎn),在m個(gè)節(jié)點(diǎn)上運(yùn)行IAP算法n次,找到所有頻繁項(xiàng)集,利用剪枝的方法有效地減少了頻繁項(xiàng)集的挖掘時(shí)間,但是每個(gè)節(jié)點(diǎn)的運(yùn)行時(shí)間由數(shù)據(jù)塊上的節(jié)點(diǎn)數(shù)決定。文獻(xiàn)[3]提出了一種改進(jìn)的DC-Apriori算法,該算法重構(gòu)了數(shù)據(jù)庫(kù)的存儲(chǔ)結(jié)構(gòu),簡(jiǎn)化了項(xiàng)集的連接過(guò)程,僅需將1個(gè)頻繁項(xiàng)目集與k-1個(gè)頻繁項(xiàng)目集結(jié)合即可生成k個(gè)頻繁項(xiàng)目集,從而大大地減少了連接數(shù),只需一次修剪即可直接獲取頻繁項(xiàng)集,減少了無(wú)效的候選項(xiàng)集計(jì)算,較好地提高了頻繁項(xiàng)集的生成效率。雖然該算法減少了數(shù)據(jù)的連接次數(shù),但是仍然需要對(duì)進(jìn)數(shù)據(jù)庫(kù)進(jìn)行多次掃描,運(yùn)算過(guò)程比較復(fù)雜。文獻(xiàn)[4]提出了一種基于MapReduce并行處理的頻繁項(xiàng)集挖掘方法,使用Hadoop云計(jì)算框架作為數(shù)據(jù)挖掘平臺(tái),引入了矩陣模型并結(jié)合MapReduce模型來(lái)實(shí)現(xiàn)并行化改進(jìn)Apriori算法,從而縮短算法的運(yùn)行時(shí)間。該算法在處理海量數(shù)據(jù)集時(shí)具有良好的效率和擴(kuò)展性,但是該算法通常運(yùn)行在集群中,需要強(qiáng)大的計(jì)算和存儲(chǔ)能力支撐。曹瑩等[5]提出了一種改進(jìn)Apriori算法,該算法采用事務(wù)數(shù)據(jù)向量矩陣與行候選向量相結(jié)合的優(yōu)化方法,減少生成冗余的候選項(xiàng)集,優(yōu)化了候選項(xiàng)集計(jì)算過(guò)程,減少事務(wù)數(shù)據(jù)向量的存儲(chǔ)量和項(xiàng)集之間的比較次數(shù),提高頻繁項(xiàng)集的挖掘效率。文武等[6]提出了一種結(jié)合遺傳算法的Apriori算法搜索頻繁項(xiàng)集,利用Apriori算法和遺傳算法的特點(diǎn),利用交叉計(jì)算產(chǎn)生候選項(xiàng)集和變異算法篩選頻繁項(xiàng)集,減少了冗余項(xiàng)集,較好地提高搜索效率。趙學(xué)健等[7]提出了一種利用正交鏈表存儲(chǔ)數(shù)據(jù)所對(duì)應(yīng)的關(guān)系矩陣,克服了多次掃描數(shù)據(jù)庫(kù)的缺點(diǎn),同時(shí)優(yōu)化了傳統(tǒng)的Apriori算法的自連接和剪枝過(guò)程,但是該算法需要利用正交鏈表存儲(chǔ)數(shù)據(jù)庫(kù)中的數(shù)據(jù),因此對(duì)數(shù)據(jù)的處理量受限于主存空間。

本文提出一種基于鄰接表存儲(chǔ)與哈希表的頻繁項(xiàng)集挖掘算法(ATSAHT-Apriori算法)。該算法利用哈希表的特性,將數(shù)據(jù)庫(kù)中的數(shù)據(jù)進(jìn)行處理,將數(shù)據(jù)全部轉(zhuǎn)化為哈希表進(jìn)行映射,在后續(xù)計(jì)算項(xiàng)集支持度頻數(shù)的時(shí)候不必進(jìn)行數(shù)據(jù)與項(xiàng)集自匹配的過(guò)程,由于只需要在哈希表中進(jìn)行查找來(lái)計(jì)算項(xiàng)集支持度頻數(shù)[7],極大地減少了每一輪項(xiàng)集支持度頻數(shù)的計(jì)算時(shí)間。由于只需要對(duì)數(shù)據(jù)庫(kù)中的數(shù)據(jù)掃描一次存在哈希表中,極大地減少了I/O的時(shí)間開銷與負(fù)載。同時(shí),結(jié)合圖存儲(chǔ)的思想利用鄰接表來(lái)存儲(chǔ)項(xiàng)集,有效地優(yōu)化了存儲(chǔ)項(xiàng)集的內(nèi)存空間占用,在計(jì)算候選項(xiàng)集的過(guò)程中,利用堆排序的思想構(gòu)建大根堆和動(dòng)態(tài)剪枝的思想減少了冗余項(xiàng)集的計(jì)算,進(jìn)一步優(yōu)化了算法執(zhí)行時(shí)間和內(nèi)存空間占用。

1 Apriori預(yù)測(cè)算法簡(jiǎn)介

Apriori算法是基于一種迭代計(jì)算搜索的方式,同時(shí)利用頻繁k項(xiàng)集的自連接來(lái)擴(kuò)展生成(k+1)項(xiàng)集,首先獲取頻繁1項(xiàng)集(簡(jiǎn)稱C1),然后通過(guò)C1自連接擴(kuò)展生成候選2項(xiàng)集(簡(jiǎn)稱C2),然后通過(guò)候選2項(xiàng)集擴(kuò)展生成頻繁3項(xiàng)集(簡(jiǎn)稱C3),一直迭代下去,直到不能繼續(xù)擴(kuò)展生成下一項(xiàng)頻繁項(xiàng)集,該迭代方法結(jié)束[8]。

由上述步驟可以看出Apriori算法的不足之處:

1) 數(shù)據(jù)預(yù)處理后,每生成一個(gè)候選項(xiàng)集時(shí),對(duì)數(shù)據(jù)庫(kù)每一條數(shù)據(jù)進(jìn)行多次掃描,當(dāng)計(jì)算各候選k(k=1,2,…,n)項(xiàng)集的支持度頻數(shù),至少要掃描n次數(shù)據(jù)庫(kù)中的數(shù)據(jù),多次訪問(wèn)數(shù)據(jù)庫(kù)將會(huì)造成I/O上有較大時(shí)間開銷與負(fù)載,消耗大量的時(shí)間[9]。

2) Apriori算法在擴(kuò)展下一項(xiàng)的過(guò)程中掃描數(shù)據(jù)庫(kù)中都會(huì)因?yàn)轫?xiàng)集自連接而產(chǎn)生大量冗余的候選項(xiàng)集。例如頻繁k項(xiàng)集經(jīng)過(guò)自連接擴(kuò)展生成所有候選k+1項(xiàng)集Ck+1,就需要進(jìn)行多次自連接,生成的候選項(xiàng)集與最小支持度比較次數(shù)增多,消耗了大量計(jì)算時(shí)間。項(xiàng)集個(gè)數(shù)為n的頻繁項(xiàng)集Lk,其生成頻繁k項(xiàng)集時(shí)間復(fù)雜度為O(k×n2),在此過(guò)程中生成的冗余數(shù)據(jù)占用了大量的內(nèi)存空間[10]。

3) 在頻繁項(xiàng)集進(jìn)行擴(kuò)展生成下一項(xiàng)時(shí),測(cè)試C(C∈Ck)里每個(gè)(k-1)項(xiàng)集是否是Lk-1中的頻繁(k-1)項(xiàng)集,需要掃描[1,k]次Lk-1,對(duì)于Lk-1掃描的時(shí)間復(fù)雜度為O(k×|Lk-1|/2),所以對(duì)每一個(gè)候選k項(xiàng)集Ck掃描時(shí)間復(fù)雜度為O(|Ck|×k×|Lk-1|/2),在計(jì)算過(guò)程中需要消耗大量時(shí)間[11]。

根據(jù)上述Apriori算法在時(shí)間復(fù)雜度和空間復(fù)雜度的不足,本文提出一種ATSAHT-Apriori算法進(jìn)行優(yōu)化。

2 ATSAHT-Apriori挖掘算法

2.1 ATSAHT-Apriori算法描述

鄰接表[12](Adjacency List)就是把從同一個(gè)頂點(diǎn)出發(fā)到達(dá)的相鄰節(jié)點(diǎn)的點(diǎn)和邊連接在同一個(gè)單鏈表中,單鏈表的每個(gè)節(jié)點(diǎn)代表一條邊,稱為邊節(jié)點(diǎn)。每個(gè)邊節(jié)點(diǎn)有三個(gè)域:該起點(diǎn)項(xiàng)集對(duì)應(yīng)終點(diǎn)的項(xiàng)集,起點(diǎn)項(xiàng)集與終點(diǎn)項(xiàng)集進(jìn)行交集后的項(xiàng)集與項(xiàng)集頻數(shù),以及指向下一個(gè)邊節(jié)點(diǎn)的指針。在鄰接表中,還需要一個(gè)用于存儲(chǔ)頂點(diǎn)信息的頂點(diǎn)數(shù)組。

結(jié)合鄰接表存儲(chǔ)的圖節(jié)點(diǎn)的思想(關(guān)聯(lián)項(xiàng)集如圖1所示,邊的權(quán)重表示兩點(diǎn)項(xiàng)集的支持度頻數(shù)),鄰接表中節(jié)點(diǎn)屬性(如圖2所示),利用鄰接表存儲(chǔ)頻繁項(xiàng)集[13](如圖3所示)。

圖1 關(guān)聯(lián)項(xiàng)集

圖2 鏈表節(jié)點(diǎn)屬性

圖3 關(guān)聯(lián)項(xiàng)集的鄰接表

定義1假定候選項(xiàng)集F=(X1,X2,…,Xn),項(xiàng)集F中的Xi在哈希表Hash=(H1,H2,…,Hn)中的第j(j=1,2,…,n)行中都能通過(guò)哈希表找到,證明F中的Xi全部存在于哈希表Hash第j(j=1,2,…,n)行中則候選項(xiàng)集F=(X1,X2,…,Xn)對(duì)應(yīng)的支持度頻數(shù)計(jì)數(shù)加1。

定義2如果集合A=(X1,X2,…,Xm)的頻數(shù)小于最小支持度頻數(shù),則A集合是非頻繁項(xiàng)集,如果A?B,可以判斷B=(X1,X2,…,Xm,…,Xn)是非頻繁項(xiàng)集[14]。

定義3如果A=(X1,X2,…,Xm,…,Xn)集合的頻數(shù)大于最小支持度頻數(shù),可以判斷A是頻繁項(xiàng)集,如果B?A,則集合B=(X1,X2,…,Xm)所有子集合都是頻繁項(xiàng)集[14]。

推論1假設(shè)頻繁k項(xiàng)集的集合數(shù)量記為|Lk|,如果|Lk|

2.2 算法的優(yōu)化方法

ATSAHT-Apriori算法通過(guò)以下方法進(jìn)行優(yōu)化:

1) 本文提出一種哈希表存儲(chǔ)方式來(lái)存儲(chǔ)數(shù)據(jù),即把數(shù)據(jù)庫(kù)中的數(shù)據(jù)預(yù)處理后,存儲(chǔ)在哈希表中,然后在哈希表中進(jìn)行計(jì)算項(xiàng)集支持度頻數(shù),利用哈希表存儲(chǔ)的方法就僅需要掃描一次數(shù)據(jù),在后續(xù)的過(guò)程中極大地減少了I/O的時(shí)間開銷與負(fù)載。

2) 在哈希表中,假設(shè)數(shù)據(jù)有m行,每個(gè)候選項(xiàng)集有n個(gè)事務(wù),根據(jù)定義1,利用哈希表進(jìn)行計(jì)算候選項(xiàng)集支持度頻數(shù),在哈希表中進(jìn)行查找,如果候選項(xiàng)集Q=(X1,X2,…,Xn)中每個(gè)項(xiàng)集都能夠在該條數(shù)據(jù)的哈希表的第j(j=0,1,…,n)行中找到,該項(xiàng)集對(duì)應(yīng)的支持度頻數(shù)計(jì)數(shù)加1,因此候選項(xiàng)集中的每個(gè)事務(wù)利用哈希表查找單個(gè)項(xiàng)集所需要的時(shí)間復(fù)雜度為O(1),則查找Q=(X1,X2,…,Xn)項(xiàng)集所需要時(shí)間需要O(n),所需要的時(shí)間遠(yuǎn)遠(yuǎn)小于數(shù)據(jù)之間進(jìn)行逐個(gè)匹配以及計(jì)算項(xiàng)集頻繁的時(shí)間,優(yōu)化了計(jì)算項(xiàng)集支持度頻數(shù)的運(yùn)算過(guò)程,極大地優(yōu)化了計(jì)算過(guò)程。

3) 將每輪交叉連接生成的項(xiàng)集進(jìn)行判斷,利用哈希表的特性同時(shí)結(jié)合定義2和定義3,進(jìn)行動(dòng)態(tài)剪枝,減少了冗余項(xiàng)集的存儲(chǔ)和計(jì)算過(guò)程,優(yōu)化了計(jì)算過(guò)程,優(yōu)化了項(xiàng)集的內(nèi)存占用空間。

4) 利用哈希表可以判斷在當(dāng)前輪已經(jīng)計(jì)算的項(xiàng)集,將當(dāng)前輪已經(jīng)生成的項(xiàng)集及項(xiàng)集支持度頻數(shù)存入到哈希表中,在后面的計(jì)算中,就可以利用哈希表進(jìn)行判斷,如果該項(xiàng)集已經(jīng)計(jì)算過(guò),不需要重復(fù)計(jì)算,減少了存儲(chǔ)冗余項(xiàng)集的計(jì)算時(shí)間。

5) 利用圖存儲(chǔ)的思想,利用鄰接表存儲(chǔ)兩點(diǎn)項(xiàng)集生成的候選項(xiàng)集,利用定義2與定義3,結(jié)合哈希表對(duì)當(dāng)前輪的項(xiàng)集進(jìn)行動(dòng)態(tài)剪枝與去除重復(fù)項(xiàng)集,將篩選后的候選項(xiàng)集存儲(chǔ)在鄰接表中,極大地優(yōu)化了內(nèi)存空間。

6) 當(dāng)前輪計(jì)算結(jié)束后,利用堆排序思想構(gòu)建大根堆,將候選項(xiàng)集插入大根堆中進(jìn)行排序,每次刪除大根堆中支持度頻數(shù)最大的項(xiàng)集,并將該項(xiàng)集插入新的鄰接表中,當(dāng)大根堆中最大元素不滿足最小支持度后,堆排序結(jié)束,剩余的不符合要求的項(xiàng)集不需要排序,將剩余項(xiàng)集存儲(chǔ)非頻繁項(xiàng)集集合中,為計(jì)算下一輪項(xiàng)集優(yōu)化了存儲(chǔ)空間。

3 ATSAHT-Apriori算法的優(yōu)化

基于前面的定義和推論,算法優(yōu)化具體步驟如下:

1) 首先掃描數(shù)據(jù)庫(kù),對(duì)數(shù)據(jù)庫(kù)中的數(shù)據(jù)進(jìn)行預(yù)處理(假設(shè)數(shù)據(jù)庫(kù)數(shù)據(jù)為N條,最小支持度為Min_Sup,由此可以計(jì)算出最小支持度頻數(shù)為Min_sup_Count=N×Min_Sup),按照字母首位進(jìn)行排序,并且將數(shù)據(jù)以鍵-值對(duì)映射的方式存儲(chǔ)在哈希表Hash_Total中,只需要遍歷一次數(shù)據(jù)庫(kù)中的數(shù)據(jù),就可以將數(shù)據(jù)存儲(chǔ)到哈希表Hash_Total中,在后續(xù)的過(guò)程中需要在哈希表Hash_Total中進(jìn)行計(jì)算項(xiàng)集支持度頻數(shù),因此不需要多次訪問(wèn)數(shù)據(jù)庫(kù)中的數(shù)據(jù),減少了訪問(wèn)數(shù)據(jù)庫(kù)次數(shù),降低了I/O方面的時(shí)間開銷與負(fù)載,然后遍歷哈希表計(jì)算出每一項(xiàng)的事務(wù)頻數(shù),得到候選1項(xiàng)集(簡(jiǎn)稱C1)。

2) 對(duì)于步驟1)得到的C1,遍歷C1中所有項(xiàng)集,對(duì)于不滿足最小支持度頻數(shù)的項(xiàng)集直接存入集合res(res存儲(chǔ)非頻繁項(xiàng)集),事務(wù)頻數(shù)滿足最小支持度頻數(shù)的項(xiàng)集直接存入集合V1(Vi(i=1,2,…)存儲(chǔ)頻繁項(xiàng)集),此時(shí)生成頻繁1項(xiàng)集L1(假設(shè)L1中數(shù)量為n),將L1的2到n項(xiàng)與L1的1到n-1項(xiàng)進(jìn)行交叉連接取并集可以擴(kuò)展生成2項(xiàng)集。

3) 根據(jù)推論1,如果|Lk|≥k+1,可以繼續(xù)擴(kuò)展下一項(xiàng),此時(shí)利用L1[i]和L1[j]的項(xiàng)集交叉連接進(jìn)行取并集生成新的項(xiàng)集flag,首先判斷flag是否在哈希表Hash_Item出現(xiàn),如果該項(xiàng)集存在哈希表Hash_Item中,則不需要進(jìn)行計(jì)算該項(xiàng)集頻數(shù),直接進(jìn)行該輪下一個(gè)項(xiàng)集計(jì)算,反之,進(jìn)行下一步計(jì)算:如果flag是集合Vi(Vi存儲(chǔ)頻繁i(i=1,2,…,k)項(xiàng)集)項(xiàng)集中的子集,根據(jù)定義3進(jìn)行動(dòng)態(tài)剪枝,則不需計(jì)算該項(xiàng)集頻數(shù),同時(shí)將項(xiàng)集flag中對(duì)應(yīng)的支持度頻數(shù)設(shè)置為Min_sup_Count,并進(jìn)行該輪下一個(gè)項(xiàng)集計(jì)算,反之,繼續(xù)下一步計(jì)算,如果flag是res中項(xiàng)集(res集合存儲(chǔ)非頻繁項(xiàng)集)的子集,根據(jù)定義2利用哈希表進(jìn)行動(dòng)態(tài)剪枝,則不需要進(jìn)行計(jì)算該項(xiàng)集支持度頻數(shù),直接進(jìn)行當(dāng)前輪下一個(gè)項(xiàng)集計(jì)算,反之,繼續(xù)進(jìn)行下一步,遍歷該項(xiàng)集中每一個(gè)事務(wù),在哈希表Hash_Total中進(jìn)行查找,時(shí)間復(fù)雜度為O(1),根據(jù)定義1可知,如果該輪項(xiàng)集在哈希表Hash_Total中第i行(i=1,2,…,n)都找到的話,該項(xiàng)集的支持度頻數(shù)計(jì)數(shù)加1,遍歷哈希表Hash_Total中的每一行,重復(fù)定義1的步驟,就可以計(jì)算該項(xiàng)集對(duì)應(yīng)的支持度頻數(shù),計(jì)算該項(xiàng)集支持度頻數(shù)結(jié)束后,利用哈希表Hash_Item(key表示該項(xiàng)集,value對(duì)應(yīng)項(xiàng)集頻數(shù))鍵-值對(duì)存儲(chǔ)此次計(jì)算的項(xiàng)集與項(xiàng)集頻數(shù),每一次計(jì)算項(xiàng)集支持度頻數(shù)結(jié)束后,就將項(xiàng)集插入到鄰接表中,此輪遍歷結(jié)束就可以生成候選2項(xiàng)集鄰接表,將一維列表ansk(k=2)遍歷鄰接表,并存儲(chǔ)鄰接表中的每一個(gè)節(jié)點(diǎn),然后利用堆排序的思想對(duì)ansk進(jìn)行部分堆排序[13],構(gòu)建大根堆(遞減排序出項(xiàng)集頻數(shù)滿足最小支持度的項(xiàng)集,其余的項(xiàng)集為非頻繁項(xiàng)集不需要進(jìn)行排序,將頻繁項(xiàng)集存儲(chǔ)在Vi(i=2)中,非頻繁項(xiàng)集存儲(chǔ)在res中,就計(jì)算得到了頻繁2項(xiàng)集L2。

4) 通過(guò)推論1判斷,如果|Lk|≥k+1,說(shuō)明利用Lk中的頻繁項(xiàng)集可以計(jì)算(k+1)項(xiàng),重復(fù)步驟2)和步驟3)中求下一項(xiàng)頻繁項(xiàng)集的過(guò)程,并且通過(guò)頻繁k項(xiàng)集來(lái)繼續(xù)擴(kuò)展第k+1項(xiàng)的頻繁項(xiàng)集。

5) 重復(fù)循環(huán)步驟4),利用推論1,直到第k項(xiàng)頻繁項(xiàng)集的數(shù)量小于k+1,就表明無(wú)法進(jìn)行下一層尋找更多的頻繁項(xiàng)集,查找頻繁項(xiàng)集算法結(jié)束。

ATSAHT-Apriori算法核心的偽代碼描述如下:

ATSAHT-Apriori (){

將Database每條數(shù)據(jù)中的事務(wù)映射存入哈希表Hash_Total中(N表示有N行哈希表);

/*定義存儲(chǔ)候選集列表ansk(k=1,2,…)表示第k項(xiàng)集,ansk[i](i=1,2,…,M)表示k項(xiàng)集中的矩陣的第i個(gè)事務(wù)(ansk[i].count表示k項(xiàng)集的第i個(gè)事務(wù)的支持度頻數(shù),初始化為0),Vk(k=1,2,…)存儲(chǔ)第k項(xiàng)頻繁項(xiàng)集,res存儲(chǔ)所有非頻繁項(xiàng)集。*/

FOR(i=0;i

WHILE遍歷哈希表Hash_Total[i].items():

ans1[Hash_Total[i].key].count++;

//對(duì)事務(wù)進(jìn)行計(jì)數(shù)

END FOR

FOR(i=0;i

IF(ans1[i].count>=Min_sup_Count)

V1.append({ans1[i].key:ans1[i].count});

//將頻繁項(xiàng)集存入V1

ELSE

res.append({ans1[i].key:ans1[i].count});

//將非頻繁項(xiàng)集存入res中

END FOR

FOR(k=2;|Vk-1|.length()>=k+1;k++)

M=dict();

//定義新的哈希表

FOR(i=1;i<|Vk-1|.length()-1;i++) DO

p=Vk-1[i].key;

//表示k-1項(xiàng)集中第i行事務(wù)

FOR(j=i+1;j<|Vk-1|.length();j++) DO

q=Vk-1[j].key;

//表示k-1項(xiàng)集中第j列事務(wù)

/*p∪q表示交叉連接取的項(xiàng)集賦值給flag */

flag=p∪q;

IF 哈希表Hash_Item出現(xiàn)過(guò)flag

/*不用重復(fù)計(jì)算,計(jì)算下一個(gè)項(xiàng)集*/

Continue;

IF flag是Vk中的子集

/*根據(jù)定義4判斷,直接設(shè)置為最小支持度,計(jì)算下一個(gè)項(xiàng)集*/

M[flag]=Min_sup_Count;

Continue;

IF flag是res中的子集

/*根據(jù)定義3判斷,繼續(xù)計(jì)算下一項(xiàng)集*/

Continue;

FOR(p=0;p

/*計(jì)算項(xiàng)集頻數(shù)*/

//遍歷哈希表Hash_Total,N表示哈希表行數(shù)

FOR(h=0;h

//遍歷項(xiàng)集flag中的每一項(xiàng)事務(wù)。

IF Hash_Total[p][flag[0-->flag.length()-1]]存在

//根據(jù)定義2,計(jì)算每個(gè)候選項(xiàng)集頻數(shù)

//flag所有事務(wù)在第p行哈希表中能找到

M[flag]++;

/*項(xiàng)集計(jì)數(shù)*/

END FOR

END FOR

/*哈希表Hash_Item(Hash_Item的key表示項(xiàng)集,value對(duì)應(yīng)項(xiàng)集頻數(shù))對(duì)來(lái)存儲(chǔ)項(xiàng)集與頻數(shù)。*/

Hash_Item[flag]=M[flag];

將(q=Vk-1[j].key,M[flag])插入p=Vk-1[i].key的鄰接表中,鏈表尾端設(shè)置為NULL;

END FOR

END FOR

遍歷當(dāng)前輪的鄰接表,將每一個(gè)項(xiàng)集及對(duì)應(yīng)的頻數(shù)存儲(chǔ)在一維列表ansk中;

fre_item,unfre_item=ATSAHTApriori_Sort(ansk);

/*對(duì)項(xiàng)集頻數(shù)構(gòu)建大根堆排序。篩選出符合最小支持度的前k個(gè)項(xiàng)集,不符合條件的項(xiàng)集不用排序*/

Vk.insert({fre_item.key:fre_item.count});

res.insert({unfre_item.key:unfre_item.count});

END FOR}

ATSAHT-Apriori_Sort(ansk){

/*以頻繁項(xiàng)集的數(shù)量為標(biāo)準(zhǔn),用堆排序思想構(gòu)造大根堆進(jìn)行排序*/

調(diào)用堆排序算法進(jìn)行部分排序[13]

//fre_item為頻繁項(xiàng)集,unfre_item為非頻繁項(xiàng)集

fre_item,unfre_item=heap_Sort(ansk);}

4 ATSAHT-Apriori算法的優(yōu)化驗(yàn)證

假設(shè)最小支持度為0.4,經(jīng)過(guò)數(shù)據(jù)預(yù)處理之后有效數(shù)據(jù)數(shù)量有10條(如表1所列),就可以計(jì)算出最小支持度頻數(shù)為4,即min_support_count為4。

表1 數(shù)據(jù)庫(kù)數(shù)據(jù)

1) 首先對(duì)數(shù)據(jù)進(jìn)行預(yù)處理,然后將數(shù)據(jù)庫(kù)中有效數(shù)據(jù)存儲(chǔ)到哈希表Hash_Total中(見(jiàn)表2)。

表2 數(shù)據(jù)對(duì)應(yīng)的哈希表

2) 計(jì)算哈希表Hash_Total中每個(gè)事務(wù)對(duì)應(yīng)的支持度頻數(shù),計(jì)算之后可以得到候選1項(xiàng)集以及支持度頻數(shù)(見(jiàn)表3),將該項(xiàng)集支持度頻數(shù)構(gòu)建大根堆,并且利用堆排序的思想對(duì)部分項(xiàng)集頻數(shù)進(jìn)行遞減排序(對(duì)于項(xiàng)集對(duì)應(yīng)的支持度頻數(shù)如果相同,則按照名稱的首字符遞增排序,只需要將符合最小支持度的項(xiàng)集進(jìn)行排序),篩選之后就得到頻繁1項(xiàng)集L1=[[A4],[A5],[A2],[A7],[A8],[A9],[A1]],如表4所示。對(duì)上述計(jì)算出來(lái)的頻繁1項(xiàng)集(L1),可以計(jì)算出頻繁1項(xiàng)集對(duì)應(yīng)長(zhǎng)度|L1|=7≥k+1,同時(shí)利用L1構(gòu)建候選2項(xiàng)集鄰接表用來(lái)存儲(chǔ)候選2項(xiàng)集,根據(jù)推論1可以得出,可以利用L1繼續(xù)擴(kuò)展候選2項(xiàng)集(候選2項(xiàng)集鄰接表如圖4所示),把L1的項(xiàng)集進(jìn)行交叉連接取并集,就可以擴(kuò)展生成出有效的候選2項(xiàng)集,然后利用哈希表Hash_Total就可以計(jì)算出項(xiàng)集對(duì)應(yīng)的支持度頻數(shù),然后生成鏈表節(jié)點(diǎn)插入到對(duì)應(yīng)的鄰接表中。

表3 候選1項(xiàng)集表

表4 頻繁1項(xiàng)集表

圖4 候選2項(xiàng)集鄰接表

3) 從頻繁k(k≥2)項(xiàng)集開始,利用k-1頻繁項(xiàng)集交叉連接取并集的過(guò)程中,可能會(huì)出現(xiàn)重復(fù)的頻繁項(xiàng)集需要計(jì)算。

(1) 如果該項(xiàng)集在之前的計(jì)算過(guò)程中存在,則不用重復(fù)計(jì)算項(xiàng)集支持度頻數(shù),繼續(xù)計(jì)算當(dāng)前輪下一個(gè)項(xiàng)集。

(2) 如果符合定義3,項(xiàng)集的子集經(jīng)過(guò)判斷后不是頻繁項(xiàng)集,則利用哈希表進(jìn)行動(dòng)態(tài)剪枝操作,不必計(jì)算該項(xiàng)集的支持度頻數(shù),繼續(xù)計(jì)算當(dāng)前輪下一個(gè)項(xiàng)集。

(3) 根據(jù)定義4,如果該項(xiàng)集超集是頻繁項(xiàng)集,不用計(jì)算該項(xiàng)集頻數(shù),直接設(shè)置該項(xiàng)集支持度頻數(shù)為min_support_count,繼續(xù)計(jì)算當(dāng)前輪下一個(gè)項(xiàng)集。

(4) 這樣極大地減少冗余項(xiàng)集的無(wú)效計(jì)算,如果計(jì)算生成的候選項(xiàng)集(沒(méi)有執(zhí)行前幾個(gè)過(guò)程,稱為候選項(xiàng)集),對(duì)該候選項(xiàng)集中每一個(gè)事務(wù)和哈希表Hash_Total中的第p(p=1,2,…,N)行的數(shù)據(jù)進(jìn)行檢索,如果項(xiàng)集中每一個(gè)事務(wù)都能在哈希表第p(p=1,2,…,N)行中找到,根據(jù)定義2,則每在一行找到就在項(xiàng)集支持度頻數(shù)計(jì)數(shù)加1),每次計(jì)算完項(xiàng)集支持度頻數(shù)后,將項(xiàng)集與項(xiàng)集支持度頻數(shù)存儲(chǔ)在鏈表節(jié)點(diǎn)中,將鏈表節(jié)點(diǎn)插入到鄰接表中。

4) 通過(guò)遍歷候選2項(xiàng)集的鄰接表,可以得到候選2項(xiàng)集以及對(duì)應(yīng)的支持度頻數(shù),根據(jù)堆排序的思想,利用項(xiàng)集支持度頻數(shù)建立大根堆,并且利用堆排序的思想對(duì)部分項(xiàng)集頻數(shù)進(jìn)行遞減排序(只需要對(duì)于項(xiàng)集支持度頻數(shù)滿足最小支持度的項(xiàng)集排序),經(jīng)過(guò)堆排序篩選之后就得到頻繁2項(xiàng)集,L2=[[A4,A5],[A5,A7],[A2,A4],[A2,A5],[A4,A7],[A4,A8],[A4,A9],[A5,A8],[A5,A9],[A1,A5],[A2,A8],[A2,A9]]。

5) 因?yàn)閨L2|=12≥k+1(k=2),根據(jù)推論1,因此可繼續(xù)擴(kuò)展生成頻繁3項(xiàng)集集合。利用頻繁2項(xiàng)集L2構(gòu)建候選3項(xiàng)集鄰接表,可以利用L2繼續(xù)擴(kuò)展生成候選3項(xiàng)集,fi表示頻繁2項(xiàng)集(fi=[[A4,A5],[A5,A7],[A2,A4],[A2,A5],[A4,A7],[A4,A8],[A4,A9],[A5,A8],[A5,A9],[A1,A5],[A2,A8],[A2,A9]])。將L2的項(xiàng)集進(jìn)行交叉連接取并集,就可以擴(kuò)展生成出候選3項(xiàng)集(如圖5所示),重復(fù)進(jìn)行步驟3)-步驟5)的過(guò)程就可以計(jì)算下一項(xiàng)頻繁項(xiàng)集。

圖5 候選3項(xiàng)集鄰接表

6) 按照步驟5)中求頻繁項(xiàng)集的方法,就可以擴(kuò)展得到頻繁3項(xiàng)集,|L3|=4≥k+1(k=3),L3=[[A2,A4,A5],[A4,A5,A7],[A4,A5,A8],[A4,A5,A9]],滿足推論1條件,繼續(xù)向(k+1)項(xiàng)擴(kuò)展,進(jìn)而求出(k+1)頻繁項(xiàng)集。

7) 重復(fù)步驟6)中計(jì)算(k+1)項(xiàng)的處理,如果無(wú)法滿足推論1的條件,表示無(wú)法計(jì)算出下一項(xiàng)頻繁項(xiàng)集,算法結(jié)束,輸出所有的頻繁項(xiàng)集。

5 算法的效率分析

5.1 算法時(shí)間復(fù)雜度分析

Apriori算法求頻繁項(xiàng)集所需要的時(shí)間是由數(shù)據(jù)量的大小M、每條數(shù)據(jù)的事務(wù)項(xiàng)長(zhǎng)度L所決定的,項(xiàng)集個(gè)數(shù)為|Ck|,每一次掃描數(shù)據(jù)庫(kù)數(shù)據(jù)并計(jì)算項(xiàng)集支持度頻數(shù)時(shí)間復(fù)雜度是O(M×L×|Ck|),掃描數(shù)據(jù)庫(kù)后就要開始進(jìn)行項(xiàng)集的自連接平均的時(shí)間復(fù)雜度為O(|Ck-1|×|Ck-1|),在這個(gè)過(guò)程中,經(jīng)過(guò)動(dòng)態(tài)剪枝的時(shí)間復(fù)雜度為O(|Ck|),判斷符合最小支持度的平均時(shí)間復(fù)雜度為O(M×|Ck|),所以Apriori算法計(jì)算頻繁項(xiàng)集所需要總時(shí)間為[16]:

T1=O(M×L×|Ck|)+O(|Ck-1|×|Ck-1|)+

O(|Ck|)+O(M×|Ck|)

本文利用哈希表的方式存儲(chǔ)數(shù)據(jù)庫(kù)的數(shù)據(jù),并且用哈希表查找的方法來(lái)計(jì)算項(xiàng)集支持度頻數(shù),利用鄰接表存儲(chǔ)每次計(jì)算的候選項(xiàng)集。利用哈希表只需要掃描一次數(shù)據(jù)庫(kù),將數(shù)據(jù)庫(kù)數(shù)據(jù)映射到哈希表中進(jìn)行存儲(chǔ),避免了多次掃描數(shù)據(jù)庫(kù)而消耗時(shí)間,因此主要在項(xiàng)集交叉連接以及在哈希表中計(jì)算頻繁項(xiàng)集的過(guò)程中消耗的時(shí)間。假設(shè)數(shù)據(jù)庫(kù)的數(shù)量為M,即哈希表的行數(shù)為M,哈希表查找的時(shí)間復(fù)雜度為O(1),每一輪產(chǎn)生的候選項(xiàng)集為Ck,頻繁項(xiàng)集為L(zhǎng)=Lk,冗余項(xiàng)集剪枝與去重的項(xiàng)集減少的時(shí)間為T,構(gòu)建大根堆進(jìn)行排序的時(shí)間復(fù)雜度O(CklogLk),則近似推算出所需要的總時(shí)間大約為:

O(CklogLk)

5.2 算法的空間復(fù)雜度分析

Apriori算法求頻繁項(xiàng)集計(jì)算所需要的內(nèi)存空間是頻繁項(xiàng)集和非頻繁項(xiàng)集的數(shù)量所決定,該算法項(xiàng)集在內(nèi)存空間上消耗近似為[16]:

S1=O(|Ck|×|Ck|)+O(|Lk|)

本文利用哈希表檢索來(lái)計(jì)算頻繁項(xiàng)集支持度頻數(shù),并且用鄰接表來(lái)存儲(chǔ)候選項(xiàng)集,每次存儲(chǔ)的候選項(xiàng)集為Ck,該算法中項(xiàng)集所占用在空間上面的消耗近似為:

S2=O(|Ck|)+O(|Lk|)

對(duì)比兩種算法的時(shí)間復(fù)雜度和空間復(fù)雜度可以看出:T2

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

本文針對(duì)傳統(tǒng)Apriori算法與文獻(xiàn)[7]中的算法(簡(jiǎn)稱OLL-Apriori算法)和ATSAHT-Apriori算法在相同環(huán)境下進(jìn)行對(duì)比實(shí)驗(yàn),數(shù)據(jù)集為毒蘑菇的相似特征,來(lái)自于UCI數(shù)據(jù)集:數(shù)據(jù)集包含了8 124條樣本和23個(gè)特征,將數(shù)據(jù)順序隨機(jī)排列進(jìn)行分組然后對(duì)比實(shí)驗(yàn)。

第一組實(shí)驗(yàn)設(shè)置最小支持度為0.1,在數(shù)據(jù)數(shù)量逐漸遞增的情況下進(jìn)行比較兩種算法的時(shí)間效率。實(shí)驗(yàn)對(duì)比如圖6所示。

圖6 不同數(shù)據(jù)運(yùn)行時(shí)間對(duì)比

通過(guò)圖6中的實(shí)驗(yàn)對(duì)比,說(shuō)明當(dāng)最小支持度一定時(shí),隨著數(shù)據(jù)量的增多而增多,所花費(fèi)的時(shí)間也會(huì)逐漸增多。在相同的環(huán)境下,ATSAHT-Apriori算法在時(shí)間效率上明顯提高,花費(fèi)的時(shí)間明顯小于其他兩個(gè)算法。

第二組實(shí)驗(yàn)采用最小支持度為0.01,在相同環(huán)境進(jìn)行實(shí)驗(yàn),在數(shù)據(jù)數(shù)量遞增的情況下進(jìn)行比較三種算法的內(nèi)存空間占用,實(shí)驗(yàn)結(jié)果如圖7所示。

圖7 不同數(shù)據(jù)占用內(nèi)存空間對(duì)比

通過(guò)實(shí)驗(yàn)對(duì)比可知,隨著數(shù)據(jù)量范圍的不斷增加,產(chǎn)生的數(shù)據(jù)分支也會(huì)隨之增多,產(chǎn)生的頻繁項(xiàng)集也會(huì)慢慢增加,作為對(duì)比的三種算法內(nèi)存空間占有率都會(huì)增加,但是相比之下,經(jīng)過(guò)優(yōu)化后的ATSAHT-Apriori算法的時(shí)間效率與內(nèi)存空間占用明顯優(yōu)于其他兩種算法。綜合以上實(shí)驗(yàn)結(jié)果表明,在相同環(huán)境下,經(jīng)過(guò)優(yōu)化后ATSAHT-Apriori算法時(shí)間效率得到了明顯的提高,內(nèi)存空間占有得到明顯的減少,說(shuō)明了ATSAHT-Apriori方法達(dá)到了預(yù)期的效果。

7 結(jié) 語(yǔ)

本文利用哈希表的特性,提出利用哈希表來(lái)存儲(chǔ)數(shù)據(jù)庫(kù)中的數(shù)據(jù),并且利用哈希表來(lái)計(jì)算項(xiàng)集的支持度頻數(shù);利用動(dòng)態(tài)剪枝算法與哈希表去除重復(fù)項(xiàng)集減少了大量的冗余項(xiàng)集,并結(jié)合圖存儲(chǔ)的思想,利用鄰接表存儲(chǔ)項(xiàng)集交叉連接生成的候選項(xiàng)集;利用堆排序算法對(duì)候選項(xiàng)集進(jìn)行部分排序生成頻繁項(xiàng)集,極大地優(yōu)化了頻繁項(xiàng)集的計(jì)算速度與內(nèi)存空間。本文算法對(duì)Apriori算法的時(shí)間復(fù)雜度和空間復(fù)雜度的不足之處進(jìn)行了較大的優(yōu)化,通過(guò)實(shí)驗(yàn)數(shù)據(jù)對(duì)比分析,驗(yàn)證了改進(jìn)后的算法在運(yùn)行時(shí)間和內(nèi)存開銷有明顯優(yōu)化的效果。但是當(dāng)數(shù)據(jù)量較大時(shí),項(xiàng)集交叉連接和計(jì)算頻繁項(xiàng)集時(shí)同樣存在非常大的計(jì)算量,在今后的研究中將會(huì)結(jié)合Hadoop框架,實(shí)現(xiàn)并行化計(jì)算處理,以期得到更好的效果。