關(guān)聯(lián)規(guī)則和關(guān)聯(lián)分析

1、關(guān)于關(guān)聯(lián)規(guī)則與關(guān)聯(lián)分析第1頁，共37頁，2022年，5月20日，10點10分，星期四摘要關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘中成果頗豐而且比較活躍的研究分支。本章主要介紹了關(guān)聯(lián)規(guī)則挖掘的基本概念及其分類，以單維單層布爾關(guān)聯(lián)規(guī)則的挖掘理論為切入點，介紹關(guān)聯(lián)規(guī)則挖掘理論模型以及算法方面的內(nèi)容，并簡單扼要介紹了多層關(guān)聯(lián)規(guī)則挖掘、多維關(guān)聯(lián)規(guī)則挖掘的相關(guān)內(nèi)容，最后通過一個實例給出了關(guān)聯(lián)分析的醫(yī)學(xué)應(yīng)用。第2頁，共37頁，2022年，5月20日，10點10分，星期四什么是關(guān)聯(lián)規(guī)則挖掘？關(guān)聯(lián)規(guī)則挖掘：從事務(wù)數(shù)據(jù)庫，關(guān)系數(shù)據(jù)庫和其他信息存儲中的大量數(shù)據(jù)的項集之間發(fā)現(xiàn)有趣的、頻繁出現(xiàn)的模式、關(guān)聯(lián)和相關(guān)性。應(yīng)用：購物籃分析、分類

2、設(shè)計、捆綁銷售等第3頁，共37頁，2022年，5月20日，10點10分，星期四“尿布與啤酒”典型關(guān)聯(lián)分析案例采用關(guān)聯(lián)模型比較典型的案例是“尿布與啤酒”的故事。在美國，一些年輕的父親下班后經(jīng)常要到超市去買嬰兒尿布，超市也因此發(fā)現(xiàn)了一個規(guī)律，在購買嬰兒尿布的年輕父親們中，有30%40%的人同時要買一些啤酒。超市隨后調(diào)整了貨架的擺放，把尿布和啤酒放在一起，明顯增加了銷售額。同樣的，我們還可以根據(jù)關(guān)聯(lián)規(guī)則在商品銷售方面做各種促銷活動。第4頁，共37頁，2022年，5月20日，10點10分，星期四購物籃分析如果問題的全域是商店中所有商品的集合，則對每種商品都可以用一個布爾量來表示該商品是否被顧客購買，則

3、每個購物籃都可以用一個布爾向量表示；而通過分析布爾向量則可以得到商品被頻繁關(guān)聯(lián)或被同時購買的模式，這些模式就可以用關(guān)聯(lián)規(guī)則表示（0001001100，這種方法丟失了什么信息？）關(guān)聯(lián)規(guī)則的兩個興趣度度量支持度置信度第5頁，共37頁，2022年，5月20日，10點10分，星期四關(guān)聯(lián)（association）：兩個或多個變量的取值之間存在某種規(guī)律性。關(guān)聯(lián)規(guī)則（association rule）：指在同一個事件中出現(xiàn)的不同項的相關(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ī)則或者頻繁項集的形式表示。關(guān)聯(lián)規(guī)則挖掘就是從大

4、量的數(shù)據(jù)中挖掘出描述數(shù)據(jù)項之間相互聯(lián)系的有價值的有關(guān)知識。應(yīng)用：購物籃分析、生物信息學(xué)、醫(yī)療診斷、Web挖掘、科學(xué)數(shù)據(jù)分析、分類設(shè)計、捆綁銷售和虧本銷售分析第6頁，共37頁，2022年，5月20日，10點10分，星期四購物籃事務(wù)的例子第7頁，共37頁，2022年，5月20日，10點10分，星期四第一節(jié) 關(guān)聯(lián)規(guī)則基本概念和關(guān)聯(lián)規(guī)則挖掘分類關(guān)聯(lián)規(guī)則的基本概念關(guān)聯(lián)規(guī)則挖掘的基本過程與分類第8頁，共37頁，2022年，5月20日，10點10分，星期四關(guān)聯(lián)規(guī)則的基本概念令I(lǐng)=i1， i2， ，id是購物籃數(shù)據(jù)中所有項的集合，而T=t1， t2， ，tn是所有事務(wù)的集合。每個事務(wù)ti包含的項集都是I的子集

