机器学习实战：Apriori算法

直接Hello，大家好！我是MPIG2018级研究生刁金辉。今天给大家带来的是Apriori算法相关内容的介绍。从数据海洋中，寻找物品的不同组合是一项十分耗时的任务，所需的代价很高，蛮力搜索的方法并不能解决这个问题，所以需要用更智能的方法在合理的时间范围内找到频繁的项以及频繁项之间的关联，所以接下来带大家详细介绍Apriori算法。

首先我们看下本章主要内容：

1.Apriori算法的讲解

2. 使用Apriori算法来发现频繁项集

3. 从频繁项集中挖掘关联规则

4. Apriori挖掘关联规则算法的改进

一.Apriori算法的讲解

Apriori算法就是在海量的数据做关联分析，从而找到频繁项集和关联规则，

频繁项集：经常出现在一块物品的集合。

关联规则：暗示频繁项集物品之间可能存在很强的关联。

下面用一个例子来说明这两种概念：图中给出了购物清单。

频繁项集是指那些经常出现在一起的商品集合，图中的集合就是频繁项集的一个例子。从这个数据集中也可以找到诸如面包->牛奶的关联规则，即如果有人买了面包，那么他很可能也会买牛奶。

在购物清单的例子中，考虑规则→。由于项集的支持度计数为2，而事务的总数为5，所以规则的支持度为2/5=0.4。

规则的置信度是项集的支持度计数与项集支持度计数的商，由于存在3个事务同时包含牛奶和尿布，所以规则的置信度为2/3=0.67。

我们用支持度(support): 数据集中包含该项集的记录所占的比例，support(A,B)= （A,B)同时发生的个数/数据集的总个数

关联规则：暗示项集物品之间可能存在很强的关联，我们用可信度来表示

(confidence): 经常出现的项集中，物品之间的关系，形如A ==> B，confidence(A==>B) = support(A,B) / support(A)。

Apriori算法的过程：

(1) 收集数据

(2) 使用 Apriori 算法来找到频繁项集

(3) 用于发现频繁项集中物品之间的关联规则

二.使用Apriori算法来发现频繁集

定律1：如果某个项集是频繁项，那么它所有的子集也是频繁项

定律2：如果一个项集是非频繁项，那么他的所有超集也是非频繁项已知阴影

如图，若项集是非频繁的。利用这个定律，我们就知道项集，以及也是非频繁的。也就是说，一旦计算出了的支持度，知道它是非频繁的后，就可以紧接着排除、和。

使用Apriori算法来发现频繁项集的算法核心：

1 对给定的最小支持与数据集，从数据集中分离出为1项的最小候选集C1，剔除小于支持度的项集得到1项频繁集L1;

2 L1自身连接产生2项候选集C2，保留C2中满足约束条件的项集得到2项集L2；

3 L2自身连接产生2项候选集C3，保留C3中满足约束条件的项集得到2项集L3；

4 循环下去，得到最大频繁项集Lk；

相关例子来说明算法过程：

最开始数据库里有 D ={，，，，} 使用 min_support=2 作为支持度阈值，算法过程如下：

使用Apriori算法来发现L1频繁集：

一 生成C1候选项集(伪代码)：

遍历数据集中的每个transaction:

遍历每个transaction中的元素item：

检查一下 item是否在列表C1中：

如果不是，则在C1中增加item

二 从候选项集得到频繁项集(伪代码)：

遍历数据集中的每条数据tran：

遍历每个候选项集can：

检查can是否是tran的子集：

如果是，则增加can的计数值

基于python的Apriori算法来发现L1频繁集：

运行的结果如下：

L1的候选项集: [frozenset(), frozenset(), frozenset(), frozenset()]

支持度: ): 0.5, frozenset(): 0.75, frozenset(): 0.25, frozenset(): 0.75, frozenset(): 0.75}

完整的Apriori算法的伪代码如下：

当集合中项的个数大于 0 时：

构建一个K项组成的候选项集的列表

检查数据以确认每个项集都是频繁的

保留频繁项集并构建K+1项组成的候选项集的列表

基于python的完整的Apriori算法：

运行的结果如下：

L的候选项集: [[frozenset(), frozenset(), frozenset(), frozenset()], [frozenset(), frozenset(), frozenset(), frozenset()], [frozenset()], []]

支持度: ): 0.5, frozenset(): 0.75, frozenset(): 0.25, frozenset(): 0.75, frozenset(): 0.75, frozenset(): 0.5, frozenset(): 0.75, frozenset(): 0.5, frozenset(): 0.5, frozenset(): 0.25, frozenset(): 0.25, frozenset(): 0.5}

三. 从频繁项集中挖掘关联规则

频繁项集 I = ，如果某 条 规则 并 不 满 足最 小 可 信 度 要 求 ,那 么 该 规则 的 所 有 子 集 也 不 会 满 足 最 小 可信 度 要 求以图为例，假设规则 ➞ 并不满足最小可信度要求，那么就知道任何左部为子集的规则也不会满足最小可信度要求。可以利用关联规则的上述性质属性来减少需要测试的规则数目 。

基于python的挖掘关联规则算法：

运行结果如下：

frozenset() --> frozenset() conf: 1.0

frozenset() --> frozenset() conf: 1.0

frozenset() --> frozenset() conf: 1.0

四.Apriori挖掘关联规则算法的改进

1. 问题的提出：

我们在其中计算通过生成的关联规则，可以根据支持度发现关联规则➞和➞的可信度都应该为1.0的，但是在运行结果中并没有体现出来这样的推算结果。

2. 通过分析程序代码，我们可以发现：

当i = 1时，generateRules()函数直接调用了calcConf()函数直接计算其可信度，因为这时L[1]中的频繁项集均包含两个元素，可以直接生成和判断候选关联规则。比如L[1]中的，生成的候选关联规则为➞、➞，这样就可以就对两个元素的关联规则了。

当i > 1时，generateRules()函数直接调用了rulesFromConseq()函数，这时L[i]中至少包含3个元素，如，对候选关联规则的生成和判断的过程需要分层进行，但是这里却没有。函数必须将初始的H1（表示初始关联规则的右部，即箭头右边的部分）作为参数传递给了rulesFromConseq()函数，通过直接调用calcConf()函数计算生成H1生成的规则集。

3. 在i>1时，将对H1调用calcConf()的过程加上就可以了，代码如下：

运行结果如下：

frozenset() --> frozenset() conf: 1.0

frozenset() --> frozenset() conf: 1.0

frozenset() --> frozenset() conf: 1.0

frozenset() --> frozenset() conf: 1.0

frozenset() --> frozenset() conf: 1.0

想要更加详细了解本讲更多细节的内容吗？那就一起来观看下面的Presentation的具体讲解吧：