基于哈希表與十字鏈表存儲的Apriori算法優化

吳 昊 劉 釗 顧進廣

(武漢科技大學計算機科學與技術學院 湖北 武漢 430065) (武漢科技大學大數據科學與工程研究院 湖北 武漢 430065) (湖北省智能信息處理與實時工業系統重點實驗室 湖北 武漢 430065)

0 引 言

雖然Apriori算法原理簡單,算法容易實現,但是該算法的時間復雜度和空間復雜度比較高,導致在計算頻繁項集的過程中時間效率和空間效率比較低。針對傳統Apriori算法在時間復雜度和空間復雜度上的不足,文獻[1]提出了使用優化的鏈表數據結構進行存儲，并提高支持計數效率,同時采用了候選生成方法來減少匹配候選項目集。文獻[2]提出了一種基于MapReduce的頻繁項集挖掘方法，在云計算中引入了MapReduce模型來實現Apriori算法并行化。文獻[3]提出了一種基于標記事務壓縮改進的Apriori算法，該算法優化了關聯規則的參數,減少標簽比較的次數。文獻[4]提出了編碼和適應度函數的方案，建立了關聯規則的模式，提高了算法的效率和準確性。廖紀勇等[5]提出了一種基于布爾矩陣約簡的Apriori改進算法,將矩陣各列元素按照支持度升序排列,使得算法在壓縮過程中減少了掃描矩陣各列的次數,縮短了算法的運行時間。李潔等[6]提出一種基于哈希存儲與事務加權的并行Apriori改進算法，通過哈希存儲的去重特性，減少冗余計算,開啟多個線程，并行計算候選集的支持度，從而提高Apriori算法的運行效率。文武等[7]提出了一種結合遺傳算法的Apriori算法來挖掘頻繁項集,結合Apriori算法和遺傳算法的特點,利用交叉算子產生候選項集和變異算法篩選頻繁項集。趙學健等[8]提出了一種利用正交鏈表存儲數據所對應的關系矩陣,同時優化了傳統的Apriori算法的自連接和剪枝過程,合理縮小了搜索空間。

1 Apriori算法

1.1 數據關聯規則原理

假定數據集為D，Item={I1,I2,…,Im}表示數據庫所有數據的集合,I={t1,t2,…,tk}用來表示不同的事務集,每個ti對應一個事務。is、it是I中任意一個項集,并且is中含有事務的數量記為n,表示n項集,根據數據集D中生成的關聯規則表示is≥it,同時is?I,it?I,is∩it為空集,is與it是通過最小支持度(Support)和最小置信度(Conf)來對關聯規則進行約束的。頻繁項集的支持度表示對應關聯規則的頻度,頻繁項集的置信度表示對應的關聯規則的強度[9]。

關聯規則is?it在D中的頻繁項集的支持度是指Item中同時包含is、it的數量與Item的總的數量之比[9],記作:

Support(is?it)=|{I:is∪it?I,Item∈D}|/|D|

關聯規則is?it在數據集D中的頻繁項集的置信度是指Item中同時包含is項集和it項集的數量與Item中包含is項集的數量之比,記作:

Conf(is?it)=|{I:is∪it?I,I∈D}|/|{I:is?I,I∈D}|

在數據集D中利用算法挖掘有效的關聯規則就是為了找出符合用戶給定的最小支持度(Min_Support)和最小置信度(Min_Conf)的關聯規則,當利用算法挖掘出來的關聯規則的置信度和支持度分別大于Min_Support與Min_Conf時,則認為該關聯規則是有效的,稱為強關聯規則[9]。

1.2 Apriori算法過程

Apriori算法計算頻繁項集的主要原理：首先利用數據的關聯規則計算出候選1項集(簡稱C1)；然后通過C1自連接的方式計算生成候選2項集(簡稱C2)；然后由候選2項集繼續通過自連接的方式來擴展生成候選3項集(簡稱C3)；接下來按上述方法一直迭代計算下去,直到判斷不能繼續擴展生成下一項項集時,表示該迭代計算的過程結束,算法結束。

