IBM 的 Apriori 如何透過剪除不可能的候選項來挖掘購物者共同購買的商品

零售商想知道哪些產品會被一起購買，但隨著 SKU 數量增加，可能的商品組合數量呈指數爆炸。

Apriori 於 1994 年發表，利用一項性質：任何非頻繁項目集的超集本身必定也是非頻繁的。它先計算單一項目，保留頻繁者，將其擴展為成對項目，然後重複此過程，因此絕不會去計算父集合已經失敗的候選項。

這個技巧將一個很快變得難以處理的搜尋，轉化為只觸及頻繁集合這一小片前沿的搜尋。它讓購物籃分析成為實用的資料庫查詢。

若一個集合很罕見，它的每個超集也同樣罕見

向下封閉性在搜尋擴展之前就先行剪枝，因此執行時間取決於頻繁集合，而非所有集合。

每一層進行一次資料庫掃描，使記憶體佔用受限於候選集合。

它給出精確的頻繁集合，而非啟發式方法或抽樣近似。

同樣的剪枝可推廣到購物籃之外的序列與模式挖掘。

在搜尋龐大空間之前，先尋找一種單調性質，讓你能一次捨棄整個分支。一條能排除某個區域的規則，可將搜尋從指數級縮減為線性級。

Apriori 成為關聯規則的典範演算法，也是資料探勘的標準教材。它催生了支撐推薦、品類配置與交叉銷售分析的領域，以及後來減少其掃描次數的 fpgrowth 等方法。