如何使用规则约束来剪枝搜索空间？

规则约束可以分为以下五个要素：

反单调性 − 约束的第一个要素是反单调性。考虑规则约束“sum (I.price) ≤ 100”。假设它使用 Apriori 框架，在每次迭代 k 中分析大小为 k 的项集。如果项集中的项目成本总和不少于 100，则可以从搜索空间中缩短此项集，因为向集合中插入更多项目只会使其成本更高，因此不会满足约束条件。

反单调性约束的剪枝可用于 Apriori 风格算法的每次迭代，以帮助提高完整挖掘阶段的效率，同时保证数据挖掘服务的完整性。

Apriori 属性定义了频繁项集的所有非空子集都应该是频繁的，它是反单调的。如果给定项集不使用最小支持度，则其任何超集也不使用。此属性可用于 Apriori 算法的每次迭代，以减少检查的多个候选项集的数量，从而减少关联规则的搜索空间。

单调性 − 约束的第二个要素是单调性。如果规则约束为“sum (I.price) ≥ 100”，则基于约束的处理方法可能有所不同。

如果项集 I 满足约束条件，即集合中价格的总和不少于 100，则向 I 添加更多项目将增加成本，并将持续满足约束条件。

因此，对项集 I 上此约束的更多测试变得冗余。换句话说，如果项集使用此规则约束，则其所有超集也使用。

简洁约束 − 第三个要素是简洁约束。对于此约束要素，它可以枚举某些保证使用该约束的集合。如果规则约束是简洁的，它可以直接生成满足它的集合，甚至在支持计数开始之前。这避免了生成和测试范例的大量开销。

可转换约束 − 第四个要素是可转换约束。如果项集中的项目按特定顺序排列，则关于频繁项集挖掘过程，约束可以变成单调或反单调。

例如，约束“avg(I.price) ≤ 100”既不是反单调的也不是单调的。如果事务中的项目按价格升序添加到项集，则约束变为反单调的，因为如果项集 I 破坏约束（即平均成本高于 100 美元），则向项集中添加更多昂贵项目不会使其满足约束。

Ginni

更新于：2022年2月16日

浏览量：119

启动您的职业生涯

完成课程获得认证

开始学习