1、,大數(shù)據(jù)時(shí)代算法-關(guān)聯(lián)規(guī)則簡介,關(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會(huì)議上提出. 關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘中最活躍的研究方法之一。典型的關(guān)聯(lián)規(guī)則發(fā)現(xiàn)問題是對(duì)超市中的購物籃數(shù)據(jù)（Market Basket）進(jìn)行分析。通過發(fā)現(xiàn)顧客放入購物籃中的不同商品之間的關(guān)系來分析顧客的購買習(xí)慣。,關(guān)聯(lián)規(guī)則,“尿布與啤酒”的故事。 美國的沃爾瑪超市對(duì)一年多的原始交易數(shù)據(jù)進(jìn)行了詳細(xì)的

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

3、分析，可以推薦感興趣的服務(wù)等等。,案例,什么是規(guī)則？ 規(guī)則形如如果那么(IfThen),前者為條件，后者為結(jié)果。例如一個(gè)顧客，如果買了可樂，那么他也會(huì)購買果汁。 如何來度量一個(gè)規(guī)則是否夠好？有兩個(gè)量，置信度(Confidence)和支持度(Support)。假設(shè)有如下表的購買記錄。,關(guān)聯(lián)規(guī)則基本模型,關(guān)聯(lián)規(guī)則基本模型_置信度,置信度表示了這條規(guī)則有多大程度上值得可信。設(shè)條件的項(xiàng)的集合為A,結(jié)果的集合為B。置信度計(jì)算在A中，同時(shí)也含有B的概率(即：if A ,then B的概率)。即 Confidence(AB)=P(B|A)。例如計(jì)算“如果Orange則Coke”的置信度。由于在含有“橙汁”的

4、4條交易中，僅有2條交易含有“可樂”。其置信度為0.5。,關(guān)聯(lián)規(guī)則基本模型_支持度,支持度計(jì)算在所有的交易集中，既有A又有B的概率。例如在5條記錄中，既有橙汁又有可樂的記錄有2條。則此條規(guī)則的支持度為 2/5=0.4，即Support(AB)=P(AB)。 現(xiàn)在這條規(guī)則可表述為，如果一個(gè)顧客購買了橙汁,則有50%(置信度)的可能購買可樂。而這樣的情況（即買了橙汁會(huì)再買可樂）會(huì)有40%(支持度)的可能發(fā)生。,關(guān)聯(lián)規(guī)則的相關(guān)概念,定義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)，簡稱

5、為項(xiàng)集。其元素個(gè)數(shù)稱為項(xiàng)集的長度，長度為k的項(xiàng)集稱為k-項(xiàng)集(k-Itemset)。,關(guān)聯(lián)規(guī)則的相關(guān)概念,定義2 交易 每筆交易T(Transaction)是項(xiàng)集I上的一個(gè)子集，即TI，但通常TI。 對(duì)應(yīng)每一個(gè)交易有一個(gè)唯一的標(biāo)識(shí)交易號(hào)，記作TID 交易的全體構(gòu)成了交易數(shù)據(jù)庫D，或稱交易記錄集D，簡稱交易集D。 交易集D中包含交易的個(gè)數(shù)記為|D|。,關(guān)聯(lián)規(guī)則的相關(guān)概念,定義3 項(xiàng)集的支持度 對(duì)于項(xiàng)集X，XI，設(shè)定count(XT)為交易集D中包含X的交易的數(shù)量 項(xiàng)集X的支持度support(X)就是項(xiàng)集X出現(xiàn)的概率，從而描述了X的重要性。,關(guān)聯(lián)規(guī)則的相關(guān)概念,定義4 項(xiàng)集的最小支持度與頻繁集

6、發(fā)現(xiàn)關(guān)聯(lián)規(guī)則要求項(xiàng)集必須滿足的最小支持閾值，稱為項(xiàng)集的最小支持度(Minimum Support)，記為supmin。 支持度大于或等于supmin的項(xiàng)集稱為頻繁項(xiàng)集，簡稱頻繁集，反之則稱為非頻繁集。 通常k-項(xiàng)集如果滿足supmin，稱為k-頻繁集，記作Lk。,關(guān)聯(lián)規(guī)則的相關(guān)概念,定義5 關(guān)聯(lián)規(guī)則 關(guān)聯(lián)規(guī)則(Association Rule)可以表示為一個(gè)蘊(yùn)含式： R：XY 其中：XI，YI，并且XY= 。 例如：R：牛奶面包,關(guān)聯(lián)規(guī)則的相關(guān)概念,定義6 關(guān)聯(lián)規(guī)則的支持度 對(duì)于關(guān)聯(lián)規(guī)則R：XY，其中XI，YI，并且XY=。 規(guī)則R的的支持度(Support)是交易集中同時(shí)包含X和Y的交易數(shù)與

