二维KD树和最近邻搜索 [英] 2D KD Tree and Nearest Neighbour Search
问题描述
我目前正在实施一个KD树和近邻搜索，下面在这里描述的算法：的http：// ldots。组织/ kdtree /
我所遇到的几个不同的方式来实现的K D树，在其中点存储在内部节点，和一个在它们只存储在叶节点。因为我有一个非常简单的用例（我需要做的就是构建树一次，它并不需要修改），我去叶，唯一的办法就是它似乎是容易实现。我已经成功实现的事情，树永远构建成功，而且在大多数情况下，最近邻搜索将返回正确的值。不过，我有一些问题，一些数据集和搜索点，该算法返回不正确的值。考虑要点：
的 [[6,1]，[5,5]，[9,6]，[3，81]，[4,9]，[4,0]，[ 7，9]，[2,9]，[6，74]]
它构造一棵树看起来像这样（请原谅我的坏图表）：
凡平方叶节点是那些包含点，并且圆形节点包含用于分离列表中在该深度的中值。当调用这个数据集我最近邻搜索和寻找最近的邻居 [6，74] ，该算法返回 [7,9 ] 。虽然此正确地遵循的算法，它不是实际上的最近点到 [6，74] 。最近点实际上是 [3，81] 这是在7.6的距离， [7,9] 是在65的距离。
下面的点绘制，可视化，红点是一个我试图找到最近的邻居：
如果有帮助，我的搜索方法如下：
私人叶节点搜索（INT深度，点对点，KDNode节点）{
如果（节点的instanceof叶节点）
返回（叶节点）节点;
其他 {
MedianNode medianNode =（MedianNode）节点;
双meanValue = medianNode.getValue（）;
双comparisonValue = 0;
如果（valueEven（深度））{
comparisonValue = point.getX（）;
}
其他 {
comparisonValue = point.getY（）;
}
KDNode nextNode;
如果（comparisonValue＆LT; meanValue）{
如果（node.getLeft（）！= NULL）
nextNode = node.getLeft（）;
其他
nextNode = node.getRight（）;
}
其他 {
如果（node.getRight（）！= NULL）
nextNode = node.getRight（）;
其他
nextNode = node.getLeft（）;
}
返回搜索（深度+ 1，点，nextNode）;
}
}
所以，我的问题是：
-
这是从一个KD树的最近邻搜索会发生什么，或者我应该得到的最近点到一点上，我寻找（因为这是我使用树唯一原因）？
-
这是只有这种形式的KD树的问题，我应该改变它来存储点内的节点来解决这个问题？
一个正确实施KD-树总能找到的最近点（这并不重要，如果点存储在只剩与否）。你的搜索方法是不正确的，虽然。下面是它应该是什么样子：
bestDistance = INF
高清getClosest（节点，点）
如果节点为null
返回
//我假设这个节点分割点
//通过x坐标为了简洁。
如果节点是叶
// updateAnswer更新bestDistance值
//和跟踪的最近点到给定的一个的。
updateAnswer（node.point，点）
其他
middleX = node.median
如果point.x＆LT; middleX
getClosest（node.left，点）
如果node.right.minX - point.x＆LT; bestDistance
getClosest（node.right，点）
其他
getClosest（node.right，点）
如果point.x - node.left.maxX＆LT; bestDistance
getClosest（node.left，点）
I'm currently implementing a KD Tree and nearest neighbour search, following the algorithm described here: http://ldots.org/kdtree/
I have come across a couple of different ways to implement a KD Tree, one in which points are stored in internal nodes, and one in which they are only stored in leaf nodes. As I have a very simple use case (all I need to do is construct the tree once, it does not need to be modified), I went for the leaf-only approach is it seemed to be simpler to implement. I have successfully implemented everything, the tree is always constructed successfully and in most cases the nearest neighbour search returns the correct value. However, I have some issues that with some data sets and search points, the algorithm returns an incorrect value. Consider the points:
[[6, 1], [5, 5], [9, 6], [3, 81], [4, 9], [4, 0], [7, 9], [2, 9], [6, 74]]
Which constructs a tree looking something like this (excuse my bad diagramming):
Where the square leaf nodes are those that contain the points, and the circular nodes contain the median value for splitting the list at that depth. When calling my nearest neighbour search on this data set, and looking for the nearest neighbour to [6, 74], the algorithm returns [7, 9]. Although this follows the algorithm correctly, it is not in fact the closest point to [6, 74]. The closest point would actually be [3, 81] which is at a distance of 7.6, [7, 9] is at a distance of 65.
Here are the points plotted, for visualization, the red point being the one I am attempting to find the nearest neighbour for:
If it helps, my search method is as follows:
private LeafNode search(int depth, Point point, KDNode node) {
if(node instanceof LeafNode)
return (LeafNode)node;
else {
MedianNode medianNode = (MedianNode) node;
double meanValue = medianNode.getValue();
double comparisonValue = 0;
if(valueEven(depth)) {
comparisonValue = point.getX();
}
else {
comparisonValue = point.getY();
}
KDNode nextNode;
if(comparisonValue < meanValue) {
if (node.getLeft() != null)
nextNode = node.getLeft();
else
nextNode = node.getRight();
}
else {
if (node.getRight() != null)
nextNode = node.getRight();
else
nextNode = node.getLeft();
}
return search(depth + 1, point, nextNode);
}
}
So my questions are:
Is this what to expect from nearest neighbour search in a KD Tree, or should I be getting the closest point to the point I am searching for (as this is my only reason for using the tree)?
Is this an issue only with this form of KD Tree, should I change it to store points in inner nodes to solve this?
A correct implementation of a KD-tree always finds the closest point(it doesn't matter if points are stored in leaves only or not). Your search method is not correct, though. Here is how it should look like:
bestDistance = INF
def getClosest(node, point)
if node is null
return
// I will assume that this node splits points
// by their x coordinate for the sake of brevity.
if node is a leaf
// updateAnswer updates bestDistance value
// and keeps track of the closest point to the given one.
updateAnswer(node.point, point)
else
middleX = node.median
if point.x < middleX
getClosest(node.left, point)
if node.right.minX - point.x < bestDistance
getClosest(node.right, point)
else
getClosest(node.right, point)
if point.x - node.left.maxX < bestDistance
getClosest(node.left, point)
这篇关于二维KD树和最近邻搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
