關(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ī)則挖掘的基本概念及其分類(lèi)，以單維單層布爾關(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)容，最后通過(guò)一個(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)物籃分析、分類(lèi)設(shè)計(jì)、捆綁銷(xiāo)售等.4“尿布與啤酒”典型關(guān)聯(lián)分析案例 采用關(guān)聯(lián)模型比較典型的案例是“尿布與啤酒”的故事。在美國(guó)，一些年輕的父親

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

3、) ,( ) ,( confidenceportsoftwareXbuyscomputerXbuys.6 關(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ù)分析、分類(lèi)設(shè)計(jì)、捆綁銷(xiāo)售和虧本銷(xiāo)售分析.7購(gòu)

4、物籃事務(wù)的例子.8第一節(jié) 關(guān)聯(lián)規(guī)則基本概念和關(guān)聯(lián)規(guī)則挖掘分類(lèi) 關(guān)聯(lián)規(guī)則的基本概念 關(guān)聯(lián)規(guī)則挖掘的基本過(guò)程與分類(lèi).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)的集合被稱(chēng)為項(xiàng)集（itemset） 如果一個(gè)項(xiàng)集包含k個(gè)項(xiàng)，則稱(chē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的子集，則稱(chēng)事務(wù)tj包含項(xiàng)集X。 項(xiàng)集的一個(gè)重要性質(zhì)就是它的支持度計(jì)數(shù)，即包含特定

5、項(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ì)所有滿(mǎn)足最小支持度和置信度的關(guān)聯(lián)規(guī)則 支持度s是指事務(wù)集D中包含 的百分比 置信度c是指D中包含A的事務(wù)同時(shí)也包含B的百

6、分比 假設(shè)最小支持度為50%，最小置信度為50%，則有如下關(guān)聯(lián)規(guī)則 A C (50%, 66.6%) C A (50%, 100%)BA)( )(supBAPBAport)(/ )()|( )( APBAPABPBAconfidence.13關(guān)聯(lián)規(guī)則挖掘的基本過(guò)程與分類(lèi) 關(guān)聯(lián)規(guī)則挖掘的基本過(guò)程 關(guān)聯(lián)規(guī)則挖掘的分類(lèi).14關(guān)聯(lián)規(guī)則挖掘的基本過(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ī)則的支持度和置信度。但是這種方法由于過(guò)

7、高的代價(jià)而讓人望而卻步。.16關(guān)聯(lián)規(guī)則挖掘任務(wù)的步驟 找出所有頻繁項(xiàng)集：其目標(biāo)是發(fā)現(xiàn)滿(mǎn)足最小支持度閾值的所有項(xiàng)集，這些項(xiàng)集稱(chē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ī)則稱(chēng)作強(qiáng)規(guī)則（strong rule）.17關(guān)聯(lián)規(guī)則挖掘分類(lèi) (1)關(guān)聯(lián)規(guī)則有多種分類(lèi)： 根據(jù)規(guī)則中所處理的值類(lèi)型 布爾關(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 ,( computerXbuys

8、kkXincomeXage) ,( ) ,( softwareXbuyscomputerXbuyssoftwaremanagementfinancialcomputer_.18關(guān)聯(lián)規(guī)則挖掘分類(lèi) (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)集可以用來(lái)減少挖掘中產(chǎn)生的頻繁項(xiàng)集）) _ ,( ) 39.30 ,( computerlaptopXbuysX

9、age) ,( ) 39.30 ,( computerXbuysXage.19由事務(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)( )(supCAPCApo

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

11、合L1,然后用L1找到頻繁2-項(xiàng)集集合L2，接著用L2找L3，直到找不到頻繁k-項(xiàng)集，找每個(gè)Lk需要一次數(shù)據(jù)庫(kù)掃描。.22Apriori算法步驟 Apriori算法由連接連接和剪枝剪枝兩個(gè)步驟組成。連接：連接：為了找Lk，通過(guò)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中（為什么？）。因此可以通過(guò)掃描數(shù)據(jù)庫(kù)，通過(guò)計(jì)算每個(gè)k-項(xiàng)集的支持度來(lái)得到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 scan最小支持計(jì)數(shù)：2.24使用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

13、,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,C,B,E,C,E，它的所有2項(xiàng)子集都是L2的元素，因此保留這個(gè)選項(xiàng)。3這樣，剪枝后得到C3=B,C,E.25由頻繁項(xiàng)集產(chǎn)生關(guān)聯(lián)規(guī)則 同時(shí)滿(mǎn)足最小支持度和最小置信度的才是強(qiáng)關(guān)聯(lián)規(guī)則，從頻繁項(xiàng)集產(chǎn)生的規(guī)則都滿(mǎn)足支持度要求，而其置信度則可由一下公式計(jì)算： 每個(gè)關(guān)聯(lián)規(guī)則可由如下過(guò)程產(chǎn)生： 對(duì)于每個(gè)頻繁項(xiàng)集l，產(chǎn)生l的所有非空子集； 對(duì)于每個(gè)非空子集s，如果 則輸出規(guī)則“ ”)(_sup)(_sup)|()(AcountportBAcountportBAPBAconfidenceconfscountportlcountportmin_)(_sup)(_sup)(sls.26多層關(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è)置問(wèn)題上有一些要考慮的東西.27 統(tǒng)一的最小支持度：對(duì)于不同層次，都使用一個(gè)最小支持度。這樣對(duì)于用戶(hù)和算法實(shí)現(xiàn)來(lái)講都比較容易，但是弊端也是顯然的。 遞減的最小支持度：每個(gè)