# 3.5 Association Rules

## association rule

一個 <font color ="snake">association rule</font> 就是一個 ++implication++，而這個 implication 具有

\begin{equation}
X\rightarrow Y
\end{equation}

的形式。其中：

- ==$X$== 稱作 <font color = "snake">antecedent</font>
- ==$Y$== 稱作 <font color = "snake">consequent</font>

那麼接下來，一個關於 association rule 的例子就是 <font color = "snake">basket analysis</font>，其中我們要去找出 $X,Y$ 兩個物品之間的 dependency。
> 關於 basket analysis 的定義課本沒有明確給出，但它的大意就是要去對一些 data 做分析，跟據這些 data 中的不同東西（如 $X$ 和 $Y$）之間同時發生的情況，來得到它們之間的 correlations。
>
> 例子就如同我們常聽到的「如果有人在超市買了尿布，那麼很有可能這個人也會買啤酒」，類似這樣的事情。


在介紹關於 association rule 前，我們要先介紹三個常用的 measures：
> 除了這三個以外當然還有其他的 measures，但這三個是最常用的（尤其前兩個）

## 3 measures
### 1. support


在這個買東西的例子中，除了我們要去考慮第二點 confidence 來看買兩個東西的關連性之外，我們也希望我們的 support 越大越好。

> $\rightarrow$ 可以先看第二點的定義

即便我們有很高的 confidence，也就是 $P(Y|X) \rightarrow 1$，代表買兩個物品之間有很高的 dependency，但是<font color = "red">如果買 $X,Y$ 的人數非常少，這個 rule 就一點用都沒有</font>。
> 可以想成當我們的樣本數就只有一點點時，即使算起來好像得到什麼關聯性，但是數據太少的情況下根本就不能代表什麼。

因此，support 代表的其實是一種 ++statistical significance++，也就是說我們利用 support 去量化「我們得到的結果到底只是巧合還是真的有某種 rule 在背後」的程度。

### 2. confidence


confidence 也就是我們常在算的 conditional probability。
> $P(Y|X)$ 的意思由後面讀到前面，是「$X$ 發生的情況下，$Y$ 發生的機率」。
>> 因此，分母是「購買 $X$ 的顧客數」

:::warning
如果某個 rule $X\rightarrow Y$ ++holds with enough confidence++，那麼 $P(Y|X)$ 要接近 $1$。
:::

### 3. lift / interest


:::warning
如果 $X,Y$ ++independent++，則 lift 應該要接近 1。
:::

反過來說，如果 $P(Y|X)$ 和 $P(Y)$ 不同，那我們就認為 $X$ 和 $Y$ 之間應該要有某種 dependency。

除此之外，如果：

- lift $>1$，則我們說 $X$ 讓 $Y$ 更有可能發生（$X$ makes $Y$ ++more++ likely）
- lift $<1$，則我們說 $X$ 讓 $Y$ 更不容易發生（$X$ makes $Y$ ++less++ likely）

## generalize of 3 measures

上述這三個 measures 都是對兩個 items $X,Y$，但當然我們也可以 generalize 到大於兩個的 items。

舉例來說，如果我們有一個三個 items 的 set $\{X,Y,Z\}$，那我們也可以去找某個 rule 像是：

\begin{equation}
X,Z \rightarrow Y \qquad \text{i.e.} \ P(Y|X,Z)
\end{equation}
> 兩個指的是同件事，因為根據 confidence 的定義。
>
> $\rightarrow$ 意思也就是 $X,Z$ 發生的情況下，$Y$ 發生的機率。

總結來說，我們有興趣的是去找到所有具有夠高的 support 和 confidence 的 rules。

但是因為一般銷售的 database 通常都會非常大，所以我們希望可以有某種方式能夠只要對這個 database 做少少次的 passes，就能找到這些 rules。

## Apriori

其中一種能夠做到這件事的 algorithm 叫做 <font color = "snake">Apriori</font>，它是由兩個步驟組成：

1. 找出 frequent itemsets
> 即找出那些 support 夠高的物品集合
>> 意義也就是：
>> 找出在所有顧客買的東西的 dataset 裡，那些常常被買的組合有哪些。

2. 先把這些 itemsets 每個分成兩部分，一部分作為 antecedent，另一部分作為 consequent，接著把它們轉換成具有足夠 confidence 的 rules。

兩個步驟分別更詳盡的執行方式為：

