關聯規則挖掘算法綜述  


1 引言

關聯規則挖掘發現大量數據中項集之間有趣的關聯或相關聯系。它在數據挖掘中是一個重要的課題，最近幾年已被業界所廣泛研究。

關聯規則挖掘的一個典型例子是購物籃分析。關聯規則研究有助于發現交易數據庫中不同商品（項）之間的聯系，找出顧客購買行為模式，如購買了某一商品對購買其他商品的影響。分析結果可以應用于商品貨架布局、貨存安排以及根據購買模式對用戶進行分類。

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

最近也有獨立于Agrawal的頻集方法的工作[HPY00]，以避免頻集方法的一些缺陷，探索挖掘關聯規則的新方法。也有一些工作[KPR98]注重于對挖掘到的模式的價值進行評估，他們提出的模型建議了一些值得考慮的研究方向。

 

 

2 基本概念

         

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

       關聯規則是如下形式的邏輯蘊涵：A Þ B，AÌI, AÌI，且A∩B=F。關聯規則具有如下兩個重要的屬性：

支持度: P(A∪B)，即A和B這兩個項集在事務集D中同時出現的概率。

置信度: P(B｜A)，即在出現項集A的事務集D中，項集B也同時出現的概率。

同時滿足最小支持度閾值和最小置信度閾值的規則稱為強規則。給定一個事務集D，挖掘關聯規則問題就是產生支持度和可信度分別大于用戶給定的最小支持度和最小可信度的關聯規則，也就是產生強規則的問題。

 

3 關聯規則種類

 

1) 基于規則中處理的變量的類別，關聯規則可以分為布爾型和數值型。

布爾型關聯規則處理的值都是離散的、種類化的，它顯示了這些變量之間的關系。

數值型關聯規則可以和多維關聯或多層關聯規則結合起來，對數值型字段進行處理，將其進行動態的分割，或者直接對原始的數據進行處理，當然數值型關聯規則中也可以包含種類變量。

 

2) 基于規則中數據的抽象層次，可以分為單層關聯規則和多層關聯規則。

在單層關聯規則中，所有的變量都沒有考慮到現實的數據是具有多個不同的層次的。

在多層關聯規則中，對數據的多層性已經進行了充分的考慮。

 

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

在單維關聯規則中，我們只涉及到數據的一個維，如用戶購買的物品

在多維關聯規則中，要處理的數據將會涉及多個維。

 

 

4 算法綜述

4.1 經典的頻集算法

 

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

所有支持度大于最小支持度的項集稱為頻繁項集，簡稱頻集。

 

4.1.1 算法的基本思想

首先找出所有的頻集，這些項集出現的頻繁性至少和預定義的最小支持度一樣。然后由頻集產生強關聯規則，這些規則必須滿足最小支持度和最小可信度。

  挖掘關聯規則的總體性能由第一步決定，第二步相對容易實現。

 

4.1.2 Apriori核心算法分析

為了生成所有頻集，使用了遞推的方法。其核心思想簡要描述如下：

(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);    //事務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;

首先產生頻繁1-項集L1，然后是頻繁2-項集L2，直到有某個r值使得Lr為空，這時算法停止。這里在第k次循環中，過程先產生候選k-項集的集合Ck，Ck中的每一個項集是對兩個只有一個項不同的屬于Lk-1的頻集做一個(k-2)-連接來產生的。Ck中的項集是用來產生頻集的候選集，最后的頻集Lk必須是Ck的一個子集。Ck中的每個元素需在交易數據庫中進行驗證來決定其是否加入Lk，這里的驗證過程是算法性能的一個瓶頸。這個方法要求多次掃描可能很大的交易數據庫，即如果頻集最多包含10個項，那么就需要掃描交易數據庫10遍，這需要很大的I/O負載。

可能產生大量的候選集,以及可能需要重復掃描數據庫，是Apriori算法的兩大缺點。

 

4.1.3 算法的優化

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

 

 

4.2 改進的頻集算法

 

4.2.1散列

該算法由Park等在1995年提出[PCY95b]。通過實驗發現尋找頻繁項集的主要計算是在生成頻繁2項集L2上，Park就是利用這個性質引入散列技術來改進產生頻繁2項集的方法。

    其基本思想是：當掃描數據庫中每個事務，由C1中的候選1項集產生頻繁1項集L1時，對每個事務產生所有的2項集，將它們散列到散列表結構的不同桶中，并增加對應的桶計數，在散列表中對應的桶計數低于支持度閾值的2項集不可能是頻繁2項集，可從候選2項集中刪除，這樣就可大大壓縮了要考慮的2項集。

 

