挖掘大型数据库中的关联规则1.ppt

Data Mining: Concepts and Techniques 数据挖掘：概念与技术 Jiawei Han and Micheline Kamber著 Monrgan Kaufmann Publishers Inc. 范明 孟小峰等译 机械工业出版社 第6章挖掘大型数据库中的关联规则 英文幻灯片制作：Jiawei Han 中文幻灯片编译：范明 第6章：挖掘大型数据库中的关联规则 关联规则挖掘 事务数据库中(单维布尔)关联规则挖掘的可伸缩算法 挖掘各种关联/相关规则 基于限制的关联挖掘- 顺序模式挖掘 频繁模式挖掘的应用/扩展 小结 什么是关联规则挖掘? 关联规则挖掘 : 发现事务数据库, 关系数据, 或其它信息库中项或数据对象集合间的频繁模式, 关联, 相关, 或因果关系结构. 频繁模式: 在数据库中频繁出现的模式(项集, 序列, 等) [AIS93] 动机: 发现数据中的规律性 哪些产品更经常一起购买? — 啤酒 和 尿布?! 购买了PC后, 哪些将相继购买? 什么类型的 DNA 对新药敏感? 我们能自动地对Web稳当分类吗? 为什么频繁模式挖掘是数据挖掘的基本任务? 许多基本的数据挖掘任务的基础 关联, 相关, 因果关系 序列模式, 时间或周期关联, 局部周期性, 空间和多媒体关联 关联分类, 聚类分析, 冰山方, fascicles (语义数据压缩) 广泛的应用 购物篮数据分析, 交叉销售, 分类设计, 销售活动分析 Web 日志 (点击流) 分析, DNA 序列分析, 等. 基本概念: 频繁模式和关联规则 Itemset X={x1, …, xk} 找出满足最先支持度和置信读的所规则 X?Y 支持度, s, 事务包含 X?Y 的概率 置信度, c, 事务含 X 也包含 Y 的条件概率. 挖掘关联规则—一个例子 规则 A ? C: 支持度 = support({A}?{C}) = 50% 置信度 = support({A}?{C})/support({A}) = 66.6% 第6章：挖掘大型数据库中的关联规则 关联规则挖掘 事务数据库中(单维布尔)关联规则挖掘的可伸缩算法 挖掘各种关联/相关规则 基于限制的关联挖掘- 顺序模式挖掘 频繁模式挖掘的应用/扩展 小结 Apriori: 一种候选产生-测试方法 频繁项集的任何子集必须是频繁的 如果 {beer, diaper, nuts} 是频繁的, {beer, diaper}也是 每个包含 {beer, diaper, nuts}的事务 也包含 {beer, diaper} Apriori 剪枝原则: 如果一个项集不是频繁的, 将不产生/测试它的超集! 方法: 由长度为k的频繁项集产生长度为 (k+1) 的候选项集, 并且 根据 DB测试这些候选 性能研究表明了它的有效性和可伸缩性 Agrawal Srikant 1994, Mannila, et al. 1994 Apriori 算法 — 一个例子 Apriori 算法 算法伪代码: Ck: 长度为 k的候选项集 Lk : 长度为k的频繁项集 L1 = {频繁项}; for (k = 1; Lk !=?; k++) do begin Ck+1 = 由 Lk产生的候选; for each 数据库中的事务 t do 增加包含在t 中的所有候选Ck+1的计数 Lk+1 = Ck+1 中满足 min_support的候选 end return ?k Lk; Apriori的重要细节 如何产生候选? 步骤 1: Lk的自连接 步骤 2: 剪枝 入何对候选的支持度计数? 候选产生的例子 L3={abc, abd, acd, ace, bcd} 自连接: L3*L3 Abcd：由 abc 和 abd Acde：由 acd 和 ace 剪枝: acde 被删除, 因为 ade 不在 L3 C4={abcd} 如何产生候选? 假定 Lk-1 中的项集已排序 步骤 1: Lk-1自连接 insert into Ck select p.item1, p.item2, …, p.itemk-1, q.itemk-1 from Lk-1 p, Lk-1 q where p.item1=q.item1, …, p.itemk-2=q.itemk-2, p.itemk-1 q.itemk-1 Step 2: 剪枝 forall itemsets c in Ck do forall (k-1)-subsets s of c do if (s is not in Lk-1) then delete c from Ck 如何对候选的支持度计数? 为什么对候选的支持度计数是一个问