基于散列技術(shù)的多層關(guān)聯(lián)規(guī)則算法的改進(jìn)

郭 倩，殷麗鳳

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

0 引 言

自從Agrawal等[1]提出挖掘關(guān)聯(lián)規(guī)則Apriori算法以來，眾多學(xué)者針對此算法有較多冗余項(xiàng)集、很大的I/O負(fù)載的缺點(diǎn)做了不斷改進(jìn)，如周發(fā)超等[2]針對Apriori算法中的I/O過載大的問題，提出了一種I_Apriori算法來提高算法效率；孫學(xué)波等[3]基于Hadoop平臺(tái)，采用HBase文件存儲(chǔ)系統(tǒng)對海量數(shù)據(jù)分布式存儲(chǔ)以及MapReduce框架進(jìn)行分布式計(jì)算，來實(shí)現(xiàn)Apriori數(shù)據(jù)挖掘算法。

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

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

1 預(yù)備知識(shí)

本文需要關(guān)聯(lián)規(guī)則、散列技術(shù)的基本概念以及Cumulate算法思想。其中關(guān)聯(lián)規(guī)則和散列技術(shù)的具體概念請參見文獻(xiàn)[11]，Cumulate算法是較為經(jīng)典的多層關(guān)聯(lián)規(guī)則算法，該算法主要是對單層關(guān)聯(lián)規(guī)則Apriori算法進(jìn)行改進(jìn)得來的，其具體思想和優(yōu)化措施參見文獻(xiàn)[4]。

2 基于散列技術(shù)的Cumulate算法

為了克服多層關(guān)聯(lián)規(guī)則Cumulate算法的缺點(diǎn)，本節(jié)對此算法進(jìn)行了改進(jìn)，改進(jìn)思想如下：

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

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

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

圖1 算法流程

T表示事務(wù)數(shù)據(jù)庫，Min_sup表示最小支持度，L表示T中的頻繁項(xiàng)集。Hash_Cumulate算法偽代碼如下：

算法Hash_Cumulate

輸入：T：事務(wù)數(shù)據(jù)庫。

Min_sup：最小支持度。

輸出：L：T中的頻繁項(xiàng)集。

主方法：

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

k=2;

PruneTREE=L1;//將頻繁1項(xiàng)集賦給剪枝的樹

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

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

(4) If(k=2)then{

Ck=hash_candidate(Ck,Min_sup)//改進(jìn)(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的頻數(shù)

} }

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

k:=k+1; }

(10)returnL=∪kLk;

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

Procedure extenion(T)

(1)for each 事務(wù)t∈Tdo{

(2) for each 項(xiàng)x∈tdo{

Temp=findancestorforx; //找到項(xiàng)x的祖先

}

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

}

(3)returnT*;

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

Procedure apriori_gen(Lk-1,k){

(1) for each 項(xiàng)集s1∈Lk-1

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

//改進(jìn)(1), 若為子孫關(guān)系，直接跳過該循環(huán)

(3) If(k=2){

(4) If(s1,s2∈子孫關(guān)系)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;//剪枝步：刪除非頻繁項(xiàng)集

(10) else addztoCk;

(11) }

}

(12)returnCk;

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

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

Procedure hash_candidate(Ck,Min_sup)

(1)for eachc∈Ck{

(2) for eachl1，l2∈c{

//通過散列函數(shù)映射到對應(yīng)桶中

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

h.count++;

Insertctoh.content;

}

InserthtoH

}

(3)for eachh∈H

//將桶中小于最小支持度的項(xiàng)集刪掉

