前言

關(guān)聯(lián)規(guī)則挖掘發(fā)現(xiàn)大量數(shù)據(jù)中項集之間有趣的關(guān)聯(lián)或者相互聯(lián)系。關(guān)聯(lián)規(guī)則挖掘的一個典型例子就是購物籃分析，該過程通過發(fā)現(xiàn)顧客放入其購物籃中不同商品之間的聯(lián)系，分析出顧客的購買習慣，通過了解哪些商品頻繁地被顧客同時買入，能夠幫助零售商制定合理的營銷策略。購物籃事務(wù)的例子如下圖所示：??

?

例如：在同一次去超級市場時，如果顧客購買牛奶，同時他也購買面包的可能性有多大？

通過幫助零售商有選擇地經(jīng)銷和安排貨架，這種信息會引導(dǎo)銷售。零售商有兩種方法可以進行安排貨架，第一種方法是將牛奶和面包盡可能的放的近一些，方便顧客自取，第二種方法是將牛奶和面包放的遠一些，顧客在購買這兩件物品的時候，這中間貨架上的物品也會被顧客選擇購買。這兩種方法都可以進一步刺激消費。但是，如何發(fā)現(xiàn)牛奶和面包之間的關(guān)聯(lián)關(guān)系呢？Apriori算法可以進行關(guān)聯(lián)規(guī)則挖掘。

算法中的基本概念

1、項集和K-項集

令I(lǐng)={i1，i2，i3……id}是購物籃數(shù)據(jù)中所有項的集合，而T={t1，t2，t3….tN}是所有事務(wù)的集合，每個事務(wù)ti包含的項集都是I的子集。在關(guān)聯(lián)分析中，包含0個或多個項的集合稱為項集。如果一個項集包含K個項，則稱它為K-項集?？占侵覆话魏雾椀捻椉＠?，在購物籃事務(wù)的例子中，｛啤酒，尿布，牛奶｝是一個3-項集。

2、支持度計數(shù)

項集的一個重要性質(zhì)是它的支持度計數(shù)，即包含特定項集的事務(wù)個數(shù)，數(shù)學上，項集X的支持度計數(shù)σ（X）可以表示為

σ（X）=|{ti|X?ti，ti∈T}|

其中，符號|*|表示集合中元素的個數(shù)。

在購物籃事務(wù)的例子中，項集｛啤酒，尿布，牛奶｝的支持度計數(shù)為2，因為只有3和4兩個事務(wù)中同時包含這3個項。

3、關(guān)聯(lián)規(guī)則

關(guān)聯(lián)規(guī)則是形如X→Y的蘊含表達式，其中X和Y是不相交的項集，即X∩Y=?。

關(guān)聯(lián)規(guī)則的強度可以用它的支持度（support）和置信度（confidence）來度量。支持度確定規(guī)則可以用于給定數(shù)據(jù)集的頻繁程度，而置信度確定Y在包含X的事務(wù)中出現(xiàn)的頻繁程度。

支持度（s）和置信度（c）這兩種度量的形式定義如下：

s（X→Y）=σ（X∪Y）/N

c（X→Y）=σ（X∪Y）/σ（X）

其中， σ（X∪Y）是（X∪Y）的支持度計數(shù)，N為事務(wù)總數(shù)，σ（X）是X的支持度計數(shù)。

Example

在購物籃事務(wù)的例子中，考慮規(guī)則{牛奶，尿布}→{啤酒}。由于項集{牛奶，尿布，啤酒}的支持度計數(shù)為2，而事務(wù)的總數(shù)為5，所以規(guī)則的支持度為2/5=0.4。

規(guī)則的置信度是項集{牛奶，尿布，啤酒}的支持度計數(shù)與項集{牛奶，尿布}支持度技術(shù)的商，由于存在3個事務(wù)同時包含牛奶和尿布，所以規(guī)則的置信度為2/3=0.67。

關(guān)聯(lián)規(guī)則發(fā)現(xiàn)

給定事務(wù)的集合T，關(guān)聯(lián)規(guī)則發(fā)現(xiàn)是指找出支持度大于等于minsup （最小支持度）并且置信度大于等于minconf（最小置信度）的所有規(guī)則，minsup和minconf是對應(yīng)的支持度和置信度閾值。

關(guān)聯(lián)規(guī)則的挖掘是一個兩步的過程：

（1）頻繁項集產(chǎn)生：其目標是發(fā)現(xiàn)滿足最小支持度閾值的所有項集（至少和預(yù)定義的最小支持計數(shù)一樣），這些項集稱作頻繁項集。

（2）規(guī)則的產(chǎn)生：其目標是從上一步發(fā)現(xiàn)的頻繁項集中提取所有高置信度的規(guī)則，這些規(guī)則稱作強規(guī)則。（必須滿足最小支持度和最小置信度）

Apriori算法介紹

Apriori算法的實質(zhì)使用候選項集找頻繁項集。

Apriori 算法是一種最有影響的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項集的算法。算法的名字基于這樣的事實：算法使用頻繁項集性質(zhì)的先驗知識， 正如我們將看到的。Apriori 使用一種稱作逐層搜索的迭代方法，k-項集用于探索（k+1）-項集。首先，找出頻繁1-項集的集合。該集合記作L1。L1 用于找頻繁2-項集的集合L2，而L2 用于找L3，如此下去，直到不能找到頻繁k-項集。找每個Lk 需要一次數(shù)據(jù)庫掃描。

Apriori性質(zhì)

Apriori性質(zhì)：頻繁項集的所有非空子集都必須也是頻繁的。 Apriori 性質(zhì)基于如下觀察：根據(jù)定義，如果項集I不滿足最小支持度閾值s，則I不是頻繁的，即P（I）《 s。如果項A添加到I，則結(jié)果項集（即I∪A）不可能比I更頻繁出現(xiàn)。因此， I∪A也不是頻繁的，即 P（I∪A）《 s 。

該性質(zhì)屬于一種特殊的分類，稱作反單調(diào)，意指如果一個集合不能通過測試，則它的所有超集也都不能通過相同的測試。稱它為反單調(diào)的，因為在通不過測試的意義下，該性質(zhì)是單調(diào)的。

先驗定理

先驗定理：如果一個項集是頻繁的，則它的所有子集一定也是頻繁的。

（關(guān)于先驗定理、單調(diào)與反單調(diào)可以參考下面的例子理解）

?

如圖所示，假定｛c，d，e｝是頻繁項集。顯而易見，任何包含項集{c，d，e}的事務(wù)一定包含它的子集{c，d}，{c，e}，{d，e}，{c}，a5mgapgs4i和{e}。這樣，如果{c，d，e}是頻繁的，則它的所有子集一定也是頻繁的。

?

如果項集{a，b}是非頻繁的，則它的所有超集也一定是非頻繁的。即一旦發(fā)現(xiàn){a，b}是非頻繁的，則整個包含{a，b}超集的子圖可以被立即剪枝。這種基于支持度度量修剪指數(shù)搜索空間的策略稱為基于支持度的剪枝。

這種剪枝策略依賴于支持度度量的一個關(guān)鍵性質(zhì)，即一個項集的支持度絕不會超過它的子集的支持度。這個性質(zhì)也稱支持度度量的反單調(diào)性。

挖掘頻繁項集

Apriori算法的關(guān)鍵是如何用Lk-1找Lk？由下面的兩步過程連接和剪枝組成。

