COM6004 Data Mining · Chapter 6

Association Analysis: Association Rule Mining

COM6004 · Chapter 6 · Source: COM6004_Chapter_6_Association_Rules.pptx（95 slides）· Tan, Steinbach, Karpatne, Kumar, Introduction to Data Mining 2nd ed.

Contents · 19 sections

🎯 本講重點 (Learning outcomes)

定義：itemset、k-itemset、support count $\sigma$ 、support $s$ 、frequent itemset、association rule $X \rightarrow Y$ 、confidence $c$ 。
Brute-force 點解唔得： $2^d$ 個 itemsets、 $3^d - 2^{d+1} + 1$ 條 rules；改用 two-step approach（frequent itemset generation → rule generation）。
Apriori principle（anti-monotone property of support）、Apriori algorithm、candidate generation（ $F_{k-1} \times F_{k-1}$ ）、candidate pruning、support counting（hash tree）。
Rule generation： $2^k - 2$ 條 candidate rules；confidence 對 RHS item 數目係 anti-monotone。
Compact representation：maximal frequent itemset vs closed itemset。
Pattern evaluation：contingency table、confidence 嘅缺點、lift / interest、PS、φ-coefficient；measures 嘅 properties（symmetry、scaling、inversion、null addition）；Simpson's paradox。

⭐ 考試必溫 Top-5

由 transaction table 計 support 同 confidence： $s(X \rightarrow Y) = \frac{\sigma(X \cup Y)}{|T|}$ ， $c(X \rightarrow Y) = \frac{\sigma(X \cup Y)}{\sigma(X)}$ 。
Apriori principle：frequent itemset 嘅所有 subsets 都 frequent ⇔ infrequent itemset 嘅所有 supersets 都 infrequent；識行 Apriori（minsup = 3 嘅 Bread/Milk/Diaper 例子，6 + 6 + 1 = 13）。
$F_{k-1} \times F_{k-1}$ merge（頭 $k-2$ 個 items 相同）＋ candidate pruning（任何一個 $(k-1)$ -subset infrequent 就刪）。
Maximal vs closed：識喺 transaction grid 搵出 frequent / maximal / closed itemsets；Maximal ⊆ Closed ⊆ Frequent。
Lift / Interest $= \frac{P(X, Y)}{P(X)P(Y)}$ ：> 1 正相關、= 1 independent、< 1 負相關（Tea → Coffee：0.9375）；Simpson's paradox（hospital / county 例子）。

1. Association Rule Mining：問題定義

Given a set of transactions, find rules that will predict the occurrence of an item based on the occurrences of other items in the transaction。經典應用係 market-basket analysis：超市收銀紀錄入面，買咗某啲貨品嘅人仲會買乜。

成章用嘅 market-basket transactions（slide 4，由 slide 圖片 EMF 內嘅文字還原）：

TID	Items
1	Bread, Milk
2	Bread, Diaper, Beer, Eggs
3	Milk, Diaper, Beer, Coke
4	Bread, Milk, Diaper, Beer
5	Bread, Milk, Diaper, Coke

⚠️ 易混淆

Association rule 代表 co-occurrence，唔代表 causality。{Diaper} → {Beer} 只話「買尿片嘅交易通常都有啤酒」，唔係話買尿片導致買啤酒。

2. Definitions：Itemset、Support、Association Rule

⭐ 考試重點：定義

Itemset：A collection of one or more items，例如 {Milk, Bread, Diaper}。
k-itemset：An itemset that contains k items。
Support count $\sigma$ ：itemset 出現嘅次數（frequency of occurrence），例如 $\sigma(\{\text{Milk, Bread, Diaper}\}) = 2$ （TID 4、5）。
Support $s$ ：含該 itemset 嘅 transactions 嘅比例，例如 $s(\{\text{Milk, Bread, Diaper}\}) = 2/5$ 。
Frequent itemset：support ≥ minsup threshold 嘅 itemset。
Association rule：形式為 $X \rightarrow Y$ 嘅 implication expression， $X$ 、 $Y$ 係 itemsets（而且 $X \cap Y = \emptyset$ ），例如 {Milk, Diaper} → {Beer}。

Rule evaluation metrics：

s(X \rightarrow Y) = \frac{\sigma(X \cup Y)}{|T|} \qquad c(X \rightarrow Y) = \frac{\sigma(X \cup Y)}{\sigma(X)}

Support (s)：Fraction of transactions that contain both X and Y。
Confidence (c)：Measures how often items in Y appear in transactions that contain X。

例子：{Milk, Diaper} → {Beer}： $s = \frac{\sigma(\{\text{Milk, Diaper, Beer}\})}{5} = \frac{2}{5} = 0.4$ ， $c = \frac{\sigma(\{\text{Milk, Diaper, Beer}\})}{\sigma(\{\text{Milk, Diaper}\})} = \frac{2}{3} = 0.67$ 。

💡 直覺理解

Support 答「呢個組合有幾常見」（太少見嘅 rule 可能只係巧合，亦冇商業價值）；confidence 答「已知有 X，有 Y 嘅條件機率」，即 $P(Y \mid X)$ 。

3. Mining Task 與 Computational Complexity

Given a set of transactions T，association rule mining 嘅目標係搵出所有：support ≥ minsup threshold 同 confidence ≥ minconf threshold 嘅 rules。

Brute-force approach：列出所有可能 rules → 計每條嘅 support 同 confidence → prune 走唔過 minsup / minconf 嘅 → Computationally prohibitive!

⭐ 考試重點：Complexity 公式

Given $d$ unique items：

Total number of itemsets $= 2^d$
Total number of possible association rules：

R = \sum_{k=1}^{d-1} \left[ \binom{d}{k} \times \sum_{j=1}^{d-k} \binom{d-k}{j} \right] = 3^d - 2^{d+1} + 1

If $d = 6$ ： $R = 3^6 - 2^7 + 1 = 729 - 128 + 1 = 602$ rules。

💡 點解係

3^d

？

每個 item 有 3 個選擇：放 LHS、放 RHS、或者唔用 → $3^d$ 。再減走 LHS 空（ $2^d$ 種）同 RHS 空（ $2^d$ 種），兩邊都空嗰種被減咗兩次，加返 1： $3^d - 2 \cdot 2^d + 1$ 。Slide 8 個圖顯示 $d$ 由 2 到 10，rules 數目以指數增長（ $d = 10$ 已接近 57,000）。

Mining Association Rules：觀察

由 itemset {Milk, Diaper, Beer} 產生嘅 rules：

Rule	s	c
{Milk, Diaper} → {Beer}	0.4	0.67
{Milk, Beer} → {Diaper}	0.4	1.0
{Diaper, Beer} → {Milk}	0.4	0.67
{Beer} → {Milk, Diaper}	0.4	0.67
{Diaper} → {Milk, Beer}	0.4	0.5
{Milk} → {Diaper, Beer}	0.4	0.5

⭐ 考試重點：Observations

