kd 树算法之思路篇

量化课堂第 39 篇（postId=2627，作者肖睿，编辑宏观经济算命师，难度进阶上、理解深度 level-1，2016-09-01 上线）。kd 树系列（39+40）的思路篇。它不讲严格定义，只回答一个直觉问题：为什么人一眼能认出「附近」而计算机不行？答案是——把干巴巴的坐标数据加工成带空间结构的形式（把空间切块、存成二叉树），就能快速读取邻近点。阅读前提是 kNN（第 38 篇，postId=2227）。素材见 raw/collections/jq-quant-classroom/39-39-kd树算法之思路篇md.md。

量化kd树空间分割二叉树最近邻剪枝

这是什么

kd 树（k-dimensional tree）是一个记录空间信息的二叉树数据结构，用来高效算 kNN。特征维度 D、样本数 N 时，kd 树查询约 O(D·log N)，比穷算 O(D·N) 省很多。本文是全系列的直觉铺垫：用「兔子纹身哪个离爱心最近」的图，演示怎么把平面反复等分成小区域、用树记录，再沿树找最近点、用「比分割线更近就不用看另一边」剪枝。作者明说：本文例子与严格 kd 树有差异，想直接上严格版的读者可以跳去第 40 篇。

核心要点

为什么需要 kd 树：计算机没有「附近」的眼睛

问题：一堆已知样本 + 一个被问的点（红五角星），找离它最近的 15 个点。蛮算要和全部样本算距离（例子里约 300 次）。
人看图能一眼圈出紫圈里的候选，因为眼睛输入的是已经带距离概念的影像；计算机拿到的只有坐标数字，没有捷径——不加工就得 300 个全算。
结论：要在坐标数据上做加工——把空间分割成小块、以合理方式存储，方便读取「附近」的点。

切割：兔子纹身

兔子身上四个纹身（爱心、月亮、星星、眼泪），特征是平面上的横竖坐标。蛮算要算 3 次距离。
沿竖向中间切成两半 → 横向切成四份 → 竖向切八份 → 横向再切（空白区域舍弃，得 14 份）。
把切分记录成二叉树：每个节点是一幅图，两个枝是它平分出的子图。
树承载了局部性：两个点在树里离得近，实际距离也近。

搜寻：沿树找爱心

从树顶向下，找到最底部包含爱心的节点：每层是沿 x=a 或 y=a 切分，比较爱心的 x/y 坐标与 a 的大小决定走左枝还是右枝。
找到后沿同路径向上爬，遇到同区域的纹身就算距离。
关键剪枝：比较「爱心-月亮距离」（红线）与「爱心-分割线距离」（蓝线）。若前者 < 后者，分割线右边任何点都不可能更近 → 直接判月亮最近。
点到分割线距离 = 坐标差的绝对值，比算两点欧氏距离省很多计算。

麻烦：分割线另一边真有更近的点

兔子又加了叶子和圆圈两个纹身。找爱心最近点时：向上爬到有月亮的节点，记录「月亮，距离 d₁」。
若 d₁（红线）大于爱心到分割线的距离（蓝线）→ 另一边可能有更近点 → 从另一枝往下搜，找到圆圈算 d₂，d₂>d₁ 就丢弃。
再向上，发现 d₁ 又大于新的分割线距离 → 再去另一枝搜到叶子，算 d₃<d₁ → 把纸上记录更新为「叶子，d₃」。
爬到树顶时，纸上记载的就是最近点。全程只访问了少数几个区域。

结语

规则一句话：已经找到比切分线更近的点时，切分线另一边的点不用搜了（只会更远）。通过空间分割 + 树状存储，只在问题点附近搜就能找到最近点。
本文讲的还不是严格 kd 树；下一篇（第 40 篇，postId=2843）系统讲 kd 树定义与 kNN 算法。实现可自写，也可用 scikit-learn（蛮算/kd 树/ball 树三选一，见第 41 篇）。

机制 / 论证

为什么树能省计算：kNN 只需要问题点附近区域的数据。空间分割让「附近」变成树里的一个小邻域，查询从「全量算距离」变成「沿着树走一小段 + 少量回溯」。
为什么剪枝合法：以问题点为圆心、当前最近距离为半径画圈。如果这个圈没越过某条分割线，那线的另一侧全在圈外——任何点都不可能更近，不必计算。这就是第 40 篇「(2)」剪枝判定的几何直觉。
为什么人觉得简单、计算机觉得难：人看图的输入自带距离（影像），计算机只拿坐标。这解释了「空间索引」的必要性——把坐标变成可快速回答邻近查询的结构。
作者的方法论立场：做不做轮子（自写算法）另说，但要懂轮子怎么造；会了以后用 scikit-learn 很轻松。这是本批「原理 + 现成库」双线安排的原因。

可操作

思路篇没有代码。要落地看第 40 篇的严格构造与搜索算法，或直接用 scikit-learn 的 KNeighborsClassifier（algorithm 可选 'kd_tree'，见第 41 篇）。
阅读建议：先掌握 kNN（38 篇）再读本系列；两篇（39/40）内容部分重叠，思路篇服务直觉、详细篇给严格版。
判断自写 vs 用库：数据规模大、性能敏感才需要关心实现；一般用途 scikit-learn 足够。

术语

kd 树（k-dimensional tree）：记录空间信息的二叉树，kd 树的高效 kNN 工具。
空间切割 / 切分轴：沿某维把空间分成两块。
蛮力（brute force）：逐个算距离的朴素做法，O(D·N)。
剪枝：通过几何判定跳过不可能更近的区域。
ball 树：另一类基于树的最近邻算法（scikit-learn 里与 kd 树并列，本文只预告）。

不确定 / 待验证

全文约 20 张图（兔子纹身的切割/搜寻过程）承载几何演示，raw 只有图链；具体切割线位置、距离数值都在图内，文字只给了定性步骤 [需要验证]。
O(D·log N) 复杂度是理想/平均情形；数据分布极端（点挤在窄条里）时树可能不平衡、性能退化，本文未谈。
「树上近 ≈ 实际近」依赖切割较均匀；思路篇的等分切法与严格 kd 树（按中位数、轮换轴）的差异在第 40 篇修正。
思路篇明确声明自己的例子和算法「与严格的 kd 树有一些差异」，正式定义以第 40 篇为准。
代码实现（如何存树、递归细节）本文未给。