7、所有交易數(shù)之比。,關(guān)聯(lián)規(guī)則的相關(guān)概念,定義7 關(guān)聯(lián)規(guī)則的置信度 對(duì)于關(guān)聯(lián)規(guī)則R：XY，其中XI,YI，并且XY=。 規(guī)則R的置信度(Confidence)是指包含X和Y的交易數(shù)與包含X的交易數(shù)之比,一般來說，只有支持度和置信度均較高的關(guān)聯(lián)規(guī)則才是用戶感興趣的、有用的關(guān)聯(lián)規(guī)則。,關(guān)聯(lián)規(guī)則的相關(guān)概念,定義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ī)則需要滿足的最低可靠性。,關(guān)

8、聯(lián)規(guī)則的相關(guān)概念,定義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ī)則。 在挖掘關(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ān)聯(lián)規(guī)則挖掘舉例,對(duì)于規(guī)則 AC： 支持度 = support(A,C ) = 50% 置信度 = support(A,C )/support(A) = 66.6%,假設(shè)最小值支持度為50%，最小置信度為50%,規(guī)則AC滿足最小支持度和最小置信度，所以它是強(qiáng)關(guān)聯(lián)規(guī)則,關(guān)聯(lián)規(guī)則挖掘

9、的步驟,關(guān)聯(lián)規(guī)則挖掘是一個(gè)兩步的過程： 找出所有頻繁項(xiàng)集 由頻繁項(xiàng)集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則，這些規(guī)則必須大于或者等于最小支持度和最小置信度,大于或者等于最小支持度的項(xiàng)集,Apriori算法,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ī)則。 挖掘或識(shí)別出所有頻繁項(xiàng)集是該算法的核心，占整個(gè)計(jì)算量的大部分。,Apriori算法的重要性質(zhì),性質(zhì)1：頻繁項(xiàng)集的子集必為頻繁項(xiàng)集 性質(zhì)2：非頻繁項(xiàng)集的超集一定是非頻繁

10、的,假設(shè)項(xiàng)集A,C是頻繁項(xiàng)集，則A和C也為頻繁項(xiàng)集,假設(shè)項(xiàng)集D不是頻繁項(xiàng)集，則A,D和C,D也不是頻繁項(xiàng)集,Apriori算法舉例,現(xiàn)有A、B、C、D、E五種商品的交易記錄表，找出所有頻繁項(xiàng)集，假設(shè)最小支持度=50%,最小置信度=50%,Apriori算法舉例_產(chǎn)生頻繁項(xiàng)集,K=1,支持度50,Apriori算法舉例_產(chǎn)生頻繁項(xiàng)集,Apriori算法舉例_產(chǎn)生關(guān)聯(lián)規(guī)則,對(duì)于頻繁項(xiàng)集B,C,E,它的非空子集有B、C、E、B,C、B,E、C,E。以下就是據(jù)此獲得的關(guān)聯(lián)規(guī)則及其置信度。,置信度50%(最小置信度)， 都是強(qiáng)關(guān)聯(lián)規(guī)則,Apriori算法弊端,需要多次掃描數(shù)據(jù)表 如果頻繁集最多包含10個(gè)

