基于鄰接表存儲與哈希表的頻繁項集挖掘算法

吳 昊 劉 釗 顧進廣

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

0 引 言

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

本文提出一種基于鄰接表存儲與哈希表的頻繁項集挖掘算法(ATSAHT-Apriori算法)。該算法利用哈希表的特性,將數據庫中的數據進行處理,將數據全部轉化為哈希表進行映射,在后續計算項集支持度頻數的時候不必進行數據與項集自匹配的過程,由于只需要在哈希表中進行查找來計算項集支持度頻數[7],極大地減少了每一輪項集支持度頻數的計算時間。由于只需要對數據庫中的數據掃描一次存在哈希表中,極大地減少了I/O的時間開銷與負載。同時,結合圖存儲的思想利用鄰接表來存儲項集,有效地優化了存儲項集的內存空間占用,在計算候選項集的過程中,利用堆排序的思想構建大根堆和動態剪枝的思想減少了冗余項集的計算,進一步優化了算法執行時間和內存空間占用。

1 Apriori預測算法簡介

Apriori算法是基于一種迭代計算搜索的方式,同時利用頻繁k項集的自連接來擴展生成(k+1)項集,首先獲取頻繁1項集(簡稱C1),然后通過C1自連接擴展生成候選2項集(簡稱C2),然后通過候選2項集擴展生成頻繁3項集(簡稱C3),一直迭代下去,直到不能繼續擴展生成下一項頻繁項集,該迭代方法結束[8]。

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

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

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

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

根據上述Apriori算法在時間復雜度和空間復雜度的不足,本文提出一種ATSAHT-Apriori算法進行優化。

2 ATSAHT-Apriori挖掘算法

2.1 ATSAHT-Apriori算法描述

鄰接表[12](Adjacency List)就是把從同一個頂點出發到達的相鄰節點的點和邊連接在同一個單鏈表中,單鏈表的每個節點代表一條邊,稱為邊節點。每個邊節點有三個域:該起點項集對應終點的項集,起點項集與終點項集進行交集后的項集與項集頻數,以及指向下一個邊節點的指針。在鄰接表中,還需要一個用于存儲頂點信息的頂點數組。

結合鄰接表存儲的圖節點的思想(關聯項集如圖1所示,邊的權重表示兩點項集的支持度頻數),鄰接表中節點屬性(如圖2所示),利用鄰接表存儲頻繁項集[13](如圖3所示)。

圖1 關聯項集

圖2 鏈表節點屬性

圖3 關聯項集的鄰接表

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

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

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

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

2.2 算法的優化方法

ATSAHT-Apriori算法通過以下方法進行優化:

1) 本文提出一種哈希表存儲方式來存儲數據,即把數據庫中的數據預處理后,存儲在哈希表中,然后在哈希表中進行計算項集支持度頻數,利用哈希表存儲的方法就僅需要掃描一次數據,在后續的過程中極大地減少了I/O的時間開銷與負載。

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

3) 將每輪交叉連接生成的項集進行判斷,利用哈希表的特性同時結合定義2和定義3,進行動態剪枝,減少了冗余項集的存儲和計算過程,優化了計算過程,優化了項集的內存占用空間。

4) 利用哈希表可以判斷在當前輪已經計算的項集,將當前輪已經生成的項集及項集支持度頻數存入到哈希表中,在后面的計算中,就可以利用哈希表進行判斷,如果該項集已經計算過,不需要重復計算,減少了存儲冗余項集的計算時間。

5) 利用圖存儲的思想,利用鄰接表存儲兩點項集生成的候選項集,利用定義2與定義3,結合哈希表對當前輪的項集進行動態剪枝與去除重復項集,將篩選后的候選項集存儲在鄰接表中,極大地優化了內存空間。

6) 當前輪計算結束后,利用堆排序思想構建大根堆,將候選項集插入大根堆中進行排序,每次刪除大根堆中支持度頻數最大的項集,并將該項集插入新的鄰接表中,當大根堆中最大元素不滿足最小支持度后,堆排序結束,剩余的不符合要求的項集不需要排序,將剩余項集存儲非頻繁項集集合中,為計算下一輪項集優化了存儲空間。

