摘  要  本文介紹了關(guān)聯(lián)規(guī)則的基本概念和分類方法，列舉了一些關(guān)聯(lián)規(guī)則挖掘算法并簡(jiǎn)要分析了典型算法，展望了關(guān)聯(lián)規(guī)則挖掘的未來研究方向。

1 引言



關(guān)聯(lián)規(guī)則挖掘發(fā)現(xiàn)大量數(shù)據(jù)中項(xiàng)集之間有趣的關(guān)聯(lián)或相關(guān)聯(lián)系。它在數(shù)據(jù)挖掘中是一個(gè)重要的課題，最近幾年已被業(yè)界所廣泛研究。

關(guān)聯(lián)規(guī)則挖掘的一個(gè)典型例子是購物籃分析。關(guān)聯(lián)規(guī)則研究有助于發(fā)現(xiàn)交易數(shù)據(jù)庫中不同商品（項(xiàng)）之間的聯(lián)系，找出顧客購買行為模式，如購買了某一商品對(duì)購買其他商品的影響。分析結(jié)果可以應(yīng)用于商品貨架布局、貨存安排以及根據(jù)購買模式對(duì)用戶進(jìn)行分類。

Agrawal等于1993年首先提出了挖掘顧客交易數(shù)據(jù)庫中項(xiàng)集間的關(guān)聯(lián)規(guī)則問題[AIS93b]，以后諸多的研究人員對(duì)關(guān)聯(lián)規(guī)則的挖掘問題進(jìn)行了大量的研究。他們的工作包括對(duì)原有的算法進(jìn)行優(yōu)化，如引入隨機(jī)采樣、并行的思想等，以提高算法挖掘規(guī)則的效率；對(duì)關(guān)聯(lián)規(guī)則的應(yīng)用進(jìn)行推廣。

最近也有獨(dú)立于Agrawal的頻集方法的工作[HPY00]，以避免頻集方法的一些缺陷，探索挖掘關(guān)聯(lián)規(guī)則的新方法。也有一些工作[KPR98]注重于對(duì)挖掘到的模式的價(jià)值進(jìn)行評(píng)估，他們提出的模型建議了一些值得考慮的研究方向。





2 基本概念

         

設(shè)I={i1,i2,..,im}是項(xiàng)集，其中ik(k=1,2,…,m)可以是購物籃中的物品，也可以是保險(xiǎn)公司的顧客。設(shè)任務(wù)相關(guān)的數(shù)據(jù)D是事務(wù)集，其中每個(gè)事務(wù)T是項(xiàng)集，使得TÍI。設(shè)A是一個(gè)項(xiàng)集，且AÍT。

       關(guān)聯(lián)規(guī)則是如下形式的邏輯蘊(yùn)涵：A Þ B，AÌI, AÌI，且A∩B=F。關(guān)聯(lián)規(guī)則具有如下兩個(gè)重要的屬性：

支持度: P(A∪B)，即A和B這兩個(gè)項(xiàng)集在事務(wù)集D中同時(shí)出現(xiàn)的概率。

置信度: P(B｜A)，即在出現(xiàn)項(xiàng)集A的事務(wù)集D中，項(xiàng)集B也同時(shí)出現(xiàn)的概率。

同時(shí)滿足最小支持度閾值和最小置信度閾值的規(guī)則稱為強(qiáng)規(guī)則。給定一個(gè)事務(wù)集D，挖掘關(guān)聯(lián)規(guī)則問題就是產(chǎn)生支持度和可信度分別大于用戶給定的最小支持度和最小可信度的關(guān)聯(lián)規(guī)則，也就是產(chǎn)生強(qiáng)規(guī)則的問題。



3 關(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é)合起來，對(duì)數(shù)值型字段進(jìn)行處理，將其進(jìn)行動(dòng)態(tài)的分割，或者直接對(duì)原始的數(shù)據(jù)進(jìn)行處理，當(dāng)然數(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ī)則中，所有的變量都沒有考慮到現(xiàn)實(shí)的數(shù)據(jù)是具有多個(gè)不同的層次的。

在多層關(guān)聯(lián)規(guī)則中，對(duì)數(shù)據(jù)的多層性已經(jīng)進(jìn)行了充分的考慮。



3) 基于規(guī)則中涉及到的數(shù)據(jù)的維數(shù)，關(guān)聯(lián)規(guī)則可以分為單維的和多維的。

在單維關(guān)聯(lián)規(guī)則中，我們只涉及到數(shù)據(jù)的一個(gè)維，如用戶購買的物品

在多維關(guān)聯(lián)規(guī)則中，要處理的數(shù)據(jù)將會(huì)涉及多個(gè)維。





4 算法綜述

4.1 經(jīng)典的頻集算法



