假设我有五组要聚类。我了解此处介绍了SimHashing技术:
https://moultano.wordpress.com/2010/01/21/simple-simhashing-3kbzhsxyg4467-6/
例如，如果其结果是，则可以产生三个聚类({A}，{B,C,D}和{E})。
A -> h01
B -> h02
C -> h02
D -> h02
E -> h03
同样，MMDS书籍的第3章中介绍了MinHashing技术:
http://infolab.stanford.edu/~ullman/mmds/ch3.pdf
如果其结果是，也可以产生相同的三个聚类:
A -> h01 - h02 - h03
B -> h04 - h05 - h06
|
C -> h04 - h07 - h08
|
D -> h09 - h10 - h08
E -> h11 - h12 - h13
(每组对应一个由三个“带”组成的MH签名，如果两个签名带中的至少一个匹配，则将这两组分组。更多的带意味着更多的匹配机会。)
但是我有几个与此有关的问题:
(1)可以将SH理解为MH的单频段版本吗？
(2)MH是否必然暗示使用诸如Union-Find之类的数据结构来构建集群？
(3)我认为这两种技术中的聚类实际上只是“候选聚类”，也就是说它们只是“候选对”的集合，对吗？
(4)如果(3)为真，是否意味着我仍然必须在每个“预集群”中进行
O(n^2)搜索，以将其进一步划分为“真实”集群？ (如果我有很多小型且相当平衡的预丛集，那可能是合理的，否则就不那么多了) 最佳答案
SimHash和MinHash都是能够将集合映射到对应于集合签名的值列表的哈希算法。
对于SimHash，值列表只是位列表(值可以为0或1)。如果是MinHash，则列表中的值表示所有集合元素相对于给定哈希函数的最小哈希值，通常为32位或64位值。
两种算法的主要区别是哈希冲突的可能性。对于SimHash，它等于余弦相似度；对于MinHash，它等于Jaccard相似度。根据您如何定义集合之间的相似性，一个或另一个算法可能更合适。
无论选择哪种哈希算法，都将计算出的签名的值平均分配到一定数量的频段上。如果任何两个集合的签名在至少一个频带内相同，则选择相应的一对集合作为相似性候选。 (这意味着，如果n个集合在一个频带中具有相同的签名，则仅在该频带中就有O(n ^ 2)个候选对。)使用完整签名(包括来自其他频带的值)估算每个候选对的相似性，并且仅将那些估计相似度高于给定阈值的对保留下来，即可为您提供所有相似的对对，这些对最终定义了最终的聚类。