5、。在關(guān)聯(lián)分析中，包含0個或者多個項的集合被稱為項集（itemset）如果一個項集包含k個項，則稱它為k-項集。例如啤酒，尿布，牛奶是一個3-項集?？占侵覆话魏雾椀捻椉?。第9頁，共37頁，2022年，5月20日，10點10分，星期四事務(wù)的寬度定義為事務(wù)中出現(xiàn)項的個數(shù)。如果項集X是事務(wù)tj的子集，則稱事務(wù)tj包含項集X。項集的一個重要性質(zhì)就是它的支持度計數(shù)，即包含特定項集的事務(wù)個數(shù)，數(shù)學(xué)上，項集X的支持度計數(shù)（X）可以表示為： （X）=|ti|Xti，tiT|第10頁，共37頁，2022年，5月20日，10點10分，星期四關(guān)聯(lián)規(guī)則是形如XY的蘊含表達(dá)式，其中X和Y是不相交的項集。關(guān)聯(lián)規(guī)則的強

6、度可以用它的支持度（support）和置信度（confidence）度量。支持度確定了規(guī)則可以用于給定數(shù)據(jù)集的頻繁程度，而置信度確定了Y包含X的事務(wù)中出現(xiàn)的頻繁程度。第11頁，共37頁，2022年，5月20日，10點10分，星期四規(guī)則度量：支持度和置信度Customerbuys diaperCustomerbuys bothCustomerbuys beer對所有滿足最小支持度和置信度的關(guān)聯(lián)規(guī)則支持度s是指事務(wù)集D中包含 的百分比置信度c是指D中包含A的事務(wù)同時也包含B的百分比假設(shè)最小支持度為50%，最小置信度為50%，則有如下關(guān)聯(lián)規(guī)則A C (50%, 66.6%)C A (50%, 100

7、%)第12頁，共37頁，2022年，5月20日，10點10分，星期四關(guān)聯(lián)規(guī)則挖掘的基本過程與分類關(guān)聯(lián)規(guī)則挖掘的基本過程關(guān)聯(lián)規(guī)則挖掘的分類第13頁，共37頁，2022年，5月20日，10點10分，星期四關(guān)聯(lián)規(guī)則挖掘的基本過程給定事務(wù)的集合T，關(guān)聯(lián)規(guī)則發(fā)現(xiàn)是指找出支持度大于等于minsup，并且置信度大于等于minconf的所有規(guī)則，其中minsup和minconf是對應(yīng)的支持度和置信度的閾值。第14頁，共37頁，2022年，5月20日，10點10分，星期四原始關(guān)聯(lián)規(guī)則挖掘方法：計算每一個可能規(guī)則的支持度和置信度。但是這種方法由于過高的代價而讓人望而卻步。第15頁，共37頁，2022年，5月20日

8、，10點10分，星期四關(guān)聯(lián)規(guī)則挖掘任務(wù)的步驟找出所有頻繁項集：其目標(biāo)是發(fā)現(xiàn)滿足最小支持度閾值的所有項集，這些項集稱作頻繁項集（frequent itemset）由頻繁項集產(chǎn)生強關(guān)聯(lián)規(guī)則：其目標(biāo)是從上一步發(fā)現(xiàn)的頻繁項集中提取所有高置信度的規(guī)則，這些規(guī)則稱作強規(guī)則（strong rule）第16頁，共37頁，2022年，5月20日，10點10分，星期四關(guān)聯(lián)規(guī)則挖掘分類 (1)關(guān)聯(lián)規(guī)則有多種分類：根據(jù)規(guī)則中所處理的值類型布爾關(guān)聯(lián)規(guī)則量化關(guān)聯(lián)規(guī)則（規(guī)則描述的是量化的項或?qū)傩蚤g的關(guān)聯(lián)性）根據(jù)規(guī)則中涉及的數(shù)據(jù)維單維關(guān)聯(lián)規(guī)則（僅涉及buys這個維）多維關(guān)聯(lián)規(guī)則第17頁，共37頁，2022年，5月20日，10

9、點10分，星期四關(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)挖掘的各種擴充挖掘最大的頻繁模式（該模式的任何真超模式都是非頻繁的）挖掘頻繁閉項集（一個項集c是頻繁閉項集，如果不存在其真超集c，使得每個包含c的事務(wù)也包含c）（最大的頻繁模式和頻繁閉項集可以用來減少挖掘中產(chǎn)生的頻繁項集）第18頁，共37頁，2022年，5月20日，10點10分，星期四由事務(wù)數(shù)據(jù)庫挖掘單維布爾關(guān)聯(lián)規(guī)則最簡單的關(guān)聯(lián)規(guī)則挖掘，即單維、單層、布爾關(guān)聯(lián)規(guī)則的挖掘。最小支持度 50%最小置信度 50%對規(guī)則A C，支持度 =50%置信度第19頁，共37頁，202

