基于垂直分布方法的關聯規則算法及改進

楊振華

（西安文理學院 計算機科學系，陜西 西安710065）

數據庫中大量的數據與數據之間存在著某種聯系，這種數據之間的聯系就屬于一種重要的知識，也是進行數據挖掘的對象，即關聯規則挖掘[1]。在眾多的關聯規則挖掘算法中最著名的是Apriori算法[2]。它的基本思想是使用一種逐層搜索的迭代算法。但是Apriori算法也有明顯的缺點：每次都會產生大量的候選頻繁項集，而且候選頻繁項集呈指數級增長。每產生一個頻繁項目集就需要掃描一次完整的數據庫。這些都需要耗費巨大的系統資源而且算法的執行速度、效率也比較低。因此人們提出了許多改進的Apriori算法，本文吸取前人的經驗提出了一種新的改進Apriori算法，稱為Apriori-Evo算法。

1 Apriori算法分析

Apriori算法的基本步驟是：首先掃描事務數據庫D中的事務，統計各個項目出現的次數來產生頻繁項目集L1,然后由 L1×L1進行連接運算生成候選 2-項集 C2，掃描數據庫統計各個候選2-項集出現的次數,確定其中的頻繁 2-項集 L2。再由 L2×L2進行連接運算產生候選3-項集C3，一直反復進行這個過程生成頻繁k-項集Lk，直到無法再生成頻繁項目集為止。

Apriori的算法描述如下：

主算法逐層迭代產生 L1→C2→L2→C3→L3…直到Lk=φ為止。到此所有的頻繁項目集都找到了。

procedure aproiri_gen(Lk-1:frequent(k-1)-itemset;min_sup:support)

代碼中 apriori_gen()函數[3]主要完成兩個動作：連接和剪枝運算。Lk-1與Lk-1進行連接生成候選頻繁項集。然后剪枝部分利用Apriori的性質刪除掉包含非頻繁子集的候選。

Apriori算法的主要缺點是會產生大量的候選項集，如果頻繁1-項集有10 000個，則候選2-項集的個數將超過10 000 000個，算法實現時，大量的候選2-項集都被存放在哈希樹中，對它們的統計和測試所需要的開銷會很大;每產生一個頻繁項目集就需要將整個事務數據庫掃描一遍，大大降低了系統I/O效率。

2 對Apriori算法的改進

關聯規則具有如下性質：

(1)對于項目集 X和它的任意子集 Y，如果 X是頻繁的，則它的子集Y一定也是頻繁的。

(2)對于項目集 X和它的任意子集 Y，如果 Y是非頻繁項目集，則X也一定不是頻繁項目集。

(3)X是k維項目集，如果頻繁項目集Lk-1中包含的X的子集個數小于k,則X不可能是頻繁項目集。

利用它的性質對Apriori算法從以下三方面進行了改進。

(1)在剪枝階段減少掃描Lk-1的次數

進行剪枝的工作原理是：根據關聯規則的性質，Ck中的一個項集如果是頻繁項集，那么它一定有K個k-1項頻繁子集，且這K個k-1項頻繁子集一定都在Lk-1當中。因此以往的對Ck的剪枝過程都是先取出一個候選k項集，然后產生它的K個k-1項子集，再掃描一次Lk-1查看這K個k-1項子集是否都在 Lk-1中，如果不是則剪掉這個候選k項集，如此循環。如果產生m條候選k項集，就需掃描Lk-1項集m次。然而頻繁項集具有性質3[4]。所以不需要掃描 Lk-1次。首先進行 Lk-1×Lk-1的連接運算生成所有的候選項集Ck,然后取出Lk-1中的第一個頻繁k-1項集，查看該k-1項集是Ck中哪些k項集的子集，如果是子集，則對相應的k項集進行計數。然后再從Lk-1中取出第二個頻繁k-1項集，再到Ck中去查看它是哪些k項集的子集，直到Lk-1中的各個項集都比對完成。最后，查看Ck中的每個k項集，如果它的計數小于k，則它不可能是頻繁k項集，需要刪除。因為頻繁k項集一定有k個k-1項子集存放在Lk-1中。這樣整個剪枝步驟只需要掃描Lk-1一次，提高了剪枝步驟的效率和開銷。

(2)統計階段減少掃描的工作量

對于數據庫D中的事務數據先把它轉換成一個矩陣。矩陣結構[5]如下,其中T為事務，I為項目集：

矩陣的一列對應數據庫D中的一條事務記錄，例如記錄 T1：I1，I2，I5和 T2：I2，I3，I5對應的矩陣。

向量 Di與向量 Dj的內積運算記為：[Di,Dj]=di1×dj1+di2×dj2+…+din×djn。

對于Apriori算法過程中產生的候選2-項集C2中的一個項目集（I2,I3）,以往需要掃描數據庫 D中每一條事務來統計（I2,I3）的支持度。現在只需要對行向量D2與D3做內積運算就可以了。 它們內積[6]的和就是（I2,I3）的支持度。 對于項目集（I1，I2，I5，I7）只需要對 D1、D2、D5、D7這四個行向量相應的列元素做與運算，然后各個列的運算結果相加，就得到了該項目集的支持度。