### 步驟一

為了要很快地去找出這些 frequent itemsets（也就是不去 enumerate 過所有 items 的 subset），Apriori algorithm 利用一個性質：

:::success
如果某個 itemset $\{X,Y,Z\}$ 是 frequent 的（也就是說有足夠的 support），那麼它所有的 subsets：
\begin{equation}
\{X,Y\}, \ \{Y,Z\}, \ \{X,Z\}
\end{equation}
也會是 frequent 的，並且++加入另一個 item 一定不會增加 support++。
:::
> 這個性質也被稱作 Apriori principle。

也就是說，當我們要檢查具有三個 items 的 itemsets 時，我們只需要檢查那些「所有兩個 item 的 subsets 都是 frequent」的即可。

換句話說：

:::warning
如果我們發現一個只有兩個 item 的 itemset 並非 frequent，那麼所有包含它的 supersets 都可以直接刪掉不用檢查。
:::

Apriori algorithm 的整個概念就是基於下方的想法：

:::warning
如果某個 item （某個 itemset）本身就很少出現在整個 database 裡，那麼它就更不可能會被包含在另個比它更大，且很常出現（support 很高）的 itemset 中。
:::
> 舉例來說：
>
> 如果在一個消費紀錄的 database 裡，我們在找包含兩個 items 的 frequent $2$-item sets。
>
> 假設我們把 frequent 訂為出現兩次，然後在整個 database 裡，香蕉只出現一次。那其實我們就不用再去考慮會不會有某個 2-item set 包含香蕉卻又是 frequent 的，因為不可能發生，不會有某個 2-item set {香蕉、牛奶} 出現十次。

基於上面的概念，Apriori algorithm 在形成 itemsets 時用的是一種 bottom-up 的 approach，先建立 item 數小的 item sets，再慢慢從確定為 frequent 的裡面往上加：

首先我們從找到 frequent 的 one-item sets 開始，然後 inductively 我們從 frequent 的 $k$-item sets 中去產生 candidate 的 $k+1$-item sets，於此同時，要檢查這些 candidate sets 的 subset 是否都為 frequent，否則違反 Apriori principle。
> 講起來有點複雜，可以看下方例子再回來看。

然後再經過一個 pass，掃過整個 database，檢查這些 $k+1$-item sets 是否具有足夠的 support。

為了檢查 support 是否夠高／是否為 frequent（某個或某些 items 的組合是否有常出現到足以被考慮來形成某個 rule），我們會訂定一個 support threshold $C$。

因此：
:::warning
如果我們的 database 是 sparse 的（也就是有很多 item 出現次數都非常少），那我們就可以在最開始的幾個 passes 刪掉很多可能的組合。
:::
> 當然，需要多少 passes 也取決於我們的 support threshold 定多少。

- Apriori algorithm 會把 frequent itemsets 存在一個 hash table 裡，這樣我們就能快速地去 access。

看個例子比較好懂：


紅色數字標記的各個步驟解釋如下：

> 容易出錯的地方是在步驟六我們要形成 $C_3$ 時，要去檢查新建立的 3-item sets 它們的 subset 是否也在 $L_2$ 中。
>> 當然在其他次形成每個 $C_i$ 時也都要這麼做，只是剛好像步驟三時沒有這個問題。

從這個例子我們也可以看出：

:::success
當 $k$ 值（也就是每個 itemset 所含的 item 數）增加時，candidate itemsets 的數量會迅速減少。
:::

除此之外，如果我們最大的 itemset 有 $n$ 個 items，那我們全部就只要做 $n+1$ passes，也就是說我們只需要掃過 database $n+1$ 次。
> 當然這樣還是蠻多的，需要掃過 database 這麼多次一方面大幅增加了 time complexity，另一方面也 assume 了 database 應該要一直待在 memory 裡面。

這個步驟的 pseudocode 如下：

> 大致上的說明都寫在上面了，有需要的話可以放大看。
> 另外，對於這個 algorithm 來說，最重要的部分通常是去 implementt 一個 data structure 來存我們的 candidate set 有哪些，然後記錄它們在 database 裡的出現次數。
>> pseudo code 中的 `count[c]` 就是去 access 這個 data structure 中紀錄出現次數的 field（這個 field 當然初值為 $0$）

### 步驟二

一但我們找到 frequent 的 $k$-item sets，我們就需要先把它們分成兩部分 antecedent 和 consequent，再轉換成 rules。為了轉換成 rules，我們必須計算這些 frequent itemsets 的 confidence。

