數據挖掘算法-Apriori Algorithm（關聯規則）
數據挖掘算法-Apriori Algorithm（關聯規則）
Apriori algorithm是關聯規則里一項基本算法。是由Rakesh Agrawal和Ramakrishnan Srikant兩位博士在1994年提出的關聯規則挖掘算法。關聯規則的目的就是在一個數據集中找出項與項之間的關系，也被稱為購物藍分析 (Market Basket analysis)，因為“購物藍分析”很貼切的表達了適用該算法情景中的一個子集。關于這個算法有一個非常有名的故事："尿布和啤酒"。故事是這樣的： 美國的婦女們經常會囑咐她們的丈夫下班后為孩子買尿布，而丈夫在買完尿布后又要順 手買回自己愛喝的啤酒，因此啤酒和尿布在一起被購買的機會很多。這個舉措使尿布和啤酒的銷量雙雙增加，并一直為眾商家所津津樂道。
一.一些概念和定義
1.定義1 項目與項集
設I={i1,i2,…,im}是m個不同項目的集合，每個ik(k=1，2，……，m)稱為一個項目(Item)。項目的集合 I 稱為項目集合(Itemset)，簡稱為項集。其元素個數稱為項集的長度，長度為k的項集稱為k-項集(k-Itemset)。
2.定義2 交易
每筆交易T(Transaction)是項集I上的一個子集，即T 
I，但通常T 
I。
對應每一個交易有一個唯一的標識——交易號，記作TID
交易的全體構成了交易數據庫D，或稱交易記錄集D，簡稱交易集D。
交易集D中包含交易的個數記為|D|。
3.定義3 項集的支持度
對于項集X，X 
I，設定count(X 
T)為交易集D中包含X的交易的數量
項集X的支持度support(X)就是項集X出現的概率，從而描述了X的重要性。
4.定義4 項集的最小支持度與頻繁集
發現關聯規則要求項集必須滿足的最小支持閾值，稱為項集的最小支持度(Minimum Support)，記為supmin。
支持度大于或等于supmin的項集稱為頻繁項集，簡稱頻繁集，反之則稱為非頻繁集。
通常k-項集如果滿足supmin，稱為k-頻繁集，記作Lk 。
5.定義5 關聯規則
關聯規則(Association Rule)可以表示為一個蘊含式：
其中： 
。
例如：R：牛奶→面包
6.定義6 關聯規則的支持度
規則R的的支持度(Support)是交易集中同時包含X和Y的交易數與所有交易數之比。
例如：在5條記錄中，既有橙汁又有可樂的記錄有2條。則此條規則的支持度為 2/5=0.4，即Support(A-〉B)=P(AB)。
7.定義7 關聯規則的置信度
規則R的置信度(Confidence)是指包含X和Y的交易數與包含X的交易數之比
例如：計算“如果Orange則Coke”的置信度。由于在含有“橙汁”的4條交易中，僅有2條交易含有“可樂”。其置信度為0.5。
8.定義8 關聯規則的最小支持度和最小置信度
關聯規則的最小支持度也就是衡量頻繁集的最小支持度(Minimum Support)，記為supmin，它用于衡量規則需要滿足的最低重要性。關聯規則的最小置信度(Minimum Confidence)記為confmin，它表示關聯規則需要滿足的最低可靠性。
9.定義9 強關聯規則
，稱關聯規則X=》Y為強關聯規則，否則稱關聯規則X=》Y為弱關聯規則。
在挖掘關聯規則時，產生的關聯規則要經過supmin和confmin的衡量，篩選出來的強關聯規則才能用于指導商家的決策。
10.候選集（Candidate itemset）：通過向下合并得出的項集。定義為C[k]。 11.頻繁集（Frequent itemset）：支持度大于等于特定的最小支持度（Minimum Support/minsup）的項集。表示為L[k]。注意，頻繁集的子集一定是頻繁集。 12.提升比率（提升度Lift）：lift(X -> Y) = lift(Y -> X) = conf(X -> Y)/supp(Y) = conf(Y -> X)/supp(X) = P(X and Y)/(P(X)P(Y)) 經過關聯規則分析后，針對某些人推銷（根據某規則）比盲目推銷（一般來說是整個數據）的比率，這個比率越高越好，我們稱這個規則為強規則；
13.剪枝步:只有當子集都是頻繁集的候選集才是頻繁集，這個篩選的過程就是剪枝步。
二. Apriori Algorithm（關聯規則）動態演示 （ 點擊下載ppt觀看 ）
三.Apriori Algorithm（關聯規則）算法描述
Apriori 算法采用的方法為：首先產生頻繁 1-項集 L1，然后用 L1經過自連接、剪枝生成 L2，頻繁 2-項集 L2又用來生成 L3，以此類推，逐層迭代，直到無法產生新的頻繁項集為止。然后根據給定的最小可信度，利用生成的頻繁項集產生關聯規則。
1.產生頻繁項集 該過程可以通過以下步驟實現：
1) 第一階段，所有單獨的項都是候選項集 C1。任何支持度值比給定的最小支持度值小的項都將從候選項集 C1中剔除，形成頻繁 1-項集 L1。
2) 兩個 L1通過自連接形成具有 2 個項的候選項集 C2。通過再次掃描數據庫決定這些候選項的支持度。保留比預先給定的最小支持度大的候選項，形成頻繁 2-項集L2。
3) 下一步形成含有 3 個項的候選項集 C3，重復上述步驟，直到找到所有的頻繁項集為止。
Apriori 算法的偽碼描述如下所示：
輸入：數據集 D，min_sup輸出：D 中的頻繁項集 L
2.產生關聯規則
從事務數據庫 D 中挖掘出頻繁所有的頻繁項集后，就可以比較容易的獲得相應的關聯規則，即滿足可信度?min_conf 的頻繁項集產生強關聯規則。由于規則是由頻繁項集產生，所以每個規則自動滿足 min_sup。
在用頻繁項 X 生成關聯的偽碼如下：
輸入：Yk，Lk，min_conf輸出：形如 X=》Y 的關聯規則
-------------------------------------------------------------------------------------------------------------------------------------