商務(wù)智能pptCh3V2 關(guān)聯(lián)分析

第3章關(guān)聯(lián)分析Chapter3:AssociationAnalysis主要內(nèi)容3.1頻繁模式與關(guān)聯(lián)規(guī)則3.2頻繁項(xiàng)集的典型挖掘方法3.3關(guān)聯(lián)規(guī)則的生成方法3.4關(guān)聯(lián)規(guī)則的其他類型3.5關(guān)聯(lián)規(guī)則的興趣度的其他度量3.1頻繁模式與關(guān)聯(lián)規(guī)則從交易數(shù)據(jù)庫、關(guān)系數(shù)據(jù)庫以及其他的數(shù)據(jù)集中發(fā)現(xiàn)項(xiàng)或?qū)ο蟮念l繁模式（frequentpatterns）、關(guān)聯(lián)（associations）的過程buys(x,“diapers”)?buys(x,“beers”)[0.5%,60%]Rao,SrikumarS.“Diaper-beerSyndrome,”Forbes,April6,1998.pp.128–130outlooktemperaturehumiditywindyplaysunnyhothighFALSEnosunnyhothighTRUEnoovercasthothighFALSEyesrainymildhighFALSEyesrainycoolnormalFALSEyes交易號(hào)（TID）商品（Items）1beer,diaper,nuts2beer,biscuit,diaper3bread,butter,cheese4beer,cheese,diaper,nuts5beer,butter,cheese,nuts交易數(shù)據(jù)庫Transactionaldatabase

每個(gè)交易：由顧客一次購買的商品（items）組成I={i1,i2,…,im}項(xiàng)集(Itemset):x={ij1,ij2,…,ijp}，ijiI每個(gè)項(xiàng)集包含的項(xiàng)的個(gè)數(shù)，稱為項(xiàng)集的長度，一個(gè)長度為k的項(xiàng)集又稱為k項(xiàng)集。I={A,B,C,D,E,F}2項(xiàng)集：AC，AD支持度（Support）交易包含項(xiàng)集X的概率

E.g.X={A},Y={A,B}=AB若support(X)>=minsup，則X稱為頻繁項(xiàng)集(frequentitemset)，也可以說X是頻繁的.設(shè)minsup=50%

{A:3,B:3,D:4,E:3,AD:3}TIDItemsbought10A,B,D20A,C,D30A,D,E40B,E,F50B,C,D,E,F閉合頻繁項(xiàng)集一個(gè)頻繁項(xiàng)集X

被稱為閉合頻繁項(xiàng)集（closedfrequentitemset）當(dāng)且僅當(dāng)不存在任一個(gè)項(xiàng)集Y

滿足X

Y

且support(Y)=support(X)。閉合頻繁項(xiàng)集X

被稱為是閉合的。例如：A是頻繁的，但不是閉合的，因?yàn)閟upport(AD)=support(A)，且

AADTIDItemsbought10A,B,D20A,C,D30A,D,E40B,E,F50B,C,D,E,F關(guān)聯(lián)規(guī)則給定兩個(gè)項(xiàng)集X和Y，關(guān)聯(lián)規(guī)則是形如X→Y的蘊(yùn)含式X

I稱為規(guī)則的前件，Y

I稱為規(guī)則的后件，X∩Y=

規(guī)則X→Y

