问题标签 [minhash]

假设我在 O(D*sqrt(D)) 时间内预处理了一百万个文档（使用 minhash 计算的签名），其中 D 是文档数。当我得到一个查询文档时，我必须在 O(sqrt(D)) 时间内返回一百万个预处理文档中的第一个，使得 jaccard 相似度大于或等于 0.8。

如果没有与查询文档相似的文档足以达到该分数，我必须返回相似度至少为 c * 0.8（其中 c<1）且概率至少为 1 - 1/e^2 的文档。我怎样才能找到这个 minhash 方案的 C 的最大值？

我有一个应用程序，我应该在其中实现 Bloom Filters 和 Minhashing 来查找类似的项目。

我已经实现了布隆过滤器，但我需要确保我理解 Minhashing 部分来做到这一点：

• 该应用程序生成许多 k 长度的字符串并将其存储在一个文档中，然后将所有这些字符串插入到 Bloom 中。
• 我想实现 MinHash 的地方是为用户提供插入字符串的选项，然后进行比较并尝试在文档中找到最相似的字符串。

我必须将文件上的所有字符串都拼起来吗？问题是我真的找不到可以帮助我的东西，我发现的只是关于两个文档，而不是一个字符串到一组字符串。

我已经阅读了很多教程并尝试了一些 minhash LSH，但它无法生成相似度矩阵，而是只返回超过阈值的相似数据。我怎样才能生成它？我的意图是使用 LSH 结果进行聚类。

我有两个数据集，第一个是大型参考数据集，第二个数据集将通过 MinHash 算法从第一个数据集中找到最佳匹配。

对于字符串相似性，创建| （管）分开 dataString。

