6

我正在实现一个近邻搜索应用程序，它将找到类似的文档。到目前为止，我已经阅读了很多 LSH 相关材料（LSH 背后的理论有点令人困惑，我还不能 100% 理解它）。

我的代码能够使用 minhash 函数计算签名矩阵（我接近尾声）。我还在签名矩阵上应用了条带策略。但是我无法理解如何将带中的签名向量（列）散列到桶中。

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

q1：散列函数是否只会将相同的向量映射到同一个桶？（假设我们有足够的桶）

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

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

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

4

2 回答 2

6

q1：您不应该散列整个向量，而是散列其中的一部分。假设您有代表每个项目的长度为 100 的向量，您可以散列 5 个长度为 20 的切片。

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

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

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

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

q4：我不确定你在这里的意思。如果你散列一个对象，你通常会得到一个位串或一个整数或一个浮点数作为输出，这取决于语言。就是那个桶。如果您在不同的对象上使用相同的散列函数得到相同的输出，这意味着它们在同一个桶上散列。

于 2014-04-09T17:23:48.213 回答
0

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

min-hash signature对于每个带 b的给定i，计算带中的行的总和，将其称为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)

您也可以使用 product 而不是 sum。

于 2016-05-03T06:21:21.707 回答