算法具體實現步驟如下:

(1) 首先對數據庫中的數據進行預處理,然后掃描數據庫中數據中的事務,統計出每個事務對應的支持度頻數,即可生成候選1項集(簡稱C1),如果候選1項集中的事務支持度頻數滿足最小支持度頻數,經過篩選之后就可以生成頻繁1項集(簡稱L1)。

(2) 將L1中項集進行自連接,由此可以通過L1自連接生成候選2項集合(簡稱C2)。

(3) 通過C2繼續遍歷數據庫中每條數據的事務，利用計算每一個候選項集的支持度頻數,如果候選項集支持度頻數滿足最小支持度頻數,經過篩選后就生成頻繁2項集(簡稱L2)。

(4) 將L2中項集進行自連接,由此可以通過L2自連接生成候選3項集合(簡稱C3)。

(5) 通過C3繼續遍歷數據庫中每條數據的事務，計算每一個候選項集的支持度頻數,如果候選項集支持度頻數滿足最小支持度頻數,經過篩選后就生成頻繁3項集(簡稱L3)。

(6)將上述計算過程一直迭代進行,直到候選k項集為空就停止計算,算法結束,符合最小支持度的項集稱為頻繁項集[10]。

由上述過程可以看出Apriori算法在時間效率和空間效率方面有以下不足之處[9]:

(1) 首先將數據進行預處理之后,每計算一次項集的頻數就需要訪問數據庫,并對數據庫每一條數據進行掃描,因此掃描的次數比較多,這樣將會造成I/O上有比較大負載和時間開銷,降低了算法的計算性能。

(2) Apriori算法計算過程中會產生大量冗余候選項集。例如頻繁n項集經過自連接擴展生成所有的候選n+1項集Cn+1,掃描數據庫后就需要進行多次自連接產生冗余的項集,同時生成的候選項集與最小支持度比較次數增多。這樣造成了內存空間占用和計算時間的浪費。

(3) 在頻繁項集進行擴展生成下一項的時候,測試C(C∈Ck)里每個k-1項集是否是Lk-1中頻繁k-1項集,掃描k次Lk-1,對于Lk-1掃描的時間復雜度為O(k×|Lk-1|/2)，所以掃描每一個候選k項集Ck的時間復雜度為O(Ck×k×|Lk-1|/2),在計算過程中需要消耗大量時間[11]。

2 HTACL-Apriori算法

2.1 十字鏈表表示方法

十字鏈表節點的結構如圖1所示,Item為項目名，Number表示Item部分節點數目，Down表示向下指向其他事務部分,Right表示向右指向其他事務部分[11]。

圖1 十字鏈表結構

2.2 HTACL-Apriori挖掘算法原理

假定D={I1,I2,…,In}表示是所有數據的集合,I={t1,t2,…,tn}表示每條數據中的每一個事務。其中ti(i=1,2,…,n)表示每條數據中第i個事務,同時ti對應D上的一個子集(ti?D)。

定義1對于每一個項Pj定義為：

Pj=(X1j,X2j,…,Xmj)

性質1矩陣中存儲的每行元素都對應事務數據庫中的一個事務,每個事務中在矩陣用1/0表示該項目是否存在,這樣可以將所有事務都存儲在矩陣中(設定為1),后面就可以利用矩陣計算項集的頻數[10]。

定理1如果集合X的頻數小于最小支持度頻數,則集合X一定不是頻繁項集,如果存在X集合，且Y?X,可以判斷Y集合一定不是頻繁項集[12]。

定理2如果存在集合X，且集合X支持度頻數大于最小支持度頻數,則可以判定集合X為頻繁項集,如果存在Y集合，且Y?X,可以判斷Y集合同樣是頻繁項集[12]。

推論1假設頻繁k項集合個數記為|Lk|,如果|Lk|

3 HTACL-Apriori算法的優化

3.1 算法優化思想

通過3個步驟對傳統的Apriori算法進行改進優化:

