681
關聯規則挖掘之Apriori算法實現超市購物
一.關聯規則
關聯規則(Association Rules)是反映一個事物與其他事物之間的相互依存性和關聯性，是數據挖掘的一個重要技術，用於從大量數據中挖掘出有價值的數據項之間的相關關係。其中關聯規則挖掘的最經典的例子就是沃爾瑪的啤酒與尿布的故事，通過對超市購物籃數據進行分析，即顧客放入購物籃中不同商品之間的關係來分析顧客的購物習慣，發現美國婦女們經常會叮囑丈夫下班後為孩子買尿布，30%-40%的丈夫同時會順便購買喜愛的啤酒，超市就把尿布和啤酒放在一起銷售增加銷售額。
二.基本概念
關聯規則挖掘是尋找給定數據集中項之間的有趣聯係。如下圖所示：
其中，I={I1,I2,…Im}是m個不同項目的集合,集合中的元素稱為項目（Item）。項目的集合I稱為項目集合（Itemset），長度為k的項集成為k-項集。設任務相關的數據D是數據庫事務的集合，其中每個事務T是項的集合，使得T⊆I。每個事務有一個標識符TID；設A是一個項集，事務T包含A當且僅當A⊆I，則關聯規則形式為A=>B（其中A⊂I，B⊂I，並且A∩B=
∅）。
在關聯規則度量中有兩個重要的度量值：支持度和置信度。對於關聯規則R:A=>B，則：
1.支持度（suppport）：是交易集中同時包含A和B的交易數與所有交易數之比。
Support(A=>B)=P(A∪B)=count(A∪B)/|D|
2.置信度（confidence）：是包含A和B交易數與包含A的交易數之比。
Confidence(A=>B)=P(B|A)=support(A∪B)/support(A)
如上圖中數據庫D，包含4個事務，項集I={I1,I2,I3,I4,I5}，分析關聯規則：I1=>I4，事務1、4包含I1，事務4同時包含I1和I4。
支持度support=1/4=25%（1個事務同時包含I1和I4,共有4個事務）指在所有交易記錄中有25%的交易記錄同時包含I1和I4項目
置信度confidence=1/2=50%（1個事務同時包含I1和I4,2個事務包含I1）指50%的顧客在購買I1時同時還會購買I4
使用關聯規則對購物籃進行挖掘，通常采用兩個步驟進行：下麵將通超市購物的例子對關聯規則挖掘進行分析。
a.找出所有頻繁項集（文章中我使用Apriori算法>=最小支持度的項集）
b.由頻繁項集產生強關聯規則（>=最小支持度和最小置信度）
三.舉例：Apriori算法挖掘頻繁項集
Apriori算法是一種對有影響的挖掘布爾關聯規則頻繁項集的算法，通過算法的連接和剪枝即可挖掘頻繁項集.補充頻繁項集相關知識：K-項集：指包含K個項的項集；項集的出現頻率：指包含項集的事務數，簡稱為項集的頻率、支持度計數或計數；頻繁項集：如果項集的出現頻率大於或等於最小支持度計數閾值，則稱它為頻繁項集，其中頻繁K-項集的集合通常記作Lk。
下麵直接通過例子描述該算法：如下圖所示，使用Apriori算法關聯規則挖掘數據集中的頻繁項集。（最小支持度技術為2）
具體過程如下所示：
具體分析結果：
第一次掃描：對每個候選商品計數得C1，由於候選{D}支持度計數為1<最小支持度計數2，故刪除{D}得頻繁1-項集合L1；
第二次掃描：由L1產生候選C2並對候選計數得C2，比較候選支持度計數與最小支持度計數2得頻繁2-項集合L2；
第三次掃描：用Apriori算法對L2進行連接和剪枝產生候選3項集合C3的過程如下：
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.剪枝：
{A,B,C}的2項子集{A,B},{A,C}和{B,C}，其中{A,B}不是2項子集L2,因此不是頻繁的，從C3中刪除；
{A,C,E}的2項子集{A,C},{A,E}和{C,E}，其中{A,E}不是2項子集L2，因此不是頻繁的，從C3中刪除；
{B,C,E}的2項子集{B,C},{B,E}和{C,E}，它的所有2項子集都是L2的元素，保留C3中.
經過Apriori算法對L2連接和剪枝後產生候選3項集的集合為C3={B,C,E}. 在對該候選商品計數，由於等於最小支持度計數2，故得頻繁3-項集合L3，同時由於4-項集中僅1個，故C4為空集，算法終止。
四.舉例：頻繁項集產生強關聯規則
強關聯規則是指：如果規則R：X=>Y滿足support(X=>Y)>=supmin(最小支持度，它用於衡量規則需要滿足的最低重要性)且confidence(X=>Y)>=confmin（最小置信度，它表示關聯規則需要滿足的最低可靠性）稱關聯規則X=>Y為強關聯規則，否則稱關聯規則X=>Y為弱關聯規則。
例：下圖是某日超市的購物記錄，使用上麵敘述的Apriori算法實現了挖掘頻繁項集，其中頻繁項集I={i1,i2,i5}為頻繁3-項集合L3，求由I產生哪些強關聯規則？（最小支持度閾值為20%，最小置信度閾值為80%）
I的非空子集有{i1,i2}、{i1,i5}、{i2,i5}、{i1}、{i2}和{i5}。
結果關聯規則如下，每個都列出置信度
1).i1∧i2=>i5,共10個事務；5個事務包含i1,i2；2個事務包含i1,i2和i5 confidence=2/5=40%，support=2/10=20%
2).i1∧i5=>i2,共10個事務；2個事務包含i1,i5；2個事務包括i1,i2和i5 confidence=2/2=100%，support=2/10=20%
3).i2∧i5=>i1,共10個事務；2個事務包含i2,i5；2個事務包含i1,i2和i5 confidence=2/2=100%，support=2/10=20%
4).i1=>i2∧i5,共10個事務；7個事務包含i1；2個事務包含i1,i2和i5 confidence=2/7=28%，support=2/10=20%
5).i2=>i1∧i5,共10個事務；8個事務包含i2；2個事務包含i1,i2和i5 confidence=2/8=25%，support=2/10=20%
6).i5=>i1∧i2,共10個事務；2個事務包含i5；2個事務包含i1,i2和i5 confidence=2/2=100%，support=2/10=20%
因最小置信度閾值為80%,最小支持度閾值為20%,則236規則符合要求,是頻繁項集I={i1,i2,i5}產生的強關聯規則且可以輸出。
(自己的推測：如果給定的是最小支持度計數為2，則有10個事務，最小支持度閾值supmin=2/10=20%)
五.總結
這是最近學習《商務智能》課程中對關聯規則挖掘“超市購物籃”的分析，使用Apriori對數據庫進行頻繁項集挖掘與關聯規則的產生是一個非常有用的技術，其中我們眾所周知的例子如沃爾瑪超市的尿布與啤酒、超市的牛奶與麵包、百度文庫推薦相關文檔、淘寶推薦相關書籍、銀行推薦相關聯業務等。這些都是商務智能和關聯規則在實際生活中的運用，上麵的例子主要是我們學校的課件，也結合了很多網上的資料.
希望該文章能幫組到大家！同時是我對該知識點的一些總結，如果有錯誤或不足之處，見諒！
問題：我在發表博客時想縮小行間距，不知道怎樣實現，采用html也沒成功，所以上麵的排版間距很大？求告知，謝謝！
(PS:使用Ctrl+回車即可,自己博客寫多了,慢慢摸索出來的)
（By:Eastmount 2013-8-10 下午6點）
最後更新：2017-04-03 16:48:53