频繁模式挖掘与关联规则挖掘

1、2022-3-31数 据 挖 掘1数 据 挖 掘第六章 挖掘大型数据库中的关联规则孙玉芬武汉理工大学计算机科学与技术学院计算机科学系2022-3-31数 据 挖 掘2挖掘大型数据库中的关联规则n 6.1 关联规则挖掘n 6.2 由事务数据库挖掘单维布尔关联规则n 6.3 由事务数据库挖掘多层关联规则n 6.4 由关系数据库和数据仓库挖掘多维关联规则n 6.5 由关联挖掘到相关分析n 6.6 基于约束的关联挖掘n 6.7 小结2022-3-31数 据 挖 掘36.1 关联规则挖掘n由Agrawal，Imielinski，与Swami AIS93首次提出频繁项集（frequent itemsets

2、）与关联规则挖掘（association rule mining）n动机：找出数据中存在的规则 A Bn哪些产品总是被同时购买？啤酒与尿布？！n顾客购买PC后，还会购买哪些商品？n哪种DNA会对某种新药敏感？n先挖掘频繁模式，然后挖掘关联规则n频繁模式：在一个数据集中频繁出现的模式 （数据项集，子序列，子结构，等）2022-3-31数 据 挖 掘4基本概念：频繁模式与关联规则n项集 X = x1, , xkn找出所有置信度与支持度超过阈值的规则 X Yn支持度（support），s，包含X Y的事务出现的概率n置信度（confidence），c，事务包含X时，也包含Y的条件概率置supmin

3、= 50%， confmin = 50%频繁模式： A:3, B:3, D:4, E:3, AD:3关联规则：A D (60%, 100%)D A (60%, 75%)购买尿布的购买尿布的顾客顾客两样都买两样都买的顾客的顾客购买啤酒的顾客购买啤酒的顾客事务号事务号购买的项购买的项10A, B, D20A, C, D30A, D, E40B, E, F50B, C, D, E, F2022-3-31数 据 挖 掘5为什么频繁模式挖掘是重要的？n能发现数据集中内在的特性n是许多重要的数据挖掘任务的基础n关联分析，相关分析，与因果分析n序列模式，结构模式（如：子图）n时空数据、多媒体数据、时序数据、

4、流数据中的模式分析n分类：关联分类n聚类：基于频繁模式的聚类n数据仓库：冰山数据立方 n语义数据压缩n广泛的应用n购物篮数据分析，Web点击流分析，打折销售分析，DNA序列分析2022-3-31数 据 挖 掘6关联规则的分类n布尔关联规则与量化关联规则n计算机 财务管理软件n年龄（X，”3039”） 收入（X，”42k48k”） 购买（X，”高清晰电视”）n单维关联规则与多维关联规则n单层关联规则与多层关联规则n年龄（X， ”3039” ） 购买（X，”笔记本”）n年龄（X， ”3039” ） 购买（X，”计算机”）n闭模式与最大模式2022-3-31数 据 挖 掘7闭模式与最大模式n一个长模

5、式包含大量子模式。例如：a1, , a100 包含 C1001 + C1002 + + C110000 = 2100 1 = 1.27*1030子模式！n解决方法：挖掘闭模式（ closed patterns ）与最大模式（ max-patterns）n一个项集X是闭模式，如果X是频繁的，且不存在超模式 Y ? X具有与X同样的支持度（Pasquier，ICDT99）n一个项集X是一个最大模式，如果X是频繁的，并且不存在频繁超模式 Y ? X （Bayardo，SIGMOD98）n闭模式是频繁模式集的无损压缩n压缩了模式与规则的数目2022-3-31数 据 挖 掘8闭模式与最大模式n例子：DB

6、 = , n最小支持度 = 1n有哪些闭模式?n: 1n: 2n有哪些最大模式？n: 1n所有模式n!2022-3-31数 据 挖 掘9挖掘大型数据库中的关联规则n 6.1 关联规则挖掘n 6.2 由事务数据库挖掘单维布尔关联规则n 6.3 由事务数据库挖掘多层关联规则n 6.4 由关系数据库和数据仓库挖掘多维关联规则n 6.5 由关联挖掘到相关分析n 6.6 基于约束的关联挖掘n 6.7 小结2022-3-31数 据 挖 掘106.2 由事务数据库挖掘单维布尔关联规则n挖掘最简单形式的关联规则：n单维n单层n布尔n两个主要方法nApriori（Agrawal & SrikantVLD

