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

01

关联规则挖掘背景和基本概念

如下所示的数据集,表中的每一行代表一次购买清单,注意我们只关心记录出现与否,不关心某条记录购买了几次,如购买十盒牛奶也只计一次。

数据记录的所有项的集合称为总项集,上表中的总项集:

S={牛奶,面包,尿布,啤酒,鸡蛋,可乐}

关联规则

就是有关联的规则,形式是这样定义的:两个不相交的非空集合X、Y,如果有

X->Y,就说X-->Y是一条关联规则,例如,{啤酒}-->{尿布}就是一条关联规则。

关联规则的强度用支持度(support)和自信度(confidence)来描述。

支持度

support(X-->Y) = 集合X与集合Y中的项在一条记录中同时出现的次数 / 数据记录的个数。例如:support({啤酒}-->{尿布}) = 啤酒和尿布同时出现的次数 / 数据记录数 = 3/5=60%

自信度

confidence(X-->Y) = 集合X与集合Y中的项在一条记录中同时出现的次数 / 集合X出现的个数 。例如:confidence({尿布}-->{啤酒}) = 啤酒和尿布同时出现的次数 / 尿布出现的次数 = 3/4 = 75%。

总结

支持度和自信度越高,说明规则越强,关联规则挖掘就是挖掘出满足一定强度的规则。

02

关联规则挖掘的之穷举算法

关联规则挖掘

给定一个交易数据集T,找出其中所有支持度 support >= min_support、自信度confidence >= min_confidence的关联规则。

穷举算法

找出所需要的规则就是穷举项集的所有组合,并测试每个组合是否满足条件,一个元素个数为n的项集所需要的时间复杂度为O(2^N)。上表的总项集 S={牛奶,面包,尿布,啤酒,鸡蛋,可乐},元素的个数为6,所有的组合个数为63 。

为了简单起见,已知一个商品编号的总项集为:{1, 2, 3},那么所有可能的组合为:

{1},{2} {1},{3} {2},{3} {1},{2,3} {2},{1,3} {3},{1,2} {1,2,3}

共有7项(2^3 - 1),分别检查以上各种组合,在每一种组合上找出满足支持度和自信度要求的关联规则。

对于普通的超市,其商品的项集数也在1万以上,用指数时间复杂度的算法不能在可接受的时间内解决问题。

怎样快速挖出满足条件的关联规则是关联挖掘的需要解决的主要问题。

03

关联规则挖掘优化算法之Apriori算法

关联规则挖掘分两步进行:

  1)生成频繁项集

这一阶段找出所有满足最小支持度的项集,找出的这些项集称为频繁项集。

  2)生成规则

  在上一步产生的频繁项集的基础上生成满足最小自信度的规则,产生的规则称为强规则。

关联规则挖掘所花费的时间主要是在第一步:生成频繁项集上。因为找出的频繁项集往往不会很多,所以2)相对1)耗时少。

为了减少 1):频繁项集的生成时间,应该尽早的消除一些完全不可能是频繁项集的集合,Apriori算法主要通过两个规律减少频繁项集。

两个定律

  1. 高级到低级。如果一个集合是频繁项集,则它的所有子集都是频繁项集。假设一个集合{A,B}是频繁项集,则它的子集{A}, {B} 都是频繁项集。
  2. 低级到高级。如果一个集合不是频繁项集,则它的所有超集都不是频繁项集。假设集合{A}不是频繁项集,则它的任何超集如{A,B},{A,B,C}必定也不是频繁项集。

具有实际应用价值的还是第2条,从低级的频繁项集到高级的频繁项集的演化,试想,如果二级项集 {A,B}支持度都没有大于阈值,即不是频繁项集,三级{A,C,B}或更高级怎么可能是频繁项集呢?如果是的话,{A,B}就一定是频繁项集了,这不和原来的条件矛盾了吗?

