最近的邻居- k-d树- wikipedia证明
在k-d树的维基百科条目上，提出了一种在k-d树上进行最近邻搜索的算法.我不明白的是步骤3.2的解释。你怎么知道，仅仅因为搜索点的分裂坐标和当前节点之间的差异大于搜索点的分裂坐标和当前最佳点之间的差异，就没有更近的点？
二维KD树神经网络最近邻搜索动画 最近邻(NN)算法的目的是在树中寻找离给定输入点最近的点。通过使用树属性快速消除搜索空间的很大一部分，可以有效地完成此搜索。在kd-树中搜索最近的邻居的过程如下：
- 从根节点开始，算法递归地向下移动，就像插入搜索点时一样(即，它向右或向左移动，取决于该点在拆分维度中是大于还是小于当前节点)。
- 一旦算法到达一个叶节点，它就将该节点保存为“当前最佳”。
- 该算法将树的递归展开，在每个节点上执行以下步骤: 1.如果当前节点比当前最佳节点更接近，则该节点将成为当前最佳节点。2.该算法检查在分割平面的另一侧是否存在比当前最佳点更接近搜索点的点。在概念上，这是通过将分裂的超平面与搜索点周围的超球面相交来实现的，搜索点的半径等于当前最近的距离。由于超平面都是轴对齐的，这是作为一个简单的比较来实现的，以查看搜索点与当前节点的拆分坐标之间的差异是否小于从搜索点到当前最佳点的距离(总体坐标)。1.如果超球面横过平面，则平面另一侧可能有更近的点，因此算法必须按照与整个搜索过程相同的递归过程，从当前节点的另一个分支向下移动，寻找更接近的点。2.如果超球面不与分裂平面相交，则该算法继续沿着树向上行走，并消除该节点另一侧的整个分支。
- 当算法完成根节点的这一过程后，搜索就完成了。
该算法一般采用平方距离进行比较，避免了平方根的计算。此外，它还可以节省计算，将平方电流最佳距离保持在一个变量中进行比较。
回答 2
Stack Overflow用户
发布于 2010-01-10 08:12:05
仔细看页面上的动画的第6帧。
当算法返回递归时，有可能在它所在的超平面的另一边有一个更近的点。我们已经检查了一半，但另一半可能有更近的点。
事实证明我们有时可以简化一下。如果另一半的点不可能比我们目前最好的(最近的)点更接近，那么我们可以完全跳过这个超平面的一半。这个简化是在第6帧上显示的。
通过比较超平面到搜索位置的距离来判断这种简化是否可行。由于超平面与轴对齐，从它到任何其他点的最短线将沿着一维成一条线，所以我们只需比较超平面分裂的维数的坐标。
如果从搜索点到超平面的距离比从搜索点到当前最近点的距离更远，那么就没有理由通过这个分裂坐标进行搜索。
即使我的解释没有帮助，图形也会。祝你的项目好运！
Stack Overflow用户
发布于 2016-05-09 02:33:29
是的，维基百科上KD树中对NN (最近邻居)搜索的描述有点难以理解。这是没有帮助的，在NN树搜索上的谷歌搜索结果的批量是完全错误的！
下面是一些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;
};https://stackoverflow.com/questions/1627305
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号