一種基于逆序編碼性質的Apriori算法改進

張華飛，董黎剛，王 盛

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

0 引言

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

1 主要定義和性質

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

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

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

性質1 若項目Ix在頻繁項集Lk－1中出現的次數小于k－1次，那么Ix就不可能是頻繁項集Lk的元素。

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

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

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

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

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

2 數據處理及規則挖掘

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

圖1 RC算法示例

2.1 數據預處理算法

算法1 逆序編碼算法RC

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

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

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

2.2 規則生成頻繁k－項目集算法

算法2 候選頻繁項集生成算法CFIG

輸入:頻繁k－1項目集Lk－1輸出:候選頻繁k項目集Ck

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

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

☆ For all Ik－1∈ Lk－1do begin // 遍詢 Lk－1的項目 Ik－1

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

☆End

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

☆MN=Mbxor Nb;

☆If(Length(MN)=2＆＆MN?BC(k))then BC(k)=BC(k)∪ MN;//MN包含位值1的個數為2，則MN加入BC(k)，見性質2

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

☆End

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

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

輸入:候選頻繁k項目集Ck輸出:頻繁k項集Lk

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

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

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

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

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

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

☆If(Qb=Pband Qb)then Qb.sup++;//匹配，該過程僅在位向量包含頻繁項目的一端m位(m為頻繁一項集L1的數目)進行，見性質3

☆End //Ck的匹配計數結束

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

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

☆End

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

運算量為:

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

運算量為:

使用PMRC算法而減少的運算量占比:

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

2.3 BF_Advanced-Apriori算法的性能驗證

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

從圖2可以看出，BF_Advanced-Apriori算法的執行效率明顯優于B-Apriori算法，并且隨著數據集的增大，BF_Advanced-Apriori算法和 B-Apriori算法的性能差距在逐步擴大。

圖2 3－頻繁項集挖掘的算法執行時間

3 結束語

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

［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］ 何海濤，呂士勇，田海燕.基于改進 Apriori算法的數據庫入侵檢測［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的最大頻繁項目集挖掘及更新算法［J］.軟件學報，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］ 陳耿，朱玉全，楊鶴標，等.關聯規則挖掘中若干關鍵技術的研究［J］.計算機研究與發展，2005，42(10):1 785－1 789.

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