c - 如何在局部敏感哈希中将 vector 哈希到桶中(使用杰卡德距离)？

Question

我正在实现一个近邻搜索应用程序，它将找到类似的文档。到目前为止，我已经阅读了相当一部分LSH相关 Material (LSH背后的理论有些令人困惑，我还不能100%理解它)。

我的代码能够使用 minhash 函数计算签名矩阵(我已接近尾声)。我还在签名矩阵上应用了 strip 策略。但是我无法理解如何将带中的(列)签名 vector 散列到存储桶中。

我的最后一个问题可能是最重要的一个，但我必须问一些介绍问题:

q1:哈希函数是否只会将相同 vector 映射到同一个存储桶？ (假设我们有足够的桶)

q2:哈希函数是否应该将相似 vector 映射到同一个存储桶？如果是，这种相似性的程度/定义是什么，因为我不是在计算比较，而是在进行哈希处理。

q3:根据上述问题，我应该使用哪种哈希表算法？

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

Answer 1

q1:您不应该对整个 vector 进行哈希处理，而应该对其中的一部分进行哈希处理。假设您有代表每个项目的长度为 100 的 vector ，您可以对长度为 20 的 5 个切片进行哈希处理。

q2:这是整个事情背后的主要思想:通过比较事物的各个部分是否相等来衡量相似性。如果将文本中的句子视为 vector ，则两个句子不太可能完全相同(具有相同的哈希输出)。但是，如果您将它们分成几部分并分别对各个部分进行散列，则相同位置中某些匹配的单个单词的散列将返回相同的散列输出，因此您可以了解句子的相似性。

切片的数量和长度是影响相似性结果准确性的重要参数。太多的切片会产生很多误报，而太少的切片只能识别最高程度的相似性。

您可以在《海量数据集挖掘》一书中找到更多相关信息，该书位于: http://infolab.stanford.edu/~ullman/mmds.html

q3:您需要一个数据结构，对于每个切片级别，它可以保留每个 vector 切片的哈希结果，以及生成它的 vector 。然后，当想要找到 vector X 的相似邻居时，你可以检查每个切片的数据结构，看看你得到的哈希输出是否也是另一个 vector 输出的。

q4:我不确定你的意思。如果对一个对象进行哈希处理，通常会得到一个位字符串、一个整数或一个 float 作为输出，具体取决于语言。就是那个桶。如果您在不同的对象上使用相同的哈希函数获得相同的输出，则意味着它们在同一个存储桶上进行哈希处理。