当前位置:网站首页>关联规则(3)

关联规则(3)

2022-11-24 21:27:13钰涵雨辰

关联规则

1.算法背景

1.1 啤酒和尿布的故事

​ 沃尔玛的 “啤酒与尿布”是营销界经典的案例,该案例是正式刊登在1998年的《哈佛 商业评论》上面的,这应该算是目前发现的最权威报道。 20世纪90年代的美国沃尔玛超市中,沃尔玛的超市管理人员分析销售数据时发现了一 个令人难于理解的现象:在某些特定的情况下,“啤酒”与“尿布”两件看上去毫无关系 的商品会经常出现在同一个购物篮中,这种独特的销售现象引起了管理人员的注意,经过 后续调查发现,这种现象出现在年轻的父亲身上。 在美国有婴儿的家庭中,一般是母亲在家中照看婴儿,年轻的父亲前去超市购买尿布。 父亲在购买尿布的同时,往往会顺便为自己购买啤酒,这样就会出现啤酒与尿布这两件看 上去不相干的商品经常会出现在同一个购物篮的现象。

1.2 故事引发的思考

​ “啤酒与尿布”是通过人工的观察分析得到的一种关系。面对如此多的超市消费记录, 我们怎么才能高效的发现物品之间的相关性? 换句话说,我们能不能在数学上寻求这么一种算法,能在计算机上运行,从而高效的 去找到这种规则? 1993年美国学者Agrawal 提出通过分析购物篮中的商品集合,从而找出商品之间关联 关系的关联算法,并根据商品之间的关系,找出客户的购买行为。艾格拉沃从数学及计算 机算法角度提出了商品关联关系的计算方法——Apriori算法

2.算法原理

2.1 案例引导

考虑如下一家杂货店简单交易清单:

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-AQf3NyuX-1668817812518)(imgs\1.PNG)]

共有7条交易记录。A B C 等代表的是不同商品。

2.2 基本概念

概念1 事务集:如右表,{ABCD,ABCF,BDEF….},所有的流水记录构成的集合

概念2 记录(事务):ABCD 叫做一条记录(事务)

概念3 项目(项):A , B , C ….叫做一个项目(项)

概念4 项目集(项集):由项组成的集合,如{A,B,E,F},{A,B,C}就是一个项集

概念 5 K项集:项集中元素的个数为K,如{A,B,E,F}就是4项集

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-O6Bstzrb-1668817812518)(imgs\1.PNG)]

概念 6 支持度(Support):

$Sup(X)= \frac {某个项集 X 在事务集中出现的次数}{事务集中记录的总个数} $,

简单理解就是概率(频率)

如 项集X = {A,C} 则 Sup(X)= 4 /7 = 0.57

(概念13 关联规则:形如X=>Y的表达式,X和Y是不相交的项集。例如,X={A},Y={B,C},关联规则{A}=>{B,C},该规则表明如果顾客买A,大概率也会买B、C。)

概念 7 置信度(Confidence):

C o n ( X = > Y ) = S u p ( 𝑋 𝑌 ) S u p ( 𝑋 ) Con(X=>Y)= \frac{Sup(𝑋𝑌)}{Sup(𝑋)} ConX=>Y=SupXSupXY

简单理解就是条件概率

如 X = {A}, Y = {C} ,则

C o n ( X = > Y ) = S u p ( 𝑋 𝑌 ) S u p ( 𝑋 ) = 4 / 7 5 / 7 = 4 / 5 = 0.8 Con(X=>Y)= \frac{Sup(𝑋𝑌)}{Sup(𝑋)} = \frac{4/7 }{5/7}= 4/ 5 = 0.8 ConX=>Y=SupXSupXY=5/74/7=4/5=0.8

概念 8 最小支持度(min_support):人为规定的一个支持度。

概念 9 最小置信度(min_confidence):人为规定的一个置信度。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-WNKXmhih-1668817812519)(imgs\1.PNG)]

概念 10 提升度 :

