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

Question

实际上，我正在处理高维数据(~50.000~100.000功能)，必须对其执行最近邻搜索。我知道KD树的性能随着维数的增长而下降，而且我也读过，一般来说，所有的空间分区数据结构都倾向于对高维数据执行详尽的搜索。

此外，还有两个重要的事实需要考虑(按相关性排列)：

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

所以，我需要一些建议：

1. 执行k-NN的数据结构。
2. 如果使用aNN (近似最近邻)方法更好，那么将其设置得尽可能准确吗？

Answer 1

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

No.由于维数的诅咒，数据结构在较低的维度上表现得很好，但在高维空间中却表现不佳。事实上，查询时间与蛮力查询时间几乎相等，因此它是毫无价值的。

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

执行ANN的数据结构是什么？

我建议LSH，或一些RKD树。在我的回答中，我提到了一些在C++中执行ANN的优秀库。然而，请注意，LSH解决了R-最近邻问题，因此您指定了参数R，实际上是半径。然后，LSH将从查询点查找R中的NN，因此不能真正请求k NN的NN。

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

我还觉得您应该阅读我的回答，它说最优的数据结构取决于数据。

Answer 2

我认为在这种高维数据中进行聚类是不明智的。存在维数问题的诅咒。

距离的概念随着维数的增加而变得不那么精确，因为给定数据集中的任意两个点之间的距离是收敛的。

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

本页列出了一些可能的解决方案，数据。

2.1子空间聚类 2.2预测聚类 2.3混合办法 2.4相关聚类