• 1. 第6章:挖掘大型数据库中的关联规则6.1 关联规则挖掘 6.2由事务数据库挖掘单维布尔关联规则 6.3由事务数据库挖掘多层关联规则 6.4由关系数据库和数据仓库挖掘多维关联规则 6.5由关联挖掘到相关性分析 6.6基于约束的关联挖掘 6.7小结2018/10/201数据挖掘:概念和技术
  • 2. 什么是关联挖掘?关联规则挖掘: 在交易数据、关系数据或其他信息载体中,查找存在于项目集合或对象集合之间的频繁模式、关联、相关性、或因果结构。 应用: 购物篮分析、交叉销售、产品目录设计、 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%]2018/10/202数据挖掘:概念和技术
  • 3. 关联规则:基本概念给定: (1)交易数据库 (2)每笔交易是:一个项目列表 (消费者一次购买活动中购买的商品) 查找: 所有描述一个项目集合与其他项目集合相关性的规则 E.g., 98% of people who purchase tires and auto accessories also get automotive services done 应用 *  护理用品 (商店应该怎样提高护理用品的销售?) 家用电器  * (其他商品的库存有什么影响?) 在产品直销中使用附加邮寄2018/10/203数据挖掘:概念和技术
  • 4. 规则度量:支持度与可信度查找所有的规则 X & Y  Z 具有最小支持度和可信度 支持度, s, 一次交易中包含{X 、 Y 、 Z}的可能性 置信度, c, 包含{X 、 Y}的交易中也包含Z的条件概率设最小支持度为50%, 最小可信度为 50%, 则可得到 A  C (50%, 66.6%) C  A (50%, 100%)买尿布的客户二者都买的客户买啤酒的客户2018/10/204数据挖掘:概念和技术
  • 5. 关联规则挖掘:路线图布尔 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. 多层 分析(基于规则集所涉及的抽象层) 那个品种牌子的啤酒与那个牌子的尿布有关系? 各种扩展 相关性、因果分析 关联并不一定意味着相关或因果 最大模式和闭合项集2018/10/205数据挖掘:概念和技术
  • 6. 第6章:从大数据库中挖掘关联规则6.1 关联规则挖掘 6.2由事务数据库挖掘单维布尔关联规则 6.3由事务数据库挖掘多层关联规则 6.4由关系数据库和数据仓库挖掘多维关联规则 6.5由关联挖掘到相关性分析 6.6基于约束的关联挖掘 6.7小结2018/10/206数据挖掘:概念和技术
  • 7. 关联规则挖掘—一个例子对于 A  C: support = support({A 、C}) = 50% confidence = support({A 、C})/support({A}) = 66.6% Apriori的基本思想: 频繁项集的任何子集也一定是频繁的最小值尺度 50% 最小可信度 50%2018/10/207数据挖掘:概念和技术
  • 8. 关键步骤:挖掘频繁集频繁集:是指满足最小支持度的项目集合 频繁集的子集也一定是频繁的 如, 如果{AB} 是频繁集,则 {A} {B} 也一定是频繁集 从1到k(k-频繁集)递归查找频繁集 用得到的频繁集生成关联规则2018/10/208数据挖掘:概念和技术
  • 9. Apriori算法连接: 用 Lk-1自连接得到候选k-项集Ck 修剪: 一个k-项集,如果他的一个k-1项集(他的子集 )不是频繁的,那他本身也不可能是频繁的。 伪代码: Ck: Candidate itemset of size k Lk : frequent itemset of size k L1 = { frequent items}; for (k = 2; Lk-1 !=; k++) do begin Ck = candidates generated from Lk-1; for each transaction t in database do increment the count of all candidates in Ck that are contained in t Lk = candidates in Ck with min_support end return k Lk;2018/10/209数据挖掘:概念和技术
  • 10. Apriori算法 — 例子数据库 D扫描 DC1L1L2C2C2扫描 DC3L3扫描 D2018/10/2010数据挖掘:概念和技术
  • 11. 如何生成候选集假定 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 第二步: 修剪 For all itemsets c in Ck do For all (k-1)-subsets s of c do if (s is not in Lk-1) then delete c from Ck2018/10/2011数据挖掘:概念和技术
  • 12. 计算支持度为什么会成为一个问题? 候选集的个数非常巨大 一笔交易可能包含多个候选集2018/10/2012数据挖掘:概念和技术
  • 13. 生成候选集的例子L3={abc, abd, acd, ace, bcd} 自连接 : L3*L3 abc 和 abd 得到 abcd acd 和 ace 得到 acde 修剪: ade 不在 L3中,删除 acde C4={abcd}2018/10/2013数据挖掘:概念和技术
  • 14. 提高Apriori效率的方法1.基于Hash的项集计数: 若 k-项集在hash-tree的路径上的一个计数值低于阈值,那他本身也不可能是频繁的。(157页图6-6) 2.减少交易记录: 不包含任何频繁k-项集的交易也不可能包含任何大于k的频繁集,下一步计算时删除这些记录。 3.划分: 一个项集要想在整个数据库中是频繁的,那么他至少在数据库的一个分割上是频繁的。 两次扫描数据。(157页图5-6) 4.抽样: 使用小的支持度+完整性验证方法。在小的抽样集上找到局部频繁项集,然后在全部数据集找频繁项集。 5.动态项集计数: 在添加一个新的候选集之前,先估计一下是不是他的所有子集都是频繁的。2018/10/2014数据挖掘:概念和技术
  • 15. Apriori 够快了吗? — 性能瓶颈Apriori算法的核心: 用频繁的(k – 1)-项集生成候选的频繁 k-项集 用数据库扫描和模式匹配计算候选集的支持度 Apriori 的瓶颈: 候选集生成 巨大的候选集: 104 个频繁1-项集要生成 107 个候选 2-项集 要找尺寸为100的频繁模式,如 {a1, a2, …, a100}, 你必须先产生2100  1030 个候选集 多次扫描数据库: 如果最长的模式是n的话,则需要 (n +1 ) 次数据库扫描2018/10/2015数据挖掘:概念和技术
  • 16. 挖掘频繁集 不用生成候选集频繁模式增长 (FP--增长)用Frequent-Pattern tree (FP-tree) 结构压缩数据库, 高度浓缩,同时对频繁集的挖掘又完备的 避免代价较高的数据库扫描 开发一种高效的基于FP-tree的频繁集挖掘算法 采用分而治之的方法学:分解数据挖掘任务为小任务 避免生成关联规则: 分别挖掘条件数据库2018/10/2016数据挖掘:概念和技术
  • 17. 用 FP-tree挖掘频繁集基本思想 (分而治之) 用FP-tree地归增长频繁集 方法 对每个项,生成它的 条件模式库, 然后是它的 条件 FP-tree 对每个新生成的条件FP-tree,重复这个步骤 直到结果FP-tree为空, 或只含维一的一个路径 (此路径的每个子路径对应的相集都是频繁集)2018/10/2017数据挖掘:概念和技术
  • 18. 挖掘 FP-tree的主要步骤为FP-tree中的每个节点生成条件模式库 用条件模式库构造对应的条件FP-tree 递归构造条件 FP-trees 同时增长其包含的频繁集 如果条件FP-tree直包含一个路径,则直接生成所包含的频繁集。2018/10/2018数据挖掘:概念和技术
  • 19. 步骤1: 建立 FP-tree (159页图6-8)从FP-tree的头表开始 按照每个频繁项的连接遍历 FP-tree 列出能够到达此项的所有前缀路径,得到条件模式库步骤2:建立条件FP-tree进行挖掘(159页图6-9)对每个模式库 计算库中每个项的支持度 用模式库中的频繁项建立FP-tree2018/10/2019数据挖掘:概念和技术
  • 20. 为什么 频繁集增长 速度快?我们的性能研究显示 FP-growth 比Apriori快一个数量级, 同样也比 tree-projection 快。 原因 不生成候选集,不用候选测试。 使用紧缩的数据结构 避免重复数据库扫描 基本操作是计数和建立 FP-tree 树2018/10/2020数据挖掘:概念和技术
  • 21. FP-growth vs. Apriori: 相对于支持度的扩展性Data set T25I20D10K2018/10/2021数据挖掘:概念和技术
  • 22. FP-growth vs. Tree-Projection:相对于支持度的扩展性Data set T25I20D100K2018/10/2022数据挖掘:概念和技术
  • 23. 关联规则结果显示 (Table Form )2018/10/2023数据挖掘:概念和技术
  • 24. 关联规则可视化Using Plane Graph2018/10/2024数据挖掘:概念和技术
  • 25. 关联规则可视化Using Rule Graph2018/10/2025数据挖掘:概念和技术
  • 26. 第6章:从大数据库中挖掘关联规则6.1 关联规则挖掘 6.2由事务数据库挖掘单维布尔关联规则 6.3由事务数据库挖掘多层关联规则 6.4由关系数据库和数据仓库挖掘多维关联规则 6.5由关联挖掘到相关性分析 6.6基于约束的关联挖掘 6.7小结 2018/10/2026数据挖掘:概念和技术
  • 27. 多层关联规则项通常具有层次 底层的项通常支持度也低 某些特定层的规则可能更有意义 交易数据库可以按照维或层编码 可以进行共享的多维挖掘食品面包牛奶脱脂奶光明统一酸奶白黄2018/10/2027数据挖掘:概念和技术
  • 28. 挖掘多层关联规则自上而下,深度优先的方法: 先找高层的“强”规则: 牛奶 ® 面包 [20%, 60%]. 再找他们底层的“弱”规则: 酸奶 ® 黄面包 [6%, 50%]. 多层关联规则的变种 1 支持度不变: 在各层之间使用统一的支持度 + 一个最小支持度阈值. 如果一个项集的父项集不具有最小支持度,那他本身也不可能满足最小支持度。 – 底层项不会成为频繁集,如果支持度 太高  丢失底层关联规则 太低  生成太多的高层关联规则 2 支持度递减: 随着层次的降低支持度递减 2018/10/2028数据挖掘:概念和技术
  • 29. 多层关联规则: 支持度不变 vs. 支持度递减3层次交叉单项过滤: 4层次交叉K-项过滤: 4种搜索策略: 层与层独立 用k-项集跨层过滤 用项跨层过滤 用项进行可控跨层过滤 2018/10/2029数据挖掘:概念和技术
  • 30. 支持度不变支持度不变多层挖掘牛奶 [support = 10%]酸奶 [support = 6%]脱脂奶 [support = 4%]层 1 min_sup = 5%层 2 min_sup = 5%2018/10/2030数据挖掘:概念和技术
  • 31. 支持度递减支持度递减多层挖掘酸奶 [support = 6%]脱脂奶 [support = 4%]层 1 min_sup = 5%层 2 min_sup = 3%牛奶 [support = 10%]2018/10/2031数据挖掘:概念和技术
  • 32. 多层关联:冗余过滤由于“祖先”关系的原因,有些规则可能是多余的。 例子 奶制品  白面包 [support = 8%, confidence = 70%] 酸奶  白面包 [support = 2%, confidence = 72%] 酸奶占奶制品25% 我们称第一个规则是第二个规则的祖先 参考规则的祖先,如果他的支持度与我们“预期”的支持度近似的话,我们就说这条规则是冗余的。2018/10/2032数据挖掘:概念和技术
  • 33. 数据挖掘查询的逐步精化为什么要逐步精化 挖掘操作的代价可能高或低,结果可能过细致或粗糙 在速度和质量之间折衷:逐步精化 超集覆盖特征: 预存储所有正面答案—允许进一步正确性验证,而不必验证已经错误的 2或多步挖掘: 先执行粗糙的、容易的操作 (超集覆盖) 然后在减少后的候选集上进行计算量大的算法 (Koperski & Han, SSD’95).2018/10/2033数据挖掘:概念和技术
  • 34. 第6章:从大数据库中挖掘关联规则6.1 关联规则挖掘 6.2由事务数据库挖掘单维布尔关联规则 6.3由事务数据库挖掘多层关联规则 6.4由关系数据库和数据仓库挖掘多维关联规则 6.5由关联挖掘到相关性分析 6.6基于约束的关联挖掘 6.7小结 2018/10/2034数据挖掘:概念和技术
  • 35. 多维关联规则: 概念单维规则: buys(X, “milk”)  buys(X, “bread”) 多维规则: 2个以上维/谓词 维间关联规则 (维词不重复) age(X,”19-25”)  occupation(X,“student”)  buys(X,“coke”) 混合维关联规则 (维词重复) age(X,”19-25”)  buys(X, “popcorn”)  buys(X, “coke”) 类别属性 有限个值, 值之间无顺序关系 数量属性 数字的,值之间隐含了顺序关系2018/10/2035数据挖掘:概念和技术
  • 36. 挖掘多维关联的技术搜索频繁k-维词集合: 如: {age, occupation, buys} 是一个3-维词集合。 按照对 age 处理方式的不同,分为: 1. 用静态方法把数值属性离散化 数值属性可用预定义的概念层次加以离散化。 2. 带数量的关联规则 根据数据的分布,动态的把数值属性离散化到不同的“箱”。 3. 基于距离的关联规则 用数据点之间的距离动态的离散化2018/10/2036数据挖掘:概念和技术
  • 37. 数值属性的静态离散化在挖掘之前用概念层次先离散化 数值被替换为区间范围 关系数据库中,要找到所有频繁k-维词需要k或k+1次表扫描。 适宜使用数据立方体 N维立方体的每个单元 对应一个维词集合 使用数据立方体速度更快(income)(age)()(buys)(age, income)(age,buys)(income,buys)(age,income,buys)2018/10/2037数据挖掘:概念和技术
  • 38. 带数量的关联规则age(X,”30-34”)  income(X,”24K - 48K”)  buys(X,”high resolution TV”)动态 离散化数值属性 使满足某种挖掘标准,如最大化挖掘规则的置信度紧凑性. 2-维数量关联规则: Aquan1  Aquan2  Acat 用2-维表格把“邻近”的 关联规则组合起来 例子 2018/10/2038数据挖掘:概念和技术
  • 39. ARCS (关联规则聚集系统) ARCS 流程 1. 分箱 2. 查找频繁维词 集合 3. 关联规则聚类 4. 优化 2018/10/2039数据挖掘:概念和技术
  • 40. ARCS的局限性数值属性只能出现在规则的左侧 左侧只能有两个属性 (2维) ARCS 的改进 不用基于栅格的方法 等深分箱 基于局部完整性 测度的聚集 “Mining Quantitative Association Rules in Large Relational Tables” by R. Srikant and R. Agrawal.2018/10/2040数据挖掘:概念和技术
  • 41. 挖掘基于距离的关联规则分箱的方法没有体现数据间隔的语义 基于距离的分割是更有“意义”的离散化方法,考虑: 区间内密度或点的个数 区间内点的“紧密程度2018/10/2041数据挖掘:概念和技术
  • 42. 第6章:从大数据库中挖掘关联规则6.1 关联规则挖掘 6.2由事务数据库挖掘单维布尔关联规则 6.3由事务数据库挖掘多层关联规则 6.4由关系数据库和数据仓库挖掘多维关联规则 6.5由关联挖掘到相关性分析 6.6基于约束的关联挖掘 6.7小结 2018/10/2042数据挖掘:概念和技术
  • 43. 强关联规则不一定是有趣的(168页例5.8) 由关联分析到相关分析 项集A与项集B独立 P(AB)=P(A)P(B) 项集A、B的相关性 corrAB=P(AB)/P(A)P(B) 2018/10/2043数据挖掘:概念和技术
  • 44. 第6章:从大数据库中挖掘关联规则6.1 关联规则挖掘 6.2由事务数据库挖掘单维布尔关联规则 6.3由事务数据库挖掘多层关联规则 6.4由关系数据库和数据仓库挖掘多维关联规则 6.5由关联挖掘到相关性分析 6.6基于约束的关联挖掘 6.7小结 2018/10/2044数据挖掘:概念和技术
  • 45. 6.6.1 基于约束的挖掘使用约束的必要性 在数据挖掘中常使用的几种约束: 知识类型约束:指定要挖掘的知识类型 如关联规则 数据约束: 指定与任务相关的数据集 Find product pairs sold together in Vancouver in Dec.’98. 维/层次约束:指定所用的维或概念结构中的层 in relevance to region, price, brand, customer category. 规则约束:指定要挖掘的规则形式(如规则模板) 单价 (price < $10)的交易项目可能引发购买总额 (sum > $200). 兴趣度约束:指定规则兴趣度阈值或统计度量 如 (min_support  3%, min_confidence  60%).2018/10/2045数据挖掘:概念和技术
  • 46. 假定AllElectronics的一个销售多维数据库有如下关系(176页) Sales(customer_name,item_name,transaction_id) Lives(customer_name,region,city) Items(item_name,category,price) Transaction(transaction_id,day,month,year) (1) mine associations as (2)lives(C,_,”Pudong”)^sales(C,{I},{S})=>sales(C,{J}{T}) (3) from sales (4)where S.year=1999 &&T.year=1999 &&I.category=J.category (5)group by C,I.category (6)having sum(I.price<=100)&&min(J.price)>=500 (7)with support threshold=1% (8)with confidence threshold=50% Lives(C,_,”Pudong”)^Sales(C,”Census_CD”,_)^Sales(C,”MS/Office”,_)=>Sales(C,”MS/SQLSever”,_) [1.5%,65%]2018/10/2046数据挖掘:概念和技术
  • 47. 6.6.2 约束的分类单调性约束(monotone constraint) 反单调性约束(anti-monotone constraint) 可转变的约束(convertibale constraint) 简洁性约束(succinct constraint) 不可转变的约束(non-convertibale constraint)2018/10/2047数据挖掘:概念和技术
  • 48. 约束的有关概念项目集:I={i1,i2,……,im}, 交易:T= 模式S是项目集的子集,S={ij1,ij2,…,ijk} 模式S包含与T,T=,iff S<=It; S’是S的子模式(subpattern)且S 是S’的超模式(superpattern),if 有S’<=S.2018/10/2048数据挖掘:概念和技术
  • 49. 约束的有关概念(续)定义约束: C是作用于项目集I的幂集(powerset)上的谓词,C(S)=True/False; 满意模式集(satisfying pattern set) SATc(I)是指那些完全满足约束C的项目集的全体 将约束条件用于频繁集的查询无非是找出那些满足C的频繁集  2018/10/2049数据挖掘:概念和技术
  • 50. 单调和反单调的规则约束规则 Ca 是 反单调的(anti-monotone) iff 对于任给的不满足Ca的项集(模式) S, 不存在S的超集能够满足 Ca e.g: Ca : min(S)>=v , v是S的一个项集 约束Cm 是单调的iff.对于任给的满足Cm的项集(模式) S, 每一个S的超集都能够满足 Cm e.g: Cm : min(S)<=v, v是S的一个项集 2018/10/2050数据挖掘:概念和技术