關(guān)聯(lián)規(guī)則簡介與Apriori算法

1、關(guān)聯(lián)規(guī)則（Association Rules）反映一個(gè)事物與其他事物之間的相互依存性和關(guān)聯(lián)性。如果兩個(gè)或者多個(gè)事物之間存在一定的關(guān)聯(lián)關(guān)系，那么，其中一個(gè)事物就能夠通過其他事物預(yù)測到。首先被Agrawal, Imielinski and Swami在1993年的SIGMOD會議上提出. 關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘中最活躍的研究方法之一。典型的關(guān)聯(lián)規(guī)則發(fā)現(xiàn)問題是對超市中的購物籃數(shù)據(jù)（Market Basket）進(jìn)行分析。通過發(fā)現(xiàn)顧客放入購物籃中的不同商品之間的關(guān)系來分析顧客的購買習(xí)慣。 “尿布與啤酒”的故事。美國的沃爾瑪超市對一年多的原始交易數(shù)據(jù)進(jìn)行了詳細(xì)的分析，得到一個(gè)意外發(fā)現(xiàn)：與尿布一起被購買最多

2、的商品竟然是啤酒。借助于數(shù)據(jù)倉庫和關(guān)聯(lián)規(guī)則，商家發(fā)現(xiàn)了這個(gè)隱藏在背后的事實(shí)：美國的婦女們經(jīng)常會囑咐她們的丈夫下班以后要為孩子買尿布，而30%40%的丈夫在買完尿布之后又要順便購買自己愛喝的啤酒。有了這個(gè)發(fā)現(xiàn)后，超市調(diào)整了貨架的設(shè)置，把尿布和啤酒擺放在一起銷售，從而大大增加了銷售額。70%購買了牛奶的顧客將傾向于同時(shí)購買面包。某網(wǎng)上書店向用戶推薦相關(guān)書籍。在買了一臺PC之后下一步會購買？在保險(xiǎn)業(yè)務(wù)方面，如果出現(xiàn)了不常見的索賠要求組合，則可能為欺詐，需要作進(jìn)一步的調(diào)查；在醫(yī)療方面，可找出可能的治療組合；在銀行方面，對顧客進(jìn)行分析，可以推薦感興趣的服務(wù)等等。什么是規(guī)則？規(guī)則形如如果那么(IfThen

3、),前者為條件，后者為結(jié)果。例如一個(gè)顧客，如果買了可樂，那么他也會購買果汁。如何來度量一個(gè)規(guī)則是否夠好？有兩個(gè)量，置信度(Confidence)和支持度(Support)。假設(shè)有如下表的購買記錄。 置信度置信度表示了這條規(guī)則有多大程度上值得可信。設(shè)條件的項(xiàng)的集合為A,結(jié)果的集合為B。置信度計(jì)算在A中，同時(shí)也含有B的概率(即：if A ,then B的概率)。即 Confidence(AB)=P(B|A)。例如計(jì)算“如果Orange則Coke”的置信度。由于在含有“橙汁”的4條交易中，僅有2條交易含有“可樂”。其置信度為0.5。支持度支持度計(jì)算在所有的交易集中，既有A又有B的概率。例如在5條記錄

4、中，既有橙汁又有可樂的記錄有2條。則此條規(guī)則的支持度為 2/5=0.4，即Support(AB)=P(AB)。現(xiàn)在這條規(guī)則可表述為，如果一個(gè)顧客購買了橙汁,則有50%(置信度)的可能購買可樂。而這樣的情況（即買了橙汁會再買可樂）會有40%(支持度)的可能發(fā)生。 定義1 項(xiàng)目與項(xiàng)集設(shè)I=i1,i2,im是m個(gè)不同項(xiàng)目的集合，每個(gè)ik(k=1，2，m)稱為一個(gè)項(xiàng)目(Item)。項(xiàng)目的集合 I 稱為項(xiàng)目集合(Itemset)，簡稱為項(xiàng)集。其元素個(gè)數(shù)稱為項(xiàng)集的長度，長度為k的項(xiàng)集稱為k-項(xiàng)集(k-Itemset)。l定義2 交易l每筆交易T(Transaction)是項(xiàng)集I上的一個(gè)子集，即TI，但通常

