频繁模式及关联规则挖掘技术

第3课频繁模式及关联规则挖掘技术徐从富，副教授浙江大学人工智能研究所浙江大学本科生《数据挖掘导论》课件内容提纲关联规则挖掘简介关联规则基本模型关联规则价值衡量与发展参考文献I.关联规则简介关联规则反映一个事物与其他事物之间的相互依存性和关联性。如果两个或者多个事物之间存在一定的关联关系，那么，其中一个事物就能够通过其他事物预测到。典型的关联规则发现问题是对超市中的货篮数据（MarketBasket）进行分析。通过发现顾客放入货篮中的不同商品之间的关系来分析顾客的购买习惯。什么是关联规则挖掘关联规则挖掘首先被Agrawal,ImielinskiandSwami在1993年的SIGMOD会议上提出在事务、关系数据库中的项集和对象中发现频繁模式、关联规则、相关性或者因果结构频繁模式:数据库中频繁出现的项集目的:发现数据中的规律超市数据中的什么产品会一起购买？—啤酒和尿布在买了一台PC之后下一步会购买?哪种DNA对这种药物敏感?我们如何自动对Web文档进行分类?频繁模式挖掘的重要性许多重要数据挖掘任务的基础关联、相关性、因果性序列模式、空间模式、时间模式、多维关联分类、聚类分析更加广泛的用处购物篮分析、交叉销售、直销点击流分析、DNA序列分析等等II.关联规则基本模型关联规则基本模型Apriori算法Fp-Tree算法I.关联规则基本模型IBM公司Almaden研究中心的R.Agrawal首先提出关联规则模型，并给出求解算法AIS。随后又出现了SETM和Apriori等算法。其中，Apriori是关联规则模型中的经典算法。给定一组事务产生所有的关联规则满足最小支持度和最小可信度关联规则基本模型（续）设I={i1,i2,…,im}为所有项目的集合，D为事务数据库，事务T是一个项目子集（TI）。每一个事务具有唯一的事务标识TID。设A是一个由项目构成的集合，称为项集。事务T包含项集A，当且仅当AT。如果项集A中包含k个项目，则称其为k项集。项集A在事务数据库D中出现的次数占D中总事务的百分比叫做项集的支持度。如果项集的支持度超过用户给定的最小支持度阈值，就称该项集是频繁项集（或大项集）。关联规则基本模型（续）关联规则是形如XY的逻辑蕴含式，其中XI，YI，且XY=。如果事务数据库D中有s%的事务包含XY，则称关联规则XY的支持度为s%，实际上，支持度是一个概率值。若项集X的支持度记为support(X)，规则的信任度为support(XY)／support(X)。这是一个条件概率P(Y|X)。也就是：support(XY)=P(XY)confidence(XY)=P(Y|X)规则度量：支持度与可信度查找所有的规则X&YZ具有最小支持度和可信度支持度,s,一次交易中包含{X、Y、Z}的可能性可信度,c,包含{X、Y}的交易中也包含Z的条件概率交易ID购买的商品2000A,B,C1000A,C4000A,D5000B,E,F设最小支持度为50%,最小可信度为50%,则可得到AC(50%,66.6%)CA(50%,100%)买尿布的客户二者都买的客户买啤酒的客户关联规则基本模型（续）关联规则就是支持度和信任度分别满足用户给定阈值的规则。发现关联规则需要经历如下两个步骤：找出所有频繁项集。由频繁项集生成满足最小信任度阈值的规则。Letmin_support=50%,min_conf=50%:AC(50%,66.7%)CA(50%,100%)CustomerbuysdiaperCustomerbuysbothCustomerbuysbeerTransaction-idItemsbought10A,B,C20A,C30A,D40B,E,FForruleAC:support=support({A}{C})=50%confidence=support({A}{C})/support({A})=66.6%Min.support50%Min.confidence50%Transaction-idItemsbought10A,B,C20A,C30A,D40B,E,FFrequentpatternSupport{A}75%{B}50%{C}50%{A,C}50%II.Apriori算法的步骤Apriori算法命名源于算法使用了频繁项集性质的先验（Prior）知识。Apriori算法将发现关联规则的过程分为两个步骤：通过迭代，检索出事务数据库中的所有频繁项集，即支持度不低于用户设定的阈值的项集；利用频繁项集构造出满足用户最小信任度的规则。挖掘或识别出所有频繁项集是该算法的核心，占整个计算量的大部分。频繁项集为了避免计算所有项集的支持度（实际上频繁项集只占很少一部分），Apriori算法引入潜在频繁项集的概念。若潜在频繁k项集的集合记为Ck，频繁k项集的集合记为Lk，m个项目构成的k项集的集合为，则三者之间满足关系LkCk。构成潜在频繁项集所遵循的原则是“频繁项集的子集必为频繁项集”。kmCkmC关联规则的性质：性质1：频繁项集的子集必为频繁项集。性质2：非频繁项集的超集一定是非频繁的。Apriori算法运用性质1，通过已知的频繁项集构成长度更大的项集，并将其称为潜在频繁项集。潜在频繁k项集的集合Ck是指由有可能成为频繁k项集的项集组成的集合。以后只需计算潜在频繁项集的支持度，而不必计算所有不同项集的支持度，因此在一定程度上减少了计算量。Apriori算法(1)L1={频繁1项集};(2)for(k=2;Lk-1;k++)dobegin(3)Ck=apriori_gen(Lk-1);//新的潜在频繁项集(4)foralltransactionstDdobegin(5)Ct=subset(Ck,t);//t中包含的潜在频繁项集(6)forallcandidatescCtdo(7)c.count++;(8)end;(9)Lk={cCk|c.countminsup}(10)end;(11)Answer=kkL实例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}2VisualizationofAssociationRules:PaneGraphVisualizationofAssociationRules:RuleGraph提高Apriori算法的方法Hash-baseditemsetcounting（散列项集计数）Transactionreduction（事务压缩）Partitioning（划分）Sampling（采样）关联规则挖掘算法Agrawal等人提出的AIS，Apriori和AprioriTidCumulate和Stratify，Houstsma等人提出的SETMPark等人提出的DHPSavasere等人的PARTITIONHan等人提出的不生成候选集直接生成频繁模式FPGrowth其中最有效和有影响的算法为Apriori，DHP和PARTITION，FPGrowth。用Frequent-Patterntree(FP-tree)结构压缩数据库,高度浓缩，同时对频繁集的挖掘又完备的避免代价较高的数据库扫描开发一种高效的基于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-tree建立FP-tree树完备:不会打破交易中的任何模式包含了频繁模式挖掘所需的全部信息紧密去除不相关信息—不包含非频繁项支持度降序排列:支持度高的项在FP-tree中共享的机会也高决不会比原数据库大（如果不计算树节点的额外开销)FP-tree结构的好处基本思想(分而治之)用FP-tree递归增长频繁集方法对每个项，生成它的条件模式库,然后是它的条件FP-tree对每个新生成的条件FP-tree，重复这个步骤直到结果FP-tree为空,或只含唯一的一个路径(此路径的每个子路径对应的项集都是频繁集)用FP-tree挖掘频繁集1)为FP-tree中的每个节点生成条件模式库2)用条件模式库构造对应的条件FP-tree3)递归构造条件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{}f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1头表Itemfrequencyheadf4c4a3b3m3p3步骤1:从FP-tree到条件模式库Node-linkpropertyForanyfrequentitemai,allthepossiblepatternscontainingonlyfrequentitemsandaicanbeobtainedbyfollowingai’snode-links,startingfromai’sheadinthefp-treeheader.PrefixpathpropertyTocalculatethefrequentpatternswithsuffixai,onlytheprefixsubpathesofnodeslabeledaiintheFP-treeneedtobeaccumulated,andthefrequencycountofeverynodeintheprefixpathshouldcarrythesamecountasthatinthecorrespondingnodeaiinthepath.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:1m:2p:2m:1头表Itemfrequencyheadf4c4a3b3m3p3步骤2:建立条件FP-treeEmptyEmptyf{(f:3)}|c{(f: