摘  要: 數(shù)據(jù)挖掘中的關(guān)聯(lián)規(guī)則挖掘近些年一直是人們研究的熱點(diǎn)。但是關(guān)聯(lián)規(guī)則挖掘的經(jīng)典算法Apriori存在著挖掘效率低、系統(tǒng)開銷大等問題。AprioriTid、DIC等算法，也僅從某一方面進(jìn)行了改進(jìn)。針對(duì)上述問題，提出了一種新的改進(jìn)算法，新算法從三大方面對(duì)原有的算法進(jìn)行了改進(jìn)，以此提高算法的效率，降低系統(tǒng)的開銷。
關(guān)鍵詞: 數(shù)據(jù)挖掘;關(guān)聯(lián)規(guī)則; Apriori; AprioriTid; DIC

    數(shù)據(jù)庫中大量的數(shù)據(jù)與數(shù)據(jù)之間存在著某種聯(lián)系，這種數(shù)據(jù)之間的聯(lián)系就屬于一種重要的知識(shí)，也是進(jìn)行數(shù)據(jù)挖掘的對(duì)象，即關(guān)聯(lián)規(guī)則挖掘[1]。在眾多的關(guān)聯(lián)規(guī)則挖掘算法中最著名的是Apriori算法[2]。它的基本思想是使用一種逐層搜索的迭代算法。但是Apriori算法也有明顯的缺點(diǎn)：每次都會(huì)產(chǎn)生大量的候選頻繁項(xiàng)集，而且候選頻繁項(xiàng)集呈指數(shù)級(jí)增長(zhǎng)。每產(chǎn)生一個(gè)頻繁項(xiàng)目集就需要掃描一次完整的數(shù)據(jù)庫。這些都需要耗費(fèi)巨大的系統(tǒng)資源而且算法的執(zhí)行速度、效率也比較低。因此人們提出了許多改進(jìn)的Apriori算法，本文吸取前人的經(jīng)驗(yàn)提出了一種新的改進(jìn)Apriori算法，稱為Apriori-Evo算法。
1 Apriori算法分析
     Apriori算法的基本步驟是：首先掃描事務(wù)數(shù)據(jù)庫D中的事務(wù)，統(tǒng)計(jì)各個(gè)項(xiàng)目出現(xiàn)的次數(shù)來產(chǎn)生頻繁項(xiàng)目集L1,然后由L1×L1進(jìn)行連接運(yùn)算生成候選2-項(xiàng)集C2，掃描數(shù)據(jù)庫統(tǒng)計(jì)各個(gè)候選2-項(xiàng)集出現(xiàn)的次數(shù),確定其中的頻繁2-項(xiàng)集L2。再由L2×L2進(jìn)行連接運(yùn)算產(chǎn)生候選3-項(xiàng)集C3，一直反復(fù)進(jìn)行這個(gè)過程生成頻繁k-項(xiàng)集Lk，直到無法再生成頻繁項(xiàng)目集為止。

     代碼中apriori_gen( )函數(shù)[3]主要完成兩個(gè)動(dòng)作：連接和剪枝運(yùn)算。Lk-1與Lk-1進(jìn)行連接生成候選頻繁項(xiàng)集。然后剪枝部分利用Apriori的性質(zhì)刪除掉包含非頻繁子集的候選。
     Apriori算法的主要缺點(diǎn)是會(huì)產(chǎn)生大量的候選項(xiàng)集，如果頻繁1-項(xiàng)集有10 000個(gè)，則候選2-項(xiàng)集的個(gè)數(shù)將超過10 000 000個(gè)，算法實(shí)現(xiàn)時(shí)，大量的候選2-項(xiàng)集都被存放在哈希樹中，對(duì)它們的統(tǒng)計(jì)和測(cè)試所需要的開銷會(huì)很大;每產(chǎn)生一個(gè)頻繁項(xiàng)目集就需要將整個(gè)事務(wù)數(shù)據(jù)庫掃描一遍，大大降低了系統(tǒng)I/O效率。
