基于散列技術的多層關聯規則算法的改進

郭 倩，殷麗鳳

(大連交通大學 軟件學院，遼寧 大連 116028)

0 引 言

自從Agrawal等[1]提出挖掘關聯規則Apriori算法以來，眾多學者針對此算法有較多冗余項集、很大的I/O負載的缺點做了不斷改進，如周發超等[2]針對Apriori算法中的I/O過載大的問題，提出了一種I_Apriori算法來提高算法效率；孫學波等[3]基于Hadoop平臺，采用HBase文件存儲系統對海量數據分布式存儲以及MapReduce框架進行分布式計算，來實現Apriori數據挖掘算法。

隨著數據量的增加，在分析分類特征數據時，發現不同層之間也存在關聯規則，而Apriori算法只適合對單層數據挖掘關聯規則，針對這一需求，國內外研究學者進行了多層關聯規則算法的研究。Stri_kant等[4]對Apriori算法進行了改進，提出了經典的多層關聯規則Cumulate算法；李進等[5]提出能夠在層次樹上的各個抽象層進行的多層關聯規則；袁冬菊[6]提出基于FP_Growth的約束事務擴展的多層關聯挖掘算法；何晴[7]提出基于聚類的多層關聯規則算法，運用K-means算法與Apriori算法相結合來解決多層關聯規則的問題；于茜[8]提出基于粒度的多層關聯規則算法，使用粒計算進行分層并且基于粒度計算支持度與置信度在農業中進行應用研究；蔣濤等[9]提出將K-means算法與Apriori算法結合的多層關聯規則來分析山洪成因的問題；鄧曉衡等[10]提出基于層次分析法(AHP)和混合Apriori-Genetic的模型。

Cumulate算法繼承了Apriori算法的缺點。本文對Cumulate算法產生不必要冗余項集的缺點進行改進，首先將帶有子孫關系的頻繁1項集在生成候選2項集的過程中直接跳過，不生成此類候選2項集；其次將候選2項集映射到散列表中，將對應統計數小于支持度閥值的桶刪掉。通過上述兩個步驟來搜索頻繁項集，通過實例分析和實驗驗證改進后的算法具有較高的執行效率。

1 預備知識

本文需要關聯規則、散列技術的基本概念以及Cumulate算法思想。其中關聯規則和散列技術的具體概念請參見文獻[11]，Cumulate算法是較為經典的多層關聯規則算法，該算法主要是對單層關聯規則Apriori算法進行改進得來的，其具體思想和優化措施參見文獻[4]。

2 基于散列技術的Cumulate算法

為了克服多層關聯規則Cumulate算法的缺點，本節對此算法進行了改進，改進思想如下：

(1)原算法是在生成候選集之后進行判斷子孫關系進行篩選，本算法是在生成候選項集的過程中將具有子孫關系的冗余項直接刪除。

(2)使用散列技術將候選2項集進行篩選。將候選2項集通過散列函數映射到散列表中，散列表中每個桶設置計數變量count，在映射之后，直接掃描桶中對應的count，將count小于最小支持度的桶刪除，留在桶內的為新的候選2項集，再通過掃描事務集得到頻繁2項集。改進后的算法稱作Hash_Cumulate算法。

Hash_Cumulate算法的流程如圖1所示。

圖1 算法流程

T表示事務數據庫，Min_sup表示最小支持度，L表示T中的頻繁項集。Hash_Cumulate算法偽代碼如下：

算法Hash_Cumulate

輸入：T：事務數據庫。

Min_sup：最小支持度。

輸出：L：T中的頻繁項集。

主方法：

(1)T*=extenion(T); //將事務所有祖先添加進來L1:={frequent 1-itemsets}; //找到頻繁1項集

k=2;

PruneTREE=L1;//將頻繁1項集賦給剪枝的樹

(2)While(Lk-1!=?)do {

(3)Ck=apriori_gen(Lk-1,k) //生成候選集

(4) If(k=2)then{

Ck=hash_candidate(Ck,Min_sup)//改進(2)

}

(5)PruneTREE=cutTree(Ck,PruneTREE)//更新概念樹

(6) for each transcationst∈Tdo {

(7) for each itemx∈tdo{

ancestor=extentionOne(x);//獲取x的祖先

}

(8) for each candidatec∈Ckdo{

If(c∈ancestor)then{

c.frequence++; //得到候選集c的頻數

} }

(9)Lk={x∈Ck|x.frequence≥Min_sup)}//頻繁項集

k:=k+1; }

(10)returnL=∪kLk;

下面的extenion算法描述將事務數據庫T中的事務的所有祖先添加到事務集T*中。

Procedure extenion(T)

(1)for each 事務t∈Tdo{

(2) for each 項x∈tdo{

Temp=findancestorforx; //找到項x的祖先

}

InserttemptoT*//將找到的祖先插入T*

}

(3)returnT*;

