获得最接近的 k 项的最有效实现
Most efficient implementation to get the closest k items
在 K 最近邻算法中，我们从 N 个观测值中找到最接近新点的前 k 个邻居，并使用这些邻居对点进行分类。根据我对数据结构的了解，我可以想到这个过程的两种实现方式：
方法一
- 从 N 个观测值中的每一个计算到新点的距离
- 使用快速排序对距离进行排序并取前 k 个点
这需要 O(N + NlogN) = O(NlogN) 时间。
方法二
- 创建一个大小为 k 的最大堆
- 计算前k个点到新点的距离
- 对于每个后续观察，如果距离小于堆中的最大值，则从堆中弹出该点并将其替换为当前观察
- 重新堆化（N个点的logk操作）
- 继续，直到没有更多的观测值，此时我们应该只有堆中的前 5 个最近距离。
这种方法需要 O(N + NlogK) = O(NlogK) 次操作。
我的分析正确吗？如何在像 sklearn 这样的标准包中优化这个过程？谢谢！
这里很好地概述了常用方法：https://en.wikipedia.org/wiki/Nearest_neighbor_search
您描述的是线性搜索（因为您需要计算到数据集中每个点的距离）。
好消息是这总是有效的。它的缺点是速度很慢，尤其是当你经常查询它时。
如果您对数据了解得更多一些，您可以获得更好的性能。如果数据具有低维度（2D、3D）并且均匀分布（这并不意味着完美，只是不是在非常密集和非常紧密的集群中），那么 space 分区效果很好，因为它可以快速减少点无论如何都太远了（复杂性 O(logN) ）。它们也适用于更高的维度或者如果有一些集群，但性能会受到一些影响（总体上仍然比线性搜索好）。
通常 space 分区或局部敏感散列对于常见数据集就足够了。
权衡是您使用更多内存和一些设置时间来加速未来的查询。如果您有很多疑问，那么这是值得的。如果你只有几个，不要那么多。
在 K 最近邻算法中，我们从 N 个观测值中找到最接近新点的前 k 个邻居，并使用这些邻居对点进行分类。根据我对数据结构的了解，我可以想到这个过程的两种实现方式：
方法一
- 从 N 个观测值中的每一个计算到新点的距离
- 使用快速排序对距离进行排序并取前 k 个点
这需要 O(N + NlogN) = O(NlogN) 时间。
方法二
- 创建一个大小为 k 的最大堆
- 计算前k个点到新点的距离
- 对于每个后续观察，如果距离小于堆中的最大值，则从堆中弹出该点并将其替换为当前观察
- 重新堆化（N个点的logk操作）
- 继续，直到没有更多的观测值，此时我们应该只有堆中的前 5 个最近距离。
这种方法需要 O(N + NlogK) = O(NlogK) 次操作。
我的分析正确吗？如何在像 sklearn 这样的标准包中优化这个过程？谢谢！
这里很好地概述了常用方法：https://en.wikipedia.org/wiki/Nearest_neighbor_search
您描述的是线性搜索（因为您需要计算到数据集中每个点的距离）。 好消息是这总是有效的。它的缺点是速度很慢，尤其是当你经常查询它时。
如果您对数据了解得更多一些，您可以获得更好的性能。如果数据具有低维度（2D、3D）并且均匀分布（这并不意味着完美，只是不是在非常密集和非常紧密的集群中），那么 space 分区效果很好，因为它可以快速减少点无论如何都太远了（复杂性 O(logN) ）。它们也适用于更高的维度或者如果有一些集群，但性能会受到一些影响（总体上仍然比线性搜索好）。
通常 space 分区或局部敏感散列对于常见数据集就足够了。
权衡是您使用更多内存和一些设置时间来加速未来的查询。如果您有很多疑问，那么这是值得的。如果你只有几个，不要那么多。