【统计学习方法死磕系列】k近邻法

众所周知，音乐可以按风格来分类，然而风格本身是由什么来定义的呢？由谁来判定某首音乐属于那种风格？也就是说同一种风格的音乐又会具有哪些公共的特征呢？正因此也没有哪一位歌手会主动标榜自己的歌和以前的某首歌类似，但我们却实实在在的知道每一首歌在风格上的确有可能会和同风格的歌曲相近。类似于处理这样的分类问题，我们就可以使用k-近邻算法，来自动划分歌曲的风格类型。

一、k 近邻法概述

k 近邻法（k-Nearest Neighbors, k-NN）是机器学习中最简单、最直观的算法之一。它是一种非参数（non-parametric）、惰性学习（lazy learning）方法，由 Cover 和 Hart 于 1968 年提出。

1.1 核心思想

物以类聚，人以群分。

k-NN 的基本假设是：特征空间中距离相近的样本倾向于属于同一类别。因此，对于一个新样本，我们只需在训练集中找到它的 k 个最近邻居，然后根据这些邻居的标签做出预测。

1.2 算法特性速览

特性	说明
训练方式	惰性学习（lazy learning）——无显式训练过程，直接存储数据
参数形式	非参数模型——模型容量随数据量增长
适用任务	分类、回归
优点	精度高，对异常值不敏感，无需数据分布假设，实现简单
缺点	计算复杂度高、空间复杂度高、对高维数据效果差
适用范围	数值型和标称型（只在有限目标集中取值）

1.3 一般流程

k-近邻算法流程

计算已知标签的训练集中每个点与待分类点之间的距离

按照距离递增排序

选取与当前点距离最近的 k 个点

确定前 k 个点所属标签的出现频率

返回前 k 个点出现频率最高的标签作为当前点的预测类别

二、k 近邻模型的三要素

k 近邻模型的核心由三个要素决定：距离度量、k 值选择和分类决策规则。

2.1 距离度量

特征空间中两个样本点 $x_i = (x_i^{(1)}, x_i^{(2)}, \dots, x_i^{(n)})$ 和 $x_j = (x_j^{(1)}, x_j^{(2)}, \dots, x_j^{(n)})$ 之间的距离定义了”近邻”的含义。常用的距离度量如下。

2.1.1 闵可夫斯基距离（Minkowski Distance）

闵可夫斯基距离是距离度量的统一形式：

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

其中 $p$ 是一个可变参数。

当 $p = 1$ 时——曼哈顿距离（Manhattan Distance）：

$$ L_1(x_i, x_j) = \sum_{l=1}^{n} |x_i^{(l)} - x_j^{(l)}| $$

也称为城市街区距离（City Block Distance）。想象在曼哈顿的网格状街道上行走，你只能沿水平和垂直方向移动，不能沿对角线穿越街区。

当 $p = 2$ 时——欧氏距离（Euclidean Distance）：

$$ L_2(x_i, x_j) = \sqrt{\sum_{l=1}^{n} (x_i^{(l)} - x_j^{(l)})^2} $$

这是我们最直观的”直线距离”，也是最常用的距离度量。

当 $p \to \infty$ 时——切比雪夫距离（Chebyshev Distance）：

$$ L_{\infty}(x_i, x_j) = \max_{l} |x_i^{(l)} - x_j^{(l)}| $$

在国际象棋中，国王从 $(x_1, y_1)$ 到 $(x_2, y_2)$ 所需的最少步数就是 $\max(|x_2-x_1|, |y_2-y_1|)$。

2.1.2 其他重要距离度量

余弦相似度（Cosine Similarity）：常用于文本分类和高维稀疏数据：

$$ \cos(x_i, x_j) = \frac{x_i \cdot x_j}{\|x_i\| \cdot \|x_j\|} $$

关注的是向量方向的相似性而非绝对量级。对应的距离为 $1 - \cos(x_i, x_j)$。

马氏距离（Mahalanobis Distance）：考虑了特征间的相关性：

$$ D_M(x_i, x_j) = \sqrt{(x_i - x_j)^T \Sigma^{-1} (x_i - x_j)} $$

