3

假设我有五套我想聚类。我了解这里描述的 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)在每个“预集群”内进行搜索，以将它们进一步划分为“真实”集群？（如果我有很多小且相当平衡的预集群，这可能是合理的，否则就不是了）

4

1 回答 1

2

SimHash 和 MinHash 都是散列算法，能够将集合映射到与集合签名相对应的值列表。

在 SimHash 的情况下，值列表只是位列表（值是 0 或 1）。在 MinHash 的情况下，列表中的值表示所有集合元素相对于给定散列函数的最小散列值，该散列函数通常是 32 位或 64 位值。

两种算法的主要区别在于哈希冲突的概率。在 SimHash 的情况下，它等于余弦相似度，在 MinHash 的情况下，它等于 Jaccard 相似度。根据您如何定义集合之间的相似性，一种或另一种算法可能更合适。

无论选择何种散列算法，计算出的签名值都在一定数量的波段上平均划分。如果任何两个集合的签名在至少一个波段内是相同的，则选择对应的一对集合作为相似度的候选。（这意味着如果 n 个集合在一个带内具有相同的签名，则仅来自该带的 O(n^2) 个候选对。）使用完整签名（包括来自其他带的值）估计每个候选对的相似性和只保留那些估计相似度高于给定阈值的对为您提供所有相似的集合对，最终定义最终聚类。

于 2016-11-13T17:39:49.000 回答