Agrawal等于1994年提出了一個(gè)挖掘顧客交易數(shù)據(jù)庫中項(xiàng)集間的關(guān)聯(lián)規(guī)則的重要方法 [AS94a, AS94b]，其核心是基于兩階段頻集思想的遞推算法。該關(guān)聯(lián)規(guī)則在分類上屬于單維、單層、布爾關(guān)聯(lián)規(guī)則。

所有支持度大于最小支持度的項(xiàng)集稱為頻繁項(xiàng)集，簡(jiǎn)稱頻集。



4.1.1 算法的基本思想

首先找出所有的頻集，這些項(xiàng)集出現(xiàn)的頻繁性至少和預(yù)定義的最小支持度一樣。然后由頻集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則，這些規(guī)則必須滿足最小支持度和最小可信度。

  挖掘關(guān)聯(lián)規(guī)則的總體性能由第一步?jīng)Q定，第二步相對(duì)容易實(shí)現(xiàn)。



4.1.2 Apriori核心算法分析

為了生成所有頻集，使用了遞推的方法。其核心思想簡(jiǎ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)中，過程先產(chǎn)生候選k-項(xiàng)集的集合Ck，Ck中的每一個(gè)項(xiàng)集是對(duì)兩個(gè)只有一個(gè)項(xiàng)不同的屬于Lk-1的頻集做一個(gè)(k-2)-連接來產(chǎn)生的。Ck中的項(xiàng)集是用來產(chǎn)生頻集的候選集，最后的頻集Lk必須是Ck的一個(gè)子集。Ck中的每個(gè)元素需在交易數(shù)據(jù)庫中進(jìn)行驗(yàn)證來決定其是否加入Lk，這里的驗(yàn)證過程是算法性能的一個(gè)瓶頸。這個(gè)方法要求多次掃描可能很大的交易數(shù)據(jù)庫，即如果頻集最多包含10個(gè)項(xiàng)，那么就需要掃描交易數(shù)據(jù)庫10遍，這需要很大的I/O負(fù)載。

可能產(chǎn)生大量的候選集,以及可能需要重復(fù)掃描數(shù)據(jù)庫，是Apriori算法的兩大缺點(diǎn)。



4.1.3 算法的優(yōu)化

為了提高算法的效率，Mannila等引入了修剪技術(shù)來減小候選集Ck的大小[MTV94]，由此可以顯著地改進(jìn)生成所有頻集算法的性能。算法中引入的修剪策略基于這樣一個(gè)性質(zhì)：一個(gè)項(xiàng)集是頻集當(dāng)且僅當(dāng)它的所有子集都是頻集。那么，如果Ck中某個(gè)候選項(xiàng)集有一個(gè)(k-1)-子集不屬于Lk-1，則這個(gè)項(xiàng)集可以被修剪掉不再被考慮，這個(gè)修剪過程可以降低計(jì)算所有的候選集的支持度的代價(jià)。





4.2 改進(jìn)的頻集算法



4.2.1散列

該算法由Park等在1995年提出[PCY95b]。通過實(shí)驗(yàn)發(fā)現(xiàn)尋找頻繁項(xiàng)集的主要計(jì)算是在生成頻繁2項(xiàng)集L2上，Park就是利用這個(gè)性質(zhì)引入散列技術(shù)來改進(jìn)產(chǎn)生頻繁2項(xiàng)集的方法。

    其基本思想是：當(dāng)掃描數(shù)據(jù)庫中每個(gè)事務(wù)，由C1中的候選1項(xiàng)集產(chǎn)生頻繁1項(xiàng)集L1時(shí)，對(duì)每個(gè)事務(wù)產(chǎn)生所有的2項(xiàng)集，將它們散列到散列表結(jié)構(gòu)的不同桶中，并增加對(duì)應(yīng)的桶計(jì)數(shù)，在散列表中對(duì)應(yīng)的桶計(jì)數(shù)低于支持度閾值的2項(xiàng)集不可能是頻繁2項(xiàng)集，可從候選2項(xiàng)集中刪除，這樣就可大大壓縮了要考慮的2項(xiàng)集。



4.2.2 事務(wù)壓縮

Agrawal等提出壓縮進(jìn)一步迭代掃描的事務(wù)數(shù)的方法[AS94b, HF95]。因?yàn)椴话�含任何K項(xiàng)集的事務(wù)，不可能包含任何（K+1）項(xiàng)集，可對(duì)這些事務(wù)加上刪除標(biāo)志,掃描數(shù)據(jù)庫時(shí)不再考慮。



4.2.3 雜湊

一個(gè)高效地產(chǎn)生頻集的基于雜湊的算法由Park等提出[PCY95a]。通過實(shí)驗(yàn)我們可以發(fā)現(xiàn)尋找頻集主要的計(jì)算是在生成頻繁2-項(xiàng)集Lk上，Park等就是利用了這個(gè)性質(zhì)引入雜湊技術(shù)來改進(jìn)產(chǎn)生頻繁2-項(xiàng)集的方法。



