一家超市的决策者，经常需要考虑如下两个问题。第一个问题是，如何摆放商品，或者说，该将哪些商品摆放在一起，能让用户的购物体验更好。直观上想，如果用户经常同时购买某些商品，比如经常同时购买牛奶和面包，那么决策者就应该将牛奶和面包放在一起，这样能帮助同时购买牛奶和面包的用户节省一些找商品的时间。第二个问题是，假如某个商品降价了，那么其它商品的价格怎么调整，能让超市的收入更高。仍然以牛奶和面包为例，假设降价的商品是牛奶，直观上想，这时候给面包涨价应该是一个合适的决策。这是因为买了牛奶的用户一般也会买面包，当用户在超市里买了牛奶后，为了方便，也会在同一家超市买面包，因此将面包涨价就能增长超市的收入。

在上面的例子里，我们可以看到，在超市的经营决策中，寻找“哪些商品更可能同时被用户购买”和“用户购买了某些商品，就很可能会购买另一些商品”这类的规律是很有用的事情。而这类规律，通常是隐藏在营业数据中的。在数据挖掘（Data Mining）领域中，频繁项集挖掘（Frequent Itemsets Mining）就是研究如何从数据中发现这类规律的一个任务，本文将介绍这个任务最基本的定义和算法。

因为频繁项集挖掘是从数据中发现某类规律的任务，因此我们需要规定这个任务使用的数据的类型和这个任务发现的规律的类型。首先我们先规定这个任务所使用的数据的类型。频繁模式挖掘这个任务一般假设我们有 $n$ 个项（Item，也可以翻译为商品）和 $m$ 个篮子（Basket），每个篮子里有若干个项。这 $m$ 个篮子组成的数据就称为满足购物篮模型（Market-Basket Model）要求的数据。下面总结一下购物篮模型的定义。

然后我们来讨论频繁项集挖掘这个任务需要发现的规律的描述方式。为了能准确描述“哪些商品更可能同时被用户购买”这个规律，我们需要定义项集（Itemset）和频繁项集（Frequent Itemset）这两个概念。我们将项的集合称为项集，换句话说，项的全集的任一个子集，都是一个项集。对于包含 $k$ 个项的项集，我们称其为 $k$-项集。一个项集 $S$ 在数据中出现的次数（也就是包含 $S$ 的篮子的数目）称为项集 $S$ 的支持数（Support），简记为 $supp(S)$。顾名思义，频繁项集就是出现得比较频繁的项集，也就是支持数较大的项集。为了精确描述“频繁”这个概念，我们预先给定一个整数，称其为支持数阈值（Support Threshold），并称支持数不少于支持数阈值的项集是频繁项集。同样，包含 $k$ 个项的频繁项集称为频繁 $k$-项集。下面总结一下频繁项集的定义。

上面我们已经成功抽象出“哪些商品更可能同时被用户购买”这个规律的准确描述，接下来让我们尝试抽象出“用户购买了某些商品，就很可能会购买另一些商品”这个规律的准确描述。考虑两个不交的项集 $S_1$ 和 $S_2$，我们希望知道假如一个用户购买了 $S_1$ 中的全部商品后，会有多大可能购买 $S_2$ 中的全部商品。这个可能性用概率来描述就是 $$P\{用户购买了 S_2 中的商品|用户购买了 S_1 中的商品\}=\frac{P\{用户购买了 S_1\cup S_2 中的商品\}}{P\{用户购买了 S_1 中的商品\}}$$ 为了方便，将这个公式简记为 $$P(S_2|S_1)=\frac{P(S_1\cup S_2)}{P(S_1)}$$ 由于我们手上有用户的购买数据，因此可以用频率值估计这个概率值，就有 $$\hat{P}(S_2|S_1)=\frac{\hat{P}(S_1\cup S_2)}{\hat{P}(S_1)}=\frac{\frac{supp(S_1\cup S_2)}{m}}{\frac{supp(S_1)}{m}}=\frac{supp(S_1\cup S_2)}{supp(S_1)}$$ 我们称形如“用户购买了 $S_1$ 中的全部商品，就会购买 $S_2$ 中的全部商品”这样的规则为关联规则（Association Rule），简记为 $S_1\to S_2$，并称 $\hat{P}(S_2|S_1)$ 为这个关联规则的置信度（Confidence），简记为 $conf(S_1\to S_2)$。下面总结一下关联规则和关联规则的置信度的定义。

