關(guān)聯(lián)規(guī)則挖掘的原理和過(guò)程

從關(guān)聯(lián)規(guī)則（一）的分析中可知，關(guān)聯(lián)規(guī)則挖掘是從事務(wù)集合中挖掘出這樣的關(guān)聯(lián)規(guī)則：它的支持度和置信度大于最低閾值（minsup,minconf），這個(gè)閾值是由用戶指定的。根據(jù)
$$support=(X,Y).count/T.count$$

$$confidence=(X,Y).count/X.count$$

要想找出滿足條件的關(guān)聯(lián)規(guī)則，首先必須找出這樣的集合$F=X\cup Y$ ，它滿足$F.count/T.count\ge minsup$，其中$F.count$是$T$中包含$F$的事務(wù)的個(gè)數(shù)，然后再?gòu)?span id="ze8trgl8bvbq" class="katex--inline">$F$中找出這樣的蘊(yùn)含式$X\to Y$，它滿足$(X,Y).count/X.count\ge minconf$，并且$X=F?Y$。我們稱像$F$這樣的集合稱為頻繁項(xiàng)目集，假如$F$中的元素個(gè)數(shù)為$k$，我們稱這樣的頻繁項(xiàng)目集為$k?頻繁項(xiàng)目集$，它是項(xiàng)目集合$I$的子集。所以關(guān)聯(lián)規(guī)則挖掘可以大致分為兩步：

從事務(wù)集合中找出頻繁項(xiàng)目集；

從頻繁項(xiàng)目集合中生成滿足最低置信度的關(guān)聯(lián)規(guī)則。

通俗的理解：
頻繁項(xiàng)集所依賴的支持度其實(shí)就是覆蓋率。
關(guān)聯(lián)規(guī)則所依賴的可信度其實(shí)就是條件概率。

用于求解關(guān)聯(lián)規(guī)則頻繁項(xiàng)集的算法較為常用的有三種：

Apriori

FP-Growth

Eclat

本章節(jié)主要介紹Apriori算法。

Apriori算法

最出名的關(guān)聯(lián)規(guī)則挖掘算法是Apriori算法，它主要利用了向下封閉屬性：如果一個(gè)項(xiàng)集是頻繁項(xiàng)目集，那么它的非空子集必定是頻繁項(xiàng)目集。它先生成1-頻繁項(xiàng)目集，再利用1-頻繁項(xiàng)目集生成2-頻繁項(xiàng)目集。。。然后根據(jù)2-頻繁項(xiàng)目集生成3-頻繁項(xiàng)目集…依次類推，直至生成所有的頻繁項(xiàng)目集，然后從頻繁項(xiàng)目集中找出符合條件的關(guān)聯(lián)規(guī)則。

下面來(lái)討論一下頻繁項(xiàng)目集的生成過(guò)程，它的原理是根據(jù)$k?頻繁項(xiàng)目集$生成$(k+1)?頻繁項(xiàng)目集$。因此首先要做的是找出$1?頻繁項(xiàng)目集$，這個(gè)很容易得到，只要循環(huán)掃描一次事務(wù)集合統(tǒng)計(jì)出項(xiàng)目集合中每個(gè)元素的支持度，然后根據(jù)設(shè)定的支持度閾值進(jìn)行篩選，即可得到$1?頻繁項(xiàng)目集$。下面證明一下為何可以通過(guò)$k?頻繁項(xiàng)目集$生成$(k+1)?$頻繁項(xiàng)目集：

假設(shè)某個(gè)項(xiàng)目集$S=\{s_1,s_2,?s_n\}$是頻繁項(xiàng)目集，那么它的$(n?1)$非空子集$\{s_1,s_2,?s_{n?1}\}$，$\{s_1,s_2,?s_{n?2},s_n\}$ $?$ $\{s_2,s_3,?s_n\}$必定都是頻繁項(xiàng)目集，通過(guò)觀察，任何一個(gè)含有n個(gè)元素的集合$A=\{a_1,a_2,?a_n\}$，它的$(n?1)$非空子集定會(huì)包含兩項(xiàng)$\{a_1,a_2,?a_{n?2},a_{n?1}\}$和$\{a_1,a_2,?a_{n?2},a_n\}$，對(duì)比這兩個(gè)子集可以發(fā)現(xiàn)，它們的前$(n?2)$項(xiàng)是相同的，它們的并集就是集合$A$。對(duì)于2-頻繁項(xiàng)目集，它的所有1非空子集也必定是頻繁項(xiàng)目集，那么根據(jù)上面的性質(zhì)，對(duì)于2-頻繁項(xiàng)目集中的任一個(gè)，在1-頻繁項(xiàng)目集中必定存在2個(gè)集合(不需要一定是最后一個(gè)元素不同)的并集與它相同。因此在所有的1-頻繁項(xiàng)目集中找出只有一項(xiàng)不同的集合，將其合并，即可得到所有的包含2個(gè)元素的項(xiàng)目集，得到的這些包含2個(gè)元素的項(xiàng)目集不一定都是頻繁項(xiàng)目集，所以需要進(jìn)行剪枝。剪枝的辦法是看它的所有1非空子集是否在1-頻繁項(xiàng)目集中，如果存在1非空子集不在1-頻繁項(xiàng)目集中，則將該2項(xiàng)目集剔除。經(jīng)過(guò)該步驟之后，剩下的則全是頻繁項(xiàng)目集，即2-頻繁項(xiàng)目集。依次類推，可以生成3-頻繁項(xiàng)目集…直至生成所有的頻繁項(xiàng)目集。

