如何在Locality Sensitive Hashing（使用jaccard距离）中将向量哈希到桶中？
我正在实现一个近邻搜索应用程序，它将找到类似的文档。 到目前为止，我已经阅读了LSH相关材料的很大一部分（LSH背后的理论是某种令人困惑的，我还不能100％地对其进行比较）。
我的代码能够使用minhash函数计算签名矩阵（我接近结尾）。 我还在签名矩阵上应用了条带策略。 但是我无法理解如何将带中的签名向量（列）散列到桶中。
我的最后一个问题可能是最重要的问题，但我不得不问一些introduction问题：
问题1：哈希函数是否只将相同的向量映射到同一个桶？ （假设我们有足够的水桶）
问题2：哈希函数是否应该将相似的向量映射到同一个桶？ 如果是，那么这种相似性的程度/定义是什么，因为我不是在计算比较，而是在进行散列。
q3：根据上面的问题，我应该使用什么样的哈希表算法？
问题4：我认为我最弱的一点是我不知道如何生成一个哈希函数，它将向量作为输入并选择一个桶作为输出。 我可以根据q1和q2自己实现一个…有关为LSH bucketing生成哈希函数的任何建议吗？
问题1：你不应该对整个向量进行散列，而是对其中的一部分进行散列。 假设您有代表每个项目的长度为100的向量，您可以散列5个长度为20的切片。
问题2：这是整个事情背后的主要思想：通过比较事物的各个部分来衡量相似性。 如果将文本中的句子视为向量，则2个句子不可能完全相同（具有相同的哈希输出）。 但是，如果将它们分成几部分并对各部分进行散列，则在相同位置对某些匹配单个单词的散列将返回相同的散列输出，因此您可以了解句子的相似性。
切片的数量和长度是这里的重要参数，会影响相似结果的准确性。 太多的切片会产生大量的误报，而太少的切片只能识别最高的相似度。
您可以在“大规模数据集挖掘”一书中找到更多相关信息，请访问： http ： //infolab.stanford.edu/~ullman/mmds.html
q3：您需要一个数据结构，对于每个切片级别，它可以保留每个矢量切片的散列结果，以及生成它的矢量。 然后，当想要找到Vector X的类似邻居时，可以检查每个切片的数据结构，看看你得到的哈希输出是否也被另一个向量输出。
问题4：我不确定你的意思。 如果您对对象进行哈希处理，通常会根据语言获取位串或整数或浮点数作为输出。 这就是桶。 如果在不同的对象上使用相同的散列函数获得相同的输出，则意味着它们在同一个桶上进行散列。
为LSH生成哈希函数的一种简单方法如下：
对于每个频带b的给定min-hash signature i，计算频带中的行总和，将其S_ib 。 为S_ib创建一个存储桶。 对于完整集， 存储桶将附加总和与S_ib匹配的条目，否则将生成新存储桶 。
来自集合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)
你也可以使用产品而不是总和。