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

第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&YZ具有最最小支支持度度和可可信度度支持度度,s,一一次交交易中中包含含{X、、Y、、Z}的的可能性性可信度度,c,包含{X、、Y}的交交易中中也包包含Z的条件概概率设最小小支持持度为为50%,最最小可可信度度为50%,则则可得得到AC(50%,66.6%)CA(50%,100%)买尿布布的客客户二者都都买的的客户户买啤酒酒的客客户关联规规则基基本模模型（（续））关联规规则就就是支支持度度和信信任度度分别别满足足用户户给定定阈值值的规规则。。发现关关联规规则需需要经经历如如下两两个步步骤：：找出所所有频频繁项项集。。由频繁繁项集集生成成满足足最小小信任任度阈阈值的的规则则。Letmin_support=50%,min_conf=50%:AC(50%,66.7%)CA(50%,100%)CustomerbuysdiaperCustomerbuysbothCustomerbuysbeerTransaction-idItemsbought10A,B,C20A,C30A,D40B,E,FForruleAC: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%Apriori算法法的步步骤Apriori算法法命名名源于于算法法使用用了频频繁项项集性性质的的先验验（Prior）知知识。。Apriori算法法将发发现关关联规规则的的过程程分为为两个个步骤骤：通过迭迭代，，检索索出事事务数数据库库中的的所有有频繁繁项集集，即即支持持度不不低于于用户户设定定的阈阈值的的项集集；利用频频繁项项集构构造出出满足足用户户最小小信任任度的的规则则。挖掘或或识别别出所所有频频繁项项集是是该算算法的的核心心，占占整个个计算算量的的大部部分。。频繁繁项项集集为了了避避免免计计算算所所有有项项集集的的支支持持度度（（实实际际上上频频繁繁项项集集只只占占很很少少一一部部分分）），，Apriori算算法法引引入入潜潜在在频频繁繁项项集集的的概概念念。。若若潜潜在在频频繁繁k项集集的的集集合合记记为为Ck，频频繁繁k项集集的的集集合合记记为为Lk，m个项项目目构构成成的的k项集集的的集集合合为为，，则则三三者者之之间间满满足足关关系系LkCk。构构成成潜潜在在频频繁繁项项集集所所遵遵循循的的原原则则是是““频频繁繁项项集集的的子子集集必必为为频频繁繁项项集集””。。关联联规规则则的的性性质质：：性质质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)foralltransactionstDdobegin(5)Ct=subset(Ck,t);//t中中包包含含的的潜潜在在频频繁繁项项集集(6)forallcandidatescCtdo(7)c.count++;(8)end;(9)Lk={cCk|c.countminsup}(10)end;(11)Answer=实例例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和和AprioriTidCumulate和和Stratify，，Houstsma等等人人提提出出的的SETMPark等等人人提提出出的的DHPSavasere等等人人的的PARTITIONHan等等人人提提出出的的不不生生成成候候选选集集直直接接生生成成频频繁繁模模式式FPGrowth其中最有有效和有有影响的的算法为为Apriori，DHP和和PARTITION，FPGrowth。用Frequent-Patterntree(FP-tree)结构构压缩数数据库,高度浓缩缩，同时时对频繁繁集的挖挖掘又完完备的避免代价价较高的的数据库库扫描开发一种种高效的的基于FP-tree的频繁繁集挖掘掘算法采用分而而治之的的方法学学：分解解数据挖挖掘任务务为小任任务避免生成成关联规规则:只只使用用部分数数据库!挖掘频繁繁集不用生成成候选集集{}f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1头表Itemfrequencyheadf 4c 4a 3b 3m 3p 3最小支持持度=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-项集集把项按支支持度递递减排序序再一次扫扫描数据据库，建建立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列出能够够到达此此项的所所有前缀缀路径，，得到条条件模式式库条件模式式库item cond.patternbasec f:3a fc:3b fca:1,f:1,c:1m fca:2,fcab:1p fcam:2,cb:1{}f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1头表Itemfrequencyheadf 4c 4a 3b 3m 3p 3步骤1:从FP-tree到到条件模模式库Node-linkpropertyForanyfrequentitemai,allthepossiblepatternscontainingonlyfrequentitemsandaicanbeobtainedbyfollowingai’snode-links,startingfromai’sheadinthefp-treeheader.PrefixpathpropertyTocalculatethefrequentpatternswithsuffixai,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头表Itemfrequencyheadf 4c 4a 3b 3m 3p 3步骤2:建建立条件FP-treeEmptyEmptyf{(f:3)}|c{(f:3)}c{(f:3,c:3)}|a{(fc:3)}aEmpty{(fca:1),(f:1),(c:1)}b{(f:3,c:3,a:3)}|m{(fca:2),(fcab:1)}m{(c:3)}|p{(fcam:2),(cb:1)}p条件FP-tree条件模式库项通过建立条件件模式库得到到频繁集{}f:3c:3a:3m-条件

FP-tree“am”的条条件模式库:(fc:3){}f:3c:3am-条件FP-tree“cm”的条条件模式:(f:3){}f:3cm-条件FP-tree“cam”条条件模式库:(f:3){}f:3cam-条件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.Fastalgorithmsforminingassociationrulesinlargedatabases.VLDB,478-499,1994.HanJW,PeiJ,YinYW.Miningfrequentpatternswithoutcandidategeneration.SIGMOD,1-12,2000.HanJW,PeiJ,YinYW,andMaoRY.Miningfrequentpatternswithoutcandidategeneration:afrequent-patterntreeapproach.DataMiningandKnowledgeDiscovery.8,53-87,20049、静静夜夜四四无无邻邻，，荒荒居居旧旧业业贫贫。。。。12月月-2212月月-22Thursday,December29,202210、雨雨中中黄黄叶叶树树，，灯灯下下白白头头人人。。。。13:55:2213:55:2213:5512/29/20221:55:22PM11、以以我我独独沈沈久久，，愧愧君君相相见见频频。。。。12月月-2213:55:2213:55Dec-2229-Dec-2212、故人江海别别，几度隔山山川。。13:55:2213:55:2213:55Thursday,December29,202213、乍乍见见翻翻疑疑梦梦，，相相悲悲各各问问年年。。。。12月月-2212月月-2213:55:2213:55:22December29,202214、他乡生生白发，，旧国见见青山。。。29十十二月20221:55:22下午午13:55:2212月-2215、比比不不了了得得就就不不比比，，得得不不到到的的就就不不要要。。。。。十二二月月221:55下下午午12月月-2213:55December29,202216、行动出出成果，，工作出出财富。。。2022/12/2913:55:2213:55:2229December202217、做前，能能够环视四四周；做时时，你只能能或者最好好沿着以脚脚为起点的的射线向前前。。1:55:22下下午1:55下下午13:55:2212月-229、没有失败，，只有暂时停停止成功！。。12月-2212月-22Thursday,December29,202210、很很多多事事情情努努力力了了未未必必有有结结果果，，但但是是不不努努力力却却什什么么改改变变也也没没有有。。。。13:55:2213:55:2213:5512/29/20221:55:22PM11、成功就就是日复复一日那那一点点点小小努努力的积积累。。。12月-2213:55:2313:55Dec-2229-Dec-2212、世间成事，，不求其绝对对圆满，留一一份不足，可可得无限完美美。。13:55:2313:55:2313:55Thursday,December29,202213、不知香香积寺，，数里入入云峰。。。12月-