生成頻繁項(xiàng)集

生成一個(gè)頻繁集的步驟分聯(lián)合和剪枝兩步。

聯(lián)合（join），偽代碼如下：

其中$L_{k?1}$為頻繁集。合并只有一個(gè)元素不同的$item$，如(1,2,3)、(1,3,7)和(1,4,9)，就會(huì)是(1,2,3)和(1,3,7)合并成(1,2,3,7)，而不會(huì)其他的合并，因?yàn)槠渌闆r，兩元素有不只一個(gè)元素不同(為確保合并后的項(xiàng)集元素只增加了一個(gè))。

剪枝（pruning）
合并后的集合，如果有子集不在原集合中，則把該合并集合刪除。例如：有2-頻繁項(xiàng)目集
　　$\{1,2\}，\{1,3\}，\{1,4\}，\{2,3\}，\{2,4\}$
因?yàn)?span id="ze8trgl8bvbq" class="katex--inline">$\{1,2\}，\{1,3\}，\{1,4\}$除了最后一個(gè)元素以外都相同，所以求$\{1,2\}，\{1,3\}$的并集得到$\{1,2,3\}$，$\{1,2\}$和$\{1,4\}$的并集得到$\{1,2,4\}，\{1,3\}和\{1,4\}$的并集得到$\{1,3,4\}$。但是由于$\{1,3,4\}$的子集$\{3,4\}$不在2-頻繁項(xiàng)目集中，所以需要把$\{1,3,4\}$剔除掉。

生成強(qiáng)規(guī)則

??得到頻繁項(xiàng)目集之后，則需要從頻繁項(xiàng)目集中找出符合條件的強(qiáng)關(guān)聯(lián)規(guī)則。最簡(jiǎn)單的辦法是：遍歷所有的頻繁項(xiàng)目集，然后從每個(gè)項(xiàng)目集中依次取個(gè)元素作為后件，該項(xiàng)目集中的其他元素作為前件，計(jì)算該規(guī)則的置信度進(jìn)行篩選即可。這樣的窮舉效率顯然很低。假如對(duì)于一個(gè)頻繁項(xiàng)目集$f$，可以生成下面這樣的關(guān)聯(lián)規(guī)則：
$$（f?\beta ）\to \beta$$

那么這條規(guī)則的置信度$confidence=f.count/(f?\beta ).count$
??根據(jù)這個(gè)置信度計(jì)算公式可知，對(duì)于一個(gè)頻繁項(xiàng)目集$f.count$是不變的，而假設(shè)該規(guī)則是強(qiáng)關(guān)聯(lián)規(guī)則，則$(f?{\beta }_{sub})\to {\beta }_{sub}$也是強(qiáng)關(guān)聯(lián)規(guī)則，其中${\beta }_{sub}$是$\beta$的子集，因?yàn)?span id="ze8trgl8bvbq" class="katex--inline">$(f?{\beta }_{sub}).count$肯定小于$(f?\beta ).count$。即給定一個(gè)頻繁項(xiàng)目集$f$，如果一條強(qiáng)關(guān)聯(lián)規(guī)則的后件為$\beta$，那么以$\beta$的非空子集為后件的關(guān)聯(lián)規(guī)則都是強(qiáng)關(guān)聯(lián)規(guī)則。所以可以先生成所有的1-后件（后件只有一項(xiàng)）強(qiáng)關(guān)聯(lián)規(guī)則，然后再生成2-后件強(qiáng)關(guān)聯(lián)規(guī)則，依次類推(與生成頻繁項(xiàng)集類似)，直至生成所有的強(qiáng)關(guān)聯(lián)規(guī)則。

一個(gè)例子

下面舉例說(shuō)明Apiori算法的具體流程：
假如有項(xiàng)目集合$I=\{1,2,3,4,5\}$，有事務(wù)集$T$：

t1:1,2,3 t2:1,2,4 t3:1,3,4 t4:1,2,3,5 t5:1,3,5 t6:2,4,5 t7:1,2,3,4

設(shè)定minsup=3/7，minconf=5/7。

首先：生成頻繁項(xiàng)目集：

1-頻繁項(xiàng)目集：$\{1\}，\{2\}，\{3\}，\{4\}，\{5\}$

??生成2-頻繁項(xiàng)目集：
??根據(jù)1-頻繁項(xiàng)目集生成所有的包含2個(gè)元素的項(xiàng)目集：任意取兩個(gè)只有最后一個(gè)元素不同的1-頻繁項(xiàng)目集，求其并集，由于每個(gè)1-頻繁項(xiàng)目集元素只有一個(gè)，所以生成的項(xiàng)目集如下：