L i f t ( X = > Y ) = c o n ( X = > Y ) s u p ( Y ) Lift(X=>Y) = \frac{con(X=>Y)}{ sup(Y)} LiftX=>Y=supYconX=>Y ,

理解为Y在X发生的基础上发生 的概率与Y单独发生概率的比值。

如 X = {A}, Y = {C} ,则

L i f t ( X = > Y ) = c o n ( X = > Y ) s u p ( Y ) = 0.8 5 / 7 Lift(X=>Y) = \frac{con(X=>Y)}{ sup(Y)}=\frac {0.8}{5/7} LiftX=>Y=supYconX=>Y=5/70.8 =1.12,

概念 11 频繁K项(目)集:满足(大于等于)最小支持度的K项集。

如,设置最小支持度为0.5,则,

S u p ( X ) = 4 / 7 = 0.57 ≥ 0.5 Sup(X)= 4/7 = 0.57 ≥ 0.5 SupX=4/7=0.570.5 ,称 X = {A,C}就是一个频繁2项集。

概念12 候选K项(目)集:用来生成频繁K项集的K项集。(不等价于所有K项集)

概念13 关联规则:形如X=>Y的表达式,X和Y是不相交的项集。例如,X={A},Y={B,C},关联规则{A}=>{B,C},该规则表明A和B、C的销售之间存在着关联关系。

概念14 强关联规则:同时满足最小支持度和最小置信度的关联规则。

**(**连接步:在频繁2项集L2的基础上,要生成候选3项集C3。一般情况下,从 L k L_k Lk C k + 1 C_{k+1} Ck+1要执行一个合并操作:

C k + 1 = L k × L k = ( X ∪ Y ∣ X , Y ∈ L k , ∣ X ∩ Y = k − 1 项 ) C_{k+1}=L_k×L_k = ({X∪Y|X,Y∈L_k,|X∩Y=k-1项}) Ck+1=Lk×Lk=XYX,YLkXY=k1

从直观上理解为可以按照某种顺,如每个项名称的字典序或者每个项的支持度计数,对 L k L_k Lk中的每个k项集的项排序,如果两个频繁项集的前k-1项相同,则他们可以合并为一个长度是k+1的候选项集。这样做保证了候选项集产生的完全性并且避免了重复。

连接步:

将L_k-1中的所有项集l_i排序,是的l_i[1]<l_i[2]<...<l_i[k-1],

执行连接$L_{k-1} × L_{k-1}$ ,即L_k-1中的项集互相连接

如果L_i和L_j的前k-2项都是相同的,则两者连接。连接的结果为{l_i[1],l_i[2],...,l_i[k-1],l_j[k-1]}

得到所有的连接结果作为候选K项集C_k

剪枝:

1.拿出C_k中的一个候选k项集l_i,找到l_i的所有k-1项集的子集。

2.检查是否l_i的所有k-1项集子集都在L_k-1中,如果人一个k-1项集子集不在L_k-1中,从C_k中删除l_i,如果都在,保留l_i。

3.循环检查讲C_k中的每个候选k项集。

计算C_k中每个候选k项集的支持度,如果≥最小支持度,则,添加到L_k.

1项集集合产生候选k项集集合。

为了计算出Lk,根据Apriori性质,需要从Lk-1选择所有可连接的对连接产生候选k项集的集合,记作Ck。假设项集中的项按字典序排序,则可连接的对是指两个频繁项集仅有最后一项不同。例如,若Lk-1的元素l1和l2是可连接的,则l1和l2两个项集的k-1个项中仅有最后一项不同,这个条件仅仅用于保证不产生重复。

2. 剪枝步

此步骤用于快速缩小Ck包含的项集数目。

由Apriori性质可得,任何非频繁的(k-1)项集都不是频繁k项集的子集,因此,如果Ck中的一条候选k项集的任意一个(k-1)项子集不在Lk-1中,则这条候选k项集必定不是频繁的,从而可以从Ck中删除。

Ck是Lk的超集,经过子集测试压缩Ck后,即可扫描数据库,确定Ck中每个候选的计数,从而确定Lk。

2.3 两个定理

定理 1 : 如果X是一个频繁K项集,则它的所有子集一定也是频繁的。

定理 2 :如果X不是K-1项频繁,则它一定不是频繁K项集。

2.4 算法流程

Step1:令K = 1 ,计算单个商品(项目)的支持度,并筛选出频繁1项集(如最小支持度为0.3 = 2.1/7 )

Step2:(从K=2开始)根据K-1项的频繁项目集生成候选K项目集,并进行预剪枝

Step3:由候选K项目集生成频繁K项集(筛选出满足最小支持度的k项集)

重复步骤2和3,直到无法筛选出满足最小支持度的集合。(第一阶段结束)

Step4:使用频繁项集生成关联规则,将获得的频繁k={1,2,…K}项集,依次取出。对于每一个k,以s->{l-s}的方式生成 2 k − 2 2^k-2 2k2个关联规则,并计算规则的置信度, 将符合要求的强关联规则提出,s为频繁项集l的真子集,l-s是频繁项集除去s之外的项集。(算法结束)

2.4 算法流程

(设置最小支 持度为0.3 = 2.1/7 ,最小置信度为0.75)

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-5sBNNgg5-1668817812519)(imgs\1.PNG)]

