java - 使用 Spark (Java) 实现 minhash LSH

Question

这篇文章很长，对此我深表歉意。

我一直在尝试实现chapter 3中讨论的Minhash LSH算法。通过使用 Spark (Java)。我正在使用这样的玩具问题:

+--------+------+------+------+------+
|element | doc0 | doc1 | doc2 | doc3 |
+--------+------+------+------+------+
|   d    |   1  |  0   |  1   |  1   |
|   c    |   0  |  1   |  0   |  1   |
|   a    |   1  |  0   |  0   |  1   |
|   b    |   0  |  0   |  1   |  0   |
|   e    |   0  |  0   |  1   |  0   |  
+--------+------+------+------+------+

目标是在这四个文档( doc0 、 doc1 、 doc2 和 doc3 )中识别哪些文档彼此相似。显然，唯一可能的候选对是 doc0和doc3 .

使用 Spark 的支持，生成以下“特征矩阵”是我目前所能达到的:

+----+---------+-------------------------+
|key |value    |vector                   |
+----+---------+-------------------------+
|key0|[a, d]   |(5,[0,2],[1.0,1.0])      |
|key1|[c]      |(5,[1],[1.0])            |
|key2|[b, d, e]|(5,[0,3,4],[1.0,1.0,1.0])|
|key3|[a, c, d]|(5,[0,1,2],[1.0,1.0,1.0])|
+----+---------+-------------------------+

这是代码片段:

CountVectorizer vectorizer = new CountVectorizer().setInputCol("value").setOutputCol("vector").setBinary(false);
Dataset<Row> matrixDoc = vectorizer.fit(df).transform(df);

MinHashLSH mh = new MinHashLSH()
  .setNumHashTables(5)
  .setInputCol("vector")
  .setOutputCol("hashes");

MinHashLSHModel model = mh.fit(matrixDoc);

现在，MinHashLSHModel model 上似乎有两个主要调用可以使用:model.approxSimilarityJoin(...)和model.approxNearestNeighbors(...) 。有关使用这两个调用的示例如下:https://spark.apache.org/docs/latest/ml-features.html#lsh-algorithms

另一方面，model.approxSimilarityJoin(...)要求我们加入两个数据集，而我只有一个数据集，其中有 4 个文档，我想弄清楚这四个文档中哪些是彼此相似的，所以我没有第二个数据集要加入...只是为了尝试一下，我实际上将我唯一的数据集与其自身连接起来。根据结果​​，看起来像 model.approxSimilarityJoin(...)刚刚进行了成对的 Jaccard 计算，我没有看到更改哈希函数数量等的任何影响，这让我想知道 minhash 签名到底是在哪里计算的以及带/行分区发生在哪里......

另一个电话，model.approxNearestNeighbors(...) ，实际上询问一个比较点，然后模型将识别该给定点的最近邻居...显然，这也不是我想要的，因为我有四个玩具文档，并且我没有额外的引用点。

我已经没有想法了，所以我继续使用 Spark API 实现了我自己的算法版本，但 MinHashLSHModel model 的支持不多 ，这确实让我感觉很糟糕。我想我一定错过了什么...??

我很想听听任何想法，真的很想解开这个谜团。

先谢谢大家了!

Answer 1

• minHash 签名计算发生在model.approxSimilarityJoin(...) 本身，其中 model.transform(...)对每个输入数据集和哈希签名调用函数在加入它们并进行成对杰卡德之前计算距离计算。那么，改变hash个数的影响函数可以在这里看到。
• 在model.approxNearestNeighbors(...)中，使用创建模型时可以看到相同的影响调用 transform(...) 的 minHash.fit(...) 函数输入数据集。