其中 $\Sigma$ 是特征的协方差矩阵。马氏距离是尺度无关的（scale-invariant），克服了欧氏距离中将各特征”等权”看待的缺点。

汉明距离（Hamming Distance）：用于离散/二值特征：

$$ D_H(x_i, x_j) = \sum_{l=1}^{n} \mathbb{I}(x_i^{(l)} \neq x_j^{(l)}) $$

即两个字符串对应位置不同字符的个数。

杰卡德距离（Jaccard Distance）：用于集合相似度：

$$ D_J(A, B) = 1 - \frac{|A \cap B|}{|A \cup B|} $$

2.1.3 距离度量的选择指南

场景	推荐度量
低维连续特征	欧氏距离
高维稀疏（如文本 TF-IDF）	余弦相似度
特征尺度差异大	马氏距离
网格/离散数据	曼哈顿距离
二值特征	汉明距离
集合比较	杰卡德距离

重要提醒：距离度量依赖于特征的尺度。如果特征 $x_1$ 范围是 $[0, 1]$ 而 $x_2$ 范围是 $[0, 10000]$，$x_2$ 将主导欧氏距离的计算。因此使用 k-NN 前必须进行特征归一化。

2.2 k 值的选择

k 值的选择对 k-NN 的结果有决定性影响。

2.2.1 k 值的影响

k 过小（如 k = 1）：

模型复杂度高，容易过拟合
分类边界曲折而不光滑，对噪声数据非常敏感
在极限情况（k = 1），训练误差为零但不代表泛化性能好
决策面呈现 Voronoi 分割

k 过大（如 k = N）：

模型过于简单，容易欠拟合
决策边界过于平滑
极限情况（k = N），对所有样本都预测训练集的多数类，完全忽略数据的局部结构

k 适中：

在偏差（bias）和方差（variance）之间取得平衡
可以用交叉验证来选择

2.2.2 k 值选择策略

通常选择小于训练样本数平方根的奇数（避免平票）：

import numpy as np
from sklearn.model_selection import cross_val_score
from sklearn.neighbors import KNeighborsClassifier

# 通过交叉验证选择最佳 k
best_k = 1
best_score = 0
for k in range(1, int(np.sqrt(N)) + 2, 2):  # 奇数
    knn = KNeighborsClassifier(n_neighbors=k)
    scores = cross_val_score(knn, X, y, cv=5)
    if scores.mean() > best_score:
        best_score = scores.mean()
        best_k = k

2.2.3 可视化 k 值的影响

以一个二维二分类问题为例：

k = 1：决策边界紧贴数据点，产生许多”孤岛”
k = 5：决策边界更平滑但仍能捕捉局部特征
k = 15：决策边界非常平滑，但可能丢失重要的类别细节
k = 50：决策边界接近线性，严重欠拟合

2.3 分类决策规则

k-NN 的分类决策规则通常是多数表决（majority voting）：

$$ \hat{y} = \arg\max_{c \in \mathcal{Y}} \sum_{x_i \in N_k(x)} \mathbb{I}(y_i = c) $$

其中 $N_k(x)$ 是样本 $x$ 的 $k$ 个最近邻的集合。

2.3.1 加权投票

当不同距离的邻居应当具有不同的重要性时，可以引入距离加权：

$$ \hat{y} = \arg\max_{c \in \mathcal{Y}} \sum_{x_i \in N_k(x)} w_i \cdot \mathbb{I}(y_i = c) $$

其中权重常见的形式有：

反距离权重：$w_i = \frac{1}{d(x, x_i)}$ 或 $w_i = \frac{1}{d(x, x_i)^2}$
高斯核权重：$w_i = \exp\left(-\frac{d(x, x_i)^2}{2\sigma^2}\right)$
均匀权重：$w_i = 1$（即标准多数表决）

加权 k-NN 对邻居的贡献进行差异化对待，在实践中通常比均匀权重表现更好，尤其当 k 较大时。

2.3.2 k-NN 回归

对于回归任务，预测值为 k 个近邻标签的（加权）平均：

$$ \hat{y} = \frac{1}{k} \sum_{x_i \in N_k(x)} y_i $$

