醫(yī)藥信息分析與決策-第8章關(guān)聯(lián)規(guī)則

1、主主要要規(guī)規(guī)則則應(yīng)應(yīng)用用案案例例8.1.1啤酒與尿布啤酒與尿布l 在在美美國國沃沃爾爾瑪瑪超超市市的的貨貨架架上，上，尿尿片片和和啤啤酒酒赫赫然然地地擺擺在在一一起起出出售。售。為為啥啥？l 每每逢逢周周末，末，啤啤酒酒和和尿尿片片的的銷銷量量都都很很大大l 有有孩孩子子的的家家庭庭中，中，太太太太經(jīng)經(jīng)常常囑囑咐咐丈丈夫夫下下班班后后要要買買尿尿片，片，而而丈丈夫夫們們在在買買完完尿尿片片以以后后又又順順手手買買啤啤酒酒8.1.1啤酒與尿布啤酒與尿布嘗嘗試試將將啤啤酒酒和和尿尿片片擺擺在在一一起，起，結(jié)結(jié)果果使使得得啤啤酒酒和和尿尿片片的的銷銷量量雙雙雙雙激激增，增，為為商商家家?guī)韥砹肆舜?/p>

2、大量量的的利利潤潤l 在在顧顧客客同同一一次次購購物物活活動動中，中，對對其其所所購購買買商商品品組組成成的的相相關(guān)關(guān)性性進進行行研研究究的的方方法法學(xué)學(xué)8.1.2 基本概念與規(guī)則度量l 項項目目與與項項集集:數(shù)數(shù)據(jù)據(jù)庫庫中中不不可可分分割割的的最最小小信信息息單單位，位，稱稱為為項項目，目，用用符符號號 i表表示。示。項項目目的的集集合合稱稱為為項項目目集，集，簡簡稱稱項項集。集。設(shè)設(shè)集集合合 是是項項集，集， I中中項項目目的的個個數(shù)數(shù)為為 n ，則則集集合合 稱稱為為 n -項項集。集。例例如，如，集集合合啤啤酒，酒，尿尿布，布，牛牛奶奶是是一一個個3-項項集。集。8.1.2 基本概念與

3、規(guī)則度量基本概念與規(guī)則度量目目構(gòu)構(gòu)成成的的集集合，合，一一次次處處理理所所含含項項目目的的集集合合用用表表示，示，是是I 的的子子集，集，稱稱為為一一個個事事務(wù)。務(wù)。事事務(wù)務(wù)的的集集合合包包括括k 個個事事務(wù)，務(wù)，稱稱為為事事務(wù)務(wù)集。集。8.1.2 基本概念與規(guī)則度量基本概念與規(guī)則度量l 關(guān)關(guān)聯(lián)聯(lián)規(guī)規(guī)則則: 關(guān)關(guān)聯(lián)聯(lián)規(guī)規(guī)則則是是形形如如 的的蘊蘊含含式，式，其其中中事事務(wù)務(wù) X, Y 分分別別是是 I 的的真真子子集，集，并并且且 。 X稱稱為為規(guī)規(guī)則則的的前前提，提， Y稱稱為為規(guī)規(guī)則則的的結(jié)結(jié)果。果。關(guān)關(guān)聯(lián)聯(lián)規(guī)規(guī)則則反反映映 X中中的的項項目目出出現(xiàn)現(xiàn)時，時， Y中中的的項項目目也也跟跟著

4、著出出現(xiàn)現(xiàn)的的規(guī)規(guī)律。律。8.1.2 基本概念與規(guī)則度量基本概念與規(guī)則度量l 關(guān)關(guān)聯(lián)聯(lián)規(guī)規(guī)則則的的支支持持度度（support）:關(guān)關(guān)聯(lián)聯(lián)規(guī)規(guī)則則的的支支持持度度是是事事務(wù)務(wù)集集中中同同時時包包含含X 和和Y的的事事務(wù)務(wù)數(shù)數(shù)與與所所有有事事務(wù)務(wù)數(shù)數(shù)之之比比,記記為為support ( )，即：即： support ( ) = support = 。l 支支持持度度反反映映了了 X和和 Y中中所所含含項項在在事事務(wù)務(wù)集集中中同同時時出出現(xiàn)現(xiàn)的的頻頻率。率。8.1.2 基本概念與規(guī)則度量基本概念與規(guī)則度量l 關(guān)關(guān)聯(lián)聯(lián)規(guī)規(guī)則則的的置置信信度度（confidence）:關(guān)關(guān)聯(lián)聯(lián)規(guī)規(guī)則則的的置置信信度度

