關(guān)聯(lián)規(guī)則簡介

關(guān)聯(lián)規(guī)則挖掘可以讓我們從數(shù)據(jù)集中發(fā)現(xiàn)項(xiàng)與項(xiàng)之間的關(guān)系，它在我們的生活中有很多應(yīng)用場景，“購物籃分析”就是一個常見的場景，這個場景可以從消費(fèi)者交易記錄中發(fā)掘商品與商品之間的關(guān)聯(lián)關(guān)系，進(jìn)而通過商品捆綁銷售或者相關(guān)推薦的方式帶來更多的銷售量。

1. 搞懂關(guān)聯(lián)規(guī)則中的幾個重要概念：支持度、置信度、提升度

2. Apriori 算法的工作原理

3. 在實(shí)際工作中，我們該如何進(jìn)行關(guān)聯(lián)規(guī)則挖掘

關(guān)聯(lián)規(guī)則中重要的概念

我舉一個超市購物的例子，下面是幾名客戶購買的商品列表：

支持度

支持度是個百分比，它指的是某個商品組合出現(xiàn)的次數(shù)與總次數(shù)之間的比例。支持度越高，代表這個組合出現(xiàn)的頻率越大。

我們看啤酒出現(xiàn)了3次，那么5筆訂單中啤酒的支持度是3/5=0.6。同理，尿布出現(xiàn)了5次，那么尿布的支持度是5/5=1。尿布和啤酒同時出現(xiàn)的支持度是3/6=0.6。

置信度

它指的就是當(dāng)你購買了商品 A，會有多大的概率購買商品 B。

我們可以看上面的商品，購買尿布的同時又購買啤酒的訂單數(shù)是3，購買啤酒的訂單數(shù)是3，那么（尿布->啤酒）置信度= 3/3=1。

再看購買了啤酒同時購買尿布的訂單數(shù)是3，購買尿布的訂單數(shù)是5，那么（啤酒->尿布）置信度=3/5=0.6。

提升度

提升度代表的是“商品 A 的出現(xiàn)，對商品 B 的出現(xiàn)概率提升的”程度。所以我們在做商品推薦的時候，重點(diǎn)考慮的是提升度。

我們來看提升度公式：

那么我們來計(jì)算下尿布對啤酒的提升度是多少：

怎么解讀1.67這個數(shù)值呢？

1. 提升度 (A→B)>1：代表有提升

2. 提升度 (A→B)=1：代表有沒有提升，也沒有下降

3. 提升度 (A→B)<1：代表有下降。

其實(shí)看上面提升度的公式，我們就可以理解，也就是AB同時出現(xiàn)的次數(shù)越多，單獨(dú)出現(xiàn)B的次數(shù)越少，那么支持度也就越大也就是B的出現(xiàn)總是伴隨著A的出現(xiàn)，那么A對B出現(xiàn)的概率就越有提升！

Apriori 的工作原理

我們一起來看下經(jīng)典的關(guān)聯(lián)規(guī)則 Apriori 算法是如何工作的。

Apriori 算法其實(shí)就是查找頻繁項(xiàng)集 (frequent itemset) 的過程，所以我們需要先了解是頻繁項(xiàng)集。

頻繁項(xiàng)集就是支持度大于等于最小支持度閾值的項(xiàng)集，所以小于最小值支持度的項(xiàng)目就是非頻繁項(xiàng)集，而大于等于最小支持度的項(xiàng)集就是頻繁項(xiàng)集。

下面我們來舉個栗子：

假設(shè)我隨機(jī)指定最小支持度是0.2。首先，我們先計(jì)算單個商品的支持度：

因?yàn)樽钚≈С侄仁?0.2，所以你能看到商品 雞蛋 是不符合最小支持度的，不屬于頻繁項(xiàng)集，于是經(jīng)過篩選商品的頻繁項(xiàng)集如下：

在這個基礎(chǔ)上，我們將商品兩兩組合，得到兩個商品的支持度：

篩選大于最小支持度（0.2）的數(shù)據(jù)后

在這個基礎(chǔ)上，我們再將商品三個組合，得到三個商品的支持度：

篩選大于最小支持度（0.2）的數(shù)據(jù)后

在這個基礎(chǔ)上，我們將商品四個組合，得到四個商品的支持度：

