我有大约16,000个75维数据点，对于每个点，我想找到它的k个最近邻居（使用欧几里得距离，目前k=2以使问题简化）。
我的第一个想法是使用kd树实现，但是随着维数增长，它们变得相当低效。在我的示例实现中，它只比穷举搜索略快一些。
我的下一个想法是使用PCA（主成分分析）来减少维数，但我想知道：是否有聪明的算法或数据结构可以在合理的时间内精确解决这个问题？
如何高效地在高维数据中找到k个最近邻居？
21
- Benno
6
我认为这与以下其中一个相似：http://www.facebook.com/careers/puzzles.php - Joni
1就精确解而言，我怀疑答案是否定的，但我想建议使用随机投影和约翰逊-林登斯特劳斯定理可能会有所帮助。 - piccolbo
+1 对于之前的评论表示赞同，该评论与局部敏感哈希和人工神经网络的思路相似。 - Steve Tjoa
1我推荐阅读Hanan Samet的《多维度和度量数据结构基础》一书。它有一些专门介绍适用于高维数据的章节。 - comingstorm
我的库实际上有这个，所以我一定会看一下。大多数答案似乎都需要阅读很多内容，所以我猜可能需要一些时间才能接受其中一个 :) - Benno
1我已经删除了我的回答，因为思考后我意识到它既具有误导性又是不正确的。 - Jonathan
6个回答
4
- Eugen Constantin Dinca
5
2+1 对于 ANN 来说，是最近信息检索领域中非常热门的话题。搜索 Lowe 的一个实现 "FLANN" 和 David Mount 的 "ANN"。同时搜索相关的 "局部敏感哈希"。 - Steve Tjoa
@Steve：谢谢你分享FLANN和局部敏感哈希技巧，非常有趣的内容！ - Eugen Constantin Dinca
这就是我最终使用的，而且（加上用C++重写程序）它非常快（<1秒）。 - Benno
@Benno：很高兴它对你有用。作为一件好奇心的事情，你将其应用在原始数据上（75个维度）还是在进行PCA / ICA后得到的数据上？ - Eugen Constantin Dinca
我确实应用了PCA，但只是为了改变基向量，而不是为了降低维度。然而，它也有其局限性，对于另一个包含240,000个数据点的数据集，需要大约15分钟的时间。 - Benno
3
使用kd-tree
不幸的是，在高维度下，这种数据结构受到维数灾难的严重影响，导致其搜索时间与暴力搜索相当。
减少维数
降维 是一个不错的方法，它在准确性和速度之间提供了公平的权衡。当您减少维数时，会失去一些信息，但会获得一些速度。
准确性指的是找到精确的最近邻（NN）。
当您想要减少数据所在的维度空间时，主成分分析（PCA）是一个不错的选择。
近似最近邻搜索（ANNS）是一种方法，您可以通过查找可能不是精确最近邻，而是它的良好近似值（例如，对于您正在寻找第一个NN，其为第四个NN）来满足自己。有没有一些聪明的算法或数据结构可以在合理的时间内完全解决这个问题？
这种方法会牺牲准确性，但显著提高性能。此外，找到良好的NN（接近查询）的概率相对较高。
您可以在我们的kd-GeRaF paper中介绍更多关于ANNS的内容。
将ANNS与降维结合起来是一个好主意。
局部敏感哈希（LSH）是解决高维最近邻问题的现代方法。其关键思想是将彼此靠近的点哈希到同一个桶中。因此，当查询到达时，它将被哈希到一个桶中，该桶（通常还有其相邻的桶）包含良好的NN候选项。
FALCONN 是一个很好的 C++ 实现，专注于余弦相似度。另一个很好的实现是我们的 DOLPHINN，它是一个更通用的库。
- gsamaras
1
你可以考虑使用Morton Codes，但是在75个维度下它们会非常庞大。如果你只有16000个数据点，穷举搜索不应该花费太长时间。
- Anon
2
这对于每个点来说是16000次比较，因此总共有16000^2次比较。虽然不会花费永远的时间，但至少需要数小时到数天的时间。我会研究一下莫顿码。 - Benno
@Benno：啊，我以为你是在寻找最近的邻居来到达点。如果你想按地区排序，那么莫顿码可能是最好的选择，无论大小如何。你应该搜索Z-order曲线，因为它有一些奇怪的地方。你可能还想看看维基百科上关于GeoHash的文章，它本质上是莫顿码的文本翻译。（最后，请注意，所描述的莫顿码是用于2维的，但你可以交错任意数量的维度） - Anon
1
没有理由认为这是NP完全问题。你并没有真正优化任何东西，我很难想象如何将其转换为另一个NP完全问题（我书架上有Garey and Johnson，但找不到类似的内容）。实际上，我会追求更有效的搜索和排序方法。如果你有n个观测值，你必须先计算n x n的距离。然后对于每个观测值，你需要挑选出前k个最近的邻居。这是n平方的距离计算，n log (n)的排序，但你必须对每个n值进行n次排序（每个n值都不同）。虽然有些混乱，但仍然可以在多项式时间内得到答案。
- Grembo
1
BK-Tree 不是一个坏的想法。看一下Nick's Blog on Levenshtein Automata。虽然他的重点是字符串，但它应该为其他方法提供了一个跳板。我能想到的另一件事是R-Trees，但我不知道它们是否已经被推广到大维度。我不能再多说了，因为我既没有直接使用过它们，也没有自己实现过它们。
- wheaties
0
一个非常常见的实现方法是对计算出的每个数据点的最近邻数组进行排序。 由于对整个数组进行排序可能非常昂贵，因此可以使用间接排序的方法，例如Python Numpy库中的Numpy.argpartition，只对您感兴趣的最接近的K个值进行排序。无需对整个数组进行排序。
上面@Grembo的答案应该大幅减少，因为您只需要K个最近的值，并且没有必要对每个点之间的距离进行排序。
如果您只需要K个邻居，这种方法将非常有效地降低计算成本和时间复杂度。
如果您需要排序后的K个邻居，请再次对输出进行排序。
请参阅
- Irtaza
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接