10、2年，5月20日，10點10分，星期四Apriori算法 (1)Apriori算法是挖掘布爾關(guān)聯(lián)規(guī)則頻繁項集的算法Apriori算法利用的是Apriori性質(zhì)：頻繁項集的所有非空子集也必須是頻繁的。 模式不可能比A更頻繁的出現(xiàn)Apriori算法是反單調(diào)的，即一個集合如果不能通過測試，則該集合的所有超集也不能通過相同的測試。Apriori性質(zhì)通過減少搜索空間，來提高頻繁項集逐層產(chǎn)生的效率第20頁，共37頁，2022年，5月20日，10點10分，星期四Apriori算法 (2)Apriori算法利用頻繁項集性質(zhì)的先驗知識（prior knowledge），通過逐層搜索的迭代方法，即將k-項集用于探

11、察(k+1)-項集，來窮盡數(shù)據(jù)集中的所有頻繁項集。先找到頻繁1-項集集合L1,然后用L1找到頻繁2-項集集合L2，接著用L2找L3，直到找不到頻繁k-項集，找每個Lk需要一次數(shù)據(jù)庫掃描。第21頁，共37頁，2022年，5月20日，10點10分，星期四Apriori算法步驟Apriori算法由連接和剪枝兩個步驟組成。連接：為了找Lk，通過Lk-1與自己連接產(chǎn)生候選k-項集的集合，該候選k項集記為Ck。Lk-1中的兩個元素L1和L2可以執(zhí)行連接操作 的條件是Ck是Lk的超集，即它的成員可能不是頻繁的，但是所有頻繁的k-項集都在Ck中（為什么？）。因此可以通過掃描數(shù)據(jù)庫，通過計算每個k-項集的支持度

12、來得到Lk 。為了減少計算量，可以使用Apriori性質(zhì)，即如果一個k-項集的(k-1)-子集不在Lk-1中，則該候選不可能是頻繁的，可以直接從Ck刪除。第22頁，共37頁，2022年，5月20日，10點10分，星期四Apriori算法示例Database TDB1st scanC1L1L2C2C22nd scanC3L33rd scan最小支持計數(shù)：2第23頁，共37頁，2022年，5月20日，10點10分，星期四使用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使用Aprior

13、i性質(zhì)剪枝：頻繁項集的所有子集必須是頻繁的，對候選項C3，我們可以刪除其子集為非頻繁的選項：A,B,C的2項子集是A,B,A,C,B,C，其中A,B不是L2的元素，所以刪除這個選項；A,C,E的2項子集是A,C,A,E,C,E，其中A,E 不是L2的元素，所以刪除這個選項；B,C,E的2項子集是B,C,B,E,C,E，它的所有2項子集都是L2的元素，因此保留這個選項。3這樣，剪枝后得到C3=B,C,E第24頁，共37頁，2022年，5月20日，10點10分，星期四由頻繁項集產(chǎn)生關(guān)聯(lián)規(guī)則同時滿足最小支持度和最小置信度的才是強關(guān)聯(lián)規(guī)則，從頻繁項集產(chǎn)生的規(guī)則都滿足支持度要求，而其置信度則可由一下公式

14、計算：每個關(guān)聯(lián)規(guī)則可由如下過程產(chǎn)生：對于每個頻繁項集l，產(chǎn)生l的所有非空子集；對于每個非空子集s，如果 則輸出規(guī)則“ ”第25頁，共37頁，2022年，5月20日，10點10分，星期四多層關(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è)置問題上有一些要考慮的東西第26頁，共37頁，2022年，5月20日，10點10分，星期四統(tǒng)一的最小支持度：對于不同層次，都使用一個最小支持度。這樣對于用戶和算法實現(xiàn)來講都比較容易，但是弊端也是顯然的。遞減的最小支

15、持度：每個層次都有不同的最小支持度，較低層次的最小支持度相對較小。同時還可以利用上層挖掘得到的信息進(jìn)行一些過濾的工作第27頁，共37頁，2022年，5月20日，10點10分，星期四多維關(guān)聯(lián)規(guī)則挖掘數(shù)值字段被分成一些預(yù)定義的層次結(jié)構(gòu)：這些區(qū)間都是由用戶預(yù)先定義的。得出的規(guī)則也稱為靜態(tài)數(shù)量關(guān)聯(lián)規(guī)則數(shù)值字段根據(jù)數(shù)據(jù)的分布分成了一些布爾字段：每個布爾字段都表示一個數(shù)值字段的區(qū)間，落在其中為1，反之為0。這種分法是動態(tài)的，得出的規(guī)則稱為布爾數(shù)量關(guān)聯(lián)規(guī)則。第28頁，共37頁，2022年，5月20日，10點10分，星期四第29頁，共37頁，2022年，5月20日，10點10分，星期四第30頁，共37頁，2022年，5月20日，10點10分，星期四第3