algorithm - 如何在高维数据中高效寻找k近邻？

Question

所以我有大约 16,000 个 75 维数据点，对于每个点我想找到它的 k 个最近邻居(使用欧氏距离，如果这样更容易，目前 k=2)

我的第一个想法是为此使用 kd 树，但事实证明，随着维数的增加，它们变得相当低效。在我的示例实现中，它只比穷举搜索快一点。

我的下一个想法是使用 PCA(主成分分析)来减少维数，但我想知道:是否有一些聪明的算法或数据结构可以在合理的时间内准确地解决这个问题？

Answer 1

关于 kd-trees 的维基百科文章有一个链接到 ANN library :

ANN is a library written in C++, whichsupports data structures andalgorithms for both exact andapproximate nearest neighbor searchingin arbitrarily high dimensions.

Based on our own experience, ANNperforms quite efficiently for pointsets ranging in size from thousands tohundreds of thousands, and indimensions as high as 20. (For applications in significantly higherdimensions, the results are ratherspotty, but you might try it anyway.)

就算法/数据结构而言:

The library implements a number ofdifferent data structures, based onkd-trees and box-decomposition trees,and employs a couple of differentsearch strategies.

我会先直接尝试，如果不能产生令人满意的结果，我会在应用 PCA/ICA 后将其与数据集一起使用(因为你不太可能最终得到足够少的维度来满足 kd - 要处理的树)。