一、apriori 算法概述
apriori 算法是一種最有影響力的挖掘布爾關聯規則的頻繁項集的 算法，它是由rakesh agrawal 和ramakrishnanskrikant 提出的。它使用一種稱作逐層搜尋的疊代方法，k- 項集用于探索（k+1）- 項集。首先，找出頻繁 1- 項集的集合。該集合記作l1。l1 用于找頻繁2- 項集的集合 l2，而l2 用于找l2，如此下去，直到不能找到 k- 項集。每找一個 lk 需要一次資料庫掃描。為提高頻繁項集逐層産生的效率，一種稱作apriori 性質的重 要性質 用于壓縮搜尋空間。其運作定理在于一是頻繁項集的所有非空子集都必須也是頻繁的，二是非頻繁項集的所有父集都是非頻繁的。
二、問題的引入
購物籃分析：引發性例子
question：哪組商品顧客可能會在一次購物時同時購買？
關聯分析
solutions：
1：經常同時購買的商品可以擺近一點，以便進一步刺激這些商品一起銷售。
2：規劃哪些附屬商品可以降價銷售，以便刺激主體商品的捆綁銷售。
三、關聯分析的基本概念
1、支援度
關聯規則a->b的支援度support=p(ab)，指的是事件a和事件b同時發生的機率。
2、置信度
置信度confidence=p(b|a)=p(ab)/p(a),指的是發生事件a的基礎上發生事件b的機率。比如說在規則computer => antivirus_software , 其中 support=2%, confidence=60%中，就表示的意思是所有的商品交易中有2%的顧客同時買了電腦和防毒軟體，并且購買電腦的顧客中有60%也購買了防毒軟體。
3、k項集
如果事件a中包含k個元素，那麼稱這個事件a為k項集，并且事件a滿足最小支援度門檻值的事件稱為頻繁k項集。
4、由頻繁項集産生強關聯規則
1）k維資料項集lk是頻繁項集的必要條件是它所有k-1維子項集也為頻繁項集，記為lk-1
2）如果k維資料項集lk的任意一個k-1維子集lk-1，不是頻繁項集，則k維資料項集lk本身也不是最大資料項集。
3）lk是k維頻繁項集，如果所有k-1維頻繁項集合lk-1中包含lk的k-1維子項集的個數小于k，則lk不可能是k維最大頻繁資料項集。
4）同時滿足最小支援度閥值和最小置信度閥值的規則稱為強規則。
例如：用一個簡單的例子說明。表1是顧客購買記錄的資料庫d，包含6個事務。項集i={網球拍,網球,運動鞋,羽毛球}。考慮關聯規則：網球拍
網球，事務1,2,3,4,6包含網球拍，事務1,2,6同時包含網球拍和網球，支援度
，置信度
。若給定最小支援度
，最小置信度
，關聯規則網球拍
網球是有趣的，認為購買網球拍和購買網球之間存在強關聯。
四、apriori算法的基本思想：
apriori算法過程分為兩個步驟：
第一步通過疊代，檢索出事務資料庫中的所有頻繁項集，即支援度不低于使用者設定的門檻值的項集；
第二步利用頻繁項集構造出滿足使用者最小信任度的規則。
具體做法就是：
首先找出頻繁1-項集，記為l1；然後利用l1來産生候選項集c2，對c2中的項進行判定挖掘出l2，即頻繁2-項集；不斷如此循環下去直到無法發現更多的頻繁k-項集為止。每挖掘一層lk就需要掃描整個資料庫一遍。算法利用了一個性質：
apriori 性質：任一頻繁項集的所有非空子集也必須是頻繁的。意思就是說，生成一個k-itemset的候選項時，如果這個候選項有子集不在(k-1)-itemset(已經确定是frequent的)中時，那麼這個候選項就不用拿去和支援度判斷了，直接删除。具體而言：
1） 連接配接步
為找出lk（所有的頻繁k項集的集合），通過将lk-1（所有的頻繁k-1項集的集合）與自身連接配接産生候選k項集的集合。候選集合記作ck。設l1和l2是lk-1中的成員。記li[j]表示li中的第j項。假設apriori算法對事務或項集中的項按字典次序排序，即對于（k-1）項集li，li[1]<li[2]<……….<li[k-1]。将lk-1與自身連接配接，如果(l1[1]=l2[1])&&(
l1[2]=l2[2])&&……..&& (l1[k-2]=l2[k-2])&&(l1[k-1]<l2[k-1])，那認為l1和l2是可連接配接。連接配接l1和l2 産生的結果是{l1[1],l1[2],……,l1[k-1],l2[k-1]}。
2） 剪枝步
ck是lk的超集，也就是說，ck的成員可能是也可能不是頻繁的。通過掃描所有的事務（交易），确定ck中每個候選的計數，判斷是否小于最小支援度計數，如果不是，則認為該候選是頻繁的。為了壓縮ck,可以利用apriori性質：任一頻繁項集的所有非空子集也必須是頻繁的，反之，如果某個候選的非空子集不是頻繁的，那麼該候選肯定不是頻繁的，進而可以将其從ck中删除。
五、執行個體說明
執行個體一：下面以圖例的方式說明該算法的運作過程： 假設有一個資料庫d，其中有4個事務記錄，分别表示為：
這裡預定最小支援度minsupport=2,下面用圖例說明算法運作的過程：
1、掃描d，對每個候選項進行支援度計數得到表c1:
2、比較候選項支援度計數與最小支援度minsupport，産生1維最大項目集l1：
3、由l1産生候選項集c2：
4、掃描d，對每個候選項集進行支援度計數:
5、比較候選項支援度計數與最小支援度minsupport，産生2維最大項目集l2：
6、由l2産生候選項集c3：
7、比較候選項支援度計數與最小支援度minsupport，産生3維最大項目集l3：
算法終止。
執行個體二：下圖從整體同樣的能說明此過程：
此例的分析如下：
1 . 連接配接：c3=l2
l2= {{a,c},{b,c},{b,e}{c,e}}
{{a,c},{b,c},{b,e}{c,e}} = {{a,b,c},{a,c,e},{b,c,e}}
2．使用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的元素，是以保留這個選項。
3．這樣，剪枝後得到c3={{b,c,e}}
ps
從算法的運作過程，我們可以看出該apriori算法的優點：簡單、易了解、資料要求低，然而我們也可以看到apriori算法的缺點：
(1)在每一步産生侯選項目集時循環産生的組合過多，沒有排除不應該參與組合的元素;
(2)每次計算項集的支援度時，都對資料庫d中的全部記錄進行了一遍掃描比較，如果是一個大型的資料庫的話，這種掃描比較會大大增加計算機系統的i/o開銷。而這種代價是随着資料庫的記錄的增加呈現出幾何級數的增加。是以人們開始尋求更好性能的算法。
六、改進apriori算法的方法
方法1：基于hash表的項集計數
将每個項集通過相應的hash函數映射到hash表中的不同的桶中，這樣可以通過将桶中的項集技術跟最小支援計數相比較先淘汰一部分項集。
方法2：事務壓縮（壓縮進一步疊代的事務數）
不包含任何k-項集的事務不可能包含任何(k+1)-項集，這種事務在下一步的計算中可以加上标記或删除
方法3：劃分
挖掘頻繁項集隻需要兩次資料掃描
d中的任何頻繁項集必須作為局部頻繁項集至少出現在一個部分中。
第一次掃描：将資料劃分為多個部分并找到局部頻繁項集
第二次掃描：評估每個候選項集的實際支援度，以确定全局頻繁項集。
方法4：選樣（在給定資料的一個子集挖掘）
基本思想：選擇原始資料的一個樣本，在這個樣本上用apriori算法挖掘頻繁模式
通過犧牲精确度來減少算法開銷，為了提高效率，樣本大小應該以可以放在記憶體中為宜，可以适當降低最小支援度來減少遺漏的頻繁模式
可以通過一次全局掃描來驗證從樣本中發現的模式
可以通過第二此全局掃描來找到遺漏的模式
方法5：動态項集計數
在掃描的不同點添加候選項集，這樣，如果一個候選項集已經滿足最少支援度，則在可以直接将它添加到頻繁項集，而不必在這次掃描的以後對比中繼續計算。
ps：apriori算法的優化思路
1、在逐層搜尋循環過程的第k步中，根據k-1步生成的k-1維頻繁項目集來産生k維候選項目集，由于在産生k-1維頻繁項目集時，我們可以實作對該集中出現元素的個數進行計數處理，是以對某元素而言，若它的計數個數不到k-1的話，可以事先删除該元素，進而排除由該元素将引起的大規格所有組合。
這是因為對某一個元素要成為k維項目集的一進制素的話，該元素在k-1階頻繁項目集中的計數次數必須達到k-1個，否則不可能生成k維項目集(性質3)。
2、根據以上思路得到了這個候選項目集後，可以對資料庫d的每一個事務進行掃描，若該事務中至少含有候選項目集ck中的一員則保留該項事務，否則把該事物記錄與資料庫末端沒有作删除标記的事務記錄對換，并對移到資料庫末端的事務記錄作删除标一記，整個資料庫掃描完畢後為新的事務資料庫d’ 中。
是以随着k 的增大，d’中事務記錄量大大地減少，對于下一次事務掃描可以大大節約i/0 開銷。由于顧客一般可能一次隻購買幾件商品，是以這種虛拟删除的方法可以實作大量的交易記錄在以後的挖掘中被剔除出來，在所剩餘的不多的記錄中再作更高維的資料挖掘是可以大大地節約時間的。
執行個體過程如下圖：
當然還有很多相應的優化算法，比如針對apriori算法的性能瓶頸問題-需要産生大量候選項集和需要重複地掃描資料庫，2000年jiawei han等人提出了基于fp樹生成頻繁項集的fp-growth算法。該算法隻進行2次資料庫掃描且它不使用侯選集，直接壓縮資料庫成一個頻繁模式樹，最後通過這棵樹生成關聯規則。研究表明它比apriori算法大約快一個數量級。