algorithm - 在嘈杂的数据中寻找公共(public)集

Question

上下文:将 G 中的每个集合视为在特定计算机上找到的文件(内容或 MD5 哈希，而不是名称)的集合。

假设我有一个巨大的集合列表 G 和一个未知的集合列表 H。 G 中的每个单独集合 I 都是通过从列表 H 中获取一些未知数量的集合的并集，然后添加和删除一个未知数来创建的元素。

现在，我可以使用其他数据构造列表 H 中的一些集合。但是，我觉得可能涉及某种技术 Bayesian probability去做这个。例如。类似的东西，“如果在 G 的集合中找到 X 意味着很有可能也找到 Y，那么可能有一个集合H 中包含 X 和 Y。”

编辑:我的目标是构建一组集合，这些集合很有可能非常类似于或等于H。

有什么想法吗？

示例用法:

通过用 H 的 block 替换它的 block 来压缩 G，例如

G[1]  = {1,2,3,5,6,7,9,10,11}
H[5]  = {1,2,3}
H[6]  = {5,6,7,8,9,10}
G[1]' = {H[5],H[6],-8,11}

Answer 1

定义距离 d(i,j) = 1/(G 中同时包含 i 和 j 的集合数)，然后运行聚类分析。( http://en.wikipedia.org/wiki/Cluster_analysis )