一種基于逆序編碼性質(zhì)的Apriori算法改進(jìn)

張華飛，董黎剛，王 盛

(浙江工商大學(xué)信息與電子工程學(xué)院，浙江杭州310018)

0 引言

隨著關(guān)聯(lián)規(guī)則［1］挖掘概念的提出，經(jīng)典的Apriori算法［2］逐漸在該領(lǐng)域被廣泛的應(yīng)用。為應(yīng)付日益膨脹的數(shù)據(jù)量，當(dāng)前挖掘算法結(jié)合多種策略進(jìn)行改進(jìn)，如基于剪枝技術(shù)的Apriori改進(jìn)算法［3］，采用HAPPI結(jié)構(gòu)的算法［4］，采用PLT結(jié)構(gòu)的算法［5］，DMFIA算法及UMFIA算法［6］。這些算法改進(jìn)預(yù)處理技術(shù)以提高挖掘效率但較大幅度增大了系統(tǒng)開銷，預(yù)處理后的數(shù)據(jù)，無法對原始數(shù)據(jù)進(jìn)行很好的回溯，對于新增加的項(xiàng)目，轉(zhuǎn)換后的數(shù)據(jù)對新數(shù)據(jù)無法兼容，必須整體重新掃描生成數(shù)據(jù)，這種特性降低了數(shù)據(jù)分析的效率，也增加了系統(tǒng)的開銷。同時，這些算法對當(dāng)前基于網(wǎng)絡(luò)的分布式數(shù)據(jù)庫系統(tǒng)的數(shù)據(jù)分析兼容性存在不足。再如結(jié)合壓縮事物信息技術(shù)的算法［7］，這些算法改進(jìn)幅度較小，性能提升有限。另外，位向量以其運(yùn)算簡單，存儲容量要求相對較低的優(yōu)點(diǎn)為算法的改進(jìn)方向提供了一些思路［8］。一種基于位向量的BF-Apriori算法［9］較好地克服了以上算法適用性范圍狹窄的問題，但其性能方面依然存在問題。為此，本文將針對該算法性能上的不足，做進(jìn)一步的改進(jìn)，提出BF_Advanced-Apriori算法。

1 主要定義和性質(zhì)

為了描述BF_Advanced-Apriori算法，根據(jù)B-Apriori算法描述給出定義1，定義2［8］，根據(jù)BF-Apriori給出性質(zhì)1［9］，并增補(bǔ)兩條性質(zhì)，性質(zhì)2及性質(zhì)3。

定義1 事務(wù)－位向量(項(xiàng)目集－位向量)的編碼關(guān)系。給定I={I1，I2，…，Im}(項(xiàng)目按其支持度大小逆序排列，m為數(shù)據(jù)庫包含的項(xiàng)目總數(shù)，限于篇幅，下面將不再說明)。事務(wù)數(shù)據(jù)庫表示為D，事物T∈D(項(xiàng)目集X)，并且T?I(X?I)，規(guī)定f:T ×I(X ×I)→b1b2b3…bk(1≤k≤m，k值為事務(wù)T(項(xiàng)目集X)中存在項(xiàng)目的逆序位置序號最大值)，并稱b=b1b2b3…bk為事務(wù)T(項(xiàng)目集X)所對應(yīng)的位向量，記為 Bt(Bx)，其中 bj∈{0，1}，若事務(wù)中包含 Ij，則 bj=1，否則 bj=0，j=1，2，…，k。

定義2 長度Length。給定I={I1，I2，…，Im}及位向量Bt(Bx)。將Bt(Bx)包含位值1的數(shù)目稱為Bt(Bx)的長度，記為Length(Bt(Bx))。

性質(zhì)1 若項(xiàng)目Ix在頻繁項(xiàng)集Lk－1中出現(xiàn)的次數(shù)小于k－1次，那么Ix就不可能是頻繁項(xiàng)集Lk的元素。

證明 由頻繁項(xiàng)集的定義可知，頻繁項(xiàng)集的任一子集都是頻繁的。頻繁項(xiàng)集Lk的k－1維子集意味著在k個項(xiàng)中去掉一個，那么每一項(xiàng)目在Lk的k－1維子集中出現(xiàn)的次數(shù)等于k－1次，所以若某一項(xiàng)目在頻繁項(xiàng)集Lk－1中出現(xiàn)的次數(shù)小于k－1次，那么它就不可能是頻繁項(xiàng)集Lk的項(xiàng)，性質(zhì)1得證。

性質(zhì)2 給定 I={I1，I2，…，Im}，對于 k 項(xiàng)集 X1，X2，對應(yīng)位向量分別為 Bx1，Bx2，Length(Bx1)=Length(Bx2)=k，當(dāng)且僅當(dāng)Length(Bx1xor Bx2)=2時，項(xiàng)集X1與X2有且只有k－1個元素相同。

