数据挖掘——关联规则(Association Rule)Apriori算法和python代码实现
创始人
2024-04-20 14:50:24
0

关联规则(Association Rule)

    • 什么是关联规则
    • 一些基本概念
    • 任务是什么
    • Apriori 算法
        • 核心思想
        • 步骤与流程图
        • 如何找到候选集
    • python代码实现

什么是关联规则

关联规则(Association Rules)是反映一个事物与其他事物之间的相互依存性和关联性,是数据挖掘的一个重要技术,用于从大量数据中挖掘出有价值的数据项之间的相关关系。

用一些例子来说明一下:
当我们在超市进行购物时,超市中有琳琅满目的商品,在每一次购物结束之后,我们会拥有一个购物车然后去结账,然后产生购物小票,购物小票中记录了我们购买的每件商品的信息,如此日积月累,所有的这些记录就会产生海量的用户购买行为。从这些购买行为中,我们特别希望能够发掘出类似买了面包的人就会去购买牛奶这样的规则。
这种规则,在数据挖掘中有很多,比如著名的啤酒和尿布的例子:在美国,一些年轻的父亲下班后经常要到超市去买婴儿尿布,而他们中有30%~40%的人同时也为自己买一些啤酒。产生这一现象的原因是:美国的太太们常叮嘱她们的丈夫下班后为小孩买尿布,而丈夫们在买尿布后又随手带回了他们喜欢的啤酒。
在这里插入图片描述
买了一样商品就会去买另外一件商品,这就是一种关联规则。

一些基本概念

Items(项)
实际上就是一些商品,面包,牛奶,巧克力,啤酒,尿布… 每一个都是一个itemitemitem。

Transaction(交易)
一条交易记录(购物小票),是所有商品的非空子集。可以买一件商品,两件商品… 但是集合不能是空集。

Itemset(项集)
同时购买的一组东西。itemsetitemsetitemset有大有小,购买的东西有可能有1个,2个,kkk个,如果有kkk个,那么 itemset 就被称作 k−itemsetk-itemsetk−itemset。

Dataset(数据库)
包含一系列的transactiontransactiontransaction

下面给出一个例子:
在这里插入图片描述
Bread是一个itemitemitem,Butter也是一个itemitemitem,而第1、2、4交易记录中,同时购买的Bread和Butter,就组成一个 2−itemset2-itemset2−itemset。

Support(支持度)
可以理解成是一种频率,就是在一些 transactiontransactiontransaction 当中某一个item(或者itemset)item( 或者 itemset)item(或者itemset)出现的频率。
在这里插入图片描述

例如上表中的 Bread$ 的support就是6/8,Bread与Butter的supportsupportsupport是3/8,Bread、Butter和Chips的supportsupportsupport是0

关联规则x−>yx -> yx−>y的支持度就是一些交易中同时包含xxx和yyy的频率。
在这里插入图片描述
Confidence(置信度)
关联规则x−>yx -> yx−>y的置信度就是一些交易中 同时包含xxx和yyy的数量与xxx的数量的比。
在这里插入图片描述
也可以被写作下面的公式:
在这里插入图片描述
置信度也可以被理解为是一种条件概率 P(X∣Y)P(X | Y)P(X∣Y),比如当我购买牛奶这个事件发生的时候,又购买面包这个事件发生的概率是多少。

引用上表的例子,如
Bread −>->−> Milk 的 supportsupportsupport = 2/8 , confidenceconfidenceconfidence = 1/3
Milk −>->−> Bread 的 supportsupportsupport = 2/8 , confidenceconfidenceconfidence = 2/3

我们需要的规则,它必须是一种强规则,而且要频繁。supportsupportsupport度量了一条规则的频繁程度,confidenceconfidenceconfidence度量了一条规则的强度。我们定义两个阈值来量化这条规则的频繁程度和强度:
minimumminimumminimum supportsupportsupport:σ
minimumminimumminimum confidenceconfidenceconfidence:Φ

Frequent itemset(频繁集)
一个itemset,它的support>σsupport > σsupport>σ

Strong rule(强规则)
一个规则x−>yx->yx−>y,它既要是频繁的 (support>σsupport > σsupport>σ),而且要 confidence>Φconfidence > Φconfidence>Φ

任务是什么

当已知 Items,dataset,σ,ΦItems,dataset,σ,ΦItems,dataset,σ,Φ,我们要做的就是从datasetdatasetdataset中挖掘出类似于 x−>yx->yx−>y的所有的 Strong rule。
要找出所有的强规则,方法就是:

  1. 找出所有的 frequentfrequentfrequent itemsetsitemsetsitemsets
  2. 运用 frequentfrequentfrequent itemsetsitemsetsitemsets ,对于每一个frequentfrequentfrequent itemitemitem,生成它的所有的非空子集,然后利用这些非空子集找出所有可能的关联规则,然后对这些规则进行校验 supportsupportsupport 和 confidenceconfidenceconfidence。