以上全部係同一個 itemset {Milk, Diaper, Beer} 嘅 binary partitions。
同一個 itemset 產生嘅 rules support 一樣，但 confidence 可以唔同（分母 $\sigma(X)$ 唔同）。
所以可以 decouple support 同 confidence 嘅要求 → Two-step approach：
1. Frequent Itemset Generation：搵出所有 support ≥ minsup 嘅 itemsets。
2. Rule Generation：由每個 frequent itemset 產生 high confidence rules，每條 rule 係 frequent itemset 嘅一個 binary partitioning。
Frequent itemset generation 仍然 computationally expensive。

4. Frequent Itemset Generation

Given $d$ items，有 $2^d$ 個 possible candidate itemsets（slide 11 嘅 itemset lattice：由 null 到 A…E、AB…DE、一直到 ABCDE，5 個 items 共 32 個 nodes）。

Brute-force approach：lattice 入面每個 itemset 都係 candidate frequent itemset；scan database 計每個 candidate 嘅 support，每個 transaction 要同每個 candidate match。

\text{Complexity} \sim O(NMw)

$N$ = number of transactions， $M$ = number of candidates， $w$ = maximum transaction width。Expensive since $M = 2^d$ !!!

⭐ 考試重點：Frequent itemset generation strategies

Reduce…	做法
Number of candidates ( $M$ )	Complete search： $M = 2^d$ ；用 pruning techniques 減少 $M$ （Apriori）
Number of transactions ( $N$ )	Itemset size 增加時減少 $N$ ；DHP 同 vertical-based mining algorithms 用
Number of comparisons ( $NM$ )	用 efficient data structures 儲 candidates 或 transactions，唔使每個 candidate 同每個 transaction 都 match（hash tree）

5. Apriori Principle

⭐ 考試重點

Apriori principle：If an itemset is frequent, then all of its subsets must also be frequent。

成立原因：support measure 有以下 property——Support of an itemset never exceeds the support of its subsets。即：

\forall X, Y : (X \subseteq Y) \Rightarrow s(X) \geq s(Y)

呢個叫 support 嘅 anti-monotone property。

💡 直覺理解：反過嚟用先有用

Contrapositive：如果一個 itemset infrequent，佢所有 supersets 都一定 infrequent。所以喺 lattice 一發現 {A,B} infrequent，所有含 A、B 嘅 itemsets（ABC、ABD、…、ABCDE）全部可以 prune 走，唔使計（slide 15：「Found to be Infrequent → Pruned supersets」）。

Illustrating Apriori Principle（minsup = 3）

Items (1-itemsets) count（用 Section 1 嘅 5 transactions）：

Item	Count
Bread	4
Coke	2 ✗
Milk	4
Beer	3
Diaper	4
Eggs	1 ✗

Coke 同 Eggs infrequent → No need to generate candidates involving Coke or Eggs。Pairs (2-itemsets)：只由 4 個 frequent items 組合， $\binom{4}{2} = 6$ 個：

Itemset	Count
{Bread, Milk}	3
{Bread, Beer}	2 ✗
{Bread, Diaper}	3
{Milk, Beer}	2 ✗
{Milk, Diaper}	3
{Beer, Diaper}	3

Triplets (3-itemsets)：slide 21 列出 4 個 candidates：{Beer, Diaper, Milk} 2、{Beer, Bread, Diaper} 2、{Bread, Diaper, Milk} 2、{Beer, Bread, Milk} 1——全部 < 3，冇 frequent 3-itemset。

⭐ 考試重點：數 candidates

If every subset is considered： $\binom{6}{1} + \binom{6}{2} + \binom{6}{3} = 6 + 15 + 20 = 41$
With support-based pruning： $6 + 6 + 4 = 16$ （slide 16–21）
再用 Apriori 嘅 candidate pruning（任何 2-subset infrequent 就刪）： $6 + 6 + 1 = 13$ （slide 22）——4 個 triplets 之中，只有 {Bread, Diaper, Milk} 嘅三個 pairs 全部 frequent；其餘三個都含 {Bread, Beer} 或 {Milk, Beer}。

6. Apriori Algorithm

⭐ 考試重點：Algorithm steps

$F_k$ ：frequent k-itemsets； $L_k$ ：candidate k-itemsets

Let $k = 1$
Generate $F_1$ = {frequent 1-itemsets}
Repeat until $F_k$ $F_{k}$ is empty：
- Candidate Generation：Generate $L_{k+1}$ from $F_k$
- Candidate Pruning：Prune candidate itemsets in $L_{k+1}$ containing subsets of length $k$ that are infrequent
- Support Counting：Count the support of each candidate in $L_{k+1}$ by scanning the DB
- Candidate Elimination：Eliminate candidates in $L_{k+1}$ that are infrequent, leaving only those that are frequent ⇒ $F_{k+1}$

⚠️ 易混淆：Pruning vs Elimination

Candidate pruning 唔使 scan database，只係睇 $F_k$ ：candidate 有某個 k-subset 唔喺 $F_k$ 就刪。Candidate elimination 要 scan database 數 support 之後，先刪 support < minsup 嘅。Pruning 喺 counting 之前做，目的係減少要數嘅 candidates。

Candidate Generation 方法

Brute-force method（slide 24）：由 items 組合所有可能 k-itemsets，再 prune——candidates 太多。
Merge $F_{k-1}$ and $F_1$ itemsets（slide 25）：每個 frequent $(k-1)$ -itemset 加一個 frequent item。

🖼️ Slides 24、25、28 圖片

三張都用同一個超市例子（TID 1 {Bread, Milk}；2 {Beer, Bread, Diaper, Eggs}；3 {Beer, Coke, Diaper, Milk}；4 {Beer, Bread, Diaper, Milk}；5 {Bread, Coke, Diaper, Milk}），目標係產生 candidate 3-itemsets：

Slide 24 Brute-force：6 個 items（Beer, Bread, Cola, Diapers, Eggs, Milk）全部組合，得出 $\binom{6}{3} = 20$ 個 candidates（{Beer, Bread, Cola} … {Diapers, Eggs, Milk}）。Candidate pruning 之後只剩 {Bread, Diapers, Milk}。
Slide 25 $F_{k-1} \times F_1$ ：frequent 2-itemsets {Beer, Diapers}、{Bread, Diapers}、{Bread, Milk}、{Diapers, Milk} 各加一個 frequent item（Beer, Bread, Diapers, Milk），得出 4 個 candidates：{Beer, Bread, Diapers}、{Beer, Diapers, Milk}、{Bread, Diapers, Milk}、{Beer, Bread, Milk}。Pruning 之後同樣只剩 {Bread, Diapers, Milk}。Figure 5.7 註明：some of the candidates are unnecessary because their subsets are infrequent。
Slide 28 $F_{k-1} \times F_{k-1}$ ：兩份同樣嘅 frequent 2-itemsets 互相 merge，只有 {Bread, Diapers} + {Bread, Milk}（第一個 item 相同）可以 merge，一開始就只產生 1 個 candidate {Bread, Diapers, Milk}，pruning 之後仍然保留。

