Apriori

Apriori 是一种挖掘关联规则（association rules）的算法

它通过挖掘频繁项集（frequent item sets）来揭示物品之间的关联关系，被广泛应用到商业挖掘和网络安全等领域中

频繁项集是指经常出现在一起的物品的集合，关联规则暗示着两种物品之间可能存在很强的关系

"购物篮分析"就是一个常见的场景，这个场景可以从消费者交易记录中挖掘商品与商品之间的关联关系，进而通过商品捆绑销售或者相关推荐的方式带来更多的销售量

搞懂关联规则中的几个概念

支持度

是个百分比，它指的是某个商品组合出现的次数与总次数之间的比例。支持度越高，代表这个组合出现的频率越大

在这个例子中，我们能看到“牛奶”出现了4次，那么这5笔订单中“牛奶”的支持度就是4/5=0.8

同样“牛奶+面包”出现了3次，那么这5笔订单中“牛奶+面包”的支持度就是3/5=0.6

置信度

它指的就是当你购买了商品A，会有多大的概率购买商品B

在这个例子中，置信度（牛奶->啤酒）=2/4=0.5，代表如果你购买了牛奶，有多大的概率会购买啤酒？

置信度（啤酒->牛奶）=2/3=0.67，代表如果你购买了啤酒，有多大的概率会购买牛奶？

所以说置信度是个条件概率，就是说在A发生的情况下，B发生的概率是多少

提升度

我们在做商品推荐的时候，重点考虑的是提升度，因为提升度代表的是“商品A的出现，对商品B的出现概率提升的程度”

还是看上面的例子，如果我们单纯看置信度(可乐->尿布)=1，也就是说可乐出现的时候，用户都会购买尿布，那么当用户购买可乐的时候，我们就需要推荐尿布么？

实际上，就算用户不购买可乐，也会直接购买尿布的，所以用户是否购买可乐，对尿布的提升作用并不大。我们可以用下面的公式来计算商品A对商品B的提升度：

提升度(A->B)=置信度(A->B)/支持度(B)

这个公式是用来衡量A出现的情况下，是否会对B出现的概率有所提升

所以提升度有三种可能：

• 提升度(A->B)>1：代表有提升；
• 提升度(A->B)=1：代表有没有提升，也没有下降；
• 提升度(A->B)<1：代表有下降。

Apriori的工作原理

我们把上面案例中的商品用ID来代表，牛奶、面包、尿布、可乐、啤酒、鸡蛋的商品ID分别设置为1-6，上面的数据表可以变为

Apriori算法其实就是查找频繁项集(frequent itemset)的过程，所以首先我们需要定义什么是频繁项集

频繁项集就是支持度大于等于最小支持度(Min Support)阈值的项集，所以小于最小值支持度的项目就是非频繁项集，而大于等于最小支持度的项集就是频繁项集

项集这个概念，英文叫做itemset，它可以是单个的商品，也可以是商品的组合。我们再来看下这个例子，假设我随机指定最小支持度是50%，也就是0.5

首先，我们先计算单个商品的支持度，也就是得到K=1项的支持度：

因为最小支持度是0.5，所以商品4、6是不符合最小支持度的，不属于频繁项集，于是经过筛选商品的频繁项集就变成：

在这个基础上，我们将商品两两组合，得到k=2项的支持度：

我们再筛掉小于最小值支持度的商品组合，可以得到：

我们再将商品进行K=3项的商品组合，可以得到：

再筛掉小于最小值支持度的商品组合，可以得到：

通过上面这个过程，我们可以得到K=3项的频繁项集{1,2,3}，也就是{牛奶、面包、尿布}的组合

Apriori算法的递归流程：

• K=1，计算K项集的支持度；
• 筛选掉小于最小支持度的项集；
• 如果项集为空，则对应K-1项集的结果为最终结果；
• 否则K=K+1，重复1-3步

Apriori的改进算法：FP-Growth算法

Apriori在计算的过程中有以下几个缺点：

• 可能产生大量的候选集。因为采用排列组合的方式，把可能的项集都组合出来了；
• 每次计算都需要重新扫描数据集，来计算每个项集的支持度

所以Apriori算法会浪费很多计算空间和计算时间，为此人们提出了FP-Growth算法，它的特点是：

