緒論：從「尿布與啤酒」說起
Apriori 演算法由 R. Agrawal 與 R. Srikant 於 1994 年提出，是關聯規則探勘的基石。經典案例：美國超市發現尿布與啤酒常同時被購買，調整陳列後雙銷量齊升。核心目標：在大量交易資料中發現項目間的共現模式 (頻繁項集)，進而推導關聯規則 (A ⇒ B)。
核心定義與度量指標
| 術語 | 符號 | 定義 |
|---|
| 交易資料庫 | D | 所有交易記錄集合，每筆交易為一項集 |
| 項目集 | I | 所有不同項目的全集 |
| 交易/記錄 | T | 資料庫中單筆記錄，T ∈ D |
| k-項集 | k-itemset | 包含 k 個項目的集合，為某交易的子集 |
| 支持度 | supp(X) | 包含項集 X 的交易數 / 總交易數 = P(X) |
| 信心度 | conf(X→Y) | supp(X∪Y) / supp(X) = P(Y|X)，即買 X 後買 Y 的機率 |
| 候選項集 | Ck | 由頻繁 (k-1)-項集連接產生的潛在 k-項集 |
| 頻繁項集 | Lk | 支持度 ≥ 最小支持度 的項集。頻繁項集的所有子集必須頻繁 (Apriori 性質) |
| 提升度 | lift(X→Y) | conf(X→Y) / supp(Y) = P(X∩Y) / (P(X)P(Y))，>1 表示正相關，<1 負相關，=1 獨立 |
Apriori 核心流程：迭代「連接-剪枝-掃描」
- 掃描 D 計算 1-項集支持度，產生 L1 (頻繁 1-項集)。
- 連接步驟：由 Lk-1 自連接產生候選集 Ck (兩個僅最後一項不同的頻繁項集連接)。
- 剪枝步驟：移除 Ck 中含有非頻繁 (k-1)-子集的項集 (利用 Apriori 性質：頻繁項集的所有子集必須頻繁)。
- 掃描 D 計算 Ck 支持度，保留 ≥ minsup 者形成 Lk。
- 重複 2-4 直到 Ck 為空，演算法終止。所有 Lk 即為完整頻繁項集集合。
兩大效能瓶頸與優化演算法
瓶頸
- 多次掃描資料庫：每輪迭代需完整掃描 D，I/O 成本極高。
- 候選集爆炸：低支持度下候選集數量呈指數增長，記憶體/計算壓力大。
優化一：FP-Tree (Frequent Pattern Tree)
- 僅掃描資料庫 兩次：第一次統計頻繁 1-項集並排序；第二次依排序順序建構壓縮樹結構。
- 樹節點儲存項目與計數，共享前綴路徑，大幅壓縮儲存。
- 採用「條件模式基底 + 遞迴探勘」從樹中直接挖掘頻繁項集，無需產生候選集。
- 適用於記憶體可容納壓縮樹的場景。
優化二：垂直資料格式 (Vertical Data Format)
- 將水平交易表 (TID, Items) 轉置為垂直格式 (Item, TID_Set)。
- 支持度計算簡化為 TID 集合交集大小，利用位元組運算加速。
- 易於平行化與分散式擴展 (如 Eclat 演算法)。
其他平行化策略 (Agrawal & Shafer)
- 計數分發 (CD)：資料分散，候選集廣播，各節點計數後匯總。
- 資料分發 (DD)：候選集與資料同步分散，無廣播成本。
- 候選分發 (CaD)：候選集分散至節點，各節點掃描本地資料計數。
規則產生與篩選
從頻繁項集產生關聯規則：對每個頻繁項集 L，枚舉其非空真子集 S，規則 S ⇒ (L-S) 的信心度 = supp(L)/supp(S)。保留信心度 ≥ minconf 的規則。常結合提升度、杠桿值、集體強度等指標進一步篩選「強規則」。
實務應用建議
- 資料準備：交易資料清洗、項目編碼、稀疏矩陣表示。
- 參數設定：minsup 過高漏發現，過低爆炸；建議從業務可接受的最小模式頻率反推。
- 工具選擇：SQL Server Analysis Services (內建關聯規則)、Python
mlxtend/apyori、R arules、Spark MLlib (FP-Growth)。
- 結果解讀：提升度 > 1 且信心度高者優先；結合領域知識驗證業務意義，避免虛假相關 (如季節性商品同時熱銷)。
總結
Apriori 以「頻繁項集遞迴產生 + 向下封閉性剪枝」奠定關聯規則探勘基礎。雖原始演算法有多次掃描與候選集爆炸缺陷，但 FP-Tree、垂直格式、平行化等後續改進大幅提升實用性。掌握其核心邏輯與度量指標，是進行市場籃分析、推薦系統、異常偵測等應用的關鍵入門。