5、TI。l對應(yīng)每一個(gè)交易有一個(gè)唯一的標(biāo)識交易號，記作TIDl交易的全體構(gòu)成了交易數(shù)據(jù)庫D，或稱交易記錄集D，簡稱交易集D。l交易集D中包含交易的個(gè)數(shù)記為|D|。 l定義3 項(xiàng)集的支持度l對于項(xiàng)集X，XI，設(shè)定count(XT)為交易集D中包含X的交易的數(shù)量l項(xiàng)集X的支持度support(X)就是項(xiàng)集X出現(xiàn)的概率，從而描述了X的重要性。 |D|T)count(Xsupport(X)定義4 項(xiàng)集的最小支持度與頻繁集發(fā)現(xiàn)關(guān)聯(lián)規(guī)則要求項(xiàng)集必須滿足的最小支持閾值，稱為項(xiàng)集的最小支持度(Minimum Support)，記為supmin。支持度大于或等于supmin的項(xiàng)集稱為頻繁項(xiàng)集，簡稱頻繁集，反之則稱為

6、非頻繁集。通常k-項(xiàng)集如果滿足supmin，稱為k-頻繁集，記作Lk。定義5 關(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)則(Association Rule)可以表示為一個(gè)蘊(yùn)含式： R：XY 其中：XI，YI，并且XY= 。例如：R：牛奶面包定義6 關(guān)聯(lián)規(guī)則的支持度對于關(guān)聯(lián)規(guī)則R：XY，其中XI，YI，并且XY=。規(guī)則R的的支持度(Support)是交易集中同時(shí)包含X和Y的交易數(shù)與所有交易數(shù)之比。 |D|Y)count(XY)support(X定義7 關(guān)聯(lián)規(guī)則的置信度對于關(guān)聯(lián)規(guī)則R：XY，其中XI,YI，并且XY=。規(guī)則R的置信度(Confidence)是指包含X和Y的交易數(shù)與包含X的交易數(shù)之比 support(X)Y)

