iT邦幫忙

2017 iT 邦幫忙鐵人賽
DAY 23
2

關聯規則

在資料探勘的演講或是課程上,講者一定會提到「啤酒尿布」這樣的案例。估且不論這是不是江湖謠傳,這的確是一個經典的資料探勘算法 - 關聯規則(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?

上一篇
淺談資料探勘
下一篇
資料探勘演算法 - 分類法
系列文
從學生到職場:菜鳥資料科學家的第一個月30

尚未有邦友留言

立即登入留言