關(guān)聯(lián)規(guī)則與關(guān)聯(lián)分析ppt課件

1、1.2摘要關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘中成果頗豐而且比較活躍的研究分支。本章主要介紹了關(guān)聯(lián)規(guī)則挖掘的基本概念及其分類，以單維單層布爾關(guān)聯(lián)規(guī)則的挖掘理論為切入點(diǎn)，介紹關(guān)聯(lián)規(guī)則挖掘理論模型以及算法方面的內(nèi)容，并簡(jiǎn)單扼要介紹了多層關(guān)聯(lián)規(guī)則挖掘、多維關(guān)聯(lián)規(guī)則挖掘的相關(guān)內(nèi)容，最后通過一個(gè)實(shí)例給出了關(guān)聯(lián)分析的醫(yī)學(xué)應(yīng)用。3什么是關(guān)聯(lián)規(guī)則挖掘？關(guān)聯(lián)規(guī)則挖掘： 從事務(wù)數(shù)據(jù)庫(kù)，關(guān)系數(shù)據(jù)庫(kù)和其他信息存儲(chǔ)中的大量數(shù)據(jù)的項(xiàng)集之間發(fā)現(xiàn)有趣的、頻繁出現(xiàn)的模式、關(guān)聯(lián)和相關(guān)性。應(yīng)用： 購(gòu)物籃分析、分類設(shè)計(jì)、捆綁銷售等4“尿布與啤酒”典型關(guān)聯(lián)分析案例采用關(guān)聯(lián)模型比較典型的案例是“尿布與啤酒”的故事。在美國(guó)，一些年輕的父親下班后經(jīng)常要到

2、超市去買嬰兒尿布，超市也因此發(fā)現(xiàn)了一個(gè)規(guī)律，在購(gòu)買嬰兒尿布的年輕父親們中，有30%40%的人同時(shí)要買一些啤酒。超市隨后調(diào)整了貨架的擺放，把尿布和啤酒放在一起，明顯增加了銷售額。同樣的，我們還可以根據(jù)關(guān)聯(lián)規(guī)則在商品銷售方面做各種促銷活動(dòng)。5購(gòu)物籃分析如果問題的全域是商店中所有商品的集合，則對(duì)每種商品都可以用一個(gè)布爾量來表示該商品是否被顧客購(gòu)買，則每個(gè)購(gòu)物籃都可以用一個(gè)布爾向量表示；而通過分析布爾向量則可以得到商品被頻繁關(guān)聯(lián)或被同時(shí)購(gòu)買的模式，這些模式就可以用關(guān)聯(lián)規(guī)則表示（0001001100，這種方法丟失了什么信息？）關(guān)聯(lián)規(guī)則的兩個(gè)興趣度度量 支持度 置信度%60%,2sup) ,( ) ,(

3、confidenceportsoftwareXbuyscomputerXbuys6關(guān)聯(lián)（association）：兩個(gè)或多個(gè)變量的取值之間存在某種規(guī)律性。關(guān)聯(lián)規(guī)則（association rule）：指在同一個(gè)事件中出現(xiàn)的不同項(xiàng)的相關(guān)性。關(guān)聯(lián)分析（association analysis）：用于發(fā)現(xiàn)隱藏在大型數(shù)據(jù)集中的令人感興趣的聯(lián)系。所發(fā)現(xiàn)的聯(lián)系可以用關(guān)聯(lián)規(guī)則或者頻繁項(xiàng)集的形式表示。關(guān)聯(lián)規(guī)則挖掘就是從大量的數(shù)據(jù)中挖掘出描述數(shù)據(jù)項(xiàng)之間相互聯(lián)系的有價(jià)值的有關(guān)知識(shí)。應(yīng)用：購(gòu)物籃分析、生物信息學(xué)、醫(yī)療診斷、Web挖掘、科學(xué)數(shù)據(jù)分析、分類設(shè)計(jì)、捆綁銷售和虧本銷售分析7購(gòu)物籃事務(wù)的例子TID項(xiàng)集1面包，

4、牛奶2面包，尿布，啤酒，雞蛋3牛奶，尿布，啤酒，可樂4面包，牛奶，尿布，啤酒5面包，牛奶，尿布，可樂8第一節(jié) 關(guān)聯(lián)規(guī)則基本概念和關(guān)聯(lián)規(guī)則挖掘分類關(guān)聯(lián)規(guī)則的基本概念關(guān)聯(lián)規(guī)則挖掘的基本過程與分類9關(guān)聯(lián)規(guī)則的基本概念令I(lǐng)=i1， i2， ，id是購(gòu)物籃數(shù)據(jù)中所有項(xiàng)的集合，而T=t1， t2， ，tn是所有事務(wù)的集合。每個(gè)事務(wù)ti包含的項(xiàng)集都是I的子集。在關(guān)聯(lián)分析中，包含0個(gè)或者多個(gè)項(xiàng)的集合被稱為項(xiàng)集（itemset）如果一個(gè)項(xiàng)集包含k個(gè)項(xiàng)，則稱它為k-項(xiàng)集。例如啤酒，尿布，牛奶是一個(gè)3-項(xiàng)集?？占侵覆话魏雾?xiàng)的項(xiàng)集。10事務(wù)的寬度定義為事務(wù)中出現(xiàn)項(xiàng)的個(gè)數(shù)。如果項(xiàng)集X是事務(wù)tj的子集，則稱事務(wù)tj

