发现规则
我们在这里考虑的关联规则比 [AIS93b] 中的更通用，因为我们允许结果有多个项目； [AIS93b] 中的规则仅限于单个项目的结果。我们首先给出了 [AIS93b] 中算法的简单概括，然后提出了一个更快的算法。
为了生成规则，对于每个大项集 l，我们找到 l 的所有非空子集；对于每个这样的子集 a，如果 support(l) 与 support(a) 的比率至少为 minconf，则我们输出形式为 a ==> (l-a) 的规则。我们考虑 l 的所有子集来生成具有多个结果的规则。由于大项集存储在哈希表中，因此可以有效地找到子集项集的支持计数。
我们可以通过以递归深度优先方式生成大型项目集的子集来改进上述过程。例如，给定一个项集 ABCD，我们首先考虑子集 ABC，然后是 AB，等等。然后如果一个大项集 l 的子集 a 没有生成规则，那么使用 l 的生成规则不需要考虑 a 的子集。例如，如果 ABC ==> D 没有足够的置信度，我们就不需要检查 AB ==> CD 是否成立。我们不会遗漏任何规则，因为 a 的任何子集 a~ 的支持度必须与 a 的支持度一样大。因此，规则a~==>(l-a~)的置信度不能大于a==>(l-a)的置信度。因此，如果 a 没有产生一个规则，涉及 l 中的所有项目，并且 a 作为先行词，那么 a~ 也不会。以下算法体现了这些想法：
更快的算法
我们之前已经证明，如果 a ==> (l-a) 不成立，那么 a~ ==> (l-a~) 对于包含在 a 中的任何 a~ 也不成立。通过重写，它遵循规则 (l-c) ==> c 成立，所有形式 (l-c~) ==> c~ 的规则也必须成立，其中 c~ 是 c 的非空子集。例如，如果规则 AB ==> CD 成立，那么规则 ABC ==> D 和 ABD ==> C 也必须成立。
考虑上述性质，对于给定的大项集，如果具有结果 c 的规则成立，那么具有作为 c 的子集的结果的规则也成立。这类似于如果一个项集很大，那么所有项的子集也很大。因此，从一个大的项目集 l 中，我们首先生成所有规则，其中包含一个项目。然后我们使用这些规则的结果和第 2.1.1 节中的函数 apriori-gen 来生成所有可能的结果，其中有两个项目可以出现在从 l 等生成的规则中。下面给出了使用这个想法的算法。在该算法的步骤 2 中具有单项结果的规则可以通过使用前面的 genrules 函数的修改版本找到，其中删除步骤 8 和 9 以避免递归调用。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/103081.html