連接步：為找Lk，通過Lk-1與自己連接產(chǎn)生候選k-項集的集合。該候選項集的集合記作Ck。設(shè)l1和l2是Lk-1中的項集。記號li［j］表示li的第j項（例如，l1［k-2］表示l1的倒數(shù)第3項）。為方便計，假定事務(wù)或項集中的項按字典次序排序。執(zhí)行連接Lk-1　Lk-1；其中，Lk-1的元素是可連接的，如果它們前（k-2）個項相同；即，Lk-1的元素l1和l2是可連接的，如果（l1［1］=l2［1］）∧（l1［2］=l2［2］）∧…∧（l1［k-2］=l2［k-2］）∧（l1［k-1］《 l2［k-1］）。條件（l1［k-1］《 l2［k-1］）是簡單地保證不產(chǎn)生重復(fù)。連接l1和l2產(chǎn)生的結(jié)果項集是l1［1］l1［2］…l1［k-1］l2［k-1］。

剪枝步：Ck是Lk的超集；即，它的成員可以是頻繁的，也可以不是頻繁的，但所有的頻繁k-項集都包含在Ck中。掃描數(shù)據(jù)庫，確定Ck中每個候選的計數(shù)，從而確定Lk（即，根據(jù)定義，計數(shù)值不小于最小支持度計數(shù)的所有候選是頻繁的，從而屬于Lk）。然而，Ck可能很大，這樣所涉及的計算量就很大。為壓縮Ck，可以用以下辦法使用Apriori性質(zhì)：任何非頻繁的（k-1）-項集都不是可能是頻繁k-項集的子集。因此，如果一個候選k-項集的（k-1）-子集不在Lk-1中，則該候選也不可能是頻繁的，從而可以由Ck中刪除。這種子集測試可以使用所有頻繁項集的散列樹快速完成。

Apriori算法

算法6.2.1（Apriori） 使用逐層迭代找出頻繁項集

輸入：事務(wù)數(shù)據(jù)庫D；12345678910111213141516最小支持度閾值。

輸出：D中的頻繁項集L。

方法：

1） L1 = find_frequent_1_itemsets（D）; //找出頻繁1-項集的集合L1

2） for（k = 2; Lk-1 ≠ ?; k++） { //產(chǎn)生候選，并剪枝

3） Ck = aproiri_gen（Lk-1，min_sup）;

4） for each transaction t∈D{ //掃描D進行候選計數(shù)

5） Ct = subset（Ck，t）; //得到t的子集

6） for each candidate c∈Ct

7） c.count++; //支持度計數(shù)

8） }

9） Lk={c∈Ck| c.count ≥min_sup} //返回候選項集中不小于最小支持度的項集

10） }

11） return L = ∪kLk；//所有的頻繁集

第一步（連接 join）

Procedure apriori_gen（Lk-1： frequent （k-1）-itemset; min_sup： support）

1） for each itemset l1∈Lk-1

2） for each itemset l2∈Lk-1

3） if（l1［1］=l2［1］）∧。..∧（l1［k-2］=l2［k-2］）∧（l1［k-1］《l2［k-1］） then{

4） c = l1　l2; //連接步：l1連接l2

//連接步產(chǎn)生候選，若K-1項集中已經(jīng)存在子集c，則進行剪枝

5） if has_infrequent_subset（c，Lk-1） then

6） delete c; //剪枝步：刪除非頻繁候選

7） else add c to Ck;

8） }

9） return Ck;

12345678910111213

第二步：剪枝（prune）

Procedure has_infrequent_subset（c:candidate k-itemset; Lk-1:frequent （k-1）-itemset） //使用先驗定理

1） for each （k-1）-subset s of c

2） if c?Lk-1 then

3） return TRUE;

4） return FALSE;

1234567

由頻繁項集產(chǎn)生關(guān)聯(lián)規(guī)則

一旦由數(shù)據(jù)庫D中的事務(wù)找出頻繁項集，由它們產(chǎn)生強關(guān)聯(lián)規(guī)則是直接了當?shù)模◤婈P(guān)聯(lián)規(guī)則滿足最小支持度和最小置信度）。對于置信度，可以用下式，其中條件概率用項集支持度計數(shù)表示。

confidence（A→B）=P（A│B）=support（A∪B）/support（A）

