algorithm - 获得最接近的 k 项的最有效实现

Question

在 K 最近邻算法中，我们从 N 个观测值中找到最接近新点的前 k 个邻居，并使用这些邻居对点进行分类。根据我对数据结构的了解，我可以想到这个过程的两种实现方式:

方法一

1. 从 N 个观测值中的每一个计算到新点的距离
2. 使用快速排序对距离进行排序并取前 k 个点

这需要 O(N + NlogN) = O(NlogN) 时间。

方法二

1. 创建一个大小为k的最大堆
2. 计算前k个点到新点的距离
3. 对于每个后续观察，如果距离小于堆中的最大值，则从堆中弹出该点并将其替换为当前观察
4. 再堆化(N个点的logk操作)
5. 继续，直到没有更多的观测值，此时我们应该只有堆中的前 5 个最近距离。

这种方法需要 O(N + NlogK) = O(NlogK) 操作。

我的分析是否正确？如何在像 sklearn 这样的标准包中优化这个过程？谢谢你!

Answer 1

以下是对常用方法的一个很好的概述:https://en.wikipedia.org/wiki/Nearest_neighbor_search

您描述的是线性搜索(因为您需要计算到数据集中每个点的距离)。好消息是这总是有效的。它的缺点是速度很慢，尤其是当您经常查询时。

如果您对自己的数据了解得更多一点，您可以获得更好的性能。如果数据具有低维度(2D、3D)并且均匀分布(这并不意味着完美，只是不是在非常密集和非常紧密的集群中)，那么空间分区会很好用，因为它可以快速减少太远的点无论如何(复杂度 O(logN) )。它们也适用于更高的维度或者如果有一些集群，但性能会受到一些影响(总体上仍然比线性搜索好)。

通常空间分区或局部敏感散列对于常见数据集就足够了。

权衡是您使用更多内存和一些设置时间来加速 future 的查询。如果您有很多疑问，那么这是值得的。如果您只有几个，则不会太多。