java - 通过余弦距离获取前 N 个最近 vector 的最快方法

Question

我有一个巨大的 vector 列表(~100k)(代表单词并使用随机索引计算)并且必须找到给定的 1 个输入单词前 N 个最接近的 vector 。我现在的做法是按距离进行完整排序，然后提取前 N 个结果，但这需要太多时间才能使用，因为我必须计算 100k 距离。有没有更有效的方法呢？ vector 已经归一化，所以我只需要在计算距离时计算点积。

vector 存储在 Java HashMap<String, Vector> 中，其中 Vector 是稀疏 vector 的 la4j 类。

Answer 1

您可以将 vector 放入空间感知容器中，例如 R-tree或 k-d tree或 PK-Tree .

通过这种方式，您无需遍历所有数据集即可找到点，只需查看几个相邻的单元格即可。不要忘记，您不仅需要在单个单元格中搜索，还需要在相邻单元格中搜索，并且在多维空间中有很多邻居。

更新:您仍然需要手动测量距离。但是，您不需要遍历所有 vector 。

一个简单的解决方案——定义最大距离，迭代该距离内单元格内的所有 vector ，排序，选择前 N 个。

最佳解决方案(更难开发)——迭代搜索过程。例如，从输入 vector vX 所在的单个单元格开始，在该单元格中找到 N 个最近的 vector 。如果 vX 与第 N 个找到的 vector (最远的 vector )之间的距离小于 vX 与任何尚未搜索的单元格的最近点之间的距离，那么您将获得 N 个结果。否则，从最近的尚未搜索的单元格中添加 vector ，然后重复该过程。这里最复杂的事情 — 跟踪已经搜索了哪些单元格以及下一步要做什么(尤其是对于树高度可变的 PK 树)。

权衡解决方案(开发起来并不难，可能对您来说是合理的最佳选择)— 迭代搜索过程，您一直在树上进行搜索。你从包含 vX 的叶节点开始，如果它没有 N 个 vector ，或者如果 vX 更接近单元格的边界，那么找到第 N 个 vector ，你向上一级，并添加完整的子 -从父节点开始的树。这样算法就简单多了，因为搜索区域总是矩形的。然而，最坏的情况(即，如果 vX 位于 2 个根单元格之间的边界上)会更糟——您将不得不遍历所有 100k 个点。