關聯規則

在資料探勘的演講或是課程上，講者一定會提到「啤酒尿布」這樣的案例。估且不論這是不是江湖謠傳，這的確是一個經典的資料探勘算法 - 關聯規則（Association rule）。因為常用在商品資料上，所以也被稱為購物籃分析（Basket data analysis）。

關聯規則透過資料間的關係，目標去找出怎樣的組合是比較常出現的。與傳統統計的相關性差異在於關聯法則更重視的是關聯性。

問題定義

關聯規則的目標是找出資料集中很常共同出現的組合。我們會把這樣的組合稱為「頻繁樣式集(Frequent pattern) 」，組合間的關係稱為「關聯（Associations）」。

最後找出來的結果會用下面這個樣子表示：X, Y 分別代表物品的集合，s, c 是作為量化的指標。這個例子的含義是：當購買 X 集合的人，會購買 Y 集合的比率也很高。

X -> Y [s, c]

• s 是 Support 值：代表在所有資料集中， X 與 Y 共同出現的比例。
• c 是 Confidence 值：代表在所有出現 X 在資料集中也出現 Y 的比例。

當兩個指標都很高的話就表示，這樣的組合是很常出現的，而且這樣的關聯是顯著的。

演算法

大部分的關聯法都會採用這兩個主要的步驟：

1. 找出所有頻繁項目集
2. 找出頻繁項目集中具有強關聯規則的規則

通常在第一步會需要大量的空間及時間，因此透過窮舉法的複雜度會是 2 的 n 次。因此發展出更節能的演算是必須的。大部分的演算法都著重在第一步找出所有頻繁項目集的優化。

Apriori Algorithm

Apriori 所採用的性質是：「若一項目集是頻繁的，則他的所有非空子集合也必定是頻繁的。」這句話可以倒過來說：「如果有一個集合不是頻繁的話，則他的母集合也一定不是頻繁的。」

所以這個做法大致上是這樣，從數量低的集合開始做起，當發現這個某個集合不是頻繁的，則他的母集合也不需要考慮。這樣可以大幅縮減計算的複雜度。

簡單來說，可以用「prune and Join」去記憶。先把不可能的集合刪減（prune）吊，再把可能的集合組合（Join）起來

FP-Growth Algorithm

FP-Growth 是另外一種經典的做法，利用 FP-Tree
的資料結構儲存。有興趣的朋友可以再多看看，這邊就不細講。

Reference

1. 挖掘關聯規則(Mining Association Rules) - 聯合大學陳士杰
2. Apriori algorithm in plain English?