摘要：本文首先回顧了關聯規則" title="關聯規則">關聯規則挖掘研究進展情況，然后對關聯規則問題進行了形式化描述，最后討論了關聯規則挖掘" title="關聯規則挖掘">關聯規則挖掘的處理流程和主要算法。?

關鍵詞：數據挖掘" title="數據挖掘">數據挖掘? 關聯規則? 支持度? 可信度?

關聯規則挖掘研究進展

數據挖掘是指從大量數據中挖掘出隱含的、先前未知的、對決策有潛在價值的知識和規則的高級處理過程[1,2]。通過數據挖掘，有價值的知識、規則或高層次的信息就能從數據庫的相關數據集合中抽取出來，并從不同角度展現，從而使大型數據庫作為一個豐富、可靠的資源為知識的提取服務。?

R. Agrawal等人在1993年首先提出在交易數據庫中挖掘關聯規則[3]，典型的例子是“多數顧客在購買面包和黃油的同時也會購買牛奶”，找出所有這類規則，對于確定市場策略是很有價值的，例如可用于追加銷售、倉儲規劃，并可根據購買模式對顧客進行劃分。?

AIS算法是第一個發表的生成事務數據庫中所有大項目集的算法[3]。它集中在增強數據庫必要的功能以支持決策支持查詢。該算法的目標是發現定性規則。該技術的局限性是結論中只有一個項目。即關聯規則是形如XTI_j | a的規則，其中X是一個項目集合，I_j是值域I中的單個項目，a是規則的置信度。?

AIS算法要對整個數據庫進行多次分析。每次分析都要掃描全部事務。第一次分析計算數據庫中單個項目的支持度，并確定哪個是大或頻繁項目集。對每次分析的大項目集進行擴展以生成候選項目集。掃描一個事務之后，可確定上一次分析的大項目集和該事務項目的公共項目集。這些公共項目集被該事務中的其它項目擴展，生成新的候選項目集。大項目集l只能由在當前事務中的大項目并且按照詞典順序位于l中所有項目之后的項目。為了高效地完成該任務，它采用了一種評估工具和剪枝技術。該評估和剪枝技術通過刪除候選集合中不必要的項目集來確定最終的候選集合。然后計算每個候選集合的支持度。支持度大于等于最小支持度閾值的候選集合被選出作為大項目集。這些大項目集繼續被擴展以生成下一次分析的候選集合。直到不能發現更多大項目集時該處理過程結束。?

STEM算法在[4]中提出，其目的是用SQL來處理候選大項目集[5]。在該算法中，大項目集組成的集合的每個成員形如，其中TID是事務的唯一標識符。類似地，候選項目集組成的集合的每個成員形如。與AIS算法類似，SETM算法也要多次分析數據庫。?

Apriori是對AIS和SETM算法的改進，并且是第一個可擴展的關聯規則挖掘算法[2,6]。當進行初始數據庫掃描時Apriori算法搜索大項目集合，然后用該搜索結果作為后續掃描并發現其它達數據集合的種子。支持度大于給定最小值的規則稱為大項目集（large itemsets）頻繁項目集（frequent itemsets），支持度小于給定最小值規則稱為小項目集（small itemsets）[7]。?

簡而言之，給定一個數據集合，Apriori算法需要通過初始掃描整個數據集合產生一個支持度不小于指定最小值的項目集合。生成該項目集合（稱為1-候選集合）之后，再形成下一個候選集合（稱為2-候選集合）。再次掃描數據庫來計算2-候選集合的支持度。所有支持度小于最小值的集合將被剪裁掉。當不再生成新的候選集合時算法終止，得到k-候選集合。?

該算法基于頻繁項目集合的性質，即一個頻繁集合的任何子集都是頻繁集合；如果一個項目集合不是頻繁集合，其所有超集均不是頻繁集合[8]。?

