召回层，“局部敏感哈希”（Locality Sensitive Hashing,LSH）

1. 局部敏感哈希的基本原理

定性的结论：欧式空间中，将高维空间的点映射到低维空间，原本接近的点在低维空间中肯定依然接近，但原本远离的点则有一定概率变成接近的点。

映射操作会损失部分距离信息，如果我们仅采用一个哈希函数进行分桶，必然存在相近点误判的情况，因此，我们可以采用 m 个哈希函数同时进行分桶。如果两个点同时掉进了 m 个桶，那它们是相似点的概率将大大增加。通过分桶找到相邻点的候选集合后，我们就可以在有限的候选集合中通过遍历找到目标点真正的 K 近邻了。

事实上距离的定义有很多种，比如“曼哈顿距离”“切比雪夫距离”“汉明距离”等等

2. 局部敏感哈希的多桶策略

假设有 A、B、C、D、E 五个点，有 h1和 h2两个分桶函数。使用 h1来分桶时，A 和 B 掉到了一个桶里，C、D、E 掉到了一个桶里；使用 h2来分桶时，A、C、D 掉到了一个桶里，B、E 在一个桶。那么请问如果我们想找点 C 的最近邻点，应该怎么利用两个分桶结果来计算呢？

如果我们用“且”（And）操作来处理两个分桶结果之间的关系，那么结果是这样的，找到与点 C 在 h1函数下同一个桶的点，且在 h2函数下同一个桶的点，作为最近邻候选点。我们可以看到，满足条件的点只有一个，那就是点 D。也就是说，点 D 最有可能是点 C 的最近邻点。

用“且”操作作为多桶策略，可以最大程度地减少候选点数量。但是，由于哈希分桶函数不是一个绝对精确的操作，点 D 也只是最有可能的最近邻点，不是一定的最近邻点，因此，“且”操作其实也增大了漏掉最近邻点的概率。

那如果我们采用“或”（Or）操作作为多桶策略，又会是什么情况呢？具体操作就是，我们找到与点 C 在 h1函数下同一个桶的点，或在 h2函数下同一个桶的点。这个时候，我们可以看到候选集中会有三个点，分别是 A、D、E。这样一来，虽然我们增大了候选集的规模，减少了漏掉最近邻点的可能性，但增大了后续计算的开销。

我们到底应该选择“且”操作还是“或”操作，以及到底该选择使用几个分桶函数，每个分桶函数分几个桶呢？这些都还是工程上的权衡问题

  1. 点数越多，我们越应该增加每个分桶函数中桶的个数；相反，点数越少，我们越应该减少桶的个数；

  2. Embedding 向量的维度越大，我们越应该增加哈希函数的数量，尽量采用且的方式作为多桶策略；相反，Embedding 向量维度越小，我们越应该减少哈希函数的数量，多采用或的方式作为分桶策略。

局部敏感哈希实践

def embeddingLSH(spark:SparkSession, movieEmbMap:Map[String, Array[Float]]): Unit ={

//将电影embedding数据转换成dense Vector的形式，便于之后处理

val movieEmbSeq = movieEmbMap.toSeq.map(item => (item._1, Vectors.dense(item._2.map(f => f.toDouble))))

val movieEmbDF = spark.createDataFrame(movieEmbSeq).toDF("movieId", "emb")

//利用Spark MLlib创建LSH分桶模型

val bucketProjectionLSH = new BucketedRandomProjectionLSH()

.setBucketLength(0.1)

.setNumHashTables(3)

.setInputCol("emb")

.setOutputCol("bucketId")

//训练LSH分桶模型

val bucketModel = bucketProjectionLSH.fit(movieEmbDF)

//进行分桶

val embBucketResult = bucketModel.transform(movieEmbDF)


//打印分桶结果

println("movieId, emb, bucketId schema:")

embBucketResult.printSchema()

println("movieId, emb, bucketId data result:")

embBucketResult.show(10, truncate = false)


//尝试对一个示例Embedding查找最近邻

println("Approximately searching for 5 nearest neighbors of the sample embedding:")

val sampleEmb = Vectors.dense(0.795,0.583,1.120,0.850,0.174,-0.839,-0.0633,0.249,0.673,-0.237)

bucketModel.approxNearestNeighbors(movieEmbDF, sampleEmb, 5).show(truncate = false)

}


  • 无标签