一種改進的挖掘關聯(lián)規(guī)則Apriori算法

王志春

摘要：該文通過分析Apriori算法存在的瓶頸問題，給出了一種對Apriori算法改進的策略。該策略針對挖掘關聯(lián)規(guī)則步驟中Apriori算法形成的候選項目集進行了優(yōu)化，以避免產(chǎn)生重復的候選集，減少掃描數(shù)據(jù)庫的次數(shù)，提高算法的效率。在實驗評估中顯示，改進后的Apriori算法在執(zhí)行效率上有一定的提高。

關鍵詞：數(shù)據(jù)挖掘；關聯(lián)規(guī)則；Apriori算法

中圖分類號：TP391 文獻標識碼：A 文章編號：1009-3044（2015）34-0004-02

1 概述

隨著計算機和網(wǎng)絡技術的迅速發(fā)展，積累的數(shù)據(jù)海量增長，如何在這些海量數(shù)據(jù)中獲取有價值的信息和知識變得越來越重要。數(shù)據(jù)挖掘[1]在此背景下得到迅速發(fā)展，目前被廣泛地應用于數(shù)據(jù)分析領域中，其目的是從大量的數(shù)據(jù)中挖掘隱藏的、潛在的、有價值的模式或規(guī)則，以對政府和企業(yè)的決策提供有用的依據(jù)。關聯(lián)規(guī)則[2]作為數(shù)據(jù)挖掘中的一個重要課題，通過在大量數(shù)據(jù)中的挖掘和計算，獲取看似不相關的項目間的關聯(lián)性。在關聯(lián)規(guī)則的相關研究中，由Agrawal和Srikant（1994）所提出的Apriori算法[3]是最具代表性的經(jīng)典算法之一，在以后的研究中，提出了許多可改善Apriori算法的性能的優(yōu)化算法，如Park等人提出的基于hash的算法[4]、Savasere等人提出的基于劃分的算法[5]、Toivonen提出基于采樣的算法[6]、Brin等人提出的動態(tài)項集計數(shù)算法[7]以及曾萬聰?shù)热颂岢龅木仃囁惴╗8]等等，這些算法都在不同方面對Apriori算法進行了優(yōu)化。

在大量的數(shù)據(jù)中找出項目間的關聯(lián)性，首先必須要找出頻繁項目集，然后得到滿足設定條件的關聯(lián)規(guī)則，其中找出頻繁項目集的過程是挖掘關聯(lián)規(guī)則過程中最費時的步驟。傳統(tǒng)的Apriori算法及其類似算法在找出頻繁項目集的過程中，必須掃描全部的頻繁項目集，以形成新的候選項目集。本算法對Apriori算法形成候選項目集的方式進行修改，避免產(chǎn)生重復的候選集項目集，從而提高算法的效率。

2 Apriori算法

2.1 關聯(lián)規(guī)則

設[I=i1，i2，…im]是事務數(shù)據(jù)庫全部項目的集合，[T=t1，t2，…tm]是事務數(shù)據(jù)庫的集合，Tj是一組項目組成的項目集。關聯(lián)規(guī)則是形如[A?Bs，c]的蘊含式[9]，其中A稱為前項，B稱為后項，[A?I]，[B?I]且[A?B=Φ]，參數(shù)s（Support）是支持度，參數(shù)c是置信度（Confidence）。挖掘關聯(lián)規(guī)則的過程中，必須由參數(shù)s和c決定關聯(lián)規(guī)則[A?B]是否形成有效的規(guī)則。支持度Support是事務同時包含A和B的比率，即[Support=PA?B=A，B.count/T.count]，反映了A和B所含的項同時出現(xiàn)在事務集T中的概率，其中（A，B）.count表示事務集T中同時包含A和B的事務的個數(shù)，T.count表示事務集T中事務的個數(shù)；置信度Confidence是事務集T中包含A事務的同時也包含B事務的比率，即[Confidence=PB|A=A，B.count/A.count ]，其中A.count表示事務集T中包含A的事務的個數(shù)。為了挖掘有效的關聯(lián)規(guī)則，支持度和置信度必須大于或等于指定的最小支持度和置信度，關聯(lián)規(guī)則[A?B]稱為強規(guī)則，挖掘關聯(lián)規(guī)則即是對最小支持度和置信度求解其強規(guī)則。

挖掘關聯(lián)規(guī)則的過程分為兩個步驟：

1） 找出滿足最小支持度的頻繁項目集，即找出支持度不小于指定的最小支持度的事務集，若該事務集包含k個項目則稱為頻繁k項集。