7、B94）n频繁模式增长方法（FPgrowthHan, Pei & Yin SIGMOD00）2022-3-31数 据 挖 掘116.2.1 Apriori：一个基于候选集的方法nApriori性质：n一个频繁项集的所有非空子集都必定是频繁的n如果 啤酒，尿布，坚果 是频繁的，则 啤酒，尿布必定是频繁的n每个包含 啤酒，尿布，坚果 的事务，必定包含 啤酒，尿布 n反单调nApriori 修剪原则: 如果某个项集是不频繁的，则它的超集不需要被考虑2022-3-31数 据 挖 掘12Apriori 方法n逐层搜索：由 K项集到 k+1候选项集n方法：n扫描数据集一次，得到所有长度为1的频繁项

8、集n基于长度为 K 的频繁项集，生成长度为 k+1 的候选项集n扫描数据集，检测候选项集是否频繁n当没有频繁项集或候选项集生成时，中止算法。2022-3-31数 据 挖 掘13例子：Apriori 算法 事务数据库第一遍扫描C1L1L2C2C2第二遍扫描C3L3第三遍扫描事务号事务号项项10A, C, D20B, C, E30A, B, C, E40B, E项集项集SA2B3C3D1E3项集项集SA2B3C3E3项集项集A, BA, CA, EB, CB, EC, E项集项集SA, B1A, C2A, E1B, C2B, E3C, E2项集项集SA, C2B, C2B, E3C, E2项集项集

9、B, C, E项集项集SB, C, E2Smin = 22022-3-31数 据 挖 掘14Apriori 算法n伪码：Ck ：长度为 k 的候选项集Lk ： 长度为 k 的频繁项集L1 = 频繁项;for (k = 1; Lk !=; k+) do begin Ck+1 = 由 Lk 生成的候选项集； 对对数据库中的每个事务 t do 将 Ck+1 中所有在 t 中出现的候选项集的计数分别加 1 Lk+1 = Ck+1 中所有计数超过支持度阈值的候选项集 endreturn k Lk;2022-3-31数 据 挖 掘15Apriori 中的重要细节n如何生成候选项集？n第一步：self-jo

10、ining Lkn第二步：修剪n生成候选项集的例子nL3=abc, abd, acd, ace, bcdnSelf-joining: L3*L3n由 abc 与 abd 得到 abcdn由 acd 与 ace 得到 acden修剪：n由于 ade 不在 L3 中，acde 被删除nC4=abcd2022-3-31数 据 挖 掘16如何生成候选项集？n假设 Lk-1 中的项按某个次序排列n第一步：self-joining Lk-1 insert into Ckselect p.item1, p.item2, , p.itemk-1, q.itemk-1from Lk-1 p, Lk-1 qwhe

11、re p.item1=q.item1, , p.itemk-2=q.itemk-2, p.itemk-1 = 3n产生候选 select P.cust_ID select P.item_ID from Purchases P from Purchases P group by P.cust_ID group by P.item_ID having SUM(P.qty) = 3 having SUM(P.qty) = 32022-3-31数 据 挖 掘36挖掘大型数据库中的关联规则n6.1 关联规则挖掘n6.2 由事务数据库挖掘单维布尔关联规则n6.3 由事务数据库挖掘多层关联规则n6.4 由关

12、系数据库和数据仓库挖掘多维关联规则n6.5 由关联挖掘到相关分析n6.6 基于约束的关联挖掘n6.7 小结2022-3-31数 据 挖 掘376.3.1 多层关联规则n数据库中的项经常形成层次关系n多层关联规则：由具有概念分层的关联规则挖掘产生的规则n为什么要挖掘多层关联规则n在低层/原始层的数据项之间很难找出强关联规则n用户的需求n例子：2022-3-31数 据 挖 掘386.3.2 挖掘多层关联规则的方法n通常采用自顶向下的策略n对于所有层使用一致的最小支持度n递减的支持度阈值设置 n较低层次的项通常具有较低的支持度统一的支持度阈值computer支持度支持度 = 10%laptop 支持

13、度支持度 = 6%desktop 支持度支持度 = 4%层层 1支持度阈值 = 5%层层 2支持度阈值= 5%层层 1支持度阈值 = 5%层层 2支持度阈值= 3%不统一的支持度阈值2022-3-31数 据 挖 掘39频繁项集搜索策略n逐层独立n没有剪枝n层交叉单项过滤n一个第 i 层的项被考察，当且仅当它在第（i-1）层的父节点是频繁的computer支持度支持度 = 10%laptop （未考察）未考察）desktop （未考察）未考察）层层 1支持度阈值 = 12%层层 2支持度阈值= 3%2022-3-31数 据 挖 掘40频繁项集搜索策略n层交叉 k-项集过滤n一个第 i 层的 k-

