最近邻居 - k-d树 - 维基百科证明-Java 学习之路

在wikipedia entry for k-d trees上，提出了一种用于在k-d树上进行最近邻搜索的算法 . 我只是因为搜索点的分割坐标与当前节点之间的差异大于搜索点的分割坐标与当前最佳分割之间的差异，所以我更接近于什么？

最近邻搜索在2D中使用KD树进行NN搜索的动画最近邻居（NN）算法旨在找到树中最接近给定输入点的点 . 通过使用树属性快速消除搜索空间的大部分，可以有效地完成此搜索 . 在kd树中搜索最近邻居的过程如下：从根节点开始，算法以递归方式向下移动树，其方式与插入搜索点时相同（即，它向右或向左移动）关于该点是大于还是小于拆分维度中的当前节点 . 一旦算法到达叶节点，它就将该节点保存为“当前最佳”算法解除树的递归，在每个节点执行以下步骤：1 . 如果当前节点比当前节点更接近，则它成为当前最好的 . 2.该算法检查在分裂平面的另一侧是否可能存在比当前最佳点更接近搜索点的任何点 . 在概念上，这通过使分裂超平面与搜索点周围的超球面相交来完成，该超球面具有等于当前最近距离的半径 . 由于超平面都是轴对齐的，因此将其实现为简单的比较，以查看搜索点的分割坐标与当前节点之间的差异是否小于从搜索点到当前最佳的距离（总坐标） . 1.如果超球面穿过平面，则在平面的另一侧可能存在更近的点，因此算法必须从当前节点向下移动树的另一个分支，寻找更近的点，遵循与之相同的递归过程 . 整个搜索 . 2.如果超球面不与分裂平面相交，则算法继续向上走树，并且消除该节点另一侧的整个分支 . 当算法完成根节点的此过程时，搜索完成 . 通常，算法使用平方距离进行比较以避免计算平方根 . 另外，它可以通过在变量中保持平方电流最佳距离来进行比较来节省计算 .

2 回答

1

仔细看看animation on that page的第6帧 .

随着算法回溯递归，有可能超平面的另一侧有一个更近的点，它正在进行 . 我们检查了一半，但另一半可能会有更接近的点 .

好吧，事实证明我们有时可以进行简化 . 如果在另一半上的点不可能比我们当前的最佳（最近）点更接近，那么我们可以完全跳过该超平面 . 这种简化是第6帧所示的简化 .

通过比较超平面到我们的搜索位置的距离来确定是否可以进行这种简化 . 因为超平面与轴对齐，所以从它到任何其他点的最短线将是沿着一个维度的线，因此我们可以仅比较超平面分割的维度的坐标 .

如果它从搜索点到超平面的距离比从搜索点到当前的最近点更远，则没有理由搜索超过该分裂坐标 .

即使我的解释没有帮助，图形也会 . 祝你的项目好运！

回复于 2024-04-29T15:30:30+08:00

是的，维基百科上的KD树中的NN（最近邻）搜索的描述有点难以理解 . 在NN KD Tree搜索中获得最佳Google搜索结果只是完全错误，这无济于事！

这里有一些C代码向您展示如何正确使用它：

template <class T, std::size_t N>
void KDTree<T,N>::nearest (
    const const KDNode<T,N> &node,
    const std::array<T, N> &point, // looking for closest node to this point
    const KDPoint<T,N> &closest,   // closest node (so far)
    double &minDist,
    const uint depth) const
{
    if (node->isLeaf()) {
        const double dist = distance(point, node->leaf->point);
        if (dist < minDist) {
            minDist = dist;
            closest = node->leaf;
        }
    } else {
        const T dim = depth % N;
        if (point[dim] < node->splitVal) {
            // search left first
            nearest(node->left, point, closest, minDist, depth + 1);
            if (point[dim] + minDist >= node->splitVal)
                nearest(node->right, point, closest, minDist, depth + 1);
        } else {
            // search right first
            nearest(node->right, point, closest, minDist, depth + 1);
            if (point[dim] - minDist <= node->splitVal)
                nearest(node->left, point, closest, minDist, depth + 1);
        }
    }
}

在KD树上搜索NN的API：

// Nearest neighbour
template <class T, std::size_t N>
const KDPoint<T,N> KDTree<T,N>::nearest (const std::array<T, N> &point) const {
    const KDPoint<T,N> closest;
    double minDist = std::numeric_limits<double>::max();
    nearest(root, point, closest, minDist);
    return closest;
}

默认距离函数：

template <class T, std::size_t N>
double distance (const std::array<T, N> &p1, const std::array<T, N> &p2) {
    double d = 0.0;
    for (uint i = 0; i < N; ++i) {
        d += pow(p1[i] - p2[i], 2.0);
    }
    return sqrt(d);
}

编辑：有些人也在寻求数据结构的帮助（不仅仅是NN算法），所以这就是我所使用的 . 根据您的目的，您可能希望稍微修改数据结构 . （注意：但你几乎肯定不想修改NN算法 . ）

KDPoint类：

template <class T, std::size_t N>
class KDPoint {
    public:
        KDPoint<T,N> (std::array<T,N> &&t) : point(std::move(t)) { };
        virtual ~KDPoint<T,N> () = default;
        std::array<T, N> point;
};

KDNode类：

template <class T, std::size_t N>
class KDNode
{
    public:
        KDNode () = delete;
        KDNode (const KDNode &) = delete;
        KDNode & operator = (const KDNode &) = delete;
        ~KDNode () = default;

        // branch node
        KDNode (const T                       split,
                std::unique_ptr<const KDNode> &lhs,
                std::unique_ptr<const KDNode> &rhs) : splitVal(split), left(std::move(lhs)), right(std::move(rhs)) { };
        // leaf node
        KDNode (std::shared_ptr<const KDPoint<T,N>> p) : splitVal(0), leaf(p) { };

        bool isLeaf (void) const { return static_cast<bool>(leaf); }

        // data members
        const T                                   splitVal;
        const std::unique_ptr<const KDNode<T,N>>  left, right;
        const std::shared_ptr<const KDPoint<T,N>> leaf;
};

KDTree类:(注意：你需要添加一个成员函数来构建/填充你的树 . ）

template <class T, std::size_t N>
class KDTree {
    public:
        KDTree () = delete;
        KDTree (const KDTree &) = delete;
        KDTree (KDTree &&t) : root(std::move(const_cast<std::unique_ptr<const KDNode<T,N>>&>(t.root))) { };
        KDTree & operator = (const KDTree &) = delete;
        ~KDTree () = default;

        const KDPoint<T,N> nearest (const std::array<T, N> &point) const;

        // Nearest neighbour search - runs in O(log n)
        void nearest (const std::unique_ptr<const KDNode<T,N>> &node,
                      const std::array<T, N> &point,
                      std::shared_ptr<const KDPoint<T,N>> &closest,
                      double &minDist,
                      const uint depth = 0) const;

        // data members
        const std::unique_ptr<const KDNode<T,N>> root;
};

回复于 2024-04-29T15:30:30+08:00

最近邻居 - k-d树 - 维基百科证明

2 回答

相关问题