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

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

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

3、本概念與規(guī)則度量基本概念與規(guī)則度量目目構(gòu)構(gòu)成成的的集集合，合，一一次次處處理理所所含含項(xiàng)項(xiàng)目目的的集集合合用用表表示，示，是是I 的的子子集，集，稱稱為為一一個(gè)個(gè)事事務(wù)。務(wù)。事事務(wù)務(wù)的的集集合合包包括括k 個(gè)個(gè)事事務(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ī)則則是是形形如如 的的蘊(yùn)蘊(yùn)含含式，式，其其中中事事務(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àng)項(xiàng)目目出出現(xiàn)現(xiàn)時(shí)，時(shí)， Y中中的的項(xiàng)項(xiàng)目目也

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ù)集集中中同同時(shí)時(shí)包包含含X 和和Y的的事事務(wù)務(wù)數(shù)數(shù)與與所所有有事事務(wù)務(wù)數(shù)數(shù)之之比比,記記為為support ( )，即：即： support ( ) = support = 。l 支支持持度度反反映映了了 X和和 Y中中所所含含項(xiàng)項(xiàng)在在事事務(wù)務(wù)集集中中同同時(shí)時(shí)出出現(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( ) 分分別別大大于于等等于于各各自自的的閾閾值值時(shí)，時(shí)，認(rèn)認(rèn)為為是是有有價(jià)價(jià)值值的，的，被被稱稱為為最最小小支支持持度度閾閾值值(m

6、insupport)和和最最小小置置信信度度閾閾值值(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 頻頻繁繁項(xiàng)項(xiàng)集集: 設(shè)設(shè) 為為項(xiàng)項(xiàng)目目的的集集合，合，且且 ， ， 對(duì)對(duì)于于給給定定的的最最小小支支持持度度minsupport，若若 的的支支持持度度support minsupport，則則稱稱 為為頻頻繁繁項(xiàng)項(xiàng)目目集，集，否否則，則，稱稱 為為非非頻頻繁繁項(xiàng)項(xiàng)目目集。

7、集。8.1.2 基本概念與規(guī)則度量必必須須且且同同時(shí)時(shí)成成立，立，否否則則稱稱為為弱弱關(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ù)集集 中中的的項(xiàng)項(xiàng)目目子子集集 （1）若若 ，則則support (X ) support (Y) （2）若若 ，且且 X是是非非頻頻繁繁項(xiàng)項(xiàng)目目集，集，則則Y也也是是非非頻頻繁繁項(xiàng)項(xiàng)目目集，集，即即任任意意弱弱項(xiàng)項(xiàng)目目集集的的超超集集都都是是弱弱項(xiàng)項(xiàng)集。集。 （3）若若 ，如如果果 Y是是頻頻繁繁項(xiàng)項(xiàng)目目集，集，則則 X也也是是頻頻繁繁項(xiàng)項(xiàng)目目集，集，即即任任意意大大項(xiàng)項(xiàng)集集的的子子集集都都是是大大項(xiàng)項(xiàng)集。集。8

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

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

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

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

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

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

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

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

16、規(guī)則則。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é)合合起起來來，對(duì)對(duì)數(shù)數(shù)值值型型字字段段進(jìn)進(jìn)行行處處理理，將將其其進(jìn)進(jìn)行行動(dòng)動(dòng)態(tài)態(tài)的的分分割割，或或者者直直接接對(duì)對(duì)原原始始的的數(shù)數(shù)據(jù)據(jù)進(jìn)進(jìn)行行處處理理，當(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ù)值值類類型型，所所以以是是一一個(gè)個(gè)數(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í)的的數(shù)數(shù)據(jù)據(jù)是是具具有有多多個(gè)個(gè)不不同同的的層層次次的的；而而在在多多層層的的關(guān)關(guān)聯(lián)聯(lián)規(guī)規(guī)則則中中，

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