问题标签 [lsh]

我的想法是提取CLS数据库中所有文本的令牌并将其保存在 CSV 或其他地方。所以当一个新的文本出现时Cosine Similarity/JAccard/MAnhattan/Euclidean，我必须使用一些近似值，而不是使用或其他距离，比如LSH, ANN (ANNOY, sklearn.neighbor)或这里给出的一个faiss。怎么可能呢？我的代码如下：

火炬：

使用张量流：

我认为可以将CLS令牌获取为：（如果错误请更正）

请告诉我这是否是正确的使用方式，我该如何使用其中的任何一种LSH, ANNOT, faiss或类似的东西？

因此，对于每个文本，都会有一个768长度向量，我们可以创建一个N(No of texts 10M)x768矩阵，我怎样才能找到与给定图像/嵌入/数据最相似 的数据点（文本）的索引点？top-5

我正在尝试以 SparseVectors 的形式计算某些 id 及其属性之间的 Jaccard 距离。

df 有两列，id并且sparse_vector. idcolumn 是一个字母数字 id 并且sparse_vectorcolumns 包含这样的记录SparseVector(243775, {0: 1.0, 1: 1.0, 2: 1.0, 3: 1.0, 4: 1.0, 6: 1.0, 7: 1.0, 8: 1.0, 9: 1.0, 10: 1.0, 11: 1.0, 12: 1.0, 13: 1.0, 14: 1.0, 15: 1.0, 16: 1.0, 24: 1.0, 30: 1.0, 31: 1.0, 32: 1.0, 61: 1.0, 88: 1.0, 90: 1.0, 96: 1.0, 104: 1.0, 153: 1.0, 155: 1.0, 159: 1.0, 160: 1.0, 161: 1.0, 162: 1.0, 169: 1.0, 181: 1.0, 194: 1.0, 212: 1.0, 220: 1.0, 222: 1.0, 232: 1.0, 303: 1.0, 390: 1.0, 427: 1.0, 506: 1.0, 508: 1.0, 509: 1.0, 518: 1.0, 554: 1.0, 568: 1.0, 798: 1.0, 1431: 1.0, 2103: 1.0, 2139: 1.0, 3406: 1.0, 3411: 1.0, 3415: 1.0, 3429: 1.0, 3431: 1.0, 3440: 1.0, 3443: 1.0, 3449: 1.0}))

当我计算 Jaccard 并写下数据时，我错过了很多 id 对。数据中共有 45k 个身份，因此输出应包含大约 45k*45k 对。

此外，当我将 1k ids 与 45k ids 进行比较并以这种方式进行所有 ids 时，我得到了所有可能的对，有点像批次。任何输入都会有所帮助。另外，我可以并行化代码以便我更快地拥有批处理系统吗？我在 emr 集群上运行代码并且有资源来增加集群大小。

以下脚本可用于生成带有 id 的样本数据和人工生成的稀疏向量。

显然，来自 spark 2.4 的 MLLib 的 LSHModel 支持 Spark Structured Streaming ( https://issues.apache.org/jira/browse/SPARK-24465 )。

但是，我不清楚如何。例如，可以将approxSimilarityJoinfromMinHashLSH转换 ( https://spark.apache.org/docs/latest/ml-features#lsh-operations ) 直接应用于流式数据帧？

我在网上找不到更多关于它的信息。有人可以帮助我吗？

spark mllib 中 minhashLSH 的拟合实际上有什么作用？据我了解，它会生成一组散列函数。这些函数是随机生成的吗？我们在这里用输入数据拟合什么？

我使用过的代码参考

• https://github.com/apache/spark/blob/master/mllib/src/main/scala/org/apache/spark/ml/feature/MinHashLSH.scala#L179-L186

• https://github.com/apache/spark/blob/master/mllib/src/main/scala/org/apache/spark/ml/feature/LSH.scala#L349-L354

上面生成的哈希函数可以在两个数据集上的 appx.similiarityjoin 中使用以生成哈希，并在这些哈希上计算 jaccard 距离。如果我在这里遗漏了什么，请告诉我。

我在 python 中为 minhash 和 shingle 运行此代码以检测重复的文本，但它给了我一个错误。用于绘图。我有一些错误。它说“float() 参数必须是字符串或数字，而不是 'dict_keys'”。我试图列出它，但它绘制错误。此外，字典的键和值是数字。

从这个例子开始，我在 Pyspark 上使用了局部敏感散列 (LSH) 来查找重复的文档。
关于我的数据库的一些注释：我有 4M 文本文件。每个文件平均有 20K 个字符。目前，我只考虑每个文档的前 500 个字符。
当我将字符数从 500 增加到 1000 时，会出现内存错误。
我已经尝试过处理管道的参数。我知道我可以避免内存错误增加 Ngram 中的 n 和减少 MinHashLSH 中的 NumHashTables。但是，这会过多地增加假阴性。
管道中是否还有其他可以提高性能的步骤？
我的目标是将字符数从 500 增加到 2000，而不会出现内存错误或非常长的计算时间（理想情况下，时间计算 < 6h）。
这是我的假数据代码：

我有两个数据集 dfA (5M) 和 dfB (6K)。我在 spark 2.2 上训练LSH ：

我跟踪一对距离为 17.59 的记录：

到目前为止，一切都很好。但是当我使用 approxSimilarityJoin 时，我没有得到我的 17.59 ，而是来自 A 的距离更大的其他人。

更准确地说，如果我使用persist，我永远不会得到那对，而没有persist ，我总是看到它存在。

每次运行生成的数据集都会显示大小大幅波动：

不过，我了解哈希冲突的随机性质：

1. 在这里使用持久性有什么问题吗？
2. 可以做些什么来提高approxSimilarityJoin的准确性？我看不到任何工具可以评估 BucketLength 的好坏。
3. 如果我提前知道 A 和 B，我应该在 A 和 B 的联合上训练brp吗？
4. 遍历 B 并按键查询每条记录是一种更稳定的方法吗？

嗨，我在试图解决这个 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 。

我有一个 LSH 表构建器实用程序类，如下所示（引用自此处）：

然后我执行以下命令来构建我的 LSH 表：

现在，当我尝试通过 Apache Beam（下面的代码）执行此操作时，它会抛出：

用于 Beam 的代码：

这就是我调用光束运行器的方式：

我正在尝试实施这篇论文

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

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

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

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

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

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

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

感谢您的回答！