關聯規則研究

摘要:對關聯規則挖掘技術進行了研究，描述了關聯規則的基本概念，介紹了關聯規則的分類;闡述了挖掘關聯規則的步驟，并展望了關聯規則進一步的研究方向。關聯規則挖掘作為數據挖掘領域的一個重要研究內容，它揭示了項集之間有趣的相關關系，可廣泛應用于購物籃分析、數據分析、分類、網絡個性化服務、企業電子商務中客戶數據挖掘等廣泛領域。

關鍵詞:數據挖掘; 關聯規則; 關聯規則挖掘

中圖分類號:TP311.13 文獻標志碼:A文章編號:1673-291X(2010)11-0198-02

數據挖掘是一個飛速發展的領域，不斷有新的技術和系統出現。而如何將這一技術應用于實際工作中，還需要作更深一步的開發與研究，作為一個年輕的和很有希望的領域，數據挖掘依然面臨著很大挑戰和許多等待解決的問題。

在數據挖掘的知識模式中，關聯規則模式是比較重要的一種，也是最活躍的一個分支。

一、關聯規則的基本概念

關聯規則表示數據庫中一組對象之間某種關聯關系的規則。例如，關聯規則可以表示為“購買了項目A和B的顧客中有95%的人又買了C和D”。從這些規則可找出顧客購買行為模式，可以應用于商品貨架設計、生產安排、針對性的市場營銷等。

采用關聯模型比較典型的例子是“啤酒和尿布”的故事。關聯規則問題由Agrawa1等人于1993年首先提出，隨即引起了廣泛的關注。許多研究者(包括R.Agrawal本人)對關聯規則挖掘問題進行深入的研究，對最初的關聯規則挖掘算法進行了改進和擴展。同時，關聯規則的挖掘被應用到許多其它領域的數據庫，取得了良好的挖掘效果。

為了準確地描述關聯規則挖掘問題，便于問題的討論，給出關聯規則挖掘問題的正式定義[1]:

定義1關聯規則挖掘的數據集記為D(D為事務數據庫)，D={t1，t2，…，tk，…，tn}，tk={i1，i2，…，ij…，…ip}(k=1，2，…，n)為一條事務;tk中的元素ij(j=1，2，…，P)稱為項目(item)。

定義2設I={i1，i2，…，in}是事務數據庫D中全體項目組成的集合，I的任何子集X稱為D中的項目集(itemset)，|X|=k稱集合X為k項目集。設tk和X分別為D中的事務和項目集，如果X?哿tk，稱事務tk包含項目集X。

事務和項目集雖然都是項目的集合，但兩者有不同的含義。事務是數據庫D的組成元素(類似于關系數據庫中的記錄或元組)，而項目僅僅是為挖掘關聯規則而規定的項目組合(類似于關系數據庫中的字段)。事務與項目集的包含關系表明對該事務來說，此項目集中的各個項目是相互關聯的。

定義3數據集D中包含項目集X的事務數稱為項目集X的支持數，記為σx。項目集X的支持率，記作:support(X)，即概率P(X)。[1]

support(X)= ■×100%(1)

其中，|D|是數據集D的事務數。若support(X)不小于用戶指定的最小支持率(記作:minsupport)，則稱X為頻繁項目集(或大項目集)，否則稱X為非頻繁項目集(或小項目集)。

定義4若X、Y為項目集，且X∩Y=?準，蘊涵式X?圯Y稱為關聯規則，X、Y分別稱為關聯規則X?圯Y的前提和結論。項目集(X?圯Y)的支持率稱為關聯規則X?圯Y的支持率，是D中事務包含(X∪Y)的百分比，即概率P(X∪Y)，記作:support(X?圯Y)[2]。

support(X?圯Y)=support(X∪Y)=P(X∪Y)(2)

關聯規則X?圯Y的置信度是D中事務包含X的同時也包含Y的百分比，即條件概率P(Y│X)，記作:confidence(X?圯Y)。

confidence(X?圯Y)=■×100%=P(Y│X)(3)

支持度和置信度是描述關聯規則的兩個重要概念，前者用于衡量關聯規則在整個數據集中的統計重要性，后者用于衡量關聯規則的可信程度。一般來說，只有支持度和置信度均較高的關聯規則才可能是用戶感興趣的、有用的關聯規則。