表面上看，置信度越大的关联规则，应该是越有用的关联规则，但事实并不是这样。举个例子，假设来超市购物的所有用户都买了矿泉水这个商品，那么对任意一个商品，比如铅笔，就会有 $supp(\{铅笔\})=supp(\{铅笔，矿泉水\})$，从而 $$conf(\{铅笔\}\to\{矿泉水\})=\frac{supp(\{铅笔，矿泉水\})}{supp(\{铅笔\})}=1$$ 可以看到，这条关联规则的置信度很大，但它并不能反映任何因果关系，因为这时候从概率的角度来看（假设样本空间是数据 $D$），铅笔和矿泉水的购买是两个独立的事件，也就是 $$P(\{矿泉水\}|\{铅笔\})=P(\{矿泉水\})$$ 由此可见，对于关联规则 $S_1\to S_2$，当 $\frac{\hat{P}(S_2|S_1)}{\hat{P}(S_2)}=1$ 时（这个公式代表两个购买事件独立），这条关联规则就基本没什么用处了。因此我们将 $\frac{\hat{P}(S_2|S_1)}{\hat{P}(S_2)}$ 称为关联规则 $S_1\to S_2$ 的提升度（Lift），作为关联规则的有效性的一个评价指标。下面总结一下关联规则的提升度的定义。

由提升度的定义可见，当一条关联规则的提升度较大时（远大于 $1$），就说明相比于不完全购买 $S_1$ 中的商品的用户，完全购买 $S_1$ 中的商品的用户更可能完全购买 $S_2$ 中的商品。当一条关联规则的提升度较小时（远小于 $1$），就说明相比于不完全购买 $S_1$ 中的商品的用户，完全购买 $S_1$ 中的商品的用户更不可能完全购买 $S_2$ 中的商品。当一条关联规则的提升度接近 $1$ 时，就说明用户是否完全购买 $S_2$ 中的商品，和用户是否完全购买 $S_1$ 中的商品，没有太大关系。

我们一般倾向于从数据中挖掘满足 $supp(S_1\cup S_2)$ 和 $conf(S_1\to S_2)$ 都比较大的关联规则（之所以要求 $supp(S_1\cup S_2)$ 较大，是因为如果 $S_1\cup S_2$ 不常见，那么这条关联规则可能不会带来太多商业利润），再用提升度等指标筛选出真正有效的关联规则。而关联规则的挖掘，可以归结为频繁项集的挖掘，这是因为只要找到所有的频繁项集，那对于任意一个频繁项集 $S$，枚举其子集 $S_1$，令 $S_2=S-S_1$，再验证置信度，就可以生成所有满足要求的关联规则。因此下一节主要讨论挖掘频繁项集的算法。

本节主要介绍挖掘频繁项集的算法。先来回顾一下算法需要解决的任务，如下所示。

首先，很容易给出一个暴力算法（Brute-Force Algorithm）作为这个任务的解法，如下所示。

可以看到，这个暴力算法不管是在空间开销上，还是在时间开销上，都是很爆炸的。尤其是空间开销，因为项的总数量 $n$ 一般是很大的，即使 $k$ 很小（如 $k=2$），也需要在内存中维护至少 $C_n^k$ 个计数器。

但事实上，并不是所有的 $k$-项集都需要作为频繁 $k$-项集候选，我们可以找到一些简单的规则筛选掉一些不可能是频繁 $k$-项集的 $k$-项集。比如，先预处理得到所有的频繁项（这只需要 $n$ 个计数器，空间开销是可以接受的），那么，对于一个 $k$-项集，假如它包含一个非频繁项，那它肯定不可能是频繁 $k$-项集，换句话说，频繁 $k$-项集的项一定都是频繁项。更一般的，我们有如下命题。

根据这个命题，我们可以看出，若一个项集是频繁项集，那么它的全部子项集都是频繁项集。利用这条性质，研究人员提出Apriori算法（Apriori Algorithm），从小到大地来求解频繁项集，即先求解全体频繁 $1$-项集，根据结果选取合适的频繁 $2$-项集候选，再求解全体频繁 $2$-项集，依次类推。Apriori算法在实际使用中大幅度降低了内存开销，算法步骤如下所示。

相比于暴力算法，Apriori算法减少了频繁 $k$-项集候选的数目，节省了内存开销，但可能增加了时间开销（不考虑删除数据中的非频繁项导致部分篮子变小这件事，Apriori算法需要遍历 $k$ 次数据，而暴力算法只需要遍历 $1$ 次数据。实际应用中 $m$ 一般较大（因此数据只能存储在硬盘中），所以遍历数据的时间开销是最主要的时间开销）。这里还需要注意一件事，就是在将频繁 $j$-项集拓展到频繁 $j+1$-项集候选这个步骤中，我们对增加的项，是要求它的编号要大于 $j$-项集中所有项的编号的。这里主要是为了防止拓展出重复的频繁 $j+1$-项集候选，比如假设 $\{1,2\}$ 和 $\{2,3\}$ 都是频繁 $2$-项集，如果拓展时不加限制，那么这两个频繁 $2$-项集都能拓展出 $\{1,2,3\}$ 这个频繁 $3$-项集候选。

