问题标签 [locality-sensitive-hash]

我对检测相似文档的技术有一个合理的理解，该技术首先计算它们的 minhash 签名（从它们的 shingles 或 n-gram），然后使用基于 LSH 的算法来有效地对它们进行聚类（即避免二次复杂度，这将需要一个简单的成对穷举搜索）。

我正在尝试做的是桥接三种不同的算法，我认为这些算法都与这个 minhash + LSH 框架有关，但以非显而易见的方式：

（1） Mining of Massive Datasets（Rajaraman and Ullman）一书第3章第3.4.3节勾勒的算法，似乎是minhashing的规范描述

(2) Ryan Moulton 的Simple Simhashing文章

（3）Charikar所谓的SimHash算法，本文介绍

我觉得这很令人困惑，因为我假设虽然 (2) 使用术语“simhashing”，但它实际上是以类似于 (1) 的方式进行 minhashing，但关键区别在于集群只能由单个签名表示（甚至可能涉及复杂的多个哈希函数），而两个文档有更多与（1）相似的机会，因为签名可以在多个“带”中发生冲突。(3) 似乎完全不同，因为签名是根据它们的汉明距离进行比较的，而 LSH 技术意味着对签名进行多次排序，而不是对它们进行捆绑。我还看到（在其他地方）最后一种技术可以包含加权的概念，它可以用来更加强调某些文档部分，而这似乎在 (1) 和 (2) 中缺乏。

所以最后，我的两个问题：

(a) 是否有一种（令人满意的）方法可以连接这三种算法？

(b) 有没有办法将权重概念从 (3) 导入到 (1)？

我想找出一种局部敏感散列算法，以便将我的空间数据分成多个桶（reducer 任务）。空间数据实际上是轨迹，所以从我对 LSH 的理解来看，轨迹将表示一组 2d 点。

谢谢，亚当

我正在实现一个近邻搜索应用程序，它将找到类似的文档。到目前为止，我已经阅读了很多 LSH 相关材料（LSH 背后的理论有点令人困惑，我还不能 100% 理解它）。

我的代码能够使用 minhash 函数计算签名矩阵（我接近尾声）。我还在签名矩阵上应用了条带策略。但是我无法理解如何将带中的签名向量（列）散列到桶中。

我的最后一个问题可能是最重要的一个，但我必须问一些introduction问题：

q1：散列函数是否只会将相同的向量映射到同一个桶？（假设我们有足够的桶）

q2：哈希函数是否应该将相似的向量映射到同一个桶？如果是，那么这种相似性的程度/定义是什么，因为我不是在计算比较，而是在做散列。

q3：根据上面的问题，我应该使用什么样的哈希表算法？

q4：我认为我最弱的一点是我不知道如何生成一个以向量作为输入并选择一个桶作为输出的哈希函数。我可以根据 q1 和 q2 自己实现一个......关于为 LSH 生成散列函数有什么建议bucketing吗？

我正在用 Java 编写一个 minhashing 算法，它要求我生成任意数量的随机散列函数（在我的例子中为 240 个散列函数），并通过它运行任意数量的整数（目前为 2000 个）。

为了做到这一点，我一直在为 240 个散列函数中的每一个生成随机数 a、b 和 c（范围从 1 到 2001）。然后，我的哈希函数返回 h = ((a*x) + b) % c，其中 h 是返回值，x 是通过它的整数之一。

这是随机散列的有效实现，还是有更常见/可接受的方法来做到这一点？

这篇文章问了一个类似的问题，但我仍然对答案的措辞感到有些困惑： Minhash implementation how to find hash functions for permutations

我有一个大的稀疏 numpy/scipy 矩阵，其中每一行对应于高维空间中的一个点。我想进行以下类型的查询：

给定一个点P（矩阵中的一行）和一个距离epsilon ，找到与P的距离最大为epsilon的所有点。

我使用的距离度量是 Jaccard-similarity，所以应该可以使用 Locality Sensitive Hashing 技巧，例如 MinHash。

在某处是否有用于稀疏 numpy 数组的 MinHash 实现（我似乎找不到），还是有一种简单的方法可以做到这一点？

我不只是从 Github 中提取为非稀疏数组构建的东西的原因是 scipy 中的稀疏数据结构可能会导致时间复杂度爆炸。

我想使用局部敏感哈希来近似匹配字符串。我有许多字符串> 10M，可能包含拼写错误。对于每个字符串，我想与所有其他字符串进行比较，并根据某个阈值选择具有编辑距离的字符串。

