Chapter6關(guān)聯(lián)規(guī)則

AssociationRule

目標:提供關(guān)聯(lián)規(guī)則問題的概述并介紹幾種基本的關(guān)聯(lián)規(guī)則挖掘算法關(guān)聯(lián)規(guī)則問題概述大項目集關(guān)聯(lián)規(guī)則算法Apriori算法抽樣算法劃分算法并行算法1?PrenticeHall啤酒和尿布的故事

沃爾瑪公司在美國的一位店面經(jīng)理曾發(fā)現(xiàn)，每周，啤酒和尿布的銷量都會有一次同比攀升，一時卻搞不清是什么原因。后來，沃爾瑪運用數(shù)據(jù)挖掘技術(shù)發(fā)現(xiàn)，購買這兩種產(chǎn)品的顧客幾乎都是25歲到35歲、家中有嬰兒的男性，每次購買的時間均在周末。沃爾瑪在對相關(guān)數(shù)據(jù)分析后得知，這些人習(xí)慣晚上邊看球賽、邊喝啤酒，邊照顧孩子，為了圖省事而使用一次性的尿布。得到這個結(jié)果后，沃爾瑪決定把這兩種商品擺放在一起，結(jié)果，這兩種商品的銷量都有了顯著增加。2?PrenticeHall這個故事說明了什么？在海量的數(shù)據(jù)中，總是隱藏著各種各樣的信息。而隨著時間的推移以及信息爆炸，我們已經(jīng)很難不借助其他的外力去從海量的數(shù)據(jù)中發(fā)覺信息，即使能發(fā)覺，根據(jù)現(xiàn)在信息的發(fā)布速度，這樣也是毫無實際意義的。如何從龐大的數(shù)據(jù)海洋中發(fā)掘有效信息，已經(jīng)成為信息時代所急待解決的問題。于是數(shù)據(jù)倉庫，數(shù)據(jù)挖掘、在線分析等等概念開始出現(xiàn)在我們視野里。這個時代是一個炒做概念的時代，新名詞、新概念層出不窮；惹的我們紛紛雙眼昏花起來。這個故事告訴大家，數(shù)據(jù)里蘊藏著許多肉眼所看不見的東西。根據(jù)現(xiàn)在的零售業(yè)發(fā)展規(guī)模來看，再想創(chuàng)造沃爾瑪?shù)纳衿婀适乱呀?jīng)不可能了，誰都沒有神的眼睛，沒有經(jīng)過梳理的數(shù)據(jù)對我們來說比垃圾還垃圾。因此，如何發(fā)掘垃圾里的有價值信息，就成了一個市場的賣點。因此，請關(guān)注數(shù)據(jù)挖掘。3?PrenticeHall例子:購物籃數(shù)據(jù)購買一種商品時也同時購買另一種商品的情形就構(gòu)成了一條關(guān)聯(lián)規(guī)則:花生醬

面包應(yīng)用領(lǐng)域:場地布局廣告市場營銷庫存控制目的:增加銷售量并減少成本4?PrenticeHall關(guān)聯(lián)規(guī)則相關(guān)概念一組項目:

I={I1,I2,…,Im}事務(wù)數(shù)據(jù)庫:D={t1,t2,…,tn},tj

I項目集:{Ii1,Ii2,…,Iik}

I項目集的支持度:包含該項目集的事務(wù)占庫中所有事務(wù)的百分比。大(頻繁)項目集:

是出現(xiàn)次數(shù)大于閾值s的項目集.5?PrenticeHall關(guān)聯(lián)規(guī)則示例5個項目I={Beer,Bread,Jelly,Milk,PeanutButter}項目集{Bread,PeanutButter}的支持度是60%6?PrenticeHall關(guān)聯(lián)規(guī)則定義

給定一組項目I={I1,I2,…,Im}和一個事務(wù)數(shù)據(jù)庫D={t1,t2,…,tn}，其中ti={Ii1,Ii2,…,Iik}并且Iij

I,關(guān)聯(lián)規(guī)則(AR):形如X

Y的蘊含式，其中X,Y

I是兩個項目集，并且X

Y=?;關(guān)聯(lián)規(guī)則X

Y

的支持度s:數(shù)據(jù)庫中包含X