例如:根据集合a,b,c{a,b,c}a,b,c,找出其所有可能的关联规则。
在这里插入图片描述
根据上面的2个步骤可以找出强规则。但是假如我们共有ddd种商品,那么所有可能的itemsetsitemsetsitemsets的个数就是2d−12^d-12d−1,这是一个指数级的数字,想象一下,商品的数量如果有成百上千种,那么itemsetitemsetitemset的数量是不可估计的。所以问题的关键就是,如何高效率的找出所有的 frequentfrequentfrequent itemsetsitemsetsitemsets,下面介绍的就是解决这个核心问题的一个算法: Apriori 算法

Apriori 算法

核心思想

首先介绍两个核心思想:

  1. 一个频繁集的子集一定是频繁集,
    {Milk, Bread, Coke} is frequent -> {Milk, Coke} is frequent
  2. 一个itemsetitemsetitemset不是频繁集,那么它的所有的超级一定不是频繁集,
    {Battery} is infrequent -> {Milk, Battery} is infrequent
    例如下图,我们知道B不是一个频繁集,那么所有标记为绿色的itemsetitemsetitemset都不是频繁集。

在这里插入图片描述

步骤与流程图

下面介绍Apriori的核心思路
(1) 先生成某一个特定大小的itemsetsitemsetsitemsets,一般从1开始,如{牛奶},{面包},{巧克力}
(2) 扫描数据库,观察这些 itemsetsitemsetsitemsets 哪些是频繁的,即频繁集,不频繁的itemsetitemsetitemset直接舍弃
(3) 运用这些频繁集,组合成数量加1个大小的 itemsetsitemsetsitemsets(被称为 candidatecandidatecandidate itemsetsitemsetsitemsets 候选集),例如{牛奶,面包},{面包,巧克力},{牛奶,巧克力}。然后重复上面的第(2)步扫描数据库,舍弃不频繁的itemsetsitemsetsitemsets,之后重复(2),(3)步。itemsetsitemsetsitemsets的大小逐一增加。
(4) 综上,核心思想就是尽量避免去生成不频繁的candidatecandidatecandidate itemsetsitemsetsitemsets

算法流程图:
定义:
CkC_kCk​:大小为kkk的candidatecandidatecandidate itemsetsitemsetsitemsets
LkL_kLk​:大小为kkk的frequentfrequentfrequent itemsetitemsetitemset

在这里插入图片描述
首先找出所有的frequentfrequentfrequent itemsitemsitems,长度是一。里面的小循环是扫描数据库中的每一条记录,根据已知的candidatecandidatecandidate itemsetitemsetitemset,我们在每一条记录中查看一下是否存在这样一个candidatecandidatecandidate itemsetitemsetitemset,如果存在,那么就count++count++count++ 计数,也就是说在所有的记录中,有多少条记录包括这样一个特定的itemsetitemsetitemset。里面的循环走完之后,我们就开始过滤操作,比较一下supportsupportsupport,如果> 我们之前设置的阈值σσσ,那么就把这个itemsetitemsetitemset留下,否则抛弃。然后外面的大循环,是把这些频繁集进行组合,组合成更大的candidatecandidatecandidate itemsetsitemsetsitemsets,生成可能频繁的候选集,步数是1。

上面的算法中,最为关键的一步就是如何从LkL_kLk​生成Ck+1C_{k+1}Ck+1​
LkL_kLk​是一个集合,集合里面所有的 itemsetitemsetitemset 中的 itemitemitem 个数都是一样的,都是kkk个,而且这些 itemsetitemsetitemset都是频繁的
Ck+1C_{k+1}Ck+1​也是一个集合,其中的 itemsetitemsetitemset 中的itemitemitem 个数都是比LkL_kLk​中的多一个
如何从LkL_kLk​生成Ck+1C_{k+1}Ck+1​,要做到必须把所有的频繁集都找到,同时又不能生成太多的冗余的

用下面这个例子进行讲述:
已知L1L_1L1​:{1,2,3,4,5},L2L_2L2​:{ {1,2},{2,3} },即1,2,3,4,5都是频繁的,{1,2},{2,3}也是频繁的。如何利用L1L_1L1​,L2L_2L2​生成 C3C_3C3​?

如何找到候选集