(1) 將數據庫中的事務映射到布爾矩陣進行存儲(0表示不存在,1表示存在),這樣避免多次訪問數據庫掃描數據,只需要將數據一次性存儲在布爾矩陣中,后面利用布爾矩陣的特性來進行計算項集的頻數,極大地減少了計算過程中的I/O時間開銷與負載,優化了算法的運行速度[13]。

(2) 由于鏈表具有動態插入和動態刪除的優點,因此對每次生成的項集和對應頻數作為一個節點插入到鏈表中,然后對鏈表節點進行部分選擇排序,經過部分選擇排序,將不滿足最小支持度頻數的項集直接刪除(滿足最小支持度的項集不用排序),在后面的計算過程中減少了一些無效的自連接匹配運算,優化了算法運行速度和內存空間。

(3) 利用布爾矩陣的特性減少匹配時間。十字鏈表中節點的Item部分轉換為布爾向量和布爾矩陣中每一行進行“與”操作,然后利用定義1來計算項集在數據中出現的頻數,其過程所需要的時間小于事務數據之間自連接后再逐一判斷每個事務是否匹配所需要時間,通過布爾矩陣的特性來判斷,減少了一些無效自連接匹配運算,減少了時間消耗。

(4) 利用十字鏈表交叉正交存儲頻繁項集。根據定理1和定理2,利用哈希表對項集進行剪枝和去除重復項集,然后存儲在十字鏈表中，極大地減少了內存占用空間和冗余項集計算頻數的時間[13]。

3.2 算法的優化步驟

輸入:數據庫中數據經過預處理后的數量有N條,假定最小支持度為Min_Support,則最小支持度頻數為Min_support_Count=N×Min_Support。

輸出:輸出符合條件的頻繁項集。

算法優化的具體步驟如下:

(1) 將數據庫中的數據經過預處理后,根據性質1將每條數據中的事務按照0/1分布(0表示不存在,1表示存在)映射到布爾矩陣中,遍歷矩陣,利用定義1計算出候選1項集對應的頻數。

(2) 將候選1項集和對應頻數作為節點插入到鏈表中,然后對鏈表中項集的頻數進行部分選擇排序,只需要將不滿足最小支持度的項集頻數對應的鏈表節點篩選出來(不需要鏈表所有節點全部排序)進行刪除,同時利用哈希表hash_unfrequent存儲非頻繁項集(后面過程中利用定理1可以剪枝優化,減少計算時間),利用哈希表hash_frequent存儲頻繁項集(后面過程利用定理2可以剪枝優化,減少計算時間),就生成了頻繁1項集鏈表L1。

(3) 利用步驟(2)得到的頻繁1項集的鏈表進行交叉正交,然后將交叉正交的項集用哈希表hash_unique存儲(表示該項集已經出現,在后面項集的生成過程中可以去除重復項集,減少計算時間和冗余數據內存空間),將十字鏈表中節點Item部分轉換為對應布爾向量(0表示不存在,1表示存在),然后與布爾矩陣中每條數據進行“與”運算,如果判斷在該條數據中存在該項集,利用定義1可以計算出每個項集的對應的頻數,然后鏈表交叉正交生成項集時,首先用哈希表hash_unfrequent來判斷,如果符合定理1的情況的非頻繁項集進行剪枝優化(不用計算項集支持度頻數,不用將節點插入到十字鏈表中,繼續下一步),然后用哈希表hash_frequent來判斷,如果符合定理2情況的頻繁項集進行剪枝(直接將項集的頻數設置為最小支持度頻數,然后將節點直接插入到十字鏈表中)。接著用哈希表hash_unique判斷是否出現重復項集,如果哈希表hash_unique判斷已經存在,繼續下一步,不用將節點插入到十字鏈表中,反之,將節點插入到十字鏈表中。這樣就生成候選2項集的十字鏈表,遍歷十字鏈表中的每一個節點,將節點插入到新的鏈表當中。此時就生成候選2項集鏈表C2,將鏈表進行部分選擇排序,動態刪除小于最小支持度的鏈表節點,同時將非頻繁項集插入到哈希表hash_unfrequent中,將頻繁項集插入到哈希表hash_frequent中,最后生成頻繁2項集鏈表L2。

