2D KD树和最近邻搜索

Question

我目前正在按照此处描述的算法实施 KD 树和最近邻搜索：http://ldots.org/kdtree/

我遇到过几种实现 KD 树的不同方法，一种是将点存储在内部节点中，另一种是仅将点存储在叶节点中。因为我有一个非常简单的用例（我需要做的就是构建一次树，不需要修改），我选择了 leaf-only 方法，它似乎更容易实现。我已经成功地实现了一切，树总是构建成功并且在大多数情况下最近的邻居搜索 returns 正确的值。但是，我有一些问题，对于某些数据集和搜索点，算法 returns 的值不正确。考虑要点：

[[6, 1], [5, 5], [9, 6], [3, 81], [4, 9], [4, 0], [7, 9], [2, 9], [6, 74]]

它构造了一棵看起来像这样的树（请原谅我糟糕的图表）：

其中方形叶节点是包含点的节点，圆形节点包含在该深度拆分列表的中值。当在这个数据集上调用我最近的邻居搜索，并寻找到 [6, 74] 的最近邻居时，算法 returns [7, 9]。虽然这正确地遵循了算法，但它实际上并不是最接近 [6, 74] 的点。最近的点实际上是 [3, 81]，距离为 7.6，[7, 9] 距离为 65。

这里是绘制的点，用于可视化，红点是我试图为其寻找最近邻居的点：

如果有帮助，我的搜索方法如下：

 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);
        }
    }

所以我的问题是：

这是 KD 树中最近邻搜索的预期结果，还是我应该得到离我正在搜索的点最近的点（因为这是我使用树的唯一原因)?
只有这种形式的KD树才有这个问题吗，我应该改成在内部节点存储点来解决这个问题吗？

Answer 1

KD 树的正确实现总能找到最近的点（点是否只存储在叶子中并不重要）。但是，您的搜索方法不正确。它应该是这样的：

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)

Answer 2

ldots.org 上给出的解释完全错误（连同许多其他 Google 搜索 KD 树的顶级结果）。

有关正确的实施，请参阅。

Answer 3

不确定这个答案是否仍然相关，但无论如何我敢于建议以下 kd-tree 实现：https://github.com/stanislav-antonov/kdtree

该实现非常简单，如果您决定弄清楚这些东西在实践中是如何工作的，那么它可能会很有用。

关于树的构建方式，使用了迭代方法，因此其大小受内存限制，而不是堆栈大小。

2D KD树和最近邻搜索

2D KD Tree and Nearest Neighbour Search

java

algorithm

search

kdtree

nearest-neighbor