小伙伴们，继续一起学习机器学习算法啦，今天学习关联分析、Apriori算法啦！大家肯定很熟悉一个故事-沃尔玛超市数据总结出的啤酒与尿布的相关性（知乎上也有牛人们在讨论这个故事的真假）

图1

来自《机器学习实战》这本书里提到的一个例子，展示了如下的一个购物清单：

图2

在上述购物交易单中发现，{尿布，葡萄酒}出现的次数较多，辣么，他们之间真的有木有关系呢？这就需要关联分析。

关联分析：在大规模数据集中寻找有趣关系的任务。这些关系可以有两种形式：频繁项集或者关联规则。频繁项集(frequent item sets)是指经常出现在一起的物品的集合，关联关系(association rules)暗示两种物品之间可能存在很强的关系。比如上面的{尿布，葡萄酒}就频繁出现，他们之间可能存在一些关系，辣么，如何来确定是否是频繁项集呢？主要是依靠支持度和可信度。

一个项集的支持度(support)被定义为数据集中包含该项集的记录所占的比例。比如，图2中{豆奶}的支持度为4/5。支持度是针对项集来说的，因此可以定义一个最小支持度，而只保留满足最小支持度的项集。可信度或置信度(confidence)是针对一条诸如{尿布}->{葡萄酒}的关联关系来定义的。这条规则的可信度被定义为“支持度({尿布，葡萄酒})/支持度({尿布})”

可是，如何计算一个集合中的频繁项集的支持度，首先需要遍历全部可能的项集，比如针对一个包含了4个产品的集合，那么购买该集合产品的可能集合数目为2^4-1=15，而针对包含N项的集合，就需要遍历2^N-1。显然，这样的计算量很大。因此，出现了Apriori原理。

Apriori原理：如果某个项集是频繁的，那么它的所有子集也是频繁的。该定理的逆反定理为：如果某一个项集是非频繁的，那么它的所有超集（包含该集合的集合）也是非频繁的。Apriori原理的出现，可以在得知某些项集是非频繁之后，不需要计算该集合的超集，有效地避免项集数目的指数增长，从而在合理时间内计算出频繁项集。

Apriori算法实现：Apriori算法是发现频繁项集的一种方法。Apriori算法的两个输入参数分别是最小支持度和数据集。该算法首先会生成所有单个物品的项集列表->接着扫描交易记录来查看哪些项集满足最小支持度要求，其中不满足最小支持度的集合会被去掉->然后对剩下的集合进行组合以生成包含两个数据集的项集->接着重新扫描交易记录，去掉不满足最小支持度的项集->该过程重复进行直到所有项集都被滤掉。

Apriori算法Python编程

1）准备数据

图3

在图2中提到的createC1()函数中的C1指的是最原始的待选项集，也就是所有单个物品的项集列表；为什么这里将C1转换为frozenset，而不是一般额set呢，简单解释：

set无序排序且不重复，是可变的，有add()，remove()等方法。既然是可变的，所以它不存在哈希值。基本功能包括关系测试和消除重复元素. 集合对象还支持union(联合), intersection(交集), difference(差集)和sysmmetric difference(对称差集)等数学运算。sets 支持 x in set, len(set),和 for x in set 。作为一个无序的集合，sets不记录元素位置或者插入点。因此，sets不支持 indexing, 或其它类序列的操作。

frozenset是冻结的集合，它是不可变的，存在哈希值，好处是它可以作为字典的key，也可以作为其它集合的元素。缺点是一旦创建便不能更改，没有add，remove方法。详情见set与frozenset

2)过滤函数：根据待选项集Ck的情况，判断数据集D中Ck元素的出现频率，过滤掉低于最低支持度的项集。

图4

3）当待选项集不是单个元素时，比如K>=2的情况下，合并元素时容易出现出现重复，因此针对包含K个元素的频繁项集，对比每个频繁项集第K-2位是否一致。详情如下：

图5

图6

4）Apriori算法核心

图7

基于上述算法，仿真得到，不同的最小支持度得到的频繁项集是不同的。

当minSupport=0.5时，得到的频繁项集是：[[frozenset([1]), frozenset([3]), frozenset([2]), frozenset([5])], [frozenset([1, 3]), frozenset([2, 5]), frozenset([2, 3]), frozenset([3, 5])], [frozenset([2, 3, 5])], []]

当minSupport=0.7时，得到的频繁项集是：[[frozenset([3]), frozenset([2]), frozenset([5])], [frozenset([2, 5])], []]；

实际每个项集的支持度为：{frozenset([5]): 0.75, frozenset([3]): 0.75, frozenset([3, 5]): 0.5, frozenset([4]): 0.25, frozenset([2, 3]): 0.5, frozenset([2, 5]): 0.75, frozenset([1]): 0.5, frozenset([2]): 0.75}

基于Apriori算法，从频繁项集挖掘关联规则

基于Apriori算法可以获得频繁项，基于这些频繁项集可以产生很多关联规则。如果能够减少规则数目来确保问题的可解性，可以较大的减少计算复杂度。易知，如果某条规则不满足最小可信度要求，那么该规则的所有子集也不会满足最小可信度要求。利用关联规则的上述性质，基于Apriori算法，首先从一个频繁项集开始，接着创建一个规则列表，其中规则右部只包含一个元素，，然后对这些规则进行测试。接下来合并所有的剩余规则列表来创建一个新的规则列表，其中规则右部包含两个元素。这种方法称作分级法。

图8

图9 针对图8张函数说明

好哒，关于Apriori算法的初步学习基本到这里，希望对大家有用，欢迎大牛不吝赐教哈，各位朋友，晚安、早安啦~~