5、包含項(xiàng)集X。項(xiàng)集的一個(gè)重要性質(zhì)就是它的支持度計(jì)數(shù)，即包含特定項(xiàng)集的事務(wù)個(gè)數(shù)，數(shù)學(xué)上，項(xiàng)集X的支持度計(jì)數(shù)（X）可以表示為： （X）=|ti|Xti，tiT|11關(guān)聯(lián)規(guī)則是形如XY的蘊(yùn)含表達(dá)式，其中X和Y是不相交的項(xiàng)集。關(guān)聯(lián)規(guī)則的強(qiáng)度可以用它的支持度（support）和置信度（confidence）度量。支持度確定了規(guī)則可以用于給定數(shù)據(jù)集的頻繁程度，而置信度確定了Y包含X的事務(wù)中出現(xiàn)的頻繁程度。12規(guī)則度量：支持度和置信度Customerbuys diaperCustomerbuys bothCustomerbuys beer對(duì)所有滿足最小支持度和置信度的關(guān)聯(lián)規(guī)則 支持度s是指事務(wù)集D中包含 的百

6、分比 置信度c是指D中包含A的事務(wù)同時(shí)也包含B的百分比假設(shè)最小支持度為50%，最小置信度為50%，則有如下關(guān)聯(lián)規(guī)則 A C (50%, 66.6%) C A (50%, 100%)BA)( )(supBAPBAport)(/ )()|( )( APBAPABPBAconfidence13關(guān)聯(lián)規(guī)則挖掘的基本過程與分類關(guān)聯(lián)規(guī)則挖掘的基本過程關(guān)聯(lián)規(guī)則挖掘的分類14關(guān)聯(lián)規(guī)則挖掘的基本過程給定事務(wù)的集合T，關(guān)聯(lián)規(guī)則發(fā)現(xiàn)是指找出支持度大于等于minsup，并且置信度大于等于minconf的所有規(guī)則，其中minsup和minconf是對(duì)應(yīng)的支持度和置信度的閾值。15原始關(guān)聯(lián)規(guī)則挖掘方法：計(jì)算每一個(gè)可能規(guī)則的

7、支持度和置信度。但是這種方法由于過高的代價(jià)而讓人望而卻步。16關(guān)聯(lián)規(guī)則挖掘任務(wù)的步驟找出所有頻繁項(xiàng)集：其目標(biāo)是發(fā)現(xiàn)滿足最小支持度閾值的所有項(xiàng)集，這些項(xiàng)集稱作頻繁項(xiàng)集（frequent itemset）由頻繁項(xiàng)集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則：其目標(biāo)是從上一步發(fā)現(xiàn)的頻繁項(xiàng)集中提取所有高置信度的規(guī)則，這些規(guī)則稱作強(qiáng)規(guī)則（strong rule）17關(guān)聯(lián)規(guī)則挖掘分類 (1)關(guān)聯(lián)規(guī)則有多種分類： 根據(jù)規(guī)則中所處理的值類型 布爾關(guān)聯(lián)規(guī)則 量化關(guān)聯(lián)規(guī)則（規(guī)則描述的是量化的項(xiàng)或?qū)傩蚤g的關(guān)聯(lián)性） 根據(jù)規(guī)則中涉及的數(shù)據(jù)維 單維關(guān)聯(lián)規(guī)則 （僅涉及buys這個(gè)維） 多維關(guān)聯(lián)規(guī)則) ,( ) 48.42 ,( ) 39.30 ,(

8、computerXbuyskkXincomeXage) ,( ) ,( softwareXbuyscomputerXbuyssoftwaremanagementfinancialcomputer_18關(guān)聯(lián)規(guī)則挖掘分類 (2) 根據(jù)規(guī)則集所涉及的抽象層 單層關(guān)聯(lián)規(guī)則 多層關(guān)聯(lián)規(guī)則 （在不同的抽象層發(fā)現(xiàn)關(guān)聯(lián)規(guī)則） 根據(jù)關(guān)聯(lián)挖掘的各種擴(kuò)充 挖掘最大的頻繁模式（該模式的任何真超模式都是非頻繁的） 挖掘頻繁閉項(xiàng)集（一個(gè)項(xiàng)集c是頻繁閉項(xiàng)集，如果不存在其真超集c，使得每個(gè)包含c的事務(wù)也包含c） （最大的頻繁模式和頻繁閉項(xiàng)集可以用來減少挖掘中產(chǎn)生的頻繁項(xiàng)集）) _ ,( ) 39.30 ,( computer

9、laptopXbuysXage) ,( ) 39.30 ,( computerXbuysXage19由事務(wù)數(shù)據(jù)庫(kù)挖掘單維布爾關(guān)聯(lián)規(guī)則最簡(jiǎn)單的關(guān)聯(lián)規(guī)則挖掘，即單維、單層、布爾關(guān)聯(lián)規(guī)則的挖掘。Transaction ID Items Bought2000A,B,C1000A,C4000A,D5000B,E,FFrequent Itemset SupportA75%B50%C50%A,C50%最小支持度 50%最小置信度 50%對(duì)規(guī)則A C，支持度 =50%置信度%6 .66)(sup/ )(sup)(/ )()|( )( AportCAportAPCAPACPCAconfidence)( )(su

10、pCAPCAport20Apriori算法 (1)Apriori算法是挖掘布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)集的算法Apriori算法利用的是Apriori性質(zhì)：頻繁項(xiàng)集的所有非空子集也必須是頻繁的。 模式不可能比A更頻繁的出現(xiàn) Apriori算法是反單調(diào)的，即一個(gè)集合如果不能通過測(cè)試，則該集合的所有超集也不能通過相同的測(cè)試。 Apriori性質(zhì)通過減少搜索空間，來提高頻繁項(xiàng)集逐層產(chǎn)生的效率BA21Apriori算法 (2)Apriori算法利用頻繁項(xiàng)集性質(zhì)的先驗(yàn)知識(shí)（prior knowledge），通過逐層搜索的迭代方法，即將k-項(xiàng)集用于探察(k+1)-項(xiàng)集，來窮盡數(shù)據(jù)集中的所有頻繁項(xiàng)集。 先找到頻繁1-