3 ATSAHT-Apriori算法的優化

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

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

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

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

4) 通過推論1判斷,如果|Lk|≥k+1,說明利用Lk中的頻繁項集可以計算(k+1)項,重復步驟2)和步驟3)中求下一項頻繁項集的過程,并且通過頻繁k項集來繼續擴展第k+1項的頻繁項集。

5) 重復循環步驟4),利用推論1,直到第k項頻繁項集的數量小于k+1,就表明無法進行下一層尋找更多的頻繁項集,查找頻繁項集算法結束。

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

ATSAHT-Apriori (){

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

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

FOR(i=0;i

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

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

//對事務進行計數

END FOR

FOR(i=0;i

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

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

//將頻繁項集存入V1

ELSE

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

//將非頻繁項集存入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項集中第i行事務

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

q=Vk-1[j].key;

//表示k-1項集中第j列事務

/*p∪q表示交叉連接取的項集賦值給flag */

flag=p∪q;

IF 哈希表Hash_Item出現過flag

/*不用重復計算,計算下一個項集*/

Continue;

IF flag是Vk中的子集

/*根據定義4判斷,直接設置為最小支持度,計算下一個項集*/

M[flag]=Min_sup_Count;

Continue;

IF flag是res中的子集

/*根據定義3判斷,繼續計算下一項集*/

Continue;

FOR(p=0;p

/*計算項集頻數*/

//遍歷哈希表Hash_Total,N表示哈希表行數

FOR(h=0;h

//遍歷項集flag中的每一項事務。

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

//根據定義2,計算每個候選項集頻數

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

M[flag]++;

/*項集計數*/

END FOR

END FOR

/*哈希表Hash_Item(Hash_Item的key表示項集,value對應項集頻數)對來存儲項集與頻數。*/

Hash_Item[flag]=M[flag];

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

END FOR

END FOR

遍歷當前輪的鄰接表,將每一個項集及對應的頻數存儲在一維列表ansk中;

fre_item,unfre_item=ATSAHTApriori_Sort(ansk);

/*對項集頻數構建大根堆排序。篩選出符合最小支持度的前k個項集,不符合條件的項集不用排序*/

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

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

END FOR}

ATSAHT-Apriori_Sort(ansk){

/*以頻繁項集的數量為標準,用堆排序思想構造大根堆進行排序*/

調用堆排序算法進行部分排序[13]

//fre_item為頻繁項集,unfre_item為非頻繁項集

fre_item,unfre_item=heap_Sort(ansk);}

4 ATSAHT-Apriori算法的優化驗證

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

表1 數據庫數據

1) 首先對數據進行預處理,然后將數據庫中有效數據存儲到哈希表Hash_Total中(見表2)。

表2 數據對應的哈希表

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

表3 候選1項集表

表4 頻繁1項集表

圖4 候選2項集鄰接表

3) 從頻繁k(k≥2)項集開始,利用k-1頻繁項集交叉連接取并集的過程中,可能會出現重復的頻繁項集需要計算。

(1) 如果該項集在之前的計算過程中存在,則不用重復計算項集支持度頻數,繼續計算當前輪下一個項集。

(2) 如果符合定義3,項集的子集經過判斷后不是頻繁項集,則利用哈希表進行動態剪枝操作,不必計算該項集的支持度頻數,繼續計算當前輪下一個項集。

(3) 根據定義4,如果該項集超集是頻繁項集,不用計算該項集頻數,直接設置該項集支持度頻數為min_support_count,繼續計算當前輪下一個項集。

(4) 這樣極大地減少冗余項集的無效計算,如果計算生成的候選項集(沒有執行前幾個過程,稱為候選項集),對該候選項集中每一個事務和哈希表Hash_Total中的第p(p=1,2,…,N)行的數據進行檢索,如果項集中每一個事務都能在哈希表第p(p=1,2,…,N)行中找到,根據定義2,則每在一行找到就在項集支持度頻數計數加1),每次計算完項集支持度頻數后,將項集與項集支持度頻數存儲在鏈表節點中,將鏈表節點插入到鄰接表中。

4) 通過遍歷候選2項集的鄰接表,可以得到候選2項集以及對應的支持度頻數,根據堆排序的思想,利用項集支持度頻數建立大根堆,并且利用堆排序的思想對部分項集頻數進行遞減排序(只需要對于項集支持度頻數滿足最小支持度的項集排序),經過堆排序篩選之后就得到頻繁2項集,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) 因為|L2|=12≥k+1(k=2),根據推論1,因此可繼續擴展生成頻繁3項集集合。利用頻繁2項集L2構建候選3項集鄰接表,可以利用L2繼續擴展生成候選3項集,fi表示頻繁2項集(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的項集進行交叉連接取并集,就可以擴展生成出候選3項集(如圖5所示),重復進行步驟3)-步驟5)的過程就可以計算下一項頻繁項集。