$\{1,2\}，\{1,3\}，\{1,4\}，\{1,5\}$
$\{2,3\}，\{2,4\}，\{2,5\}$
$\{3,4\}，\{3,5\}$
$\{4,5\}$

??計(jì)算它們的支持度，發(fā)現(xiàn)只有$\{1,2\}，\{1,3\}，\{1,4\}，\{2,3\}，\{2,4\}，\{2,5\}$的支持度滿足要求，因此求得2-頻繁項(xiàng)目集：

$\{1,2\}，\{1,3\}，\{1,4\}，\{2,3\}，\{2,4\}$

??生成3-頻繁項(xiàng)目集：

??因?yàn)?span id="ze8trgl8bvbq" class="katex--inline">$\{1,2\}，\{1,3\}，\{1,4\}$除了最后一個(gè)元素以外都相同，所以求$\{1,2\}，\{1,3\}$的并集得到$\{1,2,3\}$，$\{1,2\}，\{1,4\}$的并集得到$\{1,2,4\}$，$\{1,3\}，\{1,4\}$的并集得到$\{1,3,4\}$。但是由于$\{1,3,4\}$的子集$\{3,4\}$不在2-頻繁項(xiàng)目集中，所以需要把$\{1,3,4\}$剔除掉。然后再來(lái)計(jì)算$\{1,2,3\}$和$\{1,2,4\}$的支持度，發(fā)現(xiàn)$\{1,2,3\}$的支持度為3/7，$\{1,2,4\}$的支持度為2/7，所以需要把$\{1,2,4\}$剔除。同理可以對(duì)$\{2,3\}$，$\{2,4\}$求并集得到$\{2,3,4\}$，但是$\{2,3,4\}$的支持度不滿足要求，所以需要剔除掉。

??因此得到3-頻繁項(xiàng)目集：$\{1,2,3\}$。

??到此頻繁項(xiàng)目集生成過(guò)程結(jié)束。注意生成頻繁項(xiàng)目集的時(shí)候，頻繁項(xiàng)目集中的元素個(gè)數(shù)最大值為事務(wù)集中事務(wù)中含有的最大元素個(gè)數(shù)，即若事務(wù)集中事務(wù)包含的最大元素個(gè)數(shù)為k，那么最多能生成k-頻繁項(xiàng)目集，這個(gè)原因很簡(jiǎn)單，因?yàn)槭聞?wù)集合中的所有事務(wù)都不包含（k+1）個(gè)元素，所以不可能存在（k+1）—頻繁項(xiàng)目集。在生成過(guò)程中，若得到的頻繁項(xiàng)目集個(gè)數(shù)小于2，生成過(guò)程也可以結(jié)束了。
　　
??現(xiàn)在需要生成強(qiáng)關(guān)聯(lián)規(guī)則：

??這里只說(shuō)明3-頻繁項(xiàng)目集生成關(guān)聯(lián)規(guī)則的過(guò)程：

??對(duì)于集合$\{1,2,3\}$

??先生成1-后件的關(guān)聯(lián)規(guī)則：

$（1,2）\to 3$，置信度=3/4

$（1,3）\to 2$，置信度=3/5

$（2,3）\to 1$，置信度=3/3

$（1,3）\to 2$ 的置信度不滿足要求，所以剔除掉。因此得到1后件的集合$\{1\}$，$\{3\}$，然后再以$\{1,3\}$作為后件。
　　
?? $2\to (1,3)$ 的置信度=3/5不滿足要求，所以對(duì)于3-頻繁項(xiàng)目集生成的強(qiáng)關(guān)聯(lián)規(guī)則為：$（1,2）\to 3$和$（2,3）\to 1$。

Apriori算法的優(yōu)缺點(diǎn)

• 優(yōu)點(diǎn)
  Apriori算法采用了逐層搜索的迭代的方法，算法簡(jiǎn)單明了，沒(méi)有復(fù)雜的理論推導(dǎo)，也易于實(shí)現(xiàn)。
• 缺點(diǎn)

對(duì)數(shù)據(jù)庫(kù)的掃描次數(shù)過(guò)多，導(dǎo)致數(shù)據(jù)量大時(shí)速度很慢。

Apriori算法會(huì)產(chǎn)生大量的中間項(xiàng)集（候選集）。

采用唯一支持度。

算法的適應(yīng)面窄。

• 改進(jìn)方式有三個(gè)角度：

減少掃描數(shù)據(jù)庫(kù)的次數(shù)（Partition算法、FP-growth算法）

減少候選集（Aprior已經(jīng)減少了一部分candidates，但還有沒(méi)有更快的方法）

怎樣數(shù)這個(gè)candiates出現(xiàn)次數(shù)數(shù)的更快

參考文章:http://www.cnblogs.com/dolphin0520/archive/2012/10/29/2733356.html

總結(jié)

以上是生活随笔為你收集整理的【机器学习】数据挖掘算法——关联规则（二），挖掘过程，Aprioir算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。