- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
P( A B) confidence A B) P( B | A) ( P( A)
由于在实际应用中，概率P一般是无法事先给出的，所以常以频率代替。
占购买A的客户人数的百分比称为规则的置信度。
二、寻找强关联规则
例题2：计算下面规则的支持度与置信度。
（1）{面包} {牛奶}
（2）{牛奶} {面包}
第二步：构造关联规则。
四、 Apriori算法的典型应用
潜在强关联规 则
{a} {c} {c} {a} {b} {c}
置信度
是否为强关联 规则
Yes No No
1 0.67 0.67
给该超市的建议: 请将商品b和e的捆绑销售或就近 安排货架!
{c} {b}
{b} {e} {e} {b}
{a,b} {a,c} {a,e} {b,c} {b,e}
{c,e}
0.5
交易号
商品
1
a,c,d
b,c,e a,b,c,e b,e
step3: 在频繁L2基础上 求L3
L2 {a,c} {b,c} {b,e} {c,e} 支持度 0.5 0.5 0.75 0.5
2 3 4
连接L2* L2得到 {a,b,c},{a,c,e},{b,c,e} 剪枝，从而得到潜在的C3 {b,c,e}
0.6
0.4 0.8 0.2 0.6 0.4 0.2
3 4 5
1 0 0
1 1 0
1 1 0
2：寻找频繁（强）关联规则——高频的购物模式 如买牛奶的必然买面包。
9.1 Apriori算法
例：某超市销售数据
当数据量大时，必须引入有效算法
Apriori算法完成： 1. 寻找频繁项集； 受欢迎的商品。
ID 1 2 3 4 5
（3）{鸡蛋} {奶酪}
ID 1 2 3 4 5
牛奶 奶酪 鸡蛋 面包 1 0 0 1 1 1 0 0 1 1 0 1 0 1 0 0 1 1 1 0
二、寻找强关联规则
ID 1 2 3
4
牛奶 1 1 1
0
奶酪 0 1 1
0
鸡蛋 0 0 1
0
面包 1 1 1
1
{面包} {牛奶} (60%, 75%) {牛奶} {面包} (60%, 100%)
0.67
1 1
No
Yes Yes
成功案例：神奇的购物篮分析
《啤酒与尿布:神奇的购物篮分析》的故事 是营销届的神话，“啤酒”和“尿布”两个 看上去没有关系的商品摆放在一起进行销售、 并获得了很好的销售收益，这种现象就是卖 场中商品之间的关联性，研究“啤酒与尿布” 关联的方法就是购物篮分析，购物篮分析是 沃尔玛秘而不宣的独门武器，购物篮分析可 以帮助我们在门店的销售过程中找到具有关 联关系的商品，并以此获得销售收益的增长！
因此所有的频繁项集为： {a},{b},{c},{e},{a,c},{b,c},{b,e},{c,e},{b,c,e }
Apriori算法寻找频繁项集的步骤——受欢迎的商品或商品组合。
潜在1-项集C1 频繁1-项集L1 连接 潜在2-项集C1 频繁2-项集L2
连接
剪枝
潜在3-项集C3
频繁3-项集L3
商品
二、寻找强关联规则
例题3：同例题1的数据。
解：
step1.所有的频繁项集为：
{a},{b},{c},{e},{a,c}, {b,c},{b,e},{c,e},{b,c,e}
2 3 4
设minS=50%，minC=80%，利用Apriori算法求所有的强关联规则。
潜在强关联规则 {a} {c} {c} {a} {b} {c}
置信度 1 0.67 0.67 0.67 1 1
是否为强关联规 则 Yes No No No Yes Yes
step2. 由频繁项集产生 关联规则如表：
{c} {b} {b} {e} {e} {b}
三、 Apriori算法的步骤
Apriori算法是一种寻找强关联规则的算法 Apriori算法具体步骤: 第一步：产生频繁项集
9.1 Apriori算法
如前所述，m种商品的非空项集有2m-1个， 计算量爆炸性增长。 频繁项集的性质：
性质1：频繁项集的子集必为频繁项集； 性质2：非频繁项集的超集必为非频繁项集。
先找频繁项集；然后再找频繁规则
9.1 Apriori算法
一、寻找频繁项集
例题1：设有项集T={a,b,c,d,e}所示的简单交易数 据库，设minS=50%，求所有的频繁项集。 商品 交 解： 易 step1:潜在的频繁1-项集C1为 号 {a}，{b}，{c}，{d}，{e} 1 a,c,d 由最小支持度可以得到频繁1-项集L1 2 b,c,e {a}，{b}，{c}， {e}
.。。。
二、寻找强关联规则
关联规则：形式上为
前项 后项
A B (规则支持度，规则置信度)
支持度(Support)：同时购买A和B的客户人数占总
客户数的百分比称为规则的支持度。
support ( A 和B的客户人数
P( B)
L: <1，负相关 =1，A和B是独立的 >1，正相关，每一个出现蕴涵另一个出现
p({游戏})=0.6 ，p({影碟机})=0.75，p({游戏,影碟机})=0.4
L=0.4/0.6*0.75=0.89<1 负相关，规则无意义！
小结：
基本概念：频繁项集、关联规则、支持度、置信度
Apriori算法:(1) 寻找频繁项集; (2) 构造关联规则 (通过支持度、置信度、提升度得到有实用性的强 关联规则)。
Apriori算法是一种寻找强关联规则的算法 Apriori算法具体步骤: 第一步：产生频繁项集
第二步：构造关联规则。
附：关联规则的相关分析
强关联规则不一定有正确的指导意义！ 例：在10000个交易中，6000个顾客交易包含计 算机游戏，7500个顾客交易包含影碟机，4000个 交易包含计算机游戏和影碟机。
第9章 探索内部结构：Clementine的关联分析
信息与计算科学专业2010本科
曹慧荣
第9章 探索内部结构：Clementine的关联分析
主要方法有：
Apriori算法 GRI算法 序列关联算法
9.1 Apriori算法 内容安排：
引例 Apriori算法
Step2:给出强关联规则。
牛奶 鸡蛋 面包 1 1 1 0 0 0 0 1 1 0 1 1 1 1 0
2.寻找频繁（强）的关联规则。 高频的购物模式。
9.1 Apriori算法
一、寻找频繁项集
K-项集：包含K个项的集合。
频繁项集：所有支持度大于等于最小支持 度的项集。 频繁项集的寻找： 如果有m种商品，则只要计算所有非空 项集的支持度，大于等于最小支持度的即 为频繁项集。
3
4
a,b,c,e
b,e
交易 号 1 a,c,d b,c,e
商品
step2: 在频繁L1基础上 求L2
L1 {a} {b} {c} {e} 支持度 0.5 0.75 0.75 0.75 C2
2 3 4
支持度 0.25 0. 5 0.25 0.5 0.75
a,b,c,e b,e
连接L1* L1 得到潜在C2
Step1:寻找频繁项集;
Apriori算法的典型应用
9.1 Apriori算法
引例：某超市销售数据
1：寻找频繁项集——受欢迎的商品或商品组合。 项：商品；项集：商品的集合。
项集 支持度
ID
1 2
牛奶 鸡蛋 面包
1 1 0 0 1 1
{牛奶}
{鸡蛋} {面包} {牛奶，鸡蛋} {牛奶，面包} {鸡蛋，面包} {牛奶，鸡蛋，面包}
本算法可以做课程论文的相关题目：
1、关联规则中基本概念的意义 （1）支持度 （2）置信度 （3）提升度 2、基于***数据的关联规则分析
收集数据，寻找强关联规则 3、序列关联规则
二、寻找强关联规则
A B (规则支持度，规则置信度)
一个好的规则应该有比较高的支持度和置信 度． 如果满足最小支持度阈值和最小置信度阈值， 则称这个规则为强规则。 我们的目的就是找出强关联规则。 由频繁项集可以产生潜在的强关联规则
交易号 1 a,c,d b,c,e a,b,c,e b,e
buys( x, "计算机游戏 ) buys( x, "影碟机" )[支持度 40%, 置信度 66%] "
规则其实是误导，因为购买影碟机的可能性是75%， 比66%还大。事实是：计算机游戏和影碟机是负相 关的。
附：关联规则的相关分析
关联规则实用性的测度指标 P ( B | A) 规则 A B 提升度L=
{鸡蛋} {奶酪} (20%, 100%)
5
0
1
0
0
A B (规则支持度，规则置信度)
思考：（1）规则支持度小，规则置信度大，说明什么现象？ 如1000个人中只有一个人购买了烤炉，又购买了碳，所以 {烤炉} {碳} (0.1%, 100%) （应用机会少） （2）规则支持度大，规则置信度小，说明什么现象？
