数据挖掘概念和技术ppt课件.ppt

2001-11-6;.1数据挖掘: 概念和技术 — Chapter 6 —©张晓辉 2001-11-6;.2第6章：从大数据库中挖掘关联规则n关联规则挖掘n从交易数据库中挖掘一维的布尔形关联规则n从交易数据库中挖掘多层次关联规则n在交易数据库和数据仓库中挖掘多维关联规则n从关联挖掘到相关性分析n基于约束的关联挖掘n小结2001-11-6;.3什么是关联挖掘?n关联规则挖掘：n在交易数据、关系数据或其他信息载体中，查找存在于项目集合或对象集合之间的频繁模式、关联、相关性、或因果结构n应用：n购物篮分析、交叉销售、产品目录设计、 loss-leader analysis、聚集、分类等n举例： n规则形式： “Body ® Head [support, confidence]”.nbuys(x, “diapers”) ® buys(x, “beers”) [0.5%, 60%]nmajor(x, “CS”) ^ takes(x, “DB”) ® grade(x, “A”) [1%, 75%]2001-11-6;.4关联规则：基本概念n给定: (1)交易数据库 (2)每笔交易是：一个项目列表 (消费者一次购买活动中购买的商品)n查找: 所有描述一个项目集合与其他项目集合相关性的规则nE.g., 98% of people who purchase tires and auto accessories also get automotive services donen应用n*  护理用品 (商店应该怎样提高护理用品的销售？)n家用电器  * (其他商品的库存有什么影响?)n在产品直销中使用附加邮寄nDetecting “ping-pong”ing of patients, faulty “collisions”2001-11-6;.5规则度量：支持度与可信度n查找所有的规则 X & Y  Z 具有最小支持度和可信度n支持度, s, 一次交易中包含{X 、 Y 、 Z}的可能性n可信度, c, 包含{X 、 Y}的交易中也包含Z的条件概率设最小支持度为50%, 最小可信度为 50%, 则可得到nA  C (50%, 66.6%)nC  A (50%, 100%)买尿布的客买尿布的客户户二者都买二者都买的客户的客户买啤酒的客户买啤酒的客户2001-11-6;.6关联规则挖掘：路线图n布尔 vs. 定量 关联 (基于 处理数据的类型)nbuys(x, “SQLServer”) ^ buys(x, “DMBook”) ® buys(x, “DBMiner”) [0.2%, 60%]nage(x, “30..39”) ^ income(x, “42..48K”) ® buys(x, “PC”) [1%, 75%]n单维 vs. 多维 关联 (例子同上)n单层 vs. 多层 分析n那个品种牌子的啤酒与那个牌子的尿布有关系?n各种扩展n相关性、因果分析n关联并不一定意味着相关或因果n最大模式和闭合相集n添加约束n如, 哪些“小东西”的销售促发了“大家伙”的买卖？2001-11-6;.7第6章：从大数据库中挖掘关联规则n关联规则挖掘n从交易数据库中挖掘一维的布尔形关联规则n从交易数据库中挖掘多层次关联规则n在交易数据库和数据仓库中挖掘多维关联规则n从关联挖掘到相关性分析n基于约束的关联挖掘n小结2001-11-6;.8关联规则挖掘—一个例子对于 A  C：support = support({A 、C}) = 50%confidence = support({A 、C})/support({A}) = 66.6%Apriori的基本思想:频繁项集的任何子集也一定是频繁的最小值尺度 50%最小可信度 50%2001-11-6;.9关键步骤：挖掘频繁集n频繁集:是指满足最小支持度的项目集合n频繁集的子集也一定是频繁的n如, 如果{AB} 是频繁集，则 {A} {B} 也一定是频繁集n从1到k（k-频繁集）递归查找频繁集n用得到的频繁集生成关联规则2001-11-6;.10Apriori算法n连接: 用 Lk-1自连接得到Ckn修剪: 一个k-项集，如果他的一个k-1项集（他的子集 ）不是频繁的，那他本身也不可能是频繁的。

