1

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

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

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

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

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

data = [
    (0, Vectors.sparse(6, [0, 1, 2], [1.0, 1.0, 1.0])),
    (1, Vectors.sparse(6, [2, 3, 4], [1.0, 1.0, 1.0])),
]

df = spark.createDataFrame(data, ["id", "features"])

mh = MinHashLSH(inputCol='features', outputCol='hashes', numHashTables=5)
mh_model = mh.fit(df)
mh_model.transform(df).show(truncate=False)

输出：

+---+-------------------------+---------------------------------------------------------------------------------+
|id |features                 |hashes                                                                           |
+---+-------------------------+---------------------------------------------------------------------------------+
|0  |(6,[0,1,2],[1.0,1.0,1.0])|[[3.84540858E8], [5.873031E8], [6.9646868E8], [3.95377821E8], [1.050129459E9]]   |
|1  |(6,[2,3,4],[1.0,1.0,1.0])|[[3.19950681E8], [1.87323383E8], [1.237542508E9], [6.11223988E8], [2.07958525E8]]|
+---+-------------------------+---------------------------------------------------------------------------------+

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 签名的哈希函数数和带数/局部敏感散列中使用的散列表。

4

1 回答 1

1

我在https://spark.apache.org/docs/latest/ml-features#feature-transformation上看到

outputCol 的类型是 Seq[Vector]，其中数组的维度等于 numHashTables，向量的维度当前设置为 1。在未来的版本中，我们将实现 AND 放大，以便用户可以指定这些向量的维度.

所以看起来确实每个波段中的行数（用于 AND 放大）设置为 1。

于 2020-12-12T17:30:04.463 回答