上海交通大学高级数据库课件陆朝俊asso_ch讲述.ppt

关联 什么是频繁模式分析? 频繁模式: 在数据集中频繁出现的模式(项集, 子序列, 子结构等) 动机: 找出数据中的内在规律性 哪些产品经常被一起购买?— Beer and diapers?! 购买了PC之后下一个会买什么? 何种DNA对这个新药敏感? 能否自动分类web文档? 应用 购物篮分析, cross-marketing, 商品目录设计, 促销活动分析, Web日志(点击流)分析, DNA序列分析 例:候选项集生成 由:L3 = {abc, abd, acd, ace, bcd } Step-1:自连接L3*L3 abcd from abc 和abd acde from acd 和ace Step-2: 剪枝 由于ade 不在L3 中, acde 被删除 得:C4 = {abcd } * * 基本概念: 频繁模式和关联规则 项集X = {x1, …, xk} 找出满足最小支持度和置信度的所有规则X ? Y 支持度 s, 一笔交易包含X?Y的概率 置信度 c, 一笔包含X的交易也包含Y的条件概率 令 supmin = 50%, confmin = 50% 频繁模式: {A:3, B:3, D:4, E:3, AD:3} 关联规则: A ? D (60%, 100%) D ? A (60%, 75%) 买尿布的客户 两者都买的客户 买啤酒的客户 Transaction-id Items bought 10 A, B, D 20 A, C, D 30 A, D, E 40 B, E, F 50 B, C, D, E, F * 频繁模式挖掘: 路线图(1) 基于挖掘的模式的完备性 频繁模式的完备集合 闭频繁项集 极大频繁项集 约束频繁项集 近似频繁项集 邻近匹配频繁项集 top-k 频繁项集 基于规则中涉及的抽象层次 单层关联规则 多层关联规则 基于规则中涉及的数据维数 单维关联规则 多维关联规则 * 频繁模式挖掘: 路线图(2) 基于规则处理的值的类型 布尔型关联规则 定量关联规则 基于挖掘的规则种类 关联规则 相关性规则 强梯度联系 基于挖掘的模式的种类 频繁项集挖掘 序列模式挖掘 结构模式挖掘 * 挖掘频繁模式的可扩展方法 频繁模式的向下封闭性质 频繁项集的任何子集必是频繁的 若{beer, diaper, nuts}是频繁的, 则{beer, diaper}也是 因为: 任何包含{beer, diaper, nuts}的交易也包含{beer, diaper} 可扩展挖掘方法: 三个主要方法 Apriori (Agrawal Srikant@VLDB’94) 频繁模式增长(FPgrowth—Han, Pei Yin @SIGMOD’00) 垂直数据格式方法(Charm—Zaki Hsiao @SDM’02) * Apriori: 候选生成与检验方法 Apriori剪枝原则: 如果发现任何项集是非频繁的, 则其超集就不必生成/检验! 方法: 初始步, 扫描一次DB, 得到频繁1-项集 从长度为k的频繁项集生成长度为(k+1)的候选项集 在DB中检验候选项集 不能生成频繁或候选项集时终止 * Apriori算法—一个例子 Database TDB 1st scan C1 L1 L2 C2 C2 2nd scan C3 L3 3rd scan Tid Items 10 A, C, D 20 B, C, E 30 A, B, C, E 40 B, E Itemset sup {A} 2 {B} 3 {C} 3 {D} 1 {E} 3 Itemset sup {A} 2 {B} 3 {C} 3 {E} 3 Itemset {A, B} {A, C} {A, E} {B, C} {B, E} {C, E} Itemset sup {A, B} 1 {A, C} 2 {A, E} 1 {B, C} 2 {B, E} 3 {C, E} 2 Itemset sup {A, C} 2 {B, C} 2 {B, E} 3 {C, E} 2 Itemset {B, C, E} Itemset sup {B, C, E} 2 Supmin = 2 * Apriori算法 伪代码: Ck : 大小为k 的候选项集 Lk :大小为k 的频繁项集 L1 = {频繁项(即频繁1-项集)}; for (k = 2; Lk-1 !=?; k++) { Ck = 从Lk-1 生成的候选项集; for each 交易t do 将被t 包含的所有Ck 中候选项集的计数加1 Lk = Ck 中至少具有min_support的候选项集 } return ?k Lk * Apriori算法细节