基于布爾矩陣的關聯規則算法研究

摘 要：針對可快速在大型交易事務數據庫中挖掘關聯規則的問題，基于布爾矩陣提出一種新的挖掘算法。該算法通過僅需存儲布爾位節約了內存，通過簡單布爾運算提高了求解頻繁項集的效率。實驗證明該算法較之于Apriori 算法有更好的性能。

關鍵詞：數據挖掘；關聯規則；矩陣；Apriori算法；頻繁項集

中圖分類號：TP301．6 文獻標志碼：A

文章編號：1001-3695(2008)07-1964-03



Research of association rules algorithm based on Boolean matrix

FANG Weiwei1，2，YANG Bingru1，SONG Wei1，HOU Wei1

(1.School of Information Engineering， University of Science Technology Beijing， Beijing 100083， China；2.Information Center， Beijing University of Information Science Technology， Beijing 100192， China)

Abstract:For improving efficiency in data mining from transaction database， the paper proposed a new algorithm based on Boolean matrix， it saved memory by only storing Boolean bit， and solved frequent itemset faster by Boolean operation. Experiment proves that the new algorithm has better capability compared with Apriori algorithm.

Key words:data mining;association rule；matrix；Apriori algorithm；frequent itemset

0 引言

近年來隨著數據庫技術、人工智能和數理統計等技術的發展， 數據庫中的知識發現(KDD) 和數據挖掘技術(DM) 應運而生。在事務數據庫中挖掘關聯規則是數據挖掘的重要研究方向，它是由Agrawal等人于1993 年首先提出的， 是KDD 研究的重要內容。其最初提出的動機是針對購物籃分析問題，目的是為了發現事務數據庫中不同商品之間的聯系規則， 這些規則刻畫了顧客購買行為模式， 可以用來指導商家科學地安排進貨及貨架設計等。之后關聯規則挖掘在基因分析、金融證券分析、電信和保險業等領域的成功應用更體現出它的巨大發展潛力和應用前景^[1]。

最著名的關聯規則挖掘算法是Agrawal于1994年提出的Apriori 算法^[2]。Apriori 算法的基本思想是基于頻繁項集理論的遞推方法， 核心是用前一次掃描數據庫的k項頻繁集產生本次的(k+1)項候選頻繁集。但由于數據庫的規模通常很龐大，每次迭代時產生候選項集需要首先判斷兩個k項集是否與前(k-1)項相同且最后一項不同，以及判斷一個項集是否為另一個項集的子集；然后統計其支持度。這兩個步驟非常耗時。目前，眾多學者針對Apriori算法的不足，提出了許多較好的改進或擴展方法，如頻繁閉項集法^[3]、DHP法^[4]、Partition法^[5]、FPGrowth法^[6]、閉包項集格^[7]、TBAR算法^[8]、動態剪枝^[9]等。盡管這些算法各具優點且挖掘的性能和效率均明顯高于傳統的Apriori算法，但總的來說，算法仍較復雜。特別地，當項目集維數較大時，這些算法的挖掘效能仍然較低。

為了方便、快速地從事務數據庫中挖掘出頻繁項集，本文提出了一種簡單、實用的基于布爾矩陣的有效挖掘方法。首先，將事務數據庫映射到布爾矩陣；然后針對布爾排序矩陣的列向量應用向量內積運算，找出頻繁項集可能存在的列以達到逐步濃縮布爾矩陣列向量的目的；最后從濃縮的布爾矩陣中快速、直觀地歸納出事務數據庫要找的頻繁項集。該算法只需對事務數據庫進行一次掃描，能大量減少I/O 次數；其次對項目支持度的計算變為對二進制的運算，降低了算法的實現難度。

1 關聯規則的基本概念

令I={i1，i2，i3，…，im}是挖掘數據庫D中所有項的集合，集合T={t1，t2，t3，…，tn}是所有事務的集合，包含零個或多個項的集合稱為項集。如果項集X是事務ti的子集，則稱事務ti包含項集X。在事務集T中包含項集X的事務個數稱為項集X的支持度計數M(X)。

