如何在局部性敏感散列(使用jaccard距离)中将向量散列到桶中？

Question

我正在实现一个近邻搜索应用程序，将发现类似的文件。到目前为止，我已经阅读了很大一部分与LSH相关的材料( LSH背后的理论有些令人困惑，我还无法将其100%地组合在一起)。

我的代码能够使用最小哈希函数(接近尾端)计算签名矩阵。我还在签名矩阵上应用了分带策略。但是，我无法理解如何将(列的)签名向量散列到桶中。

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

q1:哈希函数会只将相同的向量映射到同一个桶中吗？(假设我们有足够的桶)

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

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

q4:我认为我最薄弱的一点是，我不知道如何生成一个哈希函数，该函数以向量作为输入，并选择一个桶作为输出。我可以依靠q1和q2自己来实现.关于为LSH bucketing生成散列函数的建议

Answer 1

q1:你不应该散列整个向量，而是它的一部分。假设您有长度为100的向量表示每一项，则可以散列长度为20的5片。

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

切片的数量和长度是影响相似度结果准确性的重要参数。太多的切片会给出大量的假阳性，而太少的切片只能识别出最高程度的相似性。

您可以在“挖掘海量数据集”一书中找到有关此问题的更多信息，请参见：http://infolab.stanford.edu/~ullman/mmds.html

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

q4:我不知道你在这里是什么意思。如果您散列一个对象，您通常得到一个比特字符串或整数或浮点输出，这取决于语言。那是桶。如果在不同的对象上获得相同的哈希函数的输出，这意味着它们对同一个桶进行了散列处理。

Answer 2

为LSH生成哈希函数的一种简单方法如下：

对于给定的min-hash signature i，对于每个带b，计算带内行的和，称之为S_ib。为S_ib创建一个桶。对于完整的集合，存储桶将附加与S_ib匹配的条目，否则将生成一个新桶。

从集合导入defaultdict

....
LSHdictlist = [defaultdict(list) for b in range(bands)]
....
tempsum = np.int(np.sum(M[i,b*rowsinband:(b+1)*rowsinband]))
        LSHdictlist[b][tempsum].append(i)

你也可以用产品代替和。