数据挖掘从大数据库中挖掘关联规则(编辑修改稿)

数据挖掘从大数据库中挖掘关联规则(编辑修改稿)内容摘要：

 不会打破交易中的任何模式  包含了序列模式挖掘所需的全部信息  紧密  去除不相关信息 —不包含非频繁项  支持度降序排列 : 支持度高的项在 FPtree中共享的机会也高  决不会比原数据库大（如果不计算树节点的额外开销 )  例子 : 对于 Connect4 数据库 ,压缩率超过 100 2020116 数据挖掘：概念和技术 20 用 FPtree挖掘频繁集  基本思想 (分而治之 )  用 FPtree地归增长频繁集  方法  对每个项，生成它的 条件模式库 , 然后是它的 条件 FPtree  对每个新生成的条件 FPtree， 重复这个步骤  直到结果 FPtree为 空 , 或只含 维一的一个路径 (此路径的每个子路径对应的相集都是频繁集 ) 2020116 数据挖掘：概念和技术 21 挖掘 FPtree的主要步骤 1) 为 FPtree中的每个节点生成条件模式库 2) 用条件模式库构造对应的条件 FPtree 3) 递归构造条件 FPtrees 同时增长其包含的频繁集  如果条件 FPtree直包含一个路径，则直接生成所包含的频繁集。 2020116 数据挖掘：概念和技术 22 步骤 1: 从 FPtree 到条件模式库  从 FPtree的头表开始  按照每个频繁项的连接遍历 FPtree  列出能够到达此项的所有前缀路径，得到条件模式库 条件模式库 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 {} 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 2020116 数据挖掘：概念和技术 23 FPtree支持条件模式库构造的属性  节点裢接  任何包含 ai, 的可能频繁集，都可以从 FPtree头表中的 ai沿着 ai 的节点链接得到  前缀路径  要计算路径 P 中包含节点 ai 的频繁集，只要考察到达 ai 的路径前缀即可，且其支持度等于节点 ai 的支持度 2020116 数据挖掘：概念和技术 24 步骤 2: 建立条件 FPtree  对每个模式库  计算库中每个项的支持度  用模式库中的频繁项建立 FPtree m条件模是库 : fca:2, fcab:1 {} f:3 c:3 a:3 mconditional FPtree 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 2020116 数据挖掘：概念和技术 25 通过建立条件模式库得到频繁集 Empty Empty f {(f:3)}|c {(f:3)} c {(f:3, c:3)}|a {(fc:3)} a Empty {(fca:1), (f:1), (c:1)} b {(f:3, c:3, a:3)}|m {(fca:2), (fcab:1)} m {(c:3)}|p {(fcam:2), (cb:1)} p 条件 FPtree 条件模式库 项 2020116 数据挖掘：概念和技术 26 第 3步 : 递归挖掘条件 FPtree {} f:3 c:3 a:3 m条件 FPtree ―am‖的条件模式库 : (fc:3) {} f:3 c:3 am条件 FPtree ―cm‖的条件模式 : (f:3) {} f:3 cm条件 FPtree ―cam‖条件模式库 : (f:3) {} f:3 cam条件 FPtree 2020116 数据挖掘：概念和技术 28 特例 : FPtree 中的 唯一 前缀路径  假定一个 (条件 ) FPtree 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 = 2020116 数据挖掘：概念和技术 29 频繁集增长的原理  模式增长的特征  令  为 DB的一个频繁集， B 为  的条件模式库，  是 B中的一个项，要使    是 DB中的频繁集，当且仅当  是 B 的频繁项 .  ―abcdef ‖ 是频繁集 ,当且仅当  ―abcde ‖ 是频繁集 , 且  ―f ‖ 在包含 “ abcde ‖的事务中是频繁的。 2020116 数据挖掘：概念和技术 30 为什么 频繁集增长 速度快。  我们的性能研究显示  FPgrowth 比 Apriori快一个数量级 , 同样也比 treeprojection 快。  原因  不生成候选集，不用候选测试。  使用紧缩的数据结构  避免重复数据库扫描  基本操作是计数和建立 FPtree 树 2020116 数据挖掘：概念和技术 31 FPgrowth vs. Apriori: 相对于支持度的扩。