5、是是事事務(wù)務(wù)集集中中包包含含 X和和 Y 的的事事務(wù)務(wù)數(shù)數(shù)與與所所有有包包含含X的的事事務(wù)務(wù)數(shù)數(shù)之之比，比，記記為為confidence( )， 即：即：l 置置信信度度反反映映了了包包含含X 的的事事務(wù)務(wù)中，中，出出現(xiàn)現(xiàn)Y 的的條條件件概概率。率。8.1.2 基本概念與規(guī)則度量基本概念與規(guī)則度量一一定定的的要要求，求，需需要要指指定定規(guī)規(guī)則則必必須須滿滿足足的的支支持持度度和和置置信信度度閾閾值，值，當(dāng)當(dāng)support ( ) 、confidence( ) 分分別別大大于于等等于于各各自自的的閾閾值值時，時，認認為為是是有有價價值值的，的，被被稱稱為為最最小小支支持持度度閾閾值值(minsu

6、pport)和和最最小小置置信信度度閾閾值值(mincontinence)。其其中，中，minsupport描描述述了了關(guān)關(guān)聯(lián)聯(lián)規(guī)規(guī)則則的的最最低低重重要要程程度，度，minconfidence規(guī)規(guī)定定了了關(guān)關(guān)聯(lián)聯(lián)規(guī)規(guī)則則必必須須滿滿足足的的最最低低可可靠靠性。性。8.1.2 基本概念與規(guī)則度量基本概念與規(guī)則度量l 頻頻繁繁項項集集: 設(shè)設(shè) 為為項項目目的的集集合，合，且且 ， ， 對對于于給給定定的的最最小小支支持持度度minsupport，若若 的的支支持持度度support minsupport，則則稱稱 為為頻頻繁繁項項目目集，集，否否則，則，稱稱 為為非非頻頻繁繁項項目目集。集。8.

7、1.2 基本概念與規(guī)則度量必必須須且且同同時時成成立，立，否否則則稱稱為為弱弱關(guān)關(guān)聯(lián)聯(lián)規(guī)規(guī)則。則。8.1.2 基本概念與規(guī)則度量l 性性質(zhì)質(zhì)1. 設(shè)設(shè)X 和和 Y是是數(shù)數(shù)據(jù)據(jù)集集 中中的的項項目目子子集集 （1）若若 ，則則support (X ) support (Y) （2）若若 ，且且 X是是非非頻頻繁繁項項目目集，集，則則Y也也是是非非頻頻繁繁項項目目集，集，即即任任意意弱弱項項目目集集的的超超集集都都是是弱弱項項集。集。 （3）若若 ，如如果果 Y是是頻頻繁繁項項目目集，集，則則 X也也是是頻頻繁繁項項目目集，集，即即任任意意大大項項集集的的子子集集都都是是大大項項集。集。8.2 關(guān)

8、聯(lián)規(guī)則算法l 8.2.1關(guān)關(guān)聯(lián)聯(lián)規(guī)規(guī)則則挖挖掘掘過過程程 關(guān)關(guān)聯(lián)聯(lián)規(guī)規(guī)則則挖挖掘掘問問題題可可分分解解為為以以下下兩兩個個子子問問題題: 1.找找頻頻繁繁項項目目集集:找找出出事事務(wù)務(wù)數(shù)數(shù)據(jù)據(jù)庫庫 中中所所有有大大于于或或等等于于用用戶戶指指定定最最小小支支持持度度的的項項目目集集(itemset)，即即頻頻繁繁項項目目集集。本本章章中中項項目目集集的的支支持持度度可可簡簡單單地地用用包包含含該該項項目目集集的的數(shù)數(shù)目目來來表表示示。 2.利利用用頻頻繁繁項項目目集集生生成成所所需需要要的的關(guān)關(guān)聯(lián)聯(lián)規(guī)規(guī)則則。 對對每每一一頻頻繁繁項項目目集集 ,找找到到其其所所有有非非空空子子集集 ,如如果果