再次篩選大于最小支持度（0.2）數(shù)據(jù)的話，就全刪除了，那么，此時算法結(jié)束，上一次的結(jié)果就是我們要找的頻繁項(xiàng)，也就是{牛奶、面包、尿布}、{面包、尿布、啤酒}。

我們來總結(jié)一下上述Apriori算法過程：

1. K=1，計(jì)算 K 項(xiàng)集的支持度

2. 篩選掉小于最小支持度的項(xiàng)集

3. 如果項(xiàng)集為空，則對應(yīng) K-1 項(xiàng)集的結(jié)果為最終結(jié)果

4. 否則 K=K+1，重復(fù) 1-3 步

我們可以看到 Apriori 在計(jì)算的過程中有以下幾個缺點(diǎn)：

1. 可能產(chǎn)生大量的候選集。因?yàn)椴捎门帕薪M合的方式，把可能的項(xiàng)集都組合出來了

2. 每次計(jì)算都需要重新掃描數(shù)據(jù)集，來計(jì)算每個項(xiàng)集的支持度

這就好比我們數(shù)據(jù)庫中的“全表掃描”查詢一樣，非常浪費(fèi)IO和時間。在數(shù)據(jù)庫中我們都知道使用索引來快速檢索數(shù)據(jù)，那Apriori 能優(yōu)化嗎？

Apriori 的改進(jìn)算法：FP-Growth 算法

FP-growth算法是基于Apriori原理的，通過將數(shù)據(jù)集存儲在FP樹上發(fā)現(xiàn)頻繁項(xiàng)集，但不能發(fā)現(xiàn)數(shù)據(jù)之間的關(guān)聯(lián)規(guī)則。FP-growth算法只需要對數(shù)據(jù)庫進(jìn)行兩次掃描，而Apriori算法在求每個潛在的頻繁項(xiàng)集時都需要掃描一次數(shù)據(jù)集，所以說Apriori算法是高效的。其中算法發(fā)現(xiàn)頻繁項(xiàng)集的過程是：(1)構(gòu)建FP樹；(2)從FP樹中挖掘頻繁項(xiàng)集。

創(chuàng)建項(xiàng)頭表

概念知識不在這湊字?jǐn)?shù)了，我們直接來干貨！假設(shè)我們從以下數(shù)據(jù)中來挖掘頻繁項(xiàng)。

首先創(chuàng)建，項(xiàng)頭表，這一步的流程是先掃描一遍數(shù)據(jù)集，對于滿足最小支持度的單個項(xiàng)按照支持度從高到低進(jìn)行排序，這個過程中刪除了不滿足最小支持度的項(xiàng)（假設(shè)最小支持度是0.2）。

構(gòu)建FP樹

整個流程是需要再次掃描數(shù)據(jù)集，對于每一條數(shù)據(jù)，按照支持度從高到低的順序進(jìn)行創(chuàng)建節(jié)點(diǎn)（也就是第一步中項(xiàng)頭表中的排序結(jié)果），節(jié)點(diǎn)如果存在就將計(jì)數(shù) count+1，如果不存在就進(jìn)行創(chuàng)建。同時在創(chuàng)建的過程中，需要更新項(xiàng)頭表的鏈表。

先把原始數(shù)據(jù)按照支持度排序，那么原始數(shù)據(jù)變化如下：

下面我們把以上每行數(shù)據(jù)，按照順序插入到FP樹中，注意FP樹的根節(jié)點(diǎn)記為 NULL 節(jié)點(diǎn)。

接下來插入第二行數(shù)據(jù)，由于第二行數(shù)據(jù)第一個數(shù)據(jù)也是B，和已有的樹結(jié)構(gòu)重合，那么我們保持原來樹結(jié)構(gòu)中的B位置不變，同時計(jì)數(shù)加1，C、D是新增數(shù)據(jù)，那么就會有新的樹分叉，結(jié)果如下圖：

以此類推，讀取下面的三行數(shù)據(jù)到FP樹中

最后生成的FP數(shù)如下：

根據(jù)FP數(shù)挖掘頻繁項(xiàng)

我們終于把FP樹建立好了，那么如何去看這顆樹呢？得到 FP 樹后，需要對每一個頻繁項(xiàng)，逐個挖掘頻繁項(xiàng)集。具體過程為：首先獲得頻繁項(xiàng)的前綴路徑，然后將前綴路徑作為新的數(shù)據(jù)集，以此構(gòu)建前綴路徑的條件 FP 樹。然后對條件 FP 樹中的每個頻繁項(xiàng)，獲得前綴路徑并以此構(gòu)建新的條件 FP 樹。不斷迭代，直到條件 FP 樹中只包含一個頻繁項(xiàng)為止（反正我第一次看完這句話是沒理解）。