这是查找相似性的代码，dataString (x' + y' + a')并且dataString(x + y + a)工作正常，

如上所述，代码给出了完美的结果，但我的要求是，我必须a与a'OR进行比较b'，即。

这里我不能加入这两个数据集，因为它们没有公共字段，否则将是交叉连接。

那么有什么方法可以在 Apache Spark 2.2.0 中的分组数据中实现与 OR 条件的字符串相似性。

我有一个DataSet如下：

这个数据集的vector一部分就是所谓的“特征矩阵”，它表示“哪个文档包含哪个元素”。让我用一种更容易理解的格式写出特征矩阵：

如果你仔细看，你可以看到key0映射到doc0，其中包含元素a和d，这就是为什么它有一个由给出的(5,[0,2],[1.0,1.0])向量（向量是 下的列doc0。注意特征矩阵本身不包含element列和第一行，它们只是为了让阅读更容易。

现在，我的目标是使用N哈希函数来获得这个特征矩阵的Minhash 签名。

例如 let N = 2，换句话说，使用了两个 Hash 函数，我们也说这两个 Hash 函数如下所示：

是特征矩阵中x的行号。使用这两个哈希函数后，我期待“minhash 签名矩阵”如下所示：

现在，使用 Spark Java，我如何指定我想使用的这两个哈希函数，然后如何从给定的数据集生成上述 RDD（在这个问题的乞求时）？在实际测试用例中，我可能会使用大约 1000 个哈希函数，但现在了解如何使用 2 就足够了。

我一直在搜索和阅读 Spark 文档，但似乎很难找到一个处理程序。任何提示/指导都会对我有很大帮助。

先感谢您！

现在，我确实查看了文档，并且我有以下代码：

现在，我不知道如何解释结果...... Spark 使用了哪些哈希函数？我可以控制这些功能是什么吗？然后如何将结果散列到不同的存储桶中，以便相同存储桶中的文档是“相同”文档？毕竟，我们不想进行成对比较......

this is quite long, and I am sorry about this.

I have been trying to implement the Minhash LSH algorithm discussed in chapter 3 by using Spark (Java). I am using a toy problem like this:

the goal is to identify, among these four documents (doc0,doc1,doc2 and doc3), which documents are similar to each other. And obviously, the only possible candidate pair would be doc0 and doc3.

Using Spark's support, generating the following "characteristic matrix" is as far as I can reach at this point:

and here is the code snippets:

Now, there seems to be two main calls on the MinHashLSHModel model that one can use: model.approxSimilarityJoin(...) and model.approxNearestNeighbors(...). Examples about using these two calls are here: https://spark.apache.org/docs/latest/ml-features.html#lsh-algorithms

On the other hand, model.approxSimilarityJoin(...) requires us to join two datasets, and I have only one dataset which has 4 documents and I would like to figure out which ones in these four are similar to each other, so I don't have a second dataset to join... Just to try it out, I actually joined my only dataset with itself. Based on the result, seems like model.approxSimilarityJoin(...) just did a pair-wise Jaccard calculation, and I don't see any impact by changing the number of Hash functions etc, left me wondering about where exactly the minhash signature was calculated and where the band/row partition has happened...

The other call, model.approxNearestNeighbors(...), actually asks a comparison point, and then the model will identify the nearest neighbor(s) to this given point... Obviously, this is not what I wanted either, since I have four toy documents, and I don't have an extra reference point.

I am running out of ideas, so I went ahead implemented my own version of the algorithm, using Spark APIs, but not much support from MinHashLSHModel model, which really made me feel bad. I am thinking I must have missed something... ??

I would love to hear any thoughts, really wish to solve the mystery.

Thank you guys in advance!

根据这个问题，我在 CountVectorizer 之后应用 udf 过滤空向量。

这段代码通过 spark-shell 完美运行。但是，当我通过spark-submit运行相同的代码彻底驱动程序应用程序时，它会给出以下错误：

java.lang.ClassCastException：无法将 scala.collection.immutable.List$SerializationProxy 的实例分配给 scala.collection.Seq 类型的字段 org.apache.spark.rdd.RDD.org$apache$spark$rdd$RDD$$dependencies_在 org.apache.spark.rdd.MapPartitionsRDD 的实例中

如果我isNoneZeroVector从进程中删除 UDF，那么它的作用就像魅力一样。但根据MinHash 标准，输入向量必须至少有 1 个非零条目。

那么是否有任何不同的方式为 Spark ML 编写 UDF。我之前为 Spark SQL 编写了 UDF，并且按照上述语法可以正常工作。

我正在尝试实现 LSH spark 以在包含 50000 行和每行约 5000 个特征的非常大的数据集上为每个用户找到最近的邻居。这是与此相关的代码。

这项工作陷入了 approxSimilarityJoin() 函数，并且永远不会超出它。请让我知道如何解决它。

我有大量短文本，我想过滤掉彼此非常相似（或完全相同）的文本。我想使用在 Google Cloud Dataflow 上运行的 Apache Beam 来实现这一点。

我希望使用MinHash LSH算法来判断两个文本的相似度是否超过了某个阈值。

MinHash LSH 算法生成一种哈希表形式来（概率地）找到相似的句子。我希望这个哈希表对于一百万条文本大约为 1 Gb，并随着文本数量线性增长。

我看到将此用例映射到 Apache Beam 编程模型的唯一方法是使用Combine转换为所有项目生成哈希表（累加器将是哈希表；我能够实现“合并累加器”）然后将它用作ParDo我在哈希表中查找每个文本以查看它是否与另一个文本冲突的侧面输入。

这似乎是一件合理的事情吗？具体来说，累加器可能有几 GB 大是一个问题吗？

我正在使用 Apache Spark ML LSH 的 approxSimilarityJoin 方法加入 2 个数据集，但我看到了一些奇怪的行为。

在（内部）加入之后，数据集有点倾斜，但是每次一个或多个任务都需要花费过多的时间才能完成。

如您所见，每个任务的中位数是 6 毫秒（我在较小的源数据集上运行它来测试），但 1 个任务需要 10 分钟。它几乎不使用任何 CPU 周期，它实际上连接了数据，但速度如此之慢。下一个最慢的任务在 14 秒内运行，记录多 4 倍，实际上溢出到磁盘。

如果你看

join本身是pos&hashValue(minhash)上两个数据集的内连接，按照minhash规范&udf计算匹配对之间的jaccard距离。

分解哈希表：

杰卡德距离函数：

处理数据集的加入：

我尝试过缓存、重新分区甚至启用的组合spark.speculation，但都无济于事。

数据由必须匹配的带状疱疹地址文本组成： 53536, Evansville, WI=>53, 35, 36, ev, va, an, ns, vi, il, ll, le, wi 将与城市或邮政编码中存在拼写错误的记录有很短的距离。

这给出了非常准确的结果，但可能是连接偏差的原因。

我的问题是：

• 什么可能导致这种差异？（一项任务需要很长时间，即使它的记录较少）
• 如何在不损失准确性的情况下防止 minhash 中的这种偏差？
• 有没有更好的方法来大规模地做到这一点？（我不能 Jaro-Winkler / levenshtein 将数百万条记录与位置数据集中的所有记录进行比较）