比較：20 個 → 4 個 → 1 個 candidates，方法越聰明，要 prune 同 count 嘅 candidates 越少。

⭐ 考試重點：

F_{k-1} \times F_{k-1}

Method

Merge two frequent $(k-1)$ -itemsets if their first $(k-2)$ items are identical（items 要按 lexicographic order 排好）。

$F_3$ = {ABC, ABD, ABE, ACD, BCD, BDE, CDE}

Merge(ABC, ABD) = ABCD
Merge(ABC, ABE) = ABCE
Merge(ABD, ABE) = ABDE
Do not merge(ABD, ACD) because they share only prefix of length 1 instead of length 2

Candidate pruning： $L_4$ = {ABCD, ABCE, ABDE}

Prune ABCE because ACE and BCE are infrequent
Prune ABDE because ADE is infrequent
After candidate pruning： $L_4$ = {ABCD}（ABCD 嘅 subsets ABC、ABD、ACD、BCD 全部喺 $F_3$ ）

回到超市例子（slide 29）：frequent pairs 按字母排係 {Beer, Diaper}、{Bread, Diaper}、{Bread, Milk}、{Diaper, Milk}。只有 {Bread, Diaper} 同 {Bread, Milk} 嘅第一個 item 相同 → 只產生一個 3-itemset {Bread, Diaper, Milk}，support count = 2 < 3，喺 support counting 之後被 eliminate。所以 $6 + 6 + 1 = 13$ 。

Alternate $F_{k-1} \times F_{k-1}$ Method

Merge two frequent $(k-1)$ -itemsets if the last $(k-2)$ items of the first one is identical to the first $(k-2)$ items of the second。

$F_3$ = {ABC, ABD, ABE, ACD, BCD, BDE, CDE}

Merge(ABC, BCD) = ABCD
Merge(ABD, BDE) = ABDE
Merge(ACD, CDE) = ACDE
Merge(BCD, CDE) = BCDE

Candidate pruning： $L_4$ = {ABCD, ABDE, ACDE, BCDE}

Prune ABDE because ADE is infrequent
Prune ACDE because ACE and ADE are infrequent
Prune BCDE because BCE is infrequent
After candidate pruning： $L_4$ = {ABCD}

💡 直覺理解

兩種 merge 方法產生嘅 candidates 唔同（第一種 3 個，alternate 4 個），但經過 candidate pruning 之後結果一樣（{ABCD}）。兩種都 complete（唔會漏 frequent itemset），亦避免重複產生同一個 candidate。

7. Support Counting 與 Hash Tree

Scan database 決定每個 candidate 嘅 support：每個 candidate 都要同每個 transaction match，代價好高。

改善：將 candidate itemsets 儲喺 hash structure，每個 transaction 只同 hashed buckets 入面嘅 candidates match，唔使同每個 candidate 比較。

⭐ 考試重點：Hash tree 例子

15 個 candidate 3-itemsets：{1 4 5}, {1 2 4}, {4 5 7}, {1 2 5}, {4 5 8}, {1 5 9}, {1 3 6}, {2 3 4}, {5 6 7}, {3 4 5}, {3 5 6}, {3 5 7}, {6 8 9}, {3 6 7}, {3 6 8}。

問：transaction (1, 2, 3, 5, 6) support 幾多個 candidates？

需要：

Hash function：1, 4, 7 → 左 branch；2, 5, 8 → 中 branch；3, 6, 9 → 右 branch（即 item mod 3）。Level 1 hash 第 1 個 item，Level 2 hash 第 2 個，Level 3 hash 第 3 個。
Max leaf size：一個 leaf node 最多儲幾多個 itemsets；超過就 split node。

Transaction 嘅 3-subsets（ $\binom{5}{3} = 10$ 個）：123, 125, 126, 135, 136, 156, 235, 236, 256, 356。逐層 enumerate：1 + 2 3 5 6、2 + 3 5 6、3 + 5 6，再分 1 2 + 3 5 6、1 3 + 5 6、1 5 + 6 等，只去對應嘅 leaf。

結果：Match transaction against 11 out of 15 candidates（唔使比較全部 15 個）；當中真正被 support 嘅係 {1 2 5}、{1 3 6}、{3 5 6} = 3 個。

🖼️ Slides 34–41 hash tree 結構

Slide 34 列出 15 個 candidates：{1 4 5}, {1 2 4}, {4 5 7}, {1 2 5}, {4 5 8}, {1 5 9}, {1 3 6}, {2 3 4}, {5 6 7}, {3 4 5}, {3 5 6}, {3 5 7}, {6 8 9}, {3 6 7}, {3 6 8}，問 transaction (1, 2, 3, 5, 6) support 幾多個。下面畫出 Level 1–3 嘅 enumeration，最底一行係全部 10 個 3-subsets。

Slide 41 棵 hash tree（左 = 1,4,7；中 = 2,5,8；右 = 3,6,9）：

Root（hash 第 1 個 item）
├─ 1,4,7 → node（hash 第 2 個 item）
│          ├─ 1,4,7 → leaf {1 4 5}
│          ├─ 2,5,8 → node（hash 第 3 個 item）
│          │          ├─ 1,4,7 → leaf {1 2 4, 4 5 7}
│          │          ├─ 2,5,8 → leaf {1 2 5, 4 5 8}   ✔ 到訪
│          │          └─ 3,6,9 → leaf {1 5 9}          ✔ 到訪
│          └─ 3,6,9 → leaf {1 3 6}                     ✔ 到訪
├─ 2,5,8 → leaf {2 3 4, 5 6 7}                         ✔ 到訪
└─ 3,6,9 → node（hash 第 2 個 item）
           ├─ 1,4,7 → leaf {3 4 5}
           ├─ 2,5,8 → leaf {3 5 6, 3 5 7, 6 8 9}       ✔ 到訪
           └─ 3,6,9 → leaf {3 6 7, 3 6 8}              ✔ 到訪

到訪嘅 6 個 leaves（slide 用紅框標示）共有 1 + 2 + 1 + 2 + 3 + 2 = 11 個 candidates，即 "Match transaction against 11 out of 15 candidates"。佢哋之中真正係 transaction subset 嘅只有 {1 2 5}、{1 3 6}、{3 5 6}，所以答案係 3 個（slide 冇直接寫出呢個數，係由 slide 34 底行嘅 10 個 subsets 對返 candidate list 得出）。

8. Rule Generation

⭐ 考試重點

Given a frequent itemset $L$ ，find all non-empty subsets $f \subset L$ such that $f \rightarrow L - f$ satisfies the minimum confidence requirement。

If {A,B,C,D} is a frequent itemset，candidate rules：

ABC→D, ABD→C, ACD→B, BCD→A,
A→BCD, B→ACD, C→ABD, D→ABC,
AB→CD, AC→BD, AD→BC, BC→AD, BD→AC, CD→AB

If $|L| = k$ ，then there are $2^k - 2$ candidate association rules（ignoring $L \rightarrow \emptyset$ and $\emptyset \rightarrow L$ ）。上例 $2^4 - 2 = 14$ 。