4.2.4 劃分

Savasere等設(shè)計(jì)了一個(gè)基于劃分的算法[SON95]，這個(gè)算法先把數(shù)據(jù)庫從邏輯上分成幾個(gè)互不相交的塊，每次單獨(dú)考慮一個(gè)分塊并對(duì)它生成所有的頻集，然后把產(chǎn)生的頻集合并，用來生成所有可能的頻集，最后計(jì)算這些項(xiàng)集的支持度。這里分塊的大小選擇要使得每個(gè)分塊可以被放入主存，每個(gè)階段只需被掃描一次。而算法的正確性是由每一個(gè)可能的頻集至少在某一個(gè)分塊中是頻集保證的。上面所討論的算法是可以高度并行的，可以把每一分塊分別分配給某一個(gè)處理器生成頻集。產(chǎn)生頻集的每一個(gè)循環(huán)結(jié)束后，處理器之間進(jìn)行通信來產(chǎn)生全局的候選k-項(xiàng)集。通常這里的通信過程是算法執(zhí)行時(shí)間的主要瓶頸；而另一方面，每個(gè)獨(dú)立的處理器生成頻集的時(shí)間也是一個(gè)瓶頸。其他的方法還有在多處理器之間共享一個(gè)雜湊樹來產(chǎn)生頻集。更多的關(guān)于生成頻集的并行化方法可以在文獻(xiàn)[AS96]中找到。



4.2.5 選樣

基本思想是在給定數(shù)據(jù)的一個(gè)子集挖掘。對(duì)前一遍掃描得到的信息，仔細(xì)地組合分析，可以得到一個(gè)改進(jìn)的算法，Mannila等先考慮了這一點(diǎn)[MTV94]，他們認(rèn)為采樣是發(fā)現(xiàn)規(guī)則的一個(gè)有效途徑。隨后又由Toivonen進(jìn)一步發(fā)展了這個(gè)思想[Toi96]，先使用從數(shù)據(jù)庫中抽取出來的采樣得到一些在整個(gè)數(shù)據(jù)庫中可能成立的規(guī)則，然后對(duì)數(shù)據(jù)庫的剩余部分驗(yàn)證這個(gè)結(jié)果。Toivonen的算法相當(dāng)簡(jiǎn)單并顯著地減少了I/O代價(jià)，但是一個(gè)很大的缺點(diǎn)就是產(chǎn)生的結(jié)果不精確，即存在所謂的數(shù)據(jù)扭曲(data skew)。分布在同一頁面上的數(shù)據(jù)時(shí)常是高度相關(guān)的，可能不能表示整個(gè)數(shù)據(jù)庫中模式的分布，由此而導(dǎo)致的是采樣5%的交易數(shù)據(jù)所花費(fèi)的代價(jià)可能同掃描一遍數(shù)據(jù)庫相近。



4.2.6 動(dòng)態(tài)項(xiàng)集計(jì)數(shù)

Brin等人給出該算法[BMUT97]。動(dòng)態(tài)項(xiàng)集計(jì)數(shù)技術(shù)將數(shù)據(jù)庫劃分為標(biāo)記開始點(diǎn)的塊。不象Apriori僅在每次完整的數(shù)據(jù)庫掃描之前確定新的候選，在這種變形中，可以在任何開始點(diǎn)添加新的候選項(xiàng)集。該技術(shù)動(dòng)態(tài)地評(píng)估以被計(jì)數(shù)的所有項(xiàng)集的支持度，如果一個(gè)項(xiàng)集的所有子集以被確定為頻繁的，則添加它作為新的候選。結(jié)果算法需要的數(shù)據(jù)庫掃描比Apriori 少。





4.3 FP-樹頻集算法



針對(duì)Apriori算法的固有缺陷，J. Han等提出了不產(chǎn)生候選挖掘頻繁項(xiàng)集的方法—FP-樹頻集算法[HPY00]。采用分而治之的策略，在經(jīng)過第一遍掃描之后，把數(shù)據(jù)庫中的頻集壓縮進(jìn)一棵頻繁模式樹（FP-tree），同時(shí)依然保留其中的關(guān)聯(lián)信息，隨后再將FP-tree分化成一些條件庫，每個(gè)庫和一個(gè)長(zhǎng)度為1的頻集相關(guān)，然后再對(duì)這些條件庫分別進(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算法有巨大的提高。





4.4 多層關(guān)聯(lián)規(guī)則挖掘



對(duì)于很多的應(yīng)用來說，由于數(shù)據(jù)分布的分散性，所以很難在數(shù)據(jù)最細(xì)節(jié)的層次上發(fā)現(xiàn)一些強(qiáng)關(guān)聯(lián)規(guī)則。當(dāng)我們引入概念層次后，就可以在較高的層次上進(jìn)行挖掘[HF95, SA95]。雖然較高層次上得出的規(guī)則可能是更普通的信息，但是對(duì)于一個(gè)用戶來說是普通的信息，對(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ī)則的挖掘基本上可以沿用“支持度-可信度”的框架。不過，在支持度設(shè)置的問題上有一些要考慮的東西。

同層關(guān)聯(lián)規(guī)則可以采用兩種支持度策略：

1)  統(tǒng)一的最小支持度。對(duì)于不同的層次，都使用同一個(gè)最小支持度。這樣對(duì)于用戶和算法實(shí)現(xiàn)來說都比較的容易，但是弊端也是顯然的。