證明 因?yàn)長ength(b1xor b2)=2，根據(jù)邏輯“異或”的定義，項(xiàng)目集X1，X2必有兩個位值相異，相異的情況是{(0，1)，(1，0)}，{(1，0)，(0，1)}，{(1，0)，(1，0)}，{(0，1)，(0，1)}，而當(dāng) Length(b1)=Length(b2)=k 時，相異的的情況只能是{(0，1)，(1，0)}或{(1，0)，(0，1)}，所以項(xiàng)集 X1 與 X2 有且只有k－1個元素相同，性質(zhì)2得證。

性質(zhì)3 給定I={I1，I2，…，Im}，I中前k個項(xiàng)目的支持度計數(shù)大于最小支持度minsup。那么候選頻繁項(xiàng)集在匹配時，僅需匹配前k項(xiàng)。

證明 根據(jù)Apriori算法的原理，候選頻繁項(xiàng)集的組成項(xiàng)目來源于頻繁的項(xiàng)(項(xiàng)支持度計數(shù)大于閾值的項(xiàng))，所以，在逆序編碼情況下，匹配過程僅需匹配前k項(xiàng)，性質(zhì)3得證。

2 數(shù)據(jù)處理及規(guī)則挖掘

假設(shè)I={I1，I2，…，Im}是m個項(xiàng)的集合(m為數(shù)據(jù)庫所涉及項(xiàng)目的總數(shù)且項(xiàng)目按項(xiàng)目支持度(概率)從大到小排列)，事物T構(gòu)成數(shù)據(jù)庫D。T?I，T?D，項(xiàng)的集合X同樣滿足X?I，X?D，minsup表示最小支持度閾值，X.sup表示項(xiàng)集X在事務(wù)數(shù)據(jù)庫D中所對應(yīng)的支持度計數(shù)。

圖1 RC算法示例

2.1 數(shù)據(jù)預(yù)處理算法

算法1 逆序編碼算法RC

根據(jù)定義1給出的事務(wù)－位向量編碼定義和規(guī)則，本文給出了的RC算法示例，如圖1所示。

顯然，RC算法空間效率提升的具體程度要根據(jù)具體的項(xiàng)目支持度的分布情況而定。

而RC算法的理論平均時間復(fù)雜度為O(n)，此處n代表事物數(shù)?？臻g復(fù)雜度為S(1)。

2.2 規(guī)則生成頻繁k－項(xiàng)目集算法

算法2 候選頻繁項(xiàng)集生成算法CFIG

輸入:頻繁k－1項(xiàng)目集Lk－1輸出:候選頻繁k項(xiàng)目集Ck

☆ BL(k－1)={Bx|X∈Lk－1};//BL(k－1)為 Lk－1對應(yīng)的位向量集合

☆BC(k)={Bx|X∈Ck};//BC(k)為Ck對應(yīng)的位向量集合

☆ For all Ik－1∈ Lk－1do begin // 遍詢 Lk－1的項(xiàng)目 Ik－1

☆ If(IFrek－1＜ k －1)then Ij=Ik－1and Lk－1=Lk－1－ Lk－1(Ij);//IFrek－1為項(xiàng)目 Ik－1在 Lk－1中出現(xiàn)的頻率。刪除包含項(xiàng)目Ij的Lk－1元素，見性質(zhì)1

☆End

☆ For all Mb∈ BL(k－1)，Nb∈ BL(k－1)do begin //Mb，Nb 分別為集合 BL(k－1)中任意兩個元素

☆MN=Mbxor Nb;

☆I(lǐng)f(Length(MN)=2＆＆MN?BC(k))then BC(k)=BC(k)∪ MN;//MN包含位值1的個數(shù)為2，則MN加入BC(k)，見性質(zhì)2

3）存儲管理。利用Qt的文件類QFile和數(shù)據(jù)庫SQL模塊等，進(jìn)行自動存儲管理，如記錄ROV狀態(tài)信息、清理臨時文件等。

☆End

顯然，CFIG算法減少了頻繁項(xiàng)集拼接時產(chǎn)生的部分候選項(xiàng)集。CFIG算法的理論平均時間復(fù)雜度為O(n2)，此處n代表k－1頻繁項(xiàng)集數(shù)目?？臻g復(fù)雜度為S(1)。

算法3 基于逆序編碼的模式匹配算法PMRC

輸入:候選頻繁k項(xiàng)目集Ck輸出:頻繁k項(xiàng)集Lk

☆BC(k)={Bx|X∈Ck}; //BC(k)為Ck對應(yīng)的位向量集合

☆BL(k)={Bx|X∈Lk}; //BL(k)為Lk對應(yīng)的位向量集合

☆ BL(k)=Φ; //BL(k)初始為空集

☆BT={Bx|X∈T};//BT為事物T對應(yīng)的位向量集合

☆ For all Pb∈ BTdo begin//遍詢事物集

☆For all Qb∈ BC(k)do begin //遍詢候選頻繁項(xiàng)集

☆I(lǐng)f(Qb=Pband Qb)then Qb.sup++;//匹配，該過程僅在位向量包含頻繁項(xiàng)目的一端m位(m為頻繁一項(xiàng)集L1的數(shù)目)進(jìn)行，見性質(zhì)3