Step1:令K = 1 ,计算单个商品(项目)的支持度,并筛选出频繁1项集(最小支 持度为0.3 = 2.1/7 )

{A},{B},{C},{D},{E},{F} 的支持度分别是:0.71,0.86,0.71,0.57,0.57,0.29 。 所以得到的频繁1项集为{A},{B},{C},{D},{E}

Step2:(K=2)根据K-1项的频繁项目集生成候选K项集,并进行预剪枝, 频繁1项集为{A},{B},{C},{D},{E}

如何根据K-1项的频繁项目集生成候选K项目? (最小支持度为0.3 = 2.1/7 )

1.生成候选K项集

1.1连接

将L_k-1中的所有项集l_i排序,使得l_i[1]<l_i[2]<...<l_i[k-1],

执行连接$L_{k-1} × L_{k-1}$ ,即L_k-1中的项集互相连接

如果L_i和L_j的前k-2项都是相同的,则两者连接。连接的结果为{l_i[1],l_i[2],...,l_i[k-1],l_j[k-1]}

得到所有的连接结果作为候选K项集C_k

生成{A,B},{A,C},{A,D},{A,E},{B,C},{B,D}{B,E}{C,D}{C,E}{D,E).

1.2 剪枝

剪枝:

1.拿出C_k中的一个候选k项集l_i,找到l_i的所有k-1集项子集。

2.检查是否l_i的所有k-1项集子集都在L_k-1中,如果人一个k-1项集子集不在L_k-1中,从C_k中删除l_i,如果都在,保留l_i。

3.循环检查C_k中的每个候选k项集。

生成{A,B},{A,C},{A,D},{A,E},{B,C},{B,D}{B,E}{C,D}{C,E}{D,E).

Step3:由候选K项目集生成频繁K项集(筛选出满足最小支持度的k项集)

1.计算C_k中每个候选k项集的支持度,如果≥最小支持度,则添加到L_k.

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-hvmjtakG-1668817812520)(imgs\7.PNG)]

{A,B} {A,C} {B,C} {B,D} {B,E} {C,D} 得到频繁2项集

Step2:(K=3)根据K-1项的频繁项目集生成候选K项目集,并进行预剪枝 (最小支持度为0.3 )

1.生成候选K项集

1.1 连接:{A,B,C} {B,C,D} {B,C,E} {B,D,E}

1.2 剪枝:{A,B,C} {B,C,D}

Step3:由候选K项目集生成频繁K项集(筛选出满足最小支持度的k项集)

1.计算C_k中每个候选k项集的支持度,如果≥最小支持度,则添加到L_k.

Sup(ABC) = 3/7 ,Sup(BCD) = 2/7