11、項(xiàng)，那么就需要掃描交易數(shù)據(jù)表10遍，這需要很大的I/O負(fù)載 產(chǎn)生大量頻繁集 若有100個(gè)項(xiàng)目，可能產(chǎn)生候選項(xiàng)數(shù)目,FP-growth算法,Jiawei Han等人在2000年提出了一種基于FP-樹的關(guān)聯(lián)規(guī)則挖掘算法FP_growth，它采取“分而治之”的策略，將提供頻繁項(xiàng)目集的數(shù)據(jù)庫壓縮成一棵頻繁模式樹（FP-樹）。 僅兩次掃描數(shù)據(jù)庫。 理論和實(shí)驗(yàn)表明該算法優(yōu)于Apriori算法。,FP-growth算法,其他關(guān)聯(lián)規(guī)則挖掘算法,約束性關(guān)聯(lián)規(guī)則挖掘算法 僅設(shè)置支持度和置信度閾值，缺乏用戶控制，可能產(chǎn)生過多的規(guī)則，實(shí)際效果可能并不好。用戶關(guān)心的是某些特定的關(guān)聯(lián)規(guī)則，這需要把一些約束條件引入到挖掘算

12、法中，從而篩選出符合約束條件的有用規(guī)則，提高算法的運(yùn)行效率和用戶滿意度。 增量式關(guān)聯(lián)規(guī)則挖掘算法 數(shù)據(jù)集不斷增長，有新的數(shù)據(jù)加入后，重新挖掘很費(fèi)時(shí)。增量式關(guān)聯(lián)規(guī)則挖掘算法是當(dāng)數(shù)據(jù)庫變化后，在原挖掘結(jié)果的基礎(chǔ)上生成新的關(guān)聯(lián)規(guī)則，刪除過時(shí)的關(guān)聯(lián)規(guī)則。 多層關(guān)聯(lián)規(guī)則挖掘 ,關(guān)聯(lián)規(guī)則的價(jià)值衡量,客觀上，使用“支持度和置信度”框架可能會(huì)產(chǎn)生一些不正確的規(guī)則。只憑支持度和置信度閾值未必總能找出符合實(shí)際的規(guī)則。,例：歌曲A、歌曲C為小眾歌曲，歌曲B為口水歌，共有10萬個(gè)用戶，有200個(gè)人聽過歌曲A，這200個(gè)人里面有60個(gè)聽過口水歌B，有40個(gè)人聽過歌曲C。聽過歌曲C的人數(shù)是300，聽過口水歌B的人為500

13、00。,Confidence(AB) = 0.3，Confidence(AC) = 0.2,但是10W人里面有5W聽過歌曲B，有一半的用戶都喜歡歌曲B，但聽過歌曲A的人里面只有30%的人喜歡歌曲 B,聽過歌曲A的人不喜歡歌曲B,貌似A和B更相關(guān),矛盾的規(guī)則，如何評(píng)價(jià)？,關(guān)聯(lián)規(guī)則價(jià)值衡量,提升度,Lift(AB)=Confidence(AB)/Support(B)=,引入提升度Lift，以度量此規(guī)則是否可用。它描述的是：相對(duì)于不用規(guī)則，使用規(guī)則可以提高多少。 Lift(AB) =Confidence(AB)/Support(B)=0.3/0.5=0.6 Lift(AC)= Confidence(

14、AC)/Support(C)=0.2/(300/100000)=66.7 歌曲A與B負(fù)相關(guān)，A與C正相關(guān)。 Lift大于1，表示使用這條規(guī)則進(jìn)行推薦能提升用戶聽歌曲C的概率。 Lift小于1，則表示使用這條規(guī)則來進(jìn)行推薦，還不如不推薦，讓顧客自行選擇好了。,Confidence(AB) = 0.3 Confidence(AC) = 0.2 Support(B)=0.5 Support(C)=300/100000,關(guān)聯(lián)規(guī)則的價(jià)值衡量,主觀上，一個(gè)規(guī)則的有用與否最終取決于用戶的感覺，只有用戶才能決定規(guī)則的有效性、可行性。所以，應(yīng)該將需求和關(guān)聯(lián)規(guī)則挖掘方法緊密地結(jié)合起來。例如使用“約束性關(guān)聯(lián)規(guī)則挖掘算法”，將約束條件與算法緊密結(jié)合，既能提高數(shù)據(jù)挖掘效率，又能明確數(shù)據(jù)挖掘的目標(biāo)。,參考文獻(xiàn)： 1高明 . 關(guān)聯(lián)規(guī)則挖掘算法的研究及其應(yīng)用D.山東師范大學(xué). 2006 2李彥偉 . 基于關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘方法研究D.江南大學(xué). 2011 3肖勁橙，林子禹，毛超.關(guān)聯(lián)規(guī)則在零售商業(yè)的應(yīng)用J.