第3章 K近邻法
K近邻法（k-Nearest Neighbor，简称k-NN）是一种基本且广泛使用的分类与回归方法。本章系统阐述k近邻法的算法原理、距离度量、k值选择、kd树结构以及相关的优化方法。
3.1 K近邻法基本算法
3.1.1 算法概述
k近邻法是一种懒惰学习（lazy learning）的判别方法。之所以称为懒惰学习，是因为它没有显式的训练过程，当给定训练数据集T和输入实例x时，算法仅在收到测试请求后才开始计算。换言之，k近邻法在训练阶段只是简单地将训练数据存储起来，待收到测试样本后再依据某种规则进行分类或回归预测。
具体而言，假设给定一个训练数据集：
其中，\(x_i \in \mathbb{R}^n\)为实例的特征向量，\(y_i \in \{c_1, c_2, \ldots, c_K\}\)为实例的类别标记。k近邻法在根据给定的距离度量，在训练集中找出与输入实例x最接近的k个点（即k个近邻），然后根据这k个近邻的类别信息来预测输入实例x所属的类别。
k近邻法不具有显式的学习过程这一特点，使其与之前介绍的感知机、朴素贝叶斯等方法形成鲜明对比。那些方法在训练阶段会通过优化算法学习到模型参数，而k近邻法则将所有计算推迟到预测阶段。
3.1.2 分类决策规则
在k近邻法中，分类决策规则通常采用多数表决（majority voting）方式。设k个近邻中属于类别\(c_j\)的样本数为\(\sum_{x_i \in N_k(x)} I(y_i = c_j)\)，其中\(N_k(x)\)表示与x距离最近的k个训练样本的集合，\(I(\cdot)\)为指示函数。多数表决规则等价于要求优化如下经验风险：
最小化该经验风险等价于最大化\(\sum_{x_i \in N_k(x)} I(y_i = c_j)\)，即选择出现次数最多的类别作为预测结果。从概率的角度看，这相当于后验概率最大的类别：
3.2 距离度量
k近邻法的核心在于如何定义"近邻"。距离度量（distance metric）决定了样本之间的相似性程度，直接影响k近邻算法的性能。本节介绍几种常用的距离度量方式。
3.2.1 闵可夫斯基距离
闵可夫斯基距离（Minkowski distance）是欧几里得距离和曼哈顿距离的一般化定义。设特征空间为\(\mathbb{R}^n\)，两点\(x_i = (x_i^{(1)}, x_i^{(2)}, \ldots, x_i^{(n)})^T\)和\(x_j = (x_j^{(1)}, x_j^{(2)}, \ldots, x_j^{(n)})^T\)，则闵可夫斯基距离定义为：
当\(p=1\)时，\(L_1\)称为曼哈顿距离；当\(p=2\)时，\(L_2\)称为欧几里得距离；当\(p \to \infty\)时，\(L_{\infty}\)称为切比雪夫距离（等价于\(\max_{l}|x_i^{(l)} - x_j^{(l)}|\)）。参数\(p\)的不同取值影响着距离计算的侧重点：\(p\)越小，对各维特征的差异越敏感；\(p\)越大，则越接近于考虑各维特征中的最大差异。
3.2.2 欧几里得距离
欧几里得距离（Euclidean distance）是\(p=2\)时的闵可夫斯基距离，即：
欧几里得距离是日常生活中最直观的空间距离概念，它对应于两点之间的直线段长度。在低维特征空间中，欧几里得距离应用最为广泛。当特征的各维度量纲一致时，欧几里得距离能较好地反映样本间的实际相似性。
3.2.3 曼哈顿距离
曼哈顿距离（Manhattan distance）是\(p=1\)时的闵可夫斯基距离，即：
曼哈顿距离的名称源于纽约曼哈顿街区的网格状街道布局——从一点到另一点需要沿着网格线行走，其路径长度等于曼哈顿距离。在某些应用场景下，如城市路径规划或具有离散特征的问题中，曼哈顿距离比欧几里得距离更为适用。
3.2.4 切比雪夫距离
切比雪夫距离（Chebyshev distance）是\(p \to \infty\)时的极限情况，其定义为：
切比雪夫距离只考虑各维度上差异最大的那一维，因此适用于需要以某个维度为主导的应用场景，例如棋盘游戏中王的移动步数计算。
3.2.5 距离度量的标准化
在实际应用中，不同特征通常具有不同的量纲和数值范围。如果直接使用原始特征计算距离，则数值范围大的特征将对距离产生主导性影响。因此，通常在计算距离之前对特征进行标准化处理，例如：
其中\(\mu_l\)和\(\sigma_l\)分别为第\(l\)个特征的均值和标准差。经过标准化后，各特征对距离的贡献更加均衡。
3.3 K值选择与误差分析
3.3.1 K值选择的原则
k值是k近邻法中最重要的超参数之一。k值的选择对模型的偏差和方差产生直接影响，进而影响分类性能。
当k值较小时： - 模型的偏差（bias）较低，因为近邻数量少，决策边界能够捕捉到更细致的局部结构。 - 模型的方差（variance）较高，因为预测结果对训练样本中的噪声非常敏感，个别噪声样本可能强烈影响预测结果。 - 极端情况下，当\(k=1\)时，模型称为"最近邻分类器"，决策边界会非常复杂，容易出现过拟合现象。
当k值较大时： - 模型的偏差较高，因为需要考虑更多的近邻点，决策边界趋于平滑，可能忽略一些局部细节。 - 模型的方差较低，因为多个近邻的投票能够抵消个别噪声样本的影响。 - 极端情况下，当\(k=N\)（训练样本总数）时，模型总是预测为训练集中样本数最多的类别，此时模型过于简单，偏差达到最大。
k值选择的一般原则是：在通过交叉验证等方法确定的候选值集合中，选择使验证集上误差最小的k值。通常，k值取奇数可以避免投票时出现平局的情况；k值一般不超过20，在实际应用中3、5、7、9等是常见的取值。
3.3.2 误分类率分析
考虑二分类问题，设训练数据集为T，损失函数采用0-1损失。k近邻法的误分类率（misclassification rate）可以从理论上进行分析。
给定输入实例x，其k个近邻构成集合\(N_k(x)\)。误分类率可以表示为：
其中\(f(x_i)\)为\(x_i\)的真实类别标签，\(I(\cdot)\)为指示函数。相应的，分类准确率可表示为：
从偏差-方差分解的角度看，k近邻分类器的期望预测误差可以分解为噪声方差、偏差平方和方差三部分。当k值较小时，方差主导误差；当k值较大时，偏差主导误差。因此，最优k值的选择需要在这两者之间取得平衡。
3.4 KD树
3.4.1 KD树构造算法
线性扫描（brute force）方式寻找k个最近邻的时间复杂度为\(O(N)\)，其中\(N\)为训练样本数。当训练数据集规模很大时，这种方法的计算开销非常高。kd树（kd-tree）是一种对k维空间中的样本点进行存储以便快速检索的数据结构，能够将最近邻搜索的时间复杂度降低到\(O(\log N)\)（平均情况）。
"kd树"中的"kd"表示"k-dimensional"，即k维空间。构造kd树的过程实际上是对训练数据集进行递归划分的过程。
算法3.1（kd树构造）
输入：k维空间数据集\(T = \{x_1, x_2, \ldots, x_N\}\)，其中\(x_i = (x_i^{(1)}, x_i^{(2)}, \ldots, x_i^{(k)})^T\)
输出：kd树
1。 开始构造根节点：选择其中一维（通常选择方差最大的维度或按维度序号轮流选择）作为切分坐标轴。 2。 确定切分点：在选定的坐标轴上，选取所有样本在该维度上的中位数对应的点作为切分点（如果中位数对应的点不唯一，可以选择任意一个）。将数据划分为两个子集：左子集包含该维度上值小于切分点值的样本，右子集包含大于等于切分点值的样本。 3。 对左子集和右子集分别递归执行步骤1-2，直至子集中没有样本点为止。 4。 每个节点对应一个超矩形区域，左子节点对应左下象限区域，右子节点对应右上象限区域。
构造kd树的时间复杂度为\(O(N \log N)\)，空间复杂度为\(O(N)\)。
3.4.2 KD树最近邻搜索算法
给定一个查询点x，kd树最近邻搜索的基本思想是利用kd树的结构特性，沿着树的路径快速排除不可能包含最近邻的子空间，同时维护一个当前最近邻距离上界。
算法3.2（kd树最近邻搜索）
输入：kd树、查询点x
输出：x的最近邻
1。 从根节点开始，比较查询点x与当前节点在切分维度上的坐标值，根据该值确定应当进入左子树还是右子树。同时将经过的节点依次压入一个栈中。 2。 递归搜索至叶节点，将该叶节点标记为"当前最近邻"，计算其与查询点的距离。 3。 从栈中弹出节点，逐一检查是否可能存在更近的近邻。具体做法是：计算查询点与当前节点的父节点所在超平面的距离，如果该距离小于当前最近邻距离，则说明在父节点的另一个子树中可能存在更近的点，需要递归搜索该子树。 4。 重复步骤3，直至栈为空。 5。 返回保存的最近邻点及其距离。
在理想情况下，kd树最近邻搜索的时间复杂度为\(O(\log N)\)，但最坏情况下（例如查询点位于kd树某个角落时）可能退化为\(O(N)\)。对于高维数据（维度较高时），kd树的检索效率会显著下降，这是因为大多数节点都可能被访问，这种现象称为"维度灾难"。
3.4.3 KD树K近邻搜索
kd树最近邻搜索算法可以扩展为k近邻搜索。主要区别在于：需要维护一个大小为k的优先队列（或者最大堆），以保存当前找到的k个最近邻。当找到新的候选点时，如果其距离小于队列中最大距离（队列头），则用新点替换队列头。搜索过程中的是否需要进入某子树的条件变为：查询点到当前节点的距离是否可能小于队列中最大距离。
3.5 Ball树与近似最近邻
3.5.1 Ball树结构
kd树在低维空间中效率很高，但如前所述，在高维空间中会遭遇效率退化问题。Ball树（ball tree）是另一种用于加速最近邻检索的空间索引结构，它通过构造嵌套的超球体（而非kd树中的超矩形）来划分空间，从而在高维空间中也能保持较好的检索效率。
Ball树的构造算法如下：
1。 从全部数据点中选择一个点作为球心（可以选择所有点的质心，或者通过k-means等方法确定）。 2。 以某个半径r作球，使得所有数据点都落在该球内（或通过其他准则确定球的半径）。 3。 找到一个距离球心最远的点，再找到距离该点最远的点（相对于第一步找到的球心），以这两点连线的中点作为新的球心。 4。 将所有数据点按与两个球心的距离划分为两个子集，递归地对每个子集构造ball树节点。
Ball树的搜索过程与kd树类似，也是从根节点开始，逐步向下遍历，并在回溯时检查是否需要搜索兄弟子树。Ball树的优势在于它构造的子空间是"圆形"的，能够更好地适应数据的实际分布，尤其在高维空间中表现优于kd树。
3.5.2 近似最近邻与LSH
在某些大规模应用场景中，精确的最近邻搜索可能过于耗时。此时，可以牺牲一定的精度，通过近似最近邻（Approximate Nearest Neighbor，ANN）算法来加速检索。
局部敏感哈希（Locality-Sensitive Hashing，LSH）是一种代表性的近似最近邻方法。LSH的核心思想是：设计一种哈希函数，使得距离相近的点以很高的概率被映射到相同的哈希桶中，而距离较远的点被映射到不同桶中的概率较低。
LSH函数族需要满足"局部敏感性"：如果两点\(p\)和\(q\)距离很近，则\(P(h(p) = h(q))\)应该很大；如果两点距离很远，则\(P(h(p) = h(q))\)应该很小。对于不同的距离度量（如欧几里得距离、汉明距离等），有不同的LSH函数族。
LSH的检索过程如下：
1。 将所有数据点通过LSH哈希函数映射到多个哈希表中。 2。 对于查询点q，计算其哈希值，找到对应的哈希桶。 3。 取出哈希桶中的所有点作为候选集合。 4。 在候选集合中精确计算距离，找出最近的k个点。
LSH的优点是检索速度快，缺点是可能遗漏真正的最近邻点。可以通过增加哈希表数量或降低哈希桶的阈值来提高精度，但这会增加存储开销和计算时间。
3.6 距离加权K近邻
3.6.1 距离加权投票
标准的k近邻法中，所有k个近邻对最终投票结果的影响是相同的。然而，在某些场景下，距离查询点更近的样本可能更具有参考价值。距离加权k近邻（distance-weighted k-NN）通过引入距离的倒数或距离平方的倒数作为权重，使距离较近的样本对分类决策产生更大影响。
设\(N_k(x)\)为与x距离最近的k个近邻的集合，距离加权投票的决策规则为：
其中权重\(w_i\)通常取为：
当使用\(1/d(x_i, x)^2\)作为权重时，距离越近的点在投票中的影响力越大；当使用\(1/d(x_i, x)\)时，影响力增长相对缓慢。距离平方的倒数形式更为常用，因为它能更好地突出最近邻的重要性。
需要注意的是，当查询点恰好与某个训练样本重合时（即距离为零），权重会变为无穷大。通常的处理方法是将距离加一个小的平滑项，或者当距离为零时直接返回该训练样本的标签。
3.6.2 距离加权回归
距离加权方法同样可以应用于回归问题。对于回归任务，预测值通常取为k个近邻的加权平均：
其中\(y_i\)为近邻\(x_i\)对应的目标值。这种方法称为距离加权k近邻回归，它能够得到比简单平均更平滑的预测曲线。
3.7 本章公式汇总
下表汇总了本章涉及的主要公式，便于复习和查阅。
| 序号 | 公式名称 | 公式表达式 | 说明 |
|---|---|---|---|
| 1 | 闵可夫斯基距离 | $$L_p(x_i, x_j) = \left( \sum_{l=1}^{n} | x_i^{(l)} - x_j^{(l)} |
| 2 | 欧几里得距离 | $\(L_2(x_i, x_j) = \sqrt{\sum_{l=1}^{n} (x_i^{(l)} - x_j^{(l)})^2}\)$ | \(p=2\)时的闵可夫斯基距离 |
| 3 | 曼哈顿距离 | $$L_1(x_i, x_j) = \sum_{l=1}^{n} | x_i^{(l)} - x_j^{(l)} |
| 4 | 切比雪夫距离 | $$L_{\infty}(x_i, x_j) = \max_{l} | x_i^{(l)} - x_j^{(l)} |
| 5 | 误分类率 | $\(r(x) = 1 - \frac{1}{k} \sum_{x_i \in N_k(x)} I(y_i = f(x_i))\)$ | 基于0-1损失 |
| 6 | 分类准确率 | $\(acc(x) = \frac{1}{k} \sum_{x_i \in N_k(x)} I(y_i = f(x_i))\)$ | 与误分类率互补 |
| 7 | 距离加权投票 | $\(y = \arg \max_{c_j} \sum_{x_i \in N_k(x)} w_i \cdot I(y_i = c_j)\)$ | 权重\(w_i = 1/d(x_i, x)^2\) |
| 8 | 距离加权回归 | $\(\hat{f}(x) = \frac{\sum_{x_i \in N_k(x)} w_i \cdot y_i}{\sum_{x_i \in N_k(x)} w_i}\)$ | 加权平均形式 |
3.8 小结
本章系统介绍了k近邻法这一经典的机器学习方法。主要内容包括：
1。 基本算法：k近邻法是一种基于实例的学习方法，采用多数表决规则进行分类预测，没有显式的模型训练过程（懒惰学习）。
2。 距离度量：闵可夫斯基距离是欧几里得距离、曼哈顿距离和切比雪夫距离的统一框架，不同的p值对应不同的距离计算方式。
3。 k值选择：k值的选择直接影响模型的偏差-方差权衡。k值越小，模型越复杂（低偏差高方差）；k值越大，模型越简单（高偏差低方差）。实际应用中需要通过交叉验证确定最优k值。
4。 kd树：kd树是一种空间索引结构，通过对k维空间进行递归划分来加速最近邻检索，平均时间复杂度为\(O(\log N)\)。
5。 Ball树：Ball树是另一种空间索引结构，在高维空间中优于kd树。
6。 近似最近邻：LSH等近似算法通过牺牲一定精度来换取检索速度的显著提升，适用于大规模数据场景。
7。 距离加权：通过引入距离倒数作为权重，使距离更近的样本对预测结果产生更大影响。
k近邻法作为一种简单、直观且效果稳健的方法，在文本分类、推荐系统、图像识别等领域有着广泛的应用。理解其原理、优缺点以及适用场景，对于实际工程应用和进一步学习更高级的机器学习方法都具有重要意义。
3.7 公式汇总表
| 编号 | 公式名称 | 公式形式 | 说明 | 类型 |
|---|---|---|---|---|
| (3.1) | k-NN决策规则 | \(\hat{y} = \arg\max_{c \in \mathcal{Y}} \sum_{i=1}^{k} w_i \cdot \mathbb{I}(y_i = c)\) | k近邻分类决策 | 公式 |
| (3.2) | 欧氏距离 | \(d(\mathbf{x}, \mathbf{z}) = \sqrt{\sum_{j=1}^{n} (x_j - z_j)^2}\) | 最常用距离度量 | 距离 |
| (3.3) | 曼哈顿距离 | $d_1(\mathbf{x}, \mathbf{z}) = \sum_{j=1}^{n} | x_j - z_j | $ |
| (3.4) | 闵可夫斯基距离 | $d_p(\mathbf{x}, \mathbf{z}) = \left(\sum_{j=1}^{n} | x_j - z_j | ^p\right)^{1/p}$ |
| (3.5) | kd树构建 | 在第j维上划分数据，左子树取值≤分割值，右子树取值>分割值 | kd树递归构建 | 算法 |
| (3.6) | kd树搜索 | 从根节点递归比较，叶子节点最近邻为候选，父节点兄弟子树裁剪 | kd树最近邻搜索 | 算法 |