n伪代码:Ck: Candidate itemset of size kLk : frequent itemset of size kL1 = {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 endreturn k Lk;2001-11-6;.11Apriori算法 — 例子数据库 D扫描 DC1L1L2C2C2扫描 DC3L3扫描 D2001-11-6;.12如何生成候选集n假定 Lk-1 中的项按顺序排列n第一步: 自连接 Lk-1 insert into Ckselect p.item1, p.item2, …, p.itemk-1, q.itemk-1from Lk-1 p, Lk-1 qwhere p.item1=q.item1, …, p.itemk-2=q.itemk-2, p.itemk-1 < q.itemk-1n第二步: 修剪forall itemsets c in Ck doforall (k-1)-subsets s of c doif (s is not in Lk-1) then delete c from Ck2001-11-6;.13如何计算候选集的支持度n计算支持度为什么会成为一个问题？n候选集的个数非常巨大n 一笔交易可能包含多个候选集n方法:n用 hash-tree 存放候选集n树的叶子节点 of存放项集的列表和支持度n内部节点 是一个hash表nSubset 函数: 找到包含在一笔交易中的所有候选集2001-11-6;.14生成候选集的例子nL3={abc, abd, acd, ace, bcd}n自连接 : L3*L3nabc 和 abd 得到 abcd nacd 和 ace 得到 acden修剪:nade 不在 L3中，删除 acdenC4={abcd}2001-11-6;.15提高Apriori效率的方法n基于Hash的项集计数: 如果一个 k-项集在hash-tree的路径上的一个计数值低于阈值，那他本身也不可能是频繁的。

n减少交易记录: 不包含任何频繁k-项集的交易也不可能包含任何大于k的频繁集n分割: 一个项集要想在整个数据库中是频繁的，那么他至少在数据库的一个分割上是频繁的n采样: 在给定数据的子集上挖掘，使用小的支持度+完整性验证方法n动态项集计数: 在添加一个新的候选集之前，先估计一下是不是他的所有子集都是频繁的2001-11-6;.16Apriori 够快了吗? — 性能瓶颈nApriori算法的核心:n用频繁的(k – 1)-项集生成候选的频繁 k-项集n用数据库扫描和模式匹配计算候选集的支持度nApriori 的瓶颈: 候选集生成n巨大的候选集:n104 个频繁1-项集要生成 107 个候选 2-项集n要找尺寸为100的频繁模式，如 {a1, a2, …, a100}, 你必须先产生2100  1030 个候选集n多次扫描数据库： n如果最长的模式是n的话，则需要 (n +1 ) 次数据库扫描2001-11-6;.17挖掘频繁集 不用生成候选集n用Frequent-Pattern tree (FP-tree) 结构压缩数据库, n高度浓缩，同时对频繁集的挖掘又完备的n避免代价较高的数据库扫描n开发一种高效的基于FP-tree的频繁集挖掘算法n采用分而治之的方法学：分解数据挖掘任务为小任务n避免生成关联规则: 只使用部分数据库!2001-11-6;.18用交易数据库建立 FP-tree{}f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1头表头表Item frequency head f4c4a3b3m3p3最小支持度最小支持度 = 0.5TIDItems bought (ordered) frequent items100{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}步骤:1.扫描数据库一次，得到频繁1-项集2.把项按支持度递减排序3.再一次扫描数据库，建立FP-tree2001-11-6;.19FP-tree 结构的好处n完备: n不会打破交易中的任何模式n包含了序列模式挖掘所需的全部信息n紧密n去除不相关信息—不包含非频繁项n支持度降序排列: 支持度高的项在FP-tree中共享的机会也高n决不会比原数据库大（如果不计算树节点的额外开销)n例子: 对于 Connect-4 数据库,压缩率超过 1002001-11-6;.20用 FP-tree挖掘频繁集n基本思想 (分而治之)n用FP-tree地归增长频繁集n方法 n对每个项，生成它的 条件模式库, 然后是它的 条件 FP-treen对每个新生成的条件FP-tree，重复这个步骤n直到结果FP-tree为空, 或只含维一的一个路径 (此路径的每个子路径对应的相集都是频繁集)2001-11-6;.21挖掘 FP-tree的主要步骤1)为FP-tree中的每个节点生成条件模式库2)用条件模式库构造对应的条件FP-tree3)递归构造条件 FP-trees 同时增长其包含的频繁集§如果条件FP-tree直包含一个路径，则直接生成所包含的频繁集。

