关联
基本定义
关联规则:形如 X -> Y的蕴涵表达式,其中X和Y是不相交的项集。关联规则的强度可以用支持度和置信度度量
支持度:确定规则可以用于给定数据集的频繁程度,用s表示 s=(x并y的长度)/数据集的长度
置信度:确定Y在包含X的事物中出现的频繁程度。用c表示 c=(x并Y的长度)/(X的长度)
例如 有购物蓝事物的例子
1 |
{面包,牛奶} |
2 |
{面包,尿布,啤酒,鸡蛋} |
3 |
{牛奶,尿布,啤酒,可乐} |
4 |
{面包,牛奶,尿布,啤酒} |
5 |
{面包,牛奶,尿布,可乐} |
有规则{ 牛奶,尿布}->{啤酒} ,项集{牛奶,尿布,啤酒}的支持度为2,事物总数为5,则该规则的支持度为2/5,规则的置信度为2/3.
关联规则的发现:给定事物的集合T,关联规则是指找出支持度大于等于minsup,并且置信度大于等于minconf的所有规则。
挖掘规则的原始方法是计算每个可能规则的支持度和置信度。但是从数据集中提取规则的数据成指数级。具体的说从包含d的项的数据集中提取可能的规则总数有
R=3^d-2^(d+1)+1。对上表的数据就有602条规则,所以对事先对规则删减有助于提高效率。
大多数关联规则算法通常采用的一种计算策略是将关联挖掘任务分解成两步:
- 频繁项集的产生:发现满足最小支持度的所有项集,被成为频繁项集。
- 规则的产生:从上一步的频繁项集中提取高置信度的规则
Apriori算法是根据先验原理的关联算法。
先验原理:如果一个项集是频繁的,则它的所有子集一定也是频繁的。
同样如果项集是不频繁的,则它的所有超集也是不频繁的。
Apriori中频繁项集的产生
以如下数据为例:
下面是对数据的迭代过程,其中最小支持度为2:
- 在算法的第一次迭代,每个项都是候选1-项集的集合C1的成员。算法简单地扫描所有的事务,对每个项的出现次数计数。
- 可以确定频繁1-项集的集合L1。它由具有最小支持度的候选1-项集组成。
- 为发现频繁2-项集的集合L2,算法使用L1XL1产生候选2-项集的集合C2,扫描D中事务,计算C2中每个候选项集的支持计数
- 确定频繁2-项集的集合L2,它由具有最小支持度的C2中的候选2-项集组成。
- 候选3-项集的集合C3的产生详细地列在图6.4中。首先,令C3 = L2L2 = {{I1,I2,I3}, {I1,I2,I5}, {I1,I3,I5}, {I2,I3,I4}, {I2,I3,I5}, {I2,I4,I5}}。根据Apriori性质,频繁项集的所有子集必须是频繁的,我们可以确定后4个候选不可能是频繁的。因此,我们把它们由C3删除,这样,在此后扫描D确定L3时就不必再求它们的计数值。注意,Apriori算法使用逐层搜索技术,给定k-项集,我们只需要检查它们的(k-1)-子集是否频繁,扫描D中事务,以确定L3,它由具有最小支持度的C3中的候选3-项集组成。
- 算法使用L3XL3产生候选4-项集的集合C4。尽管连接产生结果{{I1,I2,I3,I5}},这个项集被剪去,因为它的子集{I1,I3,I5}不是频繁的。这样,C4 = Æ,因此算法终止,找出了所有的频繁项集
Apriori规则的产生
频繁项集l = {I1, I2, I5},可以由l产生哪些关联规则?l的非空子集有{I1,I2}, {I1,I5}, {I2,I5}, {I1}, {I2}和{I5}。结果关联规则如下,每个都列出置信度。
如果最小置信度阈值为70%,则只有2、3和最后一个规则可以输出。
Orange中的Apriori
在Orange中针对关联规则提供了两个算法。一个是Apriori标准算法,另一个是Apriori算法的变种。
针对标准的Apriori算法例子:
import Orange
data = Orange.data.Table("inquisition.basket")
rules = Orange.associate.AssociationRulesSparseInducer(data, support = 0.5)
print "%5s %5s" % ("supp", "conf")
for r in rules:
print "%5.3f %5.3f %s" % (r.support, r.confidence, r)
输出结果:
0.500 1.000 fear -> surprise
0.500 1.000 surprise -> fear
0.500 1.000 fear -> surprise our
0.500 1.000 fear surprise -> our
0.500 1.000 fear our -> surprise
0.500 1.000 surprise -> fear our
0.500 1.000 surprise our -> fear
0.500 0.714 our -> fear surprise
0.500 1.000 fear -> our
0.500 0.714 our -> fear
0.500 1.000 surprise -> our
0.500 0.714 our -> surprise
下图给出了用可视化的方式进行关联挖掘:
file组件使用的配置如下:
配置关联规则:
发现的关联规则如下:
分享到:
相关推荐
Apriori算法对购物篮进行关联分析-Apriori算法进行购物篮关联分析.rar 大家好,出来乍到,看到好多高手分享自己的程序,我也想分享一下,做出自己的贡献。 虽然学MATLAB已经一年有余,但是一直忙着数学建模,对...
Apriori算法是关联规则挖掘的代表性算法,十大数据挖掘算法之一,可见其重要性。它的主要作用是发现事物之间的内在联系。 Apriori算法的基本思想是通过对数据的多次扫描来计算项集的支持度,发现所有的频繁项集从而...
MADlib-基于SQL的数据挖掘解决方案-关联规则之Apriori算法.docx
使用Apriori和FP-growth进行关联规则挖掘
Apriori关联规则挖掘Apriori关联规则挖掘Apriori关联规则挖掘Apriori关联规则挖掘Apriori关联规则挖掘Apriori关联规则挖掘Apriori关联规则挖掘Apriori关联规则挖掘
数据挖掘中关联规则挖掘的Apriori算法源代码,很不错,值得看一下
这是对于数据挖掘课程的一个小结,花了大约三天的时间完成,总的来说完成的还可以,虽然实现的效果不咋地。
人工智能-机器学习-关联规则分析-Apriori算法实例-挖掘电影导演的关联规则
数据挖掘 关联规则 之Apriori算法 实验报告数据挖掘
对经典的数据挖掘算法 Apriori 算法和 FP-growth 进行简单实现
该算法是数据挖掘中关联规则的经典算法。代码风格清晰,运行速度快!
一个数据挖掘的经典算法的实现,可以实现从复杂数据中找出有用的信息
数据挖掘Apriori算法参考论文几十篇,知网、万方下载打包共享 有以下几方面内容: Apriori算法并行处理、Apriori算法增量更新、Apriori算法最小支持度和最小置信度阈值设置调优。 基于Spark的并行频繁模式挖掘算法 ...
电子科技大学数据挖掘课程 第二次实验 关联规则挖掘 实验报告及代码实现 包括频繁项集获取过程 关联规则获取过程 自认为理解&写得还是很透彻的哈哈哈 没看懂可以来找我~
【转】数据挖掘-关联分析频繁模式挖掘Apriori、FP-Growth及Eclat算法的JAVA及C 实现.doc
apriori关联规则
数据挖掘中关联规则Apriori算法.pdf
apriori-java.
10.1 关联规则基本概念 ...10.6 多层关联规则挖掘 10.7 多维关联规则挖掘 10.8 约束性关联规则挖掘 10.9 数量关联规则挖掘 10.10 负关联规则挖掘算法 10.11 加权关联规则挖掘算法 10.12 应用实例分析 10.13 小结
源程序……………………