数据挖掘: 概念和技术 — Chapter 6 — ©张晓辉 xiaohui@fudan.edu 复旦大学 （国际）数据库研究中心 2001-11-6 数据挖掘：概念和技术

第6章：从大数据库中挖掘关联规则 关联规则挖掘 从交易数据库中挖掘一维的布尔形关联规则 从交易数据库中挖掘多层次关联规则 在交易数据库和数据仓库中挖掘多维关联规则 从关联挖掘到相关性分析 基于约束的关联挖掘 小结 2001-11-6 数据挖掘：概念和技术

什么是关联挖掘? 关联规则挖掘： 在交易数据、关系数据或其他信息载体中，查找存在于项目集合或对象集合之间的频繁模式、关联、相关性、或因果结构。 应用： 购物篮分析、交叉销售、产品目录设计、 loss-leader analysis、聚集、分类等。 举例： 规则形式： “Body ® Head [support, confidence]”. buys(x, “diapers”) ® buys(x, “beers”) [0.5%, 60%] major(x, “CS”) ^ takes(x, “DB”) ® grade(x, “A”) [1%, 75%] 2001-11-6 数据挖掘：概念和技术

关联规则：基本概念 给定: (1)交易数据库 (2)每笔交易是：一个项目列表 (消费者一次购买活动中购买的商品) 查找: 所有描述一个项目集合与其他项目集合相关性的规则 E.g., 98% of people who purchase tires and auto accessories also get automotive services done 应用 *  护理用品 (商店应该怎样提高护理用品的销售？) 家用电器  * (其他商品的库存有什么影响?) 在产品直销中使用附加邮寄 Detecting “ping-pong”ing of patients, faulty “collisions” 2001-11-6 数据挖掘：概念和技术

规则度量：支持度与可信度 查找所有的规则 X & Y  Z 具有最小支持度和可信度 二者都买的客户 买尿布的客户 查找所有的规则 X & Y  Z 具有最小支持度和可信度 支持度, s, 一次交易中包含{X 、 Y 、 Z}的可能性 可信度, c, 包含{X 、 Y}的交易中也包含Z的条件概率 买啤酒的客户 设最小支持度为50%, 最小可信度为 50%, 则可得到 A  C (50%, 66.6%) C  A (50%, 100%) 2001-11-6 数据挖掘：概念和技术

关联规则挖掘：路线图 布尔 vs. 定量 关联 (基于 处理数据的类型) buys(x, “SQLServer”) ^ buys(x, “DMBook”) ® buys(x, “DBMiner”) [0.2%, 60%] age(x, “30..39”) ^ income(x, “42..48K”) ® buys(x, “PC”) [1%, 75%] 单维 vs. 多维 关联 (例子同上) 单层 vs. 多层 分析 那个品种牌子的啤酒与那个牌子的尿布有关系? 各种扩展 相关性、因果分析 关联并不一定意味着相关或因果 最大模式和闭合相集 添加约束 如, 哪些“小东西”的销售促发了“大家伙”的买卖？ 2001-11-6 数据挖掘：概念和技术

第6章：从大数据库中挖掘关联规则 关联规则挖掘 从交易数据库中挖掘一维的布尔形关联规则 从交易数据库中挖掘多层次关联规则 在交易数据库和数据仓库中挖掘多维关联规则 从关联挖掘到相关性分析 基于约束的关联挖掘 小结 2001-11-6 数据挖掘：概念和技术

关联规则挖掘—一个例子 最小值尺度 50% 最小可信度 50% 对于 A  C： support = support({A 、C}) = 50% confidence = support({A 、C})/support({A}) = 66.6% Apriori的基本思想: 频繁项集的任何子集也一定是频繁的 2001-11-6 数据挖掘：概念和技术

关键步骤：挖掘频繁集 频繁集:是指满足最小支持度的项目集合 频繁集的子集也一定是频繁的 从1到k（k-频繁集）递归查找频繁集 如, 如果{AB} 是频繁集，则 {A} {B} 也一定是频繁集 从1到k（k-频繁集）递归查找频繁集 用得到的频繁集生成关联规则 2001-11-6 数据挖掘：概念和技术

Apriori算法 连接: 用 Lk-1自连接得到Ck 修剪: 一个k-项集，如果他的一个k-1项集（他的子集 ）不是频繁的，那他本身也不可能是频繁的。 伪代码: Ck: Candidate itemset of size k Lk : frequent itemset of size k L1 = {frequent items}; for (k = 1; Lk !=; k++) do begin Ck+1 = candidates generated from Lk; for each transaction t in database do increment the count of all candidates in Ck+1 that are contained in t Lk+1 = candidates in Ck+1 with min_support end return k Lk; 2001-11-6 数据挖掘：概念和技术