的支持度(support)support(X→Y）=support(X∪Y)規(guī)則X→Y

的置信度(confidence)SupportandconfidenceTransaction-idItemsbought10A,B,D20A,C,D30A,E40B,E,F50B,C,D,E,F關(guān)聯(lián)規(guī)則：X

Ysupport(X

Y)=support(X∪Y)=|TXY|/nE.g:X={A}Y={C}support(A

C)=support(AC)=0.2X={A,D}=ADY=Csupport(AD

C)=support=(ADC)=0.2SupportandconfidenceTIDItemsbought10A,B,D20A,C,D30A,E40B,E,F50B,C,D,E,F置信度（confidence）Confidence(X

Y)=|TXY|/|TX|=sup(XY)/sup(X)A

C(20%,33%)AD

C(20%,50%)買尿片的交易同時(shí)買啤酒和尿片的交易買啤酒的交易關(guān)聯(lián)規(guī)則的挖掘給定如下閾值minimumsupport:minsupMinimumconfidence:

minconf發(fā)現(xiàn)所有形如X

Y

的關(guān)聯(lián)規(guī)則，滿足Support(XY)≥minsupConfidence(XY)≥minconf3.2頻繁項(xiàng)集的典型挖掘方法3.2.1逐層發(fā)現(xiàn)算法AprioriApriori(Agrawal&Srikant@VLDB’94)3.2.2無候選集發(fā)現(xiàn)算法FP-growthFreq.patterngrowth(FPgrowth—Han,Pei&Yin@SIGMOD’00)其他方法：Verticaldataformatapproach(Charm—Zaki&Hsiao@SDM’02)Highdimensionaldataset:TD-close(Liu,Han,etal.@ICDE06)…3.2.1逐層發(fā)現(xiàn)算法Apriori主要步驟k=1統(tǒng)計(jì)每個(gè)k項(xiàng)候選集的支持度，找出頻繁的k項(xiàng)集：Lk利用頻繁的k項(xiàng)集生成k+1項(xiàng)候選集(Candidateitemset

)：Ck+1k=k+1;轉(zhuǎn)至步驟2示例DatabaseTDB1stscanC1L1L2C2C22ndscanC3L33rdscanTidItems10A,C,D20B,C,E30A,B,C,E40B,EItemsetsup{A}2{B}3{C}3{D}1{E}3Itemsetsup{A}2{B}3{C}3{E}3Itemset{A,B}{A,C}{A,E}{B,C}{B,E}{C,E}Itemsetsup{A,B}1{A,C}2{A,E}1{B,C}2{B,E}3{C,E}2Itemsetsup{A,C}2{B,C}2{B,E}3{C,E}2Itemset{B,C,E}Itemsetsup{B,C,E}2minsup=2/4如何生成候選項(xiàng)集？性質(zhì)1：給定最小支持度閾值minsup，一個(gè)頻繁項(xiàng)集的所有非空子集都是頻繁的。if{beer,diaper}isfrequent,sois{beer}and{diaper}If{beer}isnotfrequent,{beer,diaper}isnotfrequentApriori剪裁規(guī)則:若存在某些項(xiàng)集是不頻繁的，則這些項(xiàng)集的任何超集都是不頻繁的，因而無須生成和測試。如何生成候選項(xiàng)集？假設(shè)每個(gè)Lk

中的項(xiàng)集的項(xiàng)都是按順序排列的步驟1:兩兩組合

Lk中項(xiàng)集生成

Ck+1步驟2:裁剪（pruning）如何生成候選項(xiàng)集？假設(shè)項(xiàng)集的項(xiàng)按字母序排列：beer<bread<butter<cheese<diaper<nuts如何生成候選項(xiàng)集？步驟1

abcd

abce設(shè)p和q

是Lk

中的兩個(gè)項(xiàng)集,滿足時(shí)生成(k+1)項(xiàng)集：

p.item1=q.item1,…,p.itemk-1=q.itemk-1,

p.itemk<q.itemkp.item1p.item2…p.itemk-1p.itemkq.item1q.item2…q.itemk-1q.itemkp.item1p.item2…p.itemk-1p.itemkq.itemk如何生成候選項(xiàng)集？步驟1字母序：a<b<c<d<eL3={abc,abd,acd,ace,bcd}abcdfromabcandabdacdefromacdandaceC4={abcd，acde}L3item1item2item3abcabdacdacebcd如何生成候選項(xiàng)集？步驟2刪除那些包含非頻繁k項(xiàng)集的(k+1)項(xiàng)集E.g：L3={abc,abd,acd,ace,bcd}，C4={abcd，acde}由于{cde}不頻繁，所以acde不可能頻繁

C4={abcd}DatabaseTDB1stscanC1C2C22ndscanL33rdscanC3L1L2TidItems10A,C,D20B,C,E30A,B,C,E40B,EItemsetsup{A}2{B}3{C}3{D}1{E}3Itemsetsup{A}2{B}3{C}3{E}3Itemset{A,B}{A,C}{A,E}{B,C}{B,E}{C,E}Itemsetsup{A,B}1{A,C}2{A,E}1{B,C}2{B,E}3{C,E}2Itemsetsup{A,C}2{B,C}2{B,E}3{C,E}2Itemset{B,C,E}Itemsetsup{B,C,E}2Supmin=23.2.2無候選集發(fā)現(xiàn)算法FP-growthFPgrowth—Han,Pei&Yin@SIGMOD’00采用一種樹的數(shù)據(jù)結(jié)構(gòu)（FP-tree）來實(shí)現(xiàn)頻繁項(xiàng)集的發(fā)現(xiàn)，不需要先生成候選項(xiàng)集FP-tree的特點(diǎn)完整性保留了用于挖掘頻繁項(xiàng)集的所有信息緊湊性減少了與頻繁項(xiàng)集挖掘無關(guān)的信息，F(xiàn)-list:高頻項(xiàng)更多機(jī)會(huì)被不同交易共享永遠(yuǎn)小于原來的交易數(shù)據(jù)庫TID Itemsbought 100 {f,a,c,d,g,i,m,p}

200 {a,b,c,f,l,m,o}300

{b,f,h,j,o,w}

400

{b,c,k,s,p}

500

{a,f,c,e,l,p,m,n}

算法：FP-growthHeaderTableItemfrequencyheadf 4c 4a 3b 3m 3p 3minsup=3/5掃描交易數(shù)據(jù)庫，找出所有頻繁單項(xiàng)按照支持度降序排列所有頻繁單項(xiàng)，得到f-list掃描交易數(shù)據(jù)庫，構(gòu)建FP-treeT調(diào)用mineTree(T,}f-list=f-c-a-b-m-p{}f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1FP-treeTID (ordered)frequentitems100

{f,c,a,m,p}200 {f,c,a,b,m}300

{f,b}400

{c,b,p}500

{f,c,a,m,p}頻繁項(xiàng)集的分割頻繁項(xiàng)集的集合可以分為若干個(gè)不相交的子集例如：F-list=f-c-a-b-m-p所有包含p的項(xiàng)集含有m不包含p的項(xiàng)集…含有c

不含a,b,m,p的項(xiàng)集項(xiàng)f生成條件模式庫(conditionalpatternbase)從頭表(headertable)開始

通過指針鏈遍歷FP-tree找到所有包含某項(xiàng)如p的分支合并相同前綴路徑，構(gòu)成

p條件模式庫Conditionalpatternbasesitem cond.patternbasec f:3a fc:3b fca:1,f:1,c:1m fca:2,fcab:1p fcam:2,cb:1{}f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1HeaderTableItemfrequencyheadf 4c 4a 3b 3m 3p 3FP-tree:T100{f,c,a,m,p}200 {f,c,a,b,m}300

{f,b}400

{c,b,p}500

{f,c,a,m,p}mineTree(T,X)以p為例：X=

;生成并輸出頻繁項(xiàng)集X∪{p}=p,support=3生成p的條件模式庫統(tǒng)計(jì)單項(xiàng)頻率：c:3,f:2,a:2,m:2,

b:1為條件模式庫構(gòu)建FP-tree:

TpX={p},調(diào)用mineTree(Tp,X){}c:3HeaderTableItemfrequencyheadc 3Tpfcam:2cb:1優(yōu)化對(duì)單支前綴路徑特殊處理，減少處理時(shí)間設(shè)minsup=2（出現(xiàn)2次）圖3.2頻繁模式樹T項(xiàng)集頻數(shù)abc2abd2表3.3項(xiàng)e的條件模式庫優(yōu)化

圖3.3項(xiàng)e的頻繁模式樹Te

圖3.4頻繁模式樹Te的多分支部分Q單支前綴路徑ab:5,生成與e的所有組合，即S={ae:4,be:4,abe:4}將此路徑用一個(gè)空的根節(jié)點(diǎn)替換，生成樹Q，分別對(duì)單項(xiàng)c和d處理，分別生成了1個(gè)項(xiàng)集，ce和de，構(gòu)成集合M={ce:2,de:2}返回S∪M∪(S

M)，S

M={ace:2,ade:2,bce:2,bde:2,abce:2,abde:2}挖掘高維度數(shù)據(jù)集中的頻繁項(xiàng)集Carpenter(Pan,etal.@KDD’03)MinedatasetswithsmallrowsbutnumerouscolumnsConstructabottom-uprow-enumerationtreeforefficientminingTD-close(Liu,Han,etal.@ICDE06)MinedatasetswithsmallrowsbutnumerouscolumnsConstructaTop-downrow-enumerationtreeforefficientminingMiningFrequentPatternsfromVeryHighDimensional

Data:ATop-DownRowEnumerationApproach

HongyanLiuTsinghuaUniversityJiaweiHan,DongXin,ZhengShao

UniversityofIllinoisatUrbana-Champaign低維度--高維度TIDItems1A,C,D2B,C,E3A,B,C,E4B,E567…100000TIDItems1Pj1,Pj2,…,Pj100002Pk1,Pk2,…,Pk9993Pl1,Pl2,…,Pl2000…56Pm1,Pm2,…,Pm6000行枚舉方法riABCD1a1b1c1d12a1b1c2d23a1b1c1d24a2b1c2d25a2b2c2d310/29/2023Minsup=2TableTTransposedTableitemsetrowseta11,2,3a24,5b11,2,3,4c11,3c22,4,5d22,3,410/29/2023自上而下的挖掘策略1a1b1c1d12a1b1c2d23a1b1c1d24a2b1c2d25a2b2c2d313a1b1c124b1c2d225c234b1d245a2c2351514b123a1b1d2245c2234b1d2134b1124b1123a1b113512514523534512a1b11245134523451234b11235Minsup=31234510/29/2023自上而下、分而治之的遞歸挖掘345134523451234545a2c2245c214512455a2b2c2d325c2351513512523512351a1b1c1d12a1b1c2d23a1b1c1d24a2b1c2d213a1b1c124b1c2d234b1d214b123a1b1d2234b1d2134b1124b1123a1b112a1b11234b1Without5With5w/o4With45w/o3With345w/o2With2345w/o1Divide-and-conquer3.3關(guān)聯(lián)規(guī)則的生成方法生成關(guān)聯(lián)規(guī)則為每個(gè)頻繁項(xiàng)集l,生成非空子集s;若滿足

則輸出規(guī)則：(l-s)

se.g：l=ABCD,s=D,(l-s)=ABCconfidence(ABC

D)=support(ABCD)/support(ABC)生成關(guān)聯(lián)規(guī)則minconf=80%For{BCE}：Confidence(BE

C)<80%,Confidence(BC

E)>80% Confidence(CE

B)>80%

Confidence(B

CE)<80%

Confidence(E

BC)<80%

Confidence(C

BE)<80%

L1L2L3生成關(guān)聯(lián)規(guī)則minconf=80%For{BCE}：Confidence(BE

C)<80%,Confidence(BC

E)>80% Confidence(CE

B)>80%confidence(C

BE):<80%L1L2L3生成關(guān)聯(lián)規(guī)則ForBCE，Confidence(BE

C)<80%,HowaboutB

ECandE

BC?生成關(guān)聯(lián)規(guī)則對(duì)于頻繁項(xiàng)集l=ABCD若BCDA和ACDB

都成立

則CDAB

有可能成立.若CDAB,BDAC,和ADBC都成立,

則DABC

有可能成立3.4關(guān)聯(lián)規(guī)則的其他類型關(guān)聯(lián)規(guī)則的類型多層次關(guān)聯(lián)規(guī)則什么品牌的啤酒和尿片（diapers）有關(guān)聯(lián)?負(fù)關(guān)聯(lián)規(guī)則、無關(guān)規(guī)則（dissociationrule)playbasketball

