數(shù)據(jù)倉庫與數(shù)據(jù)挖掘技術(shù)第6章4關(guān)聯(lián)規(guī)則.ppt

2019/7/6,1,6.3 關(guān)聯(lián)算法,2019/7/6,2,購物籃分析 一個引發(fā)關(guān)聯(lián)規(guī)則挖掘的典型例子,2019/7/6,3,應(yīng)用：購物分析,市場購物分析結(jié)果將幫助商場內(nèi)商品應(yīng)如何合理擺放進行規(guī)劃設(shè)計。 其中一種策略就是將常常一起購買的商品擺放在相鄰近的位置，以方便顧客同時購買這兩件商品；如：如果顧客購買電腦的同時常也會購買一些金融管理類軟件，那么將電腦軟件擺放在電腦硬件附近顯然將有助于促進這兩種商品的銷售。 而另一種策略則是將電腦軟件與電腦硬件分別擺放在商場的兩端，這就會促使顧客在購買兩種商品時，走更多的路從而達到誘導(dǎo)他們購買更多商品的目的。比如：顧客在決定購買一臺昂貴電腦之后，在去購買相應(yīng)金融管理軟件的路上可能會看到安全系統(tǒng)軟件，這時他就有可能購買這一類軟件。 市場購物分析可以幫助商場主管確定那些物品可以進行捆綁減價銷售，如一個購買電腦的顧客很有可能購買一個捆綁減價銷售的打印機。,2019/7/6,4,關(guān)聯(lián)規(guī)則的概念,超市中客戶在購買A的同時，經(jīng)常會購買B，即A=B（關(guān)聯(lián)規(guī)則） 客戶在購買A后，隔了一段時間后會購買B（序列分析） “90%的客戶在購買面包時也會購買牛奶” “啤酒與尿布” “買外套=買鞋子” ,2019/7/6,5,關(guān)聯(lián)規(guī)則挖掘,關(guān)聯(lián)規(guī)則挖掘就是從大量的數(shù)據(jù)中挖掘出有價值描述數(shù)據(jù)項之間相互聯(lián)系的有關(guān)知識。 隨著收集和存儲在數(shù)據(jù)庫中的數(shù)據(jù)規(guī)模越來越大，人們對這些數(shù)據(jù)中挖掘相應(yīng)的關(guān)聯(lián)知識越來越有興趣。 例如：從大量的商業(yè)交易記錄中發(fā)現(xiàn)有價值的關(guān)聯(lián)知識就可幫助進行商品目錄的設(shè)計、交叉營銷或幫助進行其它有關(guān)的商業(yè)決策。 在數(shù)據(jù)挖掘的知識模式中，關(guān)聯(lián)規(guī)則是比較重要的一種。 關(guān)聯(lián)規(guī)則模式屬于描述型模式，發(fā)現(xiàn)關(guān)聯(lián)規(guī)則的算法屬于無監(jiān)督學(xué)習(xí)的方法。,2019/7/6,6,基本概念：關(guān)聯(lián)規(guī)則、支持度、置信度（P145）,設(shè)I=i1,i2,im是項目集，其中的元素im稱為項，D是全體事務(wù)的集合，事務(wù)T是I上的一個子集，集合TI，每個事務(wù)有唯一的TID標識。設(shè)X是一個項集，事務(wù)T包含X當(dāng)且僅當(dāng)XT ，關(guān)聯(lián)規(guī)則就是形如X=Y的蘊含式，其中XI，YI且XY =，X稱為規(guī)則的條件，Y稱為規(guī)則的結(jié)果。關(guān)聯(lián)規(guī)則設(shè)定兩項約束：支持度Supp和可信度Conf。 （1）支持度s：support(X=Y)=P(XY) P(XY):X和Y這兩個項目集在事務(wù)集D中同時出現(xiàn)的概率 （2）置信度c：confidence(X=Y)= P(YX) P(YX) :在出現(xiàn)項目集X的事務(wù)集D中，項目集Y也同時出現(xiàn)的概率 （3）關(guān)聯(lián)規(guī)則X=Y成立的條件是：它具有支持度，即事務(wù)集D中至少有s%的事務(wù)包含XY；它具有置信度，即事務(wù)集D中包含X的事務(wù)至少有c%同時也包含Y 強規(guī)則：滿足最小支持度閾值（minsup）和最小置信度閾值（minconf）的規(guī)則（用0%和100%之間的值而不是用0到1之間的值表示）,2019/7/6,7,什么是關(guān)聯(lián)挖掘？,關(guān)聯(lián)規(guī)則挖掘： 在交易數(shù)據(jù)、關(guān)系數(shù)據(jù)或其他信息載體中，查找存在于項目集合或?qū)ο蠹现g的頻繁模式、關(guān)聯(lián)、相關(guān)性、或因果結(jié)構(gòu)。 應(yīng)用： 購物籃分析、交叉銷售、產(chǎn)品目錄設(shè)計、聚集、分類、lossleader analysis等 舉例：規(guī)則形式：,2019/7/6,8,應(yīng)用：進行關(guān)聯(lián)分析,2019/7/6,9,關(guān)聯(lián)的挖掘過程,挖掘關(guān)聯(lián)規(guī)則的問題的處理過程分為兩步： (1)發(fā)現(xiàn)頻繁項目集。通過用戶給定的最小支持度尋找所有頻繁項集，即找出所有支持度不低于用戶指定的最小支持度的項目集。事實上這些頻繁項目集可能具有包含關(guān)系，一般我們只關(guān)心那些不被其他頻繁項目集所包含的，所謂頻繁大項目集的集合，這些頻繁大項目集是形成關(guān)聯(lián)規(guī)則的基礎(chǔ)。 (2)生成關(guān)聯(lián)規(guī)則。通過用戶給定的最小可信度在每個最大頻繁項目集中尋找可信度不小于給定的最小可信度的關(guān)聯(lián)規(guī)則。,所有支持度大于最小支持度的項集稱為頻繁項集（頻集）,2019/7/6,10,關(guān)聯(lián)規(guī)則的優(yōu)缺點,優(yōu)點 可以產(chǎn)生清晰有用的結(jié)果； 支持間接數(shù)據(jù)挖掘； 可以處理變長的數(shù)據(jù)； 計算的消耗量是可以預(yù)見的； 缺點 當(dāng)問題變大時，計算量增長得厲害； 難以決定正確的數(shù)據(jù)； 容易忽略離群數(shù)據(jù)；,2019/7/6,11,簡單形式的關(guān)聯(lián)規(guī)則算法,幾個經(jīng)典的關(guān)聯(lián)挖掘算法 Apriori算法 抽樣算法 DIC算法 Apriori算法是最經(jīng)典的關(guān)聯(lián)規(guī)則挖掘算法，是由R.Agrawal等人于1993年首先提出的，其核心方法是基于頻集理論的遞推方法。,2019/7/6,12,Apriori算法,算法的基本思想：Apriori算法的中心思想是首先通過對事務(wù)數(shù)據(jù)庫進行掃描，找出支持度不小于最小支持度的所有項目，即頻繁1-項集。然后循環(huán)執(zhí)行以下三步： 對頻繁k-項集中的項進行連接，前提條件是前k-1項必須相同。 進行減枝，利用Apriori性質(zhì)對連接后的項目集進行篩選，刪除那些子集不是頻繁集的項目集，得出候選(k+1)-項集。 對數(shù)據(jù)庫進行掃描，計算候選項的支持度，從候選集中刪除支持度小于最小支持度的候選項，進而得出頻繁(k+1)-項集。依此類推，直到不能找到頻繁項集為止，也即頻繁k-項集為空。,2019/7/6,13,Apriori核心算法表示,輸入：事務(wù)數(shù)據(jù)庫D，最小支持度閾值minsup。 輸出：D中的頻繁項集L。 (1) 在第一次掃描中，對D中每一個數(shù)據(jù)項計算其支持度，確定出滿足最小支持度的1頻繁項集集合L1。 (2) 利用已經(jīng)生成的Lk -1自身連接，得到候選k項集的集合Ck。 (3) 然后掃描數(shù)據(jù)庫，計算這些候選集的支持度。 (4) 對候選k項集Ck進行剪枝。掃描Ck，計算這些候選項集的支持度，刪除支持度低于用戶給定最小支持度閾值minsup的項目集，最后，生成所有長度為k的頻繁項集Lk。 (5) 重復(fù)(2)(4)，直到Lk為空。 (6) 對L1到Lk取并集，即為最終的頻繁集L。,2019/7/6,14,Apriori算法例子,【例1】假設(shè)數(shù)據(jù)庫中有9個事務(wù)，即D=9，Apriori假定事務(wù)中的項按字典次序存放。利用Apriori算法尋找D中的頻繁項集。,事務(wù)集合D,首先掃描D，對每個候選項計數(shù)得到候選1項集的集合C1,候選1項集的集合C1,2019/7/6,15,候選1項集的集合C1,將支持度計數(shù)結(jié)果與最小支持度進行比較，保留滿足最小支持度的項，得到頻繁1項的集合L1。,頻繁1項集的集合L1,設(shè)最小支持度閾值為20（即在9行中，至少出現(xiàn)兩次）,2019/7/6,16,事務(wù)集合D,繼續(xù)掃描D，產(chǎn)生候選2項集的集合C2，并對每個候選項計數(shù),候選2項集的集合C2,2019/7/6,17,將支持度計數(shù)結(jié)果與最小支持度進行比較，保留滿足最小支持度的項，得到頻繁2項的集合L2,候選2項集的集合C2,頻繁2項的集合L2,2019/7/6,18,事務(wù)集合D,繼續(xù)掃描D，產(chǎn)生候選3項集的集合C3，并連續(xù)剪枝，得到頻繁3項的集合L3,候選3項集的集合C3,頻繁3項的集合L3,C4=，因此算法由于無法發(fā)現(xiàn)新的項集而結(jié)束,對L1到L3取并集，即為最終的頻繁集L,2019/7/6,19,從頻繁項集產(chǎn)生關(guān)聯(lián)規(guī)則,當(dāng)從數(shù)據(jù)庫D的事務(wù)中找出頻繁項集后，很容易產(chǎn)生強關(guān)聯(lián)規(guī)則（強關(guān)聯(lián)規(guī)則滿足最小支持度和最小置信度）。對于置信度，可以用下式來計算，其中條件概率用項集支持度計數(shù)表示。,根據(jù)該式，關(guān)聯(lián)規(guī)則可以產(chǎn)生如下：,support_count(XY)是包含項集XY的事務(wù)數(shù)support_count(X)是包含項集X的事務(wù)數(shù),(1) 對于每個頻繁項集l，產(chǎn)生l的所有非空子集； (2) 對于l的每個非空子集，如果 則輸出規(guī)則 其中，minconf是最小置信度閾值。,2019/7/6,20,【例】基于例1的事務(wù)數(shù)據(jù)庫，假定數(shù)據(jù)包含頻繁項集，設(shè)最小置信度閾值為70%。試根據(jù)以上關(guān)聯(lián)規(guī)則原理，產(chǎn)生強規(guī)則。,2,2019/7