我有大量的向量（〜100k）（代表单词并使用随机索引进行计算），并且必须找到给定的1个输入单词，前N个最接近的向量。我现在这样做的方法是按距离进行完整排序，然后提取前N个结果，但这需要太多时间才能使用，因为我必须计算100k距离。有更有效的方法吗？向量已经归一化，因此在计算距离时我只需要计算点积。
向量存储在Java中HashMap<String, Vector>，其中Vector是稀疏向量的la4j类。
您可以将向量放入可感知空间的容器中，例如R树或kd树或PK树。
这样，您仅通过查看几个相邻的像元就可以找到点，而无需遍历所有数据集。别忘了，您不仅需要在单个单元格中搜索，而且还需要在相邻的单元格中搜索，并且在多维空间中，有很多邻居。
更新：您仍然需要手动测量距离。但是，您将不需要遍历所有向量。
一个简单的解决方案-定义最大距离，迭代该距离内的像元内的所有向量，排序并选择前N个。
最佳解决方案（很难开发）–迭代搜索过程。例如，从输入向量vX所在的单个单元格开始，在该单元格中找到N个最近的向量。如果vX与找到的第N个矢量之间的距离（最远的一个）小于vX与尚未搜索的任何单元格的最近点之间的距离，则得到N个结果。否则，从尚未搜索的最近单元中添加向量，然后重复该过程。这里最复杂的事情-跟踪已经搜索了哪些单元格以及下一步要做什么（尤其是PK树的高度可变的情况下）。
权衡解决方案（不是很难开发的，可能对您来说是最佳的）–迭代搜索过程，使您始终无所不用其极。您可以从包含vX的叶节点开始，如果它没有N个向量，或者如果vX距离单元的边界更近，则第n个找到的向量，则向上一层，然后添加完整的子节点，从父节点开始的树。这样，由于搜索区域始终为矩形，因此算法简单得多。但是，最坏的情况（即，如果vX位于2个根单元之间的边界上）会更糟-您必须遍历所有100k点。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句