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

1、内容提纲内容提纲关联规则挖掘简介关联规则基本模型关联规则价值衡量与发展参考文献第1页/共43页I.关联规则简介关联规则简介 关联规则反映一个事物与其他事物之间的相互依存性和关联性。如果两个或者多个事物之间存在一定的关联关系，那么，其中一个事物就能够通过其他事物预测到。 典型的关联规则发现问题是对超市中的货篮数据（Market Basket）进行分析。通过发现顾客放入货篮中的不同商品之间的关系来分析顾客的购买习惯。 第2页/共43页什么是关联规则挖掘什么是关联规则挖掘关联规则挖掘 首先被Agrawal, Imielinski and Swami在1993年的SIGMOD会议上提出 在事务、关系数

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

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

4、，则称其为k项集。项集A在事务数据库D中出现的次数占D中总事务的百分比叫做项集的支持度。如果项集的支持度超过用户给定的最小支持度阈值，就称该项集是频繁项集（或大项集）。 第7页/共43页关联规则基本模型（续）关联规则基本模型（续） 关联规则是形如XY的逻辑蕴含式，其中XI，YI，且XY=。如果事务数据库D中有s%的事务包含XY，则称关联规则XY的支持度为s%，实际上，支持度是一个概率值。若项集X的支持度记为support (X)，规则的信任度为support (XY)support (X)。这是一个条件概率P (Y | X)。 也就是： support (XY)=P (X Y) confide

5、nce (XY)=P (Y | X) 第8页/共43页规则度量：支持度与可信度规则度量：支持度与可信度 查找所有的规则 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%)买尿布的客户二者都买的客户买啤酒的客户第9页/共43页关联规则基本模型（续）关联规则基本模型（续） 关联规则就是支持度

6、和信任度分别满足用户给定阈值的规则。 发现关联规则需要经历如下两个步骤： 找出所有频繁项集。 由频繁项集生成满足最小信任度阈值的规则。 第10页/共43页Let min_support = 50%, min_conf = 50%:A C (50%, 66.7%)C A (50%, 100%)Customerbuys diaperCustomerbuys bothCustomerbuys beerTransaction-idItems bought10A, B, C20A, C30A, D40B, E, F第11页/共43页For rule A C:support = support(AC) =

7、 50%confidence = support(AC)/support(A) = 66.6%Min. support 50%Min. confidence 50%Transaction-idItems bought10A, B, C20A, C30A, D40B, E, FFrequent patternSupportA75%B50%C50%A, C50%第12页/共43页II.Apriori算法的步骤算法的步骤 Apriori算法命名源于算法使用了频繁项集性质的先验（Prior）知识。 Apriori算法将发现关联规则的过程分为两个步骤： 通过迭代，检索出事务数据库中的所有频繁项集，即支持

8、度不低于用户设定的阈值的项集； 利用频繁项集构造出满足用户最小信任度的规则。 挖掘或识别出所有频繁项集是该算法的核心，占整个计算量的大部分。 第13页/共43页频繁项集频繁项集 为了避免计算所有项集的支持度（实际上频繁项集只占很少一部分），Apriori算法引入潜在频繁项集的概念。若潜在频繁k项集的集合记为Ck ，频繁k项集的集合记为Lk ，m个项目构成的k项集的集合为 ，则三者之间满足关系Lk Ck 。构成潜在频繁项集所遵循的原则是“频繁项集的子集必为频繁项集”。 kmCkmC第14页/共43页关联规则的性质：关联规则的性质： 性质1：频繁项集的子集必为频繁项集。 性质2：非频繁项集的超集一

9、定是非频繁的。 Apriori算法运用性质1，通过已知的频繁项集构成长度更大的项集，并将其称为潜在频繁项集。潜在频繁k项集的集合Ck 是指由有可能成为频繁k项集的项集组成的集合。以后只需计算潜在频繁项集的支持度，而不必计算所有不同项集的支持度，因此在一定程度上减少了计算量。 第15页/共43页Apriori算法算法 (1) L1=频繁1项集; (2) for(k=2;Lk-1;k+) do begin (3) Ck=apriori_gen(Lk-1); /新的潜在频繁项集 (4) for all transactions tD do begin (5) Ct=subset(Ck,t); /t中