Confidence 嘅 anti-monotone property

一般而言，confidence 冇 anti-monotone property： $c(ABC \rightarrow D)$ 可以大過或者細過 $c(AB \rightarrow D)$ 。
但同一個 itemset 產生嘅 rules，confidence 有 anti-monotone property。例如 {A,B,C,D} 係 frequent 4-itemset：

c(ABC \rightarrow D) \geq c(AB \rightarrow CD) \geq c(A \rightarrow BCD)

Exam Confidence is anti-monotone w.r.t. number of items on the RHS of the rule。

💡 點解？

三條 rule 分子都係 $\sigma(ABCD)$ ；分母分別係 $\sigma(ABC) \leq \sigma(AB) \leq \sigma(A)$ （support anti-monotone）。分母越大，confidence 越細。所以將 items 由 LHS 搬去 RHS，confidence 只會跌或者唔變。

Lattice of rules（slide 44）：頂層係 ABCD⇒{ }，下一層 BCD⇒A、ACD⇒B、ABD⇒C、ABC⇒D，再落係 RHS 有 2 個 items、3 個 items 嘅 rules。如果某條 rule（例如 BCD⇒A）低 confidence，佢下面所有 RHS 包含 A 嘅 rules（CD⇒AB、BD⇒AC、BC⇒AD、D⇒ABC、C⇒ABD、B⇒ACD）都可以 prune。

（Slide 44 嘅圖正正係呢個例子：BCD⇒A 灰色（low confidence），紅色虛線圈住嘅 "Pruned Rules" 就係 CD⇒AB、BD⇒AC、BC⇒AD、D⇒ABC、C⇒ABD、B⇒ACD。）

9. Factors Affecting Complexity of Apriori

⭐ 考試重點

Factor	影響
Choice of minimum support threshold	降低 support threshold → 更多 frequent itemsets；可能增加 candidates 數目同 frequent itemsets 嘅最大長度
Dimensionality (number of items)	要更多 space 儲每個 item 嘅 support count；如果 frequent items 數目亦增加，computation 同 I/O costs 都可能增加
Size of database	Apriori 要 multiple passes，run time 隨 transactions 數目增加
Average transaction width	Denser data sets 嘅 transaction width 增加；可能增加 frequent itemsets 最大長度同 hash tree traversals（transaction 嘅 subsets 數目隨 width 增加）

Impact of support based pruning（slide 46）：同一組 transactions，Minimum Support = 3 時 41 vs 16；改成 Minimum Support = 2，Coke 都變 frequent，if every subset is considered 變成 $\binom{6}{1} + \binom{6}{2} + \binom{6}{3} + \binom{6}{4} = 6 + 15 + 20 + 15 = 56$ 。

Slide 47（textbook Figure 6.13）：support = 0.1%、0.2%、0.5% 三條線；support 越低，candidate 同 frequent itemsets 數目越多（0.1% 時峰值達 $3.5 \times 10^5$ 以上），而且 itemset size 延伸到 15–20。

10. Compact Representation：Maximal Frequent Itemset

有啲 frequent itemsets 係 redundant，因為佢哋嘅 supersets 都 frequent。Slide 48 例子：15 個 transactions，T1–5 有 A1–A10，T6–10 有 B1–B10，T11–15 有 C1–C10；support threshold = 5：

\text{Number of frequent itemsets} = 3 \times \sum_{k=1}^{10} \binom{10}{k} = 3 \times (2^{10} - 1) = 3069

→ Need a compact representation。

⭐ 考試重點：定義

Maximal frequent itemset：An itemset is maximal frequent if it is frequent and none of its immediate supersets is frequent。

喺 lattice 上，maximal itemsets 就喺 frequent / infrequent 之間嘅 border 上面（frequent 嗰邊）。上面 A/B/C 例子嘅 maximal frequent itemsets 係 {A1,…,A10}、{B1,…,B10}、{C1,…,C10}——3 個就代表晒 3069 個。

Illustrative example 1（slide 51–54）

10 transactions × items A–J（由 slide 表格填色還原）：

TID	Items
1	A, C, D, E, F, J
2	C, D, E, F, H
3	C, D, E, F, J
4	E, F
5	F
6	J
7	—
8	J
9–10	—

Support counts：F = 5，E = 4，J = 4，C = D = 3，{E,F} = 4，{C,D,E,F} = 3。

Support threshold (by count)	Frequent itemsets	Maximal itemsets
5	{F}	{F}
4	{E}, {F}, {E,F}, {J}	{E,F}, {J}
3	All subsets of {C,D,E,F} + {J}	{C,D,E,F}, {J}

Another illustrative example（slide 55）

Transactions：T1–T3 = {A,B,C}，T4 = {A,B}，T5 = {A,C}，T7 = {B,C}。所以 A = B = C = 5，{A,B} = {A,C} = {B,C} = 4，{A,B,C} = 3。

Support threshold	Maximal itemsets
5	{A}, {B}, {C}
4	{A,B}, {A,C}, {B,C}
3	{A,B,C}

11. Closed Itemset

⭐ 考試重點：定義

Closed itemset：An itemset X is closed if none of its immediate supersets has the same support as the itemset X。

X is not closed if at least one of its immediate supersets has the same support count as X。

Slide 57 例子：

TID	Items
1	{A,B}
2	{B,C,D}
3	{A,B,C,D}
4	{A,B,D}
5	{A,B,C,D}

Itemset	Support	Itemset	Support
{A}	4	{A,B,C}	2
{B}	5	{A,B,D}	3
{C}	3	{A,C,D}	2
{D}	4	{B,C,D}	2
{A,B}	4	{A,B,C,D}	2
{A,C}	2
{A,D}	3
{B,C}	3
{B,D}	4
{C,D}	3

⚠️ Slide 數字要小心

按上面 transactions 自己數，{B,C,D} 出現喺 T2、T3、T5，support 應該係 3，但 slide 嘅表寫 2。用 support = 3 去判斷：closed itemsets 係 {B}(5)、{A,B}(4)、{B,D}(4)、{A,B,D}(3)、{B,C,D}(3)、{A,B,C,D}(2)。例如 {A} 唔係 closed，因為 {A,B} 同佢一樣係 4；{C} 唔係 closed，因為 {B,C} = 3 = {C}。考試遇到要自己由 transactions 數。

Maximal vs Closed Itemsets（slide 58–59）

Transactions：1 = ABC，2 = ABCD，3 = BCE，4 = ACDE，5 = DE。Lattice 每個 node 旁邊寫住 supporting transaction IDs（例如 A：124；C：1234；ABCDE：not supported by any transactions）。

⭐ 考試重點：Minimum support = 2

# Closed frequent = 9：{C}, {D}, {E}, {A,C}, {B,C}, {C,E}, {D,E}, {A,B,C}, {A,C,D}
# Maximal frequent = 4：{A,B,C}, {A,C,D}, {C,E}, {D,E}（呢 4 個係 closed and maximal）
Closed but not maximal：{C}, {D}, {E}, {A,C}, {B,C}

