Association mining asks which items appear together more often than expected. A rule such as coffee -> milk is not useful merely because its confidence is high: milk may be common in almost every basket.
| Measure | Question |
|---|---|
| Support | How often does the complete itemset occur? |
| Confidence | Among baskets with the left side, how many contain the right side? |
| Lift | How much more often do both occur than independence predicts? |
Lift above 1 signals positive association; it does not prove causality or business value.
Apriori: prune with downward closure
If an itemset is frequent, every subset must also be frequent. Conversely, an infrequent subset means every superset containing it is infrequent. Apriori uses that fact to generate candidates level by level and remove impossible branches before counting them.
Its weakness is repeated database scans and candidate explosion when transactions are wide or the support threshold is low.
FP-Growth: compress repeated prefixes
FP-Growth scans to count frequent items, orders them consistently, and inserts transactions into an FP-tree. Shared prefixes reuse nodes. Mining conditional pattern bases then finds frequent itemsets without explicitly generating every candidate.
The tree is not magic compression: if transactions share little structure, it can remain large. The choice depends on sparsity, support threshold, memory, and whether incremental updates matter.
In plain terms: Apriori asks “which combinations are still possible?” FP-Growth asks “which transaction prefixes can share storage?”
Before shipping rules, filter trivial consequents, validate on a later time window, and estimate the cost of acting on a false association. A statistically frequent pattern can still be operationally useless.
Review card
- Support controls prevalence; confidence is conditional frequency.
- Lift corrects for a popular consequent.
- Apriori prunes candidates with subset monotonicity.
- FP-Growth trades candidate generation for a compressed tree.
- Association is a hypothesis generator, not a causal claim.
Association mining 想找的是「哪些 item 比預期更常一起出現」。coffee -> milk 的 confidence 很高，不代表 rule 有用，因為 milk 可能本來就出現在幾乎所有 basket。
| 指標 | 問題 |
|---|---|
| Support | 完整 itemset 出現多常？ |
| Confidence | 有左側的 basket 中，多少也有右側？ |
| Lift | 兩者共同出現，比 independent assumption 高多少？ |
Lift 大於 1 代表 positive association，但不等於 causality，也不保證有商業價值。
Apriori：用 downward closure 剪枝
若 itemset 是 frequent，它的每個 subset 必然 frequent。反過來，只要 subset 不 frequent，包含它的 superset 全都可以刪掉。Apriori 逐層產生 candidate，在真正 counting 前先剪掉不可能的 branch。
它的弱點是 repeated database scan；transaction 很寬或 support threshold 很低時，candidate 數量也可能爆炸。
FP-Growth：壓縮重複 prefix
FP-Growth 先計算 frequent item、建立固定 order，再把 transaction 插入 FP-tree；共同 prefix 共用 node。之後透過 conditional pattern base mining，不必明確產生所有 candidate。
Tree 不是保證有效的魔法壓縮：transaction 結構若很少重複，它仍可能很大。選擇要看 sparsity、support threshold、memory 與 incremental update 需求。
白話來說： Apriori 問「哪些組合還有可能？」；FP-Growth 問「哪些 transaction prefix 可以共用儲存？」
真正上線前，還要排除 trivial consequent、用之後的 time window 驗證，並估計對 false association 採取行動的成本。統計上頻繁的 pattern，營運上可能完全沒用。
複習卡
- Support 看普遍程度；confidence 是 conditional frequency。
- Lift 修正 consequent 本身很熱門的問題。
- Apriori 以 subset monotonicity 剪 candidate。
- FP-Growth 用 compressed tree 取代大量 candidate generation。
- Association 是 hypothesis generator，不是因果證明。