小白學數據分析之關聯分析算法篇Apriori

早些時候寫過關于購物籃分析的文章，其中提到了C5.0和Apriori算法，沒有仔細說說這算法的含義，昨天寫了一下關聯分析的理論部分，今天說說關聯分析算法之一的Apriori算法，很多時候大家都說，數據分析師更多的是會用就可以了，不必糾結于那些長篇累牘的理論，其實我覺得還是有點必要的，你未必要去設計算法，但是如果你掌握和熟知一個算法，這對于你如何駕馭和使用這個算法是很有幫助的，此外每個算法都有使用的局限性，比如空間和時間復雜度，使用條件約束。最典型的就是我們難道一份原始數據，然后經過數據處理要進行算法模擬分析，但是此時你會出現一個問題，我需要處理哪些數據，如何處理？而這就需要你對你所使用的算法必須熟悉，比如能夠操作的數據格式，類型。比如GRI算法要求使用的數據必須是事實表的方式存儲，這樣的算法特點必須建立在對于算法的了解把握層次上。
Apriori算法
　　其名字是因為算法基于先驗知識(prior knowledge).根據前一次找到的頻繁項來生成本次的頻繁項。Apriori是關聯分析中核心的算法。
Apriori算法的特點
　　只能處理分類變量，無法處理數值型變量；
　　數據存儲可以是交易數據格式（事務表），或者是事實表方式（表格數據）；
　　算法核心在于提升關聯規則產生的效率而設計的。
Apriori的思想
　　正如我們之前所提到的，我們希望置信度和支持度要滿足我們的閾值范圍才算是有效的規則，實際過程中我們往往會面臨大量的數據，如果只是簡單的搜索，會出現很多的規則，相當大的一部分是無效的規則，效率很低，那么Apriori就是通過產生頻繁項集，然后再依據頻繁項集產生規則，進而提升效率。
　　以上所說的代表了Apriori算法的兩個步驟：產生頻繁項集和依據頻繁項集產生規則。
　　那么什么是頻繁項集？
　　頻繁項集就是對包含項目A的項目集C，其支持度大于等于指定的支持度，則C（A）為頻繁項集，包含一個項目的頻繁項集稱為頻繁1-項集，即L1。
　　為什么確定頻繁項集？
　　剛才說了，必須支持度大于我們指定的支持度，這也就是說能夠確定后面生成的規則是在普遍代表性上的項目集生成的，因為支持度本身的高低就代表了我們關聯分析結果是否具有普遍性。
　　怎么尋找頻繁項集？
　　這里不再講述，直接說一個例子大家就都明白了。例子來源于Fast Algorithms for Mining Association Rules
　　Apriori尋找頻繁項集的過程是一個不斷迭代的過程，每次都是兩個步驟，產生候選集Ck（可能成為頻繁項集的項目組合）；基于候選集Ck計算支持度，確定Lk。
　　Apriori的尋找策略就是從包含少量的項目開始逐漸向多個項目的項目集搜索。
數據如下：

　　我們看到，數據庫存儲的數據格式，會員100購買了 1 3 4三種商品，那么對應的集合形式如右邊的圖所示。那么基于候選集C1，我們得到頻繁項集L1，如下圖所示，在此表格中{4}的支持度為1，而我們設定的支持度為2。支持度大于或者等于指定的支持度的最小閾值就成為L1了，這里{4}沒有成為L1的一員。因此，我們認定包含4的其他項集都不可能是頻繁項集，后續就不再對其進行判斷了。

　　此時我們看到L1是符合最低支持度的標準的，那么下一次迭代我們依據L1產生C2（4就不再被考慮了），此時的候選集如右圖所示C2（依據L1*L1的組合方式）確立。C2的每個集合得到的支持度對應在我們原始數據組合的計數，如下圖左所示。

　　此時，第二次迭代發現了{1 2} {1 5}的支持度只有1，低于閾值，故而舍棄，那么在隨后的迭代中，如果出現{1 2} {1 5}的組合形式將不被考慮。
 
　　如上圖，由L2得到候選集C3，那么這次迭代中的{1 2 3} { 1 3 5}哪去了？如剛才所言，{1 2} {1 5}的組合形式將不被考慮，因為這兩個項集不可能成為頻繁項集L3，此時L4不能構成候選集L4，即停止。
　　如果用一句化解釋上述的過程，就是不斷通過Lk的自身連接，形成候選集，然后在進行剪枝，除掉無用的部分。
根據頻繁項集產生簡單關聯規則
　　Apriori的關聯規則是在頻繁項集基礎上產生的，進而這可以保證這些規則的支持度達到指定的水平，具有普遍性和令人信服的水平。
　　以上就是Apriori的算法基本原理，留了兩個例子，可以加深理解。
例子1：

例子2：