14、项集被考察，当且仅当它在第（i-1）层的对应父节点 k-项集是频繁的Computer and printer支持度支持度 = 7%Laptop computer and b/w printer 支持度支持度 = 1%Desktop computer and b/w printer 支持度支持度 = 1%层层 1支持度阈值 = 5%层层 2支持度阈值= 2%Laptop computer and color printer 支持度支持度 = 2%Desktop computer and b/w printer 支持度支持度 = 3%2022-3-31数 据 挖 掘41频繁项集搜索策略n受控的层交

15、叉单项过滤策略n层传递阈值n下一层的最小支持度阈值与当前层的最小支持度阈值之间的值computer支持度支持度 = 10%laptop 支持度支持度 = 6%desktop 支持度支持度 = 4%层层 1支持度阈值 = 12%层传递阈值 = 8% 层层 2支持度阈值= 3%2022-3-31数 据 挖 掘426.3.3 检查冗余的多层关联规则n由于项之间的层次关系，一些规则之间可能存在冗余n例子nDesktop computer b/w printer 支持度 = 8%， 置信度 = 70%nIBM desktop computer b/w printer 支持度 = 2%， 置信度 = 72

16、%n我们称第一个规则是第二个规则的祖先n若一个规则的支持度与基于其祖先规则推导出的期望的支持度相似，则称这个规则是冗余的2022-3-31数 据 挖 掘43挖掘大型数据库中的关联规则n6.1 关联规则挖掘n6.2 由事务数据库挖掘单维布尔关联规则n6.3 由事务数据库挖掘多层关联规则n6.4 由关系数据库和数据仓库挖掘多维关联规则n6.5 由关联挖掘到相关分析n6.6 基于约束的关联挖掘n6.7 小结2022-3-31数 据 挖 掘446.4.1 多维关联规则n单维规则：购买（X，”desktop computer”） 购买（X，”b/w printer”）n多维关联规则: 2 维或谓词n维间

17、关联规则（没有重复的谓词）年龄（X，”19-25”） 职业（X，“学生”） 购买（X， “可乐”）n混合维关联规则（有重复出现的谓词）年龄（X，”19-25”） 购买（X，”爆米花”） 购买（X，”可乐”）n单维关联规则挖掘：搜索频繁项集n多维关联规则挖掘：搜索频繁谓词集n分类属性：具有有限数目的可能取值，值之间无次序关系n量化属性：数值型数据，值之间存在次序关系2022-3-31数 据 挖 掘45对量化属性的处理1. 使用预定义的概念分层将量化属性离散化（静态离散化）2. 根据数据的分布，将量化属性离散化到“箱”（动态离散化）3. 基于数据点之间的距离将量化属性离散化（使用聚类方法）2022

18、-3-31数 据 挖 掘466.4.2 使用量化属性的静态离散化挖掘多维关联规则n在挖掘前，使用概念层次将属性离散化n数值型属性的取值用取值区间表示n在关系数据库中，找出所有 k-谓词频繁集需要 k 或 k+1次扫描n数据立方体适合于关联规则挖掘nn-维立方体中的节点表示谓词集 n在数据立方体上挖掘可以 减少挖掘所需时间(收入)(年龄)()(购买)(年龄，收入)(年龄，购买) (收入，购买)(年龄，收入，购买)2022-3-31数 据 挖 掘476.4.3 挖掘量化关联规则n分箱：n等宽分箱n等深分箱n基于同质的分箱n找频繁谓词集n关联规则聚类2022-3-31数 据 挖 掘486.4.4 挖

19、掘基于距离的关联规则n考虑数据点之间或区间之间的相对距离，紧扣区间数据的语义，并允许数据值的近似n两遍算法：n使用聚类找出区间或簇n搜索频繁地一起出现的簇的集合，得到基于距离的关联规则2022-3-31数 据 挖 掘49挖掘大型数据库中的关联规则n6.1 关联规则挖掘n6.2 由事务数据库挖掘单维布尔关联规则n6.3 由事务数据库挖掘多层关联规则n6.4 由关系数据库和数据仓库挖掘多维关联规则n6.5 由关联挖掘到相关分析n6.6 基于约束的关联挖掘n6.7 小结2022-3-31数 据 挖 掘506.5.1 强关联规则不一定是有趣的n打篮球 吃谷类食品 40%, 66.7% 产生误导n在所有

20、学生中，有 75% 吃谷类食品，高于 66.7%。n打篮球 不吃谷类食品 20%, 33.3% 更为准确，尽管它的支持度与置信度都很低n规则 A B 的置信度有一定的欺骗性，它只给出了A，B的条件概率估计，并没有度量A和B之间的相关性。2022-3-31数 据 挖 掘516.5.2 由关联分析到相关分析n事件之间相关性的度量： corr打篮球不打篮球总和吃谷类食品200017503750不吃谷类食品10002501250总和300020005000()( |)( ) ( )( )ABP A BP B AcorrP A P BP B2022-3-31数 据 挖 掘52挖掘大型数据库中的关联规则n

