Ben*_*nno 16 algorithm nearest-neighbor computational-geometry data-structures dimensionality-reduction
所以我有大约16,000个75维数据点,并且对于每个点我想找到它的k个最近邻居(使用欧氏距离,如果这使得它更容易,则当前k = 2)
我的第一个想法是为此使用kd树,但事实证明,随着维数的增长,它们变得相当低效.在我的示例实现中,它仅比详尽的搜索稍快.
我的下一个想法是使用PCA(主成分分析)来减少维数,但我想知道:是否有一些聪明的算法或数据结构可以在合理的时间内完全解决这个问题？
kd-trees 的 Wikipedia 文章有ANN 库的链接：
ANN 是一个用 C++ 编写的库，它支持任意高维度的精确和近似最近邻搜索的数据结构和算法。
根据我们自己的经验，ANN 对于大小从数千到数十万、维度 高达 20 的点集表现相当有效。（对于维度明显更高的应用程序，结果相当参差不齐，但您无论如何都可以尝试一下。）
就算法/数据结构而言：
该库基于 kd 树和框分解树实现了许多不同的数据结构，并采用了几种不同的搜索策略。
我会首先直接尝试它，如果这不能产生令人满意的结果，我会在应用 PCA/ICA 后将它与数据集一起使用（因为你不太可能最终得到足够少的维度来让 kd 树处理）。