浙江大学远程教育学院 DISTANCELEARN I NGSCHOOLOFZHEJI ANGUN I VERS I TY 任课教师:王灿 课程代码:0703004 课程名称:数据挖掘 第13-14讲 教师E-mai:sjwj@dlc.zju.edu.cn
13-14 王 灿 数据挖掘 sjwj@dlc.zju.edu.cn 0703004
大型数据库中的关联规则 挖掘
大型数据库中的关联规则 挖掘
什么是关联规则挖掘? ■关联规则挖掘: 口从事务数据库,关系数据库和其他信息存储中的大 量数据的项集之间发现有趣的、频繁出现的模式、 关联和相关性 应用: ¤购物篮分析、分类设计、捆绑销售等
什么是关联规则挖掘？ ◼ 关联规则挖掘： ❑ 从事务数据库，关系数据库和其他信息存储中的大 量数据的项集之间发现有趣的、频繁出现的模式、 关联和相关性。 ◼ 应用： ❑ 购物篮分析、分类设计、捆绑销售等
尿布与啤酒”—一典型关联分析案例 采用关联模型比较典型的案例是“尿布与啤酒” 的故事。在美国,一些年轻的父亲下班后经常 要到超市去买婴儿尿布,超市也因此发现了 个规律,在购买婴儿尿布的年轻父亲们中,有 30%~40%的人同时要买一些啤酒。超市随后 调整了货架的摆放,把尿布和啤酒放在一起, 明显增加了销售额。同样的,我们还可以根据 关联规则在商品销售方面做各种促销活动
“尿布与啤酒”——典型关联分析案例 ◼ 采用关联模型比较典型的案例是“尿布与啤酒” 的故事。在美国，一些年轻的父亲下班后经常 要到超市去买婴儿尿布，超市也因此发现了一 个规律，在购买婴儿尿布的年轻父亲们中，有 30%～40%的人同时要买一些啤酒。超市随后 调整了货架的摆放，把尿布和啤酒放在一起， 明显增加了销售额。同样的，我们还可以根据 关联规则在商品销售方面做各种促销活动
购物篮分析 如果问题的全域是商店中所有商品的集合,则对每种 商品都可以用一个布尔量来表示该商品是否被顾客购 买,则每个购物篮都可以用一个布尔向量表示;而通 过分析布尔向量则可以得到商品被频繁关联或被同时 购买的模式,这些模式就可以用关联规则表示 (000010,02种方法丢失了什么信息?) ■关联规则的两个兴趣度度量 支持度b10(, computer")→bns(x," software") a置信度 sup port=2%, confidence=60%
购物篮分析 ◼ 如果问题的全域是商店中所有商品的集合，则对每种 商品都可以用一个布尔量来表示该商品是否被顾客购 买，则每个购物篮都可以用一个布尔向量表示；而通 过分析布尔向量则可以得到商品被频繁关联或被同时 购买的模式，这些模式就可以用关联规则表示 （0001001100，这种方法丢失了什么信息？） ◼ 关联规则的两个兴趣度度量 ❑ 支持度 ❑ 置信度 [sup 2%, 60%] ( , " ") ( , " ") = = port confidence buys X computer buys X software
关联规则:基本概念 给定 口项的集合:|=1,i2…, 口任务相关数据D是数据库事务的集合,每个事务7贝 是项的集合,使得TⅠ 口每个事务由事务标识符TD标识; 口A,B为两个项集,事务7包含A当且仅当A∈T 则关联规则是如下蕴涵式: A→B[S,c] 口其中AcI,BcI并且A∩B=Φ,规则A→B在事 务集D中成立,并且具有支持度S和置信度C
关联规则：基本概念 ◼ 给定： ❑ 项的集合：I={i1 ,i2 ,...,in } ❑ 任务相关数据D是数据库事务的集合，每个事务T则 是项的集合，使得 ❑ 每个事务由事务标识符TID标识； ❑ A,B为两个项集，事务T包含A当且仅当 ◼ 则关联规则是如下蕴涵式： ❑ 其中 并且 ，规则 在事 务集D中成立，并且具有支持度s和置信度c T I A T A B [s, c] A I, B I A B = A B
基本概念——示例 项的集合/=A,B,C,D,E,F 每个事务7由事务标识符TD标识,它是项的集合 口比如:T/D(2000)=A,B,C ■任务相关数据D是数据库事务的集合 TID 购买的tem 2000A,BC 1000 AC 4000 A D 5000 B.E.F
基本概念——示例 ◼ 项的集合 I={A,B,C,D,E,F} ◼ 每个事务T由事务标识符TID标识，它是项的集合 ❑ 比如：TID(2000)={A,B,C} ◼ 任务相关数据D是数据库事务的集合 TID 购买的item 2000 A,B,C 1000 A,C 4000 A,D 5000 B,E,F
规则度量:支持度和置信度 Customer Customer buys both 对所有满足最小支持度和 buys diaper 置信度的关联规则 口支持度s是指事务集D中包 含A∪B的百分比 sup por(A→B)=P(A∪B) a置信度c是指D中包含A的事 Customer 务同时也包含B的百分比 uys beer confidence(A→B)=P(B|A)=P(A∪B)/P(A) TD购买的em 假设最小支持度为50%, 2000 A.B.C 最小置信度为50%,则有 1000 A c 如下关联规则 4000AD A→C(50%,66.6% 5000 BEF 日C→A(50%,100%
规则度量：支持度和置信度 TID 购买的item 2000 A,B,C 1000 A,C 4000 A,D 5000 B,E,F Customer buys diaper Customer buys both Customer buys beer ◼ 对所有满足最小支持度和 置信度的关联规则 ❑ 支持度s是指事务集D中包 含 的百分比 ❑ 置信度c是指D中包含A的事 务同时也包含B的百分比 ◼ 假设最小支持度为50%， 最小置信度为50%，则有 如下关联规则 ❑ A C (50%, 66.6%) ❑ C A (50%, 100%) A B sup port(A B) = P(A B) confidence (A B) = P(B | A) = P(A B)/ P(A)
大型数据库关联规则挖掘(1) 基本概念 ak一项集:包含k个项的集合 {牛奶,面包,黄油}是个3-—项集 a项集的频率是指包含项集的事务数 口如果项集的频率大于(最小支持度×D中的事务总 数),则称该项集为频繁项集
大型数据库关联规则挖掘 (1) ◼ 基本概念 ❑ k－项集：包含k个项的集合 ◼ {牛奶，面包，黄油}是个3－项集 ❑ 项集的频率是指包含项集的事务数 ❑ 如果项集的频率大于（最小支持度×D中的事务总 数），则称该项集为频繁项集
大型数据库关联规则挖掘(2) 大型数据库中的关联规则挖掘包含两个过程: 口找出所有频繁项集 大部分的计算都集中在这一步 ¤由频繁项集产生强关联规贝 即满足最小支持度和最小置信度的规则
大型数据库关联规则挖掘 (2) ◼ 大型数据库中的关联规则挖掘包含两个过程： ❑ 找出所有频繁项集 ◼ 大部分的计算都集中在这一步 ❑ 由频繁项集产生强关联规则 ◼ 即满足最小支持度和最小置信度的规则