如何使用规则约束来修剪搜索空间?
规则约束可以分为以下五个要素:−
反单调性 − 约束的第一个要素是反单调性。考虑规则约束"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 美元)，那么在项集中添加更多成本更高的项目将不会使其使用该约束。
