關聯規則挖掘技術研究進展

摘 要:為幫助人們深入研究關聯規則挖掘技術，總結了關聯規則的分類方法、評價方法以及相關技術的最新進展，特別是對關聯規則的主要算法進行了詳細的介紹，并探討未來的發展方向。該研究比較系統全面，對將來進一步深入分析關聯規則挖掘技術具有指導意義。

關鍵詞:數據挖掘; 關聯規則; 頻繁; 并行

中圖分類號:TP391文獻標志碼:A

文章編號:1001-3695(2009)09-3210-04

doi:10.3969/j.issn.1001-3695.2009.09.003

State-of-art on association rules mining technology

CHENG Shu-tong1，2， XU Cong-fu

(1.College of Computer Science Technology， Zhejiang University， Hangzhou 310027， Chian; 2.Hangzhou Polytechnique College， Hangzhou 310012， China)

Abstract:Association rule which has a vital value both in research and practice is the basic problem in the domain of data mining， the widely research works have been done by many researchers either in home or in the other countries. The aim of this paper was that it not only helped the people to study the association rule in data mining deeply but also generalized the method of the sorting and evaluation and the development of new techniques in association rule. Especially introduced the details in major arithmetic of association rule and gave the direction. The research in which is both systematic and comprehensive is that it can help people to analyse the association rule in data mining deeply in the future.

Key words:data mining; association rules; frequent; parallel

0 引言

關聯規則(association rule)挖掘技術是數據挖掘研究的重要內容之一，旨在從大量數據中提取人們未知卻又潛在有用的規則。例如發現交易數據庫中不同商品(項)之間的聯系，通過這些規則找出顧客購買行為模式。發現這樣的規則可以應用于商品貨架設計、貨存安排以及根據購買模式對用戶進行分類。

Agrawal等人[1，2]首先提出從交易數據庫發現項目間關聯規則的相關問題，并給出了基于頻繁集的Apriori 算法。該算法以遞歸統計為基礎，以最小支持度為依據剪切生成頻繁集。以后諸多的研究人員對關聯規則的挖掘問題進行了大量的研究，他們的工作包括:對原有的算法進行優化，如引入隨機采樣、并行的思想等，以提高算法挖掘規則的效率;對關聯規則的應用進行推廣。

1 相關定義

定義1 關聯規則。設I={i1，i2，NA1AD，in}是項的集合，設任務相關的數據D是數據庫事務的集合。其中每個事務T是項的集合，使得TI。每一個事務有一個標志符，稱做TID(transactionidentifier)。設A是一個項集，事務T包含A當且僅當AT。關聯規則是形如AB的蘊涵式。其中AI，BI，并且A∩B=。規則A∩B=在事務集D中成立，具有支持度s。其中s是D中事務包含A∪B(即A和B兩者)的百分比，它是概率P(A∪B) 。規則A∩B=在事務集D中具有置信度c，如果D中包含A的事務同時也包含B的百分比是c，這是條件概率P(B|A)，即

support(AB)=P(A∪B)=|T:X∪YT，T∈D|/|D|

confidence(AB)=P(B|A)=

|T:X∪YT，T∈D|/|T:XT，T∈D|

同時滿足最小支持度閾值(min_sup)和最小置信度閾值(min_conf)的規則稱為強規則。項的集合稱為項集(itemset)。包含k個項的項集稱為k-項集。項集的出現頻率是包含項集的事務數，簡稱為項集的頻率、支持計數或計數。如果項集的出現頻繁大于或等于min_sup與中事務總數的乘積，則稱項集滿足最小支持度。如果項集滿足最小支持度，則稱它為頻繁項集frequentitemset。頻繁k-項集的集合通常記做Lk。

關聯規則的挖掘是一個兩步的過程:

a)所有頻繁項集。根據定義，這些項集出現的頻繁性至少與預定義的最小支持計數一樣。

b)頻繁項集產生強關聯規則。根據定義，這些規則必須滿足最小支持度和最小置信度。

2 關聯規則分類

1)基于規則中處理的變量類別

關聯規則可分為布爾型和數值型。布爾型關聯規則處理的值都是離散的、種類化的，它顯示了這些變量之間的關系;數值型關聯規則可以與多維關聯或多層關聯規則結合起來對數值型字段進行處理，將其進行動態的分割，或直接對原始的數據進行處理，當然數值型關聯規則中也可以包含種類變量。

2)基于規則中數據的抽象層次

關聯規則可以分為單層關聯規則和多層關聯規則。在單層的關聯規則中，所有的變量都沒有考慮到現實的數據是具有多個不同層次的;而在多層的關聯規則中，對數據的多層性已經進行了充分的考慮。

