如何有效地从kd树中找到k个最近的邻居 [英] How to efficiently find k nearest neighbours from a kd tree

问题描述

实际上，这个问题是之前提出的，但据我所知，没有提供适当的答案。

Actually the question has been asked before but to the best of my knowledge no appropriate answers have been provided.

我了解如何实现k-d树以及最近的邻居搜索它的工作方式。但是，即使环顾四周，我也找不到使用k-d树非常有效地搜索k个最近邻居的有效方法。我只能想到找到最近的邻居并将其删除，然后再次重复该过程k-1次，然后将所有已删除的节点重新插入树中。但这似乎是多余的，完全超出了目的。

I understand how to implement k-d tree and how the nearest neighbor search for it works. However even after looking around, I can't find an efficient way to search for k nearest neighbors very efficiently using k-d tree. I can only think of finding the nearest neighbor and deleting it and repeating the process again k-1 times and then inserting all the deleted nodes back into the tree. But that seems redundant and totally beats the purpose.

我只想找到一种简单的方法，使用k-d树找到k个最近的邻居。我不是在寻找可以让我这样做的在线实现或库。我只想了解逻辑，然后自己实现。

I just want to find a simple way to find the k nearest neighbors using k-d tree. I am not looking for an online implementation or a library which could let me do that. I just want to understand the logic and then I will implement it myself.

推荐答案

https://en.wikipedia.org/wiki/K-d_tree#Nearest_neighbour_search 可以看作是对以递归方式搜索整棵树，最优化的方法是找出您要搜索的子树不可能包含当前最佳邻居的改进情况。

The algorithm at https://en.wikipedia.org/wiki/K-d_tree#Nearest_neighbour_search can be regarded as an optimisation of "search the whole tree recursively" and the optimisation is to work out when the subtree you are about to search cannot possibly contain an improvement on the current best neighbour.

要更改这样可以找到k个最近的邻居，保持k个节点到目前为止，而不只是一个最近的节点，并跟踪到这些节点中最远的节点的距离。然后根据该子树中最接近的点是否可能是对这k个邻居中最远的一个的改进来决定搜索子树，还是忽略它。

To change this to find the k nearest neighbours, keep k nodes found so far instead of just one closest node, and keep track of the distance to the furthest of these nodes. Then decide to search a subtree, or ignore it, based on whether the closest point within that subtree can possibly be an improvement on the furthest one of these k neighbours.

您将需要一个数据结构，例如堆，该数据结构可让您保留k个项目，找到距离值最高的项目，删除该项目，然后插入新找到的项目。

You will want a data-structure, such as a heap, which allows you to keep k items, find the item with the highest value of distance, remove that item, and insert a newly found item.

这篇关于如何有效地从kd树中找到k个最近的邻居的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！