定義1 關聯規則是指滿足指定條件的，如下形式的一種蘊涵：X→Y。其中：XI，YI且X∩Y=；X稱為規則前件；Y稱為規則后件。

關聯規則的強度可用客觀興趣度度量。客觀興趣度度量是一種評估關聯模式質量的數據驅動方法，用從數據推導出的統計量來確定模式是否是有趣的，常用支持度和置信度來衡量。

定義2 規則X→Y的支持度表示為S(X→Y)=M(X∪Y)/N。其中：M(X∪Y)表示時間X和Y同時出現的支持度計數；N表示事務集T的事務總數。

定義3 規則X→Y的置信度表示為C(X→Y)=M(X∪Y)/M(X)，用其度量通過規則進行推理的可靠性。

定義4 挖掘關聯規則問題就是在給定的交易數據庫D中，產生所有滿足最小支持度閾值(min_sup) 和最小置信度閾值(min_conf)的關聯規則過程。

挖掘關聯規則的原始方法是計算每個可能規則的支持度和置信度，從一個包含m個項的數據集提取的可能規則的總數為3m-2m+1+1，使用min_sup=20%和min_conf=50%，則有80%以上的規則將被丟棄，使得大部分計算是無用的。為了提高關聯規則挖掘算法性能，通常采用拆分支持度和置信度要求的策略，將關聯規則挖掘任務分解為兩個主要的子任務：

a）頻繁項集產生。其目標是發現滿足最小支持度閾值的所有項集，這些項集稱為頻繁項集。

b）規則的產生。其目標是從上一步發現的頻繁項集中提取所有高置信度的規則，這些規則稱為強規則。

第二個子任務相對簡單，首先通過找到的頻繁項集產生候選規則，然后通過最小置信度閾值篩選出強規則。目前的研究工作幾乎都是集中在第一個子任務，挖掘算法都是針對盡可能地提高頻繁項集發現的速度和效率而提出的。本文提出的基于布爾矩陣的關聯規則快速挖掘算法，通過只掃描一次事務數據庫，把數據庫構造成只包含0和1的布爾矩陣，把對數據庫事務中項的掃描轉為對矩陣內0，1的掃描，節約了存儲設備I/O時間。通過對布爾矩陣的直接運算，達到查找頻繁項集的目的，大大提高了挖掘的效率。

2 基于布爾矩陣的關聯規則算法

2．1 布爾矩陣表示

對于任一給定的事務數據庫D，令

其中:i=2，…，m;j=1，2，…，n。

例如，對于給定的一個事務數據庫D^[9]，如表1所示。第一列中所出現的T1，T2，…，T7表示該事務數據庫中記錄的七項事務；第二列中所出現的I1，I2，I3，I4，I5，I6，I7表示事務數據庫中所包含的項目。例如第二行記錄的是事務T1，在該事務中所涉及到的項目有I1，I2，I4，I5。事務數據庫D經一次掃描后，就可在f的作用下映射成布爾矩陣R。

在布爾矩陣R中，每一列表示項目，第一行為標志位，0代表候選頻繁項集，1代表非頻繁項集。初始化該布爾矩陣時，第一行全設定為0，表示算法在執行前每個項目都有可能成為頻繁項集；第二~八行表示數據庫當中的七個事務，任一項tij（當i>1）表示事務Ti-1中出現項目Ij的情況，1代表事務Ti-1中出現了項目Ij，0代表事務Ti-1中沒有出現了項目Ij。例如布爾矩陣中的第二行就表示在事務T1中出現了I1，I

2．2 向量內積

