{% raw %}
# 數據挖掘十大算法--Apriori算法
> 來源：http://blog.csdn.net/u011067360/article/details/24810415
**一、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-項集，記為L<sub>1</sub>；然后利用L<sub>1</sub>來產生候選項集C<sub>2</sub>，對C<sub>2</sub>中的項進行判定挖掘出L<sub>2</sub>，即頻繁2-項集；不斷如此循環下去直到無法發現更多的頻繁k-項集為止。每挖掘一層L<sub>k</sub>就需要掃描整個數據庫一遍。算法利用了一個性質：
**Apriori 性質**：任一頻繁項集的所有非空子集也必須是頻繁的。意思就是說，生成一個k-itemset的候選項時，如果這個候選項有子集不在(k-1)-itemset(已經確定是frequent的)中時，那么這個候選項就不用拿去和支持度判斷了，直接刪除。具體而言：
1） 連接步
為找出L<sub>k</sub>（所有的頻繁k項集的集合），通過將L<sub>k-1</sub>（所有的頻繁k-1項集的集合）與自身連接產生候選k項集的集合。候選集合記作C<sub>k</sub>。設l<sub>1</sub>和l<sub>2</sub>是L<sub>k-1</sub>中的成員。記l<sub>i</sub>[j]表示l<sub>i</sub>中的第j項。假設Apriori算法對事務或項集中的項按字典次序排序，即對于（k-1）項集l<sub>i</sub>，l<sub>i</sub>[1]<l<sub>i</sub>[2]<……….<l<sub>i</sub>[k-1]。將L<sub>k-1</sub>與自身連接，如果(l<sub>1</sub>[1]=l<sub>2</sub>[1])&&( l<sub>1</sub>[2]=l<sub>2</sub>[2])&&……..&& (l<sub>1</sub>[k-2]=l<sub>2</sub>[k-2])&&(l<sub>1</sub>[k-1]<l<sub>2</sub>[k-1])，那認為l<sub>1</sub>和l<sub>2</sub>是可連接。連接l<sub>1</sub>和l<sub>2</sub> 產生的結果是{l<sub>1</sub>[1],l<sub>1</sub>[2],……,l<sub>1</sub>[k-1],l<sub>2</sub>[k-1]}。
2） 剪枝步
C<sub>K</sub>是L<sub>K</sub>的超集，也就是說，C<sub>K</sub>的成員可能是也可能不是頻繁的。通過掃描所有的事務（交易），確定C<sub>K</sub>中每個候選的計數，判斷是否小于最小支持度計數，如果不是，則認為該候選是頻繁的。為了壓縮C<sub>k</sub>,可以利用Apriori性質：任一頻繁項集的所有非空子集也必須是頻繁的，反之，如果某個候選的非空子集不是頻繁的，那么該候選肯定不是頻繁的，從而可以將其從C<sub>K</sub>中刪除。
**五、實例說明**
實例一：下面以圖例的方式說明該算法的運行過程： 假設有一個數據庫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算法大約快一個數量級。
{% endraw %}
