kd 树（把空间切成二叉树的最近邻索引）

一句话

「已经找到比分割线更近的点时，分割线另一边就不用看了。」kd 树把这句话变成数据结构：空间切块存成树，查最近邻只在目标附近搜，配上这个几何剪枝规则就能省掉绝大多数距离计算。

当前理解

• 结构：每节点记【坐标、切分轴 r、左右枝】。左枝点的第 r 维 ≤ 节点，右枝 ≥。切分轴每层 r←(r+1) mod n 轮换。
• 构造（递归）：|S|=1 停（叶子）；否则按第 r 维排序、取中位数当节点，中位前左、后右，递归；偶数个点时取中位左或右「无影响」。例：13 点二维，根取 x 中位 6.27，下一层按 y，再按 x……直到一格一点。
• 查询（找最近 k 个）：
  1. 从根下行到目标所在叶子，维护长度 k 的候选表 L。
  2. 回溯向上，每到未访问节点，能改进 L 就替换 L 里最远的点。
  3. 剪枝判定：目标到该节点分割面的距离 ≥ L 中最远距离（且 L 已满 k）→ 另一侧不可能更近，跳过；否则另一侧可能更近，进去搜。
• 为什么对：以目标为圆心、当前最远距离为半径的球若不跨分割面，另一侧的点全在球外，不可能更近。
• 完整算例（40 篇）：p=(−1,−5)、k=3。叶子 (−4.6,−10.55)→L；上爬 (−6.88,−5.4)、(1.24,−2.86) 陆续进 L 至满；p 到三点距离 6.62/5.89/3.10，而到分割线只有 2.14 < 6.62 → 搜另一边 (1.75,12.26)（距离 17.48，弃）；上爬节点距离 4.91 < 6.62 → 替换 (−4.6,−10.55)；逐层剪枝到顶。最终 L=[(−6.88,−5.4), (1.24,−2.86), (−2.96,−2.5)]。
• 现成实现：scikit-learn 的 KNeighborsClassifier(algorithm='kd_tree')（41 篇）；另有 ball_tree。作者立场：可自写也可直接用库，但要懂轮子原理。

来源

• kd 树算法之思路篇 — 思路/直觉：为什么需要、空间切割、兔子纹身搜寻（postId=2627）
• kd 树算法之详细篇 — 定义 + 构造 + kNN 算法 + 完整数值算例（postId=2843）
• 关联概念：kNN（k 最近邻分类）（kd 树服务的算法本体）、熵与信息增益（衡量特征/因子带来多少信息）（同为本库 ML 方法族的概念层）

常见混淆

• kd 树 ≠ kNN：kd 树是加速 kNN 查询的数据结构，不是新的分类方法；分类仍是「找 k 近邻投票」。
• 39 思路篇 ≠ 严格 kd 树：思路篇按图等分、节点存整幅子图，是教学简化；严格版按中位数切、节点存单点、轮换轴——以 40 篇为准（40 篇 v1.2 还修正过算法）。
• O(D·log N) 是平均情形：数据分布差（点挤在窄条）时树可能不平衡、性能退化；本库没量化退化边界。
• 剪枝的「≥」边界：到分割面距离恰好等于 L 最远距离时按「不用搜」处理；边界情形原文没展开。
• kd 树适合中低维：超高维下它的优势减弱（趋向蛮算），维数灾难让所有点距离趋同；本库未展开。

开放问题

• 中位数切分时偶数取左/右「无影响」只保证树仍有效；不同选择对树平衡/查询性能的细微影响未讨论。
• kd 树 vs ball 树在真实高维数据上的性能对比、自实现 vs sklearn 的工程细节，本库未覆盖。
• 换距离度量（非 L₂）时，「到分割面距离」这个剪枝判据是否仍成立，未展开。
• kd 树这类索引的收益只在样本量大时明显（40 篇原文提醒「少量数据很难体现」）——对低频选股这种「样本几千、查询不频繁」的场景到底值不值得，量化语境里没有讨论。