在KD树中寻找所有节点的K近邻的高效方法

Question

我目前正在尝试找到一个平衡的KD树的所有节点的K个最近邻居（其中K=2）。我的实现是代码维基百科文章的变体，可以相当快地找到任何节点的KNN，时间复杂度为O(log N)。问题在于我需要找到每个节点的KNN，如果我迭代每个节点并执行搜索，则时间复杂度达到O(N log N)左右。是否有更有效的方法来解决这个问题？

- St. John Johnson

---

您想将结果存储在某个列表中还是遍历元组（t，knn1，knn2）？ - Thomas Jung

只是迭代。虽然我很好奇，采用不同的方法会有什么区别？ - St. John Johnson

KNN搜索和您的搜索之间的主要区别在于，所有您的搜索值已经在树中。因此，您的搜索从不是根节点的节点开始。从每个节点开始，您可以遍历树，找到2个候选项，并遍历直到没有更近的候选项为止。这可能会节省一些节点遍历，但如果树是平衡的，则仍为O（n log n）。也许有一种重用计算的方法（这仍然是O（n log n））。 - Thomas Jung

Answer 1

根据您的需求，您可能希望尝试近似技术。有关详细信息，请查看Arya and Mount在该主题上的工作。一篇关键论文在这里。BigO复杂度的详细信息位于他们的'98年论文中。

下面显示了该工作的图形说明：

^{来源: http://www.cs.umd.edu/~mount/ANN/Images/annspeckle.gif}

我在具有数十万个元素的高维数据集上使用过他们的库。它比我找到的任何其他东西都要快。该库处理精确和近似搜索。该软件包包含一些CLI实用程序，您可以使用它们轻松地对数据集进行实验；甚至可视化kd树（见上文）。

FWIW：我使用了R绑定。

来自ANN手册：

"... Arya和Mount [AM93b]以及Arya等人[AMN+98]已经证明，如果用户愿意容忍搜索中出现的一些误差（返回的点可能不是最近邻，但与真实的最近邻相比没有显着差异），则可以在运行时间上获得显著的改进。 ANN是一个系统，既可以精确地回答最近邻查询，也可以近似地回答最近邻查询。"

- Ryan Cox

---

哇，感谢你的研究，Ryan。不幸的是，我正在寻找准确的结果。如果使用KD-Tree的KNN在这个速度上受到限制，也许我使用了错误的数据结构进行搜索。有什么其他的建议吗？ - St. John Johnson

正如他们手册中引用的最后一句话所指出的那样，使用这个库你可以进行精确搜索。"ANN是一个用于精确和近似回答最近邻查询的系统"。 - Ryan Cox

近似搜索有时很有帮助。首先尝试搜索可能的路径，并使用了解超平面和路径上点的距离计算。如果最终点不接近任何超平面，则通常是最近的邻居。 - Asher

Answer 2

我使用了Cover Tree来解决这个问题。这是链接：http://hunch.net/~jl/projects/cover_tree/cover_tree.html 在一个大小为50M的数据集中（所有kNN查询，k=100），创建Cover Tree花费了5.5秒，查询花费了120秒。Ann lib创建树需要3.3秒，查询需要138秒。

更新：最近邻不是对称关系。考虑以下情况：A(0,0) B(1,0) C(3,0)。B是C的最近邻，而C不是B的最近邻。

- Kanglai

---

所有数据都需要适合内存还是只有树需要？ - mrgloom

Answer 3

如果节点本身是查询点，则搜索时间可能会更短。您可以从回溯阶段开始，测试的第一个节点已经接近查询点。然后，树的大部分区域很快就可以被修剪。

最近邻是对称关系（如果n1是n2的最近邻居，则同样适用于n2），因此您只需要搜索一半的节点，跳过所有已标记为最近邻居的节点。这只是一个想法。

您还可以尝试KD-Tree BBF（最佳二叉树）搜索，这将帮助您更快地搜索最近节点（bin）。我已经在C#中实现了这一点，所以如果您有兴趣获取源代码，请写信给我。

当然，实际运行时间取决于数据集中的维数、KD-Tree结构和点的分布。

点的聚类也可能是合适的。

- Libor

Answer 4

要搜索的术语是knn join。更准确地说，您可能想要进行自连接。

也许这些搜索结果可以帮助您：

• http://scholar.google.com/scholar?q=k-d-tree+knn+join

我只看到过用于R*树的knn连接算法。然而，在我的实验中，它们未能超越重复查询。我可能错过了一些实现思路。但总的来说，为树连接适当地保存数据比单个knn查询要棘手得多。

- Has QUIT--Anony-Mousse