（列出嘅 itemsets 係按 transactions 計出嚟，同 slide 上嘅 9 / 4 數目吻合；slide 用顏色標示邊個係邊類。）

⭐ 關係

\text{Maximal Frequent Itemsets} \subseteq \text{Closed Frequent Itemsets} \subseteq \text{Frequent Itemsets}

每個 maximal frequent itemset 一定係 closed（如果有 immediate superset 同佢 support 一樣，嗰個 superset 都 frequent，咁佢就唔係 maximal）。反之唔成立。

Maximal：最 compact，可以推返所有 frequent itemsets（所有 subsets），但 失去 support 資訊。
Closed：冇 maximal 咁 compact，但可以推返每個 frequent itemset 嘅 準確 support（= 包含佢嘅 closed itemsets 之中最大嘅 support）。

Slide 60：A/B/C 例子嘅 closed itemsets 亦係 {A1–A10}、{B1–B10}、{C1–C10}——因為 A-block 任何 proper subset 嘅 support 都係 5，同 {A1,…,A10} 一樣，所以唔係 closed。

Closed itemsets examples（slide 61–65）

Example	Transactions	Supports	Closed itemsets
1	T2, T3 = {C,D}；T4 = {C}	{C} 3, {D} 2, {C,D} 2	{C}, {C,D}（{D} 唔係，{C,D} 同佢都係 2）
2	T2, T3 = {C,D,E}；T4 = {C}	{C} 3；其餘全部 2	{C}, {C,D,E}
3	T2, T3 = {C,D,E,F}；T4 = {C,F}	{C} = {F} = {C,F} = 3；{C,D,E,F} = 2	{C,D,E,F}, {C,F}
4	T2, T3 = {C,D,E,F}；T4 = {C}；T5 = {F}	{C} = {F} = 3；{C,F} = 2；{C,D,E,F} = 2	{C,D,E,F}, {C}, {F}

💡 快速判斷 closed 嘅技巧

一個 itemset 係 closed ⇔ 佢就係「所有含佢嘅 transactions 嘅 intersection」。例 3：含 C 嘅 transactions 係 T2、T3、T4，intersection = {C,F}，所以 {C} 唔 closed，{C,F} closed。例 4：含 C 嘅係 T2、T3、T4，intersection = {C}，所以 {C} closed。

Example question（slide 67）

三個 datasets（每個 10,000 transactions，圖中每行約 1,000 個 transactions；深色 = item present），support threshold = 20%（2,000 transactions）：

Data Set A：一半 transactions 有 A–E，另一半有 F–J。
Data Set B：所有 transactions 有 A、B；第 4 行加 D、E；第 6–7 行加 G。
Data Set C：第 1、3 行 {A,B,C}；第 5 行 {B,C,D}；第 7 行 {C,D}；第 9 行 {D,…,J}。

⭐ 參考答案（自己計，slides 冇提供答案）

問題	A	B	C	答案
# frequent itemsets	$2 \times (2^5 - 1) = 62$	7：{A},{B},{G},{A,B},{A,G},{B,G},{A,B,G}	9：{A},{B},{C},{D},{A,B},{A,C},{B,C},{C,D},{A,B,C}	最多：A
Longest frequent itemset	5	3	3	A
Highest maximum support	50%	100%（{A},{B},{A,B}）	40%（{C}）	B
Mixed support（20% 至 > 70%）	—	{A,B,G}：A、B 100%，G 20%	—	B
# maximal frequent	2：{A..E},{F..J}	1：{A,B,G}	2：{A,B,C},{C,D}	A、C 打和
# closed frequent	2	2：{A,B},{A,B,G}	5：{C},{D},{B,C},{C,D},{A,B,C}	C

計算假設每行剛好 1,000 個 transactions（由圖嘅 y-axis 刻度推斷）；D、E 及 E–J 只得 10%，唔 frequent。

12. Pattern Evaluation 與 Contingency Table

Association rule algorithms 會產生大量 rules。
Interestingness measures 可以用嚟 prune / rank patterns。
In the original formulation，support & confidence 係唯一用嘅 measures。

Given $X \rightarrow Y$ 或 {X, Y}，計 interestingness 所需資訊可以由 contingency table 得到：

	$Y$	$\overline{Y}$
$X$	$f_{11}$	$f_{10}$	$f_{1+}$
$\overline{X}$	$f_{01}$	$f_{00}$	$f_{0+}$
	$f_{+1}$	$f_{+0}$	$N$

$f_{11}$ ：support of X and Y； $f_{10}$ ：support of X and $\overline{Y}$ ； $f_{01}$ ：support of $\overline{X}$ and Y； $f_{00}$ ：support of $\overline{X}$ and $\overline{Y}$ 。用嚟定義 support、confidence、Gini、entropy 等 measures。

🔗 跨科連繫

呢個 2×2 contingency table 同 COM6005 Module 3b Chi-square test of independence 用嘅 table 完全一樣；Gini、entropy 就係 COM6004 Chapter 3 decision tree 嘅 impurity measures。

13. Drawback of Confidence

⭐ 考試重點：Tea → Coffee

	Coffee	$\overline{\text{Coffee}}$
Tea	150	50	200
$\overline{\text{Tea}}$	650	150	800
	800	200	1000

Association Rule：Tea → Coffee

Confidence $= P(\text{Coffee} \mid \text{Tea}) = 150/200 = 0.75$ 。Confidence > 50%，即飲茶嘅人飲咖啡多過唔飲咖啡，rule 睇落合理。
但 $P(\text{Coffee}) = 0.8$ ，即係知道一個人飲茶，反而降低佢飲咖啡嘅機率！
注意 $P(\text{Coffee} \mid \overline{\text{Tea}}) = 650/800 = 0.8125$ 。

Tea → Honey（slide 72）：Confidence $= P(\text{Honey} \mid \text{Tea}) = 100/200 = 0.50$ ，好似話飲茶對用唔用蜜糖冇乜影響，rule 睇落 uninteresting。但 $P(\text{Honey}) = 120/1000 = 0.12$ ，所以飲茶嘅人用蜜糖嘅機會其實高好多（Lift = 0.5 / 0.12 ≈ 4.17）。

⭐ 我哋真正想要嘅 rules

Confidence(X → Y) 要夠高：確保買 X 嘅人買 Y 多過唔買 Y。
Confidence(X → Y) > support(Y)：否則 rule 會誤導，因為有 X 其實降低咗同一個 transaction 有 Y 嘅機會。
有冇 measure 捕捉到呢個 constraint？有，好多。

14. Statistical Independence 與 Lift / Interest

條件 confidence(X → Y) = support(Y) 等價於：

P(Y \mid X) = P(Y) \iff P(X, Y) = P(X) \times P(Y) \quad (X \text{ and } Y \text{ are independent})

If $P(X, Y) > P(X) \times P(Y)$ ：X & Y are positively correlated
If $P(X, Y) < P(X) \times P(Y)$ ：X & Y are negatively correlated

⭐ 考試重點：Measures that take into account statistical dependence（slide 75）

