數(shù)據(jù)挖掘與關聯(lián)規(guī)則學習教案

1、數(shù)據(jù)挖掘與關聯(lián)數(shù)據(jù)挖掘與關聯(lián)(gunlin)規(guī)則規(guī)則第一頁，共35頁。同商品之間的關系來分析顧客的購買(gumi)習慣。第1頁/共35頁第二頁，共35頁。把尿布和啤酒擺放在一起銷售，從而大大增加了銷售額。第2頁/共35頁第三頁，共35頁。第3頁/共35頁第四頁，共35頁。第4頁/共35頁第五頁，共35頁。第5頁/共35頁第六頁，共35頁。第6頁/共35頁第七頁，共35頁。置信度表示了這條規(guī)則有多大程度上值得可信。設條件的項的集合置信度表示了這條規(guī)則有多大程度上值得可信。設條件的項的集合為為A,結果的集合為結果的集合為B。置信度計算在。置信度計算在A中，同時也含有中，同時也含有B的概率的概率(即

2、：即：if A ,then B的概率的概率)。即。即 Confidence(AB)=P(B|A)。例如。例如(lr)計算計算“如果如果Orange則則Coke”的置信度。由于在含有的置信度。由于在含有“橙汁橙汁”的的4條交易中，僅有條交易中，僅有2條交易含有條交易含有“可樂可樂”。其置信度為。其置信度為0.5。第7頁/共35頁第八頁，共35頁。支持度計算支持度計算(j sun)在所有的交易集中，既有在所有的交易集中，既有A又有又有B的的概率。例如在概率。例如在5條記錄中，既有橙汁又有可樂的記錄有條記錄中，既有橙汁又有可樂的記錄有2條。則此條規(guī)則的支持度為條。則此條規(guī)則的支持度為 2/5=0.4

3、，即，即Support(AB)=P(AB)。現(xiàn)在這條規(guī)則可表述為，如果一個顧客購買了橙汁現(xiàn)在這條規(guī)則可表述為，如果一個顧客購買了橙汁,則有則有50%(置信度置信度)的可能購買可樂。而這樣的情況（即買了的可能購買可樂。而這樣的情況（即買了橙汁會再買可樂）會有橙汁會再買可樂）會有40%(支持度支持度)的可能發(fā)生。的可能發(fā)生。 第8頁/共35頁第九頁，共35頁。定義1 項目與項集設I=i1,i2,im是m個不同項目的集合，每個ik(k=1，2，m)稱為(chn wi)一個項目(Item)。項目的集合 I 稱為(chn wi)項目集合(Itemset)，簡稱為(chn wi)項集。其元素個數(shù)稱為(ch

4、n wi)項集的長度，長度為k的項集稱為(chn wi)k-項集(k-Itemset)。第9頁/共35頁第十頁，共35頁。l定義2 交易l每筆交易T(Transaction)是項集I上的一個子集，即TI，但通常TI。l對應(duyng)每一個交易有一個唯一的標識交易號，記作TIDl交易的全體構成了交易數(shù)據(jù)庫D，或稱交易記錄集D，簡稱交易集D。l交易集D中包含交易的個數(shù)記為|D|。 第10頁/共35頁第十一頁，共35頁。l定義3 項集的支持度l對于(duy)項集X，XI，設定count(XT)為交易集D中包含X的交易的數(shù)量l項集X的支持度support(X)就是項集X出現(xiàn)的概率，從而描述了X的重