也就是说，简单的解决方案需要 O(n^2) 比较。为了避免这个问题，我正在考虑使用Locality Sensitive Hashing。然后接近相似的字符串会导致相同的桶，我只需要在桶内搜索。所以它是 O(n*C)，其中 C 是桶大小。

但是，我不明白如何表示字符串。如果是文本，我会在向量空间中表示。我的主要问题是这是否可以使用 LSH 以及字符串的适当向量表示来处理。

我可以使用已经实现的库来完成这项任务吗？还是取决于我的问题，所以我必须自己实施？有没有这样做的python包？

作为我正在研究的项目的一部分，我正在寻找一种将 LSH 的散列函数与 Spark 结合使用的方法。有什么办法吗？

我正在尝试构建一个余弦局部敏感哈希，这样我就可以找到候选的相似项目对，而无需比较每个可能的对。我基本上可以正常工作，但我数据中的大多数对似乎在 -0.2 到 +0.2 范围内具有余弦相似度，所以我试图将它切得很细，并挑选余弦相似度为 0.1 及以上的东西。

我一直在阅读《挖掘海量数据集》第 3 章。这谈到了通过 Amplifying Locality-Sensitive Family 来提高候选对选择的准确性。我想我只是理解数学解释，但我很难看到我是如何实际实现的。

到目前为止我所拥有的如下

1. 我说过 1000 部电影，每部电影都有来自 100 万用户的评分。每部电影由用户分数的稀疏向量表示（行号 = 用户 ID，值 = 用户分数）
2. 我构建了 N 个随机向量。矢量长度与电影矢量的长度（即用户数量）相匹配。向量值为 +1 或 -1。我实际上将这些向量编码为二进制以节省空间，+1 映射到 1，-1 映射到 0
3. 我通过获取电影的点积和 N 个随机向量中的每一个来为每部电影构建草图向量（或者更确切地说，如果我通过水平放置 N 个随机向量并将它们彼此叠加来创建矩阵 R，那么草图对于电影 m 是 R*m)，然后取结果向量中每个元素的符号，所以我以 +1s 和 -1s 的每个电影的草图向量结束，我再次将其编码为二进制。每个向量的长度为 N 位。
4. 接下来，我通过执行以下操作来寻找类似的草图
   1. 我将草图矢量分成 r 位的 b 条带
   2. 每个 r 位带是一个数字。我将该数字与乐队编号结合起来，并将电影添加到该数字下的哈希桶中。每部电影可以添加到多个存储桶中。
   3. 然后我查看每个桶。同一桶中的任何电影都是候选对。

将此与 mmds 的 3.6.3 进行比较，我的 AND 步骤是当我查看 r 位带时 - 如果 r 位具有相同的值，则一对电影通过 AND 步骤。我的 OR 步骤发生在桶中：如果电影都在任何桶中，它们就是候选对。

这本书建议我可以通过添加更多的 AND 和 OR 步骤来“放大”我的结果，但我不知道如何实际做到这一点，因为对进一步层的构造过程的解释是检查成对相等性而不是想出桶号。

谁能帮我理解如何做到这一点？

我有一个应用了简要方法的图像数据集。我使用了以下教程：http ://docs.opencv.org/trunk/doc/py_tutorials/py_feature2d/py_brief/py_brief.html

目前，矩阵的大小变化很大。我有兴趣固定矩阵的大小，但我不知道如何去做。如果有使用其他方法（如 SIFT 和 SURF）的解决方案，请告诉我。

我正在尝试在 PySpark 中实现局部敏感散列（基于spark-hash项目，用 Scala 编写）。散列步骤正在产生一些奇怪的行为。

在我获取为每个向量生成的 minhashes 列表的哈希值的步骤中，其输出似乎很大程度上取决于我是并行哈希（PySpark REPL）还是顺序哈希（之后collect）。例如，如果我以这种方式生成散列（调用groupByKey应该给我散列到同一波段的元素）：

我得到了一个类似于您所期望的列表；即，许多独特的数字：

但是，我采用完全相同的数据，但使用 Spark 构造对其进行哈希处理：

现在我得到一个如下所示的列表：

相同的哈希一遍又一遍地重复。但是，如果我使用相同的 Spark 构造，但在最后一秒将 ResultIterable 转换为frozenset：

现在我再次得到一个唯一哈希列表。知道发生了什么吗？ResultIterable在 Spark 执行期间，散列在对象上的工作方式有什么奇怪的吗？