\text{Lift} = \frac{P(Y \mid X)}{P(Y)} \qquad \text{Interest} = \frac{P(X, Y)}{P(X)P(Y)}

PS = P(X, Y) - P(X)P(Y)

\phi\text{-coefficient} = \frac{P(X, Y) - P(X)P(Y)}{\sqrt{P(X)[1 - P(X)]\,P(Y)[1 - P(Y)]}}

Lift is used for rules while interest is used for itemsets（兩者數值相同，因為 $\frac{P(Y \mid X)}{P(Y)} = \frac{P(X, Y)}{P(X)P(Y)}$ ）。

Lift = 1：independent；> 1：positively associated；< 1：negatively associated。

例子：Tea → Coffee：Interest $= \frac{0.15}{0.2 \times 0.8} = 0.9375$ （< 1，therefore is negatively associated）。

Lift 嘅問題（slide 77）

Table 1	$Y$	$\overline{Y}$		Table 2	$Y$	$\overline{Y}$
$X$	10	0	10	$X$	90	0	90
$\overline{X}$	0	90	90	$\overline{X}$	0	10	10
	10	90	100		90	10	100

\text{Lift}_1 = \frac{0.1}{(0.1)(0.1)} = 10 \qquad \text{Lift}_2 = \frac{0.9}{(0.9)(0.9)} = 1.11

Table 2 嘅 X 同 Y 有 90% 一齊出現，關係明明更強，但 lift 只得 1.11；Table 1 只有 10% 一齊出現，lift 反而係 10。Lift 對 rare items 偏高。所以單靠 confidence 或 interest 去 prune 都唔夠。

🔗 跨科連繫

Independence $P(X, Y) = P(X)P(Y)$ 、conditional probability $P(Y \mid X)$ 同 COM6005 Module 2 probability 一樣；φ-coefficient 就係兩個 binary variables 嘅 Pearson correlation（COM6005 / COM6004 Chapter 2 correlation）。

15. 唔同 Measures 同佢哋嘅 Properties

文獻提出咗好多 measures（slide 78 列出 21 個：φ-coefficient、Goodman-Kruskal's λ、odds ratio α、Yule's Q、Yule's Y、Kappa κ、Mutual Information、J-Measure、Gini index、Support、Confidence、Laplace、Conviction、Interest、cosine (IS)、Piatetsky-Shapiro's (PS)、Certainty factor、Added Value、Collective strength、Jaccard、Klosgen）。

Comparing different measures（slide 79）：用 10 個 contingency tables（E1–E10）比較唔同 measures 嘅 ranking，排名可以差好遠。例如 E10（ $f_{11} = 61, f_{10} = 2483, f_{01} = 4, f_{00} = 7452$ ）用 Gini index (G) 排第 10，但用 Interest (I) 排第 1。

Property under Variable Permutation（symmetry）

將 contingency table 嘅 A、B 對調（transpose）， $M(A, B) = M(B, A)$ 嗎？

Symmetric measures：support、lift、collective strength、cosine、Jaccard 等
Asymmetric measures：confidence、conviction、Laplace、J-measure 等

💡 用途

Symmetric measures 適合評估 itemsets；asymmetric measures 適合評估 rules（因為 X → Y 同 Y → X 意義唔同，例如 confidence $P(Y \mid X) \neq P(X \mid Y)$ ）。

Property under Row/Column Scaling

Grade-Gender Example (Mosteller, 1968)：

	Male	Female			Male (2x)	Female (3x)
High	30	20	50	High	60	60	120
Low	40	10	50	Low	80	30	110
	70	30	100		140	90	230

Mosteller：Underlying association should be independent of the relative number of male and female students in the samples。Odds-Ratio 有呢個 property：

\alpha = \frac{f_{11} f_{00}}{f_{10} f_{01}} : \quad \frac{30 \times 10}{20 \times 40} = 0.375 = \frac{60 \times 30}{60 \times 80}

Mask / Covid 例子（slide 82）：Covid-Positive column ×2、Covid-Free column ×10：

\frac{20 \times 10}{30 \times 40} = \frac{200}{1200} \approx 0.167 = \frac{40 \times 100}{300 \times 80} = \frac{4000}{24000}

⚠️ Slide 公式

Slide 文字寫 odds ratio 係「 $(f_{11} + f_{00}) / (f_{10} + f_{10})$ 」，似係排版錯誤；標準 odds ratio 係乘積 $\frac{f_{11} f_{00}}{f_{10} f_{01}}$ （slide 78 公式表亦係乘積），上面數字都係用乘積驗證。

Property under Inversion Operation

Inversion：將所有 0/1 對調（item 有 ↔ 冇），即 $f_{11} \leftrightarrow f_{00}$ 、 $f_{10} \leftrightarrow f_{01}$ 。Slide 84 例子：inversion 前後 correlation 都係 −0.1667（不變），但 IS/cosine 由 0.0 變成 0.825（改變）。

φ-coefficient 例子（slide 85）：φ-coefficient is analogous to correlation coefficient for continuous variables。

	$Y$	$\overline{Y}$			$Y$	$\overline{Y}$
$X$	60	10	70	$X$	20	10	30
$\overline{X}$	10	20	30	$\overline{X}$	10	60	70
	70	30	100		30	70	100

\phi_1 = \frac{0.6 - 0.7 \times 0.7}{\sqrt{0.7 \times 0.3 \times 0.7 \times 0.3}} = 0.5238 \qquad \phi_2 = \frac{0.2 - 0.3 \times 0.3}{\sqrt{0.7 \times 0.3 \times 0.7 \times 0.3}} = 0.5238

φ Coefficient is the same for both tables——但直覺上 Table 1（X、Y 60% 一齊出現）嘅關聯應該強過 Table 2（只 20%）。原因：Table 2 就係 Table 1 嘅 inversion，φ 係 inversion-invariant，將「一齊冇」同「一齊有」視為同等證據。對 asymmetric binary data（例如購物籃，大部分 items 都係 0）呢個未必合理。

Property under Null Addition

Null addition：加入大量 X、Y 都冇 嘅 transactions（即只增加 $f_{00}$ ）。

Invariant measures：cosine、Jaccard、All-confidence、confidence
Non-invariant measures：correlation、Interest/Lift、odds ratio 等

💡 直覺理解

超市加多 10,000 張只買咗米嘅單，唔應該改變「啤酒同尿片」之間嘅關聯。Cosine $= \frac{P(A, B)}{\sqrt{P(A)P(B)}}$ 、Jaccard $= \frac{P(A, B)}{P(A) + P(B) - P(A, B)}$ 只用 $f_{11}, f_{10}, f_{01}$ ，所以唔受影響；Lift 分母有 $N$ ，會變。

⭐ 考試重點：Different measures have different properties（slide 87）

