理論介紹
維基百科
在計算機科學以及數據挖掘領域中，先驗算法（Apriori Algorithm）是關聯規則學習的經典算法之一。先驗算法的設計目的是為了處理包含交易信息內容的資料庫（例如,顧客購買的商品清單，或者網頁常訪清單。）而其他的算法則是設計用來尋找無交易信息（如Winepi算法和Minepi算法）或無時間標記（如DNA測序）的數據之間的聯繫規則。
先驗算法採用廣度優先搜索算法進行搜索並採用樹結構來對候選項目集進行高效計數。它通過長度為k−1k−1的候選項目集來產生長度為 k 的候選項目集，然後從中刪除包含不常見子模式的候選項。根據向下封閉性引理,該候選項目集包含所有長度為 k 的頻繁項目集。之後，就可以通過掃描交易資料庫來決定候選項目集中的頻繁項目集。
數據挖掘十大算法
Apriori 算法是一種最有影響力的挖掘布爾關聯規則的頻繁項集算法，它是由Rakesh Agrawal 和RamakrishnanSkrikant 提出的。它使用一種稱作逐層搜索的迭代方法，k- 項集用於探索（k+1）- 項集。首先，找出頻繁 1- 項集的集合。該集合記作L1。L1 用於找頻繁2- 項集的集合 L2，而L2 用於找L3，如此下去，直到不能找到 k- 項集。每找一個 Lk 需要一次資料庫掃描。為提高頻繁項集逐層產生的效率，一種稱作Apriori 性質用於壓縮搜索空間。其約束條件：一是頻繁項集的所有非空子集都必須也是頻繁的，二是非頻繁項集的所有父集都是非頻繁的。
2 基本概念
關聯分析
關聯分析是一種在大規模數據集中尋找相互關係的任務。 這些關係可以有兩種形式:
相關術語
交易號碼商品0豆奶，萵苣1萵苣，尿布，葡萄酒，甜菜2豆奶，尿布，葡萄酒，橙汁3萵苣，豆奶，尿布，葡萄酒4萵苣，豆奶，尿布，橙汁頻繁項集: {葡萄酒, 尿布, 豆奶} 就是一個頻繁項集的例子。
關聯規則: 尿布 -> 葡萄酒 就是一個關聯規則。這意味著如果顧客買了尿布，那麼他很可能會買葡萄酒。
支持度: 數據集中包含該項集的記錄所佔的比例。例如上圖中，{豆奶} 的支持度為 4/5。{豆奶, 尿布} 的支持度為 3/5。
可信度: 針對一條諸如 {尿布} -> {葡萄酒} 這樣具體的關聯規則來定義的。這條規則的 可信度 被定義為 支持度({尿布, 葡萄酒})/支持度({尿布})，支持度({尿布, 葡萄酒}) = 3/5，支持度({尿布}) = 4/5，所以 {尿布} -> {葡萄酒} 的可信度 = 3/5 / 4/5 = 3/4 = 0.75。
支持度 和 可信度 是用來量化 關聯分析 是否成功的一個方法。 假設想找到支持度大於 0.8 的所有項集，應該如何去做呢？ 一個辦法是生成一個物品所有可能組合的清單，然後對每一種組合統計它出現的頻繁程度，但是當物品成千上萬時，上述做法就非常非常慢了。 我們需要詳細分析下這種情況並討論下 Apriori 原理，該原理會減少關聯規則學習時所需的計算量。
k項集
如果事件A中包含k個元素，那麼稱這個事件A為k項集，並且事件A滿足最小支持度閾值的事件稱為頻繁k項集。
由頻繁項集產生強關聯規則
K維數據項集LK是頻繁項集的必要條件是它所有K-1維子項集也為頻繁項集，記為LK-1
如果K維數據項集LK的任意一個K-1維子集Lk-1，不是頻繁項集，則K維數據項集LK本身也不是最大數據項集。
Lk是K維頻繁項集，如果所有K-1維頻繁項集合Lk-1中包含LK的K-1維子項集的個數小於K，則Lk不可能是K維最大頻繁數據項集。
同時滿足最小支持度閥值和最小置信度閥值的規則稱為強規則。
3 Apriori 算法實現
算法思想
首先找出所有的頻集，這些項集出現的頻繁性至少和預定義的最小支持度一樣。然後由頻集產生強關聯規則，這些規則必須滿足最小支持度和最小可信度。然後使用第1步找到的頻集產生期望的規則，產生只包含集合的項的所有規則，其中每一條規則的右部只有一項，這裡採用的是中規則的定義。一旦這些規則被生成，那麼只有那些大於用戶給定的最小可信度的規則才被留下來。
Apriori算法過程
第一步通過迭代，檢索出事務資料庫中的所有頻繁項集，即支持度不低於用戶設定的閾值的項集；
第二步利用頻繁項集構造出滿足用戶最小信任度的規則。
具體做法就是：
首先找出頻繁1-項集，記為L1；然後利用L1來產生候選項集C2，對C2中的項進行判定挖掘出L2，即頻繁2-項集；不斷如此循環下去直到無法發現更多的頻繁k-項集為止。每挖掘一層Lk就需要掃描整個資料庫一遍。算法利用了一個性質：任一頻繁項集的所有非空子集也必須是頻繁的。
4 Apriori 原理
假設我們一共有 4 個商品: 商品0, 商品1, 商品2, 商品3。 所有可能的情況如下:如果我們計算所有組合的支持度，也需要計算 15 次。隨著物品的增加，計算的次數呈指數的形式增長 。為了降低計算次數和時間，研究人員發現了一種所謂的 Apriori 原理，即某個項集是頻繁的，那麼它的所有子集也是頻繁的。 例如，如果 {0, 1} 是頻繁的，那麼 {0}, {1} 也是頻繁的。 該原理直觀上沒有什麼幫助，但是如果反過來看就有用了，也就是說如果一個項集是 非頻繁項集，那麼它的所有超集也是非頻繁項集，如下圖所示:
在圖中我們可以看到，已知灰色部分 {2,3} 是 非頻繁項集，那麼利用上面的知識，我們就可以知道 {0,2,3} {1,2,3} {0,1,2,3} 都是 非頻繁的。 也就是說，計算出 {2,3} 的支持度，知道它是 非頻繁 的之後，就不需要再計算 {0,2,3} {1,2,3} {0,1,2,3} 的支持度，因為我們知道這些集合不會滿足我們的要求。 使用該原理就可以避免項集數目的指數增長，從而在合理的時間內計算出頻繁項集。
Apriori 算法優缺點
優點：易編碼實現
缺點：在大數據集上可能較慢
適用數據類型：數值型 或者 標稱型數據。
Apriori 算法流程步驟：應用場景Apriori 算法廣泛應用於各種領域，通過對數據的關聯性進行了分析和挖掘，挖掘出的這些信息在決策制定過程中具有重要的參考價值。
Apriori算法廣泛應用於消費市場價格分析中:它能夠很快的求出各種產品之間的價格關係和它們之間的影響。通過數據挖掘，市場商人可以瞄準目標客戶，採用個人股票行市、最新信息、特殊的市場推廣活動或其他一些特殊的信息手段，從而極大地減少廣告預算和增加收入。百貨商場、超市和一些老字型大小的零售店也在進行數據挖掘，以便猜測這些年來顧客的消費習慣。
Apriori算法應用於網絡安全領域，比如網絡入侵檢測技術中。早期中大型的電腦系統中都收集審計信息來建立跟蹤檔，這些審計跟蹤的目的多是為了性能測試或計費，因此對攻擊檢測提供的有用信息比較少。它通過模式的學習和訓練可以發現網絡用戶的異常行為模式。採用作用度的Apriori算法削弱了Apriori算法的挖掘結果規則，是網絡入侵檢測系統可以快速的發現用戶的行為模式，能夠快速的鎖定攻擊者，提高了基於關聯規則的入侵檢測系統的檢測性。
Apriori算法應用於高校管理中。隨著高校貧困生人數的不斷增加，學校管理部門資助工作難度也越加增大。針對這一現象，提出一種基於數據挖掘算法的解決方法。將關聯規則的Apriori算法應用到貧困助學體系中，並且針對經典Apriori挖掘算法存在的不足進行改進，先將事務資料庫映射為一個布爾矩陣，用一種逐層遞增的思想來動態的分配內存進行存儲，再利用向量求」與」運算，尋找頻繁項集。實驗結果表明，改進後的Apriori算法在運行效率上有了很大的提升，挖掘出的規則也可以有效地輔助學校管理部門有針對性的開展貧困助學工作。
Apriori算法被廣泛應用於移動通信領域。移動增值業務逐漸成為移動通信市場上最有活力、最具潛力、最受矚目的業務。隨著產業的復甦，越來越多的增值業務表現出強勁的發展勢頭，呈現出應用多元化、營銷品牌化、管理集中化、合作縱深化的特點。針對這種趨勢，在關聯規則數據挖掘中廣泛應用的Apriori算法被很多公司應用。依託某電信運營商正在建設的增值業務Web數據倉庫平臺，對來自移動增值業務方面的調查數據進行了相關的挖掘處理，從而獲得了關於用戶行為特徵和需求的間接反映市場動態的有用信息，這些信息在指導運營商的業務運營和輔助業務提供商的決策制定等方面具有十分重要的參考價值。
5 Apriori 實例理解
實例理解1
一個大型超級市場根據最小存貨單位（SKU）來追蹤每件物品的銷售數據。從而也可以得知哪裡物品通常被同時購買。通過採用先驗算法來從這些銷售數據中創建頻繁購買商品組合的清單是一個效率適中的方法。假設交易資料庫包含以下子集{1,2,3,4}，{1,2}，{2,3,4}，{2,3}，{1,2,4}，{3,4}，{2,4}。每個標號表示一種商品，如「黃油」或「麵包」。先驗算法首先要分別計算單個商品的購買頻率。下表解釋了先驗算法得出的單個商品購買頻率。
然後我們可以定義一個最少購買次數來定義所謂的「頻繁」。在這個例子中，我們定義最少的購買次數為3。因此，所有的購買都為頻繁購買。接下來，就要生成頻繁購買商品的組合及購買頻率。先驗算法通過修改樹結構中的所有可能子集來進行這一步驟。然後我們僅重新選擇頻繁購買的商品組合：
商品編號購買次數{1,2}3{2,3}3{2,4}4{3,4}3並且生成一個包含3件商品的頻繁組合列表（通過將頻繁購買商品組合與頻繁購買的單件商品聯繫起來得出）。在上述例子中，不存在包含3件商品組合的頻繁組合。最常見的3件商品組合為{1,2,4}和{2,3,4}，但是他們的購買次數為2，低於我們設定的最低購買次數。
實例理解2
假設有一個資料庫D，其中有4個事務記錄，分別表示為：
TIDItemsT1l1,l3,l4T2l2,l3,l5T3l1,l2,l3,l5T4l2,l5這裡預定最小支持度minSupport=2,下面用圖例說明算法運行的過程：
1、掃描D，對每個候選項進行支持度計數得到表C1:
2、比較候選項支持度計數與最小支持度minSupport（假設為2），產生1維最大項目集L1：
項集支持度計數{l1}2{l2}3{l3}3{l5}33、由L1產生候選項集C2：
項集4、掃描D，對每個候選項集進行支持度計數:
項集支持度計數{l1,l2}1{l1,l3}2{l1,l5}1{l2,l3}2{l2,l5}3{l3,l5}25、比較候選項支持度計數與最小支持度minSupport，產生2維最大項目集L2：
項集支持度計數{l1,l3}2{l2,l3}2{l2,l5}3{l3,l5}26、由L2產生候選項集C3：
7、比較候選項支持度計數與最小支持度minSupport，產生3維最大項目集L3：
算法終止。
從整體同樣的能說明此過程
首先我們收集所有數據集（可以理解為商品清單），經過數據預處理後如Database TDB所示。我們掃描數據集，經過第一步對每個候選項進行支持度計數得到表C1，比較候選項支持度計數與最小支持度minSupport（假設最小支持度為2），產生1維最大項目集L1。再對L1進行組合產生候選項集C2。第二步我們對C2進行支持度計數，比較候選項支持度計數與最小支持度minSupport，產生2維最大項目集L2。由L2產生候選項集C3，對C3進行支持度計數，使用Apriori性質剪枝：頻繁項集的所有子集必須是頻繁的，對候選項C3，我們可以刪除其子集為非頻繁的選項，{A,B,C}的2項子集是{A,B},{A,C},{B,C}，其中{A,B}不是L2的元素，所以刪除這個選項；{A,C,E}的2項子集是{A,C},{A,E},{C,E}，其中{A,E} 不是L2的元素，所以刪除這個選項；{B,C,E}的2項子集是{B,C},{B,E},{C,E}，它的所有2－項子集都是L2的元素，因此保留這個選項。這樣，剪枝後得到{B,C,E}，比較候選項支持度計數與最小支持度minSupport，產生3維最大項目集L3：繼續進行沒有滿足條件，算法終止。
6 Apriori 算法實現
關聯分析的目標包括兩項:發現頻繁項集和發現關聯規則。Apriori算法是發現頻繁項集的一種方法。 Apriori 算法的兩個輸入參數分別是最小支持度和數據集。該算法首先會生成所有單個物品的項集列表。接著掃描交易記錄來查看哪些項集滿足最小支持度要求，那些不滿足最小支持度要求的集合會被去掉。然後對剩下來的集合進行組合以生成包含兩個元素的項集。接下來再重新掃描交易記錄，去掉不滿足最小支持度的項集。該過程重複進行直到所有項集被去掉。具體算法實現詳細代碼請查看網頁：
https://bainingchao.github.io/categories/%E6%9C%BA%E5%99%A8%E5%AD%A6%E4%B9%A0/Apriori/
7 應用：發現毒蘑菇相似特性
實際需求菌類蘑菇食用對人體有益，現在市場上很受歡迎。假設你在一個山林裡，遇到很多蘑菇，有些可以食用有些有毒。此刻，你或許會詢問山中常駐居民，居民非常友好的告訴你傘菇上有彩色花斑的，樣式好看的等等有毒。他會通過判斷蘑菇的大小，高度，顏色，形狀等23個特徵決定蘑菇有毒，我把將居民的經驗收集在mushromm.dat裡面，以下是部分數據：
1 3 9 13 23 25 34 36 38 40 52 54 59 63 67 76 85 86 90 93 98 107 113
2 3 9 14 23 26 34 36 39 40 52 55 59 63 67 76 85 86 90 93 99 108 114
2 4 9 15 23 27 34 36 39 41 52 55 59 63 67 76 85 86 90 93 99 108 115
其中第一列1代表可以食用2代表有毒。其他各列代表不同特徵。實際中，我們不可能對比23個特徵，我們只需要找出毒蘑菇特有的幾個特徵即可，比如顏色彩色，形狀方形等。我們自然語言描述很容易，就是看到蘑菇，對比下毒蘑菇的幾個特徵，不具備就可以採摘食用了。
到目前為止，我們清楚的採用毒蘑菇共同特徵判斷，那麼如何知道毒蘑菇共同特徵呢？我們就可以使用本節學習的先驗算法Apriori進行關聯規則找出毒蘑菇的共同特性。
算法實現
得到數據集
dataSet=[line.split() for line in open("./mush.dat").readlines()]利用我們的先驗算法計算L頻繁項集和所有元素支持度的全集
L, supportData = apriori(dataSet, minSupport=0.4)
找出關於2的頻繁子項，就知道如果是毒蘑菇，那麼出現頻繁的也可能是毒蘑菇
for item in L[2]:
if item.intersection('2'):
print (item)
毒蘑菇的相似特性運行結果frozenset({'59', '39', '2'})
frozenset({'59', '85', '2'})
frozenset({'34', '39', '2'})
frozenset({'90', '86', '2'})
frozenset({'34', '90', '2'})
frozenset({'39', '86', '2'})
frozenset({'85', '28', '2'})
frozenset({'59', '86', '2'})
frozenset({'34', '85', '2'})
frozenset({'90', '39', '2'})
frozenset({'39', '85', '2'})
frozenset({'34', '59', '2'})
frozenset({'34', '86', '2'})
frozenset({'90', '59', '2'})
frozenset({'85', '86', '2'})
frozenset({'90', '85', '2'})
frozenset({'63', '85', '2'})
如上結果顯示，遇到如上特徵就很可能是毒蘑菇不能食用的啦。我們上面實驗設置的2-頻繁項集，根據實際需要可以調整k-頻繁項集。
8 參考文獻
[1] 數據挖掘十大算法：
https://wizardforcel.gitbooks.io/dm-algo-top10/content/apriori.html
[2] 中文維基百科：
https://zh.wikipedia.org/wiki/%E5%85%88%E9%AA%8C%E7%AE%97%E6%B3%95
[3] GitHub：https://github.com/BaiNingchao/MachineLearning-1
[4] 圖書：《機器學習實戰》
[5] 圖書：《自然語言處理理論與實戰》
9 完整代碼下載
源碼請進【機器學習和自然語言QQ群：436303759】文件下載