2） 從頻繁項目集中生成滿足最低置信度的關聯(lián)規(guī)則，即產(chǎn)生支持度和置信度分別不小于指定的最下支持度和置信度的關聯(lián)規(guī)則。

第一個步驟的任務是高效的找出T中的所有頻繁項目集，這是挖掘關聯(lián)規(guī)則的核心問題，也是衡量挖掘關聯(lián)規(guī)則算法效率的主要指標，目前大多數(shù)有關挖掘關聯(lián)規(guī)則算法的研究都是針對第一個步驟展開的。第二個步驟只是由頻繁項目集生成強規(guī)則的枚舉探查過程，算法比較簡單。

2.2 Apriori算法

Apriori算法是最常用的挖掘關聯(lián)規(guī)則的算法之一，同時也經(jīng)常以該算法評估和比較其他算法的性能。

主要利用了向下封閉屬性：如果一個項集，是頻繁項目集，那么它的非空子集必定是頻繁項目集。Apriori算法采用一種逐層搜索的迭代方法，k項集用于搜索（k+1）項集。首先，通過掃描事務集，找出所有的頻繁1項集，該集合記做L1，然后利用L1找頻繁2項集的集合L2，L2用于找L3，如此下去，直到不能再找到任何頻繁k項集。最后再在所有的頻繁集中找出強規(guī)則，即產(chǎn)生用戶感興趣的關聯(lián)規(guī)則。生成頻繁項目集的步驟如下：

1） 找出 頻繁項目集Lk-1，k>1，若為?，則停止執(zhí)行。

2） 由步驟（1）中組合任兩個有k-2項目相同的Lk-1形成候選k項集Ck。

3） 判斷由步驟（2）所找出的Ck，其包含的k-1之子集合是否都出現(xiàn)在步驟（1）中，若成立就保留此Ck；否則就刪除。

4） 再檢查由步驟（3）所保留的Ck是否滿足最小支持度，若符合就成為頻繁項目集Lk；否則就刪除。

5） 跳至步驟（1）找Lk+1，直到無法產(chǎn)生頻繁項目集為止。

2.3 Apriori算法分析

Apriori算法的優(yōu)點是結構簡單，沒有復雜的推導，另外利用檢查候選生成頻繁項目集的方法也大幅度的壓縮了候選集的大小。但是Apriori算法在執(zhí)行速度和效率上仍然存在一定的問題。

1） Apriori算法計算過程中需要產(chǎn)生大量的候選項目集。當候選項集的基數(shù)很大，如頻繁1-項集很大的時候，由此產(chǎn)生的候選集會以指數(shù)方式增長，這樣會增加系統(tǒng)I/O的計算負荷，影響算法的執(zhí)行效率。

2） 需要多次掃描數(shù)據(jù)庫。Apriori算法每生成一次候選項集都需要遍歷數(shù)據(jù)庫進行支持度的計數(shù)，此外產(chǎn)生候選項集時還需要進行模式上的匹配。這些都會花費大量的時間，影響算法的執(zhí)行速度。

3 Apriori算法的改進

Apriori算法在形成候選集Ck的過程中，k>1，必須掃描全部頻繁項目集Lk-1找出可形成Ck的組合，然后再判斷Ck是否為頻繁項目集，如此組合過程必定產(chǎn)生很多重復的候選項目集。改進算法在組合形成候選項目集的過程中，修改產(chǎn)生候選項目集的組合方式，將項目集中出現(xiàn)次數(shù)最小的項目即首項目置于最前面，并且只考慮出現(xiàn)最少的一種組合方式，以避免重復候選集的產(chǎn)生。同時在生成L1的過程中，將事務數(shù)據(jù)庫由水平存儲方式轉化為垂直存儲方式，即一項事務包含那些項目的存儲方式，調整為一個項目屬于那些事務的方式存儲，轉換后的存儲方式在判斷候選項目集是否為頻繁項目集時，可減少所需掃描事務的數(shù)量。改進后挖掘頻繁項目集的步驟如下：

1） 掃描事務集T并計算C1的出現(xiàn)次數(shù)，若滿足最小支持度則為L1，并將事務集由水平存儲轉化為垂直存儲并以Ti表示。

2） 組合任意兩個L1形成C2，將出現(xiàn)次數(shù)最小者置于最前面，稱為字首項目，計算C2出現(xiàn)的次數(shù)。若C2包含的項目分別為A和B且出現(xiàn)次數(shù)A

3） 找出Lk-1，k>2，及T Lk-1

4） 由步驟（3）中組合字首項目相同的兩個Lk-1形成Ck，保留字首項目。

