《数据挖掘应用- 浙江大学计算机科学与技术学院》由会员分享，可在线阅读，更多相关《数据挖掘应用- 浙江大学计算机科学与技术学院（179页珍藏版）》请在金锄头文库上搜索。
1、第12讲 数据挖掘应用 Chapter 12 Applications of Data Mining,徐从富(Congfu Xu), PhD, Asso. Professor 浙江大学人工智能研究所 2005年5月17日第一稿 2006年10月30日第二次修改,浙江大学研究生人工智能引论课件,目录,关联规则挖掘 聚类分析 分类与预测 Web挖掘 流数据挖掘 隐私保护数据挖掘,关联规则挖掘,关联规则挖掘简介 关联规则基本模型 关联规则价值衡量与发展,关联规则简介,关联规则反映一个事物与其他事物之间的相互依存性和关联性。如果两个或者多个事物之间存在一定的关联关系，那么，其中一个事物就能够通过其他事
2、物预测到。 典型的关联规则发现问题是对超市中的货篮数据（Market Basket）进行分析。通过发现顾客放入货篮中的不同商品之间的关系来分析顾客的购买习惯。,什么是关联规则挖掘,关联规则挖掘 首先被Agrawal, Imielinski and Swami在1993年的SIGMOD会议上提出 在事务、关系数据库中的项集和对象中发现频繁模式、关联规则、相关性或者因果结构 频繁模式: 数据库中频繁出现的项集 目的: 发现数据中的规律 超市数据中的什么产品会一起购买？ 啤酒和尿布 在买了一台PC之后下一步会购买? 哪种DNA对这种药物敏感? 我们如何自动对Web文档进行分类?,频繁模式挖掘的重要性
3、,许多重要数据挖掘任务的基础 关联、相关性、因果性 序列模式、空间模式、时间模式、多维 关联分类、聚类分析 更加广泛的用处 购物篮分析、交叉销售、直销 点击流分析、DNA序列分析等等,关联规则基本模型,关联规则基本模型 Apriori算法,关联规则基本模型,IBM公司Almaden研究中心的R.Agrawal首先提出关联规则模型，并给出求解算法AIS。随后又出现了SETM和Apriori等算法。其中，Apriori是关联规则模型中的经典算法。 给定一组事务 产生所有的关联规则 满足最小支持度和最小可信度,关联规则基本模型（续）,设I=i1, i2, im为所有项目的集合，D为事务数据库，事务T
4、是一个项目子集（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)suppor
5、t (X)。这是一个条件概率P (Y | X)。也就是： support (XY)=P (X Y) confidence (XY)=P (Y | X),规则度量：支持度与可信度,查找所有的规则 X & Y Z 具有最小支持度和可信度 支持度, s, 一次交易中包含X 、 Y 、 Z的可能性 可信度, c, 包含X 、 Y的交易中也包含Z的条件概率,设最小支持度为50%, 最小可信度为 50%, 则可得到 A C (50%, 66.6%) C A (50%, 100%),买尿布的客户,二者都买的客户,买啤酒的客户,关联规则基本模型（续）,关联规则就是支持度和信任度分别满足用户给定阈值的规则。 发
6、现关联规则需要经历如下两个步骤： 找出所有频繁项集。 由频繁项集生成满足最小信任度阈值的规则。,Let min_support = 50%, min_conf = 50%: A C (50%, 66.7%) C A (50%, 100%),For rule A C: support = support(AC) = 50% confidence = support(AC)/support(A) = 66.6%,Min. support 50% Min. confidence 50%,Apriori算法的步骤,Apriori算法命名源于算法使用了频繁项集性质的先验（Prior）知识。 Aprior
7、i算法将发现关联规则的过程分为两个步骤： 通过迭代，检索出事务数据库中的所有频繁项集，即支持度不低于用户设定的阈值的项集； 利用频繁项集构造出满足用户最小信任度的规则。 挖掘或识别出所有频繁项集是该算法的核心，占整个计算量的大部分。,频繁项集,为了避免计算所有项集的支持度（实际上频繁项集只占很少一部分），Apriori算法引入潜在频繁项集的概念。若潜在频繁k项集的集合记为Ck ，频繁k项集的集合记为Lk ，m个项目构成的k项集的集合为 ，则三者之间满足关系Lk Ck 。构成潜在频繁项集所遵循的原则是“频繁项集的子集必为频繁项集”。,关联规则的性质：,性质6.1 频繁项集的子集必为频繁项集。 性
8、质6.2 非频繁项集的超集一定是非频繁的。 Apriori算法运用性质6.1，通过已知的频繁项集构成长度更大的项集，并将其称为潜在频繁项集。潜在频繁k项集的集合Ck 是指由有可能成为频繁k项集的项集组成的集合。以后只需计算潜在频繁项集的支持度，而不必计算所有不同项集的支持度，因此在一定程度上减少了计算量。,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)
9、; /t中包含的潜在频繁项集 (6) for all candidates cCt do (7) c.count+; (8) end; (9) Lk=cCk|c.countminsup (10) end; (11) Answer=,实例,Database TDB,1st scan,C1,L1,L2,C2,C2,2nd scan,C3,L3,3rd scan,Visualization of Association Rules: Pane Graph,Visualization of Association Rules: Rule Graph,提高Apriori算法的方法,Hash-based
10、itemset counting（散列项集计数） Transaction reduction（事务压缩） Partitioning（划分） Sampling（采样）,关联规则挖掘算法,Agrawal等人提出的AIS，Apriori和AprioriTid Cumulate和Stratify，Houstsma等人提出的SETM Park等人提出的DHP Savasere等人的PARTITION Han等人提出的不生成候选集直接生成频繁模式FPGrowth 其中最有效和有影响的算法为Apriori，DHP和PARTITION，FPGrowth。,用Frequent-Pattern tree (FP-
11、tree) 结构压缩数据库, 高度浓缩，同时对频繁集的挖掘又完备的 避免代价较高的数据库扫描 开发一种高效的基于FP-tree的频繁集挖掘算法 采用分而治之的方法学：分解数据挖掘任务为小任务 避免生成关联规则: 只使用部分数据库!,挖掘频繁集 不用生成候选集,最小支持度 = 0.5,TID Items bought (ordered) frequent items 100 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
12、, 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中共享的机会也高 决不会比原数据库大（如果不计算树节点的额外开销) 例子: 对于 Connect-4 数据库,压缩率超过 100,FP-tree 结构的好处,基本思想 (分而治之) 用FP-tree地归增长频
13、繁集 方法 对每个项，生成它的 条件模式库, 然后是它的 条件 FP-tree 对每个新生成的条件FP-tree，重复这个步骤 直到结果FP-tree为空, 或只含维一的一个路径 (此路径的每个子路径对应的项集都是频繁集),用 FP-tree挖掘频繁集,为FP-tree中的每个节点生成条件模式库 用条件模式库构造对应的条件FP-tree 递归构造条件 FP-trees 同时增长其包含的频繁集 如果条件FP-tree只包含一个路径，则直接生成所包含的频繁集。,挖掘 FP-tree的主要步骤,从FP-tree的头表开始 按照每个频繁项的连接遍历 FP-tree 列出能够到达此项的所有前缀路径，得到
14、条件模式库,条件模式库 item cond. pattern base c f:3 a fc:3 b fca:1, f:1, c:1 m fca:2, fcab:1 p fcam:2, cb:1,步骤1: 从 FP-tree 到条件模式库,节点裢接 任何包含ai, 的可能频繁集，都可以从FP-tree头表中的ai沿着ai 的节点链接得到 前缀路径 要计算路径P 中包含节点ai 的频繁集，只要考察到达ai 的路径前缀即可，且其支持度等于节点ai 的支持度,FP-tree支持条件模式库构造的属性,对每个模式库 计算库中每个项的支持度 用模式库中的频繁项建立FP-tree,m-条件模式库: fca:
15、2, fcab:1,All frequent patterns concerning m m, fm, cm, am, fcm, fam, cam, fcam,f:4,c:1,b:1,p:1,b:1,c:3,a:3,b:1,m:2,p:2,m:1,头表 Item frequency head f 4 c 4 a 3 b 3 m 3 p 3,步骤2: 建立条件 FP-tree,通过建立条件模式库得到频繁集,“am”的条件模式库: (fc:3),“cm”的条件模式: (f:3),f:3,cm-条件 FP-tree,“cam”条件模式库: (f:3),f:3,cam-条件 FP-tree,第3步:
16、递归挖掘条件FP-tree,关联规则价值衡量与发展,关联规则价值衡量 关联规则最新进展,规则价值衡量,对关联规则的评价与价值衡量涉及两个层面： 系统客观的层面 用户主观的层面,系统客观层面,使用“支持度和信任度”框架可能会产生一些不正确的规则。只凭支持度和信任度阈值未必总能找出符合实际的规则。,用户主观层面,只有用户才能决定规则的有效性、可行性。所以，应该将用户的需求和系统更加紧密地结合起来。 可以采用基于约束（Consraint-based）的数据挖掘方法。具体约束的内容有：数据约束、 限定数据挖掘的维和层次、规则约束。 如果把某些约束条件与算法紧密结合，既能提高数据挖掘效率，又能明确数据挖掘的目标。,关联规则新进展,在基于一维布尔型关联规则的算法研究中先后出现了AIS、SETM等数据挖掘算法。 R.Agrawal等人提出的Apriori 是经典算法。随后的关联规则发现算法大多数建立在Apriori算法基础上，或进行改造，或衍生变种。比如AprioriTid和AprioriHybrid算法。 Lin等人提出解决规则挖掘算法中的数据倾斜问题，从而使算法具有较好的均衡性。Park等人提出把哈希表结构用于关联规则挖掘。,
