3

我正在使用 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} 的项目，当有按字典顺序排列的前 k-2 个项目相同且最后一个项目不同时。

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

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

我希望我能清楚地向你解释我的问题！

谢谢你的帮助！！

4

1 回答 1

4

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

让我们举个例子。

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

{ A, B, C} { A, B, D} { AC, D} { B, 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 论文中获得它有效的证明。

希望这可以帮助。

于 2014-02-26T16:14:31.443 回答