数据挖掘导论之频繁模式及关联规则挖掘技术(.ppt

第3课频繁模式及关联规则挖掘技术,徐从富，副教授浙江大学人工智能研究所,浙江大学本科生数据挖掘导论课件,内容提纲,关联规则挖掘简介关联规则基本模型关联规则价值衡量与发展参考文献,关联规则简介,关联规则反映一个事物与其他事物之间的相互依存性和关联性。如果两个或者多个事物之间存在一定的关联关系，那么，其中一个事物就能够通过其他事物预测到。典型的关联规则发现问题是对超市中的货篮数据（MarketBasket）进行分析。通过发现顾客放入货篮中的不同商品之间的关系来分析顾客的购买习惯。,什么是关联规则挖掘,关联规则挖掘首先被Agrawal,ImielinskiandSwami在1993年的SIGMOD会议上提出在事务、关系数据库中的项集和对象中发现频繁模式、关联规则、相关性或者因果结构频繁模式:数据库中频繁出现的项集目的:发现数据中的规律超市数据中的什么产品会一起购买？啤酒和尿布在买了一台PC之后下一步会购买?哪种DNA对这种药物敏感?我们如何自动对Web文档进行分类?,频繁模式挖掘的重要性,许多重要数据挖掘任务的基础关联、相关性、因果性序列模式、空间模式、时间模式、多维关联分类、聚类分析更加广泛的用处购物篮分析、交叉销售、直销点击流分析、DNA序列分析等等,关联规则基本模型,关联规则基本模型Apriori算法Fp-Tree算法,关联规则基本模型,IBM公司Almaden研究中心的R.Agrawal首先提出关联规则模型，并给出求解算法AIS。随后又出现了SETM和Apriori等算法。其中，Apriori是关联规则模型中的经典算法。给定一组事务产生所有的关联规则满足最小支持度和最小可信度,关联规则基本模型（续）,设I=i1,i2,im为所有项目的集合，D为事务数据库，事务T是一个项目子集（TI）。每一个事务具有唯一的事务标识TID。设A是一个由项目构成的集合，称为项集。事务T包含项集A，当且仅当AT。如果项集A中包含k个项目，则称其为k项集。项集A在事务数据库D中出现的次数占D中总事务的百分比叫做项集的支持度。如果项集的支持度超过用户给定的最小支持度阈值，就称该项集是频繁项集（或大项集）。,关联规则基本模型（续）,关联规则是形如XY的逻辑蕴含式，其中XI，YI，且XY=。如果事务数据库D中有s%的事务包含XY，则称关联规则XY的支持度为s%，实际上，支持度是一个概率值。若项集X的支持度记为support(X)，规则的信任度为support(XY)support(X)。这是一个条件概率P(Y|X)。也就是：support(XY)=P(XY)confidence(XY)=P(Y|X),规则度量：支持度与可信度,查找所有的规则X(2)for(k=2;Lk-1;k+)dobegin(3)Ck=apriori_gen(Lk-1);/新的潜在频繁项集(4)foralltransactionstDdobegin(5)Ct=subset(Ck,t);/t中包含的潜在频繁项集(6)forallcandidatescCtdo(7)c.count+;(8)end;(9)Lk=cCk|c.countminsup(10)end;(11)Answer=,实例,DatabaseTDB,1stscan,C1,L1,L2,C2,C2,2ndscan,C3,L3,3rdscan,VisualizationofAssociationRules:PaneGraph,VisualizationofAssociationRules:RuleGraph,提高Apriori算法的方法,Hash-baseditemsetcounting（散列项集计数）Transactionreduction（事务压缩）Partitioning（划分）Sampling（采样）,关联规则挖掘算法,Agrawal等人提出的AIS，Apriori和AprioriTidCumulate和Stratify，Houstsma等人提出的SETMPark等人提出的DHPSavasere等人的PARTITIONHan等人提出的不生成候选集直接生成频繁模式FPGrowth其中最有效和有影响的算法为Apriori，DHP和PARTITION，FPGrowth。,用Frequent-Patterntree(FP-tree)结构压缩数据库,高度浓缩，同时对频繁集的挖掘又完备的避免代价较高的数据库扫描开发一种高效的基于FP-tree的频繁集挖掘算法采用分而治之的方法学：分解数据挖掘任务为小任务避免生成关联规则:只使用部分数据库!,挖掘频繁集不用生成候选集,最小支持度=0.5,TIDItemsbought(ordered)frequentitems100f,a,c,d,g,i,m,pf,c,a,m,p200a,b,c,f,l,m,of,c,a,b,m300b,f,h,j,of,b400b,c,k,s,pc,b,p500a,f,c,e,l,p,m,nf,c,a,m,p,步骤:扫描数据库一次，得到频繁1-项集把项按支持度递减排序再一次扫描数据库，建立FP-tree,建立FP-tree树,完备:不会打破交易中的任何模式包含了频繁模式挖掘所需的全部信息紧密去除不相关信息不包含非频繁项支持度降序排列:支持度高的项在FP-tree中共享的机会也高决不会比原数据库大（如果不计算树节点的额外开销),FP-tree结构的好处,基本思想(分而治之)用FP-tree递归增长频繁集方法对每个项，生成它的条件模式库,然后是它的条件FP-tree对每个新生成的条件FP-tree，重复这个步骤直到结果FP-tree为空,或只含唯一的一个路径(此路径的每个子路径对应的项集都是频繁集),用FP-tree挖掘频繁集,为FP-tree中的每个节点生成条件模式库用条件模式库构造对应的条件FP-tree递归构造条件FP-trees同时增长其包含的频繁集如果条件FP-tree只包含一个路径，则直接生成所包含的频繁集。如果条件FP-tree包含多个路径，则采用混合的方法,挖掘FP-tree的主要步骤,从FP-tree的头表开始按照每个频繁项的连接遍历FP-tree列出能够到达此项的所有前缀路径，得到条件模式库,条件模式库itemcond.patternbasecf:3afc:3bfca:1,f:1,c:1mfca:2,fcab:1pfcam:2,cb:1,步骤1:从FP-tree到条件模式库,Node-linkpropertyForanyfrequentitemai,allthepossiblepatternscontainingonlyfrequentitemsandaicanbeobtainedbyfollowingaisnode-links,startingfromaisheadinthefp-treeheader.PrefixpathpropertyTocalculatethefrequentpatternswithsuffixai,onlytheprefixsubpathesofnodeslabeledaiintheFP-treeneedtobeaccumulated,andthefrequencycountofeverynodeintheprefixpathshouldcarrythesamecountasthatinthecorrespondingnodeaiinthepath.,FP-tree支持条件模式库构造的属性,对每个模式库计算库中每个项的支持度用模式库中的频繁项建立FP-tree,m-条件模式库:fca:2,fcab:1,Allfrequentpatternsconcerningmm,fm,cm,am,fcm,fam,cam,fcam,f:4,c:1,b:1,p:1,b:1,c:3,a:3,b:1,m:2,p:2,m:1,头表Itemfrequencyheadf4c4a3b3m3p3,步骤2:建立条件FP-tree,通过建立条件模式库得到频繁集,“am”的条件模式库:(fc:3),“cm”的条件模式:(f:3),f:3,cm-条件FP-tree,“cam”条件模式库:(f:3),f:3,cam-条件FP-tree,递归挖掘条件FP-tree,关联规则价值衡量与发展,关联规则价值衡量关联规则最新进展,规则价值衡量,对关联规则的评价与价值衡量涉及两个层面：系统客观的层面用户主观的层面,系统客观层面,使用“支持度和信任度”框架可能会产生一些不正确的规则。只凭支持度和信任度阈值未必总能找出符合实际的规则。,用户主观层面,只有用户才能决定规则的有效性、可行性。所以，应该将用户的需求和系统更加紧密地结合起来。可以采用基于约束（Consraint-based）的数据挖掘方法。具体约束的内容有：数据约束、限定数据挖掘的维和层次、规则约束。如果把某些约束条件与算法紧密结合，既能提高数据挖掘效率，又能明确数据挖掘的目标。,关联规则新进展,在基于一维布尔型关联规则的算法研究中先后出现了AIS、SETM等数据挖掘算法。R.Agrawal等人提出的Apriori是经典算法。随后的关联规则发现算法大多数建立在Apriori算法基础上，或进行改造，或衍生变种。比如AprioriTid和AprioriHybrid算法。Lin等人提出解决规则挖掘算法中的数据倾斜问题，从而使算法具有较好的均衡性。Park等人提出把哈希表结构用于关联规则挖掘。,关联规则新进展（续）,数据挖掘工作是在海量数据库上进行的，数据库的规模对规则的挖掘时间有很大影响。Agrawal首先提出事务缩减技术，Han和Park等人也分别在减小数据规模上做了一些工作。抽样的方法是由Toivonen提出的。Brin等人采用动态项集计数方法求解频繁项集。Aggarwal提出用图论和格的理论求解频繁项集的方法。Prutax算法就是用格遍历的办法求解频繁项集。,关联规则新进展（续）,关联规则模型有很多扩展，如顺序模型挖掘，在顺序时间段上进行挖掘等。还有挖掘空间关联规则，挖掘周期性关联规则，挖掘负关联规则，挖掘交易内部关联规则等。Guralnik提出顺序时间段问题的形式描述语言，以便描述用户感兴趣的时间段，并且构建了有效的数据结构SP树（顺序模式树）和自底向上的数据挖掘算法。最大模式挖掘是Bayardo等人提出来的。,关联规则新进展（续）,随后人们开始探讨频率接近项集。Pei给出了一种有效的数据挖掘算法。B.zden等人的周期性关联规则是针对具有时间属性的事务数据库，发现在规律性的时间间隔中满足最小支持度和信任度的规则。贝尔实验室的S.Ramaswamy等人进一步发展了周期性关联规则，提出挖掘符合日历的关联规则（CalendricAssociationRules）算法，用以进行市场货篮分析。Fang等人给出冰山查询数据挖掘算法。,关联规则新进展（续）,T.Hannu等人把负边界引入规则发现算法中，每次挖掘不仅保存频繁项集，而且同时保存负边界，达到下次挖掘时减少扫描次数的目的。Srikant等人通过研究关联规则的上下文，提出规则兴趣度尺度用以剔除冗余规则。Zakia还用项集聚类技术求解最大的近似潜在频繁项集，然后用格迁移思想生成每个聚类中的频繁项集。CAR，也叫分类关联规则，是Lin等人提出的一种新的分类方法，是分类技术与关联规则思想相结合的产物，并给出解决方案和算法。,关联规则新进展（续）,Cheung等人提出关联规则的增量算法。Thomas等人把负边界的概念引入其中，进一步发展了增量算法。如，基于Apriori框架的并行和分布式数据挖掘算法。Oates等人将MSDD算法改造为分布式算法。还有其他的并行算法，如利用垂直数据库探求项集聚类等。,参考文献,AgrawalR,ImielinskiT,andSwamiA.Miningassociationrulesbetweensetsofitemsinlargedatabases.SIGMOD,207-216,1993.AgrawalR,andSrikantR.Fastalgorithmsforminingassociationrulesinl