[统计学习]第三章 K 邻近法

K-Nearest Neighbour 即 K 邻近算法，是可用于解决分类和回归问题的算法。在用于解决分类问题的思路是在已知的数据实例上，对于新的实例根据 $k$ 个最邻近的已知训练实例通过多数表决的方案进行预测，因此 $k$ 邻近算法不是一个显式学习过程。$k$ 邻近算法模型要素是通过 $k$ 选择，距离度量以及分类决策规则确认。

1. k 邻近算法

$k$ 邻近算法是通过多数表决的方式来确定新实例的类别，其整个训练流程:

1. 对于输入的实例 $T={(x_1, y_1), (x_2,y_2),\cdots,(x_N, y_N)}$ 满足 $x_i\in\mathcal{X} \subseteq \mathrm{R}^m$ 和 $y_i \in \mathcal{y}={c_1, c_2,\cdots,c_k}$，需要预测的实例 $x_i^\prime$ 输出的 结果是 $y$ 中某个类别
2. 学习的过程是实现 $y=\displaystyle{\text{argmax}_{c_j} \sum_{x_i\in N_{k}(x)}} I(y_i=c_j)$，当 $y_i=c_j$ 时 $I(y_i=c_j)$ 为 $1$，否则为 $0$

因为 $k$ 的不同选择，会有不同的结果，例如 $k=1$ 时表示最邻近的数据决定其类别。

1.1 模型

在完成建立邻近算法模型时，邻近的度量指标、$k$ 值选择以及相关的决策规则已经确立，对应于需要预测的新数据时通过模型确立时使用的特征子空间来判断所属的分类。换句话说也就是 $k$ 邻近算法的模型，是解决了从特征空间中选择合适的子空间来确认数据点分类。

下图的二维特征空间的例子，构建了每个实例点与其邻近的所有点组成的区域（这样的区域就是单元）：

1.2 度量指标

$k$ 邻近算法是非显性的学习，而判断学习效果需要一个重要的指标。而距离是一个比较通用的指标，包括了各种范数指标。不论是 $L_2$ 的欧式距离、$L_1$ 曼哈顿距离，还是 $L_p$ 的 Minkowski 距离，都可以通过以下的方式进行评估:
$$
\begin{align}
L_p(x_i, x_j)=\big(\displaystyle{\sum_{m=i}^m |x_i^m-x_j^m|^p} \big)^{\frac{1}{p}} \tag{1}\label{1}
\end{align}
$$
等式 $\ref{1}$ 中 $x_i,x_j \in \mathcal{X}$ 且 $m$ 为维度特征数量，Minkowski 距离 $p$ 范数是更泛化的距离，其取值范围为 $[1, \infin]$。其中当取值为 $\infin$ 时，计算的方式为 $\displaystyle{\max_{m}|x_i^m-x_j^m}|$，即取得各个坐标距离的最大值

1.3 k 值选择

$k$ 值差异会影响投票决策的数据点，如果 $k$ 越小表明训练实例可作用的领域会较小，很容易受到噪声的影响，容易发生过拟合，模型结构复杂度更高。反之如果 $k$ 越大，可以减小学习的估计误差，模型的复杂度相对较小。例如当 $k=N$ 时预测的结果由实例中最多的类决定。

2. KD 树

KD 树（即 K 维树，K Dimension Tree），是解决数据点在 K 维中划分问题的数据结构，其应用场景包括多维空间数据的搜索。而在 KNN 算法中，可以减少线性扫描计算输入实例和每个实例之间的距离所需要的时间消耗。

2.1 KD 树构造

KD 树实际还是是一个二叉树，其构建 k 维空间的划分可以看作在垂直于坐标轴的 k 维空间切分数据，最终产生一系列的 K 维超矩形区域。实例在被拆分到子区域内后（拆分为两个子区域），子区域会继续拆分直到子区域内没有实例时终止。在进行寻找子区域拆分点时，通过查找实例点在坐标轴上的中位数作为切分点——这样的好处是可以得到平衡树，但是在搜索上却未必是最有效率的一种方式。

2.1.1 构造算法

实施 KD 树的算法（构造平衡 KD 树）的过程如下：

---

输入：具有 $k$ 个维度的数据集 $T={x_1,x_2,\cdots,x_N }$，用列向量表示 $x_i=(x_i^{(1)},x_i^{(2)},\cdots,x_i^{(k)})$ 其中 $i\in[1,N]$