Y

的事務(wù)占庫中所有事務(wù)的百分比。關(guān)聯(lián)規(guī)則X

Y

的置信度a:

包含X

Y的事務(wù)數(shù)與包含X

的事務(wù)數(shù)的比值。7?PrenticeHall示例8?PrenticeHall關(guān)聯(lián)規(guī)則問題給定一組項目I={I1,I2,…,Im}和一個事務(wù)數(shù)據(jù)庫D={t1,t2,…,tn}，其中

ti={Ii1,Ii2,…,Iik}并且Iij

I,關(guān)聯(lián)規(guī)則問題就是識別出所有大于最小支持度和置信度的關(guān)聯(lián)規(guī)則

X

Y.注意:

X

Y的支持度和X

Y的支持度相等.9?PrenticeHall關(guān)聯(lián)規(guī)則技術(shù)發(fā)現(xiàn)大項目集.從大項目集合產(chǎn)生關(guān)聯(lián)規(guī)則.10?PrenticeHall產(chǎn)生關(guān)聯(lián)規(guī)則的算法ARs11?PrenticeHalls=30%,a=50%

利用該支持度，從表6.2得到大項目集的集合

L={{啤酒}，{面包}，{牛奶}，{花生醬}，{面包,花生醬}}

要想產(chǎn)生關(guān)聯(lián)規(guī)則，需要有非空子集。

只有最后一個大項目集可以產(chǎn)生關(guān)聯(lián)規(guī)則。

該大項目集產(chǎn)生的可能關(guān)聯(lián)規(guī)則如下：

（1）面包

花生醬

，其置信度為0.75，滿足條件，是一條有效的關(guān)聯(lián)規(guī)則。

（2）花生醬

面包，其置信度為1，滿足條件，是一條有效的個關(guān)聯(lián)規(guī)則。例題12?PrenticeHallApriori算法大項目集性質(zhì):大項目集的任一子集也一定是大的。因此大項目集只能從所有大的子集的組合（連接運算）產(chǎn)生對照:如果一個項目集不是大的，那么它的超集也不是大的。13?PrenticeHallApriori

算法示例(cont’d)s=30%a=50%14?PrenticeHallApriori

算法C1=ItemsetsofsizeoneinI;Determinealllargeitemsetsofsize1,L1;i=1;Repeati=i+1;

Ci

=Apriori-Gen(Li-1);CountCitodetermineLi;untilnomorelargeitemsetsfound;15?PrenticeHallApriori-Gen從大小為i

的大項目集產(chǎn)生大小為i+1的侯選項目集。具體用法：將每一個項目集合與另外一個具有共同成員的項目集進行連接運算（組合）。

比如下例，在第三趟掃描后，有4個大項目集。在對這些大項目集進行連接運算時，必須對三個屬性中的兩個進行匹配，然后生成更大的項目集?？赡苄枰藜?，因為據(jù)此產(chǎn)生的大項目集有些不是大的。16?PrenticeHallApriori-Gen算法示例17?PrenticeHallApriori-GenExample(cont’d)18?PrenticeHall抽樣算法針對大型數(shù)據(jù)庫，可以減少掃描趟數(shù)首先對數(shù)據(jù)庫進行抽樣，然后對抽樣應(yīng)用Apriori

算法.潛在的大項目集(PL):

從抽樣里產(chǎn)生的大項目集負邊界函數(shù)(BD-):把Apriori-Gen算法推廣應(yīng)用到大小變化的項目集。它定義為本身不在PL中,但其子集都在PL中的最小集合.19?PrenticeHall例題假定項目集合是{A,B,C,D}。從數(shù)據(jù)庫樣本（抽樣）中發(fā)現(xiàn)的大項目集合為PL={A,C,D,CD).第一趟掃描整個數(shù)據(jù)庫生成下面的侯選集:C=BD-(PL)(PL)={B,AC,AD}{A,C,D,CD}

這里之所以加入AC,是因為A和C都在PL中,同理也加入了AD。

沒有加入ACD，是因為它的子集AC和AD都不在PL中。20?PrenticeHall抽樣算法Ds=sampleofDatabaseD;PL=LargeitemsetsinDsusingsmalls;C=PL

