Question

Apriori算法的主要思想是找出存在于事务数据集中的最大的频繁项集，在利用得到的最大频繁项集与预先设定的最小置信度阈值生成强关联规则。

（1）Apriori的性质

频繁项集的所有非空子集也必须是频繁项集。根据该性质可以得出：向不是频繁项集I的项集中添加事务A，新的项集I∪A一定也不是频繁项集。

（2）Apriori算法实现的两个过程如下。

1）找出所有的频繁项集（支持度必须大于等于给定的最小支持度阈值），在这个过程中连接步和剪枝步互相融合，最终得到最大频繁项集L_k。

连接步：

连接步的目的是找到K项集。对给定的最小支持度阈值，分别对1项候选集C₁，剔除小于该阈值的项集得到1项频繁集L₁；下一步由L₁自身连接产生2项候选集C₂，保留C₂中满足约束条件的项集得到2项频繁集，记为L₂；再下一步由L₂与L₃连接产生3项候选集C₃，保留C₂中满足约束条件的项集得到3项频繁集，记为L₃……这样循环下去，得到最大频繁项集L_k。

剪枝步：

剪枝步紧接着连接步，在产生候选项C_k的过程中起到减小搜索空间的目的。由于C_k是L_k-1与L₁连接产生的，根据Apriori的性质频繁项集的所有非空子集也必须是频繁项集，所以不满足该性质的项集不会存在于C_k中，该过程就是剪枝。

2）由频繁项集产生强关联规则：由过程1）可知未超过预定的最小支持度阈值的项集已被剔除，如果剩下这些规则又满足了预定的最小置信度阈值，那么就挖掘出了强关联规则。

下面将结合餐饮行业的实例来讲解Apriori关联规则算法挖掘的实现过程。数据库中部分点餐数据见表5-18。

表5-18　数据库中部分点餐数据

将表5-18中的事务数据（一种特殊类型的记录数据）整理成关联规则模型所需的数据结构，从中抽取10个点餐订单作为事务数据集，设支持度为0.2（支持度计数为2），为方便起见将菜品{18491，8842，8693，7794，8705}分别简记为{a，b，c，d，e}，见表5-19。

表5-19　某餐厅事务数据集

算法过程如图5-16所示。

过程一：找最大k项频繁集

1）算法简单扫描所有的事务，事务中的每一项都是候选1项集的集合C₁的成员，计算每一项的支持度。例如，。

2）对C₁中各项集的支持度与预先设定的最小支持度阈值进行比较，保留大于或等于该阈值的项，得1项频繁集L₁。

图5-16　Apriori算法实现过程

3）扫描所有事务，L₁与L₁连接得候选2项集C₂，并计算每一项的支持度。如P（{a，b}）=。接下来是剪枝步，由于C₂的每个子集（即L₁）都是频繁集，所以没有项集从C₂中剔除。

4）对C₂中各项集的支持度与预先设定的最小支持度阈值进行比较，保留大于或等于该阈值的项，得2项频繁集L₂。

5）扫描所有事务，L₂与L₁连接得候选3项集C₃，并计算每一项的支持度，如P（{a，b，c}）=。接下来是剪枝步，L₂与L₁连接的所有项集为：{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项频繁集L₂中，即不是频繁集，应剔除，最后的C₃中的项集只有{a，b，c}和{a，c，e}；

6）对C₃中各项集的支持度与预先设定的最小支持度阈值进行比较，保留大于或等于该阈值的项，得3项频繁集L₃。

7）L₃与L₁连接得候选4项集C₄，易得剪枝后为空集。最后得到最大3项频繁集{a，b，c}和{a，c，e}。

由以上过程可知L₁，L₂，L₃都是频繁项集，L₃是最大频繁项集。

过程二：由频繁集产生关联规则

置信度的计算公式如下。

其中，Support_count（A∩B）是包含项集A∩B的事务数，Support_count（A）是包含项集A的事务数，根据该公式，尝试基于该例产生关联规则。

Python程序输出的关联规则如下。

Rule　（Support，Confidence）

a→b　（50%，71.4286%）

b→a　（50%，62.5%）

a→c　（50%，71.4286%）

c→a　（30%，71.4286%）

b→c　（50%，62.5%）

c→b　（50%，71.4286%）

e→a　（30%，100%）

e→c　（30%，100%）

a，b→c　（30%，60%）

a，c→b　（30%，60%）

b，c→a　（30%，60%）

e→a，c　（30%，100%）

a，c→e　（30%，60%）

a，e→c　（30%，100%）

c，e→a　（30%，100%）

d→b　（20%，100%）

就第一条输出结果进行解释：客户同时点菜品a和b的概率是50%，点了菜品a，再点菜品b的概率是71.4286%。知道了这些，就可以对顾客进行智能推荐，增加销量同时满足客户需求。