问题标签 [minhash]

我是 Spark ML 的新手。Spark ML 具有 Jaccard 距离的 MinHash 实现。请参阅文档https://spark.apache.org/docs/latest/ml-features#minhash-for-jaccard-distance。在示例代码中，用于比较的输入数据来自向量。我对示例代码没有任何疑问。但是当我使用文本文档作为输入，然后通过 word2Vec 将它们转换为向量时，我得到了 0 jaccard 距离。不知道我的代码有什么问题。我不明白的东西。提前感谢您的帮助。

从 Word2Vec，我得到了不同文档的不同向量。在比较两个不同的文档时，我希望得到一些 JaccardDistance 的非零值。但相反，我得到了全 0。下面显示了我运行程序时得到的结果：

文本：[嗨，我，听说过，关于 Scala] => 向量：[0.005808539432473481,-0.001387741044163704,0.007890049391426146,... ,04969391227]

文本：[I, wish, python, could, also, use, case, classes] => 向量：[-0.0022146602132124826,0.0032128597667906433,-0.00658524181926623,...,-3.716901264851913E-4]

在 Jaccard 距离小于 0.6 时近似加入 df1 和 df2：+---+---+---------------+ |id1|id2|JaccardDistance| +---+---+---------------+ | 1| 11| 0.0| | 0| 10| 0.0| | 2| 11| 0.0| | 0| 11| 0.0| | 1| 10| 0.0| | 2| 10| 0.0| +---+---+---------------+

我正在实现 minhash 和 LSH 以在 C++11 中对某些字符串元素进行相似性搜索。我的实现的 minhash 草图是 200 个 64 位整数的向量，即vector<uint64_t> MinHashSketch. 我有超过 200 万个条目，草图生成部分不需要太多时间。但是，分桶阶段需要很长时间。我想知道是否可以得到一些建议以使其更快一些。以下是我使用 LSH 的分桶阶段。

我在草图中使用连续的元素来创建一个成为桶 id 的哈希。如果bsize = 5，则（对于第 i 个元素）中的元素构成存储桶 ID 1-5, 6-10, 11-15, ... 196-200。MinHashSketch[i]遵循执行此操作的代码。

我的 spark 用 min_hash 编码了一些错误。只是不知道该怎么办？必须导入一些包？我是初学者，所以必须从小步骤开始...

在 (name_id, name) 组合的数据帧上调用 Spark 的 MinHashLSH 的 approxSimilarityJoin 时遇到问题。

我尝试解决的问题的摘要：

我有一个包含大约 3000 万个公司名称的唯一（name_id、name）组合的数据框。其中一些名称指的是同一家公司，但 (i) 拼写错误，和/或 (ii) 包含其他名称。不可能为每个组合执行模糊字符串匹配。为了减少模糊字符串匹配组合的数量，我在 Spark 中使用了 MinHashLSH。我的预期方法是使用具有相对较大 Jaccard 阈值的 approxSimilarityJoin（自连接），这样我就可以对匹配的组合运行模糊匹配算法，以进一步改善消歧。

我采取的步骤的摘要：

1. 使用 CountVectorizer 为每个名称创建一个字符计数向量，
2. 使用 MinHashLSH 及其 approxSimilarityJoin 并进行以下设置：
   • numHashTables=100
   • 阈值 = 0.3（用于 approxSimilarityJoin 的 Jaccard 阈值）
3. 在 approxSimilarityJoin 之后，我删除了重复的组合（认为存在匹配的组合（i，j）和（j，i），然后我删除（j，i））
4. 删除重复组合后，我使用 FuzzyWuzzy 包运行模糊字符串匹配算法，以减少记录数量并改善名称的消歧。
5. 最终，我在剩余的边 (i,j) 上运行 connectedComponents 算法来匹配哪些公司名称属于一起。

使用的部分代码：

解释计划edges

data外观如何：

使用的硬件：

1. 主节点：m5.2xlarge 8 vCore，32 GiB 内存，仅 EBS 存储 EBS 存储：128 GiB
2. 从节点 (10x)：m5.4xlarge 16 vCore，64 GiB 内存，仅 EBS 存储 EBS 存储：500 GiB

使用的 Spark 提交设置：

来自 Web UI 的任务错误

（部分）执行者日志：

执行者截图

我尝试了什么：

• 改变spark.sql.shuffle.partitions
• 改变spark.default.parallelism
• 重新分区数据框

我该如何解决这个问题？

提前致谢！

蒂斯

我正在处理 200k 个句子，我想使用 minhash 算法找到 Jaccard 相似度。但由于两个 for 循环，它变得非常慢。有人可以建议我一些好的实施吗？

以下是我当前的代码

我想知道LSH（局部敏感散列）是否适用于任何类型的文件以查找最近的邻居？意味着我到处都注意到了，只使用文本文件，但我想找到 wim、iso 和 zip 文件。