3)基于規則中涉及到的數據的維數

關聯規則可以分為單維的和多維的。在單維的關聯規則中只涉及到數據的一個維，如用戶購買的物品;而在多維的關聯規則中，要處理的數據將會涉及多個維。換句話說，即單維關聯規則是處理單個屬性中的一些關系;多維關聯規則是處理各個屬性之間的某些關系。

3 關聯規則的評價

1)系統客觀層面

系統客觀的層面評價是指關聯規則的有趣性是由規則的具體結構和在數據挖掘過程中所依賴的數據決定的。支持度和可信度度量是系統客觀層面評價關聯規則的兩個常用客觀性指標，這種方法主要是在這些規則上應用統計學方法，用定量的數值來判定規則的有趣性，從而避免了人為的主觀意見。因此從這個意義上講，規則有趣性的客觀評價是可靠的、有說服力的。關于關聯規則的系統客觀層面評價方法近幾年的研究較多，許多學者在傳統的支持度—可信度評價方法基礎上提出了很多實用的評價方法，如興趣度評價[2~5]、新穎度評價[6]、簡潔性評價[7]等。

由于使用支持度和信任度框架可能會產生一些不正確的規則，只憑支持度和信任度閾值的系統客觀的層面評價未必總能找出符合實際的規則。

2)用戶主觀的層面

只有用戶才能決定規則的有效性、可行性，所以應該將用戶的需求與系統更加緊密地結合起來，形成用戶主觀的層面評價。可以采用基于約束(constraint-based)的數據挖掘方法，具體約束的內容有數據約束、 限定數據挖掘的維和層次、規則約束。如果把某些約束條件與算法緊密結合，既能提高數據挖掘效率，又能明確數據挖掘的目標。

4 關聯規則挖掘技術進展

關聯規則挖掘在本質上是I/O負載集中的，為了高效地進行關聯規則挖掘，需要減少對數據庫的I/O操作次數，有以下兩種方式，即減少對數據庫的掃描次數和并行化。近年來，這兩個方面的研究都取得了一些成果。

4.1 減少對數據庫的掃描次數

4.1.1 Apriori算法及改進技術

在基于一維布爾型關聯規則的算法研究中，Agrawal首先提出關聯規則模型，并給出求解算法AIS[1]，隨后又出現了SETM等算法。在前兩者基礎上，Agrawal等人提出的Apriori是經典關聯規則算法。其主要理論依據是項集的兩個基本性質:頻繁項集的所有非空子集必是頻繁項集;任何非頻繁項集的超集也是非頻繁項集。算法采用逐層搜索的迭代，由連接和剪枝這兩步來實現。

Apriori算法的優點是簡單易懂，但同時也存在以下不足:

a)當事務數據庫中頻繁1-項集的數目|L1|較大時，候選k-項集Ck尤其是候選2-項集將非常大，這也是Apriori算法的一個效率瓶頸。

b)為了由Ck產生Lk，需要重復掃描數據庫中的事務并計算Ck中各候選項集的支持計數，特別當事務數據庫中的事務個數較大時，其效率十分低下。

針對Apriori算法的改進算法大都是從以上兩個方面著手對其進行優化，如AprioriTid[2]、AprioriHybrid[2]、DHP[3]、DIC[4]和Sampling[5，6]算法。

AprioriTid是Agrawal在Apriori算法后提出的一種改進算法。AprioriTid在每次候選集計數時通過減少要掃描的數據集中的記錄數目來加以優化，該算法在后期迭代中要比Apriori算法有效。AprioriHybrid算法是將Apriori與AprioriTid算法混合，利用各自優點彌補不足。算法的思想是先使用Apriori算法，當能匹配的事務減少到內存可以容納的程度再使用AprioriTid算法。經過算法統計平均，AprioriHybrid比Apriori效率高30%，比AprioriTid高60%，但是應用上比兩者都復雜，相對而言用Apriori可以得到更簡單的應用。

Park等人提出的DHP算法是將哈希表結構用于關聯規則挖掘，主要有兩處改進:

a)有效進行數據集刪減;

b)過濾由k-項集連接產生的候選集。

DHP算法有效地減少了候選集的數目，尤其是在前期迭代中，算法相當高效。但是在創建hash表和每次迭代時將更改后的數據集寫入磁盤將產生相當量的開銷，所以在DHP算法中的后期迭代中，僅進行數據集的刪減優化，而不進行候選集的進一步過濾。