(4) 利用推論1來判斷|Lk|

(5) 循環重復步驟(4)。如果滿足|Lk|

HTICL-Apriori算法優化思想偽代碼描述如下:

HTICL-Apriori()

{

//將數據庫中的每條數據映射存入布爾矩陣Boolean_Matrix

//(M×N，其中：N為數據中事務最多的數量；M為數據條數)。

//用0/1區別,1表示存在,0表示不存在

//數組origin存儲掃描數組后的候選項集C1,哈希表hash_

//frequent用來存儲生成的頻繁項集,hash_unfrequent用來存儲

//生成的非頻繁項集,hash_unique存儲鏈表交叉正交生成的項

//集,用于去除重復項集

FOR(i=1;i<=N;i++) DO

FOR(j=1;j<=M;j++) DO

IFBoolean_Matrix[i][j]>0

origin[i].count++;

END FOR

END FOR

//將origin中的項集和對應的頻數插入P1鏈表中

P1.insert(origin[i](i=1,2,…,n))

HTACL-Apriori_Sort(P1)；

//對鏈表P1中每一個項集對應的頻數進行部分選擇排序

//遍歷Pk+1

IF(P1.number>=Min_support_Count)

hash_ frequent.insert(P1.frequent);

//存儲滿足最小支持度的項集

Else

hash_unfrequent.insert(P1.unfrequent);

//存儲不滿足最小支持度的項集

delete(P1.unfrequent);

//將鏈表P1中非頻繁項集的部分刪除

WHILE(Pk.length()>=k+1&&Pk!=?)

{

根據定理1可知,由頻繁1項集事務進行轉置和頻繁1項集進行內積變換,生成二維布爾矩陣

FOR(i=1;z<|Pk|.length();i++) DO

FOR(j=i+1;y<|Pk|.length();j++) DO

Ck=Pk.Item[i]∪Pk.Item[j]

//交叉正交

//根據定理1和定量2判斷

IFCk∈hash_unfrequent

Pk同時向右和向下移動

Continue

IFCk∈hash_frequent

Pk.Ck.number=Min_Support_Count;

Pk同時向右和向下移動

Continue

IFCk∈hash_unique

//項集已經出現

Pk同時向右和向下移動

Continue

hash_unique.insert(Ck);

//hash_unique插入Ck,方便在十字鏈表中去除存儲重復項集

將Ck中的項集先轉換成布爾向量,用0/1區別,1表示存在,0表示不存在

WHILE矩陣Matrix

Ck與布爾矩陣Matrix每一行對應的列進行“與”運算,如果判斷在該條數據中存在該項集,利用定義1計算項集頻數。

Pk.Ck.number++;

//對該項集計數

Cross_Listk.insert(Pk)

//將該節點Pk插入十字鏈表中

END FOR

END FOR

將Cross_Listk的向下和向右的尾端設置為NULL

將十字鏈表Cross_Listk中生成的候選項集全部插入到鏈表Pk+1中。

HTACL-Apriori_Sort(Pk+1)//對鏈表Pk+1中每一個項集對應的

//頻數進行部分選擇排序遍歷Pk+1

IF(Pk+1.number>=Min_support_Count)

hash_ frequent.insert(Pk+1.frequent);

//存儲頻繁項集。

Else

hash_unfrequent.insert(Pk+1.unfrequent);

//存儲非頻繁項集

Delete(Pk+1.unfrequent);

//將鏈表Pk+1中非頻繁項集的部分刪除

END WHILE

}

HTACL-Apriori_Sort(Pk)、

{

//鏈表節點中的number,用部分選擇排序(把項集按照最小支

//持度分成兩個部分)

調用選擇排序算法Sort(Pk)

}}

3.3 算法的優化示例說明

假定關聯規則的最小支持度為0.4,數據量有10條,首先將數據進行預處理,將每條數據中的事務按照字母序列遞增排序(如表1所示),然后可以計算出最小支持度頻數Min_Support_Count=10×0.4=4,同時按照以下步驟來計算頻繁項集。