其中，support（A∪B）是（A∪B）的支持度計數(shù)，support（A）是A的支持度計數(shù)。

根據(jù)該式，關(guān)聯(lián)規(guī)則可以產(chǎn)生如下：

? 1、對于每個頻繁項集l，產(chǎn)生l的所有非空子集。

? 2、對于l的每個非空子集s，如果support（l）/support（s） ≥min_conf，則輸出規(guī)則“s?（l-s）”。其中，min_conf是最小置信度閾值。

由于規(guī)則由頻繁項集產(chǎn)生，每個規(guī)則都自動滿足最小支持度。頻繁項集連同它們的支持度預(yù)先存放在hash表中，使得它們可以快速被訪問。

Apriori算法的實例

問題：數(shù)據(jù)庫中有9個事務(wù)，即|D| = 9。Apriori假定事務(wù)中的項按字典次序存放。我們使用下圖解釋Apriori算法發(fā)現(xiàn)D中的頻繁項集。 圖四

分析與解：

（一）、挖掘頻繁項集

1、在算法的第一次迭代，每個項都是候選1-項集的集合C1的成員，算法簡單地掃描所有的事務(wù)，對每個項的出現(xiàn)次數(shù)計數(shù)。

2、假定最小事務(wù)支持計數(shù)為2（即，minsup=2/9=22%）。可以確定頻繁1-項集的集合L1。它由具有最小支持度的候選1-項集組成。

?

3、為發(fā)現(xiàn)頻繁2-項集的集合L2，算法使用L1　L1產(chǎn)生候選2-項集的集合C2。

4、下一步，掃描D中事務(wù)，計算C2中每個候選項集的支持計數(shù)。

5、確定頻繁2-項集的集合L2，它由具有最小支持度的C2中的候選2-項集組成。

【注】 L1　L1等價于L1×L1，因為Lk　Lk的定義要求兩個連接的項集共享k-1個項。

?

6、候選3-項集的集合C3的產(chǎn)生詳細地列在圖中。首先，令C3 = L2　L2 = {{I1，I2，I3}， {I1，I2，I5}， {I1，I3，I5}， {I2，I3，I4}， {I2，I3，I5}， {I2，I4，I5}}。根據(jù)Apriori性質(zhì)，頻繁項集的所有子集必須是頻繁的，我們可以確定后4個候選不可能是頻繁的。因此，我們把它們由C3刪除，這樣，在此后掃描D確定L3時就不必再求它們的計數(shù)值。注意，Apriori算法使用逐層搜索技術(shù)，給定k-項集，我們只需要檢查它們的（k-1）-子集是否頻繁。

【L2 L2連接生成C3的過程】

1．連接：C3= L2 L2={{I1，I2}，{I1，I3}，{I1，I5}，{I2，I3}，{I2，I4}，{I2，I5}} 　{{I1，I2}，{I1，I3}，{I1，I5}，{I2，I3}，{I2，I4}，{I2，I5}} = {{I1，I2，I3}，{I1，I2，I5}，{I1，I3，I5}，{I2，I3，I4}，{I2，I3，I5}，{I2，I4，I5}}

2．使用Apriori性質(zhì)剪枝：頻繁項集的所有子集必須是頻繁的。存在候選項集，其子集不是頻繁的嗎？

?{I1，I2，I3}的2-項子集是{I1，I2}，{I1，I3}和{I2，I3}。{I1，I2，I3}的所有2-項子集都是L2的元素。因此，保留{I1，I2，I3}在C3中。

?{I1，I2，I5}的2-項子集是{I1，I2}，{I1，I5}和{I2，I5}。{I1，I2，I5}的所有2-項子集都是L2的元素。因此，保留{I1，I2，I5}在C3中。

?{I1，I3，I5}的2-項子集是{I1，I3}，{I1，I5}和{I3，I5}。{I3，I5}不是L2的元素，因而不是頻繁的。這樣，由C3中刪除{I1，I3，I5}。

