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

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-項集的方法。