电火花LSH与余弦相似

Question

我有很多用户，每个用户都有一个相关联的向量。我想计算每个用户之间的余弦相似度。根据大小，这是禁止的。看起来，LSH是一个很好的近似步骤，我理解它将创建一个桶，在这里，用户被映射到同一个桶中，在这个桶中，它们很可能是相似的。在Pyspark中，下面的示例如下：

from pyspark.ml.feature import BucketedRandomProjectionLSH
from pyspark.ml.linalg import Vectors
from pyspark.sql.functions import col

dataA = [(0, Vectors.dense([1.0, 1.0]),),
         (1, Vectors.dense([1.0, -1.0]),),
         (4, Vectors.dense([1.0, -1.0]),),
         (5, Vectors.dense([1.1, -1.0]),),
         (2, Vectors.dense([-1.0, -1.0]),),
         (3, Vectors.dense([-1.0, 1.0]),)]
dfA = ss.createDataFrame(dataA, ["id", "features"])

brp = BucketedRandomProjectionLSH(inputCol="features", outputCol="hashes", bucketLength=1.0, numHashTables=3)
model = brp.fit(dfA)
model.transform(dfA).show(truncate=False)


+---+-----------+-----------------------+
|id |features   |hashes                 |
+---+-----------+-----------------------+
|0  |[1.0,1.0]  |[[-1.0], [0.0], [-1.0]]|
|1  |[1.0,-1.0] |[[-2.0], [-2.0], [1.0]]|
|4  |[1.0,-1.0] |[[-2.0], [-2.0], [1.0]]|
|5  |[1.1,-1.0] |[[-2.0], [-2.0], [1.0]]|
|2  |[-1.0,-1.0]|[[0.0], [-1.0], [0.0]] |
|3  |[-1.0,1.0] |[[1.0], [1.0], [-2.0]] |
+---+-----------+-----------------------+

任何关于如何最好地设置bucketLength和numHashTables的提示都会受到欢迎。

假设我有上面的三个哈希表，如果有超过一个，我如何从每个哈希表中确定桶来计算余弦相似度？我假设LSH用于这个任务是根据"hashes“列中的值进行分组，并且只在每个列中执行成对的相似操作。这是正确的吗？

Answer 1

我假设LSH用于这个任务是根据"hashes“列中的值进行分组，并且只在每个列中执行成对的相似操作。这是正确的吗？

是的，LSH在保持相似性的同时，使用了一种降维方法。它会将你的数据散列到一个桶里。只有在同一个桶中结束的项目才会被比较。(计算距离)

其神奇之处在于调整桶和散列函数的数量，以减少假阳性和假阴性的数量。没有一个设定的数字，它取决于您的数据。

r是您的桶大小，b是要使用的散列函数的数量(或用于检测匹配的桶数)。

帮助我了解了发生了什么。

假设您的签名矩阵有100行。审议2起案件： b1 = 10→r= 10 b2 = 20→r=5 在第二种情况下，两个向量至少在同一个桶中出现一次的可能性更高，因为它们有更多的机会(20vs10)，比较的签名元素较少(5vs10)。

如果需要加入，可以使用：approxSimilarityJoin并设置可接受的distance。(这是另一个需要调优的参数，距离是至少在散列桶上的向量之间的距离，使它们很可能接近彼此。)

distance = 300

model.approxSimilarityJoin(df, df2, distance, distCol="EuclideanDistance").select(
    col("datasetA.id").alias("idA"),
    col("datasetB.id").alias("idB"),
    col("EuclideanDistance")).show()

您可以通过查看数据(从联接)或使用approxNearestNeighbors来了解向量之间的距离是如何合理的。如果你想要10个最近的邻居，你可以在这里找到距离：

NumberOfNeigthbors = 10
CandidateVector = Vectors.dense([1.0, 2.0])
model.approxNearestNeighbors(df2, CandidateVector, NumberOfNeigthbors).collect()
[Row(id=4, features=DenseVector([2.0, 2.0]), hashes=[DenseVector([1.0])], distCol=1.0)]