圖5 候選3項集鄰接表

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

7) 重復步驟6)中計算(k+1)項的處理,如果無法滿足推論1的條件,表示無法計算出下一項頻繁項集,算法結束,輸出所有的頻繁項集。

5 算法的效率分析

5.1 算法時間復雜度分析

Apriori算法求頻繁項集所需要的時間是由數據量的大小M、每條數據的事務項長度L所決定的,項集個數為|Ck|,每一次掃描數據庫數據并計算項集支持度頻數時間復雜度是O(M×L×|Ck|),掃描數據庫后就要開始進行項集的自連接平均的時間復雜度為O(|Ck-1|×|Ck-1|),在這個過程中,經過動態剪枝的時間復雜度為O(|Ck|),判斷符合最小支持度的平均時間復雜度為O(M×|Ck|),所以Apriori算法計算頻繁項集所需要總時間為[16]:

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

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

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

O(CklogLk)

5.2 算法的空間復雜度分析

Apriori算法求頻繁項集計算所需要的內存空間是頻繁項集和非頻繁項集的數量所決定,該算法項集在內存空間上消耗近似為[16]:

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

本文利用哈希表檢索來計算頻繁項集支持度頻數,并且用鄰接表來存儲候選項集,每次存儲的候選項集為Ck,該算法中項集所占用在空間上面的消耗近似為:

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

對比兩種算法的時間復雜度和空間復雜度可以看出:T2

6 實驗驗證分析

本文針對傳統Apriori算法與文獻[7]中的算法(簡稱OLL-Apriori算法)和ATSAHT-Apriori算法在相同環境下進行對比實驗,數據集為毒蘑菇的相似特征,來自于UCI數據集:數據集包含了8 124條樣本和23個特征,將數據順序隨機排列進行分組然后對比實驗。

第一組實驗設置最小支持度為0.1,在數據數量逐漸遞增的情況下進行比較兩種算法的時間效率。實驗對比如圖6所示。

圖6 不同數據運行時間對比

通過圖6中的實驗對比,說明當最小支持度一定時,隨著數據量的增多而增多,所花費的時間也會逐漸增多。在相同的環境下,ATSAHT-Apriori算法在時間效率上明顯提高,花費的時間明顯小于其他兩個算法。

第二組實驗采用最小支持度為0.01,在相同環境進行實驗,在數據數量遞增的情況下進行比較三種算法的內存空間占用,實驗結果如圖7所示。

圖7 不同數據占用內存空間對比

通過實驗對比可知,隨著數據量范圍的不斷增加,產生的數據分支也會隨之增多,產生的頻繁項集也會慢慢增加,作為對比的三種算法內存空間占有率都會增加,但是相比之下,經過優化后的ATSAHT-Apriori算法的時間效率與內存空間占用明顯優于其他兩種算法。綜合以上實驗結果表明,在相同環境下,經過優化后ATSAHT-Apriori算法時間效率得到了明顯的提高,內存空間占有得到明顯的減少,說明了ATSAHT-Apriori方法達到了預期的效果。

7 結 語

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