4.2.2 事務壓縮

Agrawal等提出壓縮進一步迭代掃描的事務數的方法[AS94b, HF95]。因為不包含任何K項集的事務，不可能包含任何（K+1）項集，可對這些事務加上刪除標志,掃描數據庫時不再考慮。

 

4.2.3 雜湊

一個高效地產生頻集的基于雜湊的算法由Park等提出[PCY95a]。通過實驗我們可以發現尋找頻集主要的計算是在生成頻繁2-項集Lk上，Park等就是利用了這個性質引入雜湊技術來改進產生頻繁2-項集的方法。

 

4.2.4 劃分

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

 

4.2.5 選樣

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

 

4.2.6 動態項集計數

Brin等人給出該算法[BMUT97]。動態項集計數技術將數據庫劃分為標記開始點的塊。不象Apriori僅在每次完整的數據庫掃描之前確定新的候選，在這種變形中，可以在任何開始點添加新的候選項集。該技術動態地評估以被計數的所有項集的支持度，如果一個項集的所有子集以被確定為頻繁的，則添加它作為新的候選。結果算法需要的數據庫掃描比Apriori 少。

 

 

4.3 FP-樹頻集算法

 

針對Apriori算法的固有缺陷，J. Han等提出了不產生候選挖掘頻繁項集的方法—FP-樹頻集算法[HPY00]。采用分而治之的策略，在經過第一遍掃描之后，把數據庫中的頻集壓縮進一棵頻繁模式樹（FP-tree），同時依然保留其中的關聯信息，隨后再將FP-tree分化成一些條件庫，每個庫和一個長度為1的頻集相關，然后再對這些條件庫分別進行挖掘。當原始數據量很大的時候，也可以結合劃分的方法,使得一個FP-tree可以放入主存中。實驗表明，FP-growth對不同長度的規則都有很好的適應性，同時在效率上較之apriori算法有巨大的提高。

 

 

4.4 多層關聯規則挖掘

 

對于很多的應用來說，由于數據分布的分散性，所以很難在數據最細節的層次上發現一些強關聯規則。當我們引入概念層次后，就可以在較高的層次上進行挖掘[HF95, SA95]。雖然較高層次上得出的規則可能是更普通的信息，但是對于一個用戶來說是普通的信息，對于另一個用戶卻未必如此。所以數據挖掘應該提供這樣一種在多個層次上進行挖掘的功能。

多層關聯規則的分類：根據規則中涉及到的層次，多層關聯規則可以分為同層關聯規則和層間關聯規則。

多層關聯規則的挖掘基本上可以沿用“支持度-可信度”的框架。不過，在支持度設置的問題上有一些要考慮的東西。

同層關聯規則可以采用兩種支持度策略：

1)  統一的最小支持度。對于不同的層次，都使用同一個最小支持度。這樣對于用戶和算法實現來說都比較的容易，但是弊端也是顯然的。

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

層間關聯規則考慮最小支持度的時候，應該根據較低層次的最小支持度來定。

 

 

4.5 多維關聯規則挖掘

 

對于多維數據庫而言，除維內的關聯規則外，還有一類多維的關聯規則。例如：

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

在這里我們就涉及到三個維上的數據：年齡、職業、購買。

根據是否允許同一個維重復出現，可以又細分為維間的關聯規則（不允許維重復出現）和混合維關聯規則（允許維在規則的左右同時出現）。

年齡（X，“20...30”） 購買(X，“筆記本電腦”) ==> 購買(X，“打印機”)

這個規則就是混合維關聯規則。

在挖掘維間關聯規則和混合維關聯規則的時候，還要考慮不同的字段種類：種類型和數值型。

對于種類型的字段，原先的算法都可以處理。而對于數值型的字段，需要進行一定的處理之后才可以進行[KHC97]。處理數值型字段的方法基本上有以下幾種：

1)  數值字段被分成一些預定義的層次結構。這些區間都是由用戶預先定義的。得出的規則也叫做靜態數量關聯規則。

2)  數值字段根據數據的分布分成了一些布爾字段。每個布爾字段都表示一個數值字段的區間，落在其中則為1，反之為0。這種分法是動態的。得出的規則叫布爾數量關聯規則。

3)  數值字段被分成一些能體現它含義的區間。它考慮了數據之間的距離的因素。得出的規則叫基于距離的關聯規則。

4)  直接用數值字段中的原始數據進行分析。使用一些統計的方法對數值字段的值進行分析，并且結合多層關聯規則的概念，在多個層次之間進行比較從而得出一些有用的規則。得出的規則叫多層數量關聯規則。