有一些Apriori算法的變型，如AprioriTID和AprioriHybrid。AprioriTID的工作原來與Apriori類似，所不同的是它用生成的項目集合計算支持度，取代了通過數據庫掃描計算支持度的方法。據報道，只有當AprioriTID生成的項目集合能夠放在內存時，AprioriTID才比Apriori效率更高。AprioriHybrid是Apriori和AprioriTID的混合體。該算法用Apriori進行初始掃描，一旦認為生成的集合能夠與內存匹配則切換到AprioriTID算法。在大多數情況下AprioriHybrid算法比Apriori算法效率高，但是當進行到最后一次掃描時是個例外。這是因為它花費了過高的代價獲取無意義的項目。Apriori算法比其它一些算法（如SETM和AIS）更有效[6,9]。?

此后，研究人員對關聯規則挖掘問題進行了深入的研究，通過引入隨機采樣和并行挖掘等思想，對原有算法進行了優化，以提高挖掘算法的執行效率。?

J. S. Park等人指出，Apriori算法的計算開銷主要在頻繁2項目集的計算上，因此提出了基于Hash技術對生成的候選2項目集進行裁剪的DHP算法[10]。Apriori算法和DHP算法掃描數據庫的次數是和最大" title="最大">最大頻繁項目集的長度一致的，但是對大型數據庫系統一次數據庫掃描的代價是非常昂貴的，所以數據庫掃描的次數成為關聯規則挖掘算法的一個主要的瓶頸問題。?

A. Savasere等人提出了分區（Partition）算法[11]，該算法將數據庫掃描的次數降為兩次。Partition算法邏輯上將數據庫劃分為互不相交的若干個區，算法首先找出每個分區中的局部頻繁項目集，然后根據“頻繁項目集至少在一個分區中是頻繁的”這一性質，合并所有的局部頻繁項目集，最后對合并后所有的局部頻繁項目集進行全局計數，得到全局頻繁項目集。?

H. Toivonen等人提出了基于采樣的關聯規則挖掘算法[12]，該算法通過數據庫的一個隨機采樣數據生成候選頻繁項目集，然后掃描整個數據庫對其進行驗證。基于采樣的算法多數情況下只需掃描一次數據庫，最壞的情況下也只需兩次掃描，但該算法所獲得的高效率是以犧牲挖掘精度來換取的，有可能丟失一些全局頻繁項目集。?

為了進一步提高算法的有效性，S. Brin等人提出了動態項目集計數（DIC）算法[13]，該算法將數據庫劃分為若干分區并且對每個分區的開始做標記，不同于Apriori算法的是，在數據庫掃描過程中，DIC算法可以在各個分區的標記點添加候選項目集，而不是像Apriori那樣只能在每次完成整個數據庫掃描之后添加候選項目集，這樣便極大地減少了數據庫掃描次數。?

J. Han等人提出了一種無需生成候選頻繁項目集的算法FP-Growth（頻繁模式增長算法）[14]，該算法首先將數據庫壓縮成一個高度濃縮的數據結構——FP樹，隨后發現頻繁項目集的工作都在該FP樹上完成，這樣就避免了多次數據庫掃描。另外，FP-Growth算法直接在FP樹上發現頻繁項目集，避免了產生數目龐大的候選頻繁項目集，因此FP-Growth算法較Apriori算法的效率有一個量級的提高。?

Ei-Hajj等人提出了一種基于反轉矩陣（Inverted Matrix）的算法[15]，它類似于FP-Growth算法，該算法首先將數據庫映射為一個基于磁盤的反轉矩陣，然后針對該反轉矩陣在內存中建立COFI（Co-Ocurrence Frequent Item）樹，利用COFI樹發現頻繁項目集。實驗結果表明，該算法優于Apriori和FP-Growth，對于超大規模數據庫和較小支持度的情況，優勢更加明顯。另外，反轉矩陣的結構特點決定了它便于實現并行挖掘算法。?

除了上述基本關聯規則挖掘算法研究，人們還進行了諸如多層關聯規則、量化關聯規則、基于約束的關聯規則、時態關聯規則、空間關聯規則等類型關聯規則挖掘算法的研究。?

Srikant和Agrawal從廣義關聯規則挖掘的角度研究了多層關聯規則挖掘問題[16]，多層關聯規則挖掘利用概念分層的背景知識在更高的抽象層次上挖掘關聯規則，從而解決了稀疏數據中關聯規則的支持度閾值過低而難以挖掘的問題。?

Srikant等人通過將數值型數據劃分為不同區間的方法，在這些區間之上進行定量關聯規則的挖掘[17]。?