If(h.count

(4)returnH;

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

Procedure cutTree(Ck，PruneTREE)

(1) for eachtree∈PruneTREE

(2) for eachc∈candidate

If(tree∈c)then

//把候選集中存在的項(xiàng)放到新概念樹中

InsertctonewPruneTREE

(3)returnnewPruneTREE;

下面的extentionOne算法描述項(xiàng)的祖先，x表示事務(wù)集中的項(xiàng)，Temp表示x的祖先。

Procedure extentionOne(x)

(1)returnTemp=findancestorforx;

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

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

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

3 實(shí)例分析

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

表1 事務(wù)數(shù)據(jù)庫D

通過分析表1發(fā)現(xiàn)項(xiàng)間是有層次的，對表1的事物集重新進(jìn)行概念分層，得到事務(wù)表分層如圖2所示。

圖2 事務(wù)分層

步驟1 算法先將事務(wù)表D擴(kuò)展，將每一項(xiàng)的祖先全部添加進(jìn)去，計(jì)算每一項(xiàng)及其祖先的支持度，得到滿足最小支持度為2的頻繁1項(xiàng)集，見表2。

表2 頻繁1項(xiàng)集及其支持度

步驟2 進(jìn)行連接剪枝，得到候選2項(xiàng)集，見表3。

步驟3 判斷表3中項(xiàng)集中項(xiàng)的關(guān)系，如果是祖孫關(guān)系，則刪除該候選2項(xiàng)集。進(jìn)行這次篩選后得到的結(jié)果見表4。

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

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

表4 篩選后的候選2項(xiàng)集

步驟5 進(jìn)行最小支持度篩選后，得到頻繁2項(xiàng)集見表5。

表5 頻繁2項(xiàng)集

步驟6 由于找不到頻繁3項(xiàng)集，算法終止。

步驟7 根據(jù)置信度來得到關(guān)聯(lián)規(guī)則見表6。

表6 關(guān)聯(lián)規(guī)則

Hash_Cumulate算法步驟如下：

步驟1 同上。

步驟2 候選2項(xiàng)集中不能包含有子孫關(guān)系項(xiàng)，所以將這些候選項(xiàng)在存在子孫關(guān)系的項(xiàng) {{Clothes，Jacket}，{Clothes，Outerwear}，{Jacket，Outerwear}，{Hikingboot，F(xiàn)ootwear}，{Hikingboot，Shoes}} 直接跳過，這樣直接節(jié)省部分保存候選2項(xiàng)集的空間，改進(jìn)后的步驟2直接得到的候選集見表4。

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

表7 散列表

表8 篩選后的候選2項(xiàng)集

步驟4～步驟7與上述未改進(jìn)時(shí)相同，最后根據(jù)相同的置信度60%得到的關(guān)聯(lián)規(guī)則也如表6所示。

通過上述實(shí)例分析，上述改進(jìn)主要是對候選2項(xiàng)集進(jìn)行縮減，從改進(jìn)算法的步驟2可以直接得出原來Cumulate算法的步驟3所得的結(jié)果，可以看出改進(jìn)算法的優(yōu)越性，從表8中可以看出候選2項(xiàng)集對比之前確實(shí)減少了，從而縮短算法運(yùn)行時(shí)間，實(shí)例證明該改進(jìn)確實(shí)將候選2項(xiàng)集的個(gè)數(shù)減少，提高算法運(yùn)行效率。

4 Hash_Cumulate算法的實(shí)驗(yàn)及性能分析

為對比分析Hash_Cumulate算法與原始Cumulate算法的運(yùn)行效率，將這兩種算法在相同的數(shù)據(jù)記錄下的執(zhí)行時(shí)間進(jìn)行比較。

實(shí)驗(yàn)環(huán)境：操作系統(tǒng)為Windows 7，64位，內(nèi)存容量為8 G，測試工具為MyEclipse2014，語言為JAVA，采用模擬數(shù)據(jù)IBM數(shù)據(jù)集T10I4D100K進(jìn)行測試，設(shè)置最小支持度為0.2。

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

表9 實(shí)驗(yàn)結(jié)果對比

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

圖3 時(shí)間對比

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

(3)實(shí)驗(yàn)進(jìn)行了算法準(zhǔn)確率的比較，算法的準(zhǔn)確率比較結(jié)果見表10。

表10 算法準(zhǔn)確率

5 結(jié)束語

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