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