《数据挖掘6章关联优秀课件》由会员分享，可在线阅读，更多相关《数据挖掘6章关联优秀课件（50页珍藏版）》请在金锄头文库上搜索。
1、第第6章：挖掘大型数据库中的关章：挖掘大型数据库中的关联规则联规则n6.1 关联规则挖掘关联规则挖掘n6.2由事务数据库挖掘单维布尔关联规则由事务数据库挖掘单维布尔关联规则n6.3由事务数据库挖掘多层关联规则由事务数据库挖掘多层关联规则n6.4由关系数据库和数据仓库挖掘多维关联规则由关系数据库和数据仓库挖掘多维关联规则n6.5由关联挖掘到相关性分析由关联挖掘到相关性分析n6.6基于约束的关联挖掘基于约束的关联挖掘n6.7小结小结2024/7/251数据挖掘6章关联优秀什么是关联挖掘什么是关联挖掘?n关联规则挖掘：关联规则挖掘：n在交易数据、关系数据或其他信息载体中，查找存在于在交易数据、关系数
2、据或其他信息载体中，查找存在于项目集合或对象集合之间的频繁模式、关联、相关性、项目集合或对象集合之间的频繁模式、关联、相关性、或因果结构。或因果结构。n应用：应用：n购物篮分析购物篮分析、交叉销售、产品目录设计交叉销售、产品目录设计、 loss-leader analysis、聚集、分类等。聚集、分类等。n举例：举例： n规则形式：规则形式： “Body H Head support, confidence”.nbuys(x, “diapers”) buys(x, “beers”) 0.5%, 60%nmajor(x, “CS”) takes(x, “DB”) grade(x, “A”) 1%
3、, 75%2024/7/252数据挖掘6章关联优秀关联规则：基本概念关联规则：基本概念n给定给定: (1)交易数据库交易数据库 (2)每笔交易是每笔交易是：一个项目列表一个项目列表 (消费消费者一次购买活动中购买的商品者一次购买活动中购买的商品)n查找查找: 所有所有描述一个项目集合与其他项目集合相关性的规则描述一个项目集合与其他项目集合相关性的规则nE.g., 98% of people who purchase tires and auto accessories also get automotive services donen应用应用n* 护理用品护理用品 (商店应该怎样提高护理用品
4、的销售？商店应该怎样提高护理用品的销售？)n家用电器家用电器 * (其他商品的库存有什么影响其他商品的库存有什么影响?)n在产品直销中使用在产品直销中使用附加邮寄附加邮寄2024/7/253数据挖掘6章关联优秀规则度量：支持度与可信度规则度量：支持度与可信度n查找所有的规则查找所有的规则 X & Y Z 具有最小支持度和可信度具有最小支持度和可信度n支持度支持度, s, 一次交易中包含一次交易中包含X 、 Y 、 Z的的可能性可能性n置信度置信度, c, 包含包含X 、 Y的的交易中也包含交易中也包含Z的的条件概率条件概率设最小支持度为设最小支持度为50%, 最小可信最小可信度为度为 50%,
5、 则可得到则可得到nA C (50%, 66.6%)nC A (50%, 100%)买尿布的客买尿布的客户户二者都买二者都买的客户的客户买啤酒的客户买啤酒的客户2024/7/254数据挖掘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单维单
6、维 vs. 多维多维 关联关联 (基于规则中涉及的数据维基于规则中涉及的数据维)(例子同上例子同上)n单层单层 vs. 多层多层 分析分析(基于规则集所涉及的抽象层基于规则集所涉及的抽象层)n那个品种牌子的啤酒与那个牌子的尿布有关系那个品种牌子的啤酒与那个牌子的尿布有关系?n各种扩展各种扩展n相关性、因果分析相关性、因果分析n关联并不一定意味着相关或因果关联并不一定意味着相关或因果n最大模式和闭合项集最大模式和闭合项集2024/7/255数据挖掘6章关联优秀第第6章：从大数据库中挖掘关联章：从大数据库中挖掘关联规则规则n6.1 关联规则挖掘关联规则挖掘n6.2由事务数据库挖掘单维布尔关联规则由
7、事务数据库挖掘单维布尔关联规则n6.3由事务数据库挖掘多层关联规则由事务数据库挖掘多层关联规则n6.4由关系数据库和数据仓库挖掘多维关联规则由关系数据库和数据仓库挖掘多维关联规则n6.5由关联挖掘到相关性分析由关联挖掘到相关性分析n6.6基于约束的关联挖掘基于约束的关联挖掘n6.7小结小结2024/7/256数据挖掘6章关联优秀关联规则挖掘关联规则挖掘一个例子一个例子对于对于 A C：support = support(A 、C) = 50%confidence = support(A 、C)/support(A) = 66.6%Apriori的基本思想的基本思想:频繁项集的任何子集也一定是频
8、繁的频繁项集的任何子集也一定是频繁的最小值尺度 50%最小可信度 50%2024/7/257数据挖掘6章关联优秀关键步骤：挖掘频繁集关键步骤：挖掘频繁集n频繁集频繁集:是指满足最小支持度的项目集合是指满足最小支持度的项目集合n频繁集的子集也一定是频繁的频繁集的子集也一定是频繁的n如如, 如果如果AB 是频繁集，则是频繁集，则 A B 也一定是也一定是频繁集频繁集n从从1到到k（k-频繁集）递归查找频繁集频繁集）递归查找频繁集n用得到的频繁集生成关联规则用得到的频繁集生成关联规则2024/7/258数据挖掘6章关联优秀Apriori算法算法n连接连接: 用用 Lk-1自连接得到候选自连接得到候选
9、k-项集项集Ckn修剪修剪: 一个一个k-项集，如果他的一个项集，如果他的一个k-1项集（他的子集项集（他的子集 ）不是频繁的，那他本身也不可能是频繁的。不是频繁的，那他本身也不可能是频繁的。n伪代码伪代码:Ck: Candidate itemset of size kLk : frequent itemset of size kL1 = frequent items;for (k = 2; Lk-1 !=; k+) do begin Ck = candidates generated from Lk-1; for each transaction t in database do incre
10、ment the count of all candidates in Ck that are contained in t Lk = candidates in Ck with min_support endreturn k Lk;2024/7/259数据挖掘6章关联优秀Apriori算法算法 例子例子数据库 D扫描 DC1L1L2C2C2扫描 DC3L3扫描 D2024/7/2510数据挖掘6章关联优秀如何生成候选集如何生成候选集n假定假定 Lk-1 中的项按顺序排列中的项按顺序排列n第一步第一步: 自连接自连接 Lk-1 insert into Ckselect p.item1, p.i
11、tem2, , 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第二步第二步: 修剪修剪For all itemsets c in Ck doFor all (k-1)-subsets s of c doif (s is not in Lk-1) then delete c from Ck2024/7/2511数据挖掘6章关联优秀n计算支持度为什么会成为一个问题计算支持度为什么会成为一个问题？n候选集的个数非常巨大候选集的个数非常巨大
12、n 一笔交易可能包含多个候选集一笔交易可能包含多个候选集2024/7/2512数据挖掘6章关联优秀生成候选集的例子生成候选集的例子nL3=abc, abd, acd, ace, bcdn自连接自连接 : L3*L3nabc 和和 abd 得到得到 abcd nacd 和和 ace 得到得到 acden修剪修剪:nade 不在不在 L3中，删除中，删除 acdenC4=abcd2024/7/2513数据挖掘6章关联优秀提高提高Apriori效率的方法效率的方法1.基于基于Hash的项集计数的项集计数: 若若 k-项集在项集在hash-tree的路径上的一个计的路径上的一个计数值低于阈值，那他本身
13、也不可能是频繁的。数值低于阈值，那他本身也不可能是频繁的。(157页图页图6-6)2.减少交易记录减少交易记录: 不包含任何频繁不包含任何频繁k-项集的交易也不可能包含任何项集的交易也不可能包含任何大于大于k的频繁集，下一步计算时删除这些记录。的频繁集，下一步计算时删除这些记录。3.划分划分: 一个项集要想在整个数据库中是频繁的，那么他至少在数一个项集要想在整个数据库中是频繁的，那么他至少在数据库的一个分割上是频繁的。据库的一个分割上是频繁的。 两次扫描数据。两次扫描数据。(157页图页图5-6)4.抽样抽样: 使用小的支持度使用小的支持度+完整性验证方法。在小的抽样集上找到完整性验证方法。在
14、小的抽样集上找到局部频繁项集，然后在全部数据集找频繁项集。局部频繁项集，然后在全部数据集找频繁项集。5.动态项集计数动态项集计数: 在添加一个新的候选集之前，先估计一下是不是在添加一个新的候选集之前，先估计一下是不是他的所有子集都是频繁的。他的所有子集都是频繁的。2024/7/2514数据挖掘6章关联优秀Apriori 够快了吗够快了吗? 性能瓶颈性能瓶颈nApriori算法的核心算法的核心:n用频繁的用频繁的(k 1)-项集生成项集生成候选候选的频繁的频繁 k-项集项集n用数据库扫描和模式匹配计算候选集的支持度用数据库扫描和模式匹配计算候选集的支持度nApriori 的瓶颈的瓶颈: 候选集生
15、成候选集生成n巨大的候选集巨大的候选集:n104 个频繁个频繁1-项集要生成项集要生成 107 个候选个候选 2-项集项集n要找尺寸为要找尺寸为100的频繁模式，如的频繁模式，如 a1, a2, , a100, 你必须先产生你必须先产生2100 1030 个候选集个候选集n多次扫描数据库多次扫描数据库： n如果最长的模式是如果最长的模式是n的话，则需要的话，则需要 (n +1 ) 次数据库次数据库扫描扫描2024/7/2515数据挖掘6章关联优秀挖掘频繁集挖掘频繁集 不用生成候选集不用生成候选集n频繁模式增长频繁模式增长 (FP-增长增长)用用Frequent-Pattern tree (FP
16、-tree) 结构压缩数据库结构压缩数据库, n高度浓缩，同时对频繁集的挖掘又完备的高度浓缩，同时对频繁集的挖掘又完备的n避免代价较高的数据库扫描避免代价较高的数据库扫描 开发一种高效的基于开发一种高效的基于FP-tree的频繁集挖掘算法的频繁集挖掘算法n采用分而治之的方法学：分解数据挖掘任务为采用分而治之的方法学：分解数据挖掘任务为小任务小任务n避免生成关联规则避免生成关联规则: 分别挖掘条件数据库分别挖掘条件数据库2024/7/2516数据挖掘6章关联优秀用用 FP-tree挖掘频繁集挖掘频繁集n基本思想基本思想 (分而治之分而治之)n用用FP-tree地归增长频繁集地归增长频繁集n方法方
17、法 n对每个项，生成它的对每个项，生成它的 条件模式库条件模式库, 然后是它的然后是它的 条件条件 FP-treen对每个新生成的条件对每个新生成的条件FP-tree，重复这个步骤重复这个步骤n直到结果直到结果FP-tree为为空空, 或只含或只含维一的一个路径维一的一个路径 (此路径的每个子路径对应的相集都是频繁集此路径的每个子路径对应的相集都是频繁集)2024/7/2517数据挖掘6章关联优秀挖掘挖掘 FP-tree的主要步骤的主要步骤1)为为FP-tree中的每个节点生成条件模式库中的每个节点生成条件模式库2)用条件模式库构造对应的条件用条件模式库构造对应的条件FP-tree3)递归构造
18、条件递归构造条件 FP-trees 同时增长其包含的频繁同时增长其包含的频繁集集如果条件如果条件FP-tree直包含一个路径，则直接生直包含一个路径，则直接生成所包含的频繁集。成所包含的频繁集。2024/7/2518数据挖掘6章关联优秀步骤步骤1: 1: 建立建立 FP-tree FP-tree （159159页图页图6-86-8）n从从FP-tree的头表开始的头表开始n按照每个频繁项的连接遍历按照每个频繁项的连接遍历 FP-treen列出能够到达此项的所有前缀路径，得到条件模式库列出能够到达此项的所有前缀路径，得到条件模式库步骤步骤2:2:建立条件建立条件FP-treeFP-tree进行挖
19、掘（进行挖掘（159159页图页图6-96-9）n对每个模式库对每个模式库n计算库中每个项的支持度计算库中每个项的支持度n用模式库中的频繁项建立用模式库中的频繁项建立FP-tree2024/7/2519数据挖掘6章关联优秀为什么为什么 频繁集增长频繁集增长 速度快？速度快？n我们的性能研究显示我们的性能研究显示nFP-growth 比比Apriori快一个数量级快一个数量级, 同样也比同样也比 tree-projection 快。快。n原因原因n不生成候选集，不用候选测试。不生成候选集，不用候选测试。n使用紧缩的数据结构使用紧缩的数据结构n避免重复数据库扫描避免重复数据库扫描n基本操作是计数和
20、建立基本操作是计数和建立 FP-tree 树树2024/7/2520数据挖掘6章关联优秀FP-growth vs. Apriori: 相对于支持度的相对于支持度的扩展性扩展性Data set T25I20D10K2024/7/2521数据挖掘6章关联优秀FP-growth vs. Tree-Projection:相对于相对于支持度的扩展性支持度的扩展性Data set T25I20D100K2024/7/2522数据挖掘6章关联优秀关联规则结果显示关联规则结果显示 (Table Form )2024/7/2523数据挖掘6章关联优秀关联规则可视化关联规则可视化Using Plane Graph
21、2024/7/2524数据挖掘6章关联优秀关联规则可视化关联规则可视化Using Rule Graph2024/7/2525数据挖掘6章关联优秀第6章：从大数据库中挖掘关联规则n6.1 关联规则挖掘关联规则挖掘n6.2由事务数据库挖掘单维布尔关联规则由事务数据库挖掘单维布尔关联规则n6.3由事务数据库挖掘多层关联规则由事务数据库挖掘多层关联规则n6.4由关系数据库和数据仓库挖掘多维关联规则由关系数据库和数据仓库挖掘多维关联规则n6.5由关联挖掘到相关性分析由关联挖掘到相关性分析n6.6基于约束的关联挖掘基于约束的关联挖掘n6.7小结小结2024/7/2526数据挖掘6章关联优秀多层关联规则多层
22、关联规则n项通常具有层次项通常具有层次n底层的项通常支持度也低底层的项通常支持度也低n某些特定层的规则可能更某些特定层的规则可能更有意义有意义n交易数据库可以按照维或交易数据库可以按照维或层编码层编码n可以进行共享的多维挖掘可以进行共享的多维挖掘食品面包牛奶脱脂奶光明统一酸奶白黄2024/7/2527数据挖掘6章关联优秀挖掘多层关联规则挖掘多层关联规则n自上而下，深度优先的方法：自上而下，深度优先的方法：n先找高层的先找高层的“强强”规则：规则：牛奶牛奶 面包面包 20%, 60%. 20%, 60%.n再找他们底层的再找他们底层的“弱弱”规则：规则：酸奶酸奶 黄面包黄面包 6%, 50%.
23、6%, 50%.n多层关联规则的变种多层关联规则的变种1 1 支持度不变支持度不变: : 在各层之间使用统一的支持度在各层之间使用统一的支持度n+ + 一个最小支持度阈值一个最小支持度阈值. . 如果一个项集的父项集不具有最如果一个项集的父项集不具有最小支持度，那他本身也不可能满足最小支持度。小支持度，那他本身也不可能满足最小支持度。n 底层项不会成为频繁集，如果支持度底层项不会成为频繁集，如果支持度n太高太高 丢失底层关联规则丢失底层关联规则n太低太低 生成太多的高层关联规则生成太多的高层关联规则2 2 支持度递减支持度递减: : 随着层次的降低支持度递减随着层次的降低支持度递减2024/7
24、/2528数据挖掘6章关联优秀多层关联规则多层关联规则: 支持度不变支持度不变 vs. 支持度支持度递减递减3层次交叉单项过滤层次交叉单项过滤： 4层次交叉层次交叉K-项过滤项过滤：n4种搜索策略：种搜索策略：n层与层独立层与层独立n用用k-项集跨层过滤项集跨层过滤n用项跨层过滤用项跨层过滤n用项进行可控跨层过滤用项进行可控跨层过滤2024/7/2529数据挖掘6章关联优秀支持度不变支持度不变支持度不变多层挖掘支持度不变多层挖掘牛奶牛奶support = 10%酸奶酸奶 support = 6%脱脂奶脱脂奶support = 4%层层 1min_sup = 5%层层 2min_sup = 5%
25、2024/7/2530数据挖掘6章关联优秀支持度递减支持度递减支持度递减多层挖掘支持度递减多层挖掘酸奶酸奶 support = 6%脱脂奶脱脂奶 support = 4%层层 1min_sup = 5%层层 2min_sup = 3%牛奶牛奶support = 10%2024/7/2531数据挖掘6章关联优秀多层关联：冗余过滤n由于由于“祖先祖先”关系的原因，有些规则可能是多余的。关系的原因，有些规则可能是多余的。n例子例子n奶制品奶制品 白面包白面包 support = 8%, confidence = 70%n酸奶酸奶 白面包白面包 support = 2%, confidence = 7
26、2%n酸奶占酸奶占奶制品奶制品25%n我们称第一个规则是第二个规则的祖先我们称第一个规则是第二个规则的祖先n参考规则的祖先，如果他的支持度与我们参考规则的祖先，如果他的支持度与我们“预期预期”的支持度的支持度近似的话，我们就说这条规则是冗余的。近似的话，我们就说这条规则是冗余的。2024/7/2532数据挖掘6章关联优秀数据挖掘查询的逐步精化数据挖掘查询的逐步精化n为什么要逐步精化为什么要逐步精化n挖掘操作的代价可能高或低，结果可能过细致或粗糙挖掘操作的代价可能高或低，结果可能过细致或粗糙n在速度和质量之间折衷：逐步精化在速度和质量之间折衷：逐步精化n超集覆盖特征超集覆盖特征：n预存储所有正面
27、答案预存储所有正面答案允许进一步正确性验证，而不必允许进一步正确性验证，而不必验证已经错误的验证已经错误的n2或多步挖掘：或多步挖掘：n先执行粗糙的、容易的操作先执行粗糙的、容易的操作 (超集覆盖超集覆盖)n然后在减少后的候选集上进行计算量大的算法然后在减少后的候选集上进行计算量大的算法 (Koperski & Han, SSD95).2024/7/2533数据挖掘6章关联优秀第6章：从大数据库中挖掘关联规则n6.1 关联规则挖掘关联规则挖掘n6.2由事务数据库挖掘单维布尔关联规则由事务数据库挖掘单维布尔关联规则n6.3由事务数据库挖掘多层关联规则由事务数据库挖掘多层关联规则n6.4由关系数据
28、库和数据仓库挖掘多维关联规则由关系数据库和数据仓库挖掘多维关联规则n6.5由关联挖掘到相关性分析由关联挖掘到相关性分析n6.6基于约束的关联挖掘基于约束的关联挖掘n6.7小结小结2024/7/2534数据挖掘6章关联优秀多维关联规则：多维关联规则： 概念概念n单维规则：单维规则：buys(X, “milk”) buys(X, “bread”)n多维规则：多维规则： 2个以上维个以上维/谓词谓词n维间关联规则维间关联规则 (维词维词不重复不重复)age(X,”19-25”) occupation(X,“student”) buys(X,“coke”)n混合维关联规则混合维关联规则 (维词重复维词
29、重复)age(X,”19-25”) buys(X, “popcorn”) buys(X, “coke”)n类别属性类别属性n有限个值有限个值, 值之间无顺序关系值之间无顺序关系n数量属性数量属性n数字的，值之间隐含了顺序关系数字的，值之间隐含了顺序关系2024/7/2535数据挖掘6章关联优秀挖掘多维关联的技术挖掘多维关联的技术n搜索频繁搜索频繁k-维词集合维词集合：n如如: age, occupation, buys 是一个是一个3-维词集合。维词集合。n按照对按照对 age 处理方式的不同，分为：处理方式的不同，分为：1. 用静态方法把数值属性离散化用静态方法把数值属性离散化n数值属性可用
30、预定义的概念层次加以离散化数值属性可用预定义的概念层次加以离散化。2. 带数量的关联规则带数量的关联规则n根据数据的分布，动态的把数值属性离散化到不同的根据数据的分布，动态的把数值属性离散化到不同的“箱箱”。3. 基于距离的关联规则基于距离的关联规则n用数据点之间的距离动态的离散化用数据点之间的距离动态的离散化2024/7/2536数据挖掘6章关联优秀数值属性的静态离散化数值属性的静态离散化n在挖掘之前用概念层次先离散化在挖掘之前用概念层次先离散化n数值被替换为区间范围数值被替换为区间范围n关系数据库中，要找到所有频繁关系数据库中，要找到所有频繁k-维词需要维词需要k或或k+1次表扫次表扫描。
31、描。n适宜使用数据立方体适宜使用数据立方体nN维立方体的每个单元维立方体的每个单元 对应一个维词集合对应一个维词集合n使用数据立方体速度更快使用数据立方体速度更快(income)(age)()(buys)(age, income)(age,buys) (income,buys)(age,income,buys)2024/7/2537数据挖掘6章关联优秀带数量的关联规则带数量的关联规则age(X,”30-34”) income(X,”24K - 48K”) buys(X,”high resolution TV”)n动态动态 离散化数值属性离散化数值属性使满足某种挖掘标准，如最大化挖掘规则的置信度
32、紧凑性使满足某种挖掘标准，如最大化挖掘规则的置信度紧凑性.n2-维数量关联规则：维数量关联规则： Aquan1 Aquan2 Acatn用用2-维表格把维表格把“邻近邻近”的的关联规则组合起来关联规则组合起来n例子例子 2024/7/2538数据挖掘6章关联优秀ARCS (关联规则聚集系统关联规则聚集系统) ARCS 流程流程1. 分箱分箱2. 查找频繁维词查找频繁维词 集合集合3. 关联规则聚类关联规则聚类4. 优化优化2024/7/2539数据挖掘6章关联优秀ARCS的局限性的局限性n数值属性只能出现在规则的左侧数值属性只能出现在规则的左侧n左侧只能有两个属性左侧只能有两个属性 (2维维)
33、nARCS 的改进的改进n不用基于栅格的方法不用基于栅格的方法n等深分箱等深分箱n基于基于局部完整性局部完整性 测度的聚集测度的聚集n“Mining Quantitative Association Rules in Large Relational Tables” by R. Srikant and R. Agrawal.2024/7/2540数据挖掘6章关联优秀挖掘基于距离的关联规则挖掘基于距离的关联规则n分箱的方法没有体现数据间隔的语义分箱的方法没有体现数据间隔的语义n基于距离的分割是更有基于距离的分割是更有“意义意义”的离散化方法，考虑的离散化方法，考虑：n区间内密度或点的个数区间内密
34、度或点的个数n区间内点的区间内点的“紧密程度紧密程度2024/7/2541数据挖掘6章关联优秀第第6章：从大数据库中挖掘关联章：从大数据库中挖掘关联规则规则n6.1 关联规则挖掘关联规则挖掘n6.2由事务数据库挖掘单维布尔关联规则由事务数据库挖掘单维布尔关联规则n6.3由事务数据库挖掘多层关联规则由事务数据库挖掘多层关联规则n6.4由关系数据库和数据仓库挖掘多维关联规则由关系数据库和数据仓库挖掘多维关联规则n6.5由关联挖掘到相关性分析由关联挖掘到相关性分析n6.6基于约束的关联挖掘基于约束的关联挖掘n6.7小结小结2024/7/2542数据挖掘6章关联优秀n强关联规则不一定是有趣的（强关联规
35、则不一定是有趣的（168页例页例5.8）n由关联分析到相关分析由关联分析到相关分析 项集项集A与项集与项集B独立独立 P(AB)=P(A)P(B) 项集项集A、B的相关性的相关性 corrAB=P(AB)/P(A)P(B) 2024/7/2543数据挖掘6章关联优秀第第6章：从大数据库中挖掘关联章：从大数据库中挖掘关联规则规则n6.1 关联规则挖掘关联规则挖掘n6.2由事务数据库挖掘单维布尔关联规则由事务数据库挖掘单维布尔关联规则n6.3由事务数据库挖掘多层关联规则由事务数据库挖掘多层关联规则n6.4由关系数据库和数据仓库挖掘多维关联规则由关系数据库和数据仓库挖掘多维关联规则n6.5由关联挖掘
36、到相关性分析由关联挖掘到相关性分析n6.6基于约束的关联挖掘基于约束的关联挖掘n6.7小结小结2024/7/2544数据挖掘6章关联优秀6.6.1 基于约束的挖掘基于约束的挖掘n使用约束的必要性使用约束的必要性n在数据挖掘中常使用的几种约束：在数据挖掘中常使用的几种约束：n知识类型约束：知识类型约束：指定要挖掘的知识类型指定要挖掘的知识类型 如关联规则如关联规则n数据约束：数据约束： 指定与任务相关的数据集指定与任务相关的数据集 nFind product pairs sold together in Vancouver in Dec.98.n维维/层次约束层次约束:指定所用的维或概念结构中的
37、层指定所用的维或概念结构中的层nin relevance to region, price, brand, customer category.n规则约束：规则约束：指定指定要挖掘的规则形式要挖掘的规则形式(如规则模板如规则模板)n单价单价 (price $200).n兴趣度约束：兴趣度约束：指定规则兴趣度阈值或统计度量指定规则兴趣度阈值或统计度量n如如 (min_support 3%, min_confidence 60%).2024/7/2545数据挖掘6章关联优秀n假定假定AllElectronics的一个销售多维数据库有如下关系的一个销售多维数据库有如下关系(176页页)nSales(
38、customer_name,item_name,transaction_id)nLives(customer_name,region,city)nItems(item_name,category，price)nTransaction(transaction_id,day,month,year) (1) mine associations as (2)lives(C,_,”Pudong”)sales(C,I,S)=sales(C,JT) (3) from sales (4)where S.year=1999 &T.year=1999 &I.category=J.category (5)group
39、 by C,I.category (6)having sum(I.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%2024/7/2546数据挖掘6章关联优秀6.6.2 约束的分类约束的分类n单调性约束单调性约束(monotone constraint)n反单调性约束反单调性约束(anti-monotone co
40、nstraint)n可转变的约束可转变的约束(convertibale constraint)n简洁性约束简洁性约束(succinct constraint)n不可转变的约束不可转变的约束(non-convertibale constraint)2024/7/2547数据挖掘6章关联优秀约束的有关概念约束的有关概念n项目集：项目集：I=i1,i2,im,n交易：交易：T=n模式模式S是项目集的子集，是项目集的子集，S=ij1,ij2,ijkn模式模式S包含与包含与T,T=,iff S=It; S是是S的子模式的子模式(subpattern)且且S 是是S的超模式的超模式(superpattern)，if 有有S=v ， v是是S的一个项集的一个项集n约束约束Cm 是是单调的单调的iff.对于任给的满足对于任给的满足Cm的项集的项集(模式模式) S, 每一个每一个S的超集都能够满足的超集都能够满足 Cm e.g: Cm : min(S)=v, v是是S的一个项集的一个项集2024/7/2550数据挖掘6章关联优秀