{A,B,C}得到频繁3项集

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-6xbyqBCb-1668817812520)(imgs\1.PNG)]

Step4:使用频繁项集生成关联规则,将获得的频繁k={1,2,…K}项集,依次取出。对于每一个k,以s->{l-s}的方式生成 2 k − 2 2^k-2 2k2个关联规则,并计算规则的置信度, 将符合要求的强关联规则提出,s为频繁项集l的真子集,l-s是频繁项集除去s之外的项集。(算法结束)

当k=3,获得的最终的频繁3项集: {A,B,C}….(这里只有一个,数据量大的时候可能有很多) 依次取出:第一个是{A,B,C},获取其所有真子集 {A} {B} {C} {A,C} {A,B} {B,C}

以以s->{l-s}的方式形成关联规则:

{A} ->{B,C}、 {B} ->{A,C} 、{C} ->{A,B} ,{A,B} ->{C}、 {A,C} ->{B}、{B,C} ->{A}

计算置信度,大于等于我们给定的置信度的关联规则为强关联规则。以{A} ->{B,C}为例 Con( {A} ->{B,C} ) = 𝑆𝑢𝑝( 𝐴,𝐵,𝐶 ) /𝑆𝑢𝑝( 𝐴 ) = 3 /5 = 0.6

因此 {A} ->{B,C} 不是一条强关联规则。

计算置信度,以{B,C} ->{A} 为例 Con( {B,C} ->{A} ) = 𝑆𝑢𝑝( 𝐴,𝐵,𝐶 ) /𝑆𝑢𝑝( 𝐵,𝐶 ) = 3/ 4 = 0.75

因此{B,C} ->{A} 是一条强关联规则。

同理,计算其他关联规则的置信度。最后输出满足条件的规则。

最终我们使用频繁3项集获取的强关联规则为:

{B, C} -> {A}, {A, C} -> {B}, {A, B} -> {C}

(注意到 {A} -> {B,C} 的置信度是0.6,所以{B,C} ->{A} 和{A} -> {B,C} 两条关联规则还是有区别的)

3.code

1.安装相应的包

pip install efficient-apriori(需要python3.6以上)

from efficient_apriori import apriori#导入相应的包
# 设置数据集
data = [('A','B','C','D'),
           ('A','B','C','E'),
           ('B','D','E','F'),
           ('B','C','D','E'),
           ('A','C','D','F'),
        ('A','B','C'),
        ('A','B','E'),
       ]
# 挖掘频繁项集和频繁规则
#min_support:最小支持度
#min_confidence:最小置信度
#itemsets:频繁项集
#rules:强关联规则
itemsets, rules = apriori(data, min_support=0.3,  min_confidence=0.75)
print(itemsets)
print(rules)
from efficient_apriori import apriori
# 设置数据集
data = [('牛奶','面包','尿布'),
           ('可乐','面包', '尿布', '啤酒'),
           ('牛奶','尿布', '啤酒', '鸡蛋'),
           ('面包', '牛奶', '尿布', '啤酒'),
           ('面包', '牛奶', '尿布', '可乐')]
# 挖掘频繁项集和频繁规则
itemsets, rules = apriori(data, min_support=0.5,  min_confidence=1)
print(itemsets)
print(rules)

priori import apriori

设置数据集

data = [(‘牛奶’,‘面包’,‘尿布’),
(‘可乐’,‘面包’, ‘尿布’, ‘啤酒’),
(‘牛奶’,‘尿布’, ‘啤酒’, ‘鸡蛋’),
(‘面包’, ‘牛奶’, ‘尿布’, ‘啤酒’),
(‘面包’, ‘牛奶’, ‘尿布’, ‘可乐’)]

挖掘频繁项集和频繁规则

itemsets, rules = apriori(data, min_support=0.5, min_confidence=1)
print(itemsets)
print(rules)


原网站

版权声明
本文为[钰涵雨辰]所创,转载请带上原文链接,感谢
https://blog.csdn.net/weixin_52733693/article/details/127932297

随机推荐