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

1、關(guān)聯(lián)規(guī)則簡(jiǎn)介關(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ù)測(cè)到。首先被 Agrawal, Imielinski and Swami在 1993年的 SIGMOD會(huì)議上提出.關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘中最活躍的研究方法之一 。典型的關(guān)聯(lián)規(guī)則發(fā)現(xiàn)問題是對(duì)超市中的購(gòu)物籃數(shù) 據(jù)(Market Basket)進(jìn)行分析。通過發(fā)現(xiàn)顧客放 入購(gòu)物籃中的不同商品之間的關(guān)系來分析顧客的購(gòu) 頭習(xí)慣。案例“尿布與啤酒”的故事。美國(guó)的沃爾瑪超市對(duì)一年多的原始交易數(shù)據(jù)進(jìn)行了詳細(xì)的 分

2、析，得到一個(gè)意外發(fā)現(xiàn)：與尿布一起被購(gòu)買最多的商品竟然是啤酒。借助于數(shù)據(jù)倉(cāng)庫(kù)和關(guān)聯(lián)規(guī)則，商家發(fā)現(xiàn)了這個(gè)隱藏在背后的事實(shí)：美國(guó)的婦女們經(jīng)常會(huì)囑咐她們的丈 夫下班以后要為孩子買尿布，而30%40%的丈夫在買完尿布之后又要順便購(gòu)買自己愛喝的啤酒。有了這個(gè)發(fā)現(xiàn)后 ,超市調(diào)整了貨架的設(shè)置，把尿布和啤酒擺放在一起銷售 ,從而大大增加了銷售額。 70%購(gòu)買了牛奶的顧客將傾向于同時(shí)購(gòu)買面包。 某網(wǎng)上書店向用戶推薦相關(guān)書籍。案例案例購(gòu)買本商品的顧客還買過數(shù)字化生存-盤數(shù)宇化生存導(dǎo)讀-互聯(lián)網(wǎng)：碎片化生存眾聲喧嘩一一網(wǎng)絡(luò)時(shí)代的公眾輿論注?。夯ヂ?lián)網(wǎng)如何毒化了長(zhǎng)尾理論zo （超級(jí)財(cái)經(jīng)世界是平的一一21世紀(jì)簡(jiǎn)-失控：全人類

3、的最終命運(yùn)商業(yè)的常識(shí)（李開 復(fù)、牛文文¥22.80更多Nim?。〝?shù)字化生存案例在買了一臺(tái)PC之后下一步會(huì)購(gòu)買?辰呂（Acer ） VX275臺(tái)式電腦（E67案例案例瀏費(fèi)了該曲品的用戶還瀏賢了案例K10U立怎臣至列漫步古Udif： &r）咅福B101V入i強(qiáng)系列VOLEl-PAD）黒色比 標(biāo)墊專洪）環(huán)宇飛揚(yáng)Hying） V6無甌：呱您頭碩關(guān)科（SWUC）耳機(jī)M-2102飛利浦（FI訂gs） SPA1312罷色案例在保險(xiǎn)業(yè)務(wù)方面，如果出現(xiàn)了不常見的索賠要求組 合，則可能為欺詐，需要作進(jìn)一步的調(diào)查；在醫(yī)療方面，可找出可能的治療組合；在銀行方面，對(duì)顧客進(jìn)行分析，可以推薦感興趣的 服務(wù)

