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

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

Agrawal等于1993年首先提出了挖掘顧客交易數(shù)據(jù)庫(kù)中項(xiàng)集間的關(guān)聯(lián)規(guī)則問(wèn)題[AIS93b]，以后諸多的研究人員對(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ú)立于A(yíng)grawal的頻集方法的工作[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)可以是購(gòu)物籃中的物品，也可以是保險(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í)滿(mǎn)足最小支持度閾值和最小置信度閾值的規(guī)則稱(chēng)為強(qiáng)規(guī)則。給定一個(gè)事務(wù)集D，挖掘關(guān)聯(lián)規(guī)則問(wèn)題就是產(chǎn)生支持度和可信度分別大于用戶(hù)給定的最小支持度和最小可信度的關(guān)聯(lián)規(guī)則，也就是產(chǎn)生強(qiáng)規(guī)則的問(wèn)題。



3 關(guān)聯(lián)規(guī)則種類(lèi)



1) 基于規(guī)則中處理的變量的類(lèi)別，關(guān)聯(lián)規(guī)則可以分為布爾型和數(shù)值型。

布爾型關(guān)聯(lián)規(guī)則處理的值都是離散的、種類(lèi)化的，它顯示了這些變量之間的關(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ī)則中也可以包含種類(lèi)變量。



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)行了充分的考慮。



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

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

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





4 算法綜述

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



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

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



4.1.1 算法的基本思想

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

  挖掘關(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)中，過(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ù)載。

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



4.1.3 算法的優(yōu)化

為了提高算法的效率，Mannila等引入了修剪技術(shù)來(lái)減小候選集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è)修剪過(guò)程可以降低計(jì)算所有的候選集的支持度的代價(jià)。





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



4.2.1散列

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

    其基本思想是：當(dāng)掃描數(shù)據(jù)庫(kù)中每個(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)椴话魏蜬項(xiàng)集的事務(wù)，不可能包含任何（K+1）項(xiàng)集，可對(duì)這些事務(wù)加上刪除標(biāo)志,掃描數(shù)據(jù)庫(kù)時(shí)不再考慮。



4.2.3 雜湊

一個(gè)高效地產(chǎn)生頻集的基于雜湊的算法由Park等提出[PCY95a]。通過(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)集的方法。