先驗算法

在計算機科學以及數據挖掘領域中， 先驗算法（Apriori Algorithm）是關聯規則學習的經典算法之一。先驗算法的設計目的是為了處理包含交易信息內容的數據庫（例如,顧客購買的商品清單，或者網頁常訪清單。）而其他的算法則是設計用來尋找無交易信息（如Winepi算法和Minepi算法）或無時間標記（如DNA測序）的數據之間的聯繫規則。

在關聯式規則中,一般對於給定的項目集合（例如，零售交易集合，每個集合都列出的單個商品的購買信息），算法通常嘗試在項目集合中找出至少有C個相同的子集。先驗算法採用自底向上的處理方法，即頻繁子集每次只擴展一個對象（該步驟被稱為候選集產生），並且候選集由數據進行檢驗。當不再產生符合條件的擴展對象時，算法終止。

先驗算法採用廣度優先搜索算法進行搜索並採用樹結構來對候選項目集進行高效計數。它通過長度為$k-1$的候選項目集來產生長度為$k$的候選項目集，然後從中刪除包含不常見子模式的候選項。根據向下封閉性引理,該候選項目集包含所有長度為$k$的頻繁項目集。之後，就可以通過掃描交易數據庫來決定候選項目集中的頻繁項目集。

雖然先驗算法具有顯著的歷史地位，但是其中的一些低效與權衡弊端也進而引致了許多其他的算法的產生。候選集產生過程生成了大量的子集（先驗算法在每次對數據庫進行掃描之前總是嘗試加載儘可能多的候選集）。並且自底而上的子集瀏覽過程（本質上為寬度優先的子集格遍歷）也直到遍歷完所有 $2^{|S|}-1$ 個可能的子集之後才尋找任意最大子集S。

例子

一個大型超級市場根據最小存貨單位（SKU）來追蹤每件物品的銷售數據。從而也可以得知哪些物品通常被同時購買。通過採用先驗算法來從這些銷售數據中建立頻繁購買商品組合的清單是一個效率適中的方法。假設交易數據庫包含以下子集{1,2,3,4}，{1,2}，{2,3,4}，{2,3}，{1,2,4}，{3,4}，{2,4}。每個標號表示一種商品，如「奶油」或「麵包」。先驗算法首先要分別計算單個商品的購買頻率。下表解釋了先驗算法得出的單個商品購買頻率。

商品編號	購買次數
1	3
2	6
3	4
4	5

然後我們可以定義一個最少購買次數來定義所謂的「頻繁」。在這個例子中，我們定義最少的購買次數為3。因此，所有的購買都為頻繁購買。接下來，就要生成頻繁購買商品的組合及購買頻率。先驗算法通過修改樹結構中的所有可能子集來進行這一步驟。然後我們僅重新選擇頻繁購買的商品組合：

商品編號	購買次數
{1,2}	3
{2,3}	3
{2,4}	4
{3,4}	3

並且生成一個包含3件商品的頻繁組合列表（通過將頻繁購買商品組合與頻繁購買的單件商品聯繫起來得出）。在上述例子中，不存在包含3件商品組合的頻繁組合。最常見的3件商品組合為{1,2,4}和{2,3,4}，但是他們的購買次數為2，低於我們設定的最低購買次數。

算法的局限

因此Apriori算法中的一些低效與權衡弊端也進而引致了許多其他的算法的產生，例如FP-growth算法。候選集產生過程生成了大量的子集（先驗算法在每次對數據庫進行掃描之前總是嘗試加載儘可能多的候選集）。並且自底而上的子集瀏覽過程（本質上為寬度優先的子集格遍歷）也直到遍歷完所有 $2^{|S|}-1$ 個可能的子集之後才尋找任意最大子集S。