10、包含的潜在频繁项集 (6) for all candidates cCt do (7) c.count+; (8) end; (9) Lk=cCk|c.countminsup (10) end; (11) Answer= kkL第16页/共43页实例实例Database TDB1st scanC1L1L2C2C22nd scanC3L33rd scanTidItems10A, C, D20B, C, E30A, B, C, E40B, EItemsetsupA2B3C3D1E3ItemsetsupA2B3C3E3ItemsetA, BA, CA, EB, CB, EC, EItemsetsup

11、A, B1A, C2A, E1B, C2B, E3C, E2ItemsetsupA, C2B, C2B, E3C, E2ItemsetB, C, EItemsetsupB, C, E2第17页/共43页Visualization of Association Rules: Pane Graph第18页/共43页Visualization of Association Rules: Rule Graph第19页/共43页提高提高Apriori算法的方法算法的方法 Hash-based itemset counting（散列项集计数） Transaction reduction（事务压缩） Par

12、titioning（划分） Sampling（采样）第20页/共43页关联规则挖掘算法关联规则挖掘算法 Agrawal等人提出的AIS，Apriori和AprioriTid Cumulate和Stratify，Houstsma等人提出的SETM Park等人提出的DHP Savasere等人的PARTITION Han等人提出的不生成候选集直接生成频繁模式FPGrowth 其中最有效和有影响的算法为Apriori，DHP和PARTITION，FPGrowth。第21页/共43页 用Frequent-Pattern tree (FP-tree) 结构压缩数据库, 高度浓缩，同时对频繁集的挖掘又完

13、备的 避免代价较高的数据库扫描 开发一种高效的基于FP-tree的频繁集挖掘算法 采用分而治之的方法学：分解数据挖掘任务为小任务 避免生成关联规则: 只使用部分数据库!挖掘频繁集 不用生成候选集第22页/共43页f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1头表头表Item frequency head f4c4a3b3m3p3最小支持度最小支持度 = 0.5TIDItems bought (ordered) frequent items100f, a, c, d, g, i, m, pf, c, a, m, p200a, b, c, f, l, m, of, c, a,

14、b, m300 b, f, h, j, of, b400 b, c, k, s, pc, b, p500 a, f, c, e, l, p, m, nf, c, a, m, p步骤:1.扫描数据库一次，得到频繁1-项集2.把项按支持度递减排序3.再一次扫描数据库，建立FP-tree建立 FP-tree树第23页/共43页 完备: 不会打破交易中的任何模式 包含了频繁模式挖掘所需的全部信息 紧密 去除不相关信息不包含非频繁项 支持度降序排列: 支持度高的项在FP-tree中共享的机会也高 决不会比原数据库大（如果不计算树节点的额外开销)FP-tree 结构的好处第24页/共43页 基本思想 (分

15、而治之) 用FP-tree递归增长频繁集 方法 对每个项，生成它的 条件模式库, 然后是它的 条件 FP-tree 对每个新生成的条件FP-tree，重复这个步骤 直到结果FP-tree为空, 或只含唯一的一个路径 (此路径的每个子路径对应的项集都是频繁集)用FP-tree挖掘频繁集第25页/共43页1)为FP-tree中的每个节点生成条件模式库2)用条件模式库构造对应的条件FP-tree3)递归构造条件 FP-trees 同时增长其包含的频繁集如果条件FP-tree只包含一个路径，则直接生成所包含的频繁集。如果条件FP-tree包含多个路径，则采用混合的方法挖掘 FP-tree的主要步骤第2

16、6页/共43页 从FP-tree的头表开始 按照每个频繁项的连接遍历 FP-tree 列出能够到达此项的所有前缀路径，得到条件模式库条件模式库条件模式库itemcond. pattern basecf:3afc:3bfca:1, f:1, c:1mfca:2, fcab:1pfcam:2, cb:1f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1头表头表Item frequency head f4c4a3b3m3p3步骤1: 从 FP-tree 到条件模式库第27页/共43页 Node-link property For any frequent item ai, all t

17、he possible patterns containing only frequent items and ai can be obtained by following ais node-links, starting from ais head in the fp-tree header. Prefix path property To calculate the frequent patterns with suffix ai, only the prefix subpathes of nodes labeled ai in the FP-tree need to be accumu

