CHAPTER6-挖掘关联规则

费高雷通信与信息工程学院2015年春季第6章挖掘频繁模式、关联和相关性：基本概念和方法2第6章：挖掘频繁模式、关联和相关性：基本概念和方法基本概念频繁项集挖掘方法那些模式是有趣的：模式评估方法小结3什么是频繁模式分析?频繁模式:频繁出现在数据集中的模式（如项集、子序列或子结构）首先被Agrawal,ImielinskiandSwami在1993年的SIGMOD会议上提出，称为频繁项集和关联规则挖掘驱动:发现数据中的内在规律超市数据中的什么产品会一起购买？—啤酒和尿布在买了一台PC之后下一步会购买?哪种DNA对这种药物敏感?我们如何自动对Web文档进行分类?更加广泛的用处购物篮分析、交叉销售、直销点击流分析、DNA序列分析等等什么是频繁模式分析?5频繁模式挖掘为什么重要?频繁模式:数据集内在和重要的属性许多重要数据挖掘任务的基础关联,相关,和因果分析序列模式,空间模式（比如子图）时空模式分析,多媒体,时间序列和流数据分类:discriminative,frequentpatternanalysis聚类分析:基于频繁模式的聚类数据仓库:icebergcubeandcube-gradient语义数据压缩:fascicles更广泛应用6关联规则基本模型设I={i1,…,im}为所有项目的集合；D为事务数据库，事务T是一个项目子集（TI）。每一个事务具有唯一的事务标识TID项集：由项目构成的集合，为了方便表述用用A表示事务T包含项集A，当且仅当AT如果项集A中包含k个项目，则称其为k项集支持度：项集A在事务数据库D中出现的次数占D中总事务的百分比频繁项集（或大项集）：项集的支持度超过用户给定的最小支持度阈值交易ID购买的商品2000a,b,c1000a,c4000a,d5000b,e,fI={a,b,c,d,e,f}若A={a,c}，则A的支撑度为50%项属性一个事物数据对象7关联规则基本模型关联规则是形如XY的逻辑蕴含式，其中XI，YI，且XY=如果事务数据库D中有s%的事务包含XY，则称关联规则XY的支持度为s%实际上，支持度是一个概率值，是一个相对计数support(XY)=P(XY)项集的支持度计数(频率)support_count包含项集的事务数若项集X的支持度记为support(X)，规则的信任度为support(XY)／support(X)是一个条件概率P(Y|X)confidence(XY)=P(Y|X)=support_count(XY)／support_count(X)8频繁模式和关联规则itemsetX={x1,…,xk}找出满足最小支持度和置信度的所规则XY支持度s：事务包含XY的概率置信度c：事务含X也包含Y的条件概率顾客购买尿布顾客购买二者顾客购买啤酒Transaction-idItemsbought10A,B,D20A,C,D30A,D,E40B,E,F50B,C,D,E,F令supmin=50%,confmin=50%频繁模式：{A:3,B:3,D:4,E:3,AD:3}关联规则:AD(60%,100%)DA(60%,75%)9挖掘关联规则—一个例子规则AC：支持度=support({A}{C})=50%置信度=support({A}{C})/support({A})=66.6%最小支持度50%最小置信度50%Transaction-idItemsbought10A,B,C20A,C30A,D40B,E,FFrequentpatternSupport{A}75%{B}50%{C}50%{A,C}50%挖掘关联规则(实际例子)11闭频繁项集和极大频繁项集一个长模式包含子模式的数目：e.g.,{a1,…,a100}contains(1001)+(1002)+…+(110000)=2100–1=1.27*1030sub-patterns!解:引入闭频繁项集和极大频繁项集闭项集：不存在具有相同支持度的真超项集闭频繁项集：如果X是频繁的，且不存在真超项集（super-pattern）Y（XY），使X、Y有相同的支持度计数(proposedbyPasquier,etal.@ICDT’99)极大频繁项集：如果X是频繁的，并且不存在超项集Y使得XY，并且Y是频繁的(proposedbyBayardo@SIGMOD’98)两者有不同，极大频繁项集定义中对真超集要松一些极大频繁项集nullABACADAEBCBDBECDCEDEABCDEABCABDABEACDACEADEBCDBCEBDECDEABCDABCEABDEACDEBCDEABCDEBorderInfrequentItemsetsMaximalItemsets极大频繁项集的真超项集不频繁闭频繁项集最大频繁项集存在的问题：最大频繁项集的子集是频繁的，但无法推断出其具体的支持度闭频繁项集的集合包含频繁项集的完整信息（包括支持度）例子：数据库包含两个事物，且令最小支持度为1a1,…,a100,a1,…,a50闭频繁项集{a1,…,a100}:1{a1,…,a50}:2最大频繁项集{a1,…,a100}:1所有频繁模式{a1}:2,…,{a1,a2}:2,…,{a1,a51}:1,…,{a1,a2,…,a100}:1Abignumber:2100-1?Why?闭频繁项集和极大频繁项集nullABACADAEBCBDBECDCEDEABCDEABCABDABEACDACEADEBCDBCEBDECDEABCDABCEABDEACDEBCDEABCDE12412312342453451212424412323243445122244423424Minimumsupport=2#Closed=9#Maximal=4ClosedandmaximalClosedbutnotmaximalTIDItems1ABC2ABCD3BCE4ACDE5DE闭频繁项集和极大频繁项集FrequentItemsetsClosedFrequentItemsetsMaximalFrequentItemsets16第6章：挖掘频繁模式、关联和相关性：基本概念和方法基本概念频繁项集挖掘方法那些模式是有趣的：模式评估方法小结17频繁项集挖掘方法Apriori算法:通过限制候选产生发现频繁项集提高Apriori算法的效率挖掘频繁项集的模式增长方法是用垂直数据格式挖掘频繁项集挖掘闭模式和极大模式18Apriori算法的步骤Apriori算法命名源于算法使用了频繁项集性质的先验（Prior）知识Apriori算法将发现关联规则的过程分为两个步骤：通过迭代，检索出事务数据库中的所有频繁项集，即支持度不低于用户设定的阈值的项集利用频繁项集构造出满足用户最小信任度的规则挖掘或识别出所有频繁项集是该算法的核心，占整个计算量的大部分19频繁项集为了避免计算所有项集的支持度（实际上频繁项集只占很少一部分），Apriori算法引入潜在频繁项集的概念。若潜在频繁k项集的集合记为Ck，频繁k项集的集合记为Lk则两者之间满足关系LkCk构成潜在频繁项集所遵循的原则是“频繁项集的子集必为频繁项集”。20关联规则的性质性质1：频繁项集的子集必为频繁项集性质2：非频繁项集的超集一定是非频繁的Apriori算法运用性质1，通过已知的频繁项集构成长度更大的项集，并将其称为潜在频繁项集潜在频繁k项集的集合Ck是指由有可能成为频繁k项集的项集组成的集合以后只需计算潜在频繁项集的支持度，而不必计算所有不同项集的支持度，因此在一定程度上减少了计算量21Apriori:一种候选产生-测试方法频繁项集的任何子集必须是频繁的如果{啤酒,尿布,坚果}是频繁的,{啤酒,尿布}也是每个包含{啤酒,尿布,坚果}的事务也包含{啤酒,尿布}Apriori剪枝原则:如果一个项集不是频繁的,将不产生/测试它的超集!方法:由长度为k的频繁项集产生长度为(k+1)的候选项集,并且根据DB测试这些候选性能研究表明了它的有效性和可伸缩性22Apriori算法—一个例子数据库TDB第1次扫描C1L1L2C2C2第2次扫描C3L3第3次扫描TidItems10A,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}223Apriori算法(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=kkL24Apriori的重要细节如何产生候选?步骤1:Lk的自连接步骤2:剪枝候选产生的例子L3={abc,abd,acd,ace,bcd}自连接:L3*L3abcd：由abc和abdacde：由acd和ace剪枝:acde被删除,因为ade不在L3C4={abcd}25如何产生候选?假定Lk-1中的项集已排序(按字典序排序)步骤1:Lk-1自连接（参考书本p253）insertintoCkselectp.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Step2:剪枝26教材161页例6.3（支持计数=2）27例子28由频繁项集产生关联规则根据公式产生关联规则对于每个频繁项集l，产生所有的非空子集频繁对于l的每个非空子集s，如果则输出规则”s(l-s)”29频繁模式挖掘的挑战挑战事务数据库的多遍扫描数量巨大的候选候选支持度计数繁重的工作量改进Apriori:基本思想减少事务数据库的扫描遍数压缩候选数量便于候选计数30频繁项集挖掘方法Apriori算法:通过限制候选产生发现频繁项集提高Apriori算法的效率挖掘频繁项集的模式增长方法是用垂直数据格式挖掘频繁项集挖掘闭模式和极大模式31提高Apriori算法的方法Hash-baseditemsetcounting（散列项集计数）Transactionreduction（事务压缩）Partitioning（划分）Sampling（采样）思路：降低扫描次数、提高每次扫描的效率32划分:只扫描数据库两次项集在DB中是频繁的,它必须至少在DB的一个划分中频繁扫描1:划分数据库,并找出局部频繁模式localfrequentitemset扫描2:求出全局频繁模式A.Savasere,E.Omiecinski,andS.Navathe.Anefficientalgorithmforminingassociationinlargedatabases.InVLDB’9533抽样-频繁模式选取原数据库的一个样本,使用Apriori算法在样本中挖掘频繁模式扫描一次数据库,验证在样本中发现的频繁模式.再次扫描数据库,找出遗漏的频繁模式