5、要性。 |D|T)count(Xsupport(X)第11頁/共35頁第十二頁，共35頁。定義4 項集的最小支持度與頻繁集發(fā)現(xiàn)關聯(lián)規(guī)則(guz)要求項集必須滿足的最小支持閾值，稱為項集的最小支持度(Minimum Support)，記為supmin。支持度大于或等于supmin的項集稱為頻繁項集，簡稱頻繁集，反之則稱為非頻繁集。通常k-項集如果滿足supmin，稱為k-頻繁集，記作Lk。第12頁/共35頁第十三頁，共35頁。定義5 關聯(lián)規(guī)則關聯(lián)規(guī)則(Association Rule)可以表示為一個蘊含式： R：XY 其中(qzhng)：XI，YI，并且XY= 。例如：R：牛奶面包第13頁/共3

6、5頁第十四頁，共35頁。定義6 關聯(lián)規(guī)則的支持度對于關聯(lián)規(guī)則R：XY，其中XI，YI，并且XY=。規(guī)則R的的支持度(Support)是交易集中同時包含(bohn)X和Y的交易數(shù)與所有交易數(shù)之比。 |D|Y)count(XY)support(X第14頁/共35頁第十五頁，共35頁。定義7 關聯(lián)規(guī)則的置信度對于(duy)關聯(lián)規(guī)則R：XY，其中XI,YI，并且XY=。規(guī)則R的置信度(Confidence)是指包含X和Y的交易數(shù)與包含X的交易數(shù)之比 support(X)Y)support(XY)(X confidence一般來說，只有支持度和置信度均較高的關聯(lián)規(guī)則(guz)才是用戶感興趣的、有用的關聯(lián)

7、規(guī)則(guz)。第15頁/共35頁第十六頁，共35頁。定義8 關聯(lián)規(guī)則的最小支持度和最小置信度關聯(lián)規(guī)則的最小支持度也就是衡量(hng ling)頻繁集的最小支持度(Minimum Support)，記為supmin，它用于衡量(hng ling)規(guī)則需要滿足的最低重要性。關聯(lián)規(guī)則的最小置信度(Minimum Confidence)記為confmin，它表示關聯(lián)規(guī)則需要滿足的最低可靠性。第16頁/共35頁第十七頁，共35頁。定義9 強關聯(lián)規(guī)則(guz)如果規(guī)則(guz)R:XY滿足support(XY)supmin且confidence(XY)confmin，稱關聯(lián)規(guī)則(guz)XY為強關聯(lián)規(guī)則

8、(guz)，否則稱關聯(lián)規(guī)則(guz)XY為弱關聯(lián)規(guī)則(guz)。在挖掘關聯(lián)規(guī)則(guz)時，產(chǎn)生的關聯(lián)規(guī)則(guz)要經(jīng)過supmin和confmin的衡量，篩選出來的強關聯(lián)規(guī)則(guz)才能用于指導商家的決策。第17頁/共35頁第十八頁，共35頁。對于規(guī)則(guz) AC：支持度 = support(A,C ) = 50%置信度 = support(A,C )/support(A) = 66.6%交易ID購買商品2000A,B,C1000A,C4000A,D5000B,E,F假設假設(jish)(jish)最小值支持最小值支持度為度為50%50%，最小置信度為，最小置信度為50%50%規(guī)則規(guī)

9、則AC滿足最小支持度和最小置信度，滿足最小支持度和最小置信度，所以它是所以它是強關聯(lián)規(guī)則強關聯(lián)規(guī)則第18頁/共35頁第十九頁，共35頁。l關聯(lián)關聯(lián)(gunlin)(gunlin)規(guī)則挖掘是一個兩步的過程：規(guī)則挖掘是一個兩步的過程：l找出所有頻繁項集找出所有頻繁項集l由頻繁項集產(chǎn)生強關聯(lián)由頻繁項集產(chǎn)生強關聯(lián)(gunlin)(gunlin)規(guī)則，這些規(guī)則必須規(guī)則，這些規(guī)則必須大于或者等于最小支持度和最小置信度大于或者等于最小支持度和最小置信度大于或者大于或者(huzh)(huzh)等于等于最小支持度的項集最小支持度的項集第19頁/共35頁第二十頁，共35頁。Apriori算法是一種經(jīng)典的生成布爾型

10、關聯(lián)規(guī)則的頻繁項集挖掘算法。Apriori算法將發(fā)現(xiàn)關聯(lián)規(guī)則的過程分為兩個步驟：通過迭代，檢索(jin su)出事務數(shù)據(jù)庫中的所有頻繁項集，即支持度不低于用戶設定的閾值的項集；利用頻繁項集構造出滿足用戶最小置信度的規(guī)則。挖掘或識別出所有頻繁項集是該算法的核心，占整個計算量的大部分。 第20頁/共35頁第二十一頁，共35頁。性質(zhì)(xngzh)1：頻繁項集的子集必為頻繁項集性質(zhì)(xngzh)2：非頻繁項集的超集一定是非頻繁的假設假設(jish)(jish)項集項集A,CA,C是頻繁是頻繁項集，則項集，則AA和和CC也為頻繁項也為頻繁項集集假設項集假設項集D不是頻繁項集，則不是頻繁項集，則A,D和和

11、C,D也不是頻繁項集也不是頻繁項集第21頁/共35頁第二十二頁，共35頁?，F(xiàn)有A、B、C、D、E五種商品的交易記錄表，找出所有頻繁項集，假設(jish)最小支持度=50%,最小置信度=50%第22頁/共35頁第二十三頁，共35頁。K=1支持(zhch)度50A50%50%B75%75%C75%75%E75%75%L1項集項集支持度支持度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%L2第23頁/共35頁第二十四頁，共35頁

12、。A,C50%50%B,C50%50%B,E75%75%C,E50%50%L2支持度50支持度50第24頁/共35頁第二十五頁，共35頁。規(guī)則規(guī)則置信度置信度ConfidenceBCE66.7%CBE66.7%EBC66.7%CEB1BEC66.7%BCE1置信度50%(最小置信度)，都是強關聯(lián)(gunlin)規(guī)則第25頁/共35頁第二十六頁，共35頁。需要多次掃描數(shù)據(jù)表如果頻繁集最多包含10個項，那么就需要掃描交易數(shù)據(jù)表10遍，這需要很大的I/O負載產(chǎn)生大量(dling)頻繁集若有100個項目，可能產(chǎn)生候選項數(shù)目1210030100100100.1.27*10CCC第26頁/共35頁第二十七

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

14、掘算法數(shù)據(jù)集不斷增長(zngzhng)，有新的數(shù)據(jù)加入后，重新挖掘很費時。增量式關聯(lián)規(guī)則挖掘算法是當數(shù)據(jù)庫變化后，在原挖掘結果的基礎上生成新的關聯(lián)規(guī)則，刪除過時的關聯(lián)規(guī)則。多層關聯(lián)規(guī)則挖掘第29頁/共35頁第三十頁，共35頁。客觀上，使用“支持度和置信度”框架(kun ji)可能會產(chǎn)生一些不正確的規(guī)則。只憑支持度和置信度閾值未必總能找出符合實際的規(guī)則。例：歌曲(gq)A、歌曲(gq)C為小眾歌曲(gq)，歌曲(gq)B為口水歌，共有10萬個用戶，有200個人聽過歌曲(gq)A，這200個人里面有60個聽過口水歌B，有40個人聽過歌曲(gq)C。聽過歌曲(gq)C的人數(shù)是300，聽過口水歌B的人

15、為50000。Confidence(AB) = 0.3，Confidence(AC) = 0.2但是10W人里面有5W聽過歌曲B，有一半的用戶都喜歡歌曲B，但聽過歌曲A的人里面只有30%的人喜歡歌曲 B聽過歌曲A的人不喜歡歌曲B貌似A和B更相關矛盾的規(guī)則，如何評價？第30頁/共35頁第三十一頁，共35頁。Lift(AB)=Confidence(AB)/Support(B)=()( ) ( )p ABp A p B引入提升度Lift，以度量此規(guī)則是否可用。它描述的是：相對于不用規(guī)則，使用規(guī)則可以提高(t go)多少。Lift(AB) =Confidence(AB)/Support(B)=0.3/

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