我实际上正在处理高维数据（~50.000-100.000 个特征），并且必须对其执行最近邻搜索。我知道随着维度的增长，KD 树的性能很差，而且我还了解到，一般来说，所有空间分区数据结构都倾向于对高维数据执行详尽的搜索。
此外，还有两个重要事实需要考虑（按相关性排序）：
-
精确：必须找到最近的邻居（不是近似值）。
-
Speed:搜索必须尽可能快。 （创建数据结构的时间并不重要）。
所以，我需要一些建议：
- 执行 k-NN 的数据结构。
- 如果使用 aNN（近似最近邻）方法会更好，请将其设置得尽可能准确？
我可以在高维空间中进行神经网络搜索吗？
No.由于维数灾难，在较低维度中执行最近邻搜索的数据结构在高维度中表现不佳。事实上，查询时间几乎与暴力破解相同，因此毫无价值。
因此，在高维空间中，人们应该追求近似最近邻（安）搜索。说实话，这是一个must.
哪个数据结构来执行 ANN？
我建议使用 LSH，或者一些 RKD 树。在我的answer https://stackoverflow.com/questions/26641937/two-sets-of-high-dimensional-points-find-the-nearest-neighbour-in-the-other-set/26664557#26664557在这里，我提到了一些在 C++ 中执行 ANN 的优秀库。但是，请注意，LSH 解决了 R 最近邻问题，因此您指定参数 R，它实际上是半径。然后，LSH将从查询点寻找R内部的NN，因此你不能真正请求k NN's.
另一方面，RKD 树可以做到这一点并返回给你kNN的。我有一个项目，它构建了 RKD 树森林并用 C++ 执行 ANN 搜索，但它仅针对高维度。它可以在 1 秒内处理 960 维 10^6 图像的 GIST 数据集，大约 90% 的输出是真正的最近邻。名字是kd-GeRaF https://gsamaras.wordpress.com/projects/#geraf。它将在下个月更新为分布式版本，但它已经经过测试并可以使用。它还有一个可爱的标志。 :)
我也觉得你应该阅读我的answer https://stackoverflow.com/a/26266337/2411320，这表示最佳数据结构取决于数据。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
