Apriori算法中的字典序

Question

我已经一段时间在使用Apriori算法，现在我正在考虑关于频繁项集的候选生成步骤中的一个问题。

如果我想将两个频繁的三项集连接起来成为一个（候选）四项集，那么连接的两个三项集必须有两个相同的项目和另一个不同的项目。

例如，我可以将下面这些项连接起来：

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

to

{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}

我希望你能够理解我的问题！感谢你的帮助！！

- mrbela

Answer 1

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

让我们举个例子。

假设在LEVEL 3中，你有以下频繁项集：

{ A, B, C} { A, B, D} { A C, 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论文中找到它的证明。

希望这些能帮到你。

- Phil