Brin提出的DIC算法和Mannila和Toivonen等人提出的Sampling算法試圖使用較少的掃描次數或掃描較少的事務記錄來獲得性能的提升。DIC算法在添加一個新的候選集前，先估計一下是否它的所有子集都是頻繁的。它把項目集分成四種不同的狀態，即確認的大項集、確認的小項集、可疑的大項集和可疑的小項集，在這種變形中，可以在任何開始點添加新的候選項集。該技術動態地評估已被計數的所有項集的支持度，如果一個項集的所有子集已被確定為頻繁的，則添加它作為新的候選，并通過區間劃分減少遍歷數據庫的次數。Mannila等人提出的Sampling[5]在采用基于前一遍掃描得到的信息得到了一個改進算法;隨后Toivonen又進一步發展了這個思想[6]，對事務數據庫D進行隨機抽樣得到抽樣事務數據庫D′，先以小于用戶給定的最小支持度的支持度發現存在于D′中大項集L′，再在剩下的數據庫D-D′中繼續計算L′中各元素的支持數，最后以用戶給定的最小支持度計算出大項集L。Sampling算法可以顯著降低為挖掘付出的I/O代價，被廣泛地應用于網絡測量及其他領域對被測總體的指標進行估計[7]。但是它的最大問題是抽樣數據的選取以及由此而產生的結果偏差過大，即存在所謂數據扭曲問題。由于以上兩種算法對數據特征的高度依賴性，為保證算法的精確性和完備性不得不采用其他彌補措施，往往帶來候選集集合的爆炸，引起性能急劇下降。

Han Jia-wei等人[8]針對Apriori算法在處理長模式和密集數據集所表現出來的較低性能，提出了不生成候選集直接生成頻繁模式的算法FP-growth。其基本思想是將整個數據庫壓縮表達為FP-tree，將頻繁模式挖掘過程轉換為遞歸地產生條件子庫及對應的條件FP-tree的過程。FP-growth算法在數據集相當密集或支持度閾值較低時，FP-tree的密度是相當高的，計數的有效性抵銷了其維護成本，在性能表現上相當出色。

針對FP-growth算法，為了減少遍歷FP-tree的時間，提高算法的運行效率，Grahne等人[9]提出了FP-growth算法，引入了附加的數組結構，通過數組的引入避免了提取模式時構造頻繁模式樹的遍歷。與FP-growth算法相比，此算法對稀疏的事務數據集尤其有效。

4.1.2 其余相關算法

Agrawal首先提出用圖論和格的理論求解頻繁項集的方法，Zakia還用項集聚類技術求解最大的近似潛在頻繁項集，然后用格遷移思想生成每個聚類中的頻繁項集。后來出現的Prutax算法[10]就是用格遍歷的辦法求解頻繁項集，該算法使用垂直數據庫布局的形式，避免了由于深度優先遍歷項集格而產生的不必要的候選項目集。

關聯規則挖掘算法最初用于挖掘大型事務數據庫中項與項間的有趣關系，后來Liu Bing等人[11]設計出基于關聯的分類規則挖掘算法CBA，它是分類技術與關聯規則思想相結合的產物，并給出解決方案和算法。文獻[12]提出的CMAR算法，利用加權χ2計算規則前件和后件的相關度，以選擇合適規則區分測試數據。文獻[13]通過挖掘詞和類別之間的關聯規則進行分類。文獻[14]討論了利用關聯規則實現Web文檔聚類的方法。

針對Toivonen改進Sampling算法中存在的數據扭曲問題，Lin等人[15]討論了反扭曲(anti-skew)算法來挖掘關聯規則，使得掃描數據庫的次數少于兩次，算法使用了一個采樣處理來收集有關數據的次數以減少掃描遍數，從而使算法具有較好的均衡性。

Liu Jun-qiang等人[16]提出伺機挖掘思想，首次發現密集型數據子集的虛擬投影方法以及稀疏型數據子集的非過濾投影方法，巧妙地解決了提高時間效率與節省存儲開銷的矛盾。提出在挖掘過程中不斷根據局部數據子集特性自動調整解空間搜索策略、決定數據子集表示形式、選擇投影方法的啟發式原則設計實現的算法OpportuneProject性能遠優于Apriori、FP-growth等， 特別是挖掘海量數據的性能要高若干數量級。

zden等人[17]的周期性關聯規則是針對具有時間屬性的事務數據庫，發現在規律性的時間間隔中滿足最小支持度和信任度的規則。zden提出了兩種循環關聯規則發現算法:a)先用Apriori類算法產生傳統關聯規則，再找出規則中蘊涵的循環關系;b)先找出循環的大項集再生成關聯關系。zden等人在效率上做了不少努力，如周期的簡化(cycle-pruning)、周期計算的省略(cycle-skipping)和周期的刪除(cycle-elimination)。