☆End //Ck的匹配計數(shù)結(jié)束

☆For all Qb∈ BC(k)do begin//遍詢候選頻繁項(xiàng)集

☆ If(Qb.sup＞minsup)BL(k)=BL(k)∪ Qb;//篩選大于最小頻繁支持度的Ck作為Lk

☆End

PMRC算法性能分析:假設(shè)數(shù)據(jù)庫包含M條事物，N個項(xiàng)目，在支持度minsup下有s項(xiàng)頻繁項(xiàng)，且以1位運(yùn)算為基本運(yùn)算量單位(其他定義同上)。那么模式匹配過程，PMRC算法所需匹配的模式長度為:

運(yùn)算量為:

僅基于位向量的模式匹配算法所需匹配的模式長度為:

運(yùn)算量為:

使用PMRC算法而減少的運(yùn)算量占比:

由分析結(jié)果可以看出，最小支持度minsup取值越大，s越小，PMRC算法的性能也就提升越明顯。PMRC算法的理論平均時間復(fù)雜度為O(n*m)，此處n代表事物數(shù)，m為候選頻繁項(xiàng)集數(shù)目，且m＜＜n?？臻g復(fù)雜度為S(1)。

2.3 BF_Advanced-Apriori算法的性能驗(yàn)證

為了驗(yàn)證算法性能，本文在電腦上實(shí)現(xiàn)了BF_Advanced-Apriori算法和B-Apriori算法(同屬于一類算法)［8］生成3 － 頻繁項(xiàng)集。實(shí)驗(yàn)采用由 Tom Brijs提供的 retail數(shù)據(jù)集(http://fimi.cs.helsinki.fi/data/)，在支持度閾值為1 000的情況下，擷取不同大小的數(shù)據(jù)集(單位:條)10 000，20 000，…，80 000，88 162分別進(jìn)行3－頻繁項(xiàng)集的挖掘，算法執(zhí)行時間如圖2所示。

從圖2可以看出，BF_Advanced-Apriori算法的執(zhí)行效率明顯優(yōu)于B-Apriori算法，并且隨著數(shù)據(jù)集的增大，BF_Advanced-Apriori算法和 B-Apriori算法的性能差距在逐步擴(kuò)大。

圖2 3－頻繁項(xiàng)集挖掘的算法執(zhí)行時間

3 結(jié)束語

本文以B-Apriori的位向量數(shù)據(jù)結(jié)構(gòu)為前提，設(shè)計完成了基于BF-Apriori逆序編碼技術(shù)的Apriori改進(jìn)算法BF_Advanced-Apriori.該算法保留了位向量易于轉(zhuǎn)換，運(yùn)算簡單的優(yōu)點(diǎn)，并有效克服了其空間性能不足的缺陷，同時，所涉及技術(shù)大幅度提升了算法的時間效率。改進(jìn)算法能令新數(shù)據(jù)兼容已轉(zhuǎn)換的數(shù)據(jù)，其所具有數(shù)據(jù)高可壓縮性和可分割性，為大幅提升分布式系統(tǒng)間的交互效率提供了條件?？梢?，BF_Advanced-Apriori算法在海量數(shù)據(jù)的知識挖掘中將更加有效快速。

［1］ Agrawal R，Imielinske T，Swami A.Mining association rules between sets of items in large databases［C］.New York:ACM Press，1993:207 －216.

［2］ Agrawal R，Srikant R.Fast algorithms for mining association rules in large databases［C］.San Francisco:Morgan Kaufmann，1994:487－499.

［3］ 何海濤，呂士勇，田海燕.基于改進(jìn) Apriori算法的數(shù)據(jù)庫入侵檢測［J］.計算機(jī)工程，2009，35(16):154－158.

［4］ Wen Yinghsiang，Huang Jenwei，Chen Mingsyan.Hardware.Hardware-enhanced association rule mining with hashing and pipelining［J］.IEEE Trans on Knowledge and Data Engineering，2008，20(6):784－795.

［5］ Boukerche A，Samarah S.A novel algorithm for mining association rules in wireless ad hoc sensor networks［J］.IEEE Trans on Parallel and Distributed Systems，2008，19(7):865－877.

［6］ 宋余慶，朱玉全，孫志揮，等.基于FP-tree的最大頻繁項(xiàng)目集挖掘及更新算法［J］.軟件學(xué)報，2003，14(9):1 586－1 592.

［7］ RathinasabapathyR，Bhaskaran R.Performance comparison of hashing algorithm with Apriori［C］.Washington:IEEE Computer Society，2009:729 －733.

［8］ 陳耿，朱玉全，楊鶴標(biāo)，等.關(guān)聯(lián)規(guī)則挖掘中若干關(guān)鍵技術(shù)的研究［J］.計算機(jī)研究與發(fā)展，2005，42(10):1 785－1 789.

［9］ 王盛，董黎剛，李群.一種基于逆序編碼的關(guān)聯(lián)規(guī)則挖掘研究［J］.杭州電子科技大學(xué)學(xué)報，2010，30(5):169－172.