• 创建了一棵FP树来存储频繁项集。在创建前对不满足最小支持度的项进行删除，减少了存储空间
• 整个生成过程只遍历数据集2次，大大减少了计算量

所以在实际工作中，我们常用FP-Growth来做频繁项集的挖掘，FP-Growth的原理如下：

①. 创建项头表（item header table）

创建项头表的目的是为FP构建及频繁项集挖掘提供索引

这一步的流程是先扫描一遍数据集，对于满足最小支持度的单个项（K=1）按照支持度从高到低进行排序，这个过程中删除了不满足最小支持度的项

项头表包括了项目、支持度，以及该项在FP树中的链表。初始的时候链表为空

②. 构造FP树

FP树的根节点记为NULL节点

整个流程需要再次扫描数据集，对于每一条数据，按照支持度从高到低的顺序进行创建节点（也就是第一步中项头表中的排序结果），节点如果存在就将计数count+1，如果不存在就进行创建。同时在创建的过程中，需要更新项头表的链表

③. 通过FP树挖掘频繁项集

到这里，我们就得到了一个存储频繁项集的FP树，以及一个项头表。我们可以通过项头表来挖掘出每个频繁项集

具体的操作会用到一个概念，叫“条件模式基”，它指的是以要挖掘的节点为叶子节点，自底向上求出FP子树，然后将FP子树的父节点设置为子节点之和，以此类推

我们以“啤酒”的节点为例，从FP树中可以得到一棵FP子树，将父节点的支持度记为子节点之和，得到：

相比于原来的FP树，尿布和牛奶的频繁项集数减少了。这是因为我们求得的是以“啤酒”为节点的FP子树，也就是说，在频繁项集中一定要含有“啤酒”这个项

其中订单1{牛奶、面包、尿布}和订单5{牛奶、面包、尿布、可乐}并不存在“啤酒”这个项，所以针对订单1，尿布->牛奶->面包这个项集就会从FP树中去掉

针对订单5也包括了尿布->牛奶->面包这个项集也会从FP树中去掉，所以以“啤酒”为节点的FP子树，尿布、牛奶、面包项集上的计数比原来少了2

条件模式基不包括“啤酒”节点，或者父节点如果小于最小支持度就会被剪枝，所以“啤酒”的条件模式基为空

同理，我们可以求得“面包”的条件模式基为：

所以可以求得面包的频繁项集为{尿布，面包}，{尿布，牛奶，面包}。同样，我们还可以求得牛奶，尿布的频繁项集，这里就不再计算展示

当然Apriori的改进算法除了FP-Growth算法以外，还有CBA算法、GSP算法，这里就不再介绍

总结

如何使用Apriori工具包

Apriori虽然是十大算法之一，不过在sklearn工具包中并没有它，也没有FP-Growth算法

我们可以到 pypi.org 搜索工具包

pip install efficient-apriori

from efficient_apriori import apriori

# 设置数据集
data = [('牛奶', '面包', '尿布'),
        ('可乐', '面包', '尿布', '啤酒'),
        ('牛奶', '尿布', '啤酒', '鸡蛋'),
        ('面包', '牛奶', '尿布', '啤酒'),
        ('面包', '牛奶', '尿布', '可乐')]

'''
    挖掘频繁项集和频繁规则
    data 数据集
    min_support 最小支持度 0到1
    min_confidence 最小置信度 0到1
'''
itemsets, rules = apriori(data, min_support=0.5, min_confidence=1)

'''
# 频繁项集
{
    1: {
        ('牛奶', ): 4,
        ('面包', ): 4,
        ('尿布', ): 5,
        ('啤酒', ): 3
    },
    2: {
        ('啤酒', '尿布'): 3,
        ('尿布', '牛奶'): 4,
        ('尿布', '面包'): 4,
        ('牛奶', '面包'): 3
    },
    3: {
        ('尿布', '牛奶', '面包'): 3
    }
}

# 关联规则（啤酒、牛奶、面包比较热门，买了这些的人都喜欢买尿布，牛奶和面包通常会组合购买）
[{啤酒} -> {尿布}, {牛奶} -> {尿布}, {面包} -> {尿布}, {牛奶, 面包} -> {尿布}]
'''
print(itemsets)
print(rules)

如何使用FP工具包

没有找到特别好用的FP-Growth工具包，数据量不大的话，用Apriori就可以了