知识卡片
KD树的搜索与剪枝
在 KD 树上找最近邻分两个阶段:先”向下”拿到一个候选,再”回溯”修正它。回溯不是把整棵树都查一遍,而是用几何条件整枝剪掉不可能有更近点的子树。
向下:拿到初始候选。从根出发,比较目标点在当前切分维上的坐标与切分点:小于走左,否则走右,直到叶子。这一步相当于把目标点”投进”它所在的超矩形区域,因此到达的叶子点通常已经离它很近,是一个质量不错的初始最近邻。
回溯:修正并剪枝。从该叶子逐级回到父节点,每层做两件事:
- 若父节点本身比当前最近邻更近,更新当前最近邻;
- 判断父节点另一侧子空间里是否可能存在更近的点。
第 2 步就是剪枝的核心:以目标点为球心、以”目标点到当前最近邻的距离”为半径画一个球。如果这个球与另一侧切分超平面不相交,那么另一侧所有点到目标点的距离都大于半径,不可能成为更近的邻居,整棵子树可以跳过。只有球与超平面相交时,才需要进入另一侧继续搜索。回到根节点时搜索结束,当前的最近邻就是答案。
一个实例。目标点 (9,4):
- 根节点 (7,2),x 维 9 > 7 → 走右子节点 (9,6);它只有左子 (8,1) 且为叶子 → 初始最近邻取 (8,1)。
- 回溯到父节点 (9,6):到 (9,4) 的距离为 2,比 (8,1) 的 √10 更近 → 最近邻换成 (9,6)。
- (9,6) 没有另一子节点,无需检查另一侧;再回退到根,搜索结束,最近邻为 (9,6)。
(原文此处有一处笔误,写作”所以重新把(8,1)选为新的当前最近邻点”,按距离计算应为 (9,6);原文末尾的结论”最后的最近邻点就是(9,6)”与计算一致。)
为什么剪枝不丢解。超平面把空间分成两半,球若整个落在当前这一侧,另一侧的每个点都至少隔着超平面,距离必然不小于半径;而半径已经是一个实际存在的邻居的距离。既然不可能更近,就没有必要看。这个论证只依赖几何,与数据分布无关,所以剪枝是精确的,不是近似。
结构图:
flowchart TD
A[向下:按维比较走到叶子] --> B[叶子设为当前最近邻]
B --> C[回溯父节点 比较距离]
C --> D{父节点更近?}
D -->|是| E[更新当前最近邻]
D -->|否| F[保持原值]
E --> G{球与另一侧超平面相交?}
F --> G
G -->|否| H[剪枝 整枝略过]
G -->|是| I[进入该子节点继续搜索]
H --> J[继续回退至根 结束]
I --> J
边界:剪枝的有效性依赖”球很小”。维数一高,球的体积相对超矩形体积急剧缩小,几乎每个超平面都与之相交,剪枝大面积失效,搜索退化为暴力遍历。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 第05章 K近邻
原书出处 · 1 处
- 第5章 K近邻 5.4.2 搜索KD树 · 查看原书依据
检查该新的当前最近邻点的另一子节点对应的区域内是否有更近的点(相当于以该新的当前最近邻点为球心,以目标点和当前最近邻点间的距离为半径画球,看有无子节点在球内)