21、6.1 关联规则挖掘n6.2 由事务数据库挖掘单维布尔关联规则n6.3 由事务数据库挖掘多层关联规则n6.4 由关系数据库和数据仓库挖掘多维关联规则n6.5 由关联挖掘到相关分析n6.6 基于约束的关联挖掘n6.7 小结2022-3-31数 据 挖 掘536.6 基于约束的关联挖掘n自动找到数据库中的所有模式 不现实！n模式数目可能非常大，但大部分是不需要的n数据挖掘应该是一个交互式过程n用户使用数据挖掘查询语言或图形用户界面指导挖掘过程n基于约束的挖掘n用户：给出约束或指明需要挖掘什么n系统优化：利用约束进行有效挖掘基于约束的挖掘2022-3-31数 据 挖 掘546.6 基于约束的关联挖掘

22、n知识类型约束： n指定要挖掘的知识类型，如分类模型，关联规则，等等n数据约束n指定与任务相关的数据集n维/层约束n指定所用的维或概念分层结构中的层n规则约束n指定要挖掘的规则形式，如规则前件或后件中谓词的个数n兴趣度约束n指定规则兴趣度阈值或统计度量，如支持度阈值与置信度阈值2022-3-31数 据 挖 掘556.6.1 关联规则的元规则制导挖掘n元规则使得用户可以说明他们感兴趣的规则的语法形式n例子：n元规则：n与元规则匹配的规则：) ,(),(),(21softwareleducationaXbuysWXPYXP) ,()60.41 ,()39.30 ,(softwareleducati

23、onaXbuysKKXincomeXage2022-3-31数 据 挖 掘566.6.2 用附加的规则约束制导的挖掘n规则约束n反单调的n单调的n简洁的n可转变的n不可转变的2022-3-31数 据 挖 掘57反单调约束n反单调性n若项集 S 不满足约束，那么它的所有超集都不满足约束n求和(S.价格) v 是反单调的n求和(S.价格) v 不是反单调的n例子：约束C：求和(S.价格) 15 是反单调的n项集 ab 不满足 Cnab的任何超集也不满足CTID事务事务10a, b, c, d, f20b, c, d, f, g, h30a, c, d, e, f40c, e, f, g事务数据库

24、(min_sup=2)项项价格价格a40b10c20d10e30f30g20h102022-3-31数 据 挖 掘58单调约束n单调性n若项集 S 满足约束，则它的任意超集都满足约束n求和(S.价格) v 是单调的n最小(S.价格) v 是单调的n例子：约束C：求和(S.价格) 15n项集 ab 满足 Cnab的所有超集都满足CTID事务事务10a, b, c, d, f20b, c, d, f, g, h30a, c, d, e, f40c, e, f, g事务数据库 (min_sup=2)项项价格价格a40b10c20d10e30f30g20h102022-3-31数 据 挖 掘59简洁性

25、约束n简洁性：n设 A1 为满足简洁性约束C 的项的集合，则所有满足 C 的集 S 都是基于A1的，即 S 必包含一个属于 A1 的子集n可以直接精确地产生满足简洁性约束的项集集合 n最小(S.价格) v 是简洁的n和(S.价格) v 不是简洁的2022-3-31数 据 挖 掘60例子Apriori 算法TID项100 1 3 4200 2 3 5300 1 2 3 5400 2 5数据库 D项集支持度计数1223334153项集 支持度计数12233353扫描 DC1L1项集1 21 31 52 32 53 5项集 支持度计数1 211 321 512 322 533 52项集 支持度计数1

26、 322 322 533 52L2C2C2扫描 DC3L3项集2 3 5扫描 D项集支持度计数2 3 522022-3-31数 据 挖 掘61Apriori + 约束 TID项100 1 3 4200 2 3 5300 1 2 3 5400 2 5数据库 D项集 支持度计数1223334153项集支持度计数12233353扫描 DC1L1项集1 21 31 52 32 53 5项集支持度计数1 211 321 512 322 533 52项集支持度计数1 322 322 533 52L2C2C2扫描 DC3L3项集2 3 5扫描 D项集支持度计数2 3 52约束：约束：求和求和S.价格价格 52022-3-31数 据 挖 掘62基于约束的Apriori算法：集成反单调约束TID项100 1 3 4200 2 3 5300 1 2 3 5400 2 5数据库 D项集 支持度计数1223334153项集 支持度计数12233353扫描 DC1L1项集