Pyspark 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的指针都值得赞赏。

假设我有上面的 3 个哈希表，那么如果有超过 1 个哈希表，我如何确定每个哈希表中的桶来计算余弦相似度？我假设 LSH 在此任务中的使用是按“哈希”列中的值进行分组，并且仅在每个值中执行成对相似性。它是否正确？

Answer 1

\n

我假设 LSH 在此任务中的使用是按“散列”列中的值进行分组，并且仅在每个列中执行成对相似性。\n这是否正确？

\n

\n

是的，LSH 使用了一种在保持相似性的同时降低维度的方法。它将您的数据散列到存储桶中。然后仅比较最终位于同一桶中的项目。（计算距离）

\n

神奇之处在于调整存储桶和哈希函数的数量，以减少误报和漏报的数量。没有固定的数字，这取决于您的数据。

\n

r是您的存储桶大小，\nb是要使用的哈希函数的数量（或者您将用于检测匹配的存储桶的数量。

\n

从这篇文章帮助我了解了发生了什么。

\n

\n

让\xe2\x80\x99s 说你的签名矩阵有 100 行。考虑2种情况：

\n

b1 = 10 \xe2\x86\x92 r = 10

\n

b2 = 20 \xe2\x86\x92 r = 5

\n

在第二种情况下，2 个[向量] 出现在同一个桶中至少一次的机会更高，因为它们有更多的机会（20 比 10），并且比较的签名元素更少（5 比 10）

\n

\n

如果您需要加入，可以使用：approxSimilarityJoin并设置可接受的distance. （这是您需要调整的另一个参数，距离是落入至少一个哈希桶中的向量之间的距离，使它们可能彼此接近。）

\n

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

\n

您可以通过查看数据（来自连接）或使用 来了解向量之间距离的合理程度approxNearestNeighbors。如果您想要 10 个最近的邻居，您可以通过以下方法找到距离：

\n

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

\n