1引言
數據挖掘（Data Mining），又稱(chēng)數據庫中的知識發(fā)現（Knowledge Discovery in Database），在最近幾年里已被數據庫界所廣泛研究，其中關(guān)聯(lián)規則（Association Rules）的挖掘是一個(gè)重要的問(wèn)題。
關(guān)聯(lián)規則是發(fā)現交易數據庫中不同商品（項）之間的聯(lián)系，這些規則找出顧客購買(mǎi)行為模式，如購買(mǎi)了某一商品對購買(mǎi)其他商品的影響。發(fā)現這樣的規則可以應用于商品貨架設計、貨存安排以及根據購買(mǎi)模式對用戶(hù)進(jìn)行分類(lèi)。
Agrawal等于1993年[1]首先提出了挖掘顧客交易數據庫中項集間的關(guān)聯(lián)規則問(wèn)題，以后諸多的研究人員對關(guān)聯(lián)規則的挖掘問(wèn)題進(jìn)行了大量的研究。他們的工作包括對原有的算法進(jìn)行優(yōu)化，如引入隨機采樣、并行的思想等，以提高算法挖掘規則的效率；對關(guān)聯(lián)規則的應用進(jìn)行推廣。
最近也有獨立于A(yíng)grawal的頻集方法的工作[18,19]，以避免頻集方法的一些缺陷，探索挖掘關(guān)聯(lián)規則的新方法。同時(shí)隨著(zhù)OLAP技術(shù)的成熟和應用，將OLAP和關(guān)聯(lián)規則結合[20,21]也成了一個(gè)重要的方向。也有一些工作[6]注重于對挖掘到的模式的價(jià)值進(jìn)行評估，他們提出的模型建議了一些值得考慮的研究方向。
本文第二部分是對關(guān)聯(lián)規則基本概念的介紹，提出了關(guān)聯(lián)規則的分類(lèi)方法；第三部分是對挖掘算法的介紹，從經(jīng)典的apriori開(kāi)始，然后描述了對該算法的優(yōu)化拓展，接著(zhù)講述脫離apriori算法的方法，最后是多層、多維的關(guān)聯(lián)規則挖掘；第四部分歸納出關(guān)聯(lián)規則價(jià)值衡量方法，主要從兩個(gè)方面進(jìn)行考慮：系統客觀(guān)層面和用戶(hù)主觀(guān)層面；最后展望了關(guān)聯(lián)規則挖掘的未來(lái)研究方向。
2關(guān)聯(lián)規則的基本概念
2.1基本概念和問(wèn)題描述
設I={i1, i2,…, im}是二進(jìn)制文字的集合，其中的元素稱(chēng)為項(item)。記D為交易(transaction)T的集合，這里交易T是項的集合，并且TÍI 。對應每一個(gè)交易有唯一的標識，如交易號，記作TID。設X是一個(gè)I中項的集合，如果XÍT，那么稱(chēng)交易T包含X。
一個(gè)關(guān)聯(lián)規則是形如XÞY的蘊涵式，這里XÌI, YÌI，并且XÇY=F。規則XÞY在交易數據庫D中的支持度（support）是交易集中包含X和Y的交易數與所有交易數之比，記為support(XÞY)，即
support(XÞY)=|{T:XÈYÍT，TÎD}|/|D|
規則XÞY在交易集中的可信度（confidence）是指包含X和Y的交易數與包含X的交易數之比，記為confidence(XÞY)，即
confidence(XÞY)=|{T: XÈYÍT，TÎD}|/|{T:XÍT，TÎD}|
給定一個(gè)交易集D，挖掘關(guān)聯(lián)規則問(wèn)題就是產(chǎn)生支持度和可信度分別大于用戶(hù)給定的最小支持度(minsupp)和最小可信度(minconf)的關(guān)聯(lián)規則。
2.2 關(guān)聯(lián)規則的種類(lèi)
我們將關(guān)聯(lián)規則按不同的情況進(jìn)行分類(lèi)：
1. 基于規則中處理的變量的類(lèi)別，關(guān)聯(lián)規則可以分為布爾型和數值型。
布爾型關(guān)聯(lián)規則處理的值都是離散的、種類(lèi)化的，它顯示了這些變量之間的關(guān)系；而數值型關(guān)聯(lián)規則可以和多維關(guān)聯(lián)或多層關(guān)聯(lián)規則結合起來(lái)，對數值型字段進(jìn)行處理，將其進(jìn)行動(dòng)態(tài)的分割，或者直接對原始的數據進(jìn)行處理，當然數值型關(guān)聯(lián)規則中也可以包含種類(lèi)變量。
例如：性別=“女”=>職業(yè)=“秘書(shū)” ，是布爾型關(guān)聯(lián)規則；性別=“女”=>avg（收入）=2300，涉及的收入是數值類(lèi)型，所以是一個(gè)數值型關(guān)聯(lián)規則。
2. 基于規則中數據的抽象層次，可以分為單層關(guān)聯(lián)規則和多層關(guān)聯(lián)規則。
在單層的關(guān)聯(lián)規則中，所有的變量都沒(méi)有考慮到現實(shí)的數據是具有多個(gè)不同的層次的；而在多層的關(guān)聯(lián)規則中，對數據的多層性已經(jīng)進(jìn)行了充分的考慮。
例如：IBM臺式機=>Sony打印機，是一個(gè)細節數據上的單層關(guān)聯(lián)規則；臺式機=>Sony打印機，是一個(gè)較高層次和細節層次之間的多層關(guān)聯(lián)規則。
3. 基于規則中涉及到的數據的維數，關(guān)聯(lián)規則可以分為單維的和多維的。
在單維的關(guān)聯(lián)規則中，我們只涉及到數據的一個(gè)維，如用戶(hù)購買(mǎi)的物品；而在多維的關(guān)聯(lián)規則中，要處理的數據將會(huì )涉及多個(gè)維。換成另一句話(huà)，單維關(guān)聯(lián)規則是處理單個(gè)屬性中的一些關(guān)系；多維關(guān)聯(lián)規則是處理各個(gè)屬性之間的某些關(guān)系。
例如：啤酒=>尿布，這條規則只涉及到用戶(hù)的購買(mǎi)的物品；性別=“女”=>職業(yè)=“秘書(shū)”，這條規則就涉及到兩個(gè)字段的信息，是兩個(gè)維上的一條關(guān)聯(lián)規則。
給出了關(guān)聯(lián)規則的分類(lèi)之后，在下面的分析過(guò)程中，我們就可以考慮某個(gè)具體的方法適用于哪一類(lèi)規則的挖掘，某類(lèi)規則又可以用哪些不同的方法進(jìn)行處理。
3.關(guān)聯(lián)規則挖掘的算法
3.1經(jīng)典頻集方法
Agrawal等于1993年[1]首先提出了挖掘顧客交易數據庫中項集間的關(guān)聯(lián)規則問(wèn)題，其核心方法是基于頻集理論的遞推方法。以后諸多的研究人員對關(guān)聯(lián)規則的挖掘問(wèn)題進(jìn)行了大量的研究。他們的工作包括對原有的算法進(jìn)行優(yōu)化，如引入隨機采樣、并行的思想等，以提高算法挖掘規則的效率；提出各種變體，如泛化的關(guān)聯(lián)規則、周期關(guān)聯(lián)規則等，對關(guān)聯(lián)規則的應用進(jìn)行推廣。
3.1.1核心算法
Agrawal等[1]在1993年設計了一個(gè)基本算法，提出了挖掘關(guān)聯(lián)規則的一個(gè)重要方法 — 這是一個(gè)基于兩階段頻集思想的方法，將關(guān)聯(lián)規則挖掘算法的設計可以分解為兩個(gè)子問(wèn)題：
1) 找到所有支持度大于最小支持度的項集（Itemset），這些項集稱(chēng)為頻集（Frequent Itemset)。
2) 使用第1步找到的頻集產(chǎn)生期望的規則。
這里的第2步相對簡(jiǎn)單一點(diǎn)。如給定了一個(gè)頻集Y=I1I2...Ik，k³2，Ij∈I，產(chǎn)生只包含集合{I1，I2，...，Ik}中的項的所有規則(最多k條)，其中每一條規則的右部只有一項，(即形如[Y-Ii]ÞIi，"1£i£k)，這里采用的是[4]中規則的定義。一旦這些規則被生成，那么只有那些大于用戶(hù)給定的最小可信度的規則才被留下來(lái)。對于規則右部含兩個(gè)以上項的規則，在其以后的工作中進(jìn)行了研究，本文后面考慮的是這種情況。
為了生成所有頻集，使用了遞推的方法。其核心思想如下：
(1) L1 = {large 1-itemsets};
(2) for (k=2; Lk-1¹F; k++) do begin
(3) Ck=apriori-gen(Lk-1); //新的候選集
(4) for all transactions tÎD do begin
(5) Ct=subset(Ck,t); //事務(wù)t中包含的候選集
(6) for all candidates cÎ Ct do
(7) c.count++;
(8) end
(9) Lk={cÎ Ck |c.count³minsup}
(10) end
(11) Answer=ÈkLk;
首先產(chǎn)生頻繁1-項集L1，然后是頻繁2-項集L2，直到有某個(gè)r值使得Lr為空，這時(shí)算法停止。這里在第k次循環(huán)中，過(guò)程先產(chǎn)生候選k-項集的集合Ck，Ck中的每一個(gè)項集是對兩個(gè)只有一個(gè)項不同的屬于Lk-1的頻集做一個(gè)(k-2)-連接來(lái)產(chǎn)生的。Ck中的項集是用來(lái)產(chǎn)生頻集的候選集，最后的頻集Lk必須是Ck的一個(gè)子集。Ck中的每個(gè)元素需在交易數據庫中進(jìn)行驗證來(lái)決定其是否加入Lk，這里的驗證過(guò)程是算法性能的一個(gè)瓶頸。這個(gè)方法要求多次掃描可能很大的交易數據庫，即如果頻集最多包含10個(gè)項，那么就需要掃描交易數據庫10遍，這需要很大的I/O負載。
在論文[6]中，Agrawal等引入了修剪技術(shù)（Pruning）來(lái)減小候選集Ck的大小，由此可以顯著(zhù)地改進(jìn)生成所有頻集算法的性能。算法中引入的修剪策略基于這樣一個(gè)性質(zhì)：一個(gè)項集是頻集當且僅當它的所有子集都是頻集。那么，如果Ck中某個(gè)候選項集有一個(gè)(k-1)-子集不屬于Lk-1，則這個(gè)項集可以被修剪掉不再被考慮，這個(gè)修剪過(guò)程可以降低計算所有的候選集的支持度的代價(jià)。文[6]中，還引入雜湊樹(shù)（Hash Tree）方法來(lái)有效地計算每個(gè)項集的支持度。
3.1.2頻集算法的幾種優(yōu)化方法
雖然Apriori算法自身已經(jīng)進(jìn)行了一定的優(yōu)化，但是在實(shí)際的應用中，還是存在不令人滿(mǎn)意的地方，于是人們相繼提出了一些優(yōu)化的方法。
1. 基于劃分的方法。Savasere等[14]設計了一個(gè)基于劃分(partition)的算法，這個(gè)算法先把數據庫從邏輯上分成幾個(gè)互不相交的塊，每次單獨考慮一個(gè)分塊并對它生成所有的頻集，然后把產(chǎn)生的頻集合并，用來(lái)生成所有可能的頻集，最后計算這些項集的支持度。這里分塊的大小選擇要使得每個(gè)分塊可以被放入主存，每個(gè)階段只需被掃描一次。而算法的正確性是由每一個(gè)可能的頻集至少在某一個(gè)分塊中是頻集保證的。上面所討論的算法是可以高度并行的，可以把每一分塊分別分配給某一個(gè)處理器生成頻集。產(chǎn)生頻集的每一個(gè)循環(huán)結束后，處理器之間進(jìn)行通信來(lái)產(chǎn)生全局的候選k-項集。通常這里的通信過(guò)程是算法執行時(shí)間的主要瓶頸；而另一方面，每個(gè)獨立的處理器生成頻集的時(shí)間也是一個(gè)瓶頸。其他的方法還有在多處理器之間共享一個(gè)雜湊樹(shù)來(lái)產(chǎn)生頻集。更多的關(guān)于生成頻集的并行化方法可以在[2,11,17]中找到。
2. 基于hash的方法。一個(gè)高效地產(chǎn)生頻集的基于雜湊(hash)的算法由Park等[10]提出來(lái)。通過(guò)實(shí)驗我們可以發(fā)現尋找頻集主要的計算是在生成頻繁2-項集Lk上，Park等就是利用了這個(gè)性質(zhì)引入雜湊技術(shù)來(lái)改進(jìn)產(chǎn)生頻繁2-項集的方法。
3. 基于采樣的方法?；谇耙槐閽呙璧玫降男畔?，對此仔細地作組合分析，可以得到一個(gè)改進(jìn)的算法，Mannila等[8]先考慮了這一點(diǎn)，他們認為采樣是發(fā)現規則的一個(gè)有效途徑。隨后又由Toivonen[16]進(jìn)一步發(fā)展了這個(gè)思想，先使用從數據庫中抽取出來(lái)的采樣得到一些在整個(gè)數據庫中可能成立的規則，然后對數據庫的剩余部分驗證這個(gè)結果。Toivonen的算法相當簡(jiǎn)單并顯著(zhù)地減少了I/O代價(jià)，但是一個(gè)很大的缺點(diǎn)就是產(chǎn)生的結果不精確，即存在所謂的數據扭曲(data skew)。分布在同一頁(yè)面上的數據時(shí)常是高度相關(guān)的，可能不能表示整個(gè)數據庫中模式的分布，由此而導致的是采樣5%的交易數據所花費的代價(jià)可能同掃描一遍數據庫相近。Lin和Dunham在[7]中討論了反扭曲(Anti-skew)算法來(lái)挖掘關(guān)聯(lián)規則，在那里他們引入的技術(shù)使得掃描數據庫的次數少于2次，算法使用了一個(gè)采樣處理來(lái)收集有關(guān)數據的次數來(lái)減少掃描遍數。
Brin等[4]提出的算法使用比傳統算法少的掃描遍數來(lái)發(fā)現頻集，同時(shí)比基于采樣的方法使用更少的候選集，這些改進(jìn)了算法在低層的效率。具體的考慮是，在計算k-項集時(shí)，一旦我們認為某個(gè)(k+1)-項集可能是頻集時(shí)，就并行地計算這個(gè)(k+1)-項集的支持度，算法需要的總的掃描次數通常少于最大的頻集的項數。這里他們也使用了雜湊技術(shù)，并提出產(chǎn)生“相關(guān)規則”（Correlation Rules）的一個(gè)新方法，這是基于他們的[3]工作基礎上的。
4. 減少交易的個(gè)數。減少用于未來(lái)掃描的事務(wù)集的大小。一個(gè)基本的原理就是當一個(gè)事務(wù)不包含長(cháng)度為k的大項集，則必然不包含長(cháng)度為k+1的大項集。從而我們就可以將這些事務(wù)移去，這樣在下一遍的掃描中就可以要進(jìn)行掃描的事務(wù)集的個(gè)數。這個(gè)就是AprioriTid的基本思想
3.2其他的頻集挖掘方法
上面我們介紹的都是基于A(yíng)priori的頻集方法。即使進(jìn)行了優(yōu)化，但是Apriori方法一些固有的缺陷還是無(wú)法克服：
1) 可能產(chǎn)生大量的候選集。當長(cháng)度為1的頻集有10000個(gè)的時(shí)候，長(cháng)度為2的候選集個(gè)數將會(huì )超過(guò)10M。還有就是如果要生成一個(gè)很長(cháng)的規則的時(shí)候，要產(chǎn)生的中間元素也是巨大量的。
2) 無(wú)法對稀有信息進(jìn)行分析。由于頻集使用了參數minsup，所以就無(wú)法對小于minsup的事件進(jìn)行分析；而如果將minsup設成一個(gè)很低的值，那么算法的效率就成了一個(gè)很難處理的問(wèn)題。
下面將介紹兩種方法，分別用于解決以上兩個(gè)問(wèn)題。
在[18]中提到了解決問(wèn)題1的一種方法。采用了一種FP-growth的方法。他們采用了分而治之的策略：在經(jīng)過(guò)了第一次的掃描之后，把數據庫中的頻集壓縮進(jìn)一棵頻繁模式樹(shù)（FP-tree），同時(shí)依然保留其中的關(guān)聯(lián)信息。隨后我們再將FP-tree分化成一些條件庫，每個(gè)庫和一個(gè)長(cháng)度為1的頻集相關(guān)。然后再對這些條件庫分別進(jìn)行挖掘。當原始數據量很大的時(shí)候，也可以結合劃分的方法,使得一個(gè)FP-tree可以放入主存中。實(shí)驗表明，FP-growth對不同長(cháng)度的規則都有很好的適應性，同時(shí)在效率上較之a(chǎn)priori算法有巨大的提高。
第二個(gè)問(wèn)題是基于這個(gè)的一個(gè)想法：apriori算法得出的關(guān)系都是頻繁出現的，但是在實(shí)際的應用中，我們可能需要尋找一些高度相關(guān)的元素，即使這些元素不是頻繁出現的。在apriori算法中，起決定作用的是支持度，而我們現在將把可信度放在第一位，挖掘一些具有非常高可信度的規則。在[19]中介紹了對于這個(gè)問(wèn)題的一個(gè)解決方法。整個(gè)算法基本上分成三個(gè)步驟：計算特征、生成候選集、過(guò)濾候選集。在三個(gè)步驟中，關(guān)鍵的地方就是在計算特征時(shí)Hash方法的使用。在考慮方法的時(shí)候，有幾個(gè)衡量好壞的指數：時(shí)空效率、錯誤率和遺漏率?；镜姆椒ㄓ袃深?lèi)：Min_Hashing(MH)和Locality_Sensitive_Hashing(LSH)。Min_Hashing的基本想法是：將一條記錄中的頭k個(gè)為1的字段的位置作為一個(gè)Hash函數。Locality_Sentitive_Hashing的基本想法是：將整個(gè)數據庫用一種基于概率的方法進(jìn)行分類(lèi)，使得相似的列在一起的可能性更大，不相似的列在一起的可能性較小。我們再對這兩個(gè)方法比較一下。MH的遺漏率為零，錯誤率可以由k嚴格控制，但是時(shí)空效率相對的較差。LSH的遺漏率和錯誤率是無(wú)法同時(shí)降低的，但是它的時(shí)空效率卻相對的好很多。所以應該視具體的情況而定。最后的實(shí)驗數據也說(shuō)明這種方法的確能產(chǎn)生一些有用的規則。
3.3多層和多維關(guān)聯(lián)規則的挖掘
隨著(zhù)數據倉庫和OLAP技術(shù)研究的深入，可以預見(jiàn)大量的數據將經(jīng)過(guò)整合、預處理，從而存入數據倉庫之中。在當前，大多數的數據倉庫的應用都是進(jìn)行統計、建立多維以及OLAP的分析工作。隨著(zhù)數據挖掘研究的深入，已經(jīng)有了OLAP和數據挖掘相結合的方法[20,21]。
首先一個(gè)有效的數據挖掘方法應該可以進(jìn)行探索性的數據分析。用戶(hù)往往希望能在數據庫中穿行，選擇各種相關(guān)的數據，在不同的細節層次上進(jìn)行分析，以各種不同的形式呈現知識?；贠LAP的挖掘就可以提供在不同數據集、不同的細節上的挖掘，可以進(jìn)行切片、切塊、展開(kāi)、過(guò)濾等各種對規則的操作。然后再加上一些可視化的工具，就能大大的提高數據挖掘的靈活性和能力。接著(zhù)，我們來(lái)看一下多層和多維關(guān)聯(lián)規則的定義。
多層關(guān)聯(lián)規則：
對于很多的應用來(lái)說(shuō)，由于數據分布的分散性，所以很難在數據最細節的層次上發(fā)現一些強關(guān)聯(lián)規則。當我們引入概念層次后，就可以在較高的層次上進(jìn)行挖掘。雖然較高層次上得出的規則可能是更普通的信息，但是對于一個(gè)用戶(hù)來(lái)說(shuō)是普通的信息，對于另一個(gè)用戶(hù)卻未必如此。所以數據挖掘應該提供這樣一種在多個(gè)層次上進(jìn)行挖掘的功能。
多層關(guān)聯(lián)規則的分類(lèi)：根據規則中涉及到的層次，多層關(guān)聯(lián)規則可以分為同層關(guān)聯(lián)規則和層間關(guān)聯(lián)規則。
多層關(guān)聯(lián)規則的挖掘基本上可以沿用“支持度-可信度”的框架。不過(guò)，在支持度設置的問(wèn)題上有一些要考慮的東西。
同層關(guān)聯(lián)規則可以采用兩種支持度策略：
1) 統一的最小支持度。對于不同的層次，都使用同一個(gè)最小支持度。這樣對于用戶(hù)和算法實(shí)現來(lái)說(shuō)都比較的容易，但是弊端也是顯然的。
2) 遞減的最小支持度。每個(gè)層次都有不同的最小支持度，較低層次的最小支持度相對較小。同時(shí)還可以利用上層挖掘得到的信息進(jìn)行一些過(guò)濾的工作。
層間關(guān)聯(lián)規則考慮最小支持度的時(shí)候，應該根據較低層次的最小支持度來(lái)定。
多維關(guān)聯(lián)規則：
以上我們研究的基本上都是同一個(gè)字段的值之間的關(guān)系，比如用戶(hù)購買(mǎi)的物品。用多維數據庫的語(yǔ)言就是單維或者叫維內的關(guān)聯(lián)規則，這些規則一般都是在交易數據庫中挖掘的。但是對于多維數據庫而言，還有一類(lèi)多維的關(guān)聯(lián)規則。例如：
年齡（X，“20...30”）Ù職業(yè)（X,“學(xué)生”）==> 購買(mǎi)(X，“筆記本電腦”)
在這里我們就涉及到三個(gè)維上的數據：年齡、職業(yè)、購買(mǎi)。
根據是否允許同一個(gè)維重復出現，可以又細分為維間的關(guān)聯(lián)規則（不允許維重復出現）和混合維關(guān)聯(lián)規則（允許維在規則的左右同時(shí)出現）。
年齡（X，“20...30”）Ù購買(mǎi)(X，“筆記本電腦”) ==> 購買(mǎi)(X，“打印機”)
這個(gè)規則就是混合維關(guān)聯(lián)規則。
在挖掘維間關(guān)聯(lián)規則和混合維關(guān)聯(lián)規則的時(shí)候，還要考慮不同的字段種類(lèi)：種類(lèi)型和數值型。
對于種類(lèi)型的字段，原先的算法都可以處理。而對于數值型的字段，需要進(jìn)行一定的處理之后才可以進(jìn)行。處理數值型字段的方法基本上有以下幾種：
1) 數值字段被分成一些預定義的層次結構。這些區間都是由用戶(hù)預先定義的。得出的規則也叫做靜態(tài)數量關(guān)聯(lián)規則。
2) 數值字段根據數據的分布分成了一些布爾字段。每個(gè)布爾字段都表示一個(gè)數值字段的區間，落在其中則為1，反之為0。這種分法是動(dòng)態(tài)的。得出的規則叫布爾數量關(guān)聯(lián)規則。
3) 數值字段被分成一些能體現它含義的區間。它考慮了數據之間的距離的因素。得出的規則叫基于距離的關(guān)聯(lián)規則。
4) 直接用數值字段中的原始數據進(jìn)行分析。使用一些統計的方法對數值字段的值進(jìn)行分析，并且結合多層關(guān)聯(lián)規則的概念，在多個(gè)層次之間進(jìn)行比較從而得出一些有用的規則。得出的規則叫多層數量關(guān)聯(lián)規則。
在OLAP中挖掘多層、多維的關(guān)聯(lián)規則是一個(gè)很自然的過(guò)程。因為OLAP本身的基礎就是一個(gè)多層多維分析的工具，只是在沒(méi)有使用數據挖掘技術(shù)之前，OLAP只能做一些簡(jiǎn)單的統計，而不能發(fā)現其中一些深層次的有關(guān)系的規則。當我們將OLAP和DataMining技術(shù)結合在一起就形成了一個(gè)新的體系OLAM（On-Line Analytical Mining）[20]。
4關(guān)聯(lián)規則價(jià)值衡量的方法
當我們用數據挖掘的算法得出了一些結果之后，數據挖掘系統如何知道哪些規則對于用戶(hù)來(lái)說(shuō)是有用的、有價(jià)值的？這里有兩個(gè)層面：用戶(hù)主觀(guān)的層面和系統客觀(guān)的層面。
4.1系統客觀(guān)層面：
很多的算法都使用“支持度-可信度”的框架。這樣的結構有時(shí)會(huì )產(chǎn)生一些錯誤的結果?？慈缦碌囊粋€(gè)例子：
假設一個(gè)提供早餐的零售商調查了4000名學(xué)生在早晨進(jìn)行什么運動(dòng)，得到的結果是2200名學(xué)生打籃球，2750名學(xué)生晨跑，1800名學(xué)生打籃球、晨跑。那么如果設minsup為40%，minconf為60%，我們可以得到如下的關(guān)聯(lián)規則：
打籃球Þ晨跑 （1）
這條規則其實(shí)是錯誤的，因為晨跑的學(xué)生的比例是68%，甚至大于60%。然而打籃球和晨跑可能是否定關(guān)聯(lián)的，即當我們考慮如下的關(guān)聯(lián)時(shí)：
打籃球Þ（不）晨跑 （2）
雖然這條規則的支持度和可信度都比那條蘊涵正向關(guān)聯(lián)的規則（1）低，但是它更精確。 然而，如果我們把支持度和可信度設得足夠低，那么我們將得到兩條矛盾的規則。但另一方面，如果我們把那些參數設得足夠高，我們只能得到不精確的規則?？傊?，沒(méi)有一對支持度和可信度的組合可以產(chǎn)生完全正確的關(guān)聯(lián)。
于是人們引入了興趣度，用來(lái)修剪無(wú)趣的規則，即避免生成“錯覺(jué)”的關(guān)聯(lián)規則。一般一條規則的興趣度是在基于統計獨立性假設下真正的強度與期望的強度之比，然而在許多應用中已發(fā)現，只要人們仍把支持度作為最初的項集產(chǎn)生的主要決定因素，那么要么把支持度設得足夠低以使得不丟失任何有意義的規則，或者冒丟失一些重要規則的風(fēng)險；對前一種情形計算效率是個(gè)問(wèn)題，而后一種情形則有可能丟失從用戶(hù)觀(guān)點(diǎn)來(lái)看是有意義的規則的問(wèn)題。
在[12]中作者給出了感興趣的規則的定義（R-interesting），在[13]中他們又對此作了改進(jìn)。在[10]中把事件依賴(lài)性的統計定義擴展到興趣度的定義上來(lái)；[15]定義了否定關(guān)聯(lián)規則的興趣度。
除了把興趣度作為修剪無(wú)價(jià)值規則的工具，現在已有許多其他的工作來(lái)重新認識項集，如Brin等[3]考慮的相關(guān)規則。在[4]中討論了蘊涵規則(implication rule)，規則的蘊涵強度在[0,¥]之間變化，其中蘊涵強度為1表示完全無(wú)關(guān)的規則，¥表示完備的規則，如果蘊涵強度大于1則表示更大的期望存在性。
另一個(gè)度量值——“收集強度”(collective strength)在[22]中被定義，他們設想使用“大于期望值”來(lái)發(fā)現有意義的關(guān)聯(lián)規則。項集的“收集強度”是[0,¥]之間的一個(gè)數值，其中0表示完備的否定相關(guān)性，而值¥表示完備的正相關(guān)性。詳細的討論可以在[10]中找到。
4.2用戶(hù)主觀(guān)層面：
上面的討論只是基于系統方面的考慮，但是一個(gè)規則的有用與否最終取決于用戶(hù)的感覺(jué)。只有用戶(hù)可以決定規則的有效性、可行性。所以我們應該將用戶(hù)的需求和系統更加緊密的結合起來(lái)。
可以采用一種基于約束(consraint-based)[21]的挖掘。具體約束的內容可以有：
1) 數據約束。用戶(hù)可以指定對哪些數據進(jìn)行挖掘，而不一定是全部的數據。
2) 指定挖掘的維和層次。用戶(hù)可以指定對數據哪些維以及這些維上的哪些層次進(jìn)行挖掘。
3) 規則約束?？梢灾付男╊?lèi)型的規則是我們所需要的。引入一個(gè)模板（template）的概念，用戶(hù)使用它來(lái)確定哪些規則是令人感興趣的而哪些則不然：如果一條規則匹配一個(gè)包含的模板（inclusive template），則是令人感興趣的，然而如果一條規則匹配一個(gè)限制的模板（rextrictive template），則被認為是缺乏興趣的。
其中有些條件可以和算法緊密的結合，從而即提高了效率，又使挖掘的目的更加的明確化了。其他的方法還有：
Kleinberg等人的工作是希望建立一套理論來(lái)判斷所得模式的價(jià)值，他們認為這個(gè)問(wèn)題僅能在微觀(guān)經(jīng)濟學(xué)框架里被解決，他們的模型提出了一個(gè)可以發(fā)展的方向。他們引入并研究了一個(gè)新的優(yōu)化問(wèn)題——分段(Segmentation)問(wèn)題，這個(gè)框架包含了一些標準的組合分類(lèi)問(wèn)題。這個(gè)模型根據基本的目標函數，對“被挖掘的數據”的價(jià)值提供一個(gè)特殊的算法的視角，顯示了從這方面導出的具體的優(yōu)化問(wèn)題的廣泛的應用領(lǐng)域。
在[5]中Korn等就利用猜測誤差(這里他們使用“均方根”來(lái)定義)來(lái)作為一些從給定的數據集所發(fā)現的規則的“好處”(goodness)的度量，他們所定義的比例規則就是如下的規則：
顧客大多數分別花費 1 : 2 : 5的錢(qián)在“面包”:“牛奶”:“奶油”上
通過(guò)確定未知的(等價(jià)的，被隱藏的，丟失的)值，比例規則可以用來(lái)作決策支持。如果數據點(diǎn)線(xiàn)性地相關(guān)的話(huà)，那么比例規則能達到更緊湊的描述，即關(guān)聯(lián)規則更好地描述了相關(guān)性。
5.結論與展望
本文討論了數據挖掘中產(chǎn)生關(guān)聯(lián)規則的方法以及它的應用，這方面一些研究成果已取得很大的成績(jì)，并已被集成在一些系統中，如IBM的Quest項目，Simon Farse大學(xué)的DBMiner等。具體的內容有經(jīng)典頻集算法，對頻集算法的優(yōu)化，擴展。然后討論了在OLAP下進(jìn)行數據挖掘的一些內容。接著(zhù)是對規則價(jià)值的一些評價(jià)方法。
對于關(guān)聯(lián)規則的發(fā)展，我們覺(jué)得可以在下面一些方向上進(jìn)行近一步的深入研究。在處理極大量的數據時(shí)，如何提高算法效率的問(wèn)題；對于挖掘迅速更新的數據的挖掘算法的進(jìn)一步研究；在挖掘的過(guò)程中，提供一種與用戶(hù)進(jìn)行交互的方法，將用戶(hù)的領(lǐng)域知識結合在其中；對于數值型字段在關(guān)聯(lián)規則中的處理問(wèn)題；生成結果的可視化方面等等。
參考文獻
1 R. Agrawal, T. Imielinski, and A. Swami. Mining association rules between sets of items in large databases. Proceedings of the ACM SIGMOD Conference on Management of data, pp. 207-216, 1993.
2 R. Agrawal, and J. Shafer. Parallel mining of association rules:Design,Implementation, and Experience. Technical Report FJ10004, IBM Almaden Research Center, San Jose, CA 95120, Jan. 1996.
3 S. Brin, R. Motwani, and C. Silverstein. Beyond market baskets:generlizing association rules to correlations. Proceedings of the ACM SIGMOD, 1996. pages 255-276.
4 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.
5 F. Korn, A. Labrinidis, Y. Kotidis, and C. Faloutsos. Ratio rules: A new paradigm for fast, quantifiable data mining.
6 J. Kleinberg, C. Papadimitriou, and P. Raghavan. Segmentation problems. Proceedings of the 30th Annual Symposium on Theory of Computing, ACM. 1998.
7 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.
8 H. Mannila, H. Toivonen, and A. Verkamo. Efficient algorithm for discovering association rules. AAAI Workshop on Knowledge Discovery in Databases, 1994, pp. 181-192.
9 R. Ng, L. V. S. Lakshmanan, J. Han, and A. Pang. Exploratory mining and pruning optimizations of constrained associations rules. Proceedings of ACM SIGMOD International Conference on Management of Data, pates 13-24, Seattle, Washington, June 1998.
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 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.
12 R. Srikant, and R. Agrawal. Mining generalized association rules. Proceedings of the 21st International Conference on Very Large Database, 1995, pp. 407-419.
13 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.
14 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.
15 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.
16 H. Toivonen. Sampling large databases for association rules. Proceedings of the 22nd International Conference on Very Large Database, Bombay, India, September 1996.
17 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.
18 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.
19 Edith Cohen,Mayur Datar,Shinji Fujiwara, Aristides Gionis,Piotr Indyk,Rajeev Motwani,Jeffrey D.Ullman,Cheng Yang.Finding Interesting Associations without Support Pruning.
20 Jiawei Han,Sonny H.S. Chee,Jenny Y.Chiang.Issues for On-Line Analytical Mining of Data Warehouses.
21 Information Discovery,Inc.OLAP and DataMining,Bridging the Gap.
22 C. C. Aggarwal, and P. S. Yu. A new framework for itemset generation. IBM Research Report,RC-21064.
Survey of Association Rule Generation
Cai Weijie Zhang Xiaohui Zhu Jianqiu Zhu Yangyong
(Computer Science Department, Fudan University, Shanghai, 200433)
Abstract This paper provides a survey of the study in association rule generation,brings forward a classification of association rule,reviews and analyses some typical algorithms,points out the weakness of the traidional measure method,concludes the measure method of the association rule’s value,views some future directions in association rule generation.
Key Words Data Mining, Association Rules, Large Itemset,OLAP
聯(lián)系客服
