machine-learning - 如何划分数据集以降低 kNN 的时间复杂度？

Question

我使用 kNN 进行基于内容的图像检索。

数据集通常包含超过 1000 万张图像，每张图像都会转换为超过 300 维的向量。

数据量很大，加载到内存并查找 kNN 的速度很慢。

我想知道是否可以以某种方式将数据集分割成较小的数据集，并将较小的数据集分布在多个服务器之间。查询时，我只需要找出要查看的正确分区，然后只在该分区上执行 kNN。

Answer 1

一般来说，我认为你不能让普通的 kNN 比 O(n) 更快地工作(根据评论，这似乎是你所追求的)。

但是您可能想查看approximate nearest neighbor算法。它们允许更快的搜索和/或大大改善内存占用，但代价是一些预处理和非保证的全局最优(尽管通常性能是有限的)。

一些相关资源(不知道您使用什么语言):

• Spotify 的 ANNOY存储库有一个 C++ 实现(与许多语言绑定(bind))以及一些额外的比较和资源，例如完整的 performance comparison多个库之间
• This repository实现了 recent paper 中有趣的 EFINNA 算法.