方法一
把一个频繁的加入到两个频繁的,就生成了所有3个的可能频繁的 itemsetitemsetitemset
在这里插入图片描述
所以用这个方法得到的C3C_3C3​就是{ {1,2,3},{1,2,4},{1,2,5},{2,3,4},{2,3,5} }
这个方法得到的C3C_3C3​不能说是错误的,但是效率太低。例如我们看到C3C_3C3​中的 {1,2,5},其中它的子集 {1,5}是不在L2L_2L2​当中的,说明{1,5}是不频繁的,而 {1,2,5} 是它的超集,则说明 {1,2,5} 也是不频繁的。因此我们可以清楚的看到方法一生成的C3C_3C3​会有大量的冗余。

方法二
从L2L_2L2​ 中找两个itemsetitemsetitemset,xxx和yyy,这两个itemsetitemsetitemset要满足一个条件,他们中的itemitemitem只有一个是不同的。然后把xxx和yyy拼起来。
在这里插入图片描述
用方法二,我们发现我们L2L_2L2​中的两个itemsetitemsetitemset,它们的2是相同的,1和3是不同的,就可以得到C3C_3C3​就是{ {1,2,3} }。方法二的效率要比方法一的效率高很多。但是我们仔细观察会发现,这个{1,2,3}也是不频繁的,因为它的子集{1,3}不在L2L_2L2​当中,所以{1,3}也是不频繁的。

方法三
首先对所有的 itemitemitem 做一个排序,然后从L2L_2L2​ 中找两个itemsetitemsetitemset,xxx和yyy,这两个itemsetitemsetitemset要满足一个条件,xxx和yyy的前k−1k-1k−1项都是相同的,第kkk项是不同的,然后把xxx和yyy第kkk项与前k−1k-1k−1项拼起来,组成k+1k+1k+1大小的itemsetitemsetitemset。
在这里插入图片描述
用方法三我们就可以发现,对于上述的L2L_2L2​我们找不出满足方法三的两个itemset,因此得到C3C_3C3​是 {}
如果L2L_2L2​是{ {1,2},{1,3},{2,3} },生成的C3C_3C3​就是 { {1,2,3} },因为我们可以找到两个满足方法三的itemsetitemsetitemset {1,2} 和 {1,3} ,他们的第一位都是1,第2位不相同分别是2和3,由此可以得到C3C_3C3​中的一个满足条件的itemsetitemsetitemset {1,2,3}

但是如果L2L_2L2​是{ {1,2},{1,3} },生成的C3C_3C3​也是 { {1,2,3} },但是我们清楚地知道这个生成的{1,2,3}是不可能频繁的,因为它的子集{2,3}不在L2L_2L2​当中。所以虽然方法三是效率最高的,但是我们在生成了C3C_3C3​之后也要做进一步的验证,即验证它的子集是否都在L2L_2L2​中。

下面是一个具体的例子:
在这里插入图片描述

python代码实现

下面使用python实现上面的Apriori算法,其中通过频繁集生成候选集采用的是方法三。

计算支持率

#计算支持率
def support(item,T):n=len(T)   # 事务集合的长度l=len(item)count=0for x in T:if  len(set(x)&set(item)) == l:   # 判断是否有交集,有交集,分子加1count=count+1return  1.0*count/n

生成候选集

def produce_Candinate(L, k):candinate = []   # 首先创建一个空的集合for x in range(len(L)):   # 每两个元素集合进行比较for y in range(x + 1, len(L)):flag = Truex_item = L[x]y_item = L[y]for i in range(k):if x_item[k - 1] == y_item[k - 1]:   # 如果两个元素集合的最后一项相同 ,候选集为空flag = Falsebreakelif x_item[i] != y_item[i] and i < k-1: # 如果前面 k-1 项有不相同的,候选集为空flag = Falseif flag:temp = x_item.copy()temp.append(y_item[k - 1])  # 将q中的最后一项添加到p中temp.sort()if has_frequent_subset(temp, L, k):candinate.append(temp)print("候选", k + 1, "-项集:", candinate)return candinate# 判断候选集子集是否是频繁集
def has_frequent_subset(c, freq_items, n):num = len(c) * n  # count = 0flag = Falsefor c_item in freq_items:   if set(c_item).issubset(set(c)):    #判断上一层的频繁集中的每一项是否是计算出来的候选集的子集count += n   # 如果是就把count加上nif count == num:     # 如果最后相等(候选集的每个子集都在频繁集当中),就说明这个候选集中的每个子集都是频繁集flag = Truereturn flag

Apriori算法挖掘频繁项集

#Apriori算法挖掘频繁项集
def Apriori(T,min):k=1#结果集,用于保存所有的频繁集out=[]#生成1-候选集C=[]for x in T:C=list(set(x)|set(C))#生成1频繁项集F=[]for i in C:if support(list(i),T) >= min:F.append([i])#迭代while (len(F)>0):out.append(F)#生成k+1候选集C=produce_Candinate(F,k)#生成k+1频繁项集F=[]for i in C:if support(i,T) >=min:F.append(i)k=k+1return out

