问题标签 [locality-sensitive-hash]

我已经阅读了很多教程、文档和使用 min-hash 实现 LSH（位置敏感散列）的代码片段。

LSH 试图通过散列随机子集并聚合它们来找到两个集合的 Jaccard 系数。我查看了 code.google.com 中的实现，但也无法理解他们的方法。我了解论文Google 新闻个性化：可扩展的在线协作过滤，但我无法理解其中的任何实现。

有人可以用简单的话解释一下如何用 MinHash 实现 LSH 吗？

我有两个由两个彼此独立的不同系统生成的数组。我想通过仅比较从数组生成的几个数字来比较它们的相似之处。

现在，我只比较数组的最小值、最大值和总和，但我想知道是否有更好的算法？任何类型的散列算法都需要对数组之间的小浮点差异不敏感。

编辑：我要做的是验证两种算法是否生成相同的数据，而无需直接比较数据。所以算法应该对数据的变化敏感，对每个元素之间的微小差异相对不敏感。

给定一个大约 1000 万个查询的查询日志，我必须编写一个程序来询问用户的查询，并显示与输入查询最相似的 10 个查询作为输出。此外，在拼写错误的情况下，它可能会建议正确的拼写。

在这种情况下，我研究了一些关于局部敏感哈希的教程，但无法理解如何将它应用于这个问题。首先，我正在考虑按字典顺序对日志进行排序。但我认为就日志大小而言对日志进行排序不是一个好主意，因为将整个日志加载到内存中可能效率不高。

所以可以请任何人建议我解决这个问题的任何想法。谢谢你。

我有大约 100M 个数字向量（Minhash指纹），每个向量包含 0 到 65536 之间的 100 个整数，我正在尝试使用Jaccard 相似度对这个指纹数据库进行快速相似度搜索，即给定一个查询向量（例如 [ 1,0,30, 9, 42, ...]) 求该查询集与 100M 集数据库的交集/并集的比率。

要求是在笔记本电脑上在 <1 秒（不包括索引/文件 IO 时间）内返回查询向量的 k 个“最近邻”。所以显然需要某种索引，问题是最有效的方法是什么。

笔记：我想过使用SimHash，但在这种情况下实际上需要知道集合的交集的大小来识别包含而不是纯粹的相似性/相似性，但 Simhash 会丢失该信息。

我尝试使用Jeffrey Ullman 书中第3 章中描述的简单的局部敏感散列技术，将每个向量分成 20 个“带”或长度为 5 的片段，将这些片段转换为字符串（例如 [1, 2, 45, 2, 3] - >“124523”）并将这些字符串用作哈希表中的键，其中每个键包含“候选邻居”。但问题是它为其中一些片段创建了太多候选者，而改变乐队的数量也无济于事。

我正在阅读这个问题：

如何理解局部敏感哈希？

但是后来我发现计算余弦相似度的公式如下： Cos(v1, v2) = Cos(theta) = (hamming distance/signature length) * pi = ((h/b) * pi )

这意味着如果向量完全相似，则汉明距离为零，余弦值为 1。但是当向量完全不相似时，汉明距离将等于签名长度，因此我们有 cos( pi) 这将导致 -1。相似度不应该总是在 0 和 1 之间吗？

目前我正在研究如何使用 Locality-sensitive hashing 找到最近的邻居。然而，当我阅读论文和搜索网络时，我发现了两种算法：

1- 使用 L 个哈希表和 L 个随机 LSH 函数，从而增加两个相似文档获得相同签名的机会。例如，如果两个文档 80% 相似，那么它们有 80% 的机会从一个 LSH 函数中获得相同的签名。但是，如果我们使用多个 LSH 函数，则更有可能从其中一个 LSH 函数中获得文档的相同签名。这种方法在维基百科中有解释，希望我的理解是正确的：

http://en.wikipedia.org/wiki/Locality-sensitive_hashing#LSH_algorithm_for_nearest_neighbor_search

2- 另一种算法使用论文（第 5 节）中的一种方法，名为：Moses S. Charikar 的舍入算法中的相似性估计技术。它基于使用一个 LSH 函数生成签名，然后对其应用 P 排列，然后对列表进行排序。其实我不太了解这个方法，我希望有人能澄清一下。

我的主要问题是：为什么有人会使用第二种方法而不是第一种方法？我发现它更容易更快。

我真的希望有人能帮忙！！！