首先统计一级候选项集,清除不满足条件的候选集,得到满足条件的一级项集,在生成一级项集的基础上,生成二级项集,得到满足条件的二级项集,在生成三级项集时,再次根据定律2的思想,如,{牛奶,啤酒}不是频繁项集,所以{牛奶,啤酒,尿布},{牛奶,啤酒,面包}都不是频繁项集。

Apriori算法

属于候选消除算法,是一个根据定律2生成候选集、根据支持度和可信度的预置消除不满足条件的候选集,并不断循环直到不再产生候选集的过程。

算法的伪代码:

public void Apriori() { // 获取原始数据记录 record = getRecord(); // 获取第一次的候选集 List<List<String>> candidateItemset = findFirstCandidate(); // 获取候选集candidateItemset 满足支持的集合 List<List<String>> lItemset = getSupportedItemset(candidateItemset ); // 只要能继续挖掘 while (endTag != true) { // 获取下一次的候选集 List<List<String>> ckItemset = getNextCandidate(lItemset); // 获取候选集ckItemset 满足支持的集合 List<List<String>> lkItemset = getSupportedItemset(ckItemset); //得到这一级别的频繁项集 save(IkItemset) // 保存数据,为下次迭代准备 lItemset = lkItemset; }

总结了关联规则挖掘的经典算法Apriori算法,这个算法利用了一个定律:如果一个集合不是频繁项集,则它的所有超集都不是频繁项集,自下而上,挖掘出满足支持度和可信度阈值的所有级别的频繁项集。

本文分享自微信公众号 - 算法channel(alg-channel)

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

原始发表时间:2018-01-04

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏深度学习与数据挖掘实战

干货|社区发现算法FastUnfolding的GraphX实现

现实生活中存在各种各样的网络,诸如人际关系网、交易网、运输网等等。对这些网络进行社区发现具有极大的意义,如在人际关系网中,可以发现出具有不同兴趣、背景的社会团体...

39630
来自专栏天天P图攻城狮

Android 音视频系列:H264视频编码介绍

H264视频编码技术,是对序列帧图像进行压缩的技术。压缩之所以可能,是因为存在冗余数据。

76870
来自专栏算法channel

Spark|有向无环图(DAG)检测

01 — Spark背景介绍 Apache Spark 是专为大规模数据处理而设计的快速通用的计算引擎。Spark 是一种与 Hadoop 相似的开源集群计算环...

64680
来自专栏大数据文摘

手把手|如何用Python绘制JS地图?

643130
来自专栏数据魔术师

运筹学教学 | 十分钟快速掌握最大流算法(附C++代码及算例)

—“运筹教科书到底能给你啥?” —“算法和实现离教科书有多远?” —“问题解决能力到底从哪来?” 今天刚起床就接到了BOSS的 提·问·三·连 小编表示 收到直...

68350
来自专栏大数据风控

R关联规则算法(支持度、自信度、提升度)

关联规则(Association Rules) 用于大量数据中挖掘出有价值的数据项之间的相关关系 常用于用户购物篮分析,使用它来发现顾客的购买习惯 两个...

22580
来自专栏机器之心

资源 | 像「花书」一样排版:Ian Goodfellow「亲授」的高级LaTex教程

机器之心整理 作者: Ian Goodfellow 参与:邱陆陆 当地时间 3 月 1 号,深度学习知名同名教材《Deep Learning》的第一作者 Ian...

469100
来自专栏about云

使用Spark MLlib给豆瓣用户推荐电影

问题导读: 1.常用的推荐算法有哪些? 2.推荐系统是什么样的流程? 3.从这个推荐系统我们能学到什么? 推荐算法就是利用用户的一些行为,通过一些数学算法,推测...

95670
来自专栏数据和云

Thinking in SQL系列之数据挖掘Apriori关联分析再现啤酒尿布神话

编辑手记:SQL做为一种编程语言,能够满足各类数据处理的需要,关键就在于算法与思维方式。以SQL会友,希望结交更多的数据库、数据分析领域的朋友。 作者简介:牛超...

44080
来自专栏编程札记

协同过滤Item-based算法实现电影推荐系统

1.7K30

扫码关注云+社区

领取腾讯云代金券