深度解析數據挖掘關聯規則Apriori算法

01、關聯規則挖掘背景和基本概念

如下所示的數據集，表中的每一行代表一次購買清單，注意我們只關心記錄出現與否，不關心某條記錄購買了幾次，如購買十盒牛奶也只計一次。

數據記錄的所有項的集合稱為總項集，上表中的總項集：

S={牛奶,面包,尿布,啤酒,雞蛋,可樂}

關聯規則

就是有關聯的規則，形式是這樣定義的：兩個不相交的非空集合X、Y，如果有

X->Y，就說X-->Y是一條關聯規則，例如，{啤酒}-->{尿布}就是一條關聯規則。

關聯規則的強度用支持度(support)和自信度(confidence)來描述。

支持度

support(X-->Y) = 集合X與集合Y中的項在一條記錄中同時出現的次數 / 數據記錄的個數。例如：support({啤酒}-->{尿布}) = 啤酒和尿布同時出現的次數 / 數據記錄數 = 3/5=60%

自信度

confidence(X-->Y) = 集合X與集合Y中的項在一條記錄中同時出現的次數 / 集合X出現的個數 。例如：confidence({尿布}-->{啤酒}) = 啤酒和尿布同時出現的次數 / 尿布出現的次數 = 3/4 = 75%。

總結

支持度和自信度越高，說明規則越強，關聯規則挖掘就是挖掘出滿足一定強度的規則。

02、關聯規則挖掘的之窮舉算法

關聯規則挖掘

給定一個交易數據集T，找出其中所有支持度 support >= min_support、自信度confidence >= min_confidence的關聯規則。

窮舉算法

找出所需要的規則就是窮舉項集的所有組合，并測試每個組合是否滿足條件，一個元素個數為n的項集所需要的時間復雜度為O(2^N)。上表的總項集 S={牛奶,面包,尿布,啤酒,雞蛋,可樂}，元素的個數為6，所有的組合個數為63 。

為了簡單起見，已知一個商品編號的總項集為：{1, 2, 3}，那么所有可能的組合為： 

共有7項(2^3 - 1)，分別檢查以上各種組合，在每一種組合上找出滿足支持度和自信度要求的關聯規則。

對于普通的超市，其商品的項集數也在1萬以上，用指數時間復雜度的算法不能在可接受的時間內解決問題。

怎樣快速挖出滿足條件的關聯規則是關聯挖掘的需要解決的主要問題。

03、關聯規則挖掘優化算法之Apriori算法

關聯規則挖掘分兩步進行：

1)生成頻繁項集

這一階段找出所有滿足最小支持度的項集，找出的這些項集稱為頻繁項集。

2)生成規則

在上一步產生的頻繁項集的基礎上生成滿足最小自信度的規則，產生的規則稱為強規則。

關聯規則挖掘所花費的時間主要是在第一步：生成頻繁項集上。因為找出的頻繁項集往往不會很多，所以2)相對1)耗時少。

為了減少 1)：頻繁項集的生成時間，應該盡早的消除一些完全不可能是頻繁項集的集合，Apriori算法主要通過兩個規律減少頻繁項集。

兩個定律

高級到低級。如果一個集合是頻繁項集，則它的所有子集都是頻繁項集。假設一個集合{A,B}是頻繁項集，則它的子集{A}, {B} 都是頻繁項集。

低級到高級。如果一個集合不是頻繁項集，則它的所有超集都不是頻繁項集。假設集合{A}不是頻繁項集，則它的任何超集如{A,B}，{A,B,C}必定也不是頻繁項集。

具有實際應用價值的還是第2條，從低級的頻繁項集到高級的頻繁項集的演化，試想，如果二級項集 {A,B}支持度都沒有大于閾值，即不是頻繁項集，三級{A,C,B}或更高級怎么可能是頻繁項集呢?如果是的話，{A,B}就一定是頻繁項集了，這不和原來的條件矛盾了嗎?

首先統計一級候選項集，清除不滿足條件的候選集，得到滿足條件的一級項集，在生成一級項集的基礎上，生成二級項集，得到滿足條件的二級項集，在生成三級項集時，再次根據定律2的思想，如，{牛奶,啤酒}不是頻繁項集，所以{牛奶，啤酒，尿布}，{牛奶，啤酒，面包}都不是頻繁項集。 

Apriori算法

屬于候選消除算法，是一個根據定律2生成候選集、根據支持度和可信度的預置消除不滿足條件的候選集，并不斷循環直到不再產生候選集的過程。

算法的偽代碼： 

 總結了關聯規則挖掘的經典算法Apriori算法，這個算法利用了一個定律：如果一個集合不是頻繁項集，則它的所有超集都不是頻繁項集，自下而上，挖掘出滿足支持度和可信度閾值的所有級別的頻繁項集。

結語

感謝您的觀看，如有不足之處，歡迎批評指正。

如果有對大數據感興趣的小伙伴或者是從事大數據的老司機可以加群：

658558542    

歡迎大家交流分享，學習交流，共同進步。（里面還有大量的免費資料，幫助大家在成為大數據工程師，乃至架構師的路上披荊斬棘！）

最后祝福所有遇到瓶頸的大數據程序員們突破自己，祝福大家在往后的工作與面試中一切順利。