5） 判斷由步驟（4）所產(chǎn)生的Ck，其包含的Ik-1項是否都出現(xiàn)在步驟（3）中，若成立就保留Ck，并計算否則[TCk=TLk-1?TLk-1]，否則刪除。

6） 計算TCk包含事務的數(shù)量，若滿足最小支持度則為Lk，并保留TLk。

7） 轉至步驟（3）找Lk+1，直到無法產(chǎn)生頻繁項目集為止。

以上挖掘過程中，步驟（1）將事務集存儲方式的轉換垂直存儲方式，可以提升后續(xù)計算候選項目集出現(xiàn)次數(shù)的執(zhí)行效率。步驟（2）將出現(xiàn)次數(shù)最小的項目置于項目集字首，并在步驟（4）中只組合字首項目相同的兩個Lk-1形成Ck 可以減少產(chǎn)生重復候選項目集的組合計算。在整個過程中通過保留TLk，在后續(xù)找出LK+1時可以減少事務集所需的交集運算。相比較Apriori算法挖掘關聯(lián)規(guī)則的過程，改進后的算法的效率更高。

4 實驗結果與分析

為了比較算法改進前后的效率，對Apriori算法和改進算法進行測試。算法采用C#實現(xiàn)，實驗數(shù)據(jù)來自于Microsoft SQL Server2008中的示例數(shù)據(jù)庫AdventureWorks-DW，采用視圖vAssocSeqLineItems中的52761條記錄、21254個事務集進行挖掘關聯(lián)規(guī)則的實驗。

在不同支持度下，改進Apriori算法和傳統(tǒng)Apriori算法執(zhí)行時間的測試結果如圖1所示。

從圖1中可以看出，當數(shù)據(jù)規(guī)模相同而支持度不同時，改進算法的執(zhí)行時間要比Apriori算法短，并且支持度越小算法執(zhí)行時間增長越長，而改進算法執(zhí)行時間的增長速度遠低于Apriori算法。

在支持度和事務項數(shù)相同，而事務數(shù)不同的情況下，改進Apriori算法和傳統(tǒng)Apriori算法執(zhí)行時間的測試結果如圖2所示。

從圖2中可以看出隨著事務數(shù)量的增長，算法的執(zhí)行時間都不斷增長，但改進的算法比 Apriori算法增長的速度要慢。

綜上所述，改進的Apriori算法避免了重復候選集的產(chǎn)生，采用了新的數(shù)據(jù)存儲方式，減少了掃描數(shù)據(jù)庫的次數(shù)，整體上提高了挖掘關聯(lián)規(guī)則算法的執(zhí)行效率。

5 結論

本文通過分析Apriori算法，對挖掘關聯(lián)規(guī)則產(chǎn)生頻繁項目集的步驟進行了改進，并給出了改進算法的完整描述。通過理論分析和實驗結果評價來看，提高了算法的執(zhí)行效率，證明了改進后的算法的有效性。

參考文獻：

[1] Chen M S， Han J W， Yu P S. Data Mining： An Overview from a Data base Perspective [J]. IEEE Transactions on Know ledge and Data Engineering， 1996， 8 （6）： 866 883.

[2] 何軍， 劉紅巖， 杜小勇. 多關系關聯(lián)規(guī)則挖掘研究綜述 [J]. 軟件學報， 2007， 18（11）： 2752- 2765.

（下轉第17頁）

（上接第5頁）

[3] Han JW， K amber M. Data Mining Concepts and Techniques [M]. Beijing： Higher Education Press， 2001.

[4] PARKJ S ， CHEN M S ， YU P S. Efficient parallel data mining of association rules[C]/ / Proceeding of the ACM SIGMOD In2ternational Conference on Management of Data. New York： ACM， 1995： 31236.

[5] SAVASERE A， OMIECINSKI E， NAVATHE S. An efficient algorithm for mining association rules in large databases[C]/ /Proceedings of the 21st International Conference on Very Large Database. New York： ACM， 1995：4322443.

[6] TOLVONEN H. Sampling large databases for association rules[C]/ / Proceedings of the 22nd International Conference on Very Large Database. Bombay， India： [s. n. ] ， 1996 ： 1342145.

[7] RIN S ， MOTWANI R ， ULLMAN J D. Dynamic item set counting and implication rules for market basked data [C]/ /Proceeding of the ACM SIGMOD International Conference on Management of Data. New York： ACM ， 1997 ：2552264.

[8] 曾萬聰，周緒波，戴勃，等.關聯(lián)規(guī)則挖掘的矩陣其法[J]. 計算機工程，2006，32（2）：4524.

[9] 蔡麗艷.數(shù)據(jù)挖掘算法及其應用研究[M].成都：電子科技大學出版社，2013.