2001-11-6;.22步骤1: 从 FP-tree 到条件模式库n从FP-tree的头表开始n按照每个频繁项的连接遍历 FP-treen列出能够到达此项的所有前缀路径，得到条件模式库条件模式库条件模式库itemcond. pattern basecf:3afc:3bfca:1, f:1, c:1mfca:2, fcab:1pfcam:2, cb:1{}f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1头表头表Item frequency head f4c4a3b3m3p32001-11-6;.23FP-tree支持条件模式库构造的属性n节点裢接n任何包含ai, 的可能频繁集，都可以从FP-tree头表中的ai沿着ai 的节点链接得到n前缀路径n要计算路径P 中包含节点ai 的频繁集，只要考察到达ai 的路径前缀即可，且其支持度等于节点ai 的支持度2001-11-6;.24步骤2: 建立条件 FP-tree n对每个模式库n计算库中每个项的支持度n用模式库中的频繁项建立FP-treem-条件模是库条件模是库:fca:2, fcab:1{}f:3c:3a:3m-conditional FP-treeAll frequent patterns concerning mm, fm, cm, am, fcm, fam, cam, fcam{}f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1头表头表Item frequency head f4c4a3b3m3p32001-11-6;.25通过建立条件模式库得到频繁集EmptyEmptyf{(f:3)}|c{(f:3)}c{(f:3, c:3)}|a{(fc:3)}aEmpty{(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条件FP-tree条件模式库项2001-11-6;.26第3步: 递归挖掘条件FP-tree{}f:3c:3a:3m-条件 FP-tree“am”的条件模式库: (fc:3){}f:3c:3am-条件 FP-tree“cm”的条件模式: (f:3){}f:3cm-条件 FP-tree“cam”条件模式库: (f:3){}f:3cam-条件 FP-tree2001-11-6;.28特例: FP-tree 中的唯一前缀路径n假定一个 (条件) FP-tree T 又一个共享唯一前缀路径 Pn挖掘可分解为如下两个步骤n用一个节点代替此前缀路径Pn分别计算这两个部分的结果a2:n2a3:n3a1:n1{}b1:m1C1:k1C2:k2C3:k3b1:m1C1:k1C2:k2C3:k3r1+a2:n2a3:n3a1:n1{}r1=2001-11-6;.29频繁集增长的原理n模式增长的特征n令  为DB的一个频繁集， B 为  的条件模式库，  是 B中的一个项，要使    是DB中的频繁集，当且仅当  是 B 的频繁项. n“abcdef ” 是频繁集,当且仅当n“abcde ” 是频繁集, 且n“f ” 在包含 “abcde ”的事务中是频繁的。

2001-11-6;.30为什么 频繁集增长 速度快？n我们的性能研究显示nFP-growth 比Apriori快一个数量级, 同样也比 tree-projection 快n原因n不生成候选集，不用候选测试n使用紧缩的数据结构n避免重复数据库扫描n基本操作是计数和建立 FP-tree 树2001-11-6;.31FP-growth vs. Apriori: 相对于支持度的扩展性Data set T25I20D10K2001-11-6;.32FP-growth vs. Tree-Projection:相对于支持度的扩展性Data set T25I20D100K2001-11-6;.33关联规则结果显示 (Table Form )2001-11-6;.34关联规则可视化关联规则可视化Using Plane Graph2001-11-6;.35关联规则可视化关联规则可视化Using Rule Graph2001-11-6;.36冰山查询n冰山查询: 在一个或多个属性上做聚合，只有当聚合的值高于指定的值时才做计算n举例：select P.custID, P.itemID, sum(P.qty)from purchase Pgroup by P.custID, P.itemIDhaving sum(P.qty) >= 10n用Apriori提高 执行 冰山查询的效率n先计算低维n只有当所有的低维都满足预制时才计算高维。