专栏首页智能算法挖掘关联规则之Apriori算法

挖掘关联规则之Apriori算法

1. Apriori算法的目的:

主要是用来挖掘关联规则,即从一个事务数据集中发现频繁项集并推出关联规则,其名字是因为算法基于先验知识(prior knowledge).根据前一次找到的频繁项来生成本次的频繁项。Apriori是关联分析中核心的算法。

Apriori算法的特点:

只能处理分类变量,无法处理数值型变量;

数据存储可以是交易数据格式(事务表),或者是事实表方式(表格数据)。

算法核心在于提升关联规则产生的效率而设计的。

2. 新概念:

项集:

(例如所有的商品)为一个项集,则每一个事务t(例如购买小票上的商品)都是一个项集。

支持度: 项集的支持度是指包含该项集的事务所占所有事务的比例。

频繁项集:就是指满足给定的最小支持度的项集。

关联规则:X->Y 是指由X能推出Y

置信度: 对于X->Y的置信度表示p(X,Y)/p(X); 即项集X事务中也包含项集Y的事务所占的比例

3. Apriori的思想:

我们希望置信度和支持度要满足我们的阈值范围才算是有效的规则,实际过程中我们往往会面临大量的数据,如果只是简单的搜索,会出现很多的规则,相当大的一部分是无效的规则,效率很低,那么Apriori就是通过产生频繁项集,然后再依据频繁项集产生规则,进而提升效率。

以上所说的代表了Apriori算法的两个步骤:产生频繁项集和依据频繁项集产生规则。

为什么确定频繁项集?

刚才说了,必须支持度大于我们指定的支持度,这也就是说能够确定后面生成的规则是在普遍代表性上的项目集生成的,因为支持度本身的高低就代表了我们关联分析结果是否具有普遍性。

怎么寻找频繁项集?

这里不再讲述,直接说一个例子大家就都明白了。例子来源于Fast Algorithms for Mining Association Rules

如下:

Apriori寻找频繁项集的过程是一个不断迭代的过程,每次都是两个步骤,产生候选集Ck(可能成为频繁项集的项目组合);基于候选集Ck计算支持度,确定Lk。

Apriori的寻找策略就是从包含少量的项目开始逐渐向多个项目的项目集搜索。

数据如下:

我们看到,数据库存储的数据格式,会员100购买了 1 3 4三种商品,那么对应的集合形式如右边的图所示。那么基于候选集C1,我们得到频繁项集L1,如下图所示,在此表格中{4}的支持度为1,而我们设定的支持度为2。支持度大于或者等于指定的支持度的最小阈值就成为L1了,这里{4}没有成为L1的一员。因此,我们认定包含4的其他项集都不可能是频繁项集,后续就不再对其进行判断了。

此时我们看到L1是符合最低支持度的标准的,那么下一次迭代我们依据L1产生C2(4就不再被考虑了),此时的候选集如右图所示C2(依据L1*L1的组合方式)确立。C2的每个集合得到的支持度对应在我们原始数据组合的计数,如下图左所示。

此时,第二次迭代发现了{1 2} {1 5}的支持度只有1,低于阈值,故而舍弃,那么在随后的迭代中,如果出现{1 2} {1 5}的组合形式将不被考虑。

如上图,由L2得到候选集C3,那么这次迭代中的{1 2 3} { 1 3 5}哪去了?如刚才所言,{1 2} {1 5}的组合形式将不被考虑,因为这两个项集不可能成为频繁项集L3,此时L4不能构成候选集L4,即停止。

如果用一句化解释上述的过程,就是不断通过Lk的自身连接,形成候选集,然后在进行剪枝,除掉无用的部分。根据频繁项集产生简单关联规则。

Apriori的关联规则是在频繁项集基础上产生的,进而这可以保证这些规则的支持度达到指定的水平,具有普遍性和令人信服的水平。

以上就是Apriori的算法基本原理,下面以一个具体的实例进行说明下。

算法作用:Apriori算法主要是用来挖掘关联规则,即从一个事务数据集中发现频繁项集并推出关联规则

4. 算法应用:

应用数据集:Groceries(一个购物蓝的数据集)