?{I2，I3，I4}的2-項子集是{I2，I3}，{I2，I4}和{I3，I4}。{I3，I4}不是L2的元素，因而不是頻繁的。這樣，由C3中刪除{I2，I3，I4}。

?{I2，I3，I5}的2-項子集是{I2，I3}，{I2，I5}和{I3，I5}。{I3，I5}不是L2的元素，因而不是頻繁的。這樣，由C3中刪除{I2，I3，I5}。

?{I2，I4，I5}的2-項子集是{I2，I4}，{I2，I5}和{I4，I5}。{I4，I5}不是L2的元素，因而不是頻繁的。這樣，由C3中刪除{I2，I3，I5}。

3．這樣，剪枝后C3 = {{I1，I2，I3}，{I1，I2，I5}}

7、掃描D中事務(wù)，以確定L3，它由具有最小支持度的C3中的候選3-項集組成。

?

8、算法使用L3　L3產(chǎn)生候選4-項集的集合C4。盡管連接產(chǎn)生結(jié)果{{I1，I2，I3，I5}}，這個項集被剪去，因為它的子集{I1，I3，I5}不是頻繁的。這樣，C4=?，因此算法終止，找出了所有的頻繁項集。

（二）、由頻繁項集產(chǎn)生關(guān)聯(lián)規(guī)則

假定數(shù)據(jù)包含頻繁項集l={I1，I2，I5}，可以由l產(chǎn)生哪些關(guān)聯(lián)規(guī)則？l的非空子集有{I1，I2}，{I1，I5}，{I2，I5}，{I1}，{I2}和{I5}。結(jié)果關(guān)聯(lián)規(guī)則如下，每個都列出置信度。

I1∩I2→I5， confidence=2/4=0.5=50%

I1∩I5→I2， confidence=2/2=1=100%

I2∩I5→I1， confidence=2/2=1=100%

I1→I2∩I5， confidence=2/6=0.33=33%

I2→I1∩I5， confidence=2/7=0.29=29%

I5→I1∩I2， confidence=2/2=1=100%

如果最小置信度閾值為70%，則只有2、3和最后一個規(guī)則可以輸出，因為只有這些才是強規(guī)則。

優(yōu)缺點

優(yōu)點

使用先驗性質(zhì)，大大提高了頻繁項集逐層產(chǎn)生的效率；簡單易理解；數(shù)據(jù)集要求低。

缺點

1、候選頻繁K項集數(shù)量巨大。

2、在驗證候選頻繁K項集的時候，需要對整個數(shù)據(jù)庫進行掃描，非常耗時。

改進算法

算法思想：

上面的原始算法中由Ck（Lk-1直接生成的）到Lk經(jīng)過了兩步處理，第一步根據(jù)Lk-1進行裁剪，第二步根據(jù)minsupport裁剪。上面提到的兩個提高效率的方法都是基于第一步的。當經(jīng)過聯(lián)接生成K維數(shù)據(jù)項集時，判斷它的K-1維子集是否存在于Lk-1中，如果不在直接刪除。這樣每生成一個K維數(shù)據(jù)項集時，就要搜索一遍Lk-1。改進算法的思想就是只需要搜索一遍Lk-1就可以了。當所有聯(lián)接完成的時候，掃描一遍Lk-1，對于Lk-1任意元素A，判斷A是否為Ck中元素 c的子集，如果是，對子集c進行計數(shù)。也就是統(tǒng)計Lk-1中包含Ck中任意元素c的K-1維子集的個數(shù)。最后根據(jù)c進行裁剪。c的計數(shù)，即 Lk-1中包含的c的子集的個數(shù)，小于K，則刪除。

改進算法偽代碼

算法的主體不變，aprriori_gen函數(shù)改變?nèi)缦拢瘮?shù) has_infrequent_subset不再需要。

procedure apriori_gen（Lk-1:frequent（k-1）-itemsets;minsupport:minimum support threshold）

（1）for each itemset l1 ∈ Lk-1

（2）for each itemset l2∈ L k-1

（3）if（l1［1］=l2［1］）∧（l1［2］=l2［2］）∧…∧（l1［k-2］=l2［k-2］）∧（l1［k-1］=l2［k-1］） then

（4）c=l1∪ l2;

（5）for each itemset l1∈ L k-1 //掃描Lk-1中的元素

（6）for each candidate c∈ Ck //掃描 Ck中的元素

（7）if l1 is the subset of Ck then //判斷前者是不是后者的子集，如果是計數(shù)加1

（8）c.number++;

（9）C‘k={ c∈Ck |c.number=k};

（10）return C’k;

12345678910111213

例子對比：

問題：假設(shè)Lk-1={{1，2，3}，{1，2，4}，{2，3，4}，{2，3，5}，{1，3，4}}，求Lk。

由Lk-1得到Ck={{1，2，3，4}，{2，3，4，5}，{1，2，3，5}}。

原算法：首先得到{1，2，3，4}的子集{1，2，3}，{1，2，4}，{2，3，4}，{1，3，4}。然后判斷這些子集是不是 Lk-1的元素。如果都是則保留，否則刪除。這里保留，{2，3，4，5}和{1，2，3，5}則應(yīng)該刪除。得到C’k={{1，2，3，4}}。

改進算法：首先從Lk-1中取元素{1，2，3}，掃描Ck中的元素，看{1，2，3}是不是Ck元中元素的子集，{1，2，3}是{1，2，3，4}的子集，{1，2，3，4}的計數(shù)加1，{1，2，3}不是{2，3，4，5}的子集，計數(shù)不變，是{1，2，3，5}的子集，計數(shù)加1，經(jīng)過對{1，2，3}處理后得到計數(shù){1，0，1}；然后看{1，2，4}，{1，2，4}是{1，2，3，4}的子集，而不是 {2，3，4，5}的子集，也不是{1，2，3，5}的子集，計數(shù)不變，計數(shù)變?yōu)閧2，0，1}；考察{2，3，4}，{2，3，4}是{1，2，3，4}的子集，也是{2，3，4，5}的子集，不是｛1，2，3，5｝的子集，計數(shù)變?yōu)閧3，1，1}；{2，3，5}不是{1，2，3，4}的子集，是{2，3，4，5}的子集，也是{1，2，3，5}的子集，計數(shù)變?yōu)閧3，2，2}；{1，3，4}是{1，2，3，4}的子集，不是{2，3，4，5}的子集，也不是{1，2，3，5}的子集，計數(shù)變?yōu)閧4，2，2}。對數(shù)據(jù)掃描完畢。此時K=4，只有第一個元素的計數(shù)為4，為高頻數(shù)據(jù)項集。得到C’k={{1，2，3，4}}。

復(fù)雜度對比

下面對原算法和改進算法的性能進行比較。Lk-1中的數(shù)據(jù)項集的個數(shù)記為|Lk-1|，Ck中的數(shù)據(jù)項集的個數(shù)記為|Ck|，Ck中元素的子集個數(shù)設(shè)為ni，其中i=1～|Ck| 。這里只分析從Ck～C’k的處理。原 算法從 AprioriCk中取元素，然后求該元素的子集，判斷該子集是否在 |Ck|中。需要進行的計算為? 次， 1<=|L’k-1|<=|L’k-1|，1<= n’i <=n i。而改進算法是從Lk-1中選取元素，看是不是Ck中元素的子集，對 Ck中數(shù)據(jù)項集的子集個數(shù)進行統(tǒng)計。需要進行的計算是（|Lk-1|+1）*|Ck| 次。如果 n’i =1，就是每次只取Ck中數(shù)據(jù)項集的一個子集就可以判斷該數(shù)據(jù)項集，則兩個算法的效率基本相同，但是這種情況很少出現(xiàn)，從而大部分情況下，改進算法的效率要高于原算法。