编辑：实际上我不确定@Raff.Edward 是否混合了“第一”和“第二”。因为只有第二种方法使用了半径，第一种方法只使用了由哈希族 F 组成的新哈希族 g。请查看 wikipedia 链接。他们只是使用许多 g 函数来生成不同的签名，然后对于每个 g 函数，它都有一个相应的哈希表。为了找到一个点的最近邻居，您只需让该点通过 g 函数并检查相应的哈希表是否存在冲突。因此，我如何将其理解为更多功能……更多的碰撞机会。

对于第一种方法，我没有发现任何关于半径的提及。

对于第二种方法，他们只为每个特征向量生成一个签名，然后对它们应用 P 个排列。现在我们有 P 个排列列表，每个列表包含 n 个签名。现在他们然后从 P 中对每个列表进行排序。在给定查询点 q 之后，他们为其生成签名，然后对其应用 P 排列，然后对每个排列和排序的 P 列表使用二进制搜索来找到最相似的签名查询 q。我在阅读了很多关于它的论文后得出了这个结论，但我仍然不明白为什么有人会使用这种方法，因为它在找到汉明距离时似乎并不快！！！！

对我来说，我只需执行以下操作即可找到查询点 q 的最近邻居。给定签名列表 N，我将为查询点 q 生成签名，然后扫描列表 N 并计算 N 中的每个元素与 q 的签名之间的汉明距离。因此，我最终会得到 q 的最近邻居。它需要 O(N) ！！！

想知道是否有人有任何关于该主题的不错的阅读材料，这很容易解释我想要做的是创建一个能够将不同的社交媒体配置文件合并到一个配置文件中的程序。

因此，例如，如果我有一个 twitter 个人资料页面、facebook 个人资料页面和一个 stackoverflow 个人资料页面，我希望能够创建一个程序，它可以肯定地说 X 来自不同社交媒体网络的以下 3/2 个人资料适用于同一个人 Y .

在此先感谢肖恩

我需要 C# 的局部性保留哈希函数实现（或可能的替代解决方案）。我想找出一种使用相似性阈值将字符串（即有时长度略有不同的相似基因序列标记）映射到相同存储桶中的方法。例如，如果两个基因序列标记的 Levenshtein 编辑距离 < 5、10、25 等的指定阈值......我想将它们分配给相同的桶/类别。但是，我不能使用编辑距离，因为事先不知道标记类别，而且计算开销很大。我需要一个非常有效的局部性保留哈希函数（或替代解决方案），它允许我根据阈值确定最接近哈希值的存储桶，或者在不存在足够接近的存储桶时创建一个新存储桶。至今，我什至无法在 C# 中实现一个局部性保留散列函数，只有出版物。我想我会在尝试自己写之前先问一下。

i have a set of strings along with their co-ordinates and rectangular bounds int two similar pages. these strings are different in three possible ways. (i) a string can be moved to a new location on a page. (ii) a string is in the same location but it is modified. say ( abc --> abd or ABC) (iii) a combination of (i) and (ii). (iv) a string might be missing.

i tried to use locality sensitive hashing but couldn't find a good hash function for this. Can anyone please suggest me a good hash function or another algorithm to solve this problem. thanks in advance

“LSH 有一些巨大的优势。首先，它很简单。你只需计算数据库中所有点的哈希值，然后从中制作一个哈希表。要查询，只需计算查询点的哈希值，然后检索数据库中的所有点哈希表中的同一个 bin。”

参考另一个问题的答案，我正在寻找对 LSH 分析过程的澄清。假设我有稀疏的特征向量（二进制，大部分为 0）并且想使用余弦距离作为具有阈值 alpha 的度量，这可能会有所不同。

1. 我的第一步是计算每个向量的哈希值。距离测量重要吗？（我想是的）。门槛重要吗？（我想没有）。如何找到合适的哈希函数？

   如果编程，我将具有如下功能：

   bytes[] getHash(Vector featureVec)

   然后我会把结果放在Map(long vectorId, bytes[] hashcode) <-vectorHashMap

2. 然后我从哈希中制作哈希表（将哈希放入垃圾箱）。我想至少在这里阈值很重要。我怎样才能做到这一点？

   如果编程，它会像：

   Map,Map createHashTable(Map vectorHashMap, long threshold)

   它返回两个地图：Map of (hashCode, bucketId)和Map of (bucketId, ListOfVectorIds)。

3. 然后我可以轻松地检索以 vectorId 作为输入并以 vectorIds 列表作为输出的邻居。