`
cloudtech
  • 浏览: 4578912 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
文章分类
社区版块
存档分类
最新评论

使用Orange进行数据挖掘之关联------Apriori

 
阅读更多

关联

基本定义

关联规则:形如 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条规则,所以对事先对规则删减有助于提高效率。

大多数关联规则算法通常采用的一种计算策略是将关联挖掘任务分解成两步:

  1. 频繁项集的产生:发现满足最小支持度的所有项集,被成为频繁项集。
  2. 规则的产生:从上一步的频繁项集中提取高置信度的规则

Apriori算法是根据先验原理的关联算法。

先验原理:如果一个项集是频繁的,则它的所有子集一定也是频繁的。

同样如果项集是不频繁的,则它的所有超集也是不频繁的。

Apriori中频繁项集的产生

以如下数据为例:

下面是对数据的迭代过程,其中最小支持度为2:



  1. 在算法的第一次迭代,每个项都是候选1-项集的集合C1的成员。算法简单地扫描所有的事务,对每个项的出现次数计数。
  2. 可以确定频繁1-项集的集合L1。它由具有最小支持度的候选1-项集组成。
  3. 为发现频繁2-项集的集合L2,算法使用L1XL1产生候选2-项集的集合C2,扫描D中事务,计算C2中每个候选项集的支持计数
  4. 确定频繁2-项集的集合L2,它由具有最小支持度的C2中的候选2-项集组成。
  5. 候选3-项集的集合C3的产生详细地列在图6.4中。首先,令C3 = L2L2 = {{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-项集组成。
  6. 算法使用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组件使用的配置如下:

配置关联规则:

发现的关联规则如下:






分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics