Apriori 算法

如果一个项集 是频繁的，则它的所有非空子集一定也是频繁的。

证明：设 是一个项集，事务数据集 中支持 的元组数为 。对 的任意非空子集为 ，设 中支持 的元组数为

根据项集支持数的定义，易知，支持 的元组一定支持 ，所以 ，即

按照假设，项集 是频繁项集。

例如，假设

如果一个项集 是非频繁的，那么它的所有超集一定也是非频繁的。证明略。

Apriori 算法通过迭代来穷举出数据集中的所有频繁集。

1. 首先，产生 1-频繁集
2. 其次，在 上通过连接和修建产生 2-频繁集
3. 以此类推，可在 上通过连接和修建产生 -频繁集
4. 最后，直到无法产生新的频繁集为止。

数据库

取阈值 。

执行 Apriori 算法，经过第一次扫描得到

其中 属于非频繁集，通过剪枝删除

在 1-项集中进行拼接，并且回到原数据集进行扫描

其中 {A, B} 和 {A,E} 是非频繁集，通过剪枝删除

在 2-项集中进行拼接，并且回到原数据集进行扫描

最终只有 {B,C,E} 是频繁 3-项集。综上得到频繁集为

对于频繁集 来说，它的非空子集包括

• 关联规则 的置信度为
• 关联规则 的置信度为
  当最小置信度设置为 时，关联规则 是强关联规则，而 不是。但如果最小置信度设置为 时，两条都是强关联规则。

设 是项集 的一个子集，若规则 不是一条强规则，那么 也一定不是强规则。

证明：由于 ，故

又因为 不是强规则，即

所以

即 不是强规则。此定理可以利用已知结果排除一些肯定不是强规则的测试。如，若 不是强规则，则可断定 ， 一定不是强规则。

设 是项集 的一个子集，若规则 是一条强规则，那么， 也一定是强规则。

证明：由支持度的定义

故

又因为 是强规则，即

由此，可以利用已知结果避免一些肯定是强规则的测试。

Apriori 算法的核心在于

• 用频繁的 项集生成候选的频繁 -项集
• 用数据库扫描和模式匹配计算候选集的支持度

Apriori 的瓶颈：候选集生成

• 巨大的候选集：
  • 个频繁的 1-项集要生成 个候选 2-项集
  • 要找尺寸为 的频繁模式，如 ，你必须先产生 的候选集
• 多次扫描数据库
  • 如果最长的模式是 的话，则需要 次数据库扫描

有几种常见的提到 Apriori 效率的方法

• 基于 Hash 的项集计数：在一个 Hash 桶内支持度小雨最小支持度的 -项集不可能是全局频繁的
• 减少交易记录：不包含任何频繁 -项集的交易也不可能包含任何大于 的频繁集，下一步计算时删除这些记录
• 划分：一个项集想要在整个数据集中是频繁的，那么它至少在数据库的一个分割上是频繁的。
• 抽样：使用小的支持度+完整性验证方法，再小的抽样集上找到局部频繁项集，然后再全部数据集找频繁项集
• 动态项集计数：再添加一个新的候选集之前。先检查一下是不是他的所有自己都是频繁的。