高维最近邻搜索的最佳数据结构

Question

我正在处理高维数据（约50.000-100.000个特征），需要对其进行最近邻搜索。我知道随着维度的增加，KD树的性能会变差，并且我也读到过通常所有空间划分数据结构在高维数据上执行穷举搜索。

此外，有两个重要因素需要考虑（按相关性排序）：

• 精度：必须找到最近的邻居（而不是近似值）。
• 速度：搜索必须尽可能快。（创建数据结构所需的时间并不重要）。

因此，我需要一些建议：

1. 执行k-NN的数据结构。
2. 是否更好地使用aNN（近似最近邻）方法，并尽可能准确地设置它？

- mavillan

Answer 1

我能在高维空间中执行NN搜索吗？

不行。由于维度的诅咒，那些在低维度表现良好的数据结构，在高维空间中无法很好地执行最近邻搜索。事实上，查询时间几乎相当于暴力计算，因此毫无价值。

因此，在高维空间中，应该选择近似最近邻(ANN)搜索。老实说，这是必须的。

哪种数据结构可以执行ANN?

我建议使用LSH或一些RKD树。在我的答案中，我提到了一些在C++中执行ANN的好库。然而，请注意，LSH解决了R最近邻问题，因此您需要指定参数R，即半径。然后，LSH将在查询点内查找R之内的NN，因此您无法真正请求k个NN。

另一方面，RKD树可以做到并返回k个NN。我有一个项目，它在C++中构建了一个RKD树的森林，并执行ANN搜索，但它只针对高维度。它可以处理960维度下的10^6个图像的GIST数据集，并在<1秒内处理，其中约90%的输出是真实最近邻。它的名字是kd-GeRaF。它将在下个月更新为分布式版本，但已经经过测试并可以使用。它还有一个可爱的徽标。:)

我也觉得您应该阅读我的答案，其中说最优数据结构取决于数据。

- gsamaras

---

每次插入后都必须重新构建树吗？这就是我现在想要避免的kd-tree问题。谢谢。 - EyeQ Tech

请注意如何插入数据，因为它可能会使树失衡（假设它已经平衡）。在Wikipedia中了解更多信息。 - gsamaras

Answer 2

我认为在这样高维度的数据中进行聚类并不明智。存在维数灾难问题。

随着维度数量的增加，距离概念变得不太精确，因为给定数据集中任意两点之间的距离会趋于收敛。

我建议您找到一个好的距离度量方法，而不是直接在高维空间上使用欧几里得距离。

此页面列出了一些可能的解决方案， https://en.wikipedia.org/wiki/Clustering_high-dimensional_data

2.1 子空间聚类

2.2 投影聚类

2.3 混合方法

2.4 相关聚类

- William

---

我不在做聚类，也不想做聚类。我正在实现一个对象识别系统，每个类别只有一个样本。因此，对于这种情况，最好的方法是最近邻搜索。 - mavillan

我认为你正在寻找的是一次性学习（one-shot learning），https://en.wikipedia.org/wiki/One-shot_learning。你也可以使用深度学习算法来降低维度。 - William