algorithm - 移动查询点的 K 最近邻

Question

我得到了 n 个固定点和 m 个查询点的坐标。我必须从 n 个固定点中找到 m 个查询点中每个查询点的 k 最近邻。为每个查询点单独查找距离是非常昂贵的。有没有一种有效的方法来做到这一点？

Answer 1

您的问题的真正答案取决于许多因素。例如，如果您不使用欧几里德距离 - 那么您就不能使用 KDTrees。还有缩放问题（注册了多少点？维度大小？“集群”）您可以等待多长时间的训练，如果需要将值添加到集合中，等等。

JSAT中提供了一些不太常见但仍然有用的算法。这包括VP 树、RBC和LSH。（偏见警告，我是JSAT的作者）

Answer 2

有针对此类问题的快速索引结构，例如KD Tree或Ball Tree。特别是 - scikit-learn (sklearn) 在他们的 knn 例程中实现它们 ( http://scikit-learn.org/stable/modules/neighbors.html )

Answer 3

如果您正在计算平方和的平方根以获得距离，请尝试删除计算密集型的平方根。只需找到平方距离最近的那些 - 它们是相同的点。