為了改進循環規則的表達能力，可以使用日歷代數表達時態現象，貝爾實驗室的Ramaswamy等人[18]進一步發展了周期性關聯規則，提出挖掘符合日歷的關聯規則(calendric association rules)算法，用于進行市場貨籃分析。

Fang等人給出冰山查詢數據挖掘算法。所謂冰山查詢是在屬性或屬性集上計算大于等于給定閾值的聚集函數值。Hannu等人把負邊界引入規則發現算法中，每次挖掘不僅保存頻繁項集，同時保存負邊界，以達到下次挖掘時減少掃描次數的目的。

即Apriori 和FP-tree等算法之后，為了解決算法其本身都無法更新、維護和管理已挖掘出來的關聯規則等問題，Cheung等人[19]提出關聯規則的增量算法FUP及FUP2。所謂增量式挖掘算法是指針對動態變化的數據庫或數據倉庫，當某些情況發生變化時并不需要重新掃描整個數據庫，而是在原來挖掘結果的基礎上作由新情況所引起的更新。增量式挖掘使得關聯規則庫處于動態更新狀態，既具有動態的學習能力，又有相對較優的時間特性。

針對增量式挖掘算法中數據庫或數據倉庫保持不變，調整最小支持度與最小置信度引起關聯規則發生變化這種情況，馮玉才等人[20]提出了IUA，朱玉全等人[21]提出了FIUA等關聯規則的增量式更新算法。Thomas等人把負邊界的概念引入其中，進一步發展了增量算法。有學者[22，23]認為，在增量算法中，如何實現事務數據庫發生變化(包括數據量增加和減少)時的更新問題將是今后的研究工作。

4.2 并行化

在大數據量環境下進行關聯規則的挖掘需要充分的處理器資源，單處理機無論是運算能力還是內存都很難滿足算法和應用的需求。為了提高關聯規則挖掘的效率，有利于系統的擴展性，可以使用多CPU計算機系統對關聯規則進行并行挖掘。

并行挖掘能解決單機環境下串行實現所形成的下列缺陷:對數據庫進行多次掃描;可能產生大量的候選集;占用大量的系統資源，很容易受到內存或響應時間的限制。早期關聯規則并行算法有CD(count distribution)、DD(data distribution)和CaD(candidate distribution)。

后來出現的Par-Eclat、Par-MaxEclat、Par-Clique、Par-MaxClique[24]是基于集群和格遍歷的四種并行算法。新算法克服了CD和CaD算法的缺點，它們通過將項目集集群分割成小集合以利用系統的聚集內存(這些小集合被分配給不同的處理器)，運用垂直型數據庫分布，這樣在項目集標志符列表中所有相關信息均構成一個集群。每個處理器一次只能計算一個集群中的所有頻繁項目集，局部數據庫分區也只能掃描一次。新的算法不會在建立或尋找復雜數據結構上增加額外的開銷，也不會產生每一個事務的所有子集。但剪枝存在冗余節點，劃分數據庫存在無用的記錄復制，從而不能得到好的負載平衡。

NPGM(non partitioned generalized association rule mining) 和H-HPGM(hash) (hierarchical hash partitioned generalized association rule mining)，這兩種算法都是基于候選分割的負載平衡策略的。這種策略將候選項目集進行分割，使得對于每個節點搜索到的候選的數目等同于通過前一步信息所預計的支持度。

分析以上內容，可以認為一個好的并行算法要達到有效劃分數據，需盡可能減少處理機之間的依賴關系，使各處理機能獨立地進行處理;達到負載平衡，最大化算法并行的效率;減少處理機之間的通信和同步，好的并行算法允許各節點異步操作。

5 結束語

本文對關聯規則挖掘技術、分類方法、評價及其研究進展進行了詳細的描述，并對相關算法進行了深入探討。該領域未來的發展，筆者認為可以在如下方面進行研究:在處理極大量的數據時如何提高算法效率;對于挖掘迅速更新的數據的挖掘算法的進一步研究;在增量算法中，如何實現事務數據庫發生變化(包括數據量增加和減少)時的更新問題;在關聯規則并行算法中，如何尋找有效的負載平衡點等。

參考文獻:

[1]AGRAWAL R， IMIELINSKI T， SWAMI A. Mining association rules between sets of items in large databases[C]//Proc of ACM SIGMOD International Conference on Management of Data. New York: ACM Press， 1993: 207-216.

[2]AGRAWAL R， SRIKANT R. Fast algorithms for mining association rules[C]//Proc of the 20th International Conference on Very Large Data Bases. San Francisco:Morgan Kaufmann Publishers， 1994: 478-499.

