$k$ 近邻的实现—— $kd$ 树

$k$ 近邻的主要工作量是：找到到样本最近的 $k$ 个点。最简单的无疑是线性扫描，但数据量太大时非常耗时不可行，因此提出了 $kd$ 树。

$kd$ 树

特点
- 一种对 $k$ 维空间中的实例点进行存储以便进行快速检索的树形结构
- 是二叉树
- 构造 $kd$ 树相当于不断用垂直于坐标轴的超平面将 $k$ 维空间划分
- 树的每个结点对应于一个 $k$ 维超矩阵区域
构造方法
输入维 $k$ 维空间数据集 $T = \left\{ {{x_1},{x_2}, \cdots ,{x_N}} \right\}$ ，其中 ${x_i} = {\left( {x_i^{\left( 1 \right)},x_i^{\left( 2 \right)}, \cdots ,x_i^{\left( k \right)}} \right)^T}$
- 构造根节点，根节点对应于包含 $k$ 维空间所有实例点的超矩阵区域
- 选择 ${x^{\left( 1 \right)}}$ 为坐标轴，以 $T$ 中所有实例的 ${x^{\left( 1 \right)}}$ 坐标的中位数为切分点，通过切分点并垂直于 ${x^{\left( 1 \right)}}$ 坐标轴的超平面将根节点的矩形区域分为两个子区域。
- 由根节点生成深度为 $1$ 的左、右子节点，左子节点对应坐标 ${x^{\left( 1 \right)}}$ 小于切分点的子区域，右子节点则是大于的。
- 重复：对深度为 $j$ 的结点，选择 ${x^{\left( l \right)}}$ 为切分的坐标轴， $l = j\left( {\bmod k} \right) + 1$ 。
- 直到两个区域都没有实例为止，形成 $kd$ 树的区域划分。

注：通过中位数分割得到的 $kd$ 树是平衡的，但平衡 $kd$ 树的搜索效率未必是最优的。

这里我们以最近邻为例，介绍搜索算法。

如图所示的 $kd$ 树，求S的最近邻（这里考虑欧式距离）。
统计学习方法——K近邻法【k-NN】（二）
其实将其转化为树的形式为：

整个搜索过程对比两个图，应该是：