第三章关联规则挖掘4new

数据挖掘第三章：关联规则挖掘本章内容3.1关联规则挖掘的基本概念3.2由事务数据库挖掘单维布尔关联规则3.3多层关联规则挖掘3.4多维关联规则挖掘3.5关联规则、相关性、因果关系的区别基本要求：掌握关联规则、多层关联规则、多维关联规则的基本概念，掌握各种关联规则挖掘的算法3.1基本概念关联规则挖掘：从事务数据库中发现项集之间有趣的关联.应用：购物篮分析（Basketdataanalysis）、交叉营销（cross-marketing）、产品目录设计（catalogdesign）等例子：规则形式:“BodyHead[support,confidence]”.buys(x,“diapers”)buys(x,“beers”)[0.5%,60%]major(x,“CS”)^takes(x,“DB”)grade(x,“A”)[1%,75%]3.1基本概念布尔型与数值型关联规则(基于要处理的数据类型)buys(x,“SQLServer”)^buys(x,“DMBook”)buys(x,“DBMiner”)[0.2%,60%]age(x,“30..39”)^income(x,“42..48K”)buys(x,“PC”)[1%,75%]单维与多维关联规则单层与多层关联规则Whatbrandsofbeersareassociatedwithwhatbrandsofdiapers?3.1基本概念规则度量：支持度和置信度TIDItem2000A,B,C1000A,C4000A,D5000B,E,FCustomerbuysdiaperCustomerbuysbothCustomerbuysbeer支持度s是指事务集D中包含AB的百分比Support(AB)=P(AB)置信度c是指D中包含A的事务同时也包含B的百分比Confidence(AB)=P(AB)=P(AB)/P(A)AC?CA?3.1基本概念规则度量：支持度和置信度设最小支持度阈值为50%，最小置信度阈值为50%，则有如下规则AC(50%,66.6%)CA(50%,100%)同时满足最小支持度阈值和最小置信度阈值的规则称作强规则3.1基本概念关联规则的形式化表示LetI={i1,i2,…,im}beasetofitems.LetDbeasetoftransactions,whereeachtransactionTisasetofitemssuchthatTI.AtransactionTcontainsX,asetofsomeitemsinI,ifXT.AnassociationruleisanimplicationoftheformXY,whereXI,YI,andXY=Ø.XYholdsinthetransactionsetDwithconfidencecifc%oftransactionsinDthatcontainXalsocontainY.XYhassupportsinthetransactionsetDifs%oftransactionsinDcontainXY.3.1基本概念事物数据：商场购物数据Marketbaskettransactions:t1:{bread,cheese,milk}t2:{apple,eggs,salt,yogurt}……tn:{biscuit,eggs,milk}Concepts:Anitem:anitem/articleinabasketI:thesetofallitemssoldinthestoreAtransaction:itemspurchasedinabasket;itmayhaveTID(transactionID)Atransactionaldataset:Asetoftransactions3.1基本概念事物数据：文档数据集每个文档都可以看作一个词袋（bagofwords）doc1:Student,Teach,Schooldoc2:Student,Schooldoc3:Teach,School,City,Gamedoc4:Baseball,Basketballdoc5:Basketball,Player,Spectatordoc6:Baseball,Coach,Game,Teamdoc7:Basketball,Team,City,Game本章内容3.1关联规则挖掘的基本概念3.2由事务数据库挖掘单维布尔关联规则3.3多层关联规则挖掘3.4多维关联规则挖掘3.5关联规则、相关性、因果关系的区别3.2由事务数据库挖掘布尔关联规则关联规则挖掘的原始算法：枚举每个可能的规则，计算其支持度与置信度。包含d个项目的数据集中可能的规则数目为x1231111dddkkdjjkdkdRIfd=6,R=602rules3.2由事务数据库挖掘布尔关联规则频繁项集性质向下封闭性质（Downwardclosure）：频繁项集的任意子集都是频繁的•如果{beer,diaper,nuts}是频繁的,则{beer,diaper}也是频繁的•任何含有{beer,diaper,nuts}的事物数据也包含{beer,diaper}Apriori修剪原理：非频繁项集的任意超集都是非频繁的，无需生成与测试3.2由事务数据库挖掘布尔关联规则FoundtobeInfrequentnullABACADAEBCBDBECDCEDEABCDEABCABDABEACDACEADEBCDBCEBDECDEABCDABCEABDEACDEBCDEABCDEnullABACADAEBCBDBECDCEDEABCDEABCABDABEACDACEADEBCDBCEBDECDEABCDABCEABDEACDEBCDEABCDEPrunedsupersetsClosedPatternsandMax-PatternsAlongpatterncontainsacombinatorialnumberofsub-patterns,e.g.,{a1,…,a100}contains(1001)+(1002)+…+(110000)=2100–1=1.27*1030sub-patterns!Solution:Mineclosedpatternsandmax-patternsinsteadAnitemsetXisclosedifXisfrequentandthereexistsnosuper-patternYכX,withthesamesupportasXAnitemsetXisamax-patternifXisfrequentandthereexistsnofrequentsuper-patternYכXClosedpatternisalosslesscompressionoffreq.patterns•Reducingthe#ofpatternsandrules3.2由事务数据库挖掘布尔关联规则ClosedPatternsandMax-Patternsamaximalitemsetisacloseditemsetbutacloseditemsetisnotnecessarilyamaximalitemset.3.2由事务数据库挖掘布尔关联规则ClosedPatternsandMax-PatternsExercise.DB={a1,…,a100,a1,…,a50}•Min_sup=1.Whatisthesetofcloseditemset?•a1,…,a100:?•a1,…,a50:?Whatisthesetofmax-pattern?•a1,…,a100:?Whatisthesetofallpatterns?•!!3.2由事务数据库挖掘布尔关联规则3.2由事务数据库挖掘布尔关联规则Apriori算法Ck:候选k-项集Lk:频繁k-项集Join阶段:Ck由Lk-1链接而成Prune阶段:任何包含非频繁的(k-1)-项集都不可能是频繁的k-项集3.2由事务数据库挖掘布尔关联规则Apriori算法1)L1={large1-itemsets};2)for(k=2;Lk-1Ø;k++)dobegin3)Ck=apriori-gen(Lk-1);//Newcandidates4)foralltransactionstDdobegin5)Ct=subset(Ck,t);//Candidatescontainedint6)forallcandidatescCtdo7)c.count++;8)end9)Lk={cCk|c.countminsup}10)end11)Answer=kLk;3.2由事务数据库挖掘布尔关联规则Apriori候选集生成apriori-gen函数以所有的(k–1)项集的集合Lk–1为输入，返回所有k-项集的集合Ck.首先,在join阶段:insertintoCkselectp.item1,p.item2,…,p.itemk–1,q.itemk–1fromLk–1p,Lk–1qwherep.item1=q.item1,…,p.itemk–2=q.itemk–2,p.itemk–1q.itemk–1其次,在prune阶段,删除所有的满足(k–1)子集不在Lk–1的项集cCk:forallitemsetscCkdoforall(k–1)-subsetssofcdoif(sLk–1)thendeletecfromCk;3.2由事务数据库挖掘布尔关联规则L3={abc,abd,acd,ace,bcd}Self-joining:L3*L3abcdfromabcandabdacdefromacdandacePruning:acdeisremovedbecauseadeisnotinL3C4={abcd}3.2由事务数据库挖掘布尔关联规则Apriori算法举例TIDItems100134200235300123540025DatabaseDitemsetsup.{1}2{2}3{3}3{4}1{5}3itemsetsup.{1}2{2}3{3}3{5}3ScanDC1L1itemset{12}{13}{15}{23}{25}{35}itemsetsup{12}1{13}2{15}1{23}2{25}3{35}2itemsetsup{13}2{23}2{25}3{35}2L2C2C2ScanDC3L3itemset{235}ScanDitemsetsup{235}2由频繁项集产生关联规则同时满足最小支持度和最小置信度的才是强关联规则，从频繁项集产生的规则都满足支持度要求，而其置信度则可由以下公式计算：每个关联规则可由如下过程产生：•对于每个频繁项集l，产生l的所有非空子集；•对于每个非空子集s，如果则输出规则“”3.2由事务数据库挖掘布尔关联规则)(_sup)(_sup)|()(AcountportBAcountportBAPBAconfidenceconfscountportlcountportmin_)(_sup)(_sup)(sls如果{A,B,C,D}频繁项集，候选规则为:ABCD,ABDC,ACDB,BCDA,ABCD,BACD,CABD,DABCABCD,ACBD,ADBC,BCAD,BDAC,CDAB如果|L|=k,那么有2k–2候选规则(忽略LandL)候选规则天生满足最小支持度，关键是需要判断是否满足最小置信度3.2由事务数据库挖掘布尔关联规则3.2由事务数据库挖掘布尔关联规则如何有效地从频繁项集生成关联规则一般来说，置信度不具有反单调性c(ABCD)canbelargerorsmallerthanc(ABD)有相同项集生成的规则的置信