关联规则（二）：Apriori算法

1. 前言

1.1 基本背景

假设我们在经营一家商品种类并不多的杂货店，我们对那些经常在一起被购买的商品非常感兴趣。我们只有 4 种商品：商品0，商品1，商品2和商品3。

那么所有可能被一起购买的商品组合都有哪些？

这些商品组合可能只有一种商品，比如商品0，也可能包括两种、三种或者所有四种商品。我们并不关心某人买了两件商品0 以及四件商品2 的情况，我们只关心他购买了一种或多种商品。

下图显示了物品之间所有可能的组合（格结构 lattice structure）。图中从上往下的第一个集合是Ф，表示空集或不包含任何物品的集合。物品集合之间的连线表明两个或者更多集合可以组合形成一个更大的集合。

可以发现即使对于仅有 4 种物品的集合，也需要遍历数据 15 次。而随着物品数目的增加遍历次数会急剧增长。对于包含N个物品的数据集共有

种项集组合。事实上，出售 10000 或更多种物品的商店并不少见。即使只出售 100 种商品的商店也会有

种可能的项集组合。对于现代的计算机而言，需要很长的时间才能完成运算。

为了降低所需的计算时间，研究人员发现一种所谓的Apriori原理。Apriori原理可以帮我们减少可能感兴趣的项集。Apriori原理是说如果某个项集是频繁的，那么它的所有子集也是频繁的。这个原理直观上并没有什么帮助，但是如果反过来看就有用了，也就是说如果一个项集是非频繁集，那么它的所有超集也是非频繁的。

比如，已知阴影项集{2，3}是非频繁的。利用这个知识，我们就知道项集{0,2,3} ，{1,2,3}以及{0,1,2,3}也是非频繁的。这也就是说，一旦计算出了{2,3}的支持度，知道它是非频繁的之后，就不需要再计算{0,2,3}、{1,2,3}和{0,1,2,3}的支持度，因为我们知道这些集合不会满足我们的要求。

1.2 运行环境

• 操作系统： win10
• python版本：3.7.0
• Anaconda：3.5.1
• mlxtend ：0.15.0.0

2. 基本原理

apriori 在拉丁语中指“来自以前”。当定义问题时,通常会使用先验知识或者假设, 这被称作“一个先验” ( apriori )。

而Apriori算法就是基于一个先验：

如果某个项集是频繁的，那么它的所有子集也是频繁的。

初看可能这一条先验没有多大的作用，但是它的逆反，就很有实用意义了：

如果某一个项集是非频繁的，那么它的所有超集（包含该集合的集合）也是非频繁的。

Apriori算法的实现过程就和我们前文所说的过程一样，分为两步：

1. 训练算法：找到频繁项集

2. 使用算法：使用频繁项集生成关联规则

两个步骤都都基于Apriori的先验原理。

2.1 发现频繁项集

实现过程如下图所示

1. 由数据集生成候选项集C1（ 1 表示每个候选项仅有一个数据项）；再由C1通过最小支持度过滤，生成频繁项集L1（1 表示每个频繁项仅有一个数据项）。

2. 将频繁项集 L1 的数据项两两拼接成 候选项集C2。

3. 从候选项集C2开始，通过最小支持度过滤生成 频繁项集L2。

……

4. 直到 Lk 中仅有一个或没有数据项为止

2.2 生成关联规则

关联规则的生成也是使用逐层方法，初始提取规则后件只有一个项的所有高置信度规则，对这些规则进行测试——使用最小置信度，接下来合并剩下的规则来创建一个新的规则列表，不断增加后件的项数，直到候选规则列表为空。

比如，如果{123} →{0} ，{023} →{1} 和 {013} →{2} 是高置信度的规则，则通过合并规则的后件产生候选规则，如果格中的任意结点置信度较低，则根据定理应该剪去该枝，比如{012} →{3}为置信度低节点，则前件{012} 的任意子集构成的规则，即图中灰色规则，都为低置信度节点，无需再做最小置信度检验。

3. 参数详解

关联规则的发现，我们使用 mlxtend 包，他是由Sebastian Raschka开发的一个工具集，初衷也是写下一些在其他包中没有找到的特定算法，是一个机器学习扩展工具库。

3.1 支持度计算

对频繁项集的发现基于支持度的计算，基于 apriori 方法

• df ：传入的数据需要是 pandas dataframe 格式，并且是已经经过热编码的（如上图所示）
• min_support : 最小支持度 （即支持度阈值）
• use_colnames : 是否使用列名，实际上因为是热编码的数据，因此列名就是商品名（项目名），如果设置为 False ，那么会使用索引来代替
• max_len : 项集的最大长度，也就是项集中项目的最大个数
• n_jobs : 使用的计算资源，这个参数和 sklearn 中应该是一致的，即指定计算时可使用的最大核心数
• 返回值：返回值也是 dataframe 格式，由 支持度 和 项集 两列构成，各数据记录都是满足最小支持度和项集最大长度条件的

3.2 置信度检验

关联规则的发现则基于置信度的计算，基于 association_rules 方法

• df ：dataframe 格式，数据内容为与apriori方法输出内容相同格式的数据
• metric : 判定标准，默认状态下计算支持度、置信度和提升度。当support_only 参数为 True 时，则只计算置信度
• min_threshold： metric 参数的阈值
• support_only ：如果为True，则只计算置信度，其他metric中的判定标准将都会设置为 NaN （即空值）

4. 演示案例

使用 UCI 数据库中的毒蘑菇数据集，找出毒蘑菇的一些关联特征

http://archive.ics.uci.edu/ml/datasets/Mushroom

看下数据信息：

1个标签字段，确定是否是毒蘑菇，22个特征字段

数据文件 agaricus-lepiota.data 都使用了简写

首先定义一个数据获取方法，读取数据后将数据独热编码之后备用

 1def get_data():
 2    # 读取数据
 3    data = pd.read_csv(os.path.join(os.getcwd(),'data','agaricus-lepiota.data'),header=None)
 4    # 筛选出毒蘑菇
 5    data = data.loc[data.iloc[:,0] == 'p',1:]
 6    # 重置下行索引
 7    data.reset_index(drop=True,inplace=True)
 8    # 将数据转化为 热编码
 9    data = pd.get_dummies(data)
10    return data

此时的数据，含3916条记录，特征数变为了93

下面就可以直接调用 apriori() 方法来发现频繁项集

1frequent_sets = apriori(data, min_support=0.7,use_colnames=True,max_len=2)

先使用min_support = 0.3 试了下，发现产生的频繁项集过多，然后使用 0.7 发现了 27 条满足规则的项集

最后调用 association_rules() 方法来找到关联规则，因为结果属性比较多，我们将结果输出到excel

1rules = association_rules(frequent_sets, min_threshold=1)
2rules.to_excel('./data/rules.xlsx',index=False)

就得到了如下结果

现在我们再根据结果中项的名称（数字表示第几个特征，字母表示特征值），去数据集中找到相应文字描述即可。

比如第一条规则 {4_f} → {16_p} ，找到 4_f 为 bruises?--no , 16_p 为veil-type--partial ，也就是说如果 bruises 为 no， 那么 veil-type 必然是为partial 而不是 universal （因为我们设置了置信度为1）

该方法还给了 leverage 和 conviction 两个评价指标，都和 confidence 和 lift 差不多，具体的定义可在官方API 中找到。

本文完整代码：

https://github.com/firewang/lingweilingyu/tree/master/associationRules

参考网址：

• http://www.cnblogs.com/beaver-sea/p/4740830.html
• http://www.cnblogs.com/beaver-sea/p/4740774.html
• https://blog.csdn.net/lytangus/article/details/80289958
• http://rasbt.github.io/mlxtend/user_guide/frequent_patterns/apriori/
• http://rasbt.github.io/mlxtend/api_subpackages/mlxtend.frequent_patterns/
• https://www.cnblogs.com/ybjourney/p/4847489.html
• 《机器学习实战》