如同我們在前一個步驟產生 itemsets 的方法：

我們先把一個 item 放在 consequent，剩下 $k-1$ 個 items 放在 antecedent，接著對所有只有單一 item 的 consequents，我們再去檢查這個 rule 是否具有足夠的 confidence，如果沒有就刪除。
> 也就是我們讓一個 itemset 裡的 $k$ 個 items 輪流當 consequent，其他 $k-1$ 個當 antecedent，然後一一檢查每一條的 confidence。

做完這個部分後，我們可能會得到好幾條 rules，每條從同個 itemset 裡各自由不同的 subsets 組成 antecedent 和 consequent。

以上面的例子來說，我們最後得到的 $L_3$ 只有一個 itemset $\{2,3,5\}$，那我們就是分別去計算 $2,3,5$ 分別當 consequent 的 confidence：


接著，我們 inductively 去檢查如果這幾個 rules 裡的 antecedent 移到 consequent，得到的 confidence 是否有達到我們訂的某個標準。


在做這個步驟時，和上面我們在要產生 frequent itemset $C_k$ 時相同，我們不用去產生所有可能的 subset 分割方式。

如果在前面 consequent 只有一個時我們算出來的 confidence 就不足，那這樣的 rules 也不可能組合起來產生 confidence 足夠的 2 consequent rules。
> 舉例來說：
>
> 如果 $\{2,3\} \rightarrow \{5\}$ confidence 就沒有達到要求，那麼 $\{2\} \rightarrow \{3,5\}$ 也不可能會達到。要去檢查 $\{2\} \rightarrow \{3,5\}$ 是否有可能有足夠 confidence 的前提，是
> - $\{2,3\} \rightarrow \{5\}$
> - $\{2,5\} \rightarrow \{3\}$
>
> 都有足夠的 confidence。

至於為什麼要想辦法把越多的 item 移到 consequent，是因為：

:::warning
有更多 item 在 consequent 的 rule 更為 specific 且 useful。
:::
> 當 consequent 越多（antecedent 越少）時，可以想像上面的例子：
> 假設
>
> - $\{2,3\} \rightarrow \{5\}$
> - $\{2\} \rightarrow \{3,5\}$
>
> 皆具足夠的 confidence，而且前面我們就已經確認這個 itemset 足夠 frequent。
> 第一條式子告訴我們如果有人買了 $\{2,3\}$ 這兩個商品，他也很有可能買 $\{5\}$；而第二條告訴我們如果有人買了 $\{2\}$，他就也很有可能買 $\{3,5\}$。
> $\rightarrow$ 相比之下當然是第二條比較有用，因為需要滿足的條件更少，可以得到的結果又更多。

最後，要注意的一點是：

<font color = "red">$X \rightarrow Y$ 並不 imply causality，僅代表 association。</font>
> 也就是說，我們不能由 $X \rightarrow Y$ 就說發生 $X$ 必定會造成 $Y$，我們只能說這兩件事有關聯性。

況且，可能會出有我們根本沒辦法知道它的值的 hidden variables。那麼如果我們有用 hidden variables，好處是我們能更好的去定義 dependency structure。舉例來說：

在 basket analysis 中，假設我們知道買嬰兒食物、尿布、牛奶，之間存在著 dependency，買其中一個的顧客更有可能會買另外兩個，與其像我們上面那樣去在這三者之間去呈現某種 dependency，我們可以去指定某個 ++hidden node++ 叫做「家裡有小嬰兒」當作買這三樣商品的 hidden cause。

:::info
第 14 章會談可以讓我們呈現這種 hidden variables 的 graphical models。
:::

# 參考資料
- wiki: [Apriori algorithm](https://en.wikipedia.org/wiki/Apriori_algorithm)
> 步驟一的 pseudo code 來源
- stackechange: [Using apriori algorithm for market basket analysis](https://stats.stackexchange.com/questions/351669/using-apriori-algorithm-for-market-basket-analysis)
> 步驟一例子的圖出處，在這個頁面的回答中有附上圖的原始出處，是一個大學的課堂 ppt，也有 pseudo code 和一些解釋可以參考。
- geekforgeeks: [Apriori Algorithm](https://www.geeksforgeeks.org/apriori-algorithm/)
> 有很詳盡的例子與每個步驟的解說。