noteatcereal[20%,33.3%]結(jié)構(gòu)化數(shù)據(jù)中的關(guān)聯(lián)分析多層次關(guān)聯(lián)規(guī)則項(xiàng)有概念層次性低層的項(xiàng)通常具有較低的支持度將項(xiàng)抽象到一定高的層次產(chǎn)生的規(guī)則更有意義一個(gè)超市的庫存中至少有10000個(gè)項(xiàng)FoodbreadmilkskimSunsetFraser2%whitewheat

milk→bread[20%,60%].2%milk→wheatbread[6%,50%].多層次關(guān)聯(lián)規(guī)則兩類單層 F→GBC→E多層 FC→ETidItems10A,C,D20B,C,E30A,B,C,E40B,EHGFAEBDC負(fù)模式負(fù)項(xiàng)與正項(xiàng)

當(dāng)項(xiàng)ik

沒有出現(xiàn)在某個(gè)給定的交易中，稱該項(xiàng)對(duì)于該交易是個(gè)負(fù)項(xiàng)，記為

，與此對(duì)應(yīng)，出現(xiàn)在該交易中的每個(gè)項(xiàng)id

稱為正項(xiàng)。負(fù)項(xiàng)集與負(fù)關(guān)聯(lián)規(guī)則

一個(gè)包含負(fù)項(xiàng)的項(xiàng)的集合稱為負(fù)項(xiàng)集。一個(gè)負(fù)項(xiàng)集的支持度如果不小于用戶給定的最小支持度，則稱為頻繁負(fù)項(xiàng)集