Symbol	Measure	Inversion	Null Addition	Scaling
$\phi$	φ-coefficient	Yes	No	No
$\alpha$	odds ratio	Yes	No	Yes
$\kappa$	Cohen's	Yes	No	No
$I$	Interest	No	No	No
$IS$	Cosine	No	Yes	No
$PS$	Piatetsky-Shapiro's	Yes	No	No
$S$	Collective strength	Yes	No	No
$\zeta$	Jaccard	No	Yes	No
$h$	All-confidence	No	No	No
$s$	Support	No	No	No

（Yes = 喺該 operation 下 invariant。）

🖼️ Slides 83、86 圖片

Slide 83 Inversion：(a) 兩個 binary columns A、B，每行係一個 transaction（Transaction 1 至 N），大部分係 0，A 只有頭尾兩個 1，B 只有一個 1；(b) 係 $\bar{A}$ 、 $\bar{B}$ ：每個 0 變 1、1 變 0。Inversion 即係「冇買」同「有買」對調。

Slide 86 Null addition：左表 $A,B = 700$ 、 $A,\bar{B} = 100$ 、 $\bar{A},B = 100$ 、 $\bar{A},\bar{B} = 100$ ，N = 1000；右表將 $\bar{A},\bar{B}$ 加到 1100（即係加 1000 個 A、B 都冇嘅 transactions），N = 2000。（右表 $\bar{A},B$ 格印咗 "10"，但 column total 仍然係 800，應該係 100 嘅 typo。）Slide 86 寫 invariant measures：cosine、Jaccard、All-confidence、confidence；non-invariant：correlation、Interest/Lift、odds ratio。

⚠️ Slide 86 將 All-confidence 列為 null-addition invariant，但 slide 87 個表寫 No，兩頁有出入，請以 lecturer 講法為準。（按定義 $h = s(A,B) / \max(s(A), s(B))$ ，分子分母都唔受 $\bar{A}\bar{B}$ 影響，所以應該係 invariant。）

16. Simpson's Paradox

HDTV / Exercise Machine 例子（slide 88–89）：

Buy HDTV	Exercise Machine: Yes	No	Total
Yes	99	81	180
No	54	66	120
	153	147	300

$c(\{\text{HDTV = Yes}\} \rightarrow \{\text{Exercise Machine = Yes}\}) = 99/180 = 55\%$ ； $c(\{\text{HDTV = No}\} \rightarrow \{\text{Exercise Machine = Yes}\}) = 54/120 = 45\%$ 。⇒ 好似「買 HDTV 嘅客較大機會買 exercise machine」。

但按 customer group 分層（stratify）：

Group	Buy HDTV	EM Yes	EM No	Total	c(→ EM = Yes)
College Students	Yes	1	9	10	1/10 = 10%
College Students	No	4	30	34	4/34 = 11.8%
Working Adult	Yes	98	72	170	98/170 = 57.7%
Working Adult	No	50	36	86	50/86 = 58.1%

喺 每一個 group 入面，買 HDTV 嘅人買 exercise machine 嘅比例反而較低——關係反轉咗！原因：working adults 本身兩樣都較大機會買，而 HDTV 買家大部分係 working adults（170 / 180）。

⭐ 考試重點：Simpson's Paradox

Observed relationship in data may be influenced by the presence of other confounding factors (hidden variables)。
Hidden variables may cause the observed relationship to disappear or reverse its direction!
Proper stratification is needed to avoid generating spurious patterns。

Hospital 例子：Recovery rate from Covid：Hospital A 80%，Hospital B 90%。邊間好啲？分層之後：older population A 50% vs B 30%；younger population A 99% vs B 98%。A 喺兩個年齡組都較好，整體較差只因為 A 收較多（恢復率低嘅）年長病人。

County 例子：Covid-19 death per 100,000：County A 15，County B 10。分層之後：older A 20 vs B 40；younger A 2 vs B 5。A 喺兩組死亡率都較低，整體較高係因為 A 人口較老。

🔗 跨科連繫

Confounding variable 同 COM6005 嘅 regression（加 control variables）同 study design 有關；做 COM6001 pandas 分析時，用 groupby 按 group 分層計比例就係 stratification。

17. Python 示範（自己加，唔喺 slides）

用 Section 1 嘅 5 transactions 驗證 support / confidence / lift（純 Python，唔使額外 library）：

T = [{'Bread','Milk'},
     {'Bread','Diaper','Beer','Eggs'},
     {'Milk','Diaper','Beer','Coke'},
     {'Bread','Milk','Diaper','Beer'},
     {'Bread','Milk','Diaper','Coke'}]

def sigma(itemset):                       # support count
    return sum(1 for t in T if itemset <= t)

def rule(X, Y):
    s = sigma(X | Y) / len(T)             # support
    c = sigma(X | Y) / sigma(X)           # confidence
    lift = c / (sigma(Y) / len(T))
    return round(s, 2), round(c, 2), round(lift, 2)

print(rule({'Milk','Diaper'}, {'Beer'}))  # (0.4, 0.67, 1.11)
print(rule({'Milk','Beer'}, {'Diaper'}))  # (0.4, 1.0, 1.25)

自我測驗 Self-test

Q1. 用 Section 1 嘅 5 transactions，計 {Bread} → {Milk} 嘅 support、confidence 同 lift。

$\sigma(\{\text{Bread, Milk}\}) = 3$ （T1, T4, T5）， $s = 3/5 = 0.6$ ； $\sigma(\{\text{Bread}\}) = 4$ ， $c = 3/4 = 0.75$ ； $P(\text{Milk}) = 4/5 = 0.8$ ，Lift $= 0.75 / 0.8 = 0.9375 < 1$ ，輕微負相關。

Q2.

d = 4

個 items，有幾多個 possible itemsets（包括 null）同 association rules？

Itemsets： $2^4 = 16$ 。Rules： $3^4 - 2^5 + 1 = 81 - 32 + 1 = 50$ 。

Q3. 用自己嘅說話解釋 Apriori principle，同佢點樣減少計算。

如果一個 itemset frequent，佢所有 subsets 都一定 frequent，因為 support 係 anti-monotone： $X \subseteq Y \Rightarrow s(X) \geq s(Y)$ 。反過嚟，一發現某 itemset infrequent，就可以唔產生佢所有 supersets 做 candidates，減少 $M$ 同 database scans。

Q4.

F_2

= {AB, AC, AD, BC, BD, CE}。用

F_{k-1} \times F_{k-1}

產生

L_3

，再做 candidate pruning。

Merge（第一個 item 相同）：AB+AC → ABC；AB+AD → ABD；AC+AD → ACD；BC+BD → BCD。Pruning：ABC 嘅 subsets AB、AC、BC 都喺 $F_2$ ✓；ABD：AB、AD、BD ✓；ACD：CD 唔喺 $F_2$ ✗；BCD：CD ✗。結果 $L_3$ = {ABC, ABD}。

Q5. Frequent itemset {A,B,C} 有幾多條 candidate rules？如果

c(BC \rightarrow A)

低過 minconf，邊啲 rules 可以直接 prune？

$2^3 - 2 = 6$ 條。Confidence 對 RHS 數目 anti-monotone：RHS 包含 A 而且 LHS 係 {B,C} 嘅 subset 嘅 rules—— $B \rightarrow AC$ 同 $C \rightarrow AB$ ——confidence 一定 ≤ $c(BC \rightarrow A)$ ，可以 prune。

