如何在局部敏感哈希中（使用jaccard距离）将向量哈希到桶中？

Question

我正在实现一个近邻搜索应用程序，可以查找相似的文档。到目前为止，我已经阅读了大量与局部敏感哈希（LSH）相关的材料（LSH背后的理论有些混乱，我还没有完全理解它）。我的代码能够使用minhash函数计算出签名矩阵（我接近尾声）。我还对签名矩阵应用了分块策略。然而，我不知道如何将一组列的签名向量哈希到桶中。

我最后一个问题可能是最重要的，但我必须先提一些“介绍”性的问题：

1. 哈希函数是否只会将相同的向量映射到同一个桶中？（假设我们有足够的桶）

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

3. 根据以上问题，我应该使用哪种类型的哈希表算法？

4. 我认为我最薄弱的地方就是我不知道如何生成以向量作为输入并选择桶作为输出的哈希函数。根据q1和q2，我可以自己实现一个哈希函数...关于为LSH“分组”生成哈希函数有什么建议吗？

- tozak

Answer 1

q1: 不应该对整个向量进行哈希，而是对其部分进行哈希。例如，如果你有长度为100的向量表示每个项，你可以将它们划分为5个长度为20的切片进行哈希。

q2: 整个想法的主要思路就是：通过比较部分内容的相等性来衡量相似度。如果你把文本中的句子视为向量，那么很难出现两个完全相同的句子（具有相同的哈希输出）。但是，如果你把它们分成几部分并将它们单独进行哈希，那么在相同位置上匹配的单词的哈希结果可能相同，因此你可以大致了解句子的相似程度。

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

你可以在这里找到有关此问题的更多信息："Mining of Massive Datasets"一书: http://infolab.stanford.edu/~ullman/mmds.html q3: 你需要一个数据结构，对于每个切片级别，它可以保留哈希结果的每个向量切片，以及产生它的向量。然后，当你想要查找向量X的相似邻居时，可以检查每个切片的数据结构，并查看你获得的哈希输出是否也被另一个向量输出。

q4: 我不确定你的意思是什么。如果你对一个对象进行哈希，通常会得到一个位字符串、整数或浮点数，具体取决于语言。那就是“桶”。如果你在不同的对象上使用同一哈希函数得到相同的输出，那就意味着它们哈希到了同一个“桶”中。

- anon

Answer 2

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

对于每个band b的给定min-hash签名i，计算band中行的总和，称其为S_ib。为S_ib创建一个bucket。对于完整集合，如果总和匹配S_ib，则将条目附加到bucket中，否则生成新的bucket。

from collections import 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)

你也可以使用“积”代替“和”。

- user3777579