18、lated, and the frequency count of every node in the prefix path should carry the same count as that in the corresponding node ai in the path.FP-tree支持条件模式库构造的属性第28页/共43页 对每个模式库 计算库中每个项的支持度 用模式库中的频繁项建立FP-treem-条件模式库条件模式库:fca:2, fcab:1f:3c:3a:3m-conditional FP-treeAll frequent patterns concerning mm,

19、fm, cm, am, fcm, fam, cam, fcamf:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1头表头表Item frequency head f4c4a3b3m3p3步骤2: 建立条件 FP-tree第29页/共43页EmptyEmptyf(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条件模式库项通过建立条件模式库得到频繁集第30页/共43页f:3c:3a

20、: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第31页/共43页III.关联规则价值衡量与发展关联规则价值衡量与发展关联规则价值衡量关联规则最新进展第32页/共43页I.I.规则价值衡量规则价值衡量 对关联规则的评价与价值衡量涉及两个层面： 系统客观的层面 用户主观的层面第33页/共43页系统客观层面系统客观层面 使用“支持度和信任度”框架可能会产生一些不正确的规则。只凭支持度和信任

21、度阈值未必总能找出符合实际的规则。 第34页/共43页用户主观层面用户主观层面 只有用户才能决定规则的有效性、可行性。所以，应该将用户的需求和系统更加紧密地结合起来。 可以采用基于约束（Consraint-based）的数据挖掘方法。具体约束的内容有：数据约束、 限定数据挖掘的维和层次、规则约束。 如果把某些约束条件与算法紧密结合，既能提高数据挖掘效率，又能明确数据挖掘的目标。 第35页/共43页II.II.关联规则新进展关联规则新进展 在基于一维布尔型关联规则的算法研究中先后出现了AIS、SETM等数据挖掘算法。 R.Agrawal等人提出的Apriori 是经典算法。随后的关联规则发现算法

22、大多数建立在Apriori算法基础上，或进行改造，或衍生变种。比如AprioriTid和AprioriHybrid算法。 Lin等人提出解决规则挖掘算法中的数据倾斜问题，从而使算法具有较好的均衡性。Park等人提出把哈希表结构用于关联规则挖掘。第36页/共43页关联规则新进展（续）关联规则新进展（续） 数据挖掘工作是在海量数据库上进行的，数据库的规模对规则的挖掘时间有很大影响。 Agrawal首先提出事务缩减技术，Han和Park等人也分别在减小数据规模上做了一些工作。 抽样的方法是由Toivonen提出的。 Brin等人采用动态项集计数方法求解频繁项集。 Aggarwal提出用图论和格的理论

23、求解频繁项集的方法。Prutax算法就是用格遍历的办法求解频繁项集。 第37页/共43页关联规则新进展（续）关联规则新进展（续） 关联规则模型有很多扩展，如顺序模型挖掘，在顺序时间段上进行挖掘等。 还有挖掘空间关联规则，挖掘周期性关联规则，挖掘负关联规则，挖掘交易内部关联规则等。 Guralnik提出顺序时间段问题的形式描述语言，以便描述用户感兴趣的时间段，并且构建了有效的数据结构SP树（顺序模式树）和自底向上的数据挖掘算法。 最大模式挖掘是Bayardo等人提出来的。 第38页/共43页关联规则新进展（续）关联规则新进展（续） 随后人们开始探讨频率接近项集。Pei给出了一种有效的数据挖掘算法

24、。 B.zden等人的周期性关联规则是针对具有时间属性的事务数据库，发现在规律性的时间间隔中满足最小支持度和信任度的规则。 贝尔实验室的S.Ramaswamy等人进一步发展了周期性关联规则，提出挖掘符合日历的关联规则（Calendric Association Rules）算法，用以进行市场货篮分析。 Fang等人给出冰山查询数据挖掘算法。 第39页/共43页关联规则新进展（续）关联规则新进展（续） T.Hannu等人把负边界引入规则发现算法中，每次挖掘不仅保存频繁项集，而且同时保存负边界，达到下次挖掘时减少扫描次数的目的。 Srikant等人通过研究关联规则的上下文，提出规则兴趣度尺度用以剔除冗余规则。 Zakia还用项集聚类技术求解最大的近似潜在频繁项集，然后