關聯規則及Apriori算法Python執行個體

關聯規則學習概述

在大型資料庫中發現變量之間有趣關系的方法，目的是利用一些有趣的度量識别資料庫中的強規則。基于強規則的概念，Rakesh Agrawal等人引入了關聯規則以發現由超市的POS系統記錄的大批交易資料中産品之間的規律性。例如，從銷售資料中發現的規則{薄餅，雞蛋}->{火腿腸}，表明如果顧客一起買薄餅和雞蛋，他們也有可能買火腿腸（這些顧客是想早飯吃手抓餅吧，哈哈），此類資訊可以為大賣場商品組合促銷或電商網站産品推薦等相關商業決策提供依據。除了上述的購物籃分析外，關聯規則還被應用在許多領域中，包括網絡用法挖掘（web usage mining）、入侵檢測、連續生産（continuous production）及生物資訊學中，與序列挖掘（sequence mining）相比，關聯規則學習通常不考慮在事務（transaction）中或事務間項目（item）的順序。

基本概念

I = { I 1 , I 2 , . . . , I m } I =\{I_1, I_2, ..., I_m\} I={I1​,I2​,...,Im​}是項目（item）的集合。給定一個交易資料庫 D = { t 1 , t 2 , . . . , t n } D = \{t_1, t_2, ..., t_n\} D={t1​,t2​,...,tn​}，其中每個事務（transaction） t t t是 I I I的非空子集，即， t ⊆ I t \subseteq I t⊆I，每一個事務都與一個唯一的辨別符TID（transaction ID）對應。

關聯規則是形如 X ⇒ Y X \Rightarrow Y X⇒Y的蘊含式，其中 X , Y ⊆ I X, Y \subseteq I X,Y⊆I且 X ∩ Y = ∅ X \cap Y=\emptyset X∩Y=∅， X X X和 Y Y Y分别稱為關聯規則的先導（antecedent或left-hand-side，LHS）和後繼（consequent或right-hand-side，RHS）。

關聯規則 X ⇒ Y X \Rightarrow Y X⇒Y在 D D D中的支援度（support）是 D D D中包含 X ∪ Y X \cup Y X∪Y的事務所占的比例，即機率 P ( X ∪ Y ) P(X\cup Y) P(X∪Y)。置信度（confidence）是包含 X X X的事務中同時包含 Y Y Y的比例，即條件機率 P ( Y ∣ X ) P(Y|X) P(Y∣X)。如果同時滿足最小支援度門檻值（minimum support）和最小置信度門檻值（minimum confidence），則認為關聯規則是有用的，上述兩個門檻值由使用者或專家根據經驗或者需要設定。

舉例說明概念

表1：關聯規則的簡單例子

TID	網球拍	網球	運動鞋	羽毛球
1	1	1	1
2	1	1
3	1
4	1	1
5	1	1	1
6	1	1

上表是顧客購買記錄的資料庫 D D D，包含6個事務，項集 I = { 網 球 拍 ， 網 球 ， 運 動 鞋 ， 羽 毛 球 } I = \{網球拍，網球，運動鞋，羽毛球\} I={網球拍，網球，運動鞋，羽毛球}，考慮關聯規則 { 網 球 拍 ⇒ 網 球 } \{網球拍 \Rightarrow 網球\} {網球拍⇒網球}，事務 1 , 2 , 3 , 4 , 6 1,2,3,4,6 1,2,3,4,6包含網球拍，事務 1 , 2 , 6 1,2,6 1,2,6同時包含網球拍和網球，

支 持 度 （ s u p p o r t ） = 同 時 包 含 網 球 和 網 球 拍 的 事 務 數 事 務 總 數 = 3 6 = 0.5 支援度（support） = \frac{同時包含網球和網球拍的事務數}{事務總數}=\frac{3}{6}=0.5 支援度（support）=事務總數同時包含網球和網球拍的事務數​=63​=0.5

置 信 度 （ c o n f i d e n c e ） = 同 時 包 含 網 球 和 網 球 拍 的 事 務 數 包 含 網 球 拍 的 事 務 數 = 3 5 = 0.6 置信度（confidence） = \frac{同時包含網球和網球拍的事務數}{包含網球拍的事務數}=\frac{3}{5}=0.6 置信度（confidence）=包含網球拍的事務數同時包含網球和網球拍的事務數​=53​=0.6

如果給定的最小支援度（minimum support） α = 0.5 \alpha = 0.5 α=0.5和最小置信度（minimum confidence） β = 0.5 \beta = 0.5 β=0.5，則關聯規則 { 網 球 拍 ⇒ 網 球 } \{網球拍 \Rightarrow 網球\} {網球拍⇒網球}是有趣的，認為購買網球拍和購買網球之間存在強關聯。

求解算法

常用的自動從事務集中挖掘關聯規則的算法有Apriori 算法和FP-Growth算法。兩個求解算法的原理請自行查找相關資料了解。

Python執行個體

1. Apriori

pip install efficient-apriori

from efficient_apriori import apriori
transactions = [('eggs', 'bacon', 'soup'),
                ('eggs', 'bacon', 'apple'),
                ('soup', 'bacon', 'banana')]
itemsets, rules = apriori(transactions, min_support=0.5, min_confidence=0.5)

print(rules) 
# output: [{eggs} -> {bacon}, {bacon} -> {eggs}, {soup} -> {bacon}, {bacon} -> {soup}]
print(itemsets)
# output: {1: {('soup',): 2, ('bacon',): 3, ('eggs',): 2}, 2: {('bacon', 'eggs'): 2, ('bacon', 'soup'): 2}}
           

2. FP-Growth（該包目前有bug，不建議使用）

pip install fpgrowth_py

from fpgrowth_py import fpgrowth
itemSetList = [['eggs', 'bacon', 'soup'],
                ['eggs', 'bacon', 'apple'],
                ['soup', 'bacon', 'banana']]
freqItemSet, rules = fpgrowth(itemSetList, minSupRatio=0.5, minConf=0.5)
print(rules)
# output: [[{'eggs'}, {'bacon'}, 1.0], [{'bacon'}, {'eggs'}, 0.6666666666666666], [{'soup'}, {'bacon'}, 1.0], [{'bacon'}, {'soup'}, 0.6666666666666666]]
print(freqItemSet)
# output: [{'eggs'}, {'eggs', 'bacon'}, {'soup'}, {'soup', 'bacon'}, {'bacon'}]
           

參考資料

1. 關聯規則學習
2. FP Growth: Frequent Pattern Generation in Data Mining with Python Implementation
3. Efficient-Apriori