通常，用戶根據挖掘需要指定最小支持度(記為minsupport)和最小置信度(記為minconfidence)。前者描述了關聯規則的最低重要程度，后者規定了關聯規則必須滿足的最低可靠性。

二、關聯規則的分類

我們將關聯規則按不同的情況進行分類:

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

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

3.基于規則中涉及到的數據的維數，關聯規則可以分為單維的和多維的。

在實際中，用戶往往并不是對所有的關聯規則都感興趣，而只想知道關于某方面的關聯規則，如那些至少包含用戶指定的項目集中一項的規則等。這時就需要定義約束條件，進行約束性關聯規則的挖掘。

三、挖掘關聯規則的步驟

關聯規則挖掘的任務就是要挖掘出數據庫D中所有的強規則，可以把關聯規則挖掘劃分為兩個子問題[3]:(1)根據最小支持率找出數據集D中的所有頻繁項目集;(2)根據頻繁項目集和最小置信度產生關聯規則。

第一個子問題的任務是迅速高效的找出D中全部頻繁項目集，是關聯規則挖掘的中心問題，是衡量關聯規則挖掘算法的標準;第二個子問題求解是比較容易的、直接的，目前所有的關聯規則挖掘算法都是針對第一個子問題而提出的。關聯規則挖掘的基本模型如圖1。

圖1中D為數據集，Algorithm-1為頻繁項目集的搜索算法，Algorithm-2為關聯規則的產生算法，R為挖出的關聯規則集合。用戶通過指定minsupport、minconfidence分別與算法Algorithm-1和Algorithm-2交互，并通過與R的交互對挖掘結果進行解釋和評價。

關聯規則挖掘算法主要考慮的問題有兩個[4]:(1)減少操作。關聯規則挖掘的數據集有時候可達GB甚至TB數量級，頻繁的I/O操作必將影響關聯規則的挖掘效率，減少I/O操作主要是減少掃描數據集D的次數;(2)降低需要計算支持率的項目集(常稱之為候選項目集)的數量，使其與頻繁項目集的數量接近，候選項目集數量的降低可以節省為處理部分候選項目集所需的計算時間和存儲空間。

到目前為止，關聯規則挖掘產生了大量的挖掘算法，大致可分為搜索算法、層次算法、數據集劃分算法、抽樣算法等等。國內外對這些算法的研究已經有很多，層次算法有時也稱為循環算法，主要是按項目數自小而大的順序尋找頻繁項目集，常見的算法有:Apriori、AprioriTid、AprioHybro和DHA等等。

四、進一步研究的方向

目前，數據庫挖掘關聯規則己經取得了令人矚目的成績，但對下列問題進行研究也將是具有挑戰性的工作。

1.開發更高效的挖掘算法

數據庫容量的日益增大，不僅增大了挖掘算法的搜索空間，而且也增加了盲目發現的可能性。因此我們必須利用領域知識去提取與我們發現任務有關的數據，刪除無用數據，有效的降低問題的維數，設計出更加有效的挖掘算法。

在這方面，基于約束的關聯規則挖掘具有廣闊的前途。

2.可視化挖掘

設計一個靈活方便的用戶界面，允許用戶與挖掘系統進行交互，并對所挖掘的結果進行很好的可視化表示，使非領域專家也能夠進行挖掘。

3.基于不同媒體的挖掘

目前，大多數據挖掘關聯規則算法都是基于關系數據庫或事務數據庫的算法，設計應用于其他類型數據庫(如面向對象數據庫、多維數據庫、數據倉庫等)關聯規則挖掘算法也將是十分有意義的工作。

隨著研究的進一步加強，數據挖掘技術必將應用在更廣闊的天地，為更多的領域提供更多有價值的信息。

參考文獻:

[1] 徐軍莉，喻國平.關聯規則挖掘算法的研究和應用[J].微計算機信息，2009，(12) .

[2] 孫年芳.關聯規則挖掘研究[J].電腦學習，2009，(1) .

[3] 劉紅梅.基于關聯規則的分類方法初探[J].電腦知識與技術，2009，(3) .

[4] 廖偉國，張宏書.關聯規則挖掘研究綜述[J].網絡財富， 2009，(7) .