《统计学习方法》第三章：k 近邻法

k 近邻模型

k 近邻法将输入实例的特征空间划分为若干子空间，子空间中的若干实例 $x_i$ 同属于 $y_i$ 类别。具体来说，k 近邻法通过在训练集中找到与新输入实例最邻近的 k 个实例，这 k 个实例大部分属于 $y_i$ 类别，就也将新输入实例归属为 $y_i$ 类别。

k近邻模型

训练集数据为

$$ T=\{ (x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N) \} $$

其中 $x_i\in\mathbf{R}^n$ 为特征向量，$y_i\in\{c_1,c_2,\cdots,c_K\}$ 为实例类别。k 近邻法根据距离度量，在包括最邻近的 $k$ 个点的邻域 $N_k(x)$ 中确定 $x$ 的类别 $y$：

$$y=\arg \max_{c_j}\sum_{x_i\in N_k(x)}I(y_i=c_i),\qquad i=1,2,\cdots,N;\ j=1,2,3,\cdots,K$$

其中 $I$ 为指示函数，条件为真时为 $1$，条件为假时为 $0$。

在二维、三维空间中通常使用欧氏距离来衡量两点间的远近关系（相似程度）：

$$d=\sqrt{(x_2-x_1)^2+(y_2-y_1)^2}$$

$$d=\sqrt{(x_2-x_1)^2+(y_2-y_1)^2+(z_2-z_1)^2}$$

在 $\mathbf{R}^n$ 空间中，更通常的距离度量是 $L_p$ 距离，$L_p$ 距离是由距离度量的概念通过推广得到的，因此同样具有衡量两点间远近关系（相似程度）的作用。

设 $x_i,x_j\in\mathbf{R}^n$，$x_i$ 与 $x_j$ 的 $L_p$ 距离由下式给出：

$$L_p(x_i,x_j)=\left(\sum_{l=1}^n|x_i^{(l)}-x_j^{(l)}|^p\right)^{\frac{1}{p}}$$

k 近邻法的分类遵循多数表决规则，即输入实例附近 $k$ 个邻近的训练实例的大多数类决定了预测结果。因此 k 近邻法中的 $k$ 值决定了在一定的距离度量内选取分类「参考点」的数量，可以想知，若选取的 $k$ 值太小，分类结果会对最近邻的几个点敏感，模型就趋于复杂，更容易发生过拟合。

kd 树是一种二叉树，kd 树通过对 $\mathbf{R}^n$ 空间中每一个维度逐次地二分，最终将整个特征空间划分为若干超矩形，kd 树的每一个结点（训练实例）对应于一个超矩形。

算法 3.2

输入：数据集 $T$
输出：kd 树

选择 $x^{(1)}$ 为坐标轴，以所有实例的 $x_i^{(1)}$ 坐标中位数（若中位有两个数则取其中之一）为切分点，将 $x^{(1)}$ 切分为两部分。
重复切分：深度为 $j$ 的结点，选择 $x^{(l)}$ 为切分坐标轴，$l=j\ \mathrm{mod}\ k+1$。简单来说，
- 对于 $\mathbf{R}^2$ 空间，步骤为 $x^{(1)}\rightarrow x^{(2)}\rightarrow x^{(1)}\rightarrow\cdots$
- 对于 $\mathbf{R}^3$ 空间，步骤为 $x^{(1)}\rightarrow x^{(2)}\rightarrow x^{(3)}\rightarrow x^{(1)}\rightarrow\cdots$
直至将所有实例点切分完成。

构造kd树

算法 3.3

输入：kd 树，目标点 $S$
输出：$S$ 的最近邻

首先在 kd 树中找出目标点 $S$ 所属的区域，具体来说就是从根结点 $A$ 开始逐层向下访问，直到目标点 $S$。在访问过程的具体算法方面，可以通过判断点 $S$ 的坐标与切分点的大小关系来快速准确地确定访问路径。
到达点 $S$ 的父结点，以此结点作为 $S$ 的「当前最近点」。
递归向上层访问，每次访问进行两个操作：
1. 如果该点距离 $S$ 更近，将其作为新的「当前最近点」。
2. 因为 kd 为二叉树，该点必然存在另一分支子结点，那么就需要检查分支下是否存在更近的点。具体做法是判断分支子结点的区域是否与以点 $S$ 为圆心、以点 $S$ 与「当前最近点」距离为半径的圆相交。
  - 若相交，则访问分支子结点并进行 3 步骤；
  - 若不相交，回退到上一层。
最终回到根结点时，搜索结束。最后的「当前最近点」即为 $S$ 的最近邻。