在計算機科學以及數據挖掘領域中， 先驗算法是關聯式規則中的經典算法之一。
基本介紹
- 中文名：先驗算法
- 外文名：Apriori algorithm
- 類型：計算機用語
- 定義：關聯式規則中的經典算法之一
簡介,算法圖例說明,例子,
簡介
在計算機科學以及數據挖掘領域中， 先驗算法是關聯式規則中的經典算法之一。先驗算法的設計目的是為了處理包含交易信息內容的資料庫（例如,顧客購買的商品清單，或者網頁常訪清單。）而其他的算法則是設計用來尋找無交易信息（如Winepi算法和Minepi算法）或無時間標記（如DNA測序）的數據之間的聯繫規則。
在關聯式規則中,一般對於給定的項目集合（例如，零售交易集合，每個集合都列出的單個商品的購買信息），算法通常嘗試在項目集合中找出至少有C個相同的子集。先驗算法採用自底向上的處理方法，即頻繁子集每次只擴展一個對象（該步驟被稱為候選集產生），並且候選集由數據進行檢驗。當不再產生符合條件的擴展對象時，算法終止。
先驗算法採用廣度優先搜尋算法進行搜尋並採用樹結構來對候選項目集進行高效計數。它通過長度為k− 1的候選項目集來產生長度為k的候選項目集，然後從中刪除包含不常見子模式的候選項。根據向下封閉性引理,該候選項目集包含所有長度為k的頻繁項目集。之後，就可以通過掃描事務資料庫來決定候選項目集中的頻繁項目集。
雖然先驗算法具有顯著的歷史地位，但是其中的一些低效與權衡弊端也進而引致了許多其他的算法的產生。候選集產生過程生成了大量的子集（先驗算法在每次對資料庫進行掃描之前總是嘗試載入儘可能多的候選集）。並且自底而上的子集瀏覽過程（本質上為寬度優先的子集格遍歷）也直到遍歷完所有 個可能的子集之後才尋找任意最大子集S。
算法圖例說明
假設有一個資料庫D，其中有4個事務記錄，分別表示為：
| TID | Items |
|---|---|
T1 | I1,I3,I4 |
T2 | I2,I3,I5 |
T3 | I1,I2,I3,I5 |
T4 | I2,I5 |
這裡預定最小支持度minSupport=2,下面用圖例說明算法運行的過程：
| TID | Items |
|---|---|
T1 | I1,I3,I4 |
T2 | I2,I3,I5 |
T3 | I1,I2,I3,I5 |
T4 | I2,I5 |
掃描D，對每個候選項進行支持度計數得到表C1:
| 項集 | 支持度計數 |
|---|---|
{I1} | 2 |
{I2} | 3 |
{I3} | 3 |
{I4} | 1 |
{I5} | 3 |
比較候選項支持度計數與最小支持度minSupport，產生1維最大項目集L1：
| 項集 | 支持度計數 |
|---|---|
{I1} | 2 |
{I2} | 3 |
{I3} | 3 |
{I5} | 3 |
由L1產生候選項集C2：
| 項集 |
|---|
{I1,I2} |
{I1,I3} |
{I1,I5} |
{I2,I3} |
{I2,I5} |
{I3,I5} |
掃描D，對每個候選項集進行支持度計數:
| 項集 | 支持度計數 |
|---|---|
{I1,I2} | 1 |
{I1,I3} | 2 |
{I1,I5} | 1 |
{I2,I3} | 2 |
{I2,I5} | 3 |
{I3,I5} | 2 |
比較候選項支持度計數與最小支持度minSupport，產生2維最大項目集L2：
| 項集 | 支持度計數 |
|---|---|
{I1,I3} | 2 |
{I2,I3} | 2 |
{I2,I5} | 3 |
{I3,I5} | 2 |
由L2產生候選項集C3：
| 項集 |
|---|
{I1,I3,I5} |
{l1,l2,l3} |
{I2,I3,I5} |
掃描D，對每個候選項集進行支持度計數:
| 項集 | 支持度計數 |
|---|---|
{I1,I3,I5} | 1 |
{l1,l2,l3} | 1 |
{I2,I3,I5} | 2 |
比較候選項支持度計數與最小支持度minSupport，產生3維最大項目集L3：
| 項集 | 支持度計數 |
|---|---|
{I2,I3,I5} | 2 |
算法終止。
例子
一個大型超級市場根據最小存貨單位（SKU）來追蹤每件物品的銷售數據。從而也可以得知哪裡物品通常被同時購買。通過採用先驗算法來從這些銷售數據中建立頻繁購買商品組合的清單是一個效率適中的方法。假設事務資料庫包含以下子集{1,2,3,4}，{1,2}，{2,3,4}，{2,3}，{1,2,4}，{3,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，低於我們設定的最低購買次數。
