Apriori 是强有力地解决频繁项集生成的组合突发的算法。它通过使用 Apriori 原理来缩短指数搜索区域来实现这一点。尽管该算法具有重要的性能增强,但由于需要对事务记录集进行各种传递,因此该算法获得了相当大的 I/O 开销。
由于事务宽度的增加,Apriori 算法的行为本质上可以降低密集数据集。已经产生了几种方法来克服这些缺点并提高 Apriori 算法的有效性。
以下是这些方法的高级描述,如下所示 -
项集格的遍历- 对频繁项集的搜索可以被视为对项集格的遍历。在频繁项集生成阶段如何遍历格结构的算法方法所涉及的搜索方法。基于格中频繁项集的组成,一些搜索方法优于其他搜索方法。
General-to-Specific vs Specific-to-General - Apriori 算法需要一种从一般到特定的搜索方法,其中频繁 (k-l) 项集对组合以获得候选 k 项集。这种从通用到特定的搜索方法是高效的,支持的频繁项集的最大长度不会太长。
具体到一般的搜索方法首先查看更确定的频繁项集,然后再发现更一般的频繁项集。这种方法有利于在密集事务中找到最大频繁项集,其中频繁项集边界位于格子底部附近。
Apriori 原则可用于修剪最大频繁项集的一些子集。特别是,如果一个候选 k-itemset 是最大频繁的,它不必确定它的任何大小为 k-1 的子集。但是如果候选 k-itemset 不频繁,则需要检查它的所有 k-1 个子集在下一次迭代中。
另一种方法是连接通用到特定和特定到通用的搜索方法。这种双向方法需要更多的空间来保存候选项集,但它可以支持快速识别频繁项集边界。
Equivalence Classes - 设想遍历的另一种方法是首先将晶格划分为不相交的节点组(或相同的类)。频繁项集生成算法首先在特定等价类中搜索频繁项集,然后再更改为另一个等价类。
在 Apriori 中使用的 level-wise 方法,该算法可以被视为在项集大小的支持上对格进行划分;即,该算法在对更大的项集进行操作之前首先找到一些频繁的 1 项集。等价类也可以根据项目集的前缀或后缀标签来表示。