您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 质量控制/管理 > 第6章:从大数据库中挖掘关联规则(张晓辉-复旦大学)
2001-11-6数据挖掘:概念和技术1数据挖掘:概念和技术—Chapter6—©张晓辉xiaohui@fudan.edu复旦大学(国际)数据库研究中心2001-11-6数据挖掘:概念和技术2第6章:从大数据库中挖掘关联规则关联规则挖掘从交易数据库中挖掘一维的布尔形关联规则从交易数据库中挖掘多层次关联规则在交易数据库和数据仓库中挖掘多维关联规则从关联挖掘到相关性分析基于约束的关联挖掘小结2001-11-6数据挖掘:概念和技术3什么是关联挖掘?关联规则挖掘:在交易数据、关系数据或其他信息载体中,查找存在于项目集合或对象集合之间的频繁模式、关联、相关性、或因果结构。应用:购物篮分析、交叉销售、产品目录设计、loss-leaderanalysis、聚集、分类等。举例:规则形式:“Bodyead[support,confidence]”.buys(x,“diapers”)buys(x,“beers”)[0.5%,60%]major(x,“CS”)^takes(x,“DB”)grade(x,“A”)[1%,75%]2001-11-6数据挖掘:概念和技术4关联规则:基本概念给定:(1)交易数据库(2)每笔交易是:一个项目列表(消费者一次购买活动中购买的商品)查找:所有描述一个项目集合与其他项目集合相关性的规则E.g.,98%ofpeoplewhopurchasetiresandautoaccessoriesalsogetautomotiveservicesdone应用*护理用品(商店应该怎样提高护理用品的销售?)家用电器*(其他商品的库存有什么影响?)在产品直销中使用附加邮寄Detecting“ping-pong”ingofpatients,faulty“collisions”2001-11-6数据挖掘:概念和技术5规则度量:支持度与可信度查找所有的规则X&YZ具有最小支持度和可信度支持度,s,一次交易中包含{X、Y、Z}的可能性可信度,c,包含{X、Y}的交易中也包含Z的条件概率交易ID购买的商品2000A,B,C1000A,C4000A,D5000B,E,F设最小支持度为50%,最小可信度为50%,则可得到AC(50%,66.6%)CA(50%,100%)买尿布的客户二者都买的客户买啤酒的客户2001-11-6数据挖掘:概念和技术6关联规则挖掘:路线图布尔vs.定量关联(基于处理数据的类型)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%]单维vs.多维关联(例子同上)单层vs.多层分析那个品种牌子的啤酒与那个牌子的尿布有关系?各种扩展相关性、因果分析关联并不一定意味着相关或因果最大模式和闭合相集添加约束如,哪些“小东西”的销售促发了“大家伙”的买卖?2001-11-6数据挖掘:概念和技术7第6章:从大数据库中挖掘关联规则关联规则挖掘从交易数据库中挖掘一维的布尔形关联规则从交易数据库中挖掘多层次关联规则在交易数据库和数据仓库中挖掘多维关联规则从关联挖掘到相关性分析基于约束的关联挖掘小结2001-11-6数据挖掘:概念和技术8关联规则挖掘—一个例子对于AC:support=support({A、C})=50%confidence=support({A、C})/support({A})=66.6%Apriori的基本思想:频繁项集的任何子集也一定是频繁的交易ID购买商品2000A,B,C1000A,C4000A,D5000B,E,F频繁项集支持度{A}75%{B}50%{C}50%{A,C}50%最小值尺度50%最小可信度50%2001-11-6数据挖掘:概念和技术9关键步骤:挖掘频繁集频繁集:是指满足最小支持度的项目集合频繁集的子集也一定是频繁的如,如果{AB}是频繁集,则{A}{B}也一定是频繁集从1到k(k-频繁集)递归查找频繁集用得到的频繁集生成关联规则2001-11-6数据挖掘:概念和技术10Apriori算法连接:用Lk-1自连接得到Ck修剪:一个k-项集,如果他的一个k-1项集(他的子集)不是频繁的,那他本身也不可能是频繁的。伪代码:Ck:CandidateitemsetofsizekLk:frequentitemsetofsizekL1={frequentitems};for(k=1;Lk!=;k++)dobeginCk+1=candidatesgeneratedfromLk;foreachtransactiontindatabasedoincrementthecountofallcandidatesinCk+1thatarecontainedintLk+1=candidatesinCk+1withmin_supportendreturnkLk;2001-11-6数据挖掘:概念和技术11Apriori算法—例子TIDItems100134200235300123540025数据库Ditemsetsup.{1}2{2}3{3}3{4}1{5}3itemsetsup.{1}2{2}3{3}3{5}3扫描DC1L1itemset{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}2L2C2C2扫描DC3L3itemset{235}扫描Ditemsetsup{235}22001-11-6数据挖掘:概念和技术12如何生成候选集假定Lk-1中的项按顺序排列第一步:自连接Lk-1insertintoCkselectp.item1,p.item2,…,p.itemk-1,q.itemk-1fromLk-1p,Lk-1qwherep.item1=q.item1,…,p.itemk-2=q.itemk-2,p.itemk-1q.itemk-1第二步:修剪forallitemsetscinCkdoforall(k-1)-subsetssofcdoif(sisnotinLk-1)thendeletecfromCk2001-11-6数据挖掘:概念和技术13如何计算候选集的支持度计算支持度为什么会成为一个问题?候选集的个数非常巨大一笔交易可能包含多个候选集方法:用hash-tree存放候选集树的叶子节点of存放项集的列表和支持度内部节点是一个hash表Subset函数:找到包含在一笔交易中的所有候选集2001-11-6数据挖掘:概念和技术14生成候选集的例子L3={abc,abd,acd,ace,bcd}自连接:L3*L3abc和abd得到abcdacd和ace得到acde修剪:ade不在L3中,删除acdeC4={abcd}2001-11-6数据挖掘:概念和技术15提高Apriori效率的方法基于Hash的项集计数:如果一个k-项集在hash-tree的路径上的一个计数值低于阈值,那他本身也不可能是频繁的。减少交易记录:不包含任何频繁k-项集的交易也不可能包含任何大于k的频繁集分割:一个项集要想在整个数据库中是频繁的,那么他至少在数据库的一个分割上是频繁的。采样:在给定数据的子集上挖掘,使用小的支持度+完整性验证方法动态项集计数:在添加一个新的候选集之前,先估计一下是不是他的所有子集都是频繁的。2001-11-6数据挖掘:概念和技术16Apriori够快了吗?—性能瓶颈Apriori算法的核心:用频繁的(k–1)-项集生成候选的频繁k-项集用数据库扫描和模式匹配计算候选集的支持度Apriori的瓶颈:候选集生成巨大的候选集:104个频繁1-项集要生成107个候选2-项集要找尺寸为100的频繁模式,如{a1,a2,…,a100},你必须先产生21001030个候选集多次扫描数据库:如果最长的模式是n的话,则需要(n+1)次数据库扫描2001-11-6数据挖掘:概念和技术17挖掘频繁集不用生成候选集用Frequent-Patterntree(FP-tree)结构压缩数据库,高度浓缩,同时对频繁集的挖掘又完备的避免代价较高的数据库扫描开发一种高效的基于FP-tree的频繁集挖掘算法采用分而治之的方法学:分解数据挖掘任务为小任务避免生成关联规则:只使用部分数据库!2001-11-6数据挖掘:概念和技术18用交易数据库建立FP-tree{}f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1头表Itemfrequencyheadf4c4a3b3m3p3最小支持度=0.5TIDItemsbought(ordered)frequentitems100{f,a,c,d,g,i,m,p}{f,c,a,m,p}200{a,b,c,f,l,m,o}{f,c,a,b,m}300{b,f,h,j,o}{f,b}400{b,c,k,s,p}{c,b,p}500{a,f,c,e,l,p,m,n}{f,c,a,m,p}步骤:1.扫描数据库一次,得到频繁1-项集2.把项按支持度递减排序3.再一次扫描数据库,建立FP-tree2001-11-6数据挖掘:概念和技术19FP-tree结构的好处完备:不会打破交易中的任何模式包含了序列模式挖掘所需的全部信息紧密去除不相关信息—不包含非频繁项支持度降序排列:支持度高的项在FP-tree中共享的机会也高决不会比原数据库大(如果不计算树节点的额外开销)例子:对于Connect-4数据库,压缩率超过1002001-11-6数据挖掘:概念和技术20用FP-tree挖掘频繁集基本思想(分而治之)用FP-tree地归增长频繁集方法对每个项,生成它的条件模式库,然后是它的条件FP-tree对每个新生成的条件FP-tree,重复这个步骤直到结果FP-tree为空,或只含维一的一个路径(此路径的每个子路径对应的相集都是频繁集)2001-11-6数据挖掘:概念和技术21挖掘FP-tree的主要步骤1)为FP-tree中的每个节点生成条件模式库2)用条件模式库构造对应的条件FP-tree3)递归构造条件FP-trees同时增长其包含的频繁集如果条件FP-tree直包含一个路径,则直接生成所包含的频繁集。2001-11-6数据挖掘:概念和技术22步骤1:从FP-tree到条件模式库从FP-tree的头表开始按照每个频繁项的连接遍历FP-tree列出能够到达此项的所有前缀路径,得到条件模式库条件模式库itemcond.patternbasecf:3afc:3bfca:1,f:1,c:1mfca:2,fcab:1pfcam:2,cb:1{}f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1头表Itemfrequencyheadf4c4a3b3m3p32001-11-6数据挖掘:概念和技术23FP-tree支持条件模式库构造的属性节点裢接任何包含ai,的可能频繁集,都可以从FP-tree头表中的ai沿着ai的节点链接得到前缀路径要计算路径P中包含节点ai的频繁集,只要考察到达ai的路径前缀即可,且其支持度等于节点ai的支持度2001-11-6数据挖掘:概念和技术24步骤2:建立条件FP-tree对每个模式库计算库中每个项的支持度用模式库中的频繁项建立FP-treem-条件模是库:fca:2,fcab:1{}f:3c:3a:3m-conditionalFP-treeAllfrequentpatternsconcerningmm,fm,cm,am,fcm,fam,cam,fcam{}f:4c:1b:1p:1b:1c:3a:3b:1
本文标题:第6章:从大数据库中挖掘关联规则(张晓辉-复旦大学)
链接地址:https://www.777doc.com/doc-3222160 .html