过程:

• 构造根节点 构建深度为 1 的二叉树（即根节点，其节点深度为 $0$），因此需要从 $k$ 维中选择一个特征（选择第一个特征 $x^{(1)}$）作为第一个切分点。切分点的查找是通过中位数点来确认，通过切分点可以在选择的维度上讲数据分为大于切分点和小于切分点两个子区域
• 构造深度为 $j$ 的节点，需要注意⚠️深度是选择特征的方式，其计算方式（计算第 $l$ 维特征选择）：$l=j (\text{mod}\ {k}) + 1$。通过选定的特征确认切分点，获取 $j$ 节点的数据划分。
• 终止条件，需要满足两个子区域没有实例

输出: KD 树

---

2.1.2 示例[^2]

使用二维数据 $T={(70, 721), (207, 313),(479,449), (615,40),(751,177),(888,555),(343,858) }$ 进行模拟构建 KD 树:

1. 选择第一维数据 ${70,207,479, 615, 751, 888,343 }$ 进行排序，通过中位数（$(479,449)$）进行数据拆分 $T_{\text{left}}={(70,721),(207, 313), (343, 858)}$ 和 $T_{\text{right}}={(615,40),(751,177),(888,555) }$

2. 利用下面的式子计算下一个节点使用的维度：
   $$
   l=j(\text{mod }k)+1
   $$
   例如划分第二个字节点时，数据 $T$ 的维度 $k$ 为 $2$，节点 $j$ 的值为 $1$，那么选用的维度 $l= 1 (\text{mod } 2)+1=2$，得到的结果是使用第二个维度划分第二个节点为。

3. 在 $T_{\text{left}}$ 和 $T_{\text{right}}$ 中分别使用 ${721, 313, 858 }$ 和 ${40, 177, 555 }$ 获取中位数切分点，得到节点的左右叶节点

4. 重复步骤 2 和步骤 3，直到平衡二叉树不可以在分隔出叶节点

2.2 KD 树搜索

KD 树进行 $k$ 近邻搜索时，可以利用其平衡树的特点减少搜索的计算量，其搜索的步骤为：

1. 通过对目标点进行计算，搜索其最近邻点
2. 通过包括目标点的叶节点（指的是包括目标点的最小超矩形区域）进行回退，一直回退到根节点。在过程中需要不断确定与目标点最近邻的节点。最近邻的搜索过程是以目标点为中心并通过当前最近点的超球体内部，之后返回当前叶节点的父节点。如果在父节点的另一子节点中超球体区域与当前超球体相交，那么以相交区域寻找更近实例点——如果存在这样点，那么其为最新的当前最近点。如果在过程中父节点的另一区域不与超球体相交，或者不存在比当前最近点更近的点，那么直接回退
3. 在根节点时结束，确定的最近邻节点即为最终结果

2.2.2 KD 树搜索算法

下面的搜索过程是最近邻搜索，不是 K 近邻搜索：

---

输入：构造完成的 KD 树以及需要查找的点 $x$
过程：

• 在 KD 树中找出包含目标点 $x$ 的叶节点，需要从根节点出现递归向下访问——因为是平衡树，$x$ 对比的维度上数据小于节点同维度值，向左节点移动反之向右。最终需要在叶节点上停止，以此叶节点为最近点
• 向上回退搜索——存在两种方式搜素
  • 回退后的节点，如果该节点比当前最近点距离目标最近，那么该店为新的最近点
  • 当前最近点的节点，需要检查同级的另一子节点对应区域是否存在更近点。检查的方式是以另一子节点对应的区域是否存在以目标点为球心的超球体，与目标点和当前最近邻点为半径的超球体是否相交——直接通过比较两者的半径是否差值是否小于 0 。相交那么可以跳到另一个子节点递归搜索，反之直接递归回退
• 到达根节点时停止

输出：目标点的最近邻节点

参考

[^1]: kd 树算法之思路篇 - JoinQuant量化课堂
[^2]: K-D Tree: build and search for nearest neighbor
[^3]: 平衡二叉搜索树
[^4]: knn算法-kd树原理(搜索)

说明:

1. 封面图 “File:K-nearest Neighbors.png” by Pkuwangyan06 is licensed under CC BY-SA 4.0
2. 缩略图来自 Flickr janeqjames