表1 數據表

(1) 將經過預處理的數據根據性質1按照0/1分布映射到布爾矩陣中對應的位置來表示對應事務是否存在,矩陣中的行表示每條數據，每一列表示每一個事務，轉換成對應矩陣Boolean_Matrix(本示例中以事務a,b,c,d,e,f,g,h為行)。

(2) 遍歷布爾矩陣中的每一個事務,根據定義1可以計算出該數據集中每個事務對應的頻數,數據如表2所示。

表2 數據中事務表

(3) 按照每個事務對應的數量進行部分選擇排序,將小于最小支持度的項集排在最后,然后將滿足最小支持度的項集插入到鏈表中,由此可以得到新鏈表,同時將鏈表中頻繁項集全部插入到哈希表hash_frequent中,將鏈表中非頻繁項集全部插入到哈希表hash_unfrequent中。

(4) 由此可以計算出頻繁1項集鏈表(如圖1所示),即L1={{a},,g0gggggg,{e},{g},{h}}。同時計算出頻繁1項集的個數|L1|=6≥K+1。根據推論1可以得出可以由L1繼續向候選2項集進行擴展,將鏈表L1交叉正交生成候選2項集,首先根據定理1判斷該項集是否在哈希表hash_unfrequent中存在,如果存在則進行剪枝(不必計算項集的頻數,不必插入十字鏈表,繼續下一步計算),繼續根據定理2判斷是否在哈希表hash_frequent中存在,如果存在(直接設置為最小支持度,插入十字鏈表),繼續判斷該項集是否存在于哈希表hash_unique,如果存在則去重(不必計算項集的頻數,不必插入十字鏈表,繼續下一步),將生成候選2項集插入哈希表hash_unique(去除重復項集),最后將生成的項集轉換為布爾向量(0表示該事務不存在,1表示該事務存在),通過定義1進行計算對應的頻數,如果頻數不滿足最小支持度,就將項集插入哈希表hash_unfrequent中,反之插入哈希表hash_frequent中。經過上述步驟,就可以生成交叉正交后十字鏈表,如圖2所示。

圖2 頻繁1項集鏈表

(5) 遍歷十字鏈表中每一個節點,并且插入在新鏈表中,將新鏈表節點中的頻數按照最小支持度頻數進行部分選擇排序,將鏈表部分非頻繁項集進行刪除,這樣就生成新鏈表(如圖3所示),將頻繁項集全部插入到哈希表hash_frequent,非頻繁項集插入到哈希表hash_unfrequent，由此計算出頻繁2項集L2={{bd},{be},{de},{dg},{dh},{eg}},同時可以計算出頻繁2項集的數量為|L2|=6≥k+1,由推論1可以繼續向k+1項集進行擴展,重復步驟(3)中鏈表交叉正交的步驟,可以生成十字鏈表(如圖4所示)。

圖3 頻繁1項集十字鏈表

圖4 頻繁2項集鏈表

(6) 遍歷十字鏈表中的節點,將每一個節點插入到新的鏈表中,然后將新鏈表進行部分選擇排序,將鏈表中非頻繁項集進行刪除,這樣就生成新鏈表(如圖5所示[13]),重復步驟(4)，由此計算出L3={{bde},{deg},{deh}}(如圖6所示),然后通過推論1判斷是否能夠繼續進行擴展。

圖5 頻繁2項集交叉正交十字鏈表

圖6 頻繁3項集鏈表

(7) 重復循環步驟(4)和步驟(5)中計算(k+1)項的步驟,如果不滿足推論1條件,表示無法計算出下一項頻繁項集,算法結束,輸出頻繁項集。

3.4 算法的性能分析

評價算法性能的優劣主要從算法的時間復雜度和空間復雜度來進行衡量。

3.4.1兩種算法時間復雜度分析

假定有M條數據,每條數據中有事務數為L。計算頻繁項集分為3個過程。

步驟1每一次計算項集頻數掃描數據庫數據時間復雜度約為：T1=O(M×L)。