11、項(xiàng)集集合L1,然后用L1找到頻繁2-項(xiàng)集集合L2，接著用L2找L3，直到找不到頻繁k-項(xiàng)集，找每個(gè)Lk需要一次數(shù)據(jù)庫(kù)掃描。22Apriori算法步驟Apriori算法由連接連接和剪枝剪枝兩個(gè)步驟組成。連接：連接：為了找Lk，通過Lk-1與自己連接產(chǎn)生候選k-項(xiàng)集的集合，該候選候選k項(xiàng)集項(xiàng)集記為Ck。 Lk-1中的兩個(gè)元素L1和L2可以執(zhí)行連接操作 的條件是Ck是Lk的超集，即它的成員可能不是頻繁的，但是所有頻繁的k-項(xiàng)集都在Ck中（為什么？）。因此可以通過掃描數(shù)據(jù)庫(kù)，通過計(jì)算每個(gè)k-項(xiàng)集的支持度來得到Lk 。 為了減少計(jì)算量，可以使用Apriori性質(zhì)，即如果一個(gè)k-項(xiàng)集的(k-1)-子集不在

12、Lk-1中，則該候選不可能是頻繁的，可以直接從Ck刪除。)1 1()22(.)22()1 1 (21212121klklklklllll21ll 23Apriori算法示例Database TDB1st scanC1L1L2C2C22nd scanC3L33rd scanTidItems10A, C, D20B, C, E30A, B, C, E40B, EItemsetsupA2B3C3D1E3ItemsetsupA2B3C3E3ItemsetA, BA, CA, EB, CB, EC, EItemsetsupA, B1A, C2A, E1B, C2B, E3C, E2ItemsetsupA

13、, C2B, C2B, E3C, E2ItemsetB, C, EItemsetsupB, C, E2最小支持計(jì)數(shù)：224使用Apiori性質(zhì)由L2產(chǎn)生C31 連接：C3=L2 L2= A,C,B,C,B,EC,E A,C,B,C,B,EC,E = A,B,C,A,C,E,B,C,E2使用Apriori性質(zhì)剪枝：頻繁項(xiàng)集的所有子集必須是頻繁的，對(duì)候選項(xiàng)C3，我們可以刪除其子集為非頻繁的選項(xiàng)：A,B,C的2項(xiàng)子集是A,B,A,C,B,C，其中A,B不是L2的元素，所以刪除這個(gè)選項(xiàng)；A,C,E的2項(xiàng)子集是A,C,A,E,C,E，其中A,E 不是L2的元素，所以刪除這個(gè)選項(xiàng)；B,C,E的2項(xiàng)子集是B

14、,C,B,E,C,E，它的所有2項(xiàng)子集都是L2的元素，因此保留這個(gè)選項(xiàng)。3這樣，剪枝后得到C3=B,C,E25由頻繁項(xiàng)集產(chǎn)生關(guān)聯(lián)規(guī)則同時(shí)滿足最小支持度和最小置信度的才是強(qiáng)關(guān)聯(lián)規(guī)則，從頻繁項(xiàng)集產(chǎn)生的規(guī)則都滿足支持度要求，而其置信度則可由一下公式計(jì)算：每個(gè)關(guān)聯(lián)規(guī)則可由如下過程產(chǎn)生： 對(duì)于每個(gè)頻繁項(xiàng)集l，產(chǎn)生l的所有非空子集； 對(duì)于每個(gè)非空子集s，如果 則輸出規(guī)則“ ”)(_sup)(_sup)|()(AcountportBAcountportBAPBAconfidenceconfscountportlcountportmin_)(_sup)(_sup)(sls26多層關(guān)聯(lián)規(guī)則挖掘多層關(guān)聯(lián)規(guī)則可以分為同層關(guān)聯(lián)規(guī)則和層間關(guān)聯(lián)規(guī)則，同層關(guān)聯(lián)規(guī)則是指處于同概念層的關(guān)聯(lián)規(guī)則；層間關(guān)聯(lián)規(guī)則是指不同概念層的關(guān)聯(lián)規(guī)則。多層關(guān)聯(lián)規(guī)則基本上可以沿用“支持度-置信度”的框架，但是在設(shè)置問題上有一些要考慮的東西27統(tǒng)一的最小支持度：對(duì)于不同層次，都使用一個(gè)最小支持度。這樣對(duì)于用戶和算法實(shí)現(xiàn)來講都比較容易，