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

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

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

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

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

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

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

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

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

9、關聯(lián)規(guī)則的最小支持度和最小置信度關聯(lián)規(guī)則的最小支持度也就是衡量頻繁集的最小支 持度(Minimum Support),記為supmin,它用于衡 量規(guī)則需要滿足的最低重要性。關聯(lián)規(guī)則的最小置信度(Minimum Confidence)記為 confmin,它表示關聯(lián)規(guī)則需要滿足的最低可靠性。關聯(lián)規(guī)則的相關概念定義9強關聯(lián)規(guī)則如果規(guī)則 R:XnY 滿足 support(X=>Y)>supmin 且 confidence(X=>Y)>confmin ,稱關聯(lián)規(guī)則XnY為 強關聯(lián)規(guī)則，否則稱關聯(lián)規(guī)則XnY為弱關聯(lián)規(guī)則。 在挖掘關聯(lián)規(guī)則時，產生的關聯(lián)規(guī)則要經過 supmin和c

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

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

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

13、 +B,CA,B,CA,C +B,E超過三項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算法舉例_產生關聯(lián)規(guī)則對于頻繁項集B,C,E,它的非空子集有B、C、E 、B,C、B,E、C,EO以下就是據(jù)此獲得的關聯(lián) 規(guī)則及其置信度。規(guī)則置信度 ConfidenceBTCE66.7%CTBE66.7%ETBC66.7%CETB1BETC66.7%BCTE1置信度 5 0%（最小置信度）, 都是強關聯(lián)規(guī)則FP-growth 算法Jiawei Ha

14、n等人在2000年提出了一種基于FP-樹的 關聯(lián)規(guī)則挖掘算法FP_growth,它采取“分而治之” 的策略，將提供頻繁項目集的數(shù)據(jù)庫壓縮成一棵頻 繁模式樹（FP-樹）o僅兩次掃描數(shù)據(jù)庫。理論和實驗表明該算法優(yōu)于Apriori算法。FP-growth 算法其他關聯(lián)規(guī)則挖掘算法約束性關聯(lián)規(guī)則挖掘算法僅設置支持度和置信度閾值，缺乏用戶控制，可能產生過多的規(guī)則，實際 效果可能并不好。用戶關心的是某些特定的關聯(lián)規(guī)則，這需要把一些約束 條件引入到挖掘算法中，從而篩選出符合約束條件的有用規(guī)則，提高算法 的運行效率和用戶滿意度。»增量式關聯(lián)規(guī)則挖掘算法數(shù)據(jù)集不斷增長，有新的數(shù)據(jù)加入后，重新挖掘很費時

15、。增量式關聯(lián)規(guī)則 挖掘算法是當數(shù)據(jù)庫變化后，在原挖掘結果的基礎上生成新的關聯(lián)規(guī)則， 刪除過時的關聯(lián)規(guī)則。多層關聯(lián)規(guī)則挖掘關聯(lián)規(guī)則的價值衡量客觀上 使用“支持度和置信度”框架可能會產生 一些不正確的規(guī)則。只憑支持度和置信度閾值未必 總能找出符合實際的規(guī)則。例：歌曲A、歌曲C為小眾歌曲，歌曲B為口水歌，共有10萬個用戶，有200個人聽過歌曲A,這200個人里面有60個聽過口水歌B,有40個人聽過歌曲C。聽過歌曲C的人數(shù)是300,聽過口水歌B的人為50000o貌似A和B更相關Confidence(A->B) = 0.3, Confidence(A->C) = 0.2聽過歌曲A的 不喜歡歌

16、曲 B但是10W人里面有5W聽過歌曲B,有一半的用戶都喜歡歌曲B,但聽過歌曲A的人里面只有30%的人喜歡歌曲B矛盾的規(guī)則，如何評價?關聯(lián)規(guī)則價值衡量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ī)則是否可用。它描述的是：相對 于不用規(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負相關，A與C正相關。Lift大于1,表示使用這條規(guī)則進行推薦能提升用戶聽歌曲C的 概率。Lift小于1,則表示使用這條規(guī)則來進行推薦，還不如不推薦， 盛1行選擇好了。關聯(lián)規(guī)則的價值衡量主觀上，一個規(guī)則的有用與否最終取決于用戶的感 覺，只有用戶才能決定規(guī)則的有效性、可行性。所以, 應該將需求和關聯(lián)規(guī)則挖掘方法緊密地結合起來。例 如使用“約束性關聯(lián)規(guī)則挖掘算法”，將約束條件與 算法緊密結合，既能提高數(shù)據(jù)挖掘效率，又能明確數(shù) 據(jù)挖掘的目標。參考文獻：高明關聯(lián)規(guī)則挖掘算法的研究及其應用