加权回归：

$$ \hat{y} = \frac{\sum_{x_i \in N_k(x)} w_i y_i}{\sum_{x_i \in N_k(x)} w_i} $$

三、高维灾难与 k-NN 的困境

3.1 维度的诅咒（Curse of Dimensionality）

k-NN 在高维空间中会遇到严重问题。当特征维数 $d$ 增大时：

距离度量失效：在高维空间中，最近邻和最远邻之间的距离差越来越小，所有点之间的距离趋于相等，距离的概念丧失了判别力。
数据稀疏：要维持相同的密度，所需数据量随维数指数增长。
最近邻不稳定：微小的噪声扰动就可能改变最近邻集合。

3.2 数学分析

考虑 $d$ 维单位超立方体中的均匀分布。某样本到其最近邻的期望距离为：

$$ \mathbb{E}[d_{\min}] \approx \left(\frac{\Gamma(1 + d/2)}{N}\right)^{1/d} \frac{1}{\sqrt{\pi}} $$

当 $d$ 很大时，该距离将接近超立方体的对角线长度，说明”近”的概念已经模糊。

3.3 应对策略

特征选择：使用互信息、卡方检验等方法降维
特征提取：PCA、LDA 等降维技术
距离度量学习（Metric Learning）：学习一个马氏距离矩阵
哈希方法：LSH（局部敏感哈希）用于近似最近邻
放弃 k-NN：在高维场景下转向更适合的模型

四、k-d 树：加速近邻搜索

当训练集很大时，暴力搜索（线性扫描）每次查询需要 $O(Nd)$ 的时间，这对于实时应用是不可接受的。k-d 树（k-dimensional tree）是一种加速 k-NN 搜索的数据结构。

4.1 k-d 树的构造

k-d 树是一种对 k 维空间进行划分的二叉树，每个节点对应一个超矩形区域。

构造算法（递归）：

function build_kd_tree(points, depth):
    if points is empty:
        return None
    
    // 选择划分维度（轮流选择）
    axis = depth mod k
    
    // 按当前维度排序，取中位数点作为分割点
    sort points by axis-th coordinate
    median_index = len(points) // 2
    
    node = new Node()
    node.point = points[median_index]
    node.axis = axis
    
    // 左右子树
    node.left = build_kd_tree(points[0:median_index], depth + 1)
    node.right = build_kd_tree(points[median_index+1:], depth + 1)
    
    return node

时间复杂度：$O(N \log N)$。

4.2 k-d 树的最近邻搜索

搜索算法：

从根节点出发，递归向下移动，按比较结果走左子树或右子树，直到到达叶节点。将此叶节点作为当前的”最佳点”。
回溯展开递归：
- 检查当前节点是否比”最佳点”更近，如果是则更新最佳点
- 检查当前节点的另一子树所在区域是否有更近的可能性（即超球是否与超矩形相交）。如果相交，则进入另一子树搜索
最终回到根节点时，最佳点即为最近邻

平均时间复杂度：$O(\log N)$（低维情况下）。

最坏时间复杂度：$O(N)$（高维时退化为暴力搜索，实际中当 $d > 20$ 时 k-d 树优势大幅减弱）。

4.3 k-d 树的局限性

当维数较高（一般认为 $d > 20$）时效率显著下降
对频繁插入/删除的操作需要重新平衡
只适用于欧氏距离和闵可夫斯基距离族

五、球树（Ball Tree）

球树是 k-d 树的一种改进，用超球体（hypersphere）而非超矩形划分空间。

5.1 构造原理

球树的每个节点对应一个超球，包含该节点中所有数据点。构造方式：

选择一个节点内最远的点作为第一中心
选择离第一中心最远的点作为第二中心
将所有数据点分配到离其最近的中心
为两个子集分别计算最小包围球
递归构造

5.2 搜索优势

球树在搜索时使用三角形不等式剪枝：

$$ d(q, p) \geq |d(q, c) - r| $$

其中 $q$ 是查询点，$c$ 是球心，$r$ 是球半径。如果 $|d(q, c) - r|$ 已经大于当前最佳距离，则整个球可以被安全剪枝。

