数据挖掘2015最新精品课程完整课件(第6讲)---挖掘各种关联规则

挖掘各种关联规则内容多层关联规则多维关联规则约束性关联规则总结关联规则改进2020/2/24AA12关联规则史忠植3挖掘多种规则或规律多层(Multi-level),量化(quantitative)关联规则,相关(correlation)和因果(causality),比率(ratio)规则,序列(sequential)模式,浮现(emerging)模式,temporalassociations,局部周期(partialperiodicity)分类(classification),聚类(clustering),冰山立方体(icebergcubes),等等.多层关联规则项通常形成分层结构低层的项通常有低支持度.基于维数和层级可对事务数据库编码利用共享的多级挖掘一致支持度computer[support=10%]Laptopcomputer[support=6%]Desktopcomputer[support=4%]Level1min_sup=5%Level2min_sup=5%Level1min_sup=5%Level2min_sup=3%递减支持度渐进的多层挖掘方法自顶向下,渐进加深的方法，在每层挖掘所有的频繁项集:首先挖掘高层频繁项:milk(15%),bread(10%)然后挖掘低层的“较弱”频繁项集:2%milk(5%),wheatbread(4%)跨层时不同的min_support门限，算法不同:一致支持度若项的祖先非频繁，则丢掉该项，类似Apriori的优化策略递减支持度只检查那些祖先为频繁的或不可忽略的项多维关联规则多维关联规则概念单维规则:buys(X,“milk”)buys(X,“bread”)多维关联规则:2维or谓词维间关联规则(无重复谓词)age(X,”19-25”)occupation(X,“student”)buys(X,“coke”)混合维关联规则(重复谓词)age(X,”19-25”)buys(X,“popcorn”)buys(X,“coke”)分类属性:有限个可能值,值间无序—数据立方体方法量化属性:数值,值间隐含顺序—离散化,聚类和梯度法量化关联规则挖掘的技巧根据量化值的处理方式进行分类，如{age,salary}基于预定义的概念分层进行静态离散化(数据立方体方法)基于数据分布的动态离散化(量化规则,e.g.,Agrawal&Srikant@SIGMOD96)聚类:基于距离的关联(e.g.,Yang&Miller@SIGMOD97)一维聚类然后关联偏差:(suchasAumannandLindell@KDD99)Sex=female=Wage:mean=$7/hr(overallmean=$9)量化属性的静态离散化概念分层挖掘前离散化范围代替数值在关系数据库中,查找所有的k-阶谓词的频繁集需要k次或k+1次表扫描数据立方体适合于挖掘n-维立方体对应的定点对应谓词从数据立方体挖掘速度更快(income)(age)()(buys)(age,income)(age,buys)(income,buys)(age,income,buys)挖掘量化关联规则动态离散化使挖掘规则的置信度和紧致度最大2-D量化关联规则:Aquan1Aquan2Acat以2-D网格对相邻关联规则聚类成更泛化的规则Exampleage(X,“34-35”)income(X,“30-50K”)buys(X,“highresolutionTV”)约束性关联规则基于约束的挖掘数据挖掘是交互的过程自动从数据库中挖掘出所有的模式不现实用户的引导下完成，需要用好约束才有可能基于约束的挖掘用户提供约束，提示待发现的模式或规则形式可用的约束知识类型约束：分类和关联规则等etc.数据约束:SQL-like查询找出2008年10月1日卖出的球拍和球鞋维/层约束:和区域、价格、品牌、消费者类别相关.规则约束小额销售(price$10)触发大额销售(sum$200).兴趣度约束:强规则(min_support3%,min_confidence60%).规则约束两种类型规则约束规则的形式约束:元规则引导约束挖掘P(x,y)^Q(x,w)takes(x,“databasesystems”).实例:age(X,”30…39”)^income(X,”41k…60k”)=buys(X,”office”)规则内容约束:基于规则约束引导的挖掘规则中变量的期望的集合/子集联系、变量的初始化和聚集函数sum(LHS)100^min(LHS)20^count(LHS)3^sum(RHS)10001-变量vs.2-变量约束1-变量:只在规则的单边形成约束.2-变量:在两边都形成约束sum(LHS)min(RHS)^max(RHS)5*sum(LHS)规则内容约束的分类基于约束推进能力(constraintpushingcapability)反单调:若约束c不满足,可中止进一步的挖掘，所有超级均不满足约束c单调:若c满足,不必再检查c，所有的超集均满足c数据反单调:若事务t不满足约束c,t不必进一步挖掘简洁的(Succinct):c必须满足,可从约束c先考察可转换的:c既非单调也非反单调,按项集中特定项排序，约束可以成为单调或反单调的具有多种约束的挖掘实例在2004年，chicago的顾客购买什么样的便宜商品（价格和低于100美元）会促进同类贵商品的销售(最低价为500美元)?Sales(customer_name,item_name,TID)Lives_in(customer_name,region,city)item(item_name,group,price)transactions(TID,day,month,year)事实表总结频繁模式挖掘－关联规则的重要任务频繁模式挖掘方法Apriori(生成候选&测试)基于投影(FPGrowth)垂直格式方法挖掘各种类型的关联规则：多维、多层关联规则挖掘基于约束的挖掘（人为指定）关联规则的相关性:兴趣度的度量2020/2/24AA12关联规则史忠植17关联规则改进Lin等人提出解决规则挖掘算法中的数据倾斜问题，从而使算法具有较好的均衡性。Park等人提出把哈希表结构用于关联规则挖掘。Agrawal首先提出事务缩减技术，Han和Park等人也分别在减小数据规模上做了一些工作。抽样的方法是由Toivonen提出的。Brin等人采用动态项集计数方法求解频繁项集。Aggarwal提出用图论和格的理论求解频繁项集的方法。Prutax算法就是用格遍历的办法求解频繁项集。2020/2/24AA12关联规则史忠植18关联规则改进关联规则模型有很多扩展，如顺序模型挖掘，在顺序时间段上进行挖掘等。还有挖掘空间关联规则，挖掘周期性关联规则，挖掘负关联规则，挖掘交易内部关联规则等。Guralnik提出顺序时间段问题的形式描述语言，以便描述用户感兴趣的时间段，并且构建了有效的数据结构SP树（顺序模式树）和自底向上的数据挖掘算法。最大模式挖掘是Bayardo等人提出来的。2020/2/24AA12关联规则史忠植19关联规则改进随后人们开始探讨频率接近项集。Pei给出了一种有效的数据挖掘算法。B.Özden等人的周期性关联规则是针对具有时间属性的事务数据库，发现在规律性的时间间隔中满足最小支持度和信任度的规则。贝尔实验室的S.Ramaswamy等人进一步发展了周期性关联规则，提出挖掘符合日历的关联规则（CalendricAssociationRules）算法，用以进行市场货篮分析。20关联规则改进T.Hannu等人把负边界引入规则发现算法中，每次挖掘不仅保存频繁项集，而且同时保存负边界，达到下次挖掘时减少扫描次数的目的。Srikant等人通过研究关联规则的上下文，提出规则兴趣度尺度用以剔除冗余规则。Zakia还用项集聚类技术求解最大的近似潜在频繁项集，然后用格迁移思想生成每个聚类中的频繁项集。CAR，也叫分类关联规则，是Lin等人提出的一种新的分类方法，是分类技术与关联规则思想相结合的产物，并给出解决方案和算法。2020/2/2421关联规则改进Cheung等人提出关联规则的增量算法。Thomas等人把负边界的概念引入其中，进一步发展了增量算法。如，基于Apriori框架的并行和分布式数据挖掘算法。Oates等人将MSDD算法改造为分布式算法。还有其他的并行算法，如利用垂直数据库探求项集聚类等。