通过哈希（Hash）的技巧，算法的内存消耗还能进一步减小。具体来讲，就是在得到频繁 $j$-项集候选后，我们可以通过哈希函数，给若干个频繁 $j$-项集候选分配同一个计数器，再遍历数据更新计数器。这么做之后，对于一个频繁 $j$-项集候选，它对应的计数器值不小于 $s$ 并不能保证它一定频繁，但如果计数器值小于 $s$，那它一定不频繁。这样就能用少量的内存开销进一步排除部分不可能频繁的频繁 $j$-项集候选。下面介绍的PCY算法（Algorithm of Park，Chen and Yu），就是在Apriori算法的基础上，用这样的技巧做改进的一个算法。算法步骤如下所示。

这里同样是通过牺牲时间开销的方式减少空间开销（为了方便叙述，本文描述的PCY算法和真正的PCY算法在细节上略有不同，但思想是一致的）。

PCY算法有两个变种，都能够进一步减少空间开销。第一个变种是多阶段PCY算法（Multistage PCY Algorithm），这个算法的想法就是在一次哈希减少频繁项集候选后，再做一次哈希，再进一步减少频繁项集候选，依此类推。第二个变种是多哈希PCY算法（Multihash PCY Algorithm），这个算法的想法就是一次使用多套<计数器集，哈希函数>对来增强算法排除非频繁项集的能力。

上面介绍的Apriori算法变种主要是从优化空间开销的角度进行改进的，下面介绍两个从优化时间开销的角度进行改进的Apriori算法变种。

第一个算法变种是一个随机算法，算法名称是随机Apriori算法（Randomized Apriori Algorithm）。这个算法的想法是，从数据（$m$ 个篮子）中均匀随机地采样 $m_1$ 个篮子，组成一个新数据，那么在原数据中支持数不小于 $s$ 的项集，在期望的意义下，在新数据中支持数将不小于 $\frac{m_1}{m}\cdot s$。因此可以先求解新数据中的频繁 $k$-项集（求解时将支持数阈值从 $s$ 改为 $\frac{m_1}{m}\cdot s$），再遍历原数据，检查这些频繁 $k$-项集在原数据中是否是频繁的。需要注意的是，这种随机算法可能会漏求解部分频繁 $k$-项集（即可能会有false negative），这是因为在原数据中频繁的项集，在新数据中不一定频繁。为什么这个随机算法会比原算法快呢，这是因为Apriori算法的时间瓶颈主要在遍历数据上，求频繁 $k$-项集时需要遍历 $k$ 次数据，而随机Apriori算法只需要遍历 $1$ 次数据，因此在时间开销上会更少一些。随机Apriori算法的步骤总结如下。

随机Apriori算法相当于是在原数据的一个随机样本上求解频繁 $k$-项集，随机样本上的频繁 $k$-项集，相比与原数据的频繁 $k$-项集，可能会有多求解的（在原数据中不频繁，但在新数据中频繁，即false positive），也可能会有少求解的（在原数据中频繁，但在新数据中不频繁，即false negative）。随机Apriori算法通过在原数据上做检验的方式消除了“多求解”的情况，但并没有处理“少求解”的情况。实际使用中，我们可以通过减小支持数阈值的方式（如将支持数阈值从 $\frac{m_1}{m}\cdot s$ 减小至 $0.9\cdot \frac{m_1}{m}\cdot s$）来增加随机样本上频繁 $k$-项集的数量，从而减少“少求解”情况的数目。

本文介绍的最后一个算法是Apriori算法的一个并行版本，算法名称是SON算法（Algorithm of Savasere， Omiecinski and Navathe）。这个算法同样能减少时间开销，但和随机Apriori算法不同的是，随机Apriori算法会以一定概率出错，但SON算法是完全不会出错的。SON算法的想法是这样的，先将数据分成 $m_0$ 份子数据，对每份子数据，以 $\frac{1}{m_0}*s$ 为支持数阈值用Apriori算法求解频繁 $k$-项集。合并所有子数据上的全体频繁 $k$-项集，那么原数据的全体频繁 $k$-项集必然都在这里面。这是因为，对任意一个 $k$-项集 $S$，假设它在所有子数据中都不是频繁的，那么它的支持数 $$supp(S)<\frac{1}{m_0}\cdot s+...+\frac{1}{m_0}\cdot s=s$$ 从而 $S$ 不是频繁 $k$-项集。在得到频繁 $k$-项集候选后，再用原数据并行地来检验，就可以得到全体频繁 $k$-项集。算法流程如下所示。

我用python实现了Apriori算法（代码地址），并用Groceries Market Basket Dataset做实验。以 $90$ 为支持数阈值，可以求解得到 $3$ 个频繁 $3$-项集，分别为

• ('tropical fruit', 'whole milk', 'rolls/buns')，支持数为 $108$
• ('tropical fruit', 'pip fruit', 'other vegetables')，支持数为 $93$
• ('other vegetables', 'rolls/buns', 'soda')，支持数为 $97$

本文主要介绍了频繁项集挖掘的背景，基本概念和算法。

[1]CS246 of Stanford University, Week 2

[2]Mining of Massive Datasets, Chapter 6