手把手程式實作分享系列：先驗演算法（Apriori Algorithm）關聯規則分析

Published in

Bandai的機器學習筆記

5 min readJan 9, 2020

0. 前言

關聯分析的概念是由Agrawal et. al. （1993）所提出，隨後，Agrawal & Srikant （1994）進一步提出 Apriori演算法，以做為關聯法則之工具。關聯分析主要透過「支持度」（Support）與「信賴度」（Confidence）來對商品項目之間的關聯性，進行篩選。其中，支持度（Support）意指即某項目集在資料庫中出現的次數比例。例如：某資料庫中有100筆交易紀錄，其中有20筆交易有購買啤酒，則啤酒的支持度為20%。信賴度（Confidence）意指兩個項目集之間的條件機率，也就是在A出現的情況下，B出現的機率值。

如果要直接拉到最下面看程式碼的朋友，請先看完下面這一段，了解最小支持度（Min Support）與最小信賴度（Min Confidence）是什麼。

在進行關聯分析時，我們通常會先設定最小支持度（Min Support）與最小信賴度（Min Confidence）。如果所設定的最小支持度與最小信賴度太低，則關聯出來的結果會產生太多規則，造成決策上的干擾。反之，太高的最小支持度與最小信賴度則可能會面臨規則太少，難以判斷的窘境。

1. Apriori 理念

找出所有的頻集，這些項集出現的頻繁性至少和預定義的最小支持度一樣。然後由頻集產生強關聯規則，這些規則必須滿足最小支持度和最小可信度。產生只包含集合的項的所有規則，其中每一條規則的右部只有一項，這裡採用的是中規則的定義。一旦這些規則被生成，那麼只有那些大於使用者給定的最小可信度的規則才被留下來。

2. Apriori演算法過程

通過迭代，檢索出事務資料庫中的所有頻繁項集，即支持度不低於使用者設定的閾值的項集；再來利用頻繁項集構造出滿足使用者最小信任度的規則。

3. Apriori 範例

假設我們一共有 4 個商品: 商品0, 商品1, 商品2, 商品3。所有可能的情況如下:

如果我們計算所有組合的支持度，也需要計算 15 次。即 \( 2^N — 1 = 2⁴ — 1 = 15 \)。隨著物品的增加，計算的次數呈指數的形式增長。為了降低計算次數和時間，研究人員發現了一種所謂的 Apriori 原理，即某個項集是頻繁的，那麼它的所有子集也是頻繁的。例如，如果 {0, 1} 是頻繁的，那麼 {0}, {1} 也是頻繁的。該原理直觀上沒有什麼幫助，但是如果反過來看就有用了，也就是說如果一個項集是非頻繁項集，那麼它的所有超集也是非頻繁項集，如下圖所示:

在圖中我們可以看到，已知灰色部分 {2,3} 是非頻繁項集，那麼利用上面的知識，我們就可以知道 {0,2,3} {1,2,3} {0,1,2,3} 都是非頻繁的。也就是說，計算出 {2,3} 的支持度，知道它是非頻繁的之後，就不需要再計算 {0,2,3} {1,2,3} {0,1,2,3} 的支持度，因為我們知道這些集合不會滿足我們的要求。使用該原理就可以避免項集數目的指數增長，從而在合理的時間內計算出頻繁項集。

4. Apriori 演算法優缺點

優點：易編碼實現
缺點：在大資料集上可能較慢
適用資料型別：數值型或者標稱型資料。

5. Apriori 演算法流程步驟：

收集資料：使用任意方法。
準備資料：任何資料型別都可以，因為我們只儲存集合。
分析資料：使用任意方法。
訓練資料：使用Apiori演算法來找到頻繁項集。
測試演算法：不需要測試過程。
使用演算法：用於發現頻繁項集以及物品之間的關聯規則。

6. Python 程式法

有使用到套件來處理這個演算法，所以記得先去安裝apyori套件

pip install apyori

再來data的變數裡面，是存放你自己想分析的list組合，看你自己怎麼編排。

最後是要設定你的條件min_support, min_confidence, min_lift

不知道這三個是什麼的朋友，先往上看有介紹前面二個

Lift這個參數越大，代表塞選出來得二個元素相關性越大，大於1才有意義，所以在這邊初始值從2開始。

from apyori import apriori

data = [['r', 'z', 'h', 'j', 'p'],
       ['z', 'y', 'x', 'w', 'v', 'u', 't', 's'],
       ['z'],
       ['r', 'x', 'n', 'o', 's'],
       ['y', 'r', 'x', 'z', 'q', 't', 'p'],
       ['y', 'z', 'x', 'e', 'q', 's', 't', 'm']]

association_rules = apriori(data, min_support=0.16, min_confidence=0.2, min_lift=3, max_length=2) 
association_results = list(association_rules)

for item in association_results:
   pair = item[0] 
   items = [x for x in pair]
   print("Rule: " + items[0] + " -> " + items[1])
   print("Support: " + str(item[1]))
   print("Confidence: " + str(item[2][0][2]))
   print("Lift: " + str(item[2][0][3]))
   print("=====================================")

手把手程式實作分享系列：先驗演算法（Apriori Algorithm） 關聯規則分析