負(fù)關(guān)聯(lián)規(guī)則：包含負(fù)項(xiàng)的關(guān)聯(lián)規(guī)則。負(fù)項(xiàng)集和負(fù)關(guān)聯(lián)規(guī)則統(tǒng)稱為負(fù)模式。負(fù)關(guān)聯(lián)規(guī)則、無關(guān)規(guī)則（dissociationrule)TIDItems1A,B,

C,D

2

A,B,C,D

3A,B,

C,D

4A,C,D,B

發(fā)現(xiàn)帶有“非Ii”的規(guī)則：（A,

B）→CTIDItems1A,B2B,C3A,C4A,C,DTIDITEMS1age30,income=high,student=no,credit_rating=fair,buys_PC=no2age30,income=high,student=no,credit_rating=excellent,buys_PC=no3age30,income=medim,student=no,credit_rating=fair,buys_PC=no4age30,income=low,student=yes,credit_rating=fair,buys_PC=yes5age30,income=medium,student=yes,credit_rating=excellent,buys_PC=yes…14Age40,income=medium,student=no,credit_rating=excellent,buys_PC=no結(jié)構(gòu)化數(shù)據(jù)集非結(jié)構(gòu)化轉(zhuǎn)化為結(jié)構(gòu)化交易號(hào)（TID）Beerdiapernutsbiscuitbreadbuttercheese1111

211

1

3

1114111

151

1

11交易號(hào)（TID）商品（Items）1beer,diaper,nuts2beer,biscuit,diaper3bread,butter,cheese4beer,cheese,diaper,