球树在高维空间中通常优于 k-d 树。

5.3 k-d 树 vs 球树 vs 暴力搜索

方法	构造时间	查询时间	适用维度	距离支持
暴力搜索	O(1)	O(Nd)	任意	任意
k-d 树	O(N log N)	O(log N)*	d < 20	闵可夫斯基
球树	O(N log N)	O(log N)*	d < 100	任意度量
VP 树	O(N log N)	O(log N)*	中高维	任意度量

*平均情况，最坏可能退化为 O(N)

六、局部敏感哈希（LSH）

局部敏感哈希（Locality-Sensitive Hashing, LSH）是另一种处理大规模高维数据近邻搜索的技术，核心思想是：将高维空间中相近的点以高概率映射到相同的哈希桶中。

6.1 形式化定义

一个哈希函数族 $\mathcal{H}$ 是 $(d_1, d_2, p_1, p_2)$-敏感的，如果对于任意两点 $p, q$：

若 $d(p, q) \leq d_1$，则 $P_{h \in \mathcal{H}}[h(p) = h(q)] \geq p_1$
若 $d(p, q) \geq d_2$，则 $P_{h \in \mathcal{H}}[h(p) = h(q)] \leq p_2$

且 $d_1 < d_2$，$p_1 > p_2$。

6.2 常见 LSH 方法

用于余弦距离的 SimHash：

$$ h(p) = \text{sign}(p \cdot r) $$

其中 $r$ 是随机超平面的法向量。相似的向量倾向于落在超平面的同侧。

用于欧氏距离的 p-stable LSH：

$$ h(p) = \left\lfloor \frac{a \cdot p + b}{w} \right\rfloor $$

其中 $a$ 是服从 p-stable 分布的随机向量，$b$ 是 $[0, w]$ 上的均匀随机数。

用于汉明距离：直接随机选择比特位。

6.3 放大技术

使用 AND-OR 组合来放大 LSH 的精度和召回率：

AND 组合：$g(p) = (h_1(p), h_2(p), \dots, h_k(p))$，两点的所有 k 个哈希值都相同时才碰撞——提高精度
OR 组合：建立 L 个 AND 组合的哈希表，任意一个碰撞即可——提高召回率

七、k-NN 的优化技巧

7.1 特征归一化

k-NN 对特征尺度敏感，必须做归一化。常用方法：

# Min-Max 归一化
from sklearn.preprocessing import MinMaxScaler
X_scaled = MinMaxScaler().fit_transform(X)

# Z-score 标准化
from sklearn.preprocessing import StandardScaler
X_scaled = StandardScaler().fit_transform(X)

何时用 Min-Max，何时用 Z-score？

场景	推荐方法
特征边界已知且稳定	Min-Max
需要保持稀疏特征	Min-Max
特征有离群点	RobustScaler（中位数 + IQR）
假设特征近似正态分布	StandardScaler（Z-score）

7.2 压缩近邻（Condensed Nearest Neighbor）

为了减少存储和计算开销，可以通过只保留”分类边界附近”的样本来压缩数据集。CNN 算法：

1. 初始化：随机选一个样本加入压缩集 S
2. 用 S 中的样本对剩余样本分类
3. 将所有被错误分类的样本加入 S
4. 重复步骤 2-3 直到 S 不再变化

CNN 可以大幅减少训练样本数，但对噪声敏感。

7.3 编辑近邻（Edited Nearest Neighbor）

通过移除被其邻居”投票否决”的样本来清理噪声：

1. 用整个训练集对每个样本做 k-NN 分类（留一法）
2. 移除所有被分错的样本
3. 用清理后的数据集进行预测

ENN 可以平滑决策边界并减少噪声的影响。

八、k-NN 与其他算法的比较

8.1 k-NN vs k-means

尽管名字相似，但两者完全不同：

方面	k-NN	k-means
任务类型	监督学习（分类/回归）	无监督学习（聚类）
输入	需要带标签的训练数据	无标签数据
训练过程	无（惰性学习）	迭代优化簇中心
参数 k	近邻数量	簇的数量
预测	查询邻居投票	分配到最近的簇中心

8.2 k-NN vs SVM