2 對(duì)Apriori算法的改進(jìn)
　關(guān)聯(lián)規(guī)則具有如下性質(zhì)：
　(1)對(duì)于項(xiàng)目集X和它的任意子集Y，如果X是頻繁的，則它的子集Y一定也是頻繁的。
   (2)對(duì)于項(xiàng)目集X和它的任意子集Y，如果Y是非頻繁項(xiàng)目集，則X也一定不是頻繁項(xiàng)目集。
   (3)X是k維項(xiàng)目集，如果頻繁項(xiàng)目集Lk-1中包含的X的子集個(gè)數(shù)小于k,則X不可能是頻繁項(xiàng)目集。
   利用它的性質(zhì)對(duì)Apriori算法從以下三方面進(jìn)行了改進(jìn)。
   (1)在剪枝階段減少掃描Lk-1的次數(shù)
   進(jìn)行剪枝的工作原理是：根據(jù)關(guān)聯(lián)規(guī)則的性質(zhì)，Ck中的一個(gè)項(xiàng)集如果是頻繁項(xiàng)集，那么它一定有K個(gè)k-1項(xiàng)頻繁子集，且這K個(gè)k-1項(xiàng)頻繁子集一定都在Lk-1當(dāng)中。因此以往的對(duì)Ck的剪枝過程都是先取出一個(gè)候選k項(xiàng)集，然后產(chǎn)生它的K個(gè)k-1項(xiàng)子集，再掃描一次Lk-1查看這K個(gè)k-1項(xiàng)子集是否都在Lk-1中，如果不是則剪掉這個(gè)候選k項(xiàng)集，如此循環(huán)。如果產(chǎn)生m條候選k項(xiàng)集，就需掃描Lk-1項(xiàng)集m次。然而頻繁項(xiàng)集具有性質(zhì)3[4]。所以不需要掃描Lk-1次。首先進(jìn)行Lk-1×Lk-1的連接運(yùn)算生成所有的候選項(xiàng)集Ck,然后取出Lk-1中的第一個(gè)頻繁k-1項(xiàng)集，查看該k-1項(xiàng)集是Ck中哪些k項(xiàng)集的子集，如果是子集，則對(duì)相應(yīng)的k項(xiàng)集進(jìn)行計(jì)數(shù)。然后再從Lk-1中取出第二個(gè)頻繁k-1項(xiàng)集，再到Ck中去查看它是哪些k項(xiàng)集的子集，直到Lk-1中的各個(gè)項(xiàng)集都比對(duì)完成。最后，查看Ck中的每個(gè)k項(xiàng)集，如果它的計(jì)數(shù)小于k，則它不可能是頻繁k項(xiàng)集，需要?jiǎng)h除。因?yàn)轭l繁k項(xiàng)集一定有k個(gè)k-1項(xiàng)子集存放在Lk-1中。這樣整個(gè)剪枝步驟只需要掃描Lk-1一次，提高了剪枝步驟的效率和開銷。

    (3)對(duì)用于連接的頻繁項(xiàng)目集進(jìn)行精簡(jiǎn)，減少無用候選的產(chǎn)生。
    對(duì)于產(chǎn)生的頻繁項(xiàng)目集Lk-1,Apriori算法直接用它連接產(chǎn)生候選頻繁項(xiàng)目集Ck。但實(shí)際上Lk-1中的有些項(xiàng)目集已經(jīng)對(duì)產(chǎn)生Lk不起作用了，包含這些項(xiàng)目集的候選k-項(xiàng)集一定不是頻繁的，因此可以對(duì)頻繁項(xiàng)目集Lk-1進(jìn)行精簡(jiǎn)。
    根據(jù)頻繁項(xiàng)集的性質(zhì)[7],當(dāng)要用Lk-1連接產(chǎn)生Ck時(shí)，首先統(tǒng)計(jì)Lk-1中各個(gè)項(xiàng)目出現(xiàn)的次數(shù)，如果該項(xiàng)目出現(xiàn)的次數(shù)小于k-1，則該項(xiàng)目所在的項(xiàng)目集不用來鏈接生成Ck[8]。

   
    實(shí)驗(yàn)結(jié)果表明，改進(jìn)的Apriori-Evo算法確實(shí)在關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘的速度和效率方面有很大的提高，而且隨著事務(wù)數(shù)據(jù)的增多，提升效果更加明顯。
    新的算法從三個(gè)方面對(duì)原有的算法進(jìn)行了改進(jìn)，減少了產(chǎn)生的候選頻繁項(xiàng)集Ck中項(xiàng)集的數(shù)據(jù)，也減少了剪枝過程中的運(yùn)算次數(shù)，在統(tǒng)計(jì)支持度階段減少了需要掃描的數(shù)據(jù)庫中的事務(wù)數(shù)。而且計(jì)算機(jī)進(jìn)行向量運(yùn)算和位運(yùn)算速度更快，程序也會(huì)更容易實(shí)現(xiàn)。實(shí)驗(yàn)證明，新算法在系統(tǒng)的開銷和時(shí)間效率上都有很大的提高。
參考文獻(xiàn)
[1] HAN J,KAMBER M.數(shù)據(jù)挖掘:概念與技術(shù)[M]. 范明，孟小峰,譯.北京:機(jī)械工業(yè)出版社，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] 李緒成，王保保. 挖掘關(guān)聯(lián)規(guī)則中Apriori 算法的一種改進(jìn)[J]. 計(jì)算機(jī)工程，2002，7(28)：104-105.
[5] 羅芳，李志亮.一種基于壓縮矩陣的Apriori改進(jìn)算法[J]. 科技資訊，2010(4):19.
[6] 劉以安，羊斌.關(guān)聯(lián)規(guī)則挖掘中對(duì)Apriori算法的一種改進(jìn)研究[J].計(jì)算機(jī)應(yīng)用，2007，27（2）:418-420.
[7] 盛立，劉希玉，高明.挖掘關(guān)聯(lián)規(guī)則中AprioriTid算法的改進(jìn)[J].山東師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2005，20（4）: 20-22.
[8] 葉福蘭，施忠興.Apriori算法的改進(jìn)及應(yīng)用[J].現(xiàn)代計(jì)算機(jī)，2009(9):95-126.