對于事務數據庫D中的每一項Ij的向量定義^[10]為Rj=(t2j，t3j，…，tnj)，Ij的支持度support(Ij)=t2j+…+tnj，如項目I1的支持度support(I

定義5 項集{Ii，Ij}的向量內積表示為Rij=Ri∧Rj=(t2i∧t2j，t3i∧t3j，…，tni∧tnj)。其中“∧”表示邏輯與運算。2項集{Ii，Ij}的支持度support(Iij)= t2i∧t2j＋t3i∧t3j＋…＋tni∧tnj。例如項目I1和I2的向量內積support(I12)= t21∧t22＋t31∧t32＋…＋t71∧t72＝1×1＋0×1＋0×1＋1×1＋1×0＋1×1＋1×0＝3，其含義是在整個事務數據庫D的所有事務記錄中同時出現I1和I2的事務記錄有三個。

定義6 K項集{Ii，Ij，…，IK}的向量內積表示為Rij…K=Ri∧Rj∧…∧RK，K項集{I

2．3 算法思想

對于任意一個事務數據庫只需掃描一次，即可獲得與該數據庫相對應的一個布爾矩陣。故對事務數據庫的挖掘問題就可轉換為對其布爾矩陣的分析。本文所提出的算法用到Apriori算法中先驗原理，即如果一個項集是頻繁的，則它的所有子集一定也是頻繁的；相反如果一個項集是非頻繁的，則它的所有超集也一定是非頻繁的。核心思想如下：

a）按照式（1）所述，將原始事務數據庫D轉換成布爾矩陣R。

b）求出每個項目的支持度，如本例中I1=4，I2=5，I3=2，I4=2，I5=1，根據設定的最小支持度閾值min_sup＝2判斷頻繁1項集為{I1，I2，I3，I4}，并將所有非頻繁項集的標志位改為1，在本例中需要更改t51=1。

c）將所有頻繁1項集按照定義5求向量內積，如I12=3，I13=1，I14=2，I23=1，I24=3，I34=0；然后再根據min_sup＝2判斷頻繁2項集為{I12，I24，I24}，并將新產生的非頻繁項集的標志位改為1，如t31=1。

d）將對所有頻繁k項集按照定義6求向量內積，然后根據min_sup判斷頻繁(k+1)項集，并將新產生的非頻繁項集的標志位改為1。例如本例中在求頻繁3項集時，I124=2，即產生頻繁3項集是{I124}。因沒有產生非頻繁項集，所以不修改任何標志位。

e）重復d）直到沒有更大的頻繁項集產生。本例中最大頻繁項集就是3項集，因此循環結束。

f)根據定義3和4，求出cof(I124)=P(I124)/P(I12) =67%。由設定mis_cof=40%可判斷該規則I1，I2→I4為關聯規則，即當有一事務出現項目I1，I2時，就有67%的可能性也出現項目I4。 

3 算法分析 

為了驗證該算法的先進性，在Intel(R) Xeon(TM)MP CPU 2．80 GHz，3.50 GB內存，Windows Sever 2003 Enterprise操作系統的實驗環境下， 算法采用C++語言實現。采用的數據集為T40I10D100K(該數據庫共有100 000記錄，942個屬性，記錄的平均長度為40.5)，可以從頻繁項集挖掘實現資源庫下載^[11]。將本文所述的優化算法與Apriori 算法進行比較，圖1給出了兩種算法當所給支持度不同時執行時間的差別。由圖1可知，當最小支持度越小，優化后算法的執行時間比經典Apriori 算法的執行時間少得越多，這說明優化后的算法在給出支持度較小時具有較高的執行效率。圖2給出了兩種算法當數據庫中事務記錄數不同時執行時間的差別。由圖2可知，當事務記錄適當大時，優化后算法的效率比經典Apriori 算法的效率要高一些，這說明優化后的算法在所給數據庫中記錄較大時具有較高的執行效率。

3．1 時間復雜性分析

Apriori 算法在執行過程中需多次掃描數據庫，其時間復雜度為O(|D|K)。其中：|D|表示交易事務數據庫中所包含的交易數量；k表示待發現的頻繁項集的大小。本文提出的優化算法與Apriori 算法相比，只需掃描事務數據庫一次。當轉換成布爾矩陣后，事務數據庫不再使用。在求頻繁k項集時，通過對布爾矩陣的列求k維支持度， 不需要對頻繁(k-1)項集進行連接， 也不需要對k項候選集進行剪枝和模式匹配的操作。在計算過程中對布爾矩陣通過標志非頻繁項集列進行了有效的減裁， k值越大， 求k維支持度的計算量越小，其時間復雜度為O(nmk)。其中：m為修剪后矩陣的列數；n為修剪后矩陣的行數。由于實際應用中，交易數據庫交易數量遠遠大于商品的數量，即|D|>>m，本算法較Apriori算法有更好的時間特性。

3．2 空間復雜性分析

Apriori算法在執行過程中會產生大量的候選項集，并需要將其存儲在內存中供剪枝和生成頻繁項集使用，而本文提出的算法在執行過程中不需要存儲所有候選集，僅需存儲布爾值“0”和“1”， 可以位方式進行存儲。這樣大大節省了存儲空間，具有良好的空間特性。

4 結束語

為了對大型事務數據庫進行關聯規則挖掘，本文基于布爾矩陣及先驗原理提出了一種優化算法，較之于Apriori 算法需頻繁進行I/O操作以及生成大量候選集的缺陷，該算法在執行過程中只需掃描事務數據庫一次，將事務數據轉換為布爾值， 并以位方式存儲， 節省了大量的內存空間；并直接通過布爾運算產生頻繁項集， 因此有效地解決了Apriori算法迭代產生頻繁項集的瓶頸問題，提高了發現頻繁項集的效率。通過實驗證明，該算法較Apriori算

法在時間復雜性和空間復雜性上均有所改善，具有良好的性能。

參考文獻：

［1］史忠植.知識發現[M]. 北京:清華大學出版社，2002:5-6. 

［2］AGRAWAL R.Mining association rules between sets of items in large database[C]//Proc of International

Conf on Management of Data.Washington DC:ACM SIGMOD，1993:207-216.

［3］PARK J S，CHEN M S，YU P S.An effective hash based algorithm of association rules[C]//Proc of

International Conference on Management of Data.Washington DC:ACM SIGMOD，1995:175186.

［4］SAVASERE A，OMIECINSKI E，NAVATHE S.An efficient algorithm of association rules in large database[C]//Proc of International Conference on Management of Data.Washington DC:ACM SIGMOD，1995:432-443.

［5］PASQUIER N，BASTIDE Y，TAOU IL R，et al.Discovering frequent closed itemsets for association rules[C]//Proc of ICDT1999.Israel:[s.n.]，1999:398-416.

［6］HAN J，PEI J，YIN Y.Mining frequent patterns without candidate generation[C]//Proc of the 2000 ACM SIGMOD Internal Conference on Management of Data.Dallas，Texas:ACM Press，2000:112.

［7］PASQUIER N，BASTIDE Y，TAOU I L.Efficient mining of association rules using closed itemset[J]. Information System，1999，24(1):25-46.

［8］BERZAL F，CUBERO JC，MARIN N.TBAR:An efficient method for association rule mining in relational databases[J].Data Knowledge Engineering，2001，37:47-64.

［9］ HAN Jiawei，KAMBR M.Data mining:concepts and techniques[M].Beijing:Higher Education Press，2001:232-233.

［10］李超，余小平.基于矩陣的Apriori算法的改進方法[J ].計算機工程，2006(23)：68-69.

［11］Frequent itemset mining implementations repository[EB/OL].http://fimi.cs.helsinki.fi/.

［12］徐章艷，張師超，區玉明，等.挖掘關聯規則中一種優化的Apriori 算法[J].小型微型計算機系統，2005，29（19）:83 84.

［13］皮德常，秦小麟，王寧生.基于動態剪枝的關聯規則挖掘算法[J].小型微型計算機系統，2004，25（10）:18501852.

［14］牛小飛，石冰.基于向量和矩陣的挖掘關聯規則的高效算法[J].計算機工程與應用，2004，40（12）:170 173.

［15］陳剛，李秀，劉文煌.基于新穎度的關聯挖掘算法[J].微計算機信息，2006，32：81-83.

［16］陳文慶，許棠.關聯規則挖掘Apriori算法的改進與實現[J].微機發展，2005，15:155157.

［17］施毅，陸廷金，劉劍峰.飛機加油多服務臺排隊系統模型仿真分析[J].微計算機信息，2006（3S）:265-268.

［18］胡慧蓉，王周敬.一種基于關系矩陣的關聯規則快速挖掘算法[J].計算機應用，2005，25（7）:15771579.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。”