FP樹是從下往上看了，也就是根據(jù)子節(jié)點(diǎn)找父節(jié)點(diǎn)，接下來還是來圖解~

首先，我們看包含A的頻繁項(xiàng)：

我們可以看到包含A的樹有兩個，我們先看樹2，可以得到路徑{B:2,C:2}，此處的2是根據(jù)A出現(xiàn)的次數(shù)定的。接著我們創(chuàng)建FP樹，具體的創(chuàng)建過程和上面創(chuàng)建 FP 樹的過程一樣，如下圖：

注意此時頭指針表中包含兩個元素，所以對每個元素，需要獲得前綴路徑，并將前綴路徑創(chuàng)建成條件 FP 樹，直到條件 FP 樹中只包含一個元素時返回。

• 對元素 B，獲得前綴路徑為{}，則頻繁項(xiàng)集返回{A:2,B:2};

• 對元素 C，獲得前綴路徑{B:2}，則將前綴路徑創(chuàng)建成條件 FP 樹，如下圖 所示。

• 注意此時條件 FP 樹中只包含一個元素，故返回頻繁項(xiàng)集{A:2,C:2,B:2}。由于元素 C 也是頻繁項(xiàng)，所以{A:2,C:2}也是頻繁項(xiàng)集。

再加上{A:2}本身就是頻繁項(xiàng)集，所以 A 對應(yīng)的頻繁項(xiàng)集有：{A:2},{A:2,C:2} ,{A:2,B:2},{A:2,C:2,B:2}。

同理，我們來看樹1，樹1比較簡單，就一個路徑{B:1}，根據(jù)上述方法我們得到此分支頻繁項(xiàng)為{A:1,B:1},{A:1}。

綜上，我們可以看到兩個分支都包含頻繁項(xiàng){A,B},{A}的，此時我們進(jìn)行合并兩個分支，得到包含A的頻繁項(xiàng)：{A:3},{A:3,B:3},{A:2,C:2} ,{A:2,C:2,B:2}，我們用出現(xiàn)的次數(shù)轉(zhuǎn)換下，即 (A,): 3, (A, B): 3, (A, C): 2, (A, B, C): 2。

同理，按照上述方法，我們可以依次找到包含B的頻繁項(xiàng)是(D): 2, (C, D): 2, (B, D): 2, (B, C, D): 2, (C): 4, (B, C): 4, (B): 5。

實(shí)踐總結(jié)

經(jīng)典的算法，很多大神已經(jīng)實(shí)現(xiàn)，我們直接拿來用就行了，比如上面的FP-GROWTH算法，介紹一款專門的包pyfpgrowth。

代碼：

import pyfpgrowth as fp

itemsets =  [['A','B'],  ['B','C','D'],['B','C'],['A','B','C'],['A','B','C','D']]

# 頻數(shù)刪選  頻數(shù)大于2

patterns = fp.find_frequent_patterns(itemsets,  2)

print(patterns)

{('D',): 2, ('C', 'D'): 2, ('B', 'D'): 2, ('B', 'C', 'D'): 2, ('A',): 3, ('A', 'B'): 3, ('A', 'C'): 2, ('A', 'B', 'C'): 2, ('C',): 4, ('B', 'C'): 4, ('B',): 5}

很對人會問算法原理看著很費(fèi)勁，直接兩行代碼搞定。我們還看原理干嘛，直接寫（抄）代碼不就行了。我舉個例子哈，記得上小學(xué)3年級的時候，有一次數(shù)學(xué)考試，老師出了一道附加題：

附加題（10分）：求1+2+3+…+99+100的和。提示：參考梯形面積計(jì)算公式。

當(dāng)然，對于一個初中生，這道題很好解答，但對于一個小學(xué)三年級的學(xué)生來說還是比較難的。但是，我知道梯形的計(jì)算公式：

梯形面積 = （上底+下底）×高÷2

所以，就按照這個計(jì)算了

1+2+3+…+99+100 = (1 + 100)x100÷2

其實(shí)，算法原理也是一樣，我們了解后，可以舉一反三的使用，并不一定總是在一個場景下使用的。