Apriori算法 — 例子 数据库 D L1 C1 扫描 D C2 C2 L2 扫描 D C3 L3 扫描 D 2001-11-6 数据挖掘：概念和技术

如何生成候选集 假定 Lk-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 第二步: 修剪 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 2001-11-6 数据挖掘：概念和技术

如何计算候选集的支持度 计算支持度为什么会成为一个问题？ 候选集的个数非常巨大 一笔交易可能包含多个候选集 方法: 用 hash-tree 存放候选集 树的叶子节点 of存放项集的列表和支持度 内部节点 是一个hash表 Subset 函数: 找到包含在一笔交易中的所有候选集 2001-11-6 数据挖掘：概念和技术

生成候选集的例子 L3={abc, abd, acd, ace, bcd} 自连接 : L3*L3 abc 和 abd 得到 abcd acd 和 ace 得到 acde 修剪: ade 不在 L3中，删除 acde C4={abcd} 2001-11-6 数据挖掘：概念和技术

提高Apriori效率的方法 基于Hash的项集计数: 如果一个 k-项集在hash-tree的路径上的一个计数值低于阈值，那他本身也不可能是频繁的。 减少交易记录: 不包含任何频繁k-项集的交易也不可能包含任何大于k的频繁集 分割: 一个项集要想在整个数据库中是频繁的，那么他至少在数据库的一个分割上是频繁的。 采样: 在给定数据的子集上挖掘，使用小的支持度+完整性验证方法 动态项集计数: 在添加一个新的候选集之前，先估计一下是不是他的所有子集都是频繁的。 2001-11-6 数据挖掘：概念和技术

Apriori 够快了吗? — 性能瓶颈 Apriori算法的核心: Apriori 的瓶颈: 候选集生成 巨大的候选集: 多次扫描数据库： 用频繁的(k – 1)-项集生成候选的频繁 k-项集 用数据库扫描和模式匹配计算候选集的支持度 Apriori 的瓶颈: 候选集生成 巨大的候选集: 104 个频繁1-项集要生成 107 个候选 2-项集 要找尺寸为100的频繁模式，如 {a1, a2, …, a100}, 你必须先产生2100  1030 个候选集 多次扫描数据库： 如果最长的模式是n的话，则需要 (n +1 ) 次数据库扫描 2001-11-6 数据挖掘：概念和技术

挖掘频繁集 不用生成候选集 用Frequent-Pattern tree (FP-tree) 结构压缩数据库, 高度浓缩，同时对频繁集的挖掘又完备的 避免代价较高的数据库扫描 开发一种高效的基于FP-tree的频繁集挖掘算法 采用分而治之的方法学：分解数据挖掘任务为小任务 避免生成关联规则: 只使用部分数据库! 2001-11-6 数据挖掘：概念和技术

用交易数据库建立 FP-tree 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, p} {c, b, p} 500 {a, f, c, e, l, p, m, n} {f, c, a, m, p} 最小支持度 = 0.5 {} f:4 c:1 b:1 p:1 c:3 a:3 m:2 p:2 m:1 头表 Item frequency head f 4 c 4 a 3 b 3 m 3 p 3 步骤: 扫描数据库一次，得到频繁1-项集 把项按支持度递减排序 再一次扫描数据库，建立FP-tree 2001-11-6 数据挖掘：概念和技术

FP-tree 结构的好处 完备: 不会打破交易中的任何模式 包含了序列模式挖掘所需的全部信息 紧密 去除不相关信息—不包含非频繁项 决不会比原数据库大（如果不计算树节点的额外开销) 例子: 对于 Connect-4 数据库,压缩率超过 100 2001-11-6 数据挖掘：概念和技术

用 FP-tree挖掘频繁集 基本思想 (分而治之) 用FP-tree地归增长频繁集 方法 2001-11-6 数据挖掘：概念和技术

挖掘 FP-tree的主要步骤 为FP-tree中的每个节点生成条件模式库 用条件模式库构造对应的条件FP-tree 递归构造条件 FP-trees 同时增长其包含的频繁集 如果条件FP-tree直包含一个路径，则直接生成所包含的频繁集。 2001-11-6 数据挖掘：概念和技术

