2D KD树和最近邻搜索

Question

我正在实现一个KD树和最近邻搜索，遵循这里描述的算法：http://ldots.org/kdtree/

我已经找到了几种不同的KD树实现方法，一种是将点存储在内部节点中，另一种则仅将其存储在叶节点中。由于我的用例非常简单（我只需要构建一次树，不需要修改它），因此我选择了仅存储在叶节点中的方法，因为它似乎更容易实现。我已经成功地实现了所有内容，树总是成功地构建，而且在大多数情况下，最近邻搜索返回正确的值。然而，在某些数据集和搜索点中，该算法会返回不正确的值。请考虑以下点：

[[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。

以下是绘制出的数据点，红点是我正在尝试找到最近邻点的点：

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

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

我的问题如下：

1. 在KD树中，最近邻搜索是这样的吗？或者我应该得到距离我搜索点最近的点（因为这是我使用树的唯一原因）？

2. 这个问题只存在于这种形式的KD树中吗？我应该将其更改为在内部节点中存储点来解决此问题吗？

- FinalFanatic

Answer 1

ldots.org给出的解释是完全错误的（以及在搜索KD树时其他许多顶级Google结果）。

请查看https://dev59.com/nXI-5IYBdhLWcg3w48xP#37107030以获取正确实现。

- Scott Smedley

Answer 2

正确的KD-tree实现总是能够找到最近的点（无论是否仅在叶子节点存储点）。然而，您的搜索方法不正确。下面是正确的方法：

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)

- kraskevich

---

啊，我明白了！谢谢，看来我问题中链接的文章中的伪代码有点误导人。它没有考虑到神经网络可能在最初递归进入的子树中不存在，需要在向上递归时检查其他子树。 - FinalFanatic

Answer 3

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

该实现足够简单，并且在需要弄清楚实际工作原理的情况下非常有用。

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

- Stanislav Antonov