Q6. Transactions：1 = ABC，2 = ABCD，3 = BCE，4 = ACDE，5 = DE；minsup = 2。{A,C} 係 closed 嗎？係 maximal 嗎？

$\sigma(\{A, C\}) = 3$ （T1, T2, T4）。Immediate supersets：ABC = 2、ACD = 2、ACE = 1，冇一個係 3 → closed。但 ABC、ACD 都 frequent（≥ 2）→ 唔係 maximal。

Q7. 點解 maximal frequent itemsets 一定係 closed？

假設 X maximal 但唔 closed，即有 immediate superset Y 同 X support 一樣。咁 Y 都 ≥ minsup，係 frequent，同「X 冇 frequent immediate supersets」矛盾。所以 Maximal ⊆ Closed。

Q8. 1000 個客：Tea 200 人，當中 150 人飲 Coffee；全部 Coffee 800 人。Tea → Coffee confidence 0.75 好高，點解呢條 rule 誤導？計 lift。

$P(\text{Coffee}) = 0.8 > 0.75$ ，即 confidence < support(Y)：飲茶反而降低飲咖啡機率。Lift $= \frac{0.15}{0.2 \times 0.8} = 0.9375 < 1$ ，negatively associated。

Q9. 邊啲 measures 喺 null addition 下 invariant？點解對 market-basket data 重要？

Cosine、Jaccard、All-confidence、confidence（按 slide 86）。Market-basket data 大部分 transactions 都唔含某兩件貨， $f_{00}$ 好大而且隨 database 擴大；理想 measure 唔應該因為加入無關 transactions 而改變。

Q10. 解釋 Simpson's paradox，用 hospital 例子說明。

整體數據顯示 B（90%）好過 A（80%），但按年齡分層後，A 喺年長（50% vs 30%）同年輕（99% vs 98%）兩組都較好。年齡係 confounding (hidden) variable：A 收較多恢復率低嘅年長病人，拉低整體比率。所以要 proper stratification。

一頁總結 Cheat sheet

⭐ 考前速記

$\sigma(X)$ = support count； $s(X \rightarrow Y) = \sigma(X \cup Y)/|T|$ ； $c(X \rightarrow Y) = \sigma(X \cup Y)/\sigma(X) = P(Y \mid X)$ 。
Task：搵 support ≥ minsup 同 confidence ≥ minconf 嘅 rules；brute-force prohibitive。
$d$ items： $2^d$ itemsets； $R = 3^d - 2^{d+1} + 1$ rules（ $d = 6$ → 602）。
同一 itemset 嘅 rules：support 一樣，confidence 唔同 → two-step：frequent itemset generation → rule generation。
Brute-force counting $O(NMw)$ ， $M = 2^d$ ；策略：減 $M$ （pruning）、減 $N$ （DHP / vertical）、減 $NM$ （hash tree）。
Apriori principle：frequent ⇒ subsets frequent；support anti-monotone $X \subseteq Y \Rightarrow s(X) \geq s(Y)$ 。
例子 minsup = 3：41（全部）→ 16（support-based）→ 13（ $F_{k-1} \times F_{k-1}$ ）。minsup = 2 → 全部 56。
Apriori： $F_1$ → loop {Candidate Generation $L_{k+1}$ ；Candidate Pruning；Support Counting；Candidate Elimination → $F_{k+1}$ } until empty。
$F_{k-1} \times F_{k-1}$ ：頭 $k-2$ items 相同先 merge；Alternate：第一個嘅尾 $k-2$ = 第二個嘅頭 $k-2$ 。Pruning：任何 $(k-1)$ -subset infrequent 就刪。
Hash tree：hash function（1,4,7 / 2,5,8 / 3,6,9）+ max leaf size；transaction (1,2,3,5,6) 只同 11/15 candidates 比較。
Rule generation： $|L| = k$ → $2^k - 2$ rules；同一 itemset confidence 對 RHS items 數目 anti-monotone： $c(ABC \rightarrow D) \geq c(AB \rightarrow CD) \geq c(A \rightarrow BCD)$ 。
Complexity factors：minsup、dimensionality、database size、average transaction width。
Maximal：frequent 而且冇 immediate superset frequent。Closed：冇 immediate superset 有同樣 support。Maximal ⊆ Closed ⊆ Frequent；closed 保留 support 資訊。
Contingency table $f_{11}, f_{10}, f_{01}, f_{00}$ ；confidence 缺點：Tea → Coffee c = 0.75 < P(Coffee) = 0.8。
Lift $= P(Y \mid X)/P(Y)$ （rules）；Interest $= P(X, Y)/(P(X)P(Y))$ （itemsets）；PS $= P(X, Y) - P(X)P(Y)$ ；φ = correlation for binary。=1 independent，>1 positive，<1 negative。
Lift 對 rare items 偏高（10 vs 1.11）。
Symmetric：support、lift、cosine、Jaccard、collective strength；Asymmetric：confidence、conviction、Laplace、J-measure。
Scaling invariant：odds ratio $f_{11}f_{00}/(f_{10}f_{01})$ 。Inversion invariant：φ、odds ratio、κ、PS、S。Null addition invariant：cosine、Jaccard（+ confidence）。
Simpson's paradox：confounding / hidden variables 令關係消失或反轉 → proper stratification（HDTV、hospital、county 例子）。

Association Analysis: Association Rule Mining

🎯 本講重點 (Learning outcomes)

⭐ 考試必溫 Top-5

1. Association Rule Mining：問題定義

2. Definitions：Itemset、Support、Association Rule

3. Mining Task 與 Computational Complexity

Mining Association Rules：觀察

4. Frequent Itemset Generation

5. Apriori Principle

Illustrating Apriori Principle（minsup = 3）

6. Apriori Algorithm

Candidate Generation 方法

Alternate Fk−1×Fk−1F_{k-1} \times F_{k-1}Fk−1​×Fk−1​ Method

7. Support Counting 與 Hash Tree

8. Rule Generation

Confidence 嘅 anti-monotone property

9. Factors Affecting Complexity of Apriori

10. Compact Representation：Maximal Frequent Itemset

Illustrative example 1（slide 51–54）

Another illustrative example（slide 55）

11. Closed Itemset

Maximal vs Closed Itemsets（slide 58–59）

Closed itemsets examples（slide 61–65）

Example question（slide 67）

12. Pattern Evaluation 與 Contingency Table

13. Drawback of Confidence

14. Statistical Independence 與 Lift / Interest

Lift 嘅問題（slide 77）

15. 唔同 Measures 同佢哋嘅 Properties

Property under Variable Permutation（symmetry）

Property under Row/Column Scaling

Property under Inversion Operation

Property under Null Addition

16. Simpson's Paradox

17. Python 示範（自己加，唔喺 slides）

自我測驗 Self-test

一頁總結 Cheat sheet

Alternate $F_{k-1} \times F_{k-1}$ Method