2)  遞減的最小支持度。每個(gè)層次都有不同的最小支持度，較低層次的最小支持度相對(duì)較小。同時(shí)還可以利用上層挖掘得到的信息進(jìn)行一些過濾的工作。

層間關(guān)聯(lián)規(guī)則考慮最小支持度的時(shí)候，應(yīng)該根據(jù)較低層次的最小支持度來定。





4.5 多維關(guān)聯(lián)規(guī)則挖掘



對(duì)于多維數(shù)據(jù)庫而言，除維內(nèi)的關(guān)聯(lián)規(guī)則外，還有一類多維的關(guān)聯(lián)規(guī)則。例如：

年齡（X，“20...30”） 職業(yè)（X,“學(xué)生”）==> 購買(X，“筆記本電腦”)

在這里我們就涉及到三個(gè)維上的數(shù)據(jù)：年齡、職業(yè)、購買。

根據(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”） 購買(X，“筆記本電腦”) ==> 購買(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)行[KHC97]。處理數(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ī)則。





5 展望



對(duì)于關(guān)聯(lián)規(guī)則挖掘領(lǐng)域的發(fā)展，筆者認(rèn)為可以在如下一些方向上進(jìn)行深入研究：在處理極大量的數(shù)據(jù)時(shí)，如何提高算法效率；對(duì)于挖掘迅速更新的數(shù)據(jù)的挖掘算法的進(jìn)一步研究；在挖掘的過程中，提供一種與用戶進(jìn)行交互的方法，將用戶的領(lǐng)域知識(shí)結(jié)合在其中；對(duì)于數(shù)值型字段在關(guān)聯(lián)規(guī)則中的處理問題；生成結(jié)果的可視化，等等。





參考文獻(xiàn)



[AIS93b] 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, p.p. 207-216, May 1993.



[AS94a] R. Agrawal, and R. Srikant.  Fast algorithms for mining association rules in large database. Technical Report FJ9839, IBM Almaden Research Center, San Jose, CA, Jun. 1994.



[AS94b] R. Agrawal, and R. Srikant.  Fast algorithms for mining association rules. In Proc. 1994 Int. Conf. Very Large Databases(VLDB’94), Sep. 1994.



[AS96] R. Agrawal, and J. Shafer.  Parallel mining of association rules: Design, Implementation, and Experience. IEEE Trans. Knowledge and data engineering, 8:962-969, Jan. 1996.



[BMUT97] 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, p.p. 255-264, May 1997.



[HF95] J, Han and Y. Fu. Discovery of multiple-level association rules from large databases. In Proc. 1995 Int. Conf. Very Large Databases(VLDB’95), p.p. 402-431, Sep. 1995.



[HPY00] 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), p.p. 1-12, May 2000.



[KHC97] M. Kamber, J. Han, J. Chang. Metarule-guided mining of multi-dimensional association rules using data cubes. In Proc. 1997 Int. Conf. Khowledge Discovery and Data Mining(KDD’97), p.p. 207-210, Aug. 1997

[KPR98] J. Kleinberg, C. Papadimitriou, and P. Raghavan. Segmentation problems. Proceedings of the 30th Annual Symposium on Theory of Computing, ACM. Sep. 1998.

[MTV94] H. Mannila, H. Toivonen, and A. Verkamo. Efficient algorithm for discovering association  rules. AAAI Workshop on Knowledge Discovery in Databases, p.p. 181-192, Jul. 1994.

[PCY95a] 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, p.p. 175-186, May 1995.

[PCY95b] 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, Nov. 1995.

[SA95] R. Srikant, and R. Agrawal. Mining generalized association rules. Proceedings of the 21st International Conference on Very Large Database, p.p. 407-419, Sep.1995.

[SON95] 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, p.p. 432-443, Sep. 1995.

[Toi96] H. Toivonen. Sampling large databases for association rules. Proceedings of the 22nd International Conference on Very Large Database, Bombay, India, p.p. 134-145, Sep. 1996.