主函数调用

T = [['A','B','C','D'], ['B','C','E'], ['A','B','C','E'], ['B','D','E'], ['A','B','C','D'] ]
out = Apriori(T,0.3)
print('频繁项集')
for i in out:print(i)

打印结果
在这里插入图片描述
以上就是Apriori算法的全部内容,其中知识点部分参考了b站清华大学-数据挖掘 ,代码部分参考了多篇文章,并加入了一些的注释和自己的理解,有疑问欢迎评论区讨论!

上一篇:node常用依赖

下一篇:Onvif学习

相关内容

热门资讯

鸿蒙怎样还原安卓系统,系统切换... 你有没有想过,鸿蒙系统竟然能还原安卓系统?这听起来是不是有点像魔法一样神奇?没错,今天就要带你一探究...
电脑安卓转苹果系统,系统迁移攻... 你有没有想过,有一天你的安卓手机突然变成了苹果的忠实粉丝,想要跳槽到iOS的阵营呢?这可不是什么天方...
安卓xp系统下载地址,轻松获取... 你有没有想过,手机系统也能穿越时空?没错,今天我要给你揭秘的就是这样一个神奇的存在——安卓XP系统。...
安卓系统怎么清理相册,安卓系统... 手机里的相册是不是越来越臃肿了?每次打开都感觉像是在翻山越岭,找一张照片都要费老鼻子劲。别急,今天就...
安卓系统安装ios转移,轻松实... 你有没有想过,手机系统之间的转换竟然也能如此神奇?没错,今天就要来聊聊安卓系统安装iOS转移这个话题...
安卓系统与ios系统的优势,系... 你有没有想过,为什么你的手机里装的是安卓系统而不是苹果的iOS系统呢?或者反过来,为什么你的朋友用的...
安卓系统游戏如何升级,轻松实现... 亲爱的安卓玩家们,你是否也和我一样,对安卓系统游戏升级这件事充满了好奇和期待呢?每次游戏更新,都仿佛...
安卓系统蛋仔派对,安卓系统下的... 你有没有发现,最近你的手机里多了一个超级好玩的游戏?没错,就是安卓系统上的“蛋仔派对”!这款游戏可是...
坚果3安卓原生系统,深度体验原... 你有没有听说过坚果3这款手机?它可是最近在数码圈里火得一塌糊涂呢!今天,我就要来给你详细介绍一下这款...
安卓子系统点不开,排查与解决指... 最近是不是你也遇到了安卓子系统点不开的烦恼?这可真是让人头疼啊!别急,今天就来给你详细解析一下这个问...
安卓系统经常误删文件,如何有效... 你有没有遇到过这种情况?手机里的文件突然不见了,找来找去,怎么也找不到。别急,这可能是安卓系统的小调...
安卓51系统如何破解,轻松解锁... 安卓51系统如何破解——探索未知的技术边界在数字化时代,手机已经成为我们生活中不可或缺的一部分。而安...
安卓系统怎么换回主题,安卓系统... 亲爱的手机控们,你是不是也和我一样,对安卓系统的主题换换换乐此不疲呢?不过,有时候换着换着,突然发现...
黑莓安卓系统 太垃圾,令人失望... 你有没有用过黑莓的安卓系统?别告诉我你没有,因为现在这个系统真的是太垃圾了!是的,你没听错,就是那个...
修改安卓系统权限代码,安卓系统... 你有没有想过,你的安卓手机里那些神秘的系统权限代码?它们就像隐藏在手机里的秘密通道,有时候让你觉得既...
虚拟大师安卓系统教程,教程详解... 你有没有想过,手机里的世界可以变得更加神奇?今天,就让我带你一起探索虚拟大师安卓系统的奥秘吧!想象你...
基于安卓系统个人博客,轻松构建... 你有没有想过,在这个信息爆炸的时代,拥有一片属于自己的网络小天地是多么酷的事情啊!想象每天都能在这里...
安卓怎么传到苹果系统,从安卓到... 你是不是也有过这样的烦恼:手机里存了好多好用的安卓应用,可是一换到苹果系统,就发现这些宝贝们都不见了...
安卓改系统字体app,安卓系统... 你有没有想过,手机上的字体也能变得个性十足?没错,就是那个安卓改系统字体app,它可是让手机界面焕然...
安卓系统重启密码错误,破解与预... 手机突然重启了,屏幕上竟然出现了密码输入的界面!这可怎么办?别急,让我来帮你一步步解决这个安卓系统重...