MinHash 的基本原理#

MinHash 是一种用于估计集合相似性（通常是 Jaccard 相似性）的方法。Jaccard 相似性是两个集合交集的大小与它们并集的大小之比。MinHash 通过以下步骤来估计这个相似性：

1. 哈希函数：使用多个哈希函数将集合中的元素映射到一个较小的值域中。
2. 最小哈希值：对于每个集合，计算所有哈希值的最小值，这个最小值称为 MinHash 值。通过多个不同的哈希函数，可以得到多个 MinHash 值，从而形成一个 MinHash 签名。
3. 相似性估计：两个集合的 MinHash 签名的相似度（即它们的 MinHash 值的相等比例）可以用来估计这两个集合的 Jaccard 相似度。

LSH 的基本原理#

局部敏感哈希（Locality-Sensitive Hashing，LSH）是一种技术，旨在通过将相似的对象映射到同一个桶中来加速相似性搜索。LSH 的关键是设计哈希函数，使得相似的输入数据在哈希后有较高的概率被映射到同一个桶中，而不相似的数据则有较低的概率。

MinHash LSH 的结合#

MinHash LSH 将 MinHash 和 LSH 结合起来，具体步骤如下：

1. 生成 MinHash 签名：对每个集合使用 MinHash 方法生成一个 MinHash 签名。
2. 哈希签名：将 MinHash 签名通过 LSH 哈希函数进行映射。每个签名会被映射到一个或多个桶中。
3. 桶的查询：在进行相似性查询时，只需检查与查询对象在同一个桶中的其他对象，从而大幅减少需要比较的对象数量。

应用场景#

MinHash LSH 在许多应用中非常有用，包括：

• 文本相似性检测：例如，检测文档或网页的重复内容。
• 推荐系统：为用户提供相似兴趣的物品。
• 图像查找：寻找相似的图像或图像特征。
• 社交网络分析：寻找社交网络中相似的用户或群组。

通过使用 MinHash LSH，系统可以高效地处理大规模数据集，实现快速的相似性搜索，同时保持较高的准确性。

步骤 1：准备数据#

1. 输入数据：准备一组集合数据，例如文档的词集、用户的兴趣标签等。每个集合可以用一个唯一的标识符表示。

步骤 2：生成 MinHash 签名#

1. 选择哈希函数：选择一组哈希函数。通常使用多个独立的哈希函数来生成不同的 MinHash 值。每个哈希函数 ( h_i ) 可以将集合元素映射到一个整数值。

2. 计算 MinHash 值：

   • 对于每个集合 $S_j$，执行以下操作：
     • 对集合中的每个元素 $x$ 计算哈希值 $h_i(x)$。
     • 记录每个哈希函数 $h_i$ 的最小值： $$\text{MinHash}_i(S_j) = \min_{x \in S_j}(h_i(x))$$
   • 这样，对于每个集合 $S_j$，你将得到一个 MinHash 签名 $\text{MinHash}(S_j) = [\text{MinHash}_1(S_j), \text{MinHash}_2(S_j), \ldots, \text{MinHash}_k(S_j)]$，其中 $k$ 是哈希函数的数量。

步骤 3：构建 LSH 哈希表#

在这个步骤中，我们将生成 LSH 哈希表，以便将 MinHash 签名进行分组，便于后续的相似性查询。以下是更详细的步骤：

示例#

假设我们有三个集合和我们选择的参数 $b = 2$，$r = 2$，并且每个集合的 MinHash 签名长度为 4（即 $k = 4$）。我们将每个 MinHash 签名划分为两个部分，每个部分包含两个 MinHash 值。

• 集合 $S_1$ 的 MinHash 签名： $$\text{MinHash}(S_1) = [3, 1, 4, 2] \quad \text{(分为两部分: [3, 1], [4, 2])}$$
• 集合 $S_2$ 的 MinHash 签名： $$\text{MinHash}(S_2) = [2, 0, 3, 1] \quad \text{(分为两部分: [2, 0], [3, 1])}$$
• 集合 $S_3$ 的 MinHash 签名： $$\text{MinHash}(S_3) = [1, 1, 2, 0] \quad \text{(分为两部分: [1, 1], [2, 0])}$$

然后，计算每个部分的哈希值并将集合存入哈希表中。

步骤 4：查询#

1. 查询集合：对于待查询的集合 $Q$，首先计算其 MinHash 签名 $\text{MinHash}(Q)$。

2. 生成查询的 LSH 哈希值：

   • 将查询的 MinHash 签名划分为 $b$ 个部分，并为每个部分生成哈希值。

3. 查找候选集合：

   • 根据查询生成的哈希值，查找 LSH 哈希表中对应的桶，获取与查询集合 $Q$ 可能相似的候选集合。

步骤 5：相似性计算#

1. 精确相似性计算：
   • 对于候选集合，计算其与查询集合 $Q$ 的 Jaccard 相似性（或其他相似性度量），以确认哪些集合是最相似的。这可以通过以下公式计算：
   $$J(S_j, Q) = \frac{|S_j \cap Q|}{|S_j \cup Q|}$$
   • 根据计算的相似性得分，选出最相似的集合。

总结#

以上步骤概述了如何计算 MinHash LSH 的流程。通过使用 MinHash 签名和 LSH 哈希表，可以高效地进行大规模集合数据的相似性搜索，从而显著提高搜索效率，特别是在处理高维数据时。