|
1引言 關(guān)聯(lián)規(guī)則是發(fā)現(xiàn)交易數(shù)據(jù)庫(kù)中不同商品（項(xiàng)）之間的聯(lián)系，這些規(guī)則找出顧客購(gòu)買(mǎi)行為模式，如購(gòu)買(mǎi)了某一商品對(duì)購(gòu)買(mǎi)其他商品的影響。發(fā)現(xiàn)這樣的規(guī)則可以應(yīng)用于商品貨架設(shè)計(jì)、貨存安排以及根據(jù)購(gòu)買(mǎi)模式對(duì)用戶進(jìn)行分類。 Agrawal等于1993年[1]首先提出了挖掘顧客交易數(shù)據(jù)庫(kù)中項(xiàng)集間的關(guān)聯(lián)規(guī)則問(wèn)題，以后諸多的研究人員對(duì)關(guān)聯(lián)規(guī)則的挖掘問(wèn)題進(jìn)行了大量的研究。他們的工作包括對(duì)原有的算法進(jìn)行優(yōu)化，如引入隨機(jī)采樣、并行的思想等，以提高算法挖掘規(guī)則的效率；對(duì)關(guān)聯(lián)規(guī)則的應(yīng)用進(jìn)行推廣。 最近也有獨(dú)立于Agrawal的頻集方法的工作[18,19]，以避免頻集方法的一些缺陷，探索挖掘關(guān)聯(lián)規(guī)則的新方法。同時(shí)隨著OLAP技術(shù)的成熟和應(yīng)用，將OLAP和關(guān)聯(lián)規(guī)則結(jié)合[20,21]也成了一個(gè)重要的方向。也有一些工作[6]注重于對(duì)挖掘到的模式的價(jià)值進(jìn)行評(píng)估，他們提出的模型建議了一些值得考慮的研究方向。 本文第二部分是對(duì)關(guān)聯(lián)規(guī)則基本概念的介紹，提出了關(guān)聯(lián)規(guī)則的分類方法；第三部分是對(duì)挖掘算法的介紹，從經(jīng)典的apriori開(kāi)始，然后描述了對(duì)該算法的優(yōu)化拓展，接著講述脫離apriori算法的方法，最后是多層、多維的關(guān)聯(lián)規(guī)則挖掘；第四部分歸納出關(guān)聯(lián)規(guī)則價(jià)值衡量方法，主要從兩個(gè)方面進(jìn)行考慮：系統(tǒng)客觀層面和用戶主觀層面；最后展望了關(guān)聯(lián)規(guī)則挖掘的未來(lái)研究方向。 2關(guān)聯(lián)規(guī)則的基本概念 一個(gè)關(guān)聯(lián)規(guī)則是形如XÞY的蘊(yùn)涵式，這里XÌI, YÌI，并且XÇY=F。規(guī)則XÞY在交易數(shù)據(jù)庫(kù)D中的支持度（support）是交易集中包含X和Y的交易數(shù)與所有交易數(shù)之比，記為support(XÞY)，即 support(XÞY)=|{T:XÈYÍT，TÎD}|/|D| 規(guī)則XÞY在交易集中的可信度（confidence）是指包含X和Y的交易數(shù)與包含X的交易數(shù)之比，記為confidence(XÞY)，即 confidence(XÞY)=|{T: XÈYÍT，TÎD}|/|{T:XÍT，TÎD}| 給定一個(gè)交易集D，挖掘關(guān)聯(lián)規(guī)則問(wèn)題就是產(chǎn)生支持度和可信度分別大于用戶給定的最小支持度(minsupp)和最小可信度(minconf)的關(guān)聯(lián)規(guī)則。 2.2 關(guān)聯(lián)規(guī)則的種類 1. 基于規(guī)則中處理的變量的類別，關(guān)聯(lián)規(guī)則可以分為布爾型和數(shù)值型。 布爾型關(guān)聯(lián)規(guī)則處理的值都是離散的、種類化的，它顯示了這些變量之間的關(guān)系；而數(shù)值型關(guān)聯(lián)規(guī)則可以和多維關(guān)聯(lián)或多層關(guān)聯(lián)規(guī)則結(jié)合起來(lái)，對(duì)數(shù)值型字段進(jìn)行處理，將其進(jìn)行動(dòng)態(tài)的分割，或者直接對(duì)原始的數(shù)據(jù)進(jìn)行處理，當(dāng)然數(shù)值型關(guān)聯(lián)規(guī)則中也可以包含種類變量。 例如：性別=“女”=>職業(yè)=“秘書(shū)” ，是布爾型關(guān)聯(lián)規(guī)則；性別=“女”=>avg（收入）=2300，涉及的收入是數(shù)值類型，所以是一個(gè)數(shù)值型關(guān)聯(lián)規(guī)則。 2. 基于規(guī)則中數(shù)據(jù)的抽象層次，可以分為單層關(guān)聯(lián)規(guī)則和多層關(guān)聯(lián)規(guī)則。 在單層的關(guān)聯(lián)規(guī)則中，所有的變量都沒(méi)有考慮到現(xiàn)實(shí)的數(shù)據(jù)是具有多個(gè)不同的層次的；而在多層的關(guān)聯(lián)規(guī)則中，對(duì)數(shù)據(jù)的多層性已經(jīng)進(jìn)行了充分的考慮。 例如：IBM臺(tái)式機(jī)=>Sony打印機(jī)，是一個(gè)細(xì)節(jié)數(shù)據(jù)上的單層關(guān)聯(lián)規(guī)則；臺(tái)式機(jī)=>Sony打印機(jī)，是一個(gè)較高層次和細(xì)節(jié)層次之間的多層關(guān)聯(lián)規(guī)則。 3. 基于規(guī)則中涉及到的數(shù)據(jù)的維數(shù)，關(guān)聯(lián)規(guī)則可以分為單維的和多維的。 在單維的關(guān)聯(lián)規(guī)則中，我們只涉及到數(shù)據(jù)的一個(gè)維，如用戶購(gòu)買(mǎi)的物品；而在多維的關(guān)聯(lián)規(guī)則中，要處理的數(shù)據(jù)將會(huì)涉及多個(gè)維。換成另一句話，單維關(guān)聯(lián)規(guī)則是處理單個(gè)屬性中的一些關(guān)系；多維關(guān)聯(lián)規(guī)則是處理各個(gè)屬性之間的某些關(guān)系。 例如：啤酒=>尿布，這條規(guī)則只涉及到用戶的購(gòu)買(mǎi)的物品；性別=“女”=>職業(yè)=“秘書(shū)”，這條規(guī)則就涉及到兩個(gè)字段的信息，是兩個(gè)維上的一條關(guān)聯(lián)規(guī)則。
給出了關(guān)聯(lián)規(guī)則的分類之后，在下面的分析過(guò)程中，我們就可以考慮某個(gè)具體的方法適用于哪一類規(guī)則的挖掘，某類規(guī)則又可以用哪些不同的方法進(jìn)行處理。 3.關(guān)聯(lián)規(guī)則挖掘的算法 3.1.1核心算法 1) 找到所有支持度大于最小支持度的項(xiàng)集（Itemset），這些項(xiàng)集稱為頻集（Frequent Itemset)。 2) 使用第1步找到的頻集產(chǎn)生期望的規(guī)則。 這里的第2步相對(duì)簡(jiǎn)單一點(diǎn)。如給定了一個(gè)頻集Y=I1I2...Ik，k³2，Ij∈I，產(chǎn)生只包含集合{I1，I2，...，Ik}中的項(xiàng)的所有規(guī)則(最多k條)，其中每一條規(guī)則的右部只有一項(xiàng)，(即形如[Y-Ii]ÞIi，"1£i£k)，這里采用的是[4]中規(guī)則的定義。一旦這些規(guī)則被生成，那么只有那些大于用戶給定的最小可信度的規(guī)則才被留下來(lái)。對(duì)于規(guī)則右部含兩個(gè)以上項(xiàng)的規(guī)則，在其以后的工作中進(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-項(xiàng)集L1，然后是頻繁2-項(xiàng)集L2，直到有某個(gè)r值使得Lr為空，這時(shí)算法停止。這里在第k次循環(huán)中，過(guò)程先產(chǎn)生候選k-項(xiàng)集的集合Ck，Ck中的每一個(gè)項(xiàng)集是對(duì)兩個(gè)只有一個(gè)項(xiàng)不同的屬于Lk-1的頻集做一個(gè)(k-2)-連接來(lái)產(chǎn)生的。Ck中的項(xiàng)集是用來(lái)產(chǎn)生頻集的候選集，最后的頻集Lk必須是Ck的一個(gè)子集。Ck中的每個(gè)元素需在交易數(shù)據(jù)庫(kù)中進(jìn)行驗(yàn)證來(lái)決定其是否加入Lk，這里的驗(yàn)證過(guò)程是算法性能的一個(gè)瓶頸。這個(gè)方法要求多次掃描可能很大的交易數(shù)據(jù)庫(kù)，即如果頻集最多包含10個(gè)項(xiàng)，那么就需要掃描交易數(shù)據(jù)庫(kù)10遍，這需要很大的I/O負(fù)載。 在論文[6]中，Agrawal等引入了修剪技術(shù)（Pruning）來(lái)減小候選集Ck的大小，由此可以顯著地改進(jìn)生成所有頻集算法的性能。算法中引入的修剪策略基于這樣一個(gè)性質(zhì)：一個(gè)項(xiàng)集是頻集當(dāng)且僅當(dāng)它的所有子集都是頻集。那么，如果Ck中某個(gè)候選項(xiàng)集有一個(gè)(k-1)-子集不屬于Lk-1，則這個(gè)項(xiàng)集可以被修剪掉不再被考慮，這個(gè)修剪過(guò)程可以降低計(jì)算所有的候選集的支持度的代價(jià)。文[6]中，還引入雜湊樹(shù)（Hash Tree）方法來(lái)有效地計(jì)算每個(gè)項(xiàng)集的支持度。 3.1.2頻集算法的幾種優(yōu)化方法 1. 基于劃分的方法。Savasere等[14]設(shè)計(jì)了一個(gè)基于劃分(partition)的算法，這個(gè)算法先把數(shù)據(jù)庫(kù)從邏輯上分成幾個(gè)互不相交的塊，每次單獨(dú)考慮一個(gè)分塊并對(duì)它生成所有的頻集，然后把產(chǎn)生的頻集合并，用來(lái)生成所有可能的頻集，最后計(jì)算這些項(xiàng)集的支持度。這里分塊的大小選擇要使得每個(gè)分塊可以被放入主存，每個(gè)階段只需被掃描一次。而算法的正確性是由每一個(gè)可能的頻集至少在某一個(gè)分塊中是頻集保證的。上面所討論的算法是可以高度并行的，可以把每一分塊分別分配給某一個(gè)處理器生成頻集。產(chǎn)生頻集的每一個(gè)循環(huán)結(jié)束后，處理器之間進(jìn)行通信來(lái)產(chǎn)生全局的候選k-項(xiàng)集。通常這里的通信過(guò)程是算法執(zhí)行時(shí)間的主要瓶頸；而另一方面，每個(gè)獨(dú)立的處理器生成頻集的時(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í)驗(yàn)我們可以發(fā)現(xiàn)尋找頻集主要的計(jì)算是在生成頻繁2-項(xiàng)集Lk上，Park等就是利用了這個(gè)性質(zhì)引入雜湊技術(shù)來(lái)改進(jìn)產(chǎn)生頻繁2-項(xiàng)集的方法。 3. 基于采樣的方法?；谇耙槐閽呙璧玫降男畔?，對(duì)此仔細(xì)地作組合分析，可以得到一個(gè)改進(jìn)的算法，Mannila等[8]先考慮了這一點(diǎn)，他們認(rèn)為采樣是發(fā)現(xiàn)規(guī)則的一個(gè)有效途徑。隨后又由Toivonen[16]進(jìn)一步發(fā)展了這個(gè)思想，先使用從數(shù)據(jù)庫(kù)中抽取出來(lái)的采樣得到一些在整個(gè)數(shù)據(jù)庫(kù)中可能成立的規(guī)則，然后對(duì)數(shù)據(jù)庫(kù)的剩余部分驗(yàn)證這個(gè)結(jié)果。Toivonen的算法相當(dāng)簡(jiǎn)單并顯著地減少了I/O代價(jià)，但是一個(gè)很大的缺點(diǎn)就是產(chǎn)生的結(jié)果不精確，即存在所謂的數(shù)據(jù)扭曲(data skew)。分布在同一頁(yè)面上的數(shù)據(jù)時(shí)常是高度相關(guān)的，可能不能表示整個(gè)數(shù)據(jù)庫(kù)中模式的分布，由此而導(dǎo)致的是采樣5%的交易數(shù)據(jù)所花費(fèi)的代價(jià)可能同掃描一遍數(shù)據(jù)庫(kù)相近。Lin和Dunham在[7]中討論了反扭曲(Anti-skew)算法來(lái)挖掘關(guān)聯(lián)規(guī)則，在那里他們引入的技術(shù)使得掃描數(shù)據(jù)庫(kù)的次數(shù)少于2次，算法使用了一個(gè)采樣處理來(lái)收集有關(guān)數(shù)據(jù)的次數(shù)來(lái)減少掃描遍數(shù)。 Brin等[4]提出的算法使用比傳統(tǒng)算法少的掃描遍數(shù)來(lái)發(fā)現(xiàn)頻集，同時(shí)比基于采樣的方法使用更少的候選集，這些改進(jìn)了算法在低層的效率。具體的考慮是，在計(jì)算k-項(xiàng)集時(shí)，一旦我們認(rèn)為某個(gè)(k+1)-項(xiàng)集可能是頻集時(shí)，就并行地計(jì)算這個(gè)(k+1)-項(xiàng)集的支持度，算法需要的總的掃描次數(shù)通常少于最大的頻集的項(xiàng)數(shù)。這里他們也使用了雜湊技術(shù)，并提出產(chǎn)生“相關(guān)規(guī)則”（Correlation Rules）的一個(gè)新方法，這是基于他們的[3]工作基礎(chǔ)上的。 4. 減少交易的個(gè)數(shù)。減少用于未來(lái)掃描的事務(wù)集的大小。一個(gè)基本的原理就是當(dāng)一個(gè)事務(wù)不包含長(zhǎng)度為k的大項(xiàng)集，則必然不包含長(zhǎng)度為k+1的大項(xiàng)集。從而我們就可以將這些事務(wù)移去，這樣在下一遍的掃描中就可以要進(jìn)行掃描的事務(wù)集的個(gè)數(shù)。這個(gè)就是AprioriTid的基本思想
3.2其他的頻集挖掘方法 1) 可能產(chǎn)生大量的候選集。當(dāng)長(zhǎng)度為1的頻集有10000個(gè)的時(shí)候，長(zhǎng)度為2的候選集個(gè)數(shù)將會(huì)超過(guò)10M。還有就是如果要生成一個(gè)很長(zhǎng)的規(guī)則的時(shí)候，要產(chǎn)生的中間元素也是巨大量的。 2) 無(wú)法對(duì)稀有信息進(jìn)行分析。由于頻集使用了參數(shù)minsup，所以就無(wú)法對(duì)小于minsup的事件進(jìn)行分析；而如果將minsup設(shè)成一個(gè)很低的值，那么算法的效率就成了一個(gè)很難處理的問(wèn)題。 下面將介紹兩種方法，分別用于解決以上兩個(gè)問(wèn)題。 在[18]中提到了解決問(wèn)題1的一種方法。采用了一種FP-growth的方法。他們采用了分而治之的策略：在經(jīng)過(guò)了第一次的掃描之后，把數(shù)據(jù)庫(kù)中的頻集壓縮進(jìn)一棵頻繁模式樹(shù)（FP-tree），同時(shí)依然保留其中的關(guān)聯(lián)信息。隨后我們?cè)賹P-tree分化成一些條件庫(kù)，每個(gè)庫(kù)和一個(gè)長(zhǎng)度為1的頻集相關(guān)。然后再對(duì)這些條件庫(kù)分別進(jìn)行挖掘。當(dāng)原始數(shù)據(jù)量很大的時(shí)候，也可以結(jié)合劃分的方法,使得一個(gè)FP-tree可以放入主存中。實(shí)驗(yàn)表明，F(xiàn)P-growth對(duì)不同長(zhǎng)度的規(guī)則都有很好的適應(yīng)性，同時(shí)在效率上較之a(chǎn)priori算法有巨大的提高。 第二個(gè)問(wèn)題是基于這個(gè)的一個(gè)想法：apriori算法得出的關(guān)系都是頻繁出現(xiàn)的，但是在實(shí)際的應(yīng)用中，我們可能需要尋找一些高度相關(guān)的元素，即使這些元素不是頻繁出現(xiàn)的。在apriori算法中，起決定作用的是支持度，而我們現(xiàn)在將把可信度放在第一位，挖掘一些具有非常高可信度的規(guī)則。在[19]中介紹了對(duì)于這個(gè)問(wèn)題的一個(gè)解決方法。整個(gè)算法基本上分成三個(gè)步驟：計(jì)算特征、生成候選集、過(guò)濾候選集。在三個(gè)步驟中，關(guān)鍵的地方就是在計(jì)算特征時(shí)Hash方法的使用。在考慮方法的時(shí)候，有幾個(gè)衡量好壞的指數(shù)：時(shí)空效率、錯(cuò)誤率和遺漏率?；镜姆椒ㄓ袃深悾篗in_Hashing(MH)和Locality_Sensitive_Hashing(LSH)。Min_Hashing的基本想法是：將一條記錄中的頭k個(gè)為1的字段的位置作為一個(gè)Hash函數(shù)。Locality_Sentitive_Hashing的基本想法是：將整個(gè)數(shù)據(jù)庫(kù)用一種基于概率的方法進(jìn)行分類，使得相似的列在一起的可能性更大，不相似的列在一起的可能性較小。我們?cè)賹?duì)這兩個(gè)方法比較一下。MH的遺漏率為零，錯(cuò)誤率可以由k嚴(yán)格控制，但是時(shí)空效率相對(duì)的較差。LSH的遺漏率和錯(cuò)誤率是無(wú)法同時(shí)降低的，但是它的時(shí)空效率卻相對(duì)的好很多。所以應(yīng)該視具體的情況而定。最后的實(shí)驗(yàn)數(shù)據(jù)也說(shuō)明這種方法的確能產(chǎn)生一些有用的規(guī)則。 3.3多層和多維關(guān)聯(lián)規(guī)則的挖掘 首先一個(gè)有效的數(shù)據(jù)挖掘方法應(yīng)該可以進(jìn)行探索性的數(shù)據(jù)分析。用戶往往希望能在數(shù)據(jù)庫(kù)中穿行，選擇各種相關(guān)的數(shù)據(jù)，在不同的細(xì)節(jié)層次上進(jìn)行分析，以各種不同的形式呈現(xiàn)知識(shí)?；贠LAP的挖掘就可以提供在不同數(shù)據(jù)集、不同的細(xì)節(jié)上的挖掘，可以進(jìn)行切片、切塊、展開(kāi)、過(guò)濾等各種對(duì)規(guī)則的操作。然后再加上一些可視化的工具，就能大大的提高數(shù)據(jù)挖掘的靈活性和能力。接著，我們來(lái)看一下多層和多維關(guān)聯(lián)規(guī)則的定義。 多層關(guān)聯(lián)規(guī)則： 對(duì)于很多的應(yīng)用來(lái)說(shuō)，由于數(shù)據(jù)分布的分散性，所以很難在數(shù)據(jù)最細(xì)節(jié)的層次上發(fā)現(xiàn)一些強(qiáng)關(guān)聯(lián)規(guī)則。當(dāng)我們引入概念層次后，就可以在較高的層次上進(jìn)行挖掘。雖然較高層次上得出的規(guī)則可能是更普通的信息，但是對(duì)于一個(gè)用戶來(lái)說(shuō)是普通的信息，對(duì)于另一個(gè)用戶卻未必如此。所以數(shù)據(jù)挖掘應(yīng)該提供這樣一種在多個(gè)層次上進(jìn)行挖掘的功能。 多層關(guān)聯(lián)規(guī)則的分類：根據(jù)規(guī)則中涉及到的層次，多層關(guān)聯(lián)規(guī)則可以分為同層關(guān)聯(lián)規(guī)則和層間關(guān)聯(lián)規(guī)則。 多層關(guān)聯(lián)規(guī)則的挖掘基本上可以沿用“支持度-可信度”的框架。不過(guò)，在支持度設(shè)置的問(wèn)題上有一些要考慮的東西。 同層關(guān)聯(lián)規(guī)則可以采用兩種支持度策略： 1) 統(tǒng)一的最小支持度。對(duì)于不同的層次，都使用同一個(gè)最小支持度。這樣對(duì)于用戶和算法實(shí)現(xiàn)來(lái)說(shuō)都比較的容易，但是弊端也是顯然的。 2) 遞減的最小支持度。每個(gè)層次都有不同的最小支持度，較低層次的最小支持度相對(duì)較小。同時(shí)還可以利用上層挖掘得到的信息進(jìn)行一些過(guò)濾的工作。 層間關(guān)聯(lián)規(guī)則考慮最小支持度的時(shí)候，應(yīng)該根據(jù)較低層次的最小支持度來(lái)定。 多維關(guān)聯(lián)規(guī)則： 以上我們研究的基本上都是同一個(gè)字段的值之間的關(guān)系，比如用戶購(gòu)買(mǎi)的物品。用多維數(shù)據(jù)庫(kù)的語(yǔ)言就是單維或者叫維內(nèi)的關(guān)聯(lián)規(guī)則，這些規(guī)則一般都是在交易數(shù)據(jù)庫(kù)中挖掘的。但是對(duì)于多維數(shù)據(jù)庫(kù)而言，還有一類多維的關(guān)聯(lián)規(guī)則。例如： 年齡（X，“20...30”）Ù職業(yè)（X,“學(xué)生”）==> 購(gòu)買(mǎi)(X，“筆記本電腦”) 在這里我們就涉及到三個(gè)維上的數(shù)據(jù)：年齡、職業(yè)、購(gòu)買(mǎi)。 根據(jù)是否允許同一個(gè)維重復(fù)出現(xiàn)，可以又細(xì)分為維間的關(guān)聯(lián)規(guī)則（不允許維重復(fù)出現(xiàn)）和混合維關(guān)聯(lián)規(guī)則（允許維在規(guī)則的左右同時(shí)出現(xiàn)）。 年齡（X，“20...30”）Ù購(gòu)買(mǎi)(X，“筆記本電腦”) ==> 購(gòu)買(mǎi)(X，“打印機(jī)”) 這個(gè)規(guī)則就是混合維關(guān)聯(lián)規(guī)則。 在挖掘維間關(guān)聯(lián)規(guī)則和混合維關(guān)聯(lián)規(guī)則的時(shí)候，還要考慮不同的字段種類：種類型和數(shù)值型。 對(duì)于種類型的字段，原先的算法都可以處理。而對(duì)于數(shù)值型的字段，需要進(jìn)行一定的處理之后才可以進(jìn)行。處理數(shù)值型字段的方法基本上有以下幾種： 1) 數(shù)值字段被分成一些預(yù)定義的層次結(jié)構(gòu)。這些區(qū)間都是由用戶預(yù)先定義的。得出的規(guī)則也叫做靜態(tài)數(shù)量關(guān)聯(lián)規(guī)則。 2) 數(shù)值字段根據(jù)數(shù)據(jù)的分布分成了一些布爾字段。每個(gè)布爾字段都表示一個(gè)數(shù)值字段的區(qū)間，落在其中則為1，反之為0。這種分法是動(dòng)態(tài)的。得出的規(guī)則叫布爾數(shù)量關(guān)聯(lián)規(guī)則。 3) 數(shù)值字段被分成一些能體現(xiàn)它含義的區(qū)間。它考慮了數(shù)據(jù)之間的距離的因素。得出的規(guī)則叫基于距離的關(guān)聯(lián)規(guī)則。 4) 直接用數(shù)值字段中的原始數(shù)據(jù)進(jìn)行分析。使用一些統(tǒng)計(jì)的方法對(duì)數(shù)值字段的值進(jìn)行分析，并且結(jié)合多層關(guān)聯(lián)規(guī)則的概念，在多個(gè)層次之間進(jìn)行比較從而得出一些有用的規(guī)則。得出的規(guī)則叫多層數(shù)量關(guān)聯(lián)規(guī)則。 在OLAP中挖掘多層、多維的關(guān)聯(lián)規(guī)則是一個(gè)很自然的過(guò)程。因?yàn)镺LAP本身的基礎(chǔ)就是一個(gè)多層多維分析的工具，只是在沒(méi)有使用數(shù)據(jù)挖掘技術(shù)之前，OLAP只能做一些簡(jiǎn)單的統(tǒng)計(jì)，而不能發(fā)現(xiàn)其中一些深層次的有關(guān)系的規(guī)則。當(dāng)我們將OLAP和DataMining技術(shù)結(jié)合在一起就形成了一個(gè)新的體系OLAM（On-Line Analytical Mining）[20]。 4關(guān)聯(lián)規(guī)則價(jià)值衡量的方法 4.1系統(tǒng)客觀層面： 假設(shè)一個(gè)提供早餐的零售商調(diào)查了4000名學(xué)生在早晨進(jìn)行什么運(yùn)動(dòng)，得到的結(jié)果是2200名學(xué)生打籃球，2750名學(xué)生晨跑，1800名學(xué)生打籃球、晨跑。那么如果設(shè)minsup為40%，minconf為60%，我們可以得到如下的關(guān)聯(lián)規(guī)則： 打籃球Þ晨跑 （1） 這條規(guī)則其實(shí)是錯(cuò)誤的，因?yàn)槌颗艿膶W(xué)生的比例是68%，甚至大于60%。然而打籃球和晨跑可能是否定關(guān)聯(lián)的，即當(dāng)我們考慮如下的關(guān)聯(lián)時(shí)： 打籃球Þ（不）晨跑 （2） 雖然這條規(guī)則的支持度和可信度都比那條蘊(yùn)涵正向關(guān)聯(lián)的規(guī)則（1）低，但是它更精確。 然而，如果我們把支持度和可信度設(shè)得足夠低，那么我們將得到兩條矛盾的規(guī)則。但另一方面，如果我們把那些參數(shù)設(shè)得足夠高，我們只能得到不精確的規(guī)則?？傊?，沒(méi)有一對(duì)支持度和可信度的組合可以產(chǎn)生完全正確的關(guān)聯(lián)。 于是人們引入了興趣度，用來(lái)修剪無(wú)趣的規(guī)則，即避免生成“錯(cuò)覺(jué)”的關(guān)聯(lián)規(guī)則。一般一條規(guī)則的興趣度是在基于統(tǒng)計(jì)獨(dú)立性假設(shè)下真正的強(qiáng)度與期望的強(qiáng)度之比，然而在許多應(yīng)用中已發(fā)現(xiàn)，只要人們?nèi)园阎С侄茸鳛樽畛醯捻?xiàng)集產(chǎn)生的主要決定因素，那么要么把支持度設(shè)得足夠低以使得不丟失任何有意義的規(guī)則，或者冒丟失一些重要規(guī)則的風(fēng)險(xiǎn)；對(duì)前一種情形計(jì)算效率是個(gè)問(wèn)題，而后一種情形則有可能丟失從用戶觀點(diǎn)來(lái)看是有意義的規(guī)則的問(wèn)題。 在[12]中作者給出了感興趣的規(guī)則的定義（R-interesting），在[13]中他們又對(duì)此作了改進(jìn)。在[10]中把事件依賴性的統(tǒng)計(jì)定義擴(kuò)展到興趣度的定義上來(lái)；[15]定義了否定關(guān)聯(lián)規(guī)則的興趣度。 除了把興趣度作為修剪無(wú)價(jià)值規(guī)則的工具，現(xiàn)在已有許多其他的工作來(lái)重新認(rèn)識(shí)項(xiàng)集，如Brin等[3]考慮的相關(guān)規(guī)則。在[4]中討論了蘊(yùn)涵規(guī)則(implication rule)，規(guī)則的蘊(yùn)涵強(qiáng)度在[0,¥]之間變化，其中蘊(yùn)涵強(qiáng)度為1表示完全無(wú)關(guān)的規(guī)則，¥表示完備的規(guī)則，如果蘊(yùn)涵強(qiáng)度大于1則表示更大的期望存在性。 另一個(gè)度量值——“收集強(qiáng)度”(collective strength)在[22]中被定義，他們?cè)O(shè)想使用“大于期望值”來(lái)發(fā)現(xiàn)有意義的關(guān)聯(lián)規(guī)則。項(xiàng)集的“收集強(qiáng)度”是[0,¥]之間的一個(gè)數(shù)值，其中0表示完備的否定相關(guān)性，而值¥表示完備的正相關(guān)性。詳細(xì)的討論可以在[10]中找到。 4.2用戶主觀層面： 可以采用一種基于約束(consraint-based)[21]的挖掘。具體約束的內(nèi)容可以有： 1) 數(shù)據(jù)約束。用戶可以指定對(duì)哪些數(shù)據(jù)進(jìn)行挖掘，而不一定是全部的數(shù)據(jù)。 2) 指定挖掘的維和層次。用戶可以指定對(duì)數(shù)據(jù)哪些維以及這些維上的哪些層次進(jìn)行挖掘。 3) 規(guī)則約束?？梢灾付男╊愋偷囊?guī)則是我們所需要的。引入一個(gè)模板（template）的概念，用戶使用它來(lái)確定哪些規(guī)則是令人感興趣的而哪些則不然：如果一條規(guī)則匹配一個(gè)包含的模板（inclusive template），則是令人感興趣的，然而如果一條規(guī)則匹配一個(gè)限制的模板（rextrictive template），則被認(rèn)為是缺乏興趣的。 其中有些條件可以和算法緊密的結(jié)合，從而即提高了效率，又使挖掘的目的更加的明確化了。其他的方法還有： Kleinberg等人的工作是希望建立一套理論來(lái)判斷所得模式的價(jià)值，他們認(rèn)為這個(gè)問(wèn)題僅能在微觀經(jīng)濟(jì)學(xué)框架里被解決，他們的模型提出了一個(gè)可以發(fā)展的方向。他們引入并研究了一個(gè)新的優(yōu)化問(wèn)題——分段(Segmentation)問(wèn)題，這個(gè)框架包含了一些標(biāo)準(zhǔn)的組合分類問(wèn)題。這個(gè)模型根據(jù)基本的目標(biāo)函數(shù)，對(duì)“被挖掘的數(shù)據(jù)”的價(jià)值提供一個(gè)特殊的算法的視角，顯示了從這方面導(dǎo)出的具體的優(yōu)化問(wèn)題的廣泛的應(yīng)用領(lǐng)域。 在[5]中Korn等就利用猜測(cè)誤差(這里他們使用“均方根”來(lái)定義)來(lái)作為一些從給定的數(shù)據(jù)集所發(fā)現(xiàn)的規(guī)則的“好處”(goodness)的度量，他們所定義的比例規(guī)則就是如下的規(guī)則： 顧客大多數(shù)分別花費(fèi) 1 : 2 : 5的錢(qián)在“面包”:“牛奶”:“奶油”上 通過(guò)確定未知的(等價(jià)的，被隱藏的，丟失的)值，比例規(guī)則可以用來(lái)作決策支持。如果數(shù)據(jù)點(diǎn)線性地相關(guān)的話，那么比例規(guī)則能達(dá)到更緊湊的描述，即關(guān)聯(lián)規(guī)則更好地描述了相關(guān)性。 5.結(jié)論與展望 對(duì)于關(guān)聯(lián)規(guī)則的發(fā)展，我們覺(jué)得可以在下面一些方向上進(jìn)行近一步的深入研究。在處理極大量的數(shù)據(jù)時(shí)，如何提高算法效率的問(wèn)題；對(duì)于挖掘迅速更新的數(shù)據(jù)的挖掘算法的進(jìn)一步研究；在挖掘的過(guò)程中，提供一種與用戶進(jìn)行交互的方法，將用戶的領(lǐng)域知識(shí)結(jié)合在其中；對(duì)于數(shù)值型字段在關(guān)聯(lián)規(guī)則中的處理問(wèn)題；生成結(jié)果的可視化方面等等。 參考文獻(xiàn) 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 (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 |
|
|
