关联分析(2):Apriori产生频繁项集

在关联分析(1):概念及应用中，我们介绍了关联分析的应用场景、基本概念和规则产生思路。在本次的文章中，我们将介绍Apriori算法频繁项集产生的原理。文章中会涉及专有名词，不清楚概念的可在上一篇文章中查看。

先验原理与反单调性

产生频繁项集的原始方法是找到所有可能的候选项集，与每个事务比较，计算出支持度计数。但是这种方法开销太大，因此需要在候选项集的产生中，直接删除某些候选项集。这里，就需要用到先验原理和支持度的反单调性。

先验原理。如果一个项集频繁，则其所有子集也频繁。

比如｛a,b｝是频繁项集，则包含｛a,b｝的事务一定包含其子集｛a｝和｛b｝，因此如果｛a,b｝频繁，其子集一定频繁。

反单调性。如果一个项集非频繁，则其所有超集也非频繁。

比如｛a,b｝是非频繁项集，则他的所有子集也是非频繁的。即项集的支持度不超过其子集的支持度。根据支持度的反单调性，可以通过剪枝减少候选项集的数量。

Apriori算法产生频繁项集

Apriori算法是非常常用的关联算法之一，我们继续使用上一篇文章中的例子，来分析Apriori算法产生频繁项集的过程。假定支持度阈值为50%，即最小支持度计数为2。

步骤一 初始，将每个项看成候选1-项集，计算支持度。这样，{handicapped-infants=?}，{immigration=y}和{crime=n}被丢弃，因此频繁1-项集共6个。

步骤二 根据先验原理与支持度反单调性，非频繁1-项集的超集都非频繁，所以使用频繁1-项集来产生候选2-项集。

步骤三 同理，使用频繁2-项集来产生候选3-项集。根据先验原理，只需要保留子集全为频繁2-项集的候选3-项集。

步骤四 同理，使用频繁3-项集来产生候选4-项集。得到唯一的频繁4-项集

{republican,handicapped-infants=n,mx-missile=n,crime=y}。

产生频繁项集特点

1，逐层。从1-项集开始，直到可以产生的最长频繁项集。

2，产生测试策略。每次新的候选项集都由前一次产生的频繁项集生成，然后根据支持度要求，得到新的频繁项集。

候选项集产生

从上面的过程可以看出，生成频繁项集还包含一个非常重要的步骤，就是候选项集的产生。用一种可以快速有效的方法生成候选项集，可以有效提升算法效率。

为了避免生成候选项集时产生重复，同时保证产生候选的完全性，将频繁项集中的项按照字典序存储，即按照字母顺序排列。这样，只有在两个频繁k－项集的前（k－1）项都相同时，才进行合并，产生（k＋1）项集，然后验证子集是否频繁，对非频繁子集进行剪枝，生成候选（k＋1）项集。比如{crime=y，handicapped-infants=n，mx-missile=n}和{crime=y，handicapped-infants=n，republican}都是按照字典序排列的频繁3-项集，他们前两项都相同，所以进行合并，{crime=y，handicapped-infants=n，mx-missile=n，republican}，且经验证，子集都为频繁，则{crime=y，handicapped-infants=n，mx-missile=n，republican}为频繁4-项集。