问题标签 [locality-sensitive-hash]

嗨，我在试图解决这个 excersie 时不知所措。我真的很感激一些帮助！谢谢你。

定义：如果对于任何 q，p ∈ S ，哈希函数族 H = {h : X → U} 是 (r ₁ , r ₂ , p ₁ , p _{2 ) 敏感的：}

• 如果 p ∈ B(q, r ₁ ) 则 Pr[h(q) = h(p)] ≥ p ₁（其中概率超过 h 是从 H 中均匀随机选择的）。
• 如果 p 不在 B(q, r2) 中，则 PH[h(q) = h(p)] ≤ p ₂

要将 LSH 用于 ε-PLEB，我们首先固定两个参数 k，L，它们将在下面选择。对于每个 i = 1..`，我们将 P 中的每个点映射（在预处理中）到一个桶 g _i (p) = (h _i 1(p), . . . , h _i k(p))，其中 h _i 1...h _i k 是从 H 中均匀随机选择的。注意，这意味着桶的数量是 |U| ^k，每个 p 映射到其中的 L 个。为了处理查询 q，我们搜索所有桶 g ₁ (q)...g _L (q)。设 p ₁ ...p _t是这些桶中所有点的组合。对于每个这样的 p _j ，如果 p _j ∈ B(q, r2) 则返回 YES 和 p_Ĵ。否则（如果没有 p _j在 B(q, r ₂ ) 内）返回 NO。

现在设置 k = log _1/p2 n, l = n ^ρ其中 ρ = (log(1/p1))/(log(1/p2))。固定一个查询 q，并证明以下两个主张： 1.如果数据集 P 包含 p 使得 q ∈ B(p, r1)，那么至少有 1/2 的概率，p 将与 q 共享一个桶。换句话说，至少有 1/2 的概率存在 j ∈ [ ] such that g<sub>j</sub> (q) = g<sub>j</sub> (p). **2.** Define a point p to be bad for q if q 6∈ B(p, r2). Then the expected number of bad points colliding with q at some hash function g<sub>j</sub> is at most 。

我想在 python 中实现 LSH 作为大学练习。但首先，我必须使用 kshingle 库将文件夹中的所有文本文件组合在一起。我无法读取/循环文件，将它们组合起来并将它们写入数组。我试过这个，但我得到一个空数组：

我正在尝试实施这篇论文

浏览器指纹编码方法提高网络流量中用户识别的有效性

我有几个关于 LHS 算法和建议实现的问题：

• LSH 算法仅在您有很多文档要相互比较时使用（因为它应该将相似的文档放在我得到的相同存储桶中）。例如，如果我有一个新文档并且我想计算与其他文档的相似度，我必须从头开始重新启动 LHS 算法，包括新文档，对吗？

• 在“海量数据集的挖掘，第 3 章”中，据说对于 LHS，我们应该在每个波段使用一个哈希函数。每个哈希函数创建 n 个桶。所以，对于第一个波段，我们将有 n 个桶。对于第二个频段，我应该继续使用相同的哈希函数（这样我就可以继续使用与以前相同的存储桶）还是另一个（以 m>>n 存储桶结束）？

• 这个问题与上一个问题有关。如果我对所有波段使用相同的哈希函数，那么我将有 n 个桶。这里没问题。但是如果我必须使用更多的哈希函数（每行一个不同的函数），我最终会得到很多不同的桶。我应该测量每个桶中每一对的相似度吗？（如果我必须只使用一个哈希函数，那么这不是问题）。

• 在论文中，我理解了算法的大部分内容，除了它的结尾。基本上，通过 minhashing 创建了两个签名矩阵（一个用于稳定特征，一个用于不稳定特征）。然后，他们在第一个矩阵上使用 LSH 来获得候选对列表。到目前为止，一切都很好。最后会发生什么？他们在第二个矩阵上执行 LHS 吗？如何使用第一个 LHS 的结果？我看不到第一个和第二个 LHS 之间的关系。

• 最后一步的输出应该是配对候选列表，对吗？我所要做的就是对它们执行 Jaccard 相似性并设置阈值，对吗？

感谢您的回答！

我正在使用 spark 创建一个数据集，以使用 pyspark.ml 中的 minhashLSH 算法。

我有一张这样的桌子：

基本上，我的目标是创建一个这样的表：

...等等。

基本上，我想将值放在行上，将用户放在列上。每个特征都有不同的唯一值。

如果用户 1 在特征 1 中有 value_1_1，则取值为 1，否则为 0。如果用户 2 在特征 2 中有 value_2_1，则取值为 1，否则为 0

... 等等。

我这样做基本上是因为我想在 pyspark 中使用 minhashLSH 算法计算 jaccard 相似度。

有什么建议吗？

谢谢，祝你有美好的一天！

PS 以上数值只是一个例子！！！这不是我现在的 DF

我试图理解这篇论文，但我真的在努力完成一些步骤。
我添加了一些让我感到困惑的片段，但整个代码都可以在这里找到。

基本上，第一步是计算一个共现矩阵和一个稀有词列表，我对此很好。

然后我们需要一个 NN 列表和一个 NN 矩阵作为自动编码器的输入，并获得我们使用 LSH 的那些。

在这里，据我了解，我们正在为输入数据创建一个 hashsize-bit 哈希，然后我们正在为 co-occ 矩阵的每个值计算一个索引向量。

然后我们正在创建 NN 列表和矩阵：

这段代码有两点我不明白：首先，查询所有罕见词的每个共现值是什么意思（lsh.query(cooc_matr[rarewords[i]], num_results=friends,distance_func='euclidean')）。
其次，我完全不知道这个循环的目的是什么：

以及为什么将 a 附加str(8)到fri列表中。

如果您能帮助我理解，我将不胜感激。如果你觉得我的问题很愚蠢，我很抱歉，但我只是这件事的初学者。

我正在一个 256 个字符长的字符串和一个由 9000 个条目组成的语料库之间进行相似性搜索，每个条目大约 1000 个单词。

我使用过LocalitySensitiveHashing，请参阅https://github.com/Jmkernes/Locality-sensitive-hashing-tutorial/blob/main/LocalitySensitiveHashing.ipynb。它创建了我过滤的对。

这里的一个问题是documents每个条目都包含大约 1000 个单词，这使得搜索效率低下，因为它们都必须保留在内存中。一般来说，它非常慢。

目标是快速输出与256个字符长字符串内容相似度最大的语料库的索引。

我的想法是：条目需要简化并序列化为文件以便快速恢复。

您推荐哪种论文或实施？