步驟2掃描數據庫中的數據后，進行項集自連接平均的時間復雜度約為：T2=O(|Lk-1|×|Lk-1|)。

步驟3在計算頻繁項集的過程中,經過動態剪枝判斷符合最小支持度的平均的時間復雜度為：T3=O(M×|Ck|)。

本文利用了布爾矩陣“與”運算來求項集頻數,結合哈希表剪枝和十字鏈表去重來計算頻繁項集,因此主要在布爾矩陣生成以及鏈表交叉正交及剪枝去重過程中消耗時間。假設布爾矩陣數據為M條,每一條數據的事務長度為N,頻繁項集的長度為|Lk|。

步驟1每計算一次項集需要掃描矩陣中的數據的時間復雜度為：H1=O(M×N)。

步驟2鏈表交叉正交和剪枝與去除重后存儲在十字鏈表中的項集的時間復雜度約為O(((|Lk-1|×|Lk-1|)/2-|Lk-1|)×M),剪枝和去重的時間為|Tk|,該過程時間復雜度為:H2=O((((|Lk-1|×|Lk-1|)/2-|Lk-1|)-|Tk|)×M)。

步驟3遍歷十字鏈表生成新鏈表的時間復雜度為：H3=O(|Ck|)。

結論：通過前面的分析，本文利用布爾矩陣“與”運算來計算頻繁可以優化算法的運行速度，說明時間復雜度H1

3.4.2算法的空間復雜度分析

假定數據量為M,事務項的長度為L。Apriori算法的空間復雜度為:S1=O(|Lk-1|×|Lk-1|+|Ck|)。

3.5 實驗結果分析

對文獻[14]的優化方法進行算法復現(簡稱VM_Apriori算法)，本文在相同環境下做了大量的實驗來比較三種算法的時間效率和空間占用效率,實驗的操作系統為Windows 10,數據庫為MySQL,編程語言為Python3.7,開源軟件RGui自帶的Groceries數據集作為實驗數據集,該數據集中有9 835條數據，169項不同的事務。

(1) 分組設置不同的最小支持度，來比較兩種算法在計算時間上的性能[15],三種算法使用相同的數據，均為9 835條，如圖7所示。

圖7 不同支持度的計算時間

在實驗數據的測試的對比之下，經過改進后的HTACL_Apriori算法在同樣的環境與數據下,耗時明顯減少,達到了預期效果。

(2) 分組設置不同的數據量，來比較三種算法的時間效率[16]，三種算法的最小支持度均為0.01，如圖8所示。

圖8 不同數據量的計算時間

當數據量比較小的時候，算法的耗時也比較少，隨著數據量增加，三種算法所消耗的時間也不斷地增加。在實驗數據的對比之下，經過改進后的HTACL_Apriori算法在同樣的環境與數據下,耗時明顯減少,達到了實驗的預期效果。

(3) 分組設置不同的數據量，來比較三種算法的空間效率[17]，三種算法的最小支持度均為0.01，實驗對比如圖9所示。

圖9 不同數據量內存空間占用

可以看出，當數據量比較小的時候，算法的空間占用也比較小，隨著數據量增加，三種算法的空間內存開銷也不斷地增加。在實驗數據的對比之下，經過改進后的算法在同樣的環境與數據下,空間內存開銷明顯減少,達到了預期效果[18]。

通過上述理論分析和多組數據實驗對比了三種算法的性能[19]，在環境相同的情況下，算法優化后的時間復雜度和空間復雜度得到了明顯的改善,達到了預期效果。

4 結 語

本文提出利用布爾矩陣表示事務,并且結合哈希表和十字鏈表存儲對項集進行剪枝和去除重復值降低時間復雜度和空間復雜度。并且通過對實驗數據對比分析,驗證了HTACL_Apriori算法的時間復雜度和空間復雜度得到了明顯的優化。但是當數據量達到較大的規模,所處理的數據會受限于內存計算容量。在后續的研究中將考慮基于結合Spark框架,實現大規模數據處理,期望在數據處理方面得到更好的效果。