所以我有大约 16,000 个 75 维数据点，对于每个点，我想找到它的 k 个最近邻居（使用欧几里德距离，如果这样更容易，目前 k=2）
我的第一个想法是为此使用 kd-tree，但事实证明，随着维度数量的增加，它们变得相当低效。在我的示例实现中，它只比穷举搜索稍微快一点。
我的下一个想法是使用 PCA（主成分分析）来减少维数，但我想知道：是否有一些聪明的算法或数据结构可以在合理的时间内准确地解决这个问题？
问问题
9116 次
6 回答
4
kd-trees 的 Wikipedia 文章有一个指向ANN 库的链接：
ANN 是一个用 C++ 编写的库，它支持在任意高维中进行精确和近似最近邻搜索的数据结构和算法。
根据我们自己的经验，ANN 对大小从数千到数十万以及 高达 20的点集执行得非常有效。（对于更高维度的应用程序，结果相当参差不齐，但无论如何你都可以尝试。）
就算法/数据结构而言：
该库基于 kd-trees 和box-decomposition trees实现了许多不同的数据结构，并采用了几种不同的搜索策略。
我会先直接尝试，如果这不能产生令人满意的结果，我会在应用 PCA/ICA 后将它与数据集一起使用（因为你不太可能最终得到足够少的维度用于 kd-tree处理）。
于 2010-10-18T21:30:35.953 回答
3
使用 kd 树
不幸的是，在高维中，这种数据结构受到维数灾难的严重影响，这导致其搜索时间与蛮力搜索相当。
减少维数
降维是一种很好的方法，它在准确性和速度之间提供了一个公平的权衡。当您减小尺寸时，您会丢失一些信息，但会获得一些速度。
准确度是指找到确切的最近邻（NN）。
当您想要减少数据所在的维度空间时，主成分分析 ( PCA ) 是一个好主意。
是否有一些巧妙的算法或数据结构可以在合理的时间内准确地解决这个问题？
近似最近邻搜索 ( ANNS )，您对找到一个可能不是确切最近邻的点感到满意，而是一个很好的近似值（即查询的第 4 个例如 NN，而您正在寻找第一神经网络）。
这种方法会降低您的准确性，但会显着提高性能。此外，找到好的 NN（足够接近查询）的概率相对较高。
您可以在我们的 kd-GeRaF论文的介绍中阅读更多关于 ANNS 的信息。
一个好主意是将 ANNS 与降维结合起来。
局部敏感散列 ( LSH ) 是一种解决高维最近邻问题的现代方法。关键思想是将彼此靠近的点散列到同一个桶中。因此，当查询到达时，它将被散列到一个桶中，该桶（通常是其相邻的桶）包含良好的 NN 候选者）。
FALCONN是一个很好的 C++ 实现，它专注于余弦相似度。另一个很好的实现是我们的DOLPHINN，它是一个更通用的库。
于 2017-09-03T07:25:31.820 回答
1
您可以想象使用Morton Codes，但如果有 75 个维度，它们将会非常庞大。如果您只有 16,000 个数据点，那么详尽的搜索应该不会花费太长时间。
于 2010-10-18T20:07:37.210 回答
1
没有理由相信这是 NP 完全的。您并没有真正优化任何东西，我很难弄清楚如何将其转换为另一个 NP 完全问题（我的书架上有Garey 和 Johnson，找不到类似的东西）。真的，我只是追求更有效的搜索和排序方法。如果您有 n 个观察值，则必须预先计算 nxn 距离。然后对于每个观察，您需要挑选出前 k 个最近的邻居。距离计算是 n 平方，排序是 n log (n)，但是您必须进行 n 次排序（对于 n 的每个值都不同）。凌乱的，但仍然是多项式时间来得到你的答案。
于 2010-10-18T21:20:39.447 回答
1
BK-Tree 并不是一个坏主意。看看尼克关于 Levenshtein Automata 的博客。虽然他的重点是弦乐，但它应该为您提供其他方法的跳板。我能想到的另一件事是R-Trees，但是我不知道它们是否已被推广到大尺寸。我不能说更多，因为我既没有直接使用它们，也没有自己实现它们。
于 2010-10-18T21:28:09.740 回答
0
一种非常常见的实现是对您为每个数据点计算的最近邻数组进行排序。由于对整个数组进行排序可能非常昂贵，您可以使用间接排序等方法，例如 Python Numpy 库中的 Numpy.argpartition 仅对您感兴趣的最接近的 K 值进行排序。无需对整个数组进行排序。
@Grembo 上面的回答应该大大减少。因为您只需要 K 个最接近的值。并且不需要对每个点的整个距离进行排序。
如果您只需要 K 个邻居，此方法将非常有效地降低您的计算成本和时间复杂度。
如果您需要排序的 K 个邻居，请再次对输出进行排序
看
于 2015-05-31T15:06:25.977 回答