方面	k-NN	SVM
训练复杂度	O(1)（无训练）	O(N^2) 到 O(N^3)
预测复杂度	O(Nd) 暴力	O(Sd)（S 为支持向量数）
对高维数据	差（维度灾难）	好（核技巧）
非线性决策面	自然支持	需要核函数
概率输出	可按比例输出	需要 Platt scaling
缺失标签处理	自然	需专门方法

8.3 k-NN vs 决策树

方面	k-NN	决策树
可解释性	低（基于实例）	高（规则可读）
对噪声	对 k 小则很敏感	容易过拟合
特征重要度	不直接提供	基于信息增益
增量学习	自然支持	需重建树
缺失值	需要填入	可通过代理分裂处理

九、Python 实现

9.1 从零实现 k-NN 分类器

import numpy as np
from collections import Counter

class KNNClassifier:
    def __init__(self, k=3, metric='euclidean', weights='uniform'):
        self.k = k
        self.metric = metric
        self.weights = weights
    
    def fit(self, X, y):
        """惰性学习：仅存储数据"""
        self.X_train = np.array(X)
        self.y_train = np.array(y)
        return self
    
    def _distance(self, x1, x2):
        """计算两点之间的距离"""
        if self.metric == 'euclidean':
            return np.sqrt(np.sum((x1 - x2) ** 2))
        elif self.metric == 'manhattan':
            return np.sum(np.abs(x1 - x2))
        elif self.metric == 'cosine':
            dot = np.dot(x1, x2)
            norm = np.linalg.norm(x1) * np.linalg.norm(x2)
            return 1 - dot / (norm + 1e-10)
        else:
            raise ValueError(f"Unknown metric: {self.metric}")
    
    def predict_one(self, x):
        """预测单个样本"""
        # 计算到所有训练样本的距离
        distances = np.array([
            self._distance(x, x_train) for x_train in self.X_train
        ])
        
        # 获取 k 个最近邻的索引
        k_indices = np.argsort(distances)[:self.k]
        k_distances = distances[k_indices]
        k_labels = self.y_train[k_indices]
        
        if self.weights == 'uniform':
            # 多数投票
            counter = Counter(k_labels)
            return counter.most_common(1)[0][0]
        elif self.weights == 'distance':
            # 距离加权投票
            weight_sum = {}
            for label, dist in zip(k_labels, k_distances):
                w = 1.0 / (dist + 1e-10)  # 避免除零
                weight_sum[label] = weight_sum.get(label, 0) + w
            return max(weight_sum, key=weight_sum.get)
    
    def predict(self, X):
        """批量预测"""
        return np.array([self.predict_one(x) for x in X])

9.2 使用 sklearn 的实现

from sklearn.neighbors import KNeighborsClassifier
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import Pipeline
from sklearn.model_selection import GridSearchCV

# 构建 pipeline
pipeline = Pipeline([
    ('scaler', StandardScaler()),
    ('knn', KNeighborsClassifier())
])

# 网格搜索
param_grid = {
    'knn__n_neighbors': [3, 5, 7, 9, 11],
    'knn__weights': ['uniform', 'distance'],
    'knn__metric': ['euclidean', 'manhattan', 'cosine']
}

grid_search = GridSearchCV(
    pipeline, param_grid, cv=5, scoring='accuracy'
)
grid_search.fit(X_train, y_train)

print(f"Best params: {grid_search.best_params_}")
print(f"Best score: {grid_search.best_score_:.4f}")

十、面试高频问题

Q1：k-NN 是惰性学习，这意味着什么？与急切学习（eager learning）有何区别？

惰性学习（lazy learning）意味着 k-NN 在”训练”阶段不做任何计算，仅简单地存储所有训练样本。实际的”工作”——计算距离、排序、投票——全部延迟到预测时才进行。

对比：

惰性学习（k-NN、局部加权回归）：训练 O(1)，预测 O(Nd)，适合需要快速适应新数据的场景
急切学习（线性回归、决策树、神经网络）：训练可能需要较长时间，但预测很快

在需要频繁更新的在线系统中（新数据不断到达），惰性学习有其优势：不需要重新训练模型，只需将新数据加入存储。但代价是每次预测都可能非常慢。