9、比比 率率： 稱稱為為強強關(guān)關(guān)聯(lián)聯(lián)規(guī)規(guī)則則。8.2.2 Apriori算法2. 產(chǎn)生頻繁項集的過程產(chǎn)生頻繁項集的過程2. 產(chǎn)生頻繁項集的過程產(chǎn)生頻繁項集的過程3.Apriori算法的主要步驟l (1) 掃描全部數(shù)據(jù)，產(chǎn)生候選掃描全部數(shù)據(jù)，產(chǎn)生候選1-項集的集合項集的集合C1；l (2) 根據(jù)最小支持度，由候選根據(jù)最小支持度，由候選1-項集的集合項集的集合C1產(chǎn)生頻繁產(chǎn)生頻繁1-項項集的集合集的集合L1；l (3) 對對k1，重復(fù)執(zhí)行步驟，重復(fù)執(zhí)行步驟(4)、(5)、(6)；l (4) 由由Lk執(zhí)行連接和剪枝操作，產(chǎn)生候選（執(zhí)行連接和剪枝操作，產(chǎn)生候選（k+1）-項集的集項集的集合合Ck+1；l

10、 (5) 根據(jù)最小支持度，由候選（根據(jù)最小支持度，由候選（ k+1 ）-項集的集合項集的集合Ck+1，產(chǎn)生頻繁（產(chǎn)生頻繁（ k+1 ）-項集的集合項集的集合Lk+1；l (6) 若若L，則，則 k=k+1 ，跳往，跳往 (4)；否則；否則, 跳往步驟跳往步驟(7)；l (7) 根據(jù)最小置信度，由頻繁項集產(chǎn)生強關(guān)聯(lián)規(guī)則，結(jié)束根據(jù)最小置信度，由頻繁項集產(chǎn)生強關(guān)聯(lián)規(guī)則，結(jié)束。4. Apriori算法的舉例 表8.1 數(shù)據(jù)庫 的事務(wù)集4. Apriori算法的舉例表8.2 候選1-項集C1表8.3 頻繁1-項集L11) 第一次掃描4. Apriori算法的舉例表8.4 候選2-項集C2 表8.5 剪枝

11、后的C2 表8.6 頻繁2-項集L22）第二次掃描4. Apriori算法的舉例表8.7 候選3-項集C3 表8.8 剪枝后的C3 表8.9 頻繁3-項集L33）第三次掃描4. Apriori算法的舉例算法的舉例4）第第四四次次掃掃描描算算法法使使用用L3L3產(chǎn)產(chǎn)生生候候選選4-項項集集的的集集合合C4。L3L3=I1，I2，I3，I5，根根據(jù)據(jù)Apriori性性質(zhì)質(zhì)，因因為為它它的的子子集集I2，I3，I5不不是是頻頻繁繁的的，所所以以這這個個項項集集被被刪刪除除。這這樣樣C4= ，因因此此算算法法終終止止，找找出出了了所所有有的的頻頻繁繁項項集集。5.Apriori算法的優(yōu)缺點l Apri

12、ori算算法法使使用用Apriori性性質(zhì)質(zhì)來來生生成成候候選選項項集集的的方方法法，大大大大壓壓縮縮了了頻頻繁繁集集的的大大小小，取取得得了了很很好好的的性性能能。但但存存在在以以下下缺缺點點： (1) 產(chǎn)產(chǎn)生生大大量量的的頻頻繁繁集集。 (2) 重重復(fù)復(fù)掃掃描描事事務(wù)務(wù)數(shù)數(shù)據(jù)據(jù)庫庫。 Apriori算算法法會會產(chǎn)產(chǎn)生生大大量量的的頻頻繁繁集集，當(dāng)當(dāng)頻頻繁繁1-項項集集L1 有有1 000 個個時時，候候選選2-項項集集C2個個數(shù)數(shù)將將會會超超過過100萬萬。這這種種空空間間復(fù)復(fù)雜雜度度以以指指數(shù)數(shù)形形式式增增長長，使使得得Apriori算算法法的的執(zhí)執(zhí)行行效效率率很很低低。support_