4、等等。關(guān)聯(lián)規(guī)則基本模型什么是規(guī)則？規(guī)則形如”如果那么(lf.Thg.J,前者為條件，后者 為結(jié)果。例如一個(gè)顧客，如果買了可樂，那么他也會(huì)購(gòu)買 果汁。如何來度量一個(gè)規(guī)則是否夠好？有兩個(gè)量，置信度(Confidence)支持度(Support) 假設(shè)有如下表的購(gòu)買記錄。關(guān)聯(lián)規(guī)則基本模型一置信度顧客項(xiàng)目1橙汁，可樂2牛奶，橙汁，空氣清潔器3橙汁，洗潔精4橙汁，洗潔精，可樂5空氣清潔器置信度表示了這條規(guī)則有多大程度上值得可信。設(shè)條件的項(xiàng)的集合為代結(jié)果的集合為B。置信度計(jì)算在A中，同時(shí)也含有B的概率醱：if A,then B的概率。即Co n fide nee (A B)=P(B/A)。例如計(jì)算如果 O

5、range 則Coke”的置信度。由于在含有“橙汁”的4條交易中，僅有2條交易含有“可樂” o其置信度為0.5。關(guān)聯(lián)規(guī)則基本模型支持度顧客項(xiàng)目1橙汁，可樂2牛奶，橙汁，空氣清潔器3橙汁，洗潔精4橙汁，洗潔精，可樂5空氣清潔器支持度計(jì)算在所有的交易集中，既有A又有B的概率。例 如在5條記錄中，既有橙汁又有可樂的記錄有2條。則此 條規(guī)則的支持度為 2/5=0.4, Support（AB）=P（AB）.現(xiàn)在這條規(guī)則可表述為，如果一個(gè)顧客購(gòu)買了橙汁，則有 50%（置信度）的可能購(gòu)買可樂。而這樣的情況（即買了橙 汁會(huì)再買可樂）會(huì)有40%（支持度）的可能發(fā)生。關(guān)聯(lián)規(guī)則的相關(guān)概念定義1項(xiàng)目與項(xiàng)集設(shè)l=il是

6、m個(gè)不同項(xiàng)目的集合,每個(gè)ik(k=l, 2, ,m)稱為一個(gè)項(xiàng)目(Item)。項(xiàng)目的集合I稱為項(xiàng)目集合(Itemset),簡(jiǎn)稱為項(xiàng)集 。其元素個(gè)數(shù)稱為項(xiàng)集的長(zhǎng)度，長(zhǎng)度為k的項(xiàng)集稱 為 k-項(xiàng)集(k-ltemset)o關(guān)聯(lián)規(guī)則的相關(guān)概念定義2交易每筆交易丁仃ransaction）是項(xiàng)集I上的一個(gè)子集， 即Td，但通常Tul。對(duì)應(yīng)每交易有唯一的標(biāo)識(shí)交易號(hào)，記作TID交易的全體構(gòu)成了交易數(shù)據(jù)庫(kù)D,或稱交易記錄 集D,簡(jiǎn)稱交易集D。交易集D中包含交易的個(gè)數(shù)記為|D|。關(guān)聯(lián)規(guī)則的相關(guān)概念定義3項(xiàng)集的支持度對(duì)于項(xiàng)集X, Xul,設(shè)定count(XcT)為交易集D中 包含X的交易的數(shù)量support(X)=

7、count(X 匸 T)IDI項(xiàng)集X的支持度support(X)就是項(xiàng)集X出現(xiàn)的概率, 從而描述了 X的重要性。定義4項(xiàng)集的最小支持度與頻繁集發(fā)現(xiàn)關(guān)聯(lián)規(guī)則要求項(xiàng)集必須滿足的最小支持閾值，稱為項(xiàng)集的最小支持度(Minimum Support),記為 Slipmino支持度大于或等于SUpmin的項(xiàng)集稱為頻繁項(xiàng)集，簡(jiǎn) 稱頻繁集，反之則稱為非頻繁集。適常kJ貢集如果滿足Slipmin?稱為k頻繁集，記作Lk。關(guān)聯(lián)規(guī)則的相關(guān)概念定義5關(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)WJ(Association Rule)可以表示為一個(gè)蘊(yùn)含式: R： XnY其中：Xul, Yul,并且XcY=。例如：R：牛奶面包關(guān)聯(lián)規(guī)則的相關(guān)概念定義6

8、關(guān)聯(lián)規(guī)則的支持度對(duì)于關(guān)聯(lián)規(guī)則R： XnY,其中Xul, Yul,并且 XcY=。規(guī)則R的的支持度(Support)是交易集中同時(shí)包含X 和Y的交易數(shù)與所有交易數(shù)之比。support (X=> Y)=count(XoY)IDI關(guān)聯(lián)規(guī)則的相關(guān)概念定義7關(guān)聯(lián)規(guī)則的置信度對(duì)于關(guān)聯(lián)規(guī)則R： XnY,其中Xul,Yul,并且XcY=。規(guī)則R的置信度(Confidence)是指包含X和丫的交易 數(shù)與包含X的交易數(shù)之比confidence (X => Y)=support(X<j Y) support(X)一般來說，只有支持度和置信度均較高的關(guān)聯(lián)規(guī)則 才是用戶感興趣的、有用的關(guān)聯(lián)規(guī)則。定義8

9、關(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)聯(lián)規(guī)則的相關(guān)概念定義9強(qiáng)關(guān)聯(lián)規(guī)則如果規(guī)則 R:XnY 滿足 support(X=>Y)>supmin 且 confidence(X=>Y)>confmin ,稱關(guān)聯(lián)規(guī)則XnY為 強(qiáng)關(guān)聯(lián)規(guī)則，否則稱關(guān)聯(lián)規(guī)則XnY為弱關(guān)聯(lián)規(guī)則。 在挖掘關(guān)聯(lián)規(guī)則時(shí)，產(chǎn)生的關(guān)聯(lián)規(guī)則要經(jīng)過 supmin和c

10、onfmin的衡量，篩選出來的強(qiáng)關(guān)聯(lián)規(guī)則 才能用于指導(dǎo)商家的決策。關(guān)聯(lián)規(guī)則挖掘舉例交易ID購(gòu)買商品頻繁項(xiàng)集支持度2000ABCA75%1000AQ1850%4000AQ©50%5000b5e5fA3C50%假設(shè)最小值支持度為50% ,最小置信度為50%對(duì)于規(guī)則A>C：支持度=support(/l,C) = 50%卜置信度=support(4,C)/support(/)二 66.6%規(guī)則4=懾 足最小支持度和最小置信 度,所以它是強(qiáng)關(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)則挖掘的步驟關(guān)聯(lián)規(guī)則挖掘是一個(gè)兩步的過程:找出所有頻繁項(xiàng)集大于或者等于最小支持度 的項(xiàng)集Fa由頻繁項(xiàng)集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則，這些規(guī)則必須大于

11、或者等于最小支持度和最小置信度Apriori 算法Apriori算法是一種經(jīng)典的生成布爾型關(guān)聯(lián)規(guī)則的頻 繁項(xiàng)集挖掘算法。Apriori算法將發(fā)現(xiàn)關(guān)聯(lián)規(guī)則的過程分為兩個(gè)步驟：通過迭代，檢索出事務(wù)數(shù)據(jù)庫(kù)中的所有頻繁項(xiàng)集, 即支持度不低于用戶設(shè)定的閾值的項(xiàng)集；利用頻繁項(xiàng)集構(gòu)造岀滿足用戶最小置信度的規(guī)則。挖掘或識(shí)別岀所有頻繁項(xiàng)集是該算法的核心，占整 個(gè)計(jì)算量的大部分。Apriori算法的重要性質(zhì)假設(shè)項(xiàng)集A,C是頻繁項(xiàng)集，則A和C也為頻繁項(xiàng)集性質(zhì)1:頻繁項(xiàng)集的子集必為頻繁項(xiàng)集性質(zhì)2：非頻繁項(xiàng)集的超集一定是非頻繁的設(shè)項(xiàng)集D不是頻繁項(xiàng)集，則A,D?nC,Dtfe不是頻繁項(xiàng)集Apriori算法舉例現(xiàn)有A、B.

12、 C、D、E五種商品的交易記錄表，找出所 有頻繁項(xiàng)集，假設(shè)最小支持度>二50%,最小置信度 >=50%交易號(hào)商品代碼T1A、C、DT2B、C、ET3A、 B、 C、 ET4B、EApriori算法舉例_產(chǎn)生頻繁項(xiàng)集項(xiàng)集支持度ClA50%B75%©75%支持度50E75%L2A，C50%B，C50%B，E75%C，E50%ftLlA50%B75%C75%E75%VK=2C2項(xiàng)集支持度支持度50A.C150%支持度50B，C50%B，E75%C，E50%AprioriM法舉例_產(chǎn)生頻繁項(xiàng)集L2A，C50%B，C50%B，E75%C，E50%從K2中求可用來計(jì)算的的三項(xiàng)集A,C

13、 +B,CA,B,CA,C +B,E超過三項(xiàng)A，C +C,EA,C, EB,C +B,EB,C, EB，C +C,EB,C, E.B，E +C,EB,C, EL3 B, C, E 50%C3支持度v501 支持度50B,C, E50%Apriori算法舉例_產(chǎn)生關(guān)聯(lián)規(guī)則對(duì)于頻繁項(xiàng)集B,C,E,它的非空子集有B、C、E 、B,C、B,E、C,EO以下就是據(jù)此獲得的關(guān)聯(lián) 規(guī)則及其置信度。規(guī)則置信度 ConfidenceBTCE66.7%CTBE66.7%ETBC66.7%CETB1BETC66.7%BCTE1置信度 5 0%（最小置信度）, 都是強(qiáng)關(guān)聯(lián)規(guī)則FP-growth 算法Jiawei Ha

14、n等人在2000年提出了一種基于FP-樹的 關(guān)聯(lián)規(guī)則挖掘算法FP_growth,它采取“分而治之” 的策略，將提供頻繁項(xiàng)目集的數(shù)據(jù)庫(kù)壓縮成一棵頻 繁模式樹（FP-樹）o僅兩次掃描數(shù)據(jù)庫(kù)。理論和實(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ī)則，這需要把一些約束 條件引入到挖掘算法中，從而篩選出符合約束條件的有用規(guī)則，提高算法 的運(yùn)行效率和用戶滿意度。»增量式關(guān)聯(lián)規(guī)則挖掘算法數(shù)據(jù)集不斷增長(zhǎng)，有新的數(shù)據(jù)加入后，重新挖掘很費(fèi)時(shí)

15、。增量式關(guān)聯(lián)規(guī)則 挖掘算法是當(dāng)數(shù)據(jù)庫(kù)變化后，在原挖掘結(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的人為50000o貌似A和B更相關(guān)Confidence(A->B) = 0.3, Confidence(A->C) = 0.2聽過歌曲A的 不喜歡歌

16、曲 B但是10W人里面有5W聽過歌曲B,有一半的用戶都喜歡歌曲B,但聽過歌曲A的人里面只有30%的人喜歡歌曲B矛盾的規(guī)則，如何評(píng)價(jià)?關(guān)聯(lián)規(guī)則價(jià)值衡量Co n fi d e n c e (A-B073Con fide nce(AC) = 0.2 Support(B)=0.5 Support(C)=300/l 00000提升度n(ABLift(A9 B)=Confidence(A B)/Support(B)=_H 丿_ p(A)p(B)引入提升度Lift,以度量此規(guī)則是否可用。它描述的是：相對(duì) 于不用規(guī)則，使用規(guī)則可以提高多少。Lift(AB) =Confidence(A->B)/Suppo

17、rt(B)=0.3/0.5=0.6Lift(A->C)=Confidence(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)行推薦，還不如不推薦， 盛1行選擇好了。關(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)：高明關(guān)聯(lián)規(guī)則挖掘算法的研究及其應(yīng)用