為了克服Agrawal頻集方法的缺陷，人們還提出了一些新的關聯規則挖掘方法[18,19,20,21,22,23,24]。?

關聯規則問題描述

本節給出關聯規則挖掘問題的形式描述。?

定義2.1 令I = {I₁, I₂, … , I_m}是由m個不同項目（Items）組成的集合，D是由事務T組成的集合（數據庫），這里事務T是項目的集合，并且T í I。其中，每個事務T有一個唯一標識，記為TID。關聯規則是形如XTY的蘊涵式，其中X í ?I，Y í ?I，而且X ?Y = f。這里，X 稱為前提，Y 稱為結論。?

下面定義關聯規則的兩個重要測度：支持度S（Support）和可信度C（Confidence）。?

定義2.2 關聯規則XTY在事務集合D中的支持度是?

S(XTY) = |{T: XèYíT, T?D}| / |D|?

其中，|{T: XèYíT, T?D}|是D中包含X和Y的事務數，|D|是D中所有事務數。?

定義2.3 關聯規則XTY在事務集合D中的可信度是?

C(XTY) = |{T: XèYíT, T?D}| / |{T: XíT，T?D}|?

其中，|{T: XèYíT, T?D}|是包含X和Y的事務數，|{T: XíT，T?D}|是包含X的事務數。?

給定一個事務集合（數據庫）D，挖掘關聯規則問題就是產生支持度和可信度分別大于用戶給定的最小支持度S_min和最小可信度C_min的關聯規則。?

關聯規則挖掘算法

經典頻繁集合方法?

Agrawal等人1993年[3]首先提出挖掘顧客交易數據庫中項目集之間關聯規則的問題，這是一種基于頻繁集合理論的遞推方法，它將關聯規則挖掘算法分解為兩個步驟：?

1. 找到所有支持度大于最小支持度S_min的項目集合（Itemsets），這些項集稱為頻繁集合（Frequent Itemsets)；?

2. 使用第1步找到的頻繁集合產生期望的規則。?