BD-(PL);CountCinDatabaseusings;ML=largeitemsetsinBD-(PL);

L=largeitemsetsinCIfML=

thendone elseC=repeatedapplicationofBD-（IneachiterationletC=L);CountCinDatabase;21?PrenticeHall抽樣算法示例FindARassumings=20%Ds={t1,t2}Smalls=10%PL={{Bread},{Jelly},{PeanutButter},{Bread,Jelly},{Bread,PeanutButter},{Jelly,PeanutButter},{Bread,Jelly,PeanutButter}}BD-(PL)={{Beer},{Milk}}ML={{Beer},{Milk}}RepeatedapplicationofBD-generatesallremainingitemsets22?PrenticeHall作業(yè)3標準解法

若抽樣數(shù)據(jù)庫包括t1,t9兩個事務(wù)：

Ds={t1={罩衫}，t9={牛仔褲}}將s減小到smalls=10%,那么對于一個在抽樣中為大的項目集來說，它必須在至少0.1*2個事務(wù)中出現(xiàn)，也就必須在其中一個事務(wù)中出現(xiàn)；PL={{罩衫}，{牛仔褲}計算負邊界可得：

BD-（PL）={{裙子}，{T恤}，{鞋}，{短褲},{罩衫，牛仔褲}}

第一趟掃描時候選集：C=PL∪BD-（PL）={{罩衫}，{牛仔褲}，{裙子}，{T恤}，{鞋}，{短褲}，{罩衫，牛仔褲}}掃描使用s=20%，并應(yīng)用于整個數(shù)據(jù)庫的20個事務(wù)中。因此對于一個大目集來說，它必須在大于0.2*20=4個事務(wù)中出現(xiàn)。得到大項目集：L1={{牛仔褲}，{裙子}，{T恤}，{鞋}，{短褲}}23?PrenticeHall第二趟掃描令C=L1，計算負邊界：C=BD-（C）={…}

掃描使用s=20%，并應(yīng)用于整個數(shù)據(jù)庫的20個事務(wù)中。因此對于一個大目集來說，它必須在大于0.2*20=4個事務(wù)中出現(xiàn)。得到大項目集合：L2={…}第三趟掃描令C=L2，計算負邊界C=BD-（C）={…}

得到大項目集合：L3={…}

故最終的大項目集：L=L1∪L2∪L3={…}24?PrenticeHall劃分算法把數(shù)據(jù)庫分成小的數(shù)據(jù)庫D1,D2,…,Dp對每一部分應(yīng)用

Apriori

算法。任何一個大項目集至少在一個劃分是大的。25?PrenticeHallPartitioningAlgorithmDivideDintopartitionsD1,D2,…,Dp;ForI=1topdoLi=Apriori(Di);C=L1

…

Lp;CountConDtogenerateL;26?PrenticeHall劃分算法示例D1D2S=10%L1={{Bread},{Jelly},{PeanutButter},{Bread,Jelly},{Bread,PeanutButter},{Jelly,PeanutButter},{Bread,Jelly,PeanutButter}}L2={{Bread},{Milk},{PeanutButter},{Bread,Milk},{Bread,PeanutButter},{Milk,PeanutButter},{Bread,Milk,PeanutButter},{Beer},{Beer,Bread},{Beer,Milk}}27?PrenticeHall平行算法依據(jù)Apriori算法大部分平行或分布式關(guān)聯(lián)規(guī)則算法要么試圖將數(shù)據(jù)并行化（或者劃分），要么試圖將侯選并行化（或者劃分）。兩者分別稱之為數(shù)據(jù)并行和任務(wù)并行。數(shù)據(jù)并行和任務(wù)并行的典型算法分別為記數(shù)分配算法和數(shù)據(jù)分別算法。28?PrenticeHall度量關(guān)聯(lián)規(guī)則的質(zhì)量支持度s(AB)=P(A,B)置信度a(AB)=P(B|A)=P(A,B)/P(A)作用度或興趣度interest(AB)=P(A,B)/(P(A)*P(B))信任度conviction(AB)=P(A)*P(?B)/P(A,?B)

如果A和B恒成立的規(guī)則的信任度為。如果A和B不相關(guān)（獨立），則信任度為1。如果A