频繁模式挖掘与关联规则挖掘教程.ppt

数 据 挖 掘 数 据 挖 掘第六章 挖掘大型数据库中的关联规则 孙玉芬 yufen@whut.edu.cn 武汉理工大学 计算机科学与技术学院 计算机科学系 挖掘大型数据库中的关联规则 6.1 关联规则挖掘 6.2 由事务数据库挖掘单维布尔关联规则 6.3 由事务数据库挖掘多层关联规则 6.4 由关系数据库和数据仓库挖掘多维关联规则 6.5 由关联挖掘到相关分析 6.6 基于约束的关联挖掘 6.7 小结 6.1 关联规则挖掘 由Agrawal，Imielinski，与Swami [AIS93]首次提出频繁项集（frequent itemsets）与关联规则挖掘（association rule mining） 动机：找出数据中存在的规则 A ? B 哪些产品总是被同时购买？—啤酒与尿布？！ 顾客购买PC后，还会购买哪些商品？ 哪种DNA会对某种新药敏感？ 先挖掘频繁模式，然后挖掘关联规则 频繁模式：在一个数据集中频繁出现的模式 （数据项集，子序列，子结构，等） 基本概念：频繁模式与关联规则 项集 X = {x1, …, xk} 找出所有置信度与支持度超过阈值的规则 X ? Y 支持度（support），s，包含X ? Y的事务出现的概率 置信度（confidence），c，事务包含X时，也包含Y的条件概率 为什么频繁模式挖掘是重要的？ 能发现数据集中内在的特性 是许多重要的数据挖掘任务的基础 关联分析，相关分析，与因果分析 序列模式，结构模式（如：子图） 时空数据、多媒体数据、时序数据、流数据中的模式分析 分类：关联分类 聚类：基于频繁模式的聚类 数据仓库：冰山数据立方 语义数据压缩 广泛的应用 购物篮数据分析，Web点击流分析，打折销售分析，DNA序列分析 关联规则的分类 布尔关联规则与量化关联规则 计算机 ? 财务管理软件 年龄（X，”30…39”） ? 收入（X，”42k…48k”） ? 购买（X，”高清晰电视”） 单维关联规则与多维关联规则 单层关联规则与多层关联规则 年龄（X， ”30…39” ） ? 购买（X，”笔记本”） 年龄（X， ”30…39” ） ? 购买（X，”计算机”） 闭模式与最大模式 闭模式与最大模式 一个长模式包含大量子模式。例如：{a1, …, a100} 包含 C1001 + C1002 + … + C110000 = 2100 – 1 = 1.27*1030子模式！ 解决方法：挖掘闭模式（ closed patterns ）与最大模式（ max-patterns） 一个项集X是闭模式，如果X是频繁的，且不存在超模式 Y ? X具有与X同样的支持度（Pasquier，ICDT’99） 一个项集X是一个最大模式，如果X是频繁的，并且不存在频繁超模式 Y ? X （Bayardo，SIGMOD’98） 闭模式是频繁模式集的无损压缩 压缩了模式与规则的数目 闭模式与最大模式 例子：DB = {a1, …, a100, a1, …, a50} 最小支持度 = 1 有哪些闭模式? a1, …, a100: 1 a1, …, a50: 2 有哪些最大模式？ a1, …, a100: 1 所有模式 !! 挖掘大型数据库中的关联规则 6.1 关联规则挖掘 6.2 由事务数据库挖掘单维布尔关联规则 6.3 由事务数据库挖掘多层关联规则 6.4 由关系数据库和数据仓库挖掘多维关联规则 6.5 由关联挖掘到相关分析 6.6 基于约束的关联挖掘 6.7 小结 6.2 由事务数据库挖掘单维布尔关联规则 挖掘最简单形式的关联规则： 单维 单层 布尔 两个主要方法 Apriori（Agrawal Srikant@VLDB’94） 频繁模式增长方法（FPgrowth—Han, Pei Yin @SIGMOD’00） 6.2.1 Apriori：一个基于候选集的方法 Apriori性质： 一个频繁项集的所有非空子集都必定是频繁的 如果 {啤酒，尿布，坚果} 是频繁的，则 {啤酒，尿布}必定是频繁的 每个包含 {啤酒，尿布，坚果} 的事务，必定包含 {啤酒，尿布} 反单调 Apriori 修剪原则: 如果某个项集是不频繁的，则它的超集不需要被考虑 Apriori 方法 逐层有哪些信誉好的足球投注网站：由 K－项集到 k+1－候选项集 方法： 扫描数据集一次，得到所有长度为1的频繁项集 基于长度为 K 的频繁项集，生成长度为 k+1 的候选项集 扫描数据集，检测候选项集是否频繁 当没有频繁项集或候选项集生成时，中止算法。 例子：Apriori 算法 Apriori 算法 伪码： Ck ：长度为 k 的候选项集 Lk ： 长度为 k 的频繁项集 L1 = {频繁项}; for (k = 1; Lk !=?;