7、support(XY)(X confidence一般來說，只有支持度和置信度均較高的關(guān)聯(lián)規(guī)則才是用戶感興趣的、有用的關(guān)聯(lián)規(guī)則。定義8 關(guān)聯(lián)規(guī)則的最小支持度和最小置信度關(guān)聯(lián)規(guī)則的最小支持度也就是衡量頻繁集的最小支持度(Minimum Support)，記為supmin，它用于衡量規(guī)則需要滿足的最低重要性。關(guān)聯(lián)規(guī)則的最小置信度(Minimum Confidence)記為confmin，它表示關(guān)聯(lián)規(guī)則需要滿足的最低可靠性。定義9 強(qiáng)關(guān)聯(lián)規(guī)則如果規(guī)則R:XY滿足support(XY)supmin且confidence(XY)confmin，稱關(guān)聯(lián)規(guī)則XY為強(qiáng)關(guān)聯(lián)規(guī)則，否則稱關(guān)聯(lián)規(guī)則XY為弱關(guān)聯(lián)規(guī)則。在

8、挖掘關(guān)聯(lián)規(guī)則時(shí)，產(chǎn)生的關(guān)聯(lián)規(guī)則要經(jīng)過supmin和confmin的衡量，篩選出來的強(qiáng)關(guān)聯(lián)規(guī)則才能用于指導(dǎo)商家的決策。對于規(guī)則 AC：支持度 = support(A,C ) = 50%置信度 = support(A,C )/support(A) = 66.6%交易ID購買商品2000A,B,C1000A,C4000A,D5000B,E,F假設(shè)最小值支持度為假設(shè)最小值支持度為50%，最小置信度為，最小置信度為50%規(guī)則規(guī)則AC滿足最小支持度和最小置信滿足最小支持度和最小置信度，所以它是度，所以它是強(qiáng)關(guān)聯(lián)規(guī)則強(qiáng)關(guān)聯(lián)規(guī)則l關(guān)聯(lián)規(guī)則挖掘是一個(gè)兩步的過程：關(guān)聯(lián)規(guī)則挖掘是一個(gè)兩步的過程：l找出所有找出所有頻

9、繁項(xiàng)集頻繁項(xiàng)集l由頻繁項(xiàng)集產(chǎn)生由頻繁項(xiàng)集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則強(qiáng)關(guān)聯(lián)規(guī)則，這些規(guī)則必須大于，這些規(guī)則必須大于或者等于最小支持度和最小置信度或者等于最小支持度和最小置信度大于或者等于最小支持度大于或者等于最小支持度的項(xiàng)集的項(xiàng)集AprioriApriori算法算法Apriori算法是一種經(jīng)典的生成布爾型關(guān)聯(lián)規(guī)則的頻繁項(xiàng)集挖掘算法。Apriori算法將發(fā)現(xiàn)關(guān)聯(lián)規(guī)則的過程分為兩個(gè)步驟：通過迭代，檢索出事務(wù)數(shù)據(jù)庫中的所有頻繁項(xiàng)集，即支持度不低于用戶設(shè)定的閾值的項(xiàng)集；利用頻繁項(xiàng)集構(gòu)造出滿足用戶最小置信度的規(guī)則。挖掘或識別出所有頻繁項(xiàng)集是該算法的核心，占整個(gè)計(jì)算量的大部分。 AprioriApriori算法的重要性

10、質(zhì)算法的重要性質(zhì)性質(zhì)1：頻繁項(xiàng)集的子集必為頻繁項(xiàng)集性質(zhì)2：非頻繁項(xiàng)集的超集一定是非頻繁的假設(shè)項(xiàng)集假設(shè)項(xiàng)集A,CA,C是頻繁項(xiàng)集，則是頻繁項(xiàng)集，則AA和和CC也為頻繁項(xiàng)集也為頻繁項(xiàng)集假設(shè)項(xiàng)集假設(shè)項(xiàng)集DD不是頻繁項(xiàng)集，則不是頻繁項(xiàng)集，則A,DA,D和和C,DC,D也不是頻繁項(xiàng)集也不是頻繁項(xiàng)集AprioriApriori算法舉例算法舉例現(xiàn)有A、B、C、D、E五種商品的交易記錄表，找出所有頻繁項(xiàng)集，假設(shè)最小支持度=50%,最小置信度=50%AprioriApriori算法舉例算法舉例_ _產(chǎn)生頻繁項(xiàng)集產(chǎn)生頻繁項(xiàng)集K=1支持度50A50%50%B75%75%C75%75%E75%75%L1項(xiàng)集項(xiàng)集支持度

11、支持度A,B25%25%A,C50%50%A,EA,E25%25%B,C50%50%B,E75%75%C,E50%50%C2 2K=2支持度50支持度50A,C50%50%B,C50%50%B,E75%75%C,E50%50%L2AprioriApriori算法舉例算法舉例_ _產(chǎn)生頻繁項(xiàng)集產(chǎn)生頻繁項(xiàng)集A,C50%50%B,C50%50%B,E75%75%C,E50%50%L2支持度50支持度50AprioriApriori算法舉例算法舉例_ _產(chǎn)生關(guān)聯(lián)規(guī)則產(chǎn)生關(guān)聯(lián)規(guī)則對于頻繁項(xiàng)集B,C,E,它的非空子集有B、C、E、B,C、B,E、C,E。以下就是據(jù)此獲得的關(guān)聯(lián)規(guī)則及其置信度。規(guī)則規(guī)則置信度置信度ConfidenceConfidenceBCE66.7%CBE66.7%EBC66.7%C