它也适用于 wim、iso 和 zip 文件。

提前致谢

我正在尝试使用其MinHash implementation查询 Elasticsearch 索引以查找近似重复项。我使用在容器中运行的 Python 客户端来索引和执行搜索。

我的语料库是一个 JSONL 文件，有点像这样：

我成功地创建了一个 Elasticsearch 索引，尝试使用自定义设置和分析器，从官方示例和MinHash 文档中获得灵感：

我通过 Kibana 验证索引创建没有大问题，并且通过访问http://localhost:9200/documents/_settings我得到了一些看起来井井有条的东西：

但是，使用以下命令查询索引：

res['hits']即使我将 my 设置为与我的语料库中的一个条目的文本完全body匹配， my也始终为空。换句话说，如果我尝试作为例如的值，我不会得到任何结果body

或子字符串，如

虽然理想情况下，我希望该过程返回近似重复项，分数是通过 MinHash 获得的查询和近似重复项的 Jaccard 相似性的近似值。

我的查询和/或索引 Elasticsearch 的方式有问题吗？我是否完全错过了其他东西？

PS：您可以查看https://github.com/davidefiocco/dockerized-elasticsearch-duplicate-finder/tree/ea0974363b945bf5f85d52a781463fba76f4f987以获取非功能性但希望可重现的示例（我也会在找到一个解决方案！）

据我了解，LSH 方法的主要功能之一是数据减少，甚至超出了底层哈希（通常是 minhashes）。我一直textreuse在 R 中使用这个包，我对它生成的数据的大小感到惊讶。textreuse是一个经过同行评审的ROpenSci包，所以我认为它可以正确地完成它的工作，但我的问题仍然存在。

假设我分别为我的 minhash 和 LSH 函数使用 256 个排列和 64 个波段 - 通常用于检测相对确定性(~98%) 相似性低至 50% 的实际值。

如果我使用 (256 perms) 散列一个随机文本文件TextReuseTextDocument并将其分配给trtd，我将拥有：

现在让我们为这个对象（64 个波段）创建 LSH 存储桶并将其分配给l，我将拥有：

因此，LSH 存储桶中保留的哈希值是原始 minhashes 的六倍。我理解这是因为textreuse 使用 md5 摘要来创建存储桶哈希。

但这不是太浪费/矫枉过正，我不能改进它吗？我们的数据缩减技术最终膨胀到这种程度是否正常？根据原始哈希（类似于 perms = 256 和bands = 256）匹配文档然后使用阈值清除误报不是更有效吗？

请注意，我已经查看了诸如Mining of Massive Datasets之类的典型文本，但这个问题仍然是关于这个特定实现的。另请注意，这个问题不仅出于好奇，而且出于需要。当您拥有数百万或数十亿个哈希值时，这些差异就会变得很重要。

我试图了解 Spark 中的 MinHash LSH 实现，org.apache.spark.ml.feature.MinHashLSH.

这两个文件似乎最相关：MinHashLSH.scala和LSH.scala。

要使用 MinHashLSH，文档说它需要一个numHashTables参数，即

LSH OR-amplification 中使用的哈希表数量的参数。

我的理解是hashFunction方法计算每个输入实例的 MinHash 签名（例如代表文档的单曲/令牌集合），例如

输出：

numHashTables每个输入实例使用的哈希函数的数量/MinHash 签名的长度也是如此。

但是我还没有看到任何与代码中的Mining of Massive Datasets一书的第 3 章介绍的条带技术相关的内容。带状技术基本上将每个实例的所有 MinHash 值划分为b带状，每个带中都有行，因此和r的乘积应该等于使用的散列函数的数量。在计算候选对时，调整并在包含假阳性或假阴性方面具有重要意义。rbbr

从我看到sameBucket inapproxNearestNeighbors和two-dataset join inapproxSimilarityJoin是如何实现的方式来看，看起来行数总是假设为1，那么band的数量等于散列函数的数量，即numHashTables，这也是与numHashTablesLSH OR-amplification 中使用的描述一致。

然而，如果r总是一个，假设numHashTables=10我们可以计算比我们需要基于等式更多的对（误报，相关代码）的JarccardkeyDistance距离（又名in ）MinHashLSH

Pr = 1 - (1 - s^r)^b

其中Pr是具有 Jaccard 相似性（不是距离）的一对s哈希到同一个桶的概率。

所以我想确认一下我的理解是否正确：在 的实现中假定行数始终为 1 org.apache.spark.ml.feature.MinHashLSH，并且numHashTables等于用于计算 MinHash 签名的哈希函数数和带数/局部敏感散列中使用的散列表。

我正在尝试以 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 的样本数据和人工生成的稀疏向量。