假设我有五组要聚类。我了解此处描述的 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) 个候选对。)使用完整的签名(包括来自其他波段的值)和估计每个候选对的相似性仅保留估计相似度高于给定阈值的那些对，即可得到所有相似的集合对，它们最终定义了最终的聚类。
关于cluster-analysis - MinHashing 与 SimHashing，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30806037/