(3)對用于連接的頻繁項目集進行精簡，減少無用候選的產生。

對于產生的頻繁項目集Lk-1,Apriori算法直接用它連接產生候選頻繁項目集Ck。但實際上Lk-1中的有些項目集已經對產生Lk不起作用了，包含這些項目集的候選k-項集一定不是頻繁的，因此可以對頻繁項目集Lk-1進行精簡。

根據頻繁項集的性質[7],當要用Lk-1連接產生Ck時，首先統計Lk-1中各個項目出現的次數，如果該項目出現的次數小于k-1，則該項目所在的項目集不用來鏈接生成Ck[8]。

例如：有頻繁 3-項目集{I1,I2,I3}，{I1,I2,I5}，{I1,I3,I4}，{I1,I3,I5}，{I1,I3,I6}，{I1,I4,I5}，{I1,I4,I6}。 如果直接用它們進行連接產生的候選 4-項集為：{I1,I2,I3,I5}，{I1,I3,I4,I5}，{I1,I3,I4,I6}，{I1,I3,I5,I6}，{I1,I4,I5,I6}共 5 個。

按照統計頻繁 3-項集中 I1出現 7次，I22次，I34次，I43次，I53次，I62次。在頻繁4-項集中的每一個項目在頻繁3-項目集中應該出現3次，所以應該從頻繁 3-項目集中去除掉：包含 I2、I6(出現次數小于 3)的項目集，只保留{I1,I3,I4}，{I1,I3,I5}，{I1,I4,I5}。 而它們產生的Ck為{I1,I3,I4，I5}只有1個。這樣新產生的候選頻繁項集的數據將大幅減少。

綜上所述，從三個方面改進了Apriori算法，以此大幅度提高了數據挖掘的效率。新算法的描述如下：

3 實驗結果分析

在由Lk-1連接產生Ck階段Apriori算法,每產生一個Ck的項目集就掃描一次Lk-1，一共需要進行|Ck||Lk-1|k次運算，而Apriori-Evo算法只需要掃描 Lk-1一次，只需要進行|Lk-1||Ck|次運算。在掃描事務數據庫D統計各個候選頻繁項集的支持度階段，Apriori算法每產生一個頻繁項集{I1,I2…}就需掃描整個數據庫一次。Apriori-Evo算法每產生一個頻繁項集{I1,I2…}只需要 I1、I2所在的行做運算即可。最后，由Lk連接產生Ck+1階段，Apriori算法直接用Lk進行連接。而Apriori-Evo算法先刪除掉Lk中對產生Lk+1沒有作用的項目，縮小了產生的Ck體積。本文從三個方面對原有算法進行了改進。最后，通過實驗將改進的Apriori算法與原來的算法進行了比較，從數據庫中分別提取 1 000、2 000、3 000、4 000條記錄進行數據挖掘，最小支持度設為25%，運行時間如圖1所示。

實驗結果表明，改進的Apriori-Evo算法確實在關聯規則數據挖掘的速度和效率方面有很大的提高，而且隨著事務數據的增多，提升效果更加明顯。

新的算法從三個方面對原有的算法進行了改進，減少了產生的候選頻繁項集Ck中項集的數據，也減少了剪枝過程中的運算次數，在統計支持度階段減少了需要掃描的數據庫中的事務數。而且計算機進行向量運算和位運算速度更快，程序也會更容易實現。實驗證明，新算法在系統的開銷和時間效率上都有很大的提高。

[1]HAN J,KAMBER M.數據挖掘:概念與技術[M].范明，孟小峰,譯.北京:機械工業出版社，2001.

[2]AGRAWAL R,IMIEL NSKI T,SWAM I A.Mining asso-ciation rules between sets of items in large database[A].In Proc.of the ACM SIGMOD Intl Conf.on Management of Data[C].Washington D.C.,1993:207-216.

[3]AGRAWAL R,SRIKANT R.Fast algorithms for mining association rules[C].Morgan Kaufmann,San Francisco,CA:Proceedings of the 24th International Conference on Very Large Databases,1998:478-499.

[4]李緒成，王保保.挖掘關聯規則中Apriori算法的一種改進[J]. 計算機工程，2002，7(28)：104-105.

[5]羅芳，李志亮.一種基于壓縮矩陣的Apriori改進算法[J].科技資訊，2010(4):19.

[6]劉以安，羊斌.關聯規則挖掘中對 Apriori算法的一種改進研究[J].計算機應用，2007，27（2）:418-420.

[7]盛立，劉希玉，高明.挖掘關聯規則中AprioriTid算法的改進[J].山東師范大學學報（自然科學版），2005，20（4）:20-22.

[8]葉福蘭，施忠興.Apriori算法的改進及應用[J].現代計算機，2009(9):95-126.