应用目的:分析出购物蓝数据集中那些物品常存在与一个购物蓝中,并推出关联规则。

运行代码:

代码解释:第六行代码中设置支持度为1%,置信度为0.5

运行结果分析:

通过上代码运行出的结果见上图,该结果第一列为lhs(left-hand side),代表关联规则中的X,第二列rhs(right-hand side),代表关联规则中的Y,第三列为支持度,以第一项为例表示有1.006609%的人购买了lhs+rhs,第四列为置信度表示购买lhs的顾客中会有58.24%的人去买rhs,计算公式为confidence=P(lhs+rhs)/P(lhs). 最后一列lift是一个类似相关系数的指标。lift=1 时表示lhs和rhs独立,该值越大表明lhs和rhs存在一个购物蓝中并不是偶然的,计算公式为lift=P(lhs+rhs)/P(lhs)*P(rhs).

从此,我们分析下第一条关联规则:有1%的人同时购买了curd,yogurt,whole milk这三种商品,其中在购买curt和yogurt的客户中,共有58.23%的人买了whole milk。lift=2.28表示这两个(lhs和rhs)并不是独立的。

参考资料:

http://zhan.renren.com/dmeryuyang?gid=3602888498023976650&checked=true

http://rakesh.agrawal-family.com/papers/vldb94apriori.pdf

回复数字或算法名称即可查看相关文章:

1. 决策树算法之一C4.5

2. 数据挖掘之Apriori算法

3. 网页排序算法之PageRank

本文分享自微信公众号 - 智能算法(AI_Algorithm),作者:By: 左右

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2016-05-09

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 挖掘关联规则之Apriori算法

    1. Apriori算法的目的: 主要是用来挖掘关联规则,即从一个事务数据集中发现频繁项集并推出关联规则,其名字是因为算法基于先验知识(prior knowle...

    智能算法
  • 机器学习三人行(系列一)----机器学习花样入门

    写在前面 深度学习如火如荼,作为一个IT技术人员,不搞一下深度学习,总有一种活在上个世纪的感觉,因此笔者准备认认真真的搞一下深度学习,努力跟上时代的步伐。话说基...

    智能算法
  • 机器学习新手的十大算法导览

    机器学习中,有一个称为“ No Free Lunch ”的定理。简单来说,与监督学习特别相关的这个定理,它指出没有万能算法,就是用一个算法能很好地解决每个问题。

    智能算法
  • 【独家】一文读懂关联分析

    前言 关联分析是数据挖掘中一项基础又重要的技术,是一种在大型数据库中发现变量之间有趣关系的方法。说到数据挖掘的案例,相信很多人都会首先想到沃尔玛超市发现购买尿布...

    数据派THU
  • Apriori算法的python实现

    原始链接里的代码是在python2下写的,有的地方我看的不是太明白,在这里,我把它修改成能在python3下运行了,还加入了一些方便自己理解的注释。

    py3study
  • 数据挖掘|关联规则Apriori算法

    01 — 关联规则挖掘背景和基本概念 如下所示的数据集,表中的每一行代表一次购买清单,注意我们只关心记录出现与否,不关心某条记录购买了几次,如购买十盒牛奶也只...

    double
  • 机器学习实战 - 读书笔记(11) - 使用Apriori算法进行关联分析

    绿巨人
  • 关联分析(2):Apriori产生频繁项集

    在关联分析(1):概念及应用中,我们介绍了关联分析的应用场景、基本概念和规则产生思路。在本次的文章中,我们将介绍Apriori算法频繁项集产生的原理。文章中会涉...

    三猫
  • [机器学习算法]关联分析

    全球零售巨头沃尔玛分析消费者购物行为时偶然发现男性顾客同时购买啤酒和尿布的比例较高,于是通过将啤酒和尿布捆绑销售的方式提高了两者的销量。这种用于发现隐藏在大型数...

    TOMOCAT
  • 挖掘关联规则之Apriori算法

    1. Apriori算法的目的: 主要是用来挖掘关联规则,即从一个事务数据集中发现频繁项集并推出关联规则,其名字是因为算法基于先验知识(prior knowle...

    智能算法

扫码关注云+社区

领取腾讯云代金券