Apriori算法
常用关联规则算法如表所示。
表 常用关联规则算法
以超市销售数据为例，当存在很多商品时，可能的商品组合（规则的前项与后项）数目会达到一种令人望而却步的程度，这是提取关联规则的最大困难。因而各种关联规则分析算法从不同方面入手减小可能的搜索空间的大小以及减少扫描数据的次数。Apriori[1]算法是最经典的挖掘频繁项集的算法，第一次实现了在大数据集上可行的关联规则提取，其核心思想是通过连接产生候选项与其支持度，然后通过剪枝生成频繁项集。
1.关联规则和频繁项集
（1）关联规则的一般形式
项集A、B同时发生的概率称为关联规则的支持度（也称相对支持度），如式（5-33）所示。
项集A发生，则项集B发生的概率为关联规则的置信度，如式（5-34）所示。
（2）最小支持度和最小置信度
最小支持度是用户或专家定义的衡量支持度的一个阈值，表示项目集在统计意义上的最低重要性；最小置信度是用户或专家定义的衡量置信度的一个阈值，表示关联规则的最低可靠性。同时满足最小支持度阈值和最小置信度阈值的规则称作强规则。
（3）项集
项集是项的集合。包含k个项的项集称为k项集，如集合{牛奶，麦片，糖}是一个3项集。
项集的出现频率是所有包含项集的事务计数，又称作绝对支持度或支持度计数。如果项集I的相对支持度满足预定义的最小支持度阈值，则I是频繁项集。频繁k项集通常记作Lk。
（4）支持度计数
项集A的支持度计数是事务数据集中包含项集A的事务个数，简称为项集的频率或计数。
已知项集的支持度计数，则规则的支持度和置信度很容易从所有事务计数、项集A和项集的支持度计数推出式（5-35）和式（5-36），其中N表示总事务个数，σ表示计数。
也就是说，一旦得到所有事务个数，A、B和的支持度计数，就可以导出对应的关联规则和，并可以检查该规则是否是强规则。
在Python中实现上述Apriori算法的代码如代码清单5-7所示。其中，我们自行编写了Apriori算法的函数apriori.py。读者有需要的时候可以直接使用，此外可以参考代码读懂实现过程。
代码清单5-7 使用Apriori算法挖掘菜品订单关联规则
from __future__ import print_function import pandas as pd from apriori import * # 导入自行编写的apriori函数 inputfile = '../data/menu_orders.xls' outputfile = '../tmp/apriori_rules.xls' # 结果文件 data = pd.read_excel(inputfile, header=None) print('\n转换原始数据至0-1矩阵...') ct = lambda x : pd.Series(1, index=x[pd.notnull(x)]) # 转换0-1矩阵的过渡函数 b = map(ct, data.values) # 用map方式执行 data = pd.DataFrame(list(b)).fillna(0) # 实现矩阵转换，空值用0填充 print('\n转换完毕。') del b # 删除中间变量b，节省内存 support = 0.2 # 最小支持度 confidence = 0.5 # 最小置信度 ms = '---' # 连接符，默认'--'，用来区分不同元素，如A--B。 需要保证原始表格中不含有该字符 find_rule(data, support, confidence, ms).to_excel(outputfile) # 保存结果 |
运行代码清单5-7的结果如下：
support confidence
e---a 0.3 1.000000
e---c 0.3 1.000000
c---e---a 0.3 1.000000
a---e---c 0.3 1.000000
a---b 0.5 0.714286
c---a 0.5 0.714286
a---c 0.5 0.714286
c---b 0.5 0.714286
b---a 0.5 0.625000
b---c 0.5 0.625000
b---c---a 0.3 0.600000
a---c---b 0.3 0.600000
a---b---c 0.3 0.600000
a---c---e 0.3 0.600000
其中，“e---a”表示e发生能够推出a发生，置信度为100%，支持度为30%；“b---c---a”表示b、c同时发生时能够推出a发生，置信度为60%，支持度为30%等。搜索出来的关联规则不一定具有实际意义，需要根据问题背景筛选适当的有意义的规则，并赋予合理的解释。
2、Apriori算法：使用候选产生频繁项集
Apriori算法的主要思想是找出存在在于事务数据集中最大的频繁项集，再利用得到的最大频繁项集与预先设定的最小置信度阈值生成强关联规则。
（1）Apriori的性质
频繁项集的所有非空子集也必须是频繁项集。根据该性质可以得出：向不是频繁项集I的项集中添加事务A，新的项集一定也不是频繁项集。
（2）Apriori算法实现的两个过程
①找出所有的频繁项集（支持度必须大于等于给定的最小支持度阈值），在这个过程中连接步和剪枝步互相融合，最终得到最大频繁项集Lk。
a.连接步
连接步的目的是找到K项集。对给定的最小支持度阈值，分别对1项候选集C1，剔除小于该阈值的项集得到1项频繁集L1；下一步由L1自身连接产生2项候选集C2，保留C2中满足约束条件的项集得到2项频繁集，记为L2；再下一步由L2与L1连接产生3项候选集C3，保留C2中满足约束条件的项集得到3项频繁集，记为L3……这样循环下去，得到最大频繁项集Lk。
b.剪枝步
剪枝步紧接着连接步，在产生候选项Ck的过程中起到减小搜索空间的目的。由于Ck是Lk-1与L1连接产生的，根据Apriori的性质：频繁项集的所有非空子集也必须是频繁项集，所以不满足该性质的项集将不会存在于Ck中，该过程就是剪枝。
②由频繁项集产生强关联规则。由过程①可知，未超过预定的最小支持度阈值的项集已被剔除，如果剩下这些规则又满足了预定的最小置信度阈值，那么就挖掘出了强关联规则。
下面将结合餐饮行业的实例来讲解Apriori关联规则算法挖掘的实现过程。数据库中部分点餐数据如表所示。
表 数据库中部分点餐数据
首先将表中的事务数据（一种特殊类型的记录数据）整理成关联规则模型所需的数据结构，从中抽取10个点餐订单作为事务数据集，设支持度为0.2（支持度计数为2），为方便起见将菜品{18491，8842，8693，7794，8705}分别简记为{a，b，c，d，e}）如表所示。
表 某餐厅事务数据集
算法过程如图所示。
图 Apriori算法实现过程
过程一：找最大k项频繁集
①算法简单扫描所有的事务，事务中的每一项都是候选1项集的集合C1的成员，计算每一项的支持度。比如
②对C1中各项集的支持度与预先设定的最小支持度阈值进行比较，保留大于或等于该阈值的项，得1项频繁集L1。
③扫描所有事务，L1与L1连接得候选2项集C2，并计算每一项的支持度。如P（{a，b}）=。接下来是剪枝步，由于C2的每个子集（即L1）都是频繁集，所以没有项集从C2中剔除。
④对C2中各项集的支持度与预先设定的最小支持度阈值进行比较，保留大于或等于该阈值的项，得2项频繁集L2。
⑤扫描所有事务，L2与L1连接得候选3项集C3，并计算每一项的支持度，如P（{a，b，c}）=。接下来是剪枝步。L2与L1连接的所有项集为：{a，b，c}，{a，b，d}，{a，b，e}，{a，c，d}，{a，c，e}，{b，c，d}，{b，c，e}，根据Apriori算法，频繁集的所有非空子集也必须是频繁集，因为{b，d}，{b，e}，{c，d}不包含在b项频繁集L2中，即不是频繁集，应剔除，最后C3中的项集只有{a，b，c}和{a，c，e}。
⑥对C3中各项集的支持度与预先设定的最小支持度阈值作比较，保留大于或等于该阈值的项，得3项频繁集L3。
⑦L3与L1连接得候选4项集C4，剪枝后为空集。最后得到最大3项频繁集{a，b，c}和{a，c，e}。
由以上过程可知L1，L2，L3都是频繁项集，L3是最大频繁项集。
过程二：由频繁集产生关联规则
根据式（5-36），尝试基于该例产生关联规则。
Python程序输出的关联规则如下：
Rule (Support, Confidence)
e -> a (30%, 100%)
e -> c (30%, 100%)
c,e -> a (30%, 100%)
a,e -> c (30%, 100%)
a -> b (50%, 71.4286%)
c -> a (50%, 71.4286%)
a -> c (50%, 71.4286%)
c -> b (50%, 71.4286%)
b -> a (50%, 62.5%)
b -> c (50%, 62.5%)
b,c -> a (30%, 60%)
a,c -> b (30%, 60%)
a,b -> c (30%, 60%)
a,c -> e (30%, 60%)
就第一条输出结果进行解释：顾客同时点菜品e和a的概率是50%，点了菜品a，再点菜品b的概率是100%。知道了这些，就可以对顾客进行智能推荐，增加销量的同时满足顾客需求。
实验所需代码
