algorithm - 算法问题 - 找到最不常见的子集

Question

a 是具有多个“类别”的对象，b，例如 a1 具有三个类别 b1、b2、b3。问题在于，将类别的数量（可能会变得相当大）减少到总是一起出现的组中。一个“最大公共子集”的东西。

例如，给定以下数据集：

a1{ b1,b2,b3 } 
a2{ b2,b3 }
a3{ b1,b4 }

我们可以发现 b2 和 b3 总是在一起..

b23 = {b2,b3}

..我们可以将类别集减少为：

a1{ b1, b23 }
a2{ b23 }
a3{ b1,b4 }

所以，我的问题是找到一些算法来解决这个问题。

我已经开始研究最长公共序列问题，它可能是一个解决方案。即像这样反复对类别b' = LCS(set_of_As)进行分组，直到遍历所有类别。然而，这并不完整。我必须以某种方式限制输入域才能做到这一点。

我错过了一些明显的东西吗？您可以指出我的问题域的任何提示吗？有没有人认识到解决此类问题的任何其他方法。

score 7 · Accepted Answer

将您的集合转换为具有包含 a 的 b 集合：

b1 { a1, a3 }
b2 { a1, a2 }
b3 { a1, a2 }
b4 { a3 }

确保新 b 集的内容已排序。

按内容对 b 集进行排序。

任何两个具有相同元素的相邻集合都是出现在同一个集合中的 b。

score 0 · Accepted Answer

如果您可以对类别进行排序，我认为您在 LCS 的正确轨道上（如果不能，则 LCS 算法无法识别 {b3, b4} 和 {b4, b3}）。如果您可以对它们进行强制排序和排序，那么我认为这样的事情可能会起作用：


As = {a1={b1, b2},a2={b3},...}
while ((newgroup = LCS(As)) != empty) {
  for (a in As) {
     replace newgroup in a
  }
}

2 回答 2