如給定了一個頻繁集合Y=I₁I₂...I_k，k32，I_j∈I，產生只包含集合{I₁，I₂，...，I_k}中項目的所有規則（最多k個），其中每一個規則的右部只有一項，(即形如[Y-I_i]TI_i，'1￡i￡k)，這里采用的是[13]中規則的定義。一旦生成了這些規則，只有那些大于用戶給定的最小可信度的規則才被留下來。對于規則右部含兩個以上項目的規則，我們將在后面討論。?

為了生成所有頻繁集合，使用了遞推的方法。其核心算法如下：?

(1)???? L₁ = {large 1-itemsets};?

(2)???? for (k=2; L_k-11F; k++) do begin?

(3)?????? ? C_k=apriori-gen(L_k-1);?? //新的候選集?

(4)?????? ? for all transactions t?D do begin?

(5)??????? ?????? ???C_t=subset(C_k, t);??? //事務t中包含的候選集?

(6)?????????? for all candidates c? C_t do?

(7)?????????? c.count++;?

(8)?????? ? end?

(9)??????? L_k={c? C_k |c.count 3 S_min}?

(10)??? end?

(11)??? Answer = è_kL_k;?

首先產生頻繁1-項目集L₁，然后是頻繁2-項目集L₂，直到有某個r值使得L_r為空，這時算法停止。這里在第k次循環中，過程先產生候選k-項目集的集合C_k，C_k中的每一個項目集是對兩個只有一個項不同的屬于L_k-1的頻繁集合做一個(k-2)-連接來產生的。C_k中的項目集是用來產生頻繁集合的候選集，最后的頻繁集合L_k必須是C_k的一個子集。C_k中的每個元素需在事務數據庫中進行驗證來決定其是否加入L_k，這里的驗證過程是算法性能的一個瓶頸。這個方法要求多次掃描可能很大的事務數據庫，即如果頻繁集合最多包含10個項目，那么就需要掃描事務數據庫10遍，這需要很大的I/O" title="I/O">I/O開銷。?

在文獻[25]中，Agrawal等人用剪枝技術（Pruning）來減小候選集C_k的大小，由此可以顯著地改進生成所有頻繁集合算法的性能。算法中引入的剪枝策略基于這樣一個性質：一個項目集是頻繁集合當且僅當它的所有子集都是頻繁集合。那么，如果C_k中某個候選項目集合有一個(k-1)-子集不屬于L_k-1，則這個項目集可以被剪掉不再被考慮，這個剪枝過程可以降低計算所有的候選集合的支持度的代價。文獻[25]中還引入了雜湊樹（Hash Tree）方法來有效地計算每個項目集的支持度。?

頻繁集合算法的幾種優化方法?

雖然Apriori算法自身已經進行了一定的優化，但是在實際應用中還是存在不令人滿意的地方，于是人們相繼提出了一些優化方法。?

1.??劃分方法

Savasere等[11]設計了一個基于劃分（partition）的算法，該算法先把數據庫從邏輯上分成幾個互不相交的塊，每次單獨考慮一個分塊并對它生成所有的頻繁集合，然后把產生的頻繁集合合并，用來生成所有可能的頻繁集合，最后計算這些項目集的支持度。這里，分塊的大小要使得每個分塊可以被放入主存，每個階段只需被掃描一次。而算法的正確性是由每一個可能的頻繁集合至少在某一個分塊中是頻繁集合保證的。上面所討論的算法是可以高度并行的，可以把每一分塊分別分配給某一個處理器生成頻繁集合。產生頻繁集合的每一個循環結束后，處理器之間進行通信來產生全局的候選k-項目集。通常這里的通信過程是算法執行時間的主要瓶頸；而另一方面，每個獨立的處理器生成頻繁集合的時間也是一個瓶頸。其他的方法還有在多處理器之間共享一個雜湊樹來產生頻繁集合。其它關于生成頻繁集合的并行方法詳見[10,26]。?

2. Hash方法

Park等[10]提出了一種基于雜湊（Hash）方法的算法，可以高效產生頻繁集合。通過實驗我們可以發現尋找頻繁集合主要的計算是在生成頻繁2-項目集L_k上，Park等就是利用了這個性質引入雜湊技術來改進產生頻繁2-項目集的方法。?

3. 采樣方法

基于前一遍掃描得到的信息，對此仔細地進行組合分析，可以得到一個改進的算法，Mannila等[27]首先考慮到這一點，認為采樣是發現規則的一個有效途徑。隨后又由Toivonen[12]進一步發展了這個思想，先使用從數據庫中抽取出來的采樣得到一些在整個數據庫中可能成立的規則，然后對數據庫的剩余部分驗證這個結果。Toivonen的算法相當簡單并顯著地降低了I/O開銷，但該算法最大的缺點是產生的結果不精確，存在所謂的數據扭曲(Data Skew)。分布在同一頁面上的數據通常是高度相關的，可能不能表示整個數據庫中模式的分布，由此而導致的是采樣5%的交易數據所花費的代價可能同掃描一遍數據庫相近。Lin和Dunham在[28]中討論了反扭曲(Anti-skew)算法來挖掘關聯規則，在那里他們引入的技術使得掃描數據庫的次數少于2次。?

Brin等[13]提出的算法使用比傳統算法少的掃描遍數來發現頻繁集合，同時比基于采樣的方法使用更少的候選集，這些改進了算法在低層的效率。具體的考慮是，在計算k-項目集時，一旦認為某個(k+1)-項目集可能是頻繁集合，就并行地計算該(k+1)-項目集的支持度，算法所需的總的掃描次數通常少于最大頻繁集合的項目數。?

4.??減少事務個數

減少用于未來掃描的事務集合的大小。一個基本的原理就是當一個事務不包含長度為k的大項目集，則必然不包含長度為k+1的大項目集。從而我們就可以將這些事務刪掉，這樣在下一遍的掃描中就可以減少事務的個數。?

其它頻繁集合挖掘方法?

前面介紹的都是基于Apriori的頻繁集合方法。即使進行了優化， Apriori方法固有的缺陷仍然無法克服。?

（1）Apriori可能產生大量的候選集。當長度為1的頻繁集合有10000個時，長度為2的候選集個數將會超過10M。另外，如果要生成一個很長的規則，產生的中間元素的數量也是巨大的。?

（2）Apriori無法對稀有信息進行分析。由于頻繁集合使用了參數S_min（最小支持度），所以就無法對小于S_min的事件進行分析；而如果將S_min設成一個很低的值，那么算法的效率就會很低。?

下面介紹兩種方法，分別用來解決上述兩個問題。?

文獻[14]提到了一種解決問題（1）的FP-growth方法。該方法采用分而治之的策略：在經過第一次掃描之后，把數據庫中的頻繁集合壓縮進一棵頻繁模式樹（FP-tree），同時依然保留其中的關聯信息。隨后再將FP-tree分化成一些條件庫，每個庫和一個長度為1的頻繁集合相關。然后再對這些條件庫分別進行挖掘。當原始數據量很大的時候，也可以結合劃分的方法，使得一個FP-tree可以放入主存中。實驗表明，FP-growth對不同長度的規則都有很好的適應性，同時在效率上較之Apriori算法有巨大的提高。?

文獻[29]中介紹了一種解決問題（2）的方法。該方法基于這樣的思想：Apriori算法得出的關系都是頻繁出現的，但在實際應用中，我們可能需要尋找一些高度相關的元素，即使這些元素不是頻繁出現的。在Apriori算法中，起決定作用的是支持度，而我們現在把可信度放在第一位，挖掘一些具有高可信度的規則。?

整個算法大致分成計算特征、生成候選集、過濾候選集三個步驟。在這三個步驟中，關鍵是在計算特征時Hash方法的使用。在考慮算法的時候，有幾個衡量好壞的指標：時空效率、錯誤率和遺漏率。?

基本的方法有兩類：?

（1）Min_Hashing的基本思想是，將一條記錄中的頭k個為1的字段的位置作為一個Hash函數。該方法的遺漏率為零，錯誤率可以由k嚴格控制，但是時空效率相對較差。?

（2）Locality_Sentitive_Hashing的基本思想是，將整個數據庫用一種基于概率的方法進行分類，使得相似的列在一起的可能性更大，不相似的列在一起的可能性較小。該算法的遺漏率和錯誤率是無法同時降低的，但它的時空效率卻比較高。?

結束語

本文回顧了關聯規則挖掘研究的進展情況，對關聯規則問題進行了形式化描述，最后總結了關聯規則挖掘的處理流程和主要算法。?

參考文獻

[1] BERRY, M.J. and LINOFF, G. Data Mining Techniques. John Wiley & Sons, New York. 1997.?

[2] U. M.Fayyad，G. Piatesky-Shapiro，P. Smyth，and R. Uthurusamy Eds. Advances in Knowledge Discovery and Data Mining. AAAI/MIT Press，1996.?

[3] R. Agrawal, T. Imielinski and A. Swami. Mining Association Rules between Sets of Items in Large Databases. In Proc. 1993 ACM-SIGMOD Int. Conf. Management of Data, Washington, D.C., pages 207–216, May 1993.?

[4] M. Houtsma and A. Swami, Set-Oriented Mining for Association Rules in Relational Databases, Proceedings of the 11th IEEE International Conference on Data Engineering, pp. 25-34, Taipei, Taiwan, March 1995.?

[5] R. Srikant, Fast Algorithms for Mining Association Rules and Sequential Patterns, Ph.D Dissertation, 1996, University of Wisconsin, Madison.?

[6] R. Agrawal and R. Srikant. Fast algorithms for mining association rules. In Proc. 1994 Int. Conf. Very Large Databases，pages 487-499，Santiago，Chile，September 1994.?

[7] M. Chen, J. Han and P. Yu. Data mining: An overview from database perspective. IEEE Transactions on Knowledge and Data Eng., pages 866–883, December 1996.?

[8] J. W. Han，Y. Cai and N. Cercone. Knowledge Discovery in Databases: an Attribute-Oriented Approach. Proc. of 18th VLDB，1992:547-559, 1992.?

[9] J. Hipp, U. Guntzer, and G. Nakaeizadeh. Algorithms for Association Rule Mining - A General Survey and Comparison. In Proc. ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 58–64, July 2000.?

[10] J. S. Park，M. S. Chen，and P. S. Yu. An effective hash-based algorithm for mining association rules. Proceedings of ACM SIGMOD International Conference on Management of Data，pages 175-186，San Jose，CA，May 1995.?

[11] A. Savasere，E. Omiecinski，and S. Navathe. An efficient algorithm for mining association rules in large databases. Proceedings of the 21st International Conference on Very large Database，1995.?

[12] H. Toivonen. Sampling large databases for association rules. Proceedings of the 22nd International Conference on Very Large Database，Bombay，India，September 1996.?

[13] S. Brin，R. Motwani，J. D. Ullman，and S. Tsur. Dynamic Itemset counting and implication rules for market basket data. In ACM SIGMOD International Conference On the Management of Data. 1997.?

[14] J. Han，J. Pei，and Y. Yin.Mining frequent patterns without candidate generation.In Proc.2000 ACM-SIGMOD Int.Conf.Management of Data(SIGMOD’00)，Dalas，TX，May 2000.?

[15] Mohammad Ei-Hajj, Osmar R. Za?ane. Inverted Matrix Efficient Discovery of Frequent Items in Large Datasets in the Context of Interactive Mining. SIGKDD’03 Washington DC, USA, 2003.?

[16] R. Srikant，and R. Agrawal. Mining generalized association rules. Proceedings of the 21st International Conference on Very Large Database，1995，pp. 407-419.?

[17] R. Srikant，and R. Agrawal. Mining quantitative association rules in large relational tables.? Proceedings of the ACM SIGMOD Conference on Management of Data，1996. pp.1-12.?

[18] E. Omiecinsky, A. Sarasere, and S. Navathe. An efficient Algorithm for Mining Association Rules in Large Databases. In Proc. of the 21st VLDB conference, Zurich, Switzerland, pages 432–444, September 1995.?

[19] Y. Yin, J. Pei, and J. Han. Mining Frequent Patterns Without Candidate Generation. In Proc. 2000 ACM-SIGMOD Int. Conf. Management of Data (SIGMOD’00), Dallas, Texas, pages 1–12, May 2000.?

[20] M. J. Zaki, S. Parthasarathy, M. Ogihara andW. Li. New Algorithms for Fast Discovery of Association Rules. In Proc. 3rd Int’l Conf. Knowledge Discovery and Data Mining, AAAI Press, Menlo Park, California, pages 283–286, April 1997.?

[21] M. Mehta, R. Agrawal, and J. Shafer. Sprint: A scalable parallel classifier for data mining. In Proc. Of the 1996 Int. Conf. Very Large Data Bases, Bombay, India, pages 544–555, September 1996.?

[22] W. Hsu, B. Liu, and Y. Ma. Integrating Classification and Association Rule Mining. In Proc. of the Fourth International Conference on Knowledge Discovery and Data Mining KDD-98, New York, USA, pages 80–86, 1998.?

[23] J. S. Park，M. S. Chen，and P. S. Yu. Efficient parallel data mining of association rules. 4th International Conference on Information and Knowledge Management，Baltimore，Maryland，Novermber 1995.?

[24] A. Savasere，E. Omiecinski，and S. Navathe. Mining for strong negative associations in a large database of costomer transactions. Proceedings of the International Conference on Data Engineering，February 1998.?

[25] R. Agrawal and R. Srikant. Fast Algorithms for Mining Association Rules. In Proc. of the International Conference of Very Large Databases, Santiago, Chile, pages 487–499, September 1994.?

[26] M. J. Zaki，S. Parthasarathy，and W. Li. A localized algorithm for parallel association mining. 9th Annual ACM Symposium on Parallel Algorithms and Architectures，Newport，Rhode Island，June 1997.?

[27] H. Mannila，H. Toivonen，and A. Verkamo. Efficient algorithm for discovering association? rules. AAAI Workshop on Knowledge Discovery in Databases，1994，pp. 181-192.?

[28] J. L. Lin，and M. H. Dunham. Mining association rules: Anti-skew algorithms. Proceedings of the International Conference on Data Engingeering，Orlando，Florida，February 1998.?

[29] Edith Cohen，Mayur Datar，Shinji Fujiwara，Aristides Gionis，Piotr Indyk，Rajeev Motwani，Jeffrey D.Ullman，Cheng Yang. Finding Interesting Associations without Support Pruning.?