商務智能錄屏2020ch3關(guān)聯(lián)分析

第3章關(guān)聯(lián)分析Chapter3:Association ?He?He PrinciplesandApplicationsofBusiness PrinciplesandApplicationsofBusiness

Chap3：關(guān)聯(lián)分§Basic§Efficientandscalablefrequentitemsetmining§Miningvariouskindsofassociation§§2PrinciplesandApplicationsofBusiness Chap3：關(guān)聯(lián)分析 WhatIsAssociation§關(guān)聯(lián)規(guī)則的挖掘 中發(fā)現(xiàn)項或?qū)ο蟮念l繁的模式(frequentpatterns)、關(guān)聯(lián)(associations)的過buys(x, buys(x,“beers”)[0.5, （福布斯）》1998.4.6“啤酒尿布綜合癥ItemsItems1234yyes 11:11:關(guān)聯(lián)分析指導交叉銷

結(jié)點：商30:客一起30:PrinciplesandApplicationsofBusiness

Chap3：關(guān)聯(lián)分BasicConcepts:FrequentTransactionaldatabase 數(shù)據(jù)庫 每 ：eachtransactionisalistof 的商品 I={i1,i2,…, 項集Itemset):x={ij1ij2…TransactionItemsTransactionItems§I={A,B,C,D,E,§2項集5PrinciplesandApplicationsofBusiness Chap3：關(guān)聯(lián)分析 ItemsA,ItemsA,B,A,C,A,D,B,E,B,C,D,E,§ X={A}Y={A,若support(X)>=minsup，則X稱為頻繁項(frequentitemset)，也可以說X是頻繁的 Letminsup= PrinciplesandApplicationsofBusiness Chap3：關(guān)聯(lián)分析 BasicConcepts:Association§ItemsetX={x1,…,xk},Y={y1,…,§FindalltherulesXà Ywithminimumsupportandminimumconfidence§Threshold（閾值minimumsupport:Minimumconfidence:Sup(X Y)≥Conf(X Y)≥7PrinciplesandApplicationsofBusiness Chap3：關(guān)聯(lián)分析 Supportand§Association Transaction-ItemsA,B,A,C,Transaction-ItemsA,B,A,C,A,B,E,B,C,D,E,X={A}sup(A C)=sup(AC)=0.2X={A,D}=AD，Y=Csup C=sup8PrinciplesandApplicationsofBusiness Supportand§confidence（置信度

Chap3：關(guān)聯(lián)分conditionalprobabilitythatatransactionhavingXalso Y)=|XY|/|X|=sup(XY)/ItemsA,B,A,C,A,B,E,B,C,D,E,AAC(20%,C(20%,PrinciplesandApplicationsofBusiness

Chap3：關(guān)聯(lián)分§Basic§Efficientandscalablefrequentitemsetminingmethods§Miningvariouskindsofassociation§§PrinciplesandApplicationsofBusiness Chap3：關(guān)聯(lián)分析 ScalableMethodsforMiningFrequent§ScalableminingApriori(Agrawal&Freq.patterngrowth(FPgrowth—Han,Pei&YinVerticaldataformatapproach(Charm—Zaki&Hsiao@SDM’02)PrinciplesandApplicationsofBusiness Chap3：關(guān)聯(lián)分析 挖掘關(guān)聯(lián)規(guī)則(frequentitemsets)支持度>=minimumsupport的所有項集利用頻繁的k項集生成k+1項候選集itemsetTheAprioriAlgorithm—An2323313DatabaseA,C,B,C,A,B,C,B,{A,{A,2{B,2{B,3{C,2

1st{A,{A,1{A,2{A,1{B,2{B,3{C,2

22333{A,{A,{A,{B,{B,{C,2nd{B,C,{B,C,{B,C,{B,C,2PrinciplesandApplicationsofBusiness Chap3：關(guān)聯(lián)分析 §任何頻繁集的子集必須是頻繁if{beer,diaper}isfrequent,sois{beer}and-包含{beer,diaper}的 Items1234§Apriori剪裁規(guī)則:若存在某些項集是不頻繁的，則Items1234PrinciplesandApplicationsofBusiness Chap3：關(guān)聯(lián)分析 FrequentItemset

Givenditems,thereare2dpossiblecandidateitemsetsPrinciplesandApplicationsofBusiness Chap3：關(guān)聯(lián)分析 AprioriPrinciple Foundtobe

PrinciplesandApplicationsofBusiness Chap3：關(guān)聯(lián)分析 HowtoGenerate§SupposetheitemsinLkarelistedinan§Step1Lk§Step2裁剪PrinciplesandApplicationsofBusiness Chap3：關(guān)聯(lián)分析 HowtoGenerate§SupposetheitemsinLkarelistedinan§beer<bread<butter<cheese<diaper<ItemsItems1234Items1234PrinciplesandApplicationsofBusiness Chap3：關(guān)聯(lián)分析 HowtoGenerateCandidates?§Orderinalphabeticorder:abcabdacdabcabdacdacebcdabcdfromabcandacdefromacdand§PrinciplesandApplicationsofBusiness Chap3：關(guān)聯(lián)分析 HowtoGenerateCandidates?Step …p.itemk-…p.itemk-…q.itemk-§pandqistwoitemsetsinLk,ifp.item1=q.item1,…,p.itemk-1=q.itemk-Thengeneratea(k+1)lengthp.item1,p.item2,…,p.itemk,

p.itemk<…p.itemk-PrinciplesandApplicationsofBusiness Chap3：關(guān)聯(lián)分析 HowtoGenerateCandidates?Step§Deletethose(k+1)lengthitemsetswhichincludesinfrequentklengthitemsetE.g：L3={abc,abd,acd,ace,bcd}，C4={abcdSince{cde}isnotfrequent，TheAprioriAlgorithm—An233233132333DatabaseA,C,B,C,A,B,C,B,{A,{A,2{B,2{B,3{C,2

1st{A,{A,1{A,2{A,1{B,2{B,3{C,2

{A,{A,{A,{A,{B,{B,{C,2nd{B,C,{B,C,{B,C,{B,C,2PrinciplesandApplicationsofBusiness Chap3：關(guān)聯(lián)分析 §已知 PrinciplesandApplicationsofBusiness Chap3：關(guān)聯(lián)分析 Apriori:generatingassociation Y)=P(Y|X)=support(X§Foreachfrequentitemsetl,generateeverynon-subsets;ifssatisfiesconfidence((l- s)Outputrules:(l- e.g：l=ABCD,s=D,(l－s)=

sup(l-s)

? D)=support(ABCD)/PrinciplesandApplicationsofBusiness Chap3：關(guān)聯(lián)分析 Apriori:generatingassociation{A2{B2{B{A2{B2{B3{C2itemsesup.{A}2{B}3{C}3{E}3{BC2§For{BCE}：Confidence(BEC)=2/3<Confidence(BCE)=2/2>80%Confidence(CEB)=2/2>80%Confidence(BCE)=2/3<80%Confidence(CBE)=2/3<80%Confidence(EBC)=2/3<80%PrinciplesandApplicationsofBusiness Chap3：關(guān)聯(lián)分析 Apriori:generatingassociation{A2{B2{B{A2{B2{B3{C2itemsesup.{A}2{B}3{C}3{E}3{BC2§For{BCE}：Confidence(BE C)<80%,Confidence(BC E)>80%Confidence(CE B)>80%confidence(C BE):<80%PrinciplesandApplicationsofBusiness Chap3：關(guān)聯(lián)分析 Generating§ForBCE， C)< C)=support(BCE)<§Howabout ECand BC EC)= BC)=PrinciplesandApplicationsofBusiness Chap3：關(guān)聯(lián)分析 Generating§Supposel=ABCDisafrequent§IfbothBCD AandACD BholdThenCD ABispossibletohold.§If AB, AC,and BCThen ABCispossibletoFP-GrowthFreq.patterngrowth(FPgrowth—Han,Pei&Yin@SIGMOD’00)IssupportandconfidencePrinciplesandApplicationsofBusiness

Chap3：關(guān)聯(lián)分Issupportandconfidence ybasketball eatcereal[40%,66.7%] -Theoverallpercentageofstudentseatingcerealis75%whichishigherthan66.7%. ybasketball noteatcereal[20%,33.3%]ismoreaccurate,althoughwithlowersupportandPrinciplesandApplicationsofBusiness Chap3：關(guān)聯(lián)分析 InterestingnessMeasure:§Supportandconfidencearenotgoodtorepresentcorrelations:A→B(support,confidence,§Measureofdependent/correlated-lift,c2,all_conf,PrinciplesandApplicationsofBusiness Chap3：關(guān)聯(lián)分析 InterestingnessMeasure:Correlations§

lift=P(A¨P(A)P(B)

>1:positively(增益,提升度)conf(A B)=1: sup(B)

<1:negativelyNotNotLift(basketball,cereal)=2000*5000/(3750*3000)=Lift(basketball,PrinciplesandApplicationsofBusiness Chap3：關(guān)聯(lián)分析 {A2{B{A2{B2{B3{C2itemsesup.{A}2{B}3{C}3{E}3A,C,B,C,A,B,C,B,§Lift：sup§Confidence(BE SupLift(BE C)=(2/3)/(3/4)=

= sup(AB) sup(A)sup(B)§Confidence(BC SupLift(BC

conf PrinciplesandApplicationsofBusiness Chap3：關(guān)聯(lián)分析 ClosedPatternsandMax-§Alongpatterncontainsacombinatorialnumberofsub-patterns,e.g.,{a1,…,a100}10(1001)+(1002)+…+(100)=2100–1=10§Solution:Mineclosedpatternsandmax-patternsinsteadReducingthe#ofpatternsandrulesPrinciplesandApplicationsofBusiness Chap3：關(guān)聯(lián)分析 ClosedPatternsandMax-§AnitemsetXisamax-patternifXisfrequentandthereexistsnofrequentsuper-patternY (proposedbyBayardo@A,A,C,B,C,A,B,C,B,itemsesup.{A}2{B}3{C}3{E}3{A,2{B,2{B,3{C,2{BC2PrinciplesandApplicationsofBusiness Chap3：關(guān)聯(lián)分析 ClosedPatternsandMax-§AnitemsetXisclosedifXisfrequentandtherenosuper-patternY X,withthesamesupportasX(proposedbyPasquier,etal.@ICDT’99)§ClosedpatternisalosslesscompressionofA,A,C,B,C,A,B,C,B,itemsesup.{A}2{B}3{C}3{E}3{A,2{B,2{B,3{C,2{BC2PrinciplesandApplicationsofBusiness Chap3：關(guān)聯(lián)分析 ClosedPatternsandMax-§DB={<a1,…,a100>,<a1,…,-Min_sup=§Whatisthesetofclosed-<a1,…,a100>:-<a1,…,a50>:§Whatisthesetofmax--<a1,…,a100>:§Whatisthesetofall-PrinciplesandApplicationsofBusiness Chap3：關(guān)聯(lián)分析 FurtherImprovementsofMining§Carpenter(Pan,etal.@MinedatasetswithsmallrowsbutnumerousConstructabottom-uprow-enumerationtreeforefficient§TD-close(Liu,Han,etal.@SDM06,oneof4bestMinedatasetswithsmallrowsbutnumerousConstructaTop-downrow-enumerationtreeforefficientHongyanLiu,XiaoyuWang,JunHe,JiaweiHan,DongXin,ZhengShao:Top-downminingoffrequentclosedpatternsfromveryhighdimensionaldata.InformationSciences.179(7):899-924 PrinciplesandApplicationsofBusiness Chap3：關(guān)聯(lián)分析 1A,C,1A,C,2B,C,3A,B,C,4B,567…1Pj1,Pj2,…,2Pk1,Pk2,…,3Pl1,Pl2,…,…Pm1,Pm2,…,PrinciplesandApplicationsofBusiness Chap3：關(guān)聯(lián)分析 §Foreachitem,storealistoftransactionidsHorizontalDataLayoutTIDItems1A,B,ETIDItems1A,B,E2B,C,D3C,E4A,C,D5A,B,C,D6A,E7A,B8A,B,C9A,C,D10BPrinciplesandApplicationsofBusiness Chap3：關(guān)聯(lián)分析 Rowenumeration TransposedABCD123451,2,4,1,2,3,1,2,4,2,3, PrinciplesandApplicationsofBusiness Bottom-up

Chap3：關(guān)聯(lián)分§Frequentclosed§Largeclosed§

12345

b12c2c2

1 2

Fig.2.Bottom-uprowenumerationPrinciplesandApplicationsofBusiness Basic

Chap3：關(guān)聯(lián)分 Efficientandscalablefrequentitemsetmining Miningvariouskindsofassociation PrinciplesandApplicationsofBusiness

Chap3：關(guān)聯(lián)分§Singledimensionalvs.multipledimensional [0.2%,Age=30..39,e=medium buys_PC=yes[1%, Singlelevelvs.multiple- 什么品牌的啤酒和尿片（diapers）有關(guān)聯(lián) dissociationy noteatcereal[20%,PrinciplesandApplicationsofBusiness Chap3：關(guān)聯(lián)分析 ItemsItems1234…ebuys_PrinciplesandApplicationsofBusiness Chap3：關(guān)聯(lián)分析 Multiple-LevelAssociation 概念層次§低層的項通常具有較低光三§將項抽象到一定高的層次產(chǎn)生的規(guī)則更有光三§一個超市的庫存中至少milk→bread[20%,2%milk→wheatbread[6%,PrinciplesandApplicationsofBusiness Chap3：關(guān)聯(lián)分析 Multiple-LevelAssociationA,C,B,A,C,B,C,A,B,C,B,-SinglelevelrulesBC→-Multiplelevel FFC→ FDCBE§Two DCBEPrinciplesandApplicationsofBusiness Chap3：關(guān)聯(lián)分析 §當Lift<1Lift(basketball,cereal)=Lift(basketball,notCereal)=NotNotPrinciplesandApplicationsofBusiness Chap3：關(guān)聯(lián)分析 無關(guān)(負關(guān)聯(lián))規(guī)則（dissociation§發(fā)現(xiàn)帶有“非Ii” B）→1A,2B,3A,4A,C,1A, 2A,B,C 3 B,C 4A,C, PrinciplesandApplicationsofBusiness

Chap3：關(guān)聯(lián)分§Basic§Efficientandscalablefrequentitemsetminingmethods§Miningvariouskindsofassociation§§PrinciplesandApplicationsofBusiness Chap3：關(guān)聯(lián)分析 §采購籃分析（Basket ysis）,交叉銷家電HomeElectronics*(商店需要儲備proximity:atoppositeendsofthestore對哪些商品降價銷售computerprinter,reducethepriceofprinterPrinciplesandApplicationsofBusiness

Chap3：關(guān)聯(lián)分§經(jīng)過三個指標的篩選，購物籃分析的理論計算部分§另外，需要的是，購物籃分析在跟顧客分群技PrinciplesPrinciplesandApplicationsofBusiness Chap3：關(guān)聯(lián)分DoctorDoctorFraudACasePrinciplesandApplicationsofBusiness Chap3：關(guān)聯(lián)分析 HealthInsurance-TestMonitoring§DetermineifGPswereorderinginappropriatepathologytestsandifyes,whichones.§ExaminepatientrecordsforpathologytestsacrossallGPsfortestorderingpatterns(sequencesandassociations).DetermineifsomecombinationoftestswasinappropriatePrinciplesandApplicationsofBusiness Health§

Chap3：關(guān)聯(lián)分Used18millionpatientvisitsrecordstopathologists.(inonevisittherecouldbeupto20tests)UsedIBM'sassociationdiscoveryalgorithmtoseewhichtestswereperformedwithothertestsFoundthatwhenTestAwasperformedtheconfidencelevelthatBwillbeperformedwasstrikinglyhighforsomepathologiststhanothersButexpertstoldthatanother,andcheaper,TestCwasindicatedwithTestA.Thisisanindicationofmis-codingoftestsbythelab,possiblyfraudulent,toearnafewmoredollarsPrinciplesandApplicationsofBusiness Health§Thismis-codingcouldnothavebeenItisexpectedtosavethecustomerinperyear.

Chap3：關(guān)聯(lián)分excessof$1MPrinciplesandApplicationsofBusiness Chap3：關(guān)聯(lián)分析 mender§Supposewehaveadatasetrecordingwhenandwhichbookswerepurchasedbywhichcustomer(representedbyCID).Ifwewanttomendbookstousers,howcanweuseassociationrulestodothat?Describehowtobuildthetransactiondatasetinordertofindsuchrules.2010-9-2010-9-2010-9-B2,…2010-9-PrinciplesandApplicationsofBusiness A,B,C,C,D,A,A,B,E,C,D,

Chap3：關(guān)聯(lián)分§Minsup=40%,§CD→E（40%,§C→D（60%,§A→B（60%,A,B,E：up,down,up,BothAandBupimpliesEupinthenextdaywith100%