13、count(AB)()(|)support_count(A)confidence ABP A B6.由頻繁項集產(chǎn)生關(guān)聯(lián)規(guī)則一旦由數(shù)據(jù)庫一旦由數(shù)據(jù)庫D D中的事務(wù)找出頻繁項集，由它們產(chǎn)中的事務(wù)找出頻繁項集，由它們產(chǎn)生強關(guān)聯(lián)規(guī)則是直接了當(dāng)?shù)模◤婈P(guān)聯(lián)規(guī)則滿足最生強關(guān)聯(lián)規(guī)則是直接了當(dāng)?shù)模◤婈P(guān)聯(lián)規(guī)則滿足最小支持度和最小置信度）。對于置信度可以用下小支持度和最小置信度）。對于置信度可以用下式，其中條件概率用項集支持度計數(shù)表示。式，其中條件概率用項集支持度計數(shù)表示。其中，其中，support_count(AB)support_count(AB)是包含是包含ABAB的事務(wù)數(shù)，的事務(wù)數(shù)，support_coun

14、t(A)support_count(A)是包含項集是包含項集A A的事務(wù)數(shù)。的事務(wù)數(shù)。6.由頻繁項集產(chǎn)生關(guān)聯(lián)規(guī)則l 關(guān)關(guān)聯(lián)聯(lián)規(guī)規(guī)則則產(chǎn)產(chǎn)生生如如下下：l對對于于每每個個頻頻繁繁項項集集l，產(chǎn)產(chǎn)生生l的的所所有有非非空空子子集集；l對對于于l的的每每個個非非空空子子集集s,如如果果 則則輸輸出出規(guī)規(guī)則則“S=(l-s)”,其其中中min_conf是是最最小小置置信信度度閾閾值值。support_count(l)min_support_count(s)conf6.由頻繁項集產(chǎn)生關(guān)聯(lián)規(guī)則務(wù)務(wù)Ti=I1,I2,I5。設(shè)設(shè)最最小小置置信信度度閾閾值值為為70%?？煽捎捎蒚i產(chǎn)產(chǎn)生生哪哪些些強強關(guān)關(guān)聯(lián)聯(lián)規(guī)

15、規(guī)則則？l 解解：Ti的的非非空空子子集集為為：I1，I2，I1，I5及及I2，I5，I1，I2，I5。6.由頻繁項集產(chǎn)生關(guān)聯(lián)規(guī)l 對對于于每每一一子子集集，可可求求出出置置信信度度如如下下： ：confidence=24=50% ：confidence=22=100% ：confidence=22=100% ：confidence=26=33% ：confidence=27=29% ：confidence=22=100%l 由由于于最最小小置置信信度度為為70%，則則只只有有上上面面第第2、3和和最最后后一一個個規(guī)規(guī)則則可可以以輸輸出出，因因為為只只有有這這些些產(chǎn)產(chǎn)生生強強關(guān)關(guān)聯(lián)聯(lián)規(guī)規(guī)則則。

16、8.2.3 關(guān)聯(lián)規(guī)則分類1.基基于于規(guī)規(guī)則則中中處處理理的的變變量量的的類類別別。 關(guān)關(guān)聯(lián)聯(lián)規(guī)規(guī)則則處處理理的的變變量量可可以以分分為為布布爾爾型型和和數(shù)數(shù)值值型型。布布爾爾型型關(guān)關(guān)聯(lián)聯(lián)規(guī)規(guī)則則處處理理的的值值都都是是離離散散的的、種種類類化化的的，它它顯顯示示了了這這些些變變量量之之間間的的關(guān)關(guān)系系；而而數(shù)數(shù)值值型型關(guān)關(guān)聯(lián)聯(lián)規(guī)規(guī)則則可可以以和和多多維維關(guān)關(guān)聯(lián)聯(lián)或或多多層層關(guān)關(guān)聯(lián)聯(lián)規(guī)規(guī)則則結(jié)結(jié)合合起起來來，對對數(shù)數(shù)值值型型字字段段進進行行處處理理，將將其其進進行行動動態(tài)態(tài)的的分分割割，或或者者直直接接對對原原始始的的數(shù)數(shù)據(jù)據(jù)進進行行處處理理，當(dāng)當(dāng)然然數(shù)數(shù)值值型型關(guān)關(guān)聯(lián)聯(lián)規(guī)規(guī)則則中中也也可可以以

