先验算法

在计算机科学以及数据挖掘领域中， 先验算法（Apriori Algorithm）^[1]是关联规则学习的经典算法之一。先验算法的设计目的是为了处理包含交易信息内容的数据库（例如,顾客购买的商品清单，或者网页常访清单。）而其他的算法则是设计用来寻找无交易信息（如Winepi算法和Minepi算法）或无时间标记（如DNA测序）的数据之间的联系规则。

在关联式规则中,一般对于给定的项目集合（例如，零售交易集合，每个集合都列出的单个商品的购买信息），算法通常尝试在项目集合中找出至少有C个相同的子集。先验算法采用自底向上的处理方法，即频繁子集每次只扩展一个对象（该步骤被称为候选集产生），并且候选集由数据进行检验。当不再产生符合条件的扩展对象时，算法终止。

先验算法采用广度优先搜索算法进行搜索并采用树结构来对候选项目集进行高效计数。它通过长度为${\displaystyle k-1}$的候选项目集来产生长度为${\displaystyle k}$的候选项目集，然后从中删除包含不常见子模式的候选项。根据向下封闭性引理,该候选项目集包含所有长度为${\displaystyle k}$的频繁项目集。之后，就可以通过扫描交易数据库来决定候选项目集中的频繁项目集。

虽然先验算法具有显著的历史地位，但是其中的一些低效与权衡弊端也进而引致了许多其他的算法的产生。候选集产生过程生成了大量的子集（先验算法在每次对数据库进行扫描之前总是尝试加载尽可能多的候选集）。并且自底而上的子集浏览过程（本质上为宽度优先的子集格遍历）也直到遍历完所有 ${\displaystyle 2^{|S|}-1}$ 个可能的子集之后才寻找任意最大子集S。

例子

一个大型超级市场根据最小存货单位（SKU）来追踪每件物品的销售数据。从而也可以得知哪些物品通常被同时购买。通过采用先验算法来从这些销售数据中建立频繁购买商品组合的清单是一个效率适中的方法。假设交易数据库包含以下子集{1,2,3,4}，{1,2}，{2,3,4}，{2,3}，{1,2,4}，{3,4}，{2,4}。每个标号表示一种商品，如“奶油”或“面包”。先验算法首先要分别计算单个商品的购买频率。下表解释了先验算法得出的单个商品购买频率。

商品编号	购买次数
1	3
2	6
3	4
4	5

然后我们可以定义一个最少购买次数来定义所谓的“频繁”。在这个例子中，我们定义最少的购买次数为3。因此，所有的购买都为频繁购买。接下来，就要生成频繁购买商品的组合及购买频率。先验算法通过修改树结构中的所有可能子集来进行这一步骤。然后我们仅重新选择频繁购买的商品组合：

商品编号	购买次数
{1,2}	3
{2,3}	3
{2,4}	4
{3,4}	3

并且生成一个包含3件商品的频繁组合列表（通过将频繁购买商品组合与频繁购买的单件商品联系起来得出）。在上述例子中，不存在包含3件商品组合的频繁组合。最常见的3件商品组合为{1,2,4}和{2,3,4}，但是他们的购买次数为2，低于我们设定的最低购买次数。

算法的局限

因此Apriori算法中的一些低效与权衡弊端也进而引致了许多其他的算法的产生，例如FP-growth算法。候选集产生过程生成了大量的子集（先验算法在每次对数据库进行扫描之前总是尝试加载尽可能多的候选集）。并且自底而上的子集浏览过程（本质上为宽度优先的子集格遍历）也直到遍历完所有 ${\displaystyle 2^{|S|}-1}$ 个可能的子集之后才寻找任意最大子集S。

参考资料

1. Rakesh Agrawal and Ramakrishnan Srikant. Fast algorithms for mining association rules in large databases （页面存档备份，存于互联网档案馆）. Proceedings of the 20th International Conference on Very Large Data Bases, VLDB, pages 487-499, Santiago, Chile, September 1994.