摘 要: 數據挖掘中的關聯規則挖掘近些年一直是人們研究的熱點。但是關聯規則挖掘的經典算法Apriori存在著挖掘效率低、系統開銷大等問題。AprioriTid、DIC等算法，也僅從某一方面進行了改進。針對上述問題，提出了一種新的改進算法，新算法從三大方面對原有的算法進行了改進，以此提高算法的效率，降低系統的開銷。
關鍵詞: 數據挖掘;關聯規則; Apriori; AprioriTid; DIC
數據庫中大量的數據與數據之間存在著某種聯系，這種數據之間的聯系就屬于一種重要的知識，也是進行數據挖掘的對象，即關聯規則挖掘[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_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一次，提高了剪枝步驟的效率和開銷。
(3)對用于連接的頻繁項目集進行精簡，減少無用候選的產生。
對于產生的頻繁項目集Lk-1,Apriori算法直接用它連接產生候選頻繁項目集Ck。但實際上Lk-1中的有些項目集已經對產生Lk不起作用了，包含這些項目集的候選k-項集一定不是頻繁的，因此可以對頻繁項目集Lk-1進行精簡。
根據頻繁項集的性質[7],當要用Lk-1連接產生Ck時，首先統計Lk-1中各個項目出現的次數，如果該項目出現的次數小于k-1，則該項目所在的項目集不用來鏈接生成Ck[8]。
實驗結果表明，改進的Apriori-Evo算法確實在關聯規則數據挖掘的速度和效率方面有很大的提高，而且隨著事務數據的增多，提升效果更加明顯。
新的算法從三個方面對原有的算法進行了改進，減少了產生的候選頻繁項集Ck中項集的數據，也減少了剪枝過程中的運算次數，在統計支持度階段減少了需要掃描的數據庫中的事務數。而且計算機進行向量運算和位運算速度更快，程序也會更容易實現。實驗證明，新算法在系統的開銷和時間效率上都有很大的提高。
參考文獻
[1] HAN J,KAMBER M.數據挖掘:概念與技術[M]. 范明，孟小峰,譯.北京:機械工業出版社，2001.
[2] AGRAWAL R, IMIEL NSKI T , SWAM I A. Mining association 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.