17、包包含含種種類類變變量量。例例如如：性性別別=“女女”=職職業(yè)業(yè)=“秘秘書書” ，是是布布爾爾型型關(guān)關(guān)聯(lián)聯(lián)規(guī)規(guī)則則；性性別別=“女女”=avg（收收入入）=2300，涉涉及及的的收收入入是是數(shù)數(shù)值值類類型型，所所以以是是一一個個數(shù)數(shù)值值型型關(guān)關(guān)聯(lián)聯(lián)規(guī)規(guī)則則。8.2.3 關(guān)聯(lián)規(guī)則分類基基于于規(guī)規(guī)則則中中數(shù)數(shù)據(jù)據(jù)的的抽抽象象層層次次，可可以以分分為為單單層層關(guān)關(guān)聯(lián)聯(lián)規(guī)規(guī)則則和和多多層層關(guān)關(guān)聯(lián)聯(lián)規(guī)規(guī)則則。在在單單層層的的關(guān)關(guān)聯(lián)聯(lián)規(guī)規(guī)則則中中，所所有有的的變變量量都都沒沒有有考考慮慮到到現(xiàn)現(xiàn)實實的的數(shù)數(shù)據(jù)據(jù)是是具具有有多多個個不不同同的的層層次次的的；而而在在多多層層的的關(guān)關(guān)聯(lián)聯(lián)規(guī)規(guī)則則中中，對對數(shù)數(shù)

18、據(jù)據(jù)的的多多層層性性已已經(jīng)經(jīng)進進行行了了充充分分的的考考慮慮。例例如如：IBM臺臺式式機機=Sony打打印印機機，是是一一個個細細節(jié)節(jié)數(shù)數(shù)據(jù)據(jù)上上的的單單層層關(guān)關(guān)聯(lián)聯(lián)規(guī)規(guī)則則；臺臺式式機機=Sony打打印印機機，是是一一個個較較高高層層次次和和細細節(jié)節(jié)層層次次之之間間的的多多層層關(guān)關(guān)聯(lián)聯(lián)規(guī)規(guī)則則。8.2.3 關(guān)聯(lián)規(guī)則分類。關(guān)關(guān)聯(lián)聯(lián)規(guī)規(guī)則則中中的的數(shù)數(shù)據(jù)據(jù)，可可以以分分為為單單維維的的和和多多維維的的。在在單單維維的的關(guān)關(guān)聯(lián)聯(lián)規(guī)規(guī)則則中中，我我們們只只涉涉及及到到數(shù)數(shù)據(jù)據(jù)的的一一個個維維，如如用用戶戶購購買買的的物物品品；而而在在多多維維的的關(guān)關(guān)聯(lián)聯(lián)規(guī)規(guī)則則中中，要要處處理理的的數(shù)數(shù)據(jù)據(jù)將將會會涉涉及及多多個個維維。換換成成另另一一句句話話，單單維維關(guān)關(guān)聯(lián)聯(lián)規(guī)規(guī)則則是是處處理理單單個個屬屬性性中中的的一一些些關(guān)關(guān)系系；多多維維關(guān)關(guān)聯(lián)聯(lián)規(guī)規(guī)則則是是處處理理各各個個屬屬性性之之間間的的某某些些關(guān)關(guān)系系。例例如如：啤啤酒酒=尿尿布布，這這條條規(guī)規(guī)則則只只涉涉及及到到用用戶戶的的購購買買的的物物品品；性性別別=“女女”=