[精选]数据挖掘导论之频繁模式及关联规则挖掘技术(ppt 44页)531018.pptx

《[精选]数据挖掘导论之频繁模式及关联规则挖掘技术(ppt 44页)531018.pptx》由会员分享，可在线阅读，更多相关《[精选]数据挖掘导论之频繁模式及关联规则挖掘技术(ppt 44页)531018.pptx（44页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第3课 频繁模式及关联规则挖掘技术 徐从富，副教授 浙江大学人工智能研究所浙江大学本科生数据挖掘导论课件内容提纲n 关联规则挖掘简介n 关联规则基本模型n 关联规则价值衡量与发展n 参考文献I.关联规则简介n 关联规则反映一个事物与其他事物之间的相互依存性和关联性。如果两个或者多个事物之间存在一定的关联关系，那么，其中一个事物就能够通过其他事物预测到。n 典型的关联规则发现问题是对超市中的货篮数据（Market Basket）进行分析。通过发现顾客放入货篮中的不同商品之间的关系来分析顾客的购买习惯。什么是关联规则挖掘n 关联规则挖掘 首先被Agrawal,Imielinski and Swam

2、i在1993年的SIGMOD会议上提出 在事务、关系数据库中的项集和对象中发现频繁模式、关联规则、相关性或者因果结构 频繁模式:数据库中频繁出现的项集 n 目的:发现数据中的规律 超市数据中的什么产品会一起购买？啤酒和尿布 在买了一台PC之后下一步会购买?哪种DNA对这种药物敏感?我们如何自动对Web文档进行分类?频繁模式挖掘的重要性n 许多重要数据挖掘任务的基础关联、相关性、因果性序列模式、空间模式、时间模式、多维关联分类、聚类分析n 更加广泛的用处购物篮分析、交叉销售、直销点击流分析、DNA序列分析等等II.关联规则基本模型n 关联规则基本模型n Apriori算法n Fp-Tree算法I

3、.关联规则基本模型 n IBM公司Almaden研究中心的R.Agrawal首先提出关联规则模型，并给出求解算法AIS。随后又出现了SETM和Apriori等算法。其中，Apriori是关联规则模型中的经典算法。给定一组事务产生所有的关联规则满足最小支持度和最小可信度关联规则基本模型（续）n 设I=i1,i2,im为所有项目的集合，D为事务数据库，事务T是一个项目子集（T I）。每一个事务具有唯一的事务标识TID。设A是一个由项目构成的集合，称为项集。事务T包含项集A，当且仅当A T。如果项集A中包含k个项目，则称其为k项集。项集A在事务数据库D中出现的次数占D中总事务的百分比叫做项集的支持度

4、。如果项集的支持度超过用户给定的最小支持度阈值，就称该项集是频繁项集（或大项集）。关联规则基本模型（续）n 关联规则是形如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)规则度量：支持度与可信度n 查找所有的规则 X&Y Z 具有最小支持度和可信度支持度,s,一次交易中

5、包含X、Y、Z的可能性可信度,c,包含X、Y的交易中也包含Z的条件概率设最小支持度为50%,最小可信度为 50%,则可得到 A C(50%,66.6%)C A(50%,100%)买尿布的客户二者都买的客户买啤酒的客户关联规则基本模型（续）n 关联规则就是支持度和信任度分别满足用户给定阈值的规则。n 发现关联规则需要经历如下两个步骤：找出所有频繁项集。由频繁项集生成满足最小信任度阈值的规则。Let min_support=50%,min_conf=50%:A C(50%,66.7%)C A(50%,100%)Customerbuys diaperCustomerbuys bothCustomer

6、buys beerTransaction-id Items bought10 A,B,C20 A,C30 A,D40 B,E,FFor rule A C:support=support(A C)=50%confidence=support(A C)/support(A)=66.6%Min.support 50%Min.confidence 50%Transaction-id Items bought10 A,B,C20 A,C30 A,D40 B,E,FFrequent pattern SupportA 75%B 50%C 50%A,C 50%II.Apriori算法的步骤n Apriori算

7、法命名源于算法使用了频繁项集性质的先验（Prior）知识。n Apriori算法将发现关联规则的过程分为两个步骤：通过迭代，检索出事务数据库中的所有频繁项集，即支持度不低于用户设定的阈值的项集；利用频繁项集构造出满足用户最小信任度的规则。n 挖掘或识别出所有频繁项集是该算法的核心，占整个计算量的大部分。频繁项集n 为了避免计算所有项集的支持度（实际上频繁项集只占很少一部分），Apriori算法引入潜在频繁项集的概念。若潜在频繁k项集的集合记为Ck，频繁k项集的集合记为Lk，m个项目构成的k项集的集合为，则三者之间满足关系Lk Ck。构成潜在频繁项集所遵循的原则是“频繁项集的子集必为频繁项集”。

8、关联规则的性质：n 性质1：频繁项集的子集必为频繁项集。n 性质2：非频繁项集的超集一定是非频繁的。n Apriori算法运用性质1，通过已知的频繁项集构成长度更大的项集，并将其称为潜在频繁项集。潜在频繁k项集的集合Ck 是指由有可能成为频繁k项集的项集组成的集合。以后只需计算潜在频繁项集的支持度，而不必计算所有不同项集的支持度，因此在一定程度上减少了计算量。Apriori算法n(1)L1=频繁1项集;n(2)for(k=2;Lk-1;k+)do begin n(3)Ck=apriori_gen(Lk-1);/新的潜在频繁项集 n(4)for all transactions t D do b

9、egin n(5)Ct=subset(Ck,t);/t中包含的潜在频繁项集 n(6)for all candidates c Ct do n(7)c.count+;n(8)end;n(9)Lk=c Ck|c.count minsup n(10)end;n(11)Answer=实例Database TDB1st scanC1L1L2C2C22nd scanC3L33rd scanTid Items10 A,C,D20 B,C,E30 A,B,C,E40 B,EItemset supA 2B 3C 3D 1E 3Itemset supA 2B 3C 3E 3ItemsetA,BA,CA,EB,CB

10、,EC,EItemset supA,B 1A,C 2A,E 1B,C 2B,E 3C,E 2Itemset supA,C 2B,C 2B,E 3C,E 2ItemsetB,C,EItemset supB,C,E 2Visualization of Association Rules:Pane GraphVisualization of Association Rules:Rule Graph提高Apriori算法的方法n Hash-based itemset counting（散列项集计数）n Transaction reduction（事务压缩）n Partitioning（划分）n Sam

11、pling（采样）关联规则挖掘算法n Agrawal等人提出的AIS，Apriori和AprioriTidn Cumulate和Stratify，Houstsma等人提出的SETMn Park等人提出的DHPn Savasere等人的PARTITIONn Han等人提出的不生成候选集直接生成频繁模式FPGrowthn 其中最有效和有影响的算法为Apriori，DHP和PARTITION，FPGrowth。n 用Frequent-Pattern tree(FP-tree)结构压缩数据库,高度浓缩，同时对频繁集的挖掘又完备的避免代价较高的数据库扫描n 开发一种高效的基于FP-tree的频繁集挖掘算法采用分而治之的方法学：分解数据挖掘任务为小任务避免生成关联规则:只使用部分数据库!挖掘频繁集 不用生成候选集