步骤1: 从 FP-tree 到条件模式库 从FP-tree的头表开始 按照每个频繁项的连接遍历 FP-tree 列出能够到达此项的所有前缀路径，得到条件模式库 {} f:4 c:1 b:1 p:1 c:3 a:3 m:2 p:2 m:1 头表 Item frequency head f 4 c 4 a 3 b 3 m 3 p 3 条件模式库 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 2001-11-6 数据挖掘：概念和技术

FP-tree支持条件模式库构造的属性 节点裢接 任何包含ai, 的可能频繁集，都可以从FP-tree头表中的ai沿着ai 的节点链接得到 前缀路径 要计算路径P 中包含节点ai 的频繁集，只要考察到达ai 的路径前缀即可，且其支持度等于节点ai 的支持度 2001-11-6 数据挖掘：概念和技术

步骤2: 建立条件 FP-tree 对每个模式库 计算库中每个项的支持度 用模式库中的频繁项建立FP-tree   {} 头表 m-条件模是库: fca:2, fcab:1 头表 Item frequency head f 4 c 4 a 3 b 3 m 3 p 3 f:4 c:1 All frequent patterns concerning m m, fm, cm, am, fcm, fam, cam, fcam {} f:3 c:3 a:3 m-conditional FP-tree c:3 b:1 b:1   a:3 p:1 m:2 b:1 p:2 m:1 2001-11-6 数据挖掘：概念和技术

通过建立条件模式库得到频繁集 Empty f {(f:3)}|c {(f:3)} c {(f:3, c:3)}|a {(fc:3)} a b {(f:3, c:3, a:3)}|m {(fca:2), (fcab:1)} m {(c:3)}|p {(fcam:2), (cb:1)} p 条件FP-tree 条件模式库 项 2001-11-6 数据挖掘：概念和技术

第3步: 递归挖掘条件FP-tree {} f:3 {} c:3 f:3 c:3 {} a:3 f:3 {} f:3 am-条件 FP-tree {} f:3 c:3 a:3 m-条件 FP-tree “am”的条件模式库: (fc:3) {} f:3 “cm”的条件模式: (f:3) cm-条件 FP-tree {} f:3 “cam”条件模式库: (f:3) cam-条件 FP-tree 2001-11-6 数据挖掘：概念和技术

+ 特例: FP-tree 中的唯一前缀路径 用一个节点代替此前缀路径P 分别计算这两个部分的结果 = 假定一个 (条件) FP-tree T 又一个共享唯一前缀路径 P 挖掘可分解为如下两个步骤 用一个节点代替此前缀路径P 分别计算这两个部分的结果 a2:n2 a3:n3 a1:n1 {} b1:m1 C1:k1 C2:k2 C3:k3 b1:m1 C1:k1 C2:k2 C3:k3 r1 a2:n2 a3:n3 a1:n1 {} r1 = +  2001-11-6 数据挖掘：概念和技术

频繁集增长的原理 模式增长的特征 令  为DB的一个频繁集， B 为  的条件模式库，  是 B中的一个项，要使    是DB中的频繁集，当且仅当  是 B 的频繁项. “abcdef ” 是频繁集,当且仅当 “abcde ” 是频繁集, 且 “f ” 在包含 “abcde ”的事务中是频繁的。 2001-11-6 数据挖掘：概念和技术

为什么 频繁集增长 速度快？ 我们的性能研究显示 FP-growth 比Apriori快一个数量级, 同样也比 tree-projection 快。 原因 不生成候选集，不用候选测试。 使用紧缩的数据结构 避免重复数据库扫描 基本操作是计数和建立 FP-tree 树 2001-11-6 数据挖掘：概念和技术

FP-growth vs. Apriori: 相对于支持度的扩展性 Data set T25I20D10K 2001-11-6 数据挖掘：概念和技术

FP-growth vs. Tree-Projection:相对于支持度的扩展性 Data set T25I20D100K 2001-11-6 数据挖掘：概念和技术

关联规则结果显示 (Table Form ) 2001-11-6 数据挖掘：概念和技术

关联规则可视化Using Plane Graph 2001-11-6 数据挖掘：概念和技术

关联规则可视化Using Rule Graph 2001-11-6 数据挖掘：概念和技术

冰山查询 冰山查询: 在一个或多个属性上做聚合，只有当聚合的值高于指定的值时才做计算 举例： 用Apriori提高 执行 冰山查询的效率 select P.custID, P.itemID, sum(P.qty) from purchase P group by P.custID, P.itemID having sum(P.qty) >= 10 用Apriori提高 执行 冰山查询的效率 先计算低维 只有当所有的低维都满足预制时才计算高维 2001-11-6 数据挖掘：概念和技术