下面的apriori_gen算法描述將頻繁k-1項集生成候選k項集，其中Lk-1表示頻繁k-1項集，k表示當前候選集的長度。

Procedure apriori_gen(Lk-1,k){

(1) for each 項集s1∈Lk-1

(2) for each 項集s2∈Lk-1{

//改進(1), 若為子孫關系，直接跳過該循環

(3) If(k=2){

(4) If(s1,s2∈子孫關系)break；

(5) }

(6) If(s1[1]=s2[1])∧(s1[2]=s2[2])…∧

(s1[k-2]=s2[k-2])∧(s1[k-1]<

s2[k-2])then{

(8) If has_infrequent_subset(z,Lk-1)then

(9) Deletez;//剪枝步：刪除非頻繁項集

(10) else addztoCk;

(11) }

}

(12)returnCk;

本算法調用了判斷子集是否為頻繁項集的算法has_infrequent_subset(z,Lk-1)(其中z表示候選k項集，Lk-1表示頻繁k-1項集)。has_infrequent_subset的偽代碼參見文獻[11]。

下面的hash_candidate算法將候選2項集映射到桶中，其中Ck表示候選k項集，Min_sup表示最小支持度閥值。

Procedure hash_candidate(Ck,Min_sup)

(1)for eachc∈Ck{

(2) for eachl1，l2∈c{

//通過散列函數映射到對應桶中

h.num=hash(order(l1),order(l2))

h.count++;

Insertctoh.content;

}

InserthtoH

}

(3)for eachh∈H

//將桶中小于最小支持度的項集刪掉

If(h.count

(4)returnH;

下面的cutTree算法用候選集來剪枝，其中Ck表示候選k項集，PruneTREE表示剪枝樹，newPruneTREE表示剪枝之后的樹。

Procedure cutTree(Ck，PruneTREE)

(1) for eachtree∈PruneTREE

(2) for eachc∈candidate

If(tree∈c)then

//把候選集中存在的項放到新概念樹中

InsertctonewPruneTREE

(3)returnnewPruneTREE;

下面的extentionOne算法描述項的祖先，x表示事務集中的項，Temp表示x的祖先。

Procedure extentionOne(x)

(1)returnTemp=findancestorforx;

算法性能分析:算法Hash_Cumulate是正確的，其時間復雜度為O(x3)，m為事務集中的事務數，n為某事務中項的數量，z為能產生的頻繁項集的最大長度，頻繁k-1項集的數量為x，候選k項集的數量為y。

證明：正確性。算法Hash_Cumulate是通過步驟(3)和步驟(4)對Cumulate算法進行改進。步驟(3)對應生成候選集的函數apriori_gen，apriori_gen的步驟(3)完成Hash_Cumulate算法改進(1)，即在尋找頻繁2項集過程中，對生成候選2項集的過程改進，在生成候選2項集過程中判斷兩項是否具有子孫關系，將具有子孫關系的兩項跳過。Hash_Cumulate中的步驟(4)對應hash_candidate，hash_candidate將候選2項集進行散列映射篩選出新的候選2項集，從而減少冗余候選2項集，完成算法思想改進(2)，滿足Hash_Cumulate算法思想，所以算法是正確的。

時間復雜度分析:本算法的時間復雜度主要由主方法的步驟(1)和步驟(2)決定，(1)的執行次數由extenion算法中的雙重循環決定，其中外層循環extenion算法中的(1)的執行次數由事務集中的事務數m決定，extenion算法中的內層循環(2)的執行次數由事務中的項數n決定，所以主方法的(1)的執行次數為m×n。主方法的(2)的執行次數是由(2)本身及其內部的循環決定，(2)本身的執行次數由算法能找到的頻繁項集的最大長度z決定，內部循環包括步驟(3)、步驟(4)和步驟(6)，主方法的步驟(3)的執行次數由apriori_gen函數中的雙重循環決定，其中外內層循環apriori_gen函數中的(1)、(2)的執行次數都由頻繁k-1項集的數量x決定，內層循環apriori_gen函數中的(2)包括has_infrequent_subset算法，它的執行次數也由頻繁k-1項集的數量x決定，所以主方法的步驟(3)的執行次數為x3；主方法的步驟(4)由算法hash_candidate決定，它的執行次數由候選k項集的數量y決定；主方法的步驟(6)循環嵌套兩個內層循環，即主方法的步驟(7)和步驟(8)，主方法的步驟(6)的執行次數由事務集中的事務數量m決定，主方法的步驟(7)的執行次數由事務中的項的數量n決定，主方法的步驟(8)的執行次數由候選k項集的數量y決定，所以主方法的步驟(6)的執行次數為m×n+m×y。綜上所述，本算法的執行次數為m×n+z×(x3+y+m×n+m×y)，通常情況下，z和n遠小于x，m和y略大x，所以算法時間復雜度為O(x3)。

3 實例分析

本節通過實例對Cumulate算法和Hash_Cumulate算法進行分析，說明Hash_Cumulate算法較好的原因。表1給出某商場銷售事務數據庫D，D中包括6個事務，設最小支持度為2，置信度為60%。

表1 事務數據庫D

通過分析表1發現項間是有層次的，對表1的事物集重新進行概念分層，得到事務表分層如圖2所示。

圖2 事務分層

步驟1 算法先將事務表D擴展，將每一項的祖先全部添加進去，計算每一項及其祖先的支持度，得到滿足最小支持度為2的頻繁1項集，見表2。

表2 頻繁1項集及其支持度

步驟2 進行連接剪枝，得到候選2項集，見表3。

步驟3 判斷表3中項集中項的關系，如果是祖孫關系，則刪除該候選2項集。進行這次篩選后得到的結果見表4。

表3 候選2項集

步驟4 在候選集中不包含的項但事務集中包含的項，在事務集中需刪除。由表4候選集可知，在事務集中刪除項{Pant}、{Shirt}。

表4 篩選后的候選2項集

步驟5 進行最小支持度篩選后，得到頻繁2項集見表5。

表5 頻繁2項集

步驟6 由于找不到頻繁3項集，算法終止。

步驟7 根據置信度來得到關聯規則見表6。

表6 關聯規則

Hash_Cumulate算法步驟如下：

步驟1 同上。

步驟2 候選2項集中不能包含有子孫關系項，所以將這些候選項在存在子孫關系的項 {{Clothes，Jacket}，{Clothes，Outerwear}，{Jacket，Outerwear}，{Hikingboot，Footwear}，{Hikingboot，Shoes}} 直接跳過，這樣直接節省部分保存候選2項集的空間，改進后的步驟2直接得到的候選集見表4。

步驟3 選擇散列函數為：hash(x,y)=(order(x)×4+order(y))mod prime(k), 其中order(x)表示x在項集中的編號，order(y)表示y在項集中的編號，prime(k)返回在k范圍內最大的素數，k表示事務集中的事務數，例如：在頻繁1項集中Clothes的編號為1，Shoes的編號為6，事務數為6，6的范圍內最大素數是5，所以帶入哈希函數得到桶地址為0，則將候選2項集{Clothes，Shoes}放入桶地址為0的桶中。將所有候選2項集散列映射到桶中，產生沖突的候選項放入桶中并增加對應的桶計數見表7，最后將計數小于最小支持度的桶內的項刪除，即將桶地址為0中的候選2項集刪掉，桶中剩余的候選2項集即桶1、2、3、4中的候選2項集與事務集進行比較，產生頻繁2項集，通過這個方法減少2項集的數量，最終得到候選2項集見表8。

表7 散列表

表8 篩選后的候選2項集

步驟4～步驟7與上述未改進時相同，最后根據相同的置信度60%得到的關聯規則也如表6所示。

通過上述實例分析，上述改進主要是對候選2項集進行縮減，從改進算法的步驟2可以直接得出原來Cumulate算法的步驟3所得的結果，可以看出改進算法的優越性，從表8中可以看出候選2項集對比之前確實減少了，從而縮短算法運行時間，實例證明該改進確實將候選2項集的個數減少，提高算法運行效率。

4 Hash_Cumulate算法的實驗及性能分析

為對比分析Hash_Cumulate算法與原始Cumulate算法的運行效率，將這兩種算法在相同的數據記錄下的執行時間進行比較。

實驗環境：操作系統為Windows 7，64位，內存容量為8 G，測試工具為MyEclipse2014，語言為JAVA，采用模擬數據IBM數據集T10I4D100K進行測試，設置最小支持度為0.2。

(1)本實驗將已經處理好的數據對兩種算法進行運行時間的比較。分別對相同的多條事務處理的時間比較見表9，其中k表示1000。

表9 實驗結果對比

為更清晰展示算法時間的對比，時間的折線對比如圖3所示。

圖3 時間對比

(2)在算法空間上分析比較。在算法思想改進(1)中，在未生成候選2項集之前判斷其子孫的關系，從而將不存在子孫的關系的候選2項集進行存儲，節省了之前存儲冗余2項集的空間。在支持度為0.2情況下，事務為10 000條，事務的最大層數為3層，若頻繁1項集有3000個，則最多約可節省的空間為12 000個字節。

(3)實驗進行了算法準確率的比較，算法的準確率比較結果見表10。

表10 算法準確率

5 結束語

本文針對Cumulate算法存在的問題，提出了減少冗余候選2項集的改進算法，首先在候選2項集生成的時候判斷其關系，并且在生成候選2項集之后將散列技術應用于篩選候選2項集，從而減少候選2項集的數量。將改進的算法和原始算法在性能上比較和分析，發現改進算法從時間和空間上都具有良好的性能。在未來，將引進多維算法，實現多維多層的關聯規則算法。