LSH是什么意思？

本文共计1659个文字，预计阅读时间需要7分钟。

假设通过用户-物品相似度进行个性化推荐，用户和物品的Embedding都位于一个(k)维的Embedding空间中，物品总数为(n)。计算一个用户与所有物品相似度的时间复杂度是O(kn)。

假设通过用户 - 物品相似度进行个性化推荐

用户和物品的 Embedding 都在一个 \(k\) 维的 Embedding 空间中，物品总数为 \(n\)，计算一个用户和所有物品向量相似度的时间复杂度是$ O(k*n)$

直觉的解决方案

• 基于聚类
• 基于索引

基于聚类的思想

优点：

离线计算好每个 Embedding 向量的类别，在线上我们只需要在同一个类别内的 Embedding 向量中搜索就可以。

缺点：

• 存在着一些边界情况，比如，聚类边缘的点的最近邻往往会包括相邻聚类的点，如果我们只在类别内搜索，就会遗漏这些近似点

• 中心点的数量 k 也不那么好确定，k 选得太大，离线迭代的过程就会非常慢，k 选得太小，在线搜索的范围还是很大

基于索引

Kd-tree（K-dimension tree）

首先，构建索引，然后用二叉树搜索

比如，希望找到点 q 的 m 个邻接点，我们就可以先搜索它相邻子树下的点，如果数量不够，我们可以向上回退一个层级，搜索它父片区下的其他点，直到数量凑够 m 个为止

缺点：

• 无法完全解决边缘点最近邻的问题。对于点 q 来说，它的邻接片区是右上角的片区，但是它的最近邻点却是深蓝色切分线下方的那个点。