[3]PARK J S， CHEN M S， YU P S. Using a hash based method with transaction trimming for mining association rules[J]. IEEE Trans on Knowledge and Data Engineering， 1997， 9(5):813-825.

[4]BRIN S， MOTWANI R， ULLMAN J D， et al. Dynamic itemset counting and implication rules for market basket data[C]//Proc ofACM SIGMOD International Conference on Management of Data. New York: ACM Press， 1997: 255-264.

[5]MANNILA H， TOIVONEN H， VERKAMO A I. Efficient algorithms for discovering association rules[C]//Proc of the AAAI Workshop on Knowledge Discovery in Databases. Washington: AAAI Press， 1994:181-192.

[6]TOIVONEN H. Sampling large databases for association rules[C]//Proc of the 22nd International Conference on Very Large Data Bases. Sam Francisco: Morgan Kaufmann Publishers， 1996: 134-145.

[7]王俊峰， 楊建華， 周虹霞， 等. 網絡測量中自適應數據采集方法[J]. 軟件學報， 2004， 15(8):1227-1236

[8]HAN Jia-wei， PEI Jian， YIN Yi-wen. Mining frequent patterns without candidate generation[C]//Proc of ACM SIGMOD International Conference on Management of Data. New York:ACM Press， 2000:1-12.

[9]GRAHNE G， ZHU Jian-fei. Efficiently using prefix-trees in mining frequent itemsets[C]//Proc of IEEE ICDM Workshop on Frequent Itemset Mining Implementations. 2003.

[10]PIEPRZYK J， MORZY M. Mining generalized association rules using prutax and hierarchical bitmap index[EB/OL]. [2009-02-19]. http://www.cs.put.poznan.pl/mmorzy/papers/admkd07.pdf.

[11]LIU Bing， HSU Wynne， and MA Yi-ming . Integrating classification and association rule mining[EB/OL]. [2009-02-19]. http://www.comp.nus.edu.sg/~maym/publication/kdd98.doc.

[12]LI Wen-min， HAN Jia-wei， PEI Jian. CMAR: accurate and efficient classification based on multiple class-association rules[C]//Proc of IEEE International Conference on Data Mining. Washington DC: IEEE Computer Society， 2001:369-376.

[13]ANTONIE M L， ZAIANE O R. Text document categorization by term association[C]//Proc of IEEE International Conference on Data Mi-ning. Washington DC: IEEE Computer Society， 2002:19-26.

[14]宋擒豹， 沈鈞毅. 基于關聯規則的Web文檔聚類算法[J]. 軟件學報， 2002， 13(3):417-423.

[15]LIN Jun-lin， DUNHAM M H. Mining association rules: anti-skew algorithms[C]//Proc of the 14th International Conference on Data Engineering. Washington DC: IEEE Computer Society， 1998:486-493.

[16]LIU Jun-qiang， PAN Yun-he， WANG Ke， et al. Mining frequent item sets by opportunistic projection[C]//Proc of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mi-ning. New York: ACM Press， 2002: 229-238.

[17]ZDEN B， RAMASWAMY S， SILBERSCHATZ A. Cyclic association rules[C]//Proc of the 14th International Conference on Data Engineering.Washington DC: IEEE Computer Society， 1998: 412-421.

[18]RAMASWAMY S， MAHAJAN S， SILBERSCHATZ A. On the discovery of interesting patterns in association rules[C]//Proc of the 24th Internatioal Conference on Very Large Data Bases. San Francisco: Morgan Kaufmann Publishers， 1998: 368-379.

[19]CHEUNG D W， HAN Jia-wei， NG V T， et al. Maintenance of discovered association rules in large databases: an incremental updating technique[C]//Proc of the 12th International Conference on Data Engineering. Washington DC: IEEE Computer Society， 1996: 106-114.

[20]馮玉才， 馮劍琳. 關聯規則的增量式更新算法[J]. 軟件學報， 1998， 9(4):301-306.

[21]朱玉全， 孫志揮. 快速更新頻繁項集[J]. 計算機研究與發展， 2003， 40(1):94-99.

[22]GHOSH A， NATH B. Multi-objective rule mining using genetic algorithms[J]. Information Sciences， 2004， 163(1-3): 123-133.

[23]TSENG M C， LIN Wen-yang. Maintenance of generalized association rules with multiple minimum supports[J]. Intelligent Data Analysis， 2004，8(4):417-436.

[24]ZAKI M J. Scalable algorithms for association mining[J]. IEEE Trans on Knowledge and Data Engineering， 2000， 12(3):372-390.