Q2：为什么要将特征归一化？如果忘记归一化会有什么后果？

k-NN 依赖距离度量，而距离度量对特征尺度敏感。举个具体例子：

假设有两个特征：年龄（范围 0-100）和年收入（范围 0-1000000）。欧氏距离计算时，年收入差 10000 元对距离的贡献远大于年龄差 20 岁（$10000^2$ vs $20^2$），导致”年龄”这个特征实际上被忽略了。

正确的做法是在计算距离前将各特征缩放到可比范围，如 $[0, 1]$ 或均值为 0 方差为 1。

Q3：k-d 树和球树在什么条件下会退化为 O(N) 搜索？为什么？

k-d 树在以下情况会退化：

维度过高（$d > 20$）：高维空间中超矩形剪枝很难生效，大量节点需要回溯
数据分布极端：当数据几乎都在某个方向聚集时，维度划分不均匀

球树退化条件类似但比 k-d 树稍好，因为它用超球而非轴对齐超矩形，对高维数据的适应性更强，但本质上仍受维度灾难的制约。

原因：高维空间中，两点间距离趋于相等，任何划分策略都无法有效地区分”远”和”近”，因此几乎所有剪枝条件都判定为”可能更近”，导致必须访问大量节点。

Q4：加权 k-NN 中的权重如何选择？反距离权重和高斯核权重各有什么优缺点？

反距离权重 $w = 1/d$：简单直接，但 $d \to 0$ 时权重趋向无穷，需要加 epsilon 防止除零。对非常近的点极其敏感。
反距离平方 $w = 1/d^2$：更强调近邻的影响，对噪声更敏感。
高斯核 $w = \exp(-d^2/2\sigma^2)$：权重上限为 1，比较稳定。但需要额外调节带宽参数 $\sigma$。

实践中最常用的是反距离权重（$1/d$），效果通常足够好且无需调参。如果使用高斯核，可将 $\sigma$ 设为 k 个邻居中距离的中位数。

Q5：如何处理样本不平衡问题在 k-NN 中的影响？

k-NN 对类别不平衡比较敏感：多数类的样本更容易出现在 k 个最近邻中。解决方法：

距离加权：让每个邻居的投票权重与其距离成反比，这样即使多数类邻居多，如果它们的距离很远，权重也会被稀释
调整 k 值：增大 k 有助于平滑，但可能过度平滑少数类信号；需要通过交叉验证选择
过采样/欠采样：使用 SMOTE 等合成少数类样本，或随机欠采样多数类
加权投票：给少数类更高的先验投票权重
使用距离剪裁：限定只考虑固定半径内的邻居，而非固定 k 个邻居

十一、总结

k 近邻法是最基础的机器学习算法之一。它直观、无需训练、理论简单，并且在许多实际问题上表现不俗。本文从 k-NN 的三要素（距离度量、k 值选择、分类决策规则）出发，系统讨论了其原理、实现细节和优化方法。

k-NN 的核心思想——“相似的样本落在相近的位置”——看似朴素，却蕴含着非参数统计推断的深刻洞见。虽然在高维数据和大型数据集上 k-NN 暴露出效率问题，但通过 k-d 树、球树、LSH 等数据结构和技术，它在许多实际场景中仍然是一个有力且可靠的工具。

在学习更复杂的机器学习算法之前，透彻理解 k-NN 能帮助我们建立对”距离”、”近邻”、”偏差-方差权衡”等基本概念的直觉。这些概念将贯穿我们后续所有的统计学习旅程。

参考文献：

Cover, T., & Hart, P. (1967). Nearest neighbor pattern classification. IEEE Transactions on Information Theory, 13(1), 21-27.
李航. (2019). 《统计学习方法》（第2版）. 第3章.
Bentley, J. L. (1975). Multidimensional binary search trees used for associative searching. Communications of the ACM, 18(9), 509-517.
Omohundro, S. M. (1989). Five balltree construction algorithms.
Indyk, P., & Motwani, R. (1998). Approximate nearest neighbors: towards removing the curse of dimensionality. STOC ‘98.