kd 树算法之详细篇

量化课堂第 40 篇（postId=2843，作者肖睿，编辑宏观经济算命师，难度进阶下、理解深度 level-1，2016-09-12 上线，v1.1 于 09-14 改错字、v1.2 于 2016-11-01 修正算法感谢 nemo1982）。kd 树系列（39 思路篇 + 本篇）的严格版：给出 kd 树的结构、递归构造算法（按中位数切分、轮换切分轴）与 kd 树上的 kNN 搜索算法（含剪枝判定），再用一个 13 点二维实例构造树、用 p=(−1,−5)、k=3 的完整数值跟踪走一遍查询。阅读前提：kNN（38 篇）。素材见 raw/collections/jq-quant-classroom/40-40-kd树算法之详细篇md.md。

量化kd树最近邻切分轴中位数剪枝

这是什么

一篇「能照着实现」的算法详解。上一篇（39）只讲「把空间切块存树」的直觉，本篇给出可操作的规格：节点存什么、怎么递归构造、怎么查最近 k 个点、什么条件下剪枝。全篇最值钱的是那个逐步演算的实例——从树的每一层比较到候选表的替换，把算法每一步落到具体数字上。

核心要点

kd 树的结构

每个节点记载【特征坐标、切分轴、指向左枝的指针、指向右枝的指针】。
特征坐标是 Rⁿ 里的一个点 (x₁,…,xₙ)；切分轴是整数 r（1≤r≤n），表示沿第 r 维切。
不变量：左枝所有点的第 r 维 ≤ 本节点第 r 维；右枝所有点 ≥ 本节点。

构造算法（递归）

|S|=1：该点为叶子，无左右枝。
|S|>1：按第 r 维坐标排序 → 取中位元素为当前节点坐标、记录切分轴 r → 中位之前的点进左枝 S_L、之后的进右枝 S_R → 对左右递归，且 r ← (r+1) mod n（每层换一维切，切完第 n 维回到第 1 维）。
偶数个点时取中位左边或右边「并无影响」。
构造例子：13 个随机点，r=0 对应 x 轴。先取 x 中位数 6.27 当根节点，x<6.27 左、>6.27 右；下一层 r=1 按 y 切；再 r=0 按 x 切……直到每格只剩一个点，树完成。

kd 树上的 kNN 算法

零：设 L 为长度 k 的列表，保存已搜到的最近点。
一：从根按 p 的坐标与每层切分下行（p 的第 r 维 < a 走左、否则走右）到含 p 的底部叶子。
二：标记叶子已访问；L 不足 k 个就把该点加入；L 已满且该点比 L 里最远的近 → 替换。
三：若当前节点不是整棵树顶端 → 执行 (a)；否则输出 L，完成。
- (a) 向上爬一格。未访问则标记并执行 (1)(2)；已访问则继续爬。
- (1) L 不足 k 就加入；L 满且该点更近就替换 L 中最远点。
- (2) 算 p 到当前节点切分线的距离。若该距离 ≥ L 中最远距离且 L 已满 k → 切分线另一边不可能更近，回 (三)；若该距离 < L 中最远距离或 L 不足 k → 另一边可能有更近，从另一枝回 (一) 搜。

完整算例（p=(−1,−5)，k=3，L₂ 距离）

下行：根比较 x（p 更小）→ 左；比较 y（p 更小）→ 左；叶子 (−4.6,−10.55)，L=[(−4.6,−10.55)]。
上爬 (−6.88,−5.4)：L 不足 3 → 加入；其左枝空，跳过。再爬 (1.24,−2.86)：L 不足 3 → 加入，L 满。
该节点有另一枝。p 到三点距离 6.62/5.89/3.10，而 p 到切分线只有 2.14 < L 最远 6.62 → 另一边可能有更近 → 去搜。
另一枝叶子 (1.75,12.26)：与 p 距离 17.48 > L 最远 → 不换。上爬一格，该点与 p 距离 4.91 < L 最远 6.62 → 替换掉 (−4.6,−10.55)。
再比切分线：距离 < L 与 p 的最小距离 → 再搜该点另一枝（单点，更远不换）。
继续爬到顶（经过已访问节点），顶端与 p 及切分线都更远，不再搜。
输出最近 3 个：L=[(−6.88,−5.4), (1.24,−2.86), (−2.96,−2.5)]。

机制 / 论证

为什么中位数切分：每层把一个区域大致一分为二，树高约 log N → 查询约 O(D·log N)，vs 蛮算 O(D·N)。中位数保证左右点数量相近、树尽量平衡。
为什么轮换切分轴 r←(r+1) mod n：各维轮流切，避免总沿一维把空间切成又长又窄的条（那样树的「附近」会失真）。
为什么 (2) 的剪枝正确：p 到分割面的距离若 ≥ L 里最远点距离，则分割面另一侧任何点到 p 的距离 ≥ 到面距离 ≥ L 最远距离——不可能更近，整枝跳过。
为什么算法对：L 始终维护「已访问区域内最近的 k 个」；剪枝保证「没访问的区域里没有更近的点」；爬到根时 L 就是全局最近 k 个。

可操作

想手写：构造 = 上面递归规格（排序取中位 → 分左右 → r+1 mod n）；查询 = 下行到底 + 维护长度 k 的候选表 L + 回溯时按「到切分面距离 vs L 最远距离」决定剪不剪。文中伪码可直接翻译成代码。
不想手写：scikit-learn 的 KNeighborsClassifier 内置（第 41 篇），algorithm 参数选 'kd_tree'。
数据量小时优势体现不出来，规模大才省——原文提醒，别在小 toy 上误判。
v1.2 修过算法（感谢 nemo1982 指出），以本篇为准；39 篇思路版与严格版有差异。

术语

kd 树节点：坐标 + 切分轴 + 左右枝指针。
切分轴 r：本层沿第几维切（1≤r≤n）。
中位数切分：按第 r 维排序取中点划分左右枝。
候选表 L：保存已找到的最近 k 个点（按到 p 的距离维护）。
剪枝：p 到分割面距离 ≥ L 最远距离时，跳过分割面另一侧。

不确定 / 待验证

构造与查询全程约 37 张图承载逐步过程，raw 只有图链；13 个点的坐标与树图、每次比较的中间状态大多在图内，正文只完整给了核心数字（6.27、(−4.6,−10.55)、6.62/5.89/3.10、2.14、17.48、4.91、最终 L 三个点）——这些已核对 [需要验证]。
「偶数取中位左或右无影响」指树仍有效，但具体树形与查询路径会不同；对性能的细微影响没讨论。
高维（n>2）性能、数据分布差时的退化、与 ball 树对比都没展开；只给「数据少看不出、规模大才省」的定性。
(2) 的剪枝在「到分割面距离 = L 最远距离」时按「不用搜」处理（≥ 剪枝）；边界情形原文没细讲。
叶子里也可以放多个点（第 41 篇 leaf_size 参数），本篇构造演示是一叶一点。