algorithm - Apriori 算法中的字典顺序

Question

我使用 Apriori 算法有一段时间了，我问我有关频繁项集候选生成的步骤。

如果我想将两个频繁的 3 项集连接到一个(候选)4 项集，则连接项集中必须有 2 个相同的项和另一个不同的项。

比如我可以加入

{Married: Yes, Age:20, Cars:1} and {Married: Yes, Age:20, Unemployed: No}

到

{Married: Yes, Age:20, Cars:1, Unemployed: No}

但有时我会在 Apriori 算法中读到这一步:

我可以加入两个频率。 L_{k-1}中的itemtest，当有字典顺序前k-2项相同，后k-2项不同。

但是当我从上面的字典顺序排列我的项目集时，第一个 k-2 项目不会相同，所以我可能不会加入它们？!？

{Age:20, Cars:1, Married: Yes} and {Age:20, Married: Yes Unemployed: No}

我希望我能把我的问题解释清楚给你听!

感谢您的帮助!

Answer 1

是的，你不应该加入他们。

让我们举个例子。

假设在第 3 级，您有频繁项集:

{ A, B, C}{ A, B, D}{ A C, D}{乙，丙，丁}{ B, F, G

现在假设您要生成大小为 4 的候选项集。

显然，您只想组合具有 1 个不同项目的项目集。否则，结果可能包括大小大于 4 的项集。例如，如果您可以组合 BCD 和 BFG，结果将是 BCDFG 大小为 5 的项集，这是我们不想要的。所以这就是为什么我们只组合具有单个不同项目的项目集的原因。

现在，让我解释一下为什么我们只合并具有前 k-1 个相同项目的项目集。原因是我们不想两次生成相同的候选人。

例如，如果我们可以组合 BCD 和 ACD，我们将得到 ABCD。如果我们也将 ABC 和 ABD 结合起来，我们也会得到 ABCD。这不好，因为我们会生成相同的候选人两次!我们不想要那样!因此，通过根据字典顺序对项目集进行排序，并且仅在前 k-1 个项目相同时才进行组合，我们将避免这个问题。我们只会合并 ABC 和 ABD，但不会合并 BCD 和 ACD。你可以在 Apriori 论文中得到它有效的证明。

希望这对您有所帮助。