Apriori算法详解

Apriori算法总结

一、背景

关联规则学习（Association rule learning）是一种在大型数据库中发现变量之间的有趣性关系的方法。它的目的是利用一些有趣性的量度来识别数据库中发现的强规则。

关联分析是一种在大规模数据集中寻找有趣关系的任务。这些关系可以有两种形式:频繁项集或者关联规则。频繁项集(frequent item sets)是经常出现在一块的物品的集合,关联规则(association rules)暗示两种物品之间可能存在很强的关系。

二、理论

当寻找频繁项集时,频繁(frequent)的定义是什么?

最重要的是支持度和可信度。

1、一个项集的支持度(support)

被定义为数据集中包含该项集的记录所占的比例。支持度是针对项集来说的,因此可以定义一个最小支持度,而只保留满足最小支持度的项集。

2、可信度或置信度(confidence)

是针对一条诸如{尿布} ➞ {啤酒}的关联规则来定义的。这条规则的可信度被定义为“支持度({尿布, 啤酒})/支持度({尿布})”。

假设{尿布, 啤酒}的支持度为3/5,尿布的支持度为4/5,则“尿布 ➞ 啤酒”的可信度为3/4=0.75。简单来说，就是用户购买尿布的事件中包含“购买尿布和啤酒”的比率。这意味着对于包含“尿布”的所有记录,我们的规则对其中75%的记录都适用。

3、Lift（提升度）：表示“包含A的事务中同时包含B事务的比例”与“包含B事务的比例”的比值。公式表达：Lift=( P(A&B)/P(A))/P(B)=P(A&B)/P(A)/P(B)。提升度反映了关联规则中的A与B的相关性，提升度>1且越高表明正相关性越高，提升度<1且越低表明负相关性越高，提升度=1表明没有相关性。

为了减少频繁项集的生成时间，可以尽早的消除一些完全不可能是频繁项集的集合，用到Apriori的两条定律。

Apriori定律1：如果一个集合是频繁项集，则它的所有子集都是频繁项集。举例：假设一个集合{A,B}是频繁项集，即A、B同时出现在一条记录的次数大于等于最小支持度min_support，则它的子集{A},{B}出现次数必定大于等于min_support，即它的子集都是频繁项集。

Apriori定律2：如果一个集合不是频繁项集，则它的所有超集都不是频繁项集。举例：假设集合{A}不是频繁项集，即A出现的次数小于min_support，则它的任何超集如{A,B}出现的次数必定小于min_support，因此其超集必定也不是频繁项集。

三、算法流程

接下来可以看Apriori算法的简单流程：

数据集：

[ [面包，牛奶],

[面包，尿布，啤酒，鸡蛋],

[牛奶，尿布，啤酒，可乐],

[面包，牛奶，尿布，啤酒],

[面包，牛奶，尿布，可乐] ]

流程如下：

得到频繁项集之后，再由频繁项集中可以得到强关联规则（满足最小支持度和最小置信度的关联规则）。这里我没有找到流程图，于是直接从程序运行截图来看：

这是我设定支持度为0.3，得到的所有频繁集：

之后对规则进行分析，从二项集开始计算，以下是生成的关联规则进行分析：

接下来是三项集，举个例子：

即是说，对一个频繁项集，会先找出所有子集，再在循环每次分析一个子集与原项集去除该子集剩下的数据的置信度和提升度，进行对比，此时我若设定置信度大于0.7，提升度大于1，则最终结果如下：

举例说明一下lift的作用：

比如说，之前的例子中，总事件5件，购买牛奶的4个，购买尿布的有四个，两种都买的有三个，所以牛奶(A)的支持度P(A)=0.8，而牛奶(A)对尿布(B)的置信度为包含A的事务中同时包含B的占包含A的事务比例，为0.75，置信度看起来挺高的，但其实不可取，因为在没有任何条件下，B事务的出现的比例是0.8，也就是说设置了A事务出现这个条件，B事务出现的比例反而降低了。这说明A事务和B事务是排斥的。

通俗来讲,就是说,B事务不是因为A事务出现而出现,有可能是B事务本身出现的次数就很多.比如说,B事务在所有的事务集里都出现了,也就是说出现的概率为1了,还能说是因为A事务出现,B事务才出现吗?

四、算法学习总结

1、当每一个事件出现物品很多时，如果支持度、置信度阈值设置太低，关联规则会特别多，得到的结果没有价值；

eg. 数据为：

[[1,3,9,13,23,25,34,36,38,40,52,54,59,63,67,76,85,86,90,93,98,107,113],[2,3,9,14,23,26,34,36,39,40,52,55,59,63,67,76,85,86,90,93,99,108,114],[2,4,9,15,23,27,34,36,39,41,52,55,59,63,67,76,85,86,90,93,99,108,115],[1,3,10,15,23,25,34,36,38,41,52,54,59,63,67,76,85,86,90,93,98,107,113],[2,3,9,16,24,28,34,37,39,40,53,54,59,63,67,76,85,86,90,94,99,109,114],[2,3,10,14,23,26,34,36,39,41,52,55,59,63,67,76,85,86,90,93,98,108,114],[2,4,9,15,23,26,34,36,39,42,52,55,59,63,67,76,85,86,90,93,98,108,115],[2,4,10,15,23,27,34,36,39,41,52,55,59,63,67,76,85,86,90,93,99,107,115],[1,3,10,15,23,25,34,36,38,43,52,54,59,63,67,76,85,86,90,93,98,110,114]]

2、当有很多个事件时，若每个事件的物品很少，支持度、置信度阈值设置太高，关联规则会特别少，这个时候得到的结果也是没有价值；

3、故而，我觉得在初始数据和支持度、置信度之间，是要通过实际测试以及考虑预期结果来获得几个比较好的参数，也即是说，即便是Apriori这种相对其他复杂算法较为经典且基础的算法也是需要调参的。

版权声明：本文来源CSDN，感谢博主原创文章，遵循 CC 4.0 by-sa 版权协议，转载请附上原文出处链接和本声明。
原文链接：https://blog.csdn.net/weixin_39220714/article/details/83595519
站方申明：本站部分内容来自社区用户分享，若涉及侵权，请联系站方删除。

发表于 2020-06-06 09:32:52

阅读 ( 1920 )