第3章：k近邻法（k-Nearest Neighbors）

一、导读

1.1 本章学习目标

第3章介绍k近邻法（k-Nearest Neighbors, kNN）——一种基于实例的学习方法。与前面介绍的感知机不同，kNN没有显式的训练过程：它"记住"所有训练数据，在预测时找到与待预测点最近的k个训练样本，通过多数表决做出决策。这种"懒惰学习"（Lazy Learning）的思想在机器学习中独树一帜。

本章的核心学习目标包括：

理解kNN的三要素：距离度量、k值选择、分类决策规则
掌握不同距离度量的特点：欧氏距离、曼哈顿距离、闵可夫斯基距离各自的适用场景
理解k值选择的影响：k值过小导致过拟合，k值过大导致欠拟合
掌握kd树的原理：如何用树形结构加速kNN的搜索过程
理解kNN的优缺点：简单直观但计算量大
实现kNN算法：包括暴力搜索和kd树搜索两种实现

1.2 为什么本章如此重要

kNN是机器学习中最直观的算法之一——"近朱者赤，近墨者黑"。它不需要训练过程，不需要参数估计，甚至不需要对数据做任何假设。这种"非参数"方法的灵活性使其在许多实际问题中表现出色。

更重要的是，kNN揭示了机器学习中一个核心权衡：训练成本和预测成本之间的权衡。kNN几乎不需要训练时间，但预测时需要与所有训练样本计算距离。这种权衡在实际系统中至关重要。

1.3 核心问题引导

在阅读本章时，请带着以下问题思考：

kNN的"训练"过程是什么？为什么说它是"懒惰学习"？

不同的距离度量对结果有什么影响？在什么场景下应该使用不同的距离？

k值的选择如何影响模型性能？如何选择最优的k值？

暴力搜索的时间复杂度是多少？为什么需要kd树？

kd树是如何加速搜索的？它的时间复杂度是多少？

kNN在什么情况下表现好？什么情况下表现差？

二、核心概念详解

3.1 kNN模型：三要素

kNN模型的核心思想非常直观：给定一个测试样本，找到训练集中与它最近的k个样本，这k个样本中占多数的类别就是测试样本的预测类别。

kNN模型由三个要素决定：

距离度量：如何定义"近"

k值：选择多少个邻居

分类决策规则：如何从邻居的类别做出决策

3.2 距离度量

3.2.1 闵可夫斯基距离

闵可夫斯基距离（Minkowski Distance）是一族距离度量的统称：

L_p(x, y) = (Σ_i |x_i - y_i|^p)^(1/p)

p=1：曼哈顿距离（Manhattan Distance），L_1 = Σ|x_i - y_i|
p=2：欧氏距离（Euclidean Distance），L_2 = √(Σ(x_i - y_i)^2)
p=∞：切比雪夫距离，L_∞ = max|x_i - y_i|

python

import numpy as np

def minkowski_distance(x, y, p=2):
    """闵可夫斯基距离"""
    return np.sum(np.abs(x - y) ** p) ** (1 / p)

def euclidean_distance(x, y):
    """欧氏距离 (p=2)"""
    return np.sqrt(np.sum((x - y) ** 2))

def manhattan_distance(x, y):
    """曼哈顿距离 (p=1)"""
    return np.sum(np.abs(x - y))

def chebyshev_distance(x, y):
    """切比雪夫距离 (p=∞)"""
    return np.max(np.abs(x - y))

# 示例
a = np.array([1, 2, 3])
b = np.array([4, 6, 3])

print(f"欧氏距离: {euclidean_distance(a, b):.4f}")
print(f"曼哈顿距离: {manhattan_distance(a, b):.4f}")
print(f"切比雪夫距离: {chebyshev_distance(a, b):.4f}")
print(f"闵可夫斯基距离(p=3): {minkowski_distance(a, b, p=3):.4f}")

3.2.2 距离度量的选择

不同距离度量适用于不同的场景：

欧氏距离：最常用的距离度量，适用于连续特征，对大差异敏感
曼哈顿距离：适用于网格状结构（如城市街区），对异常值更鲁棒
余弦相似度：适用于文本、图像等高维稀疏数据，关注方向而非大小

python

import numpy as np

def cosine_similarity(x, y):
    """余弦相似度"""
    return np.dot(x, y) / (np.linalg.norm(x) * np.linalg.norm(y))

def cosine_distance(x, y):
    """余弦距离"""
    return 1 - cosine_similarity(x, y)

# 文本相似度示例（词频向量）
doc1 = np.array([5, 3, 0, 1, 2])  # 文档1的词频
doc2 = np.array([4, 2, 1, 0, 3])  # 文档2的词频
doc3 = np.array([50, 30, 0, 10, 20])  # 文档3（文档1的10倍）

print(f"doc1 vs doc2 欧氏距离: {euclidean_distance(doc1, doc2):.4f}")
print(f"doc1 vs doc3 欧氏距离: {euclidean_distance(doc1, doc3):.4f}")
print(f"doc1 vs doc2 余弦距离: {cosine_distance(doc1, doc2):.4f}")
print(f"doc1 vs doc3 余弦距离: {cosine_distance(doc1, doc3):.4f}")
print("余弦相似度认为doc1和doc3完全相同（方向一致）")

3.3 k值选择

k值是kNN中最重要的超参数。k值的选择直接影响模型的性能：

k值过小（如k=1）：模型复杂，容易过拟合，对噪声敏感
k值过大（如k=N）：模型简单，容易欠拟合，决策边界模糊
k值适中：在偏差和方差之间取得平衡

经验法则：

二分类问题：k取奇数，避免平票
k通常取 √N 附近（N为训练样本数）
通过交叉验证选择最优k值

python

import numpy as np
from collections import Counter

class KNN:
    def __init__(self, k=3, distance_func=None):
        self.k = k
        self.distance_func = distance_func or euclidean_distance
    
    def fit(self, X, y):
        self.X_train = X
        self.y_train = y
        return self
    
    def _predict_one(self, x):
        distances = np.array([self.distance_func(x, xi) for xi in self.X_train])
        k_indices = np.argsort(distances)[:self.k]
        k_labels = self.y_train[k_indices]
        return Counter(k_labels).most_common(1)[0][0]
    
    def predict(self, X):
        return np.array([self._predict_one(x) for x in X])
    
    def score(self, X, y):
        return np.mean(self.predict(X) == y)

# k值选择实验
np.random.seed(42)
from sklearn.datasets import make_classification

X, y = make_classification(n_samples=300, n_features=5, n_informative=3,
                           n_redundant=1, random_state=42)

# 划分训练集和测试集
split = 200
X_train, X_test = X[:split], X[split:]
y_train, y_test = y[:split], y[split:]

print(f"{'k值':>5} {'训练准确率':>12} {'测试准确率':>12}")
print("-" * 32)
for k in [1, 3, 5, 7, 10, 15, 20, 30, 50]:
    knn = KNN(k=k)
    knn.fit(X_train, y_train)
    train_acc = knn.score(X_train, y_train)
    test_acc = knn.score(X_test, y_test)
    print(f"{k:>5} {train_acc:>12.4f} {test_acc:>12.4f}")

3.4 分类决策规则

kNN最常用的分类决策规则是多数表决（Majority Voting）：k个邻居中出现最多的类别就是预测类别。

从概率角度理解，多数表决等价于选择使经验条件概率最大的类别：

P(Y=c_j | X=x) = (1/k) * Σ_{x_i ∈ N_k(x)} I(y_i = c_j)

其中 N_k(x) 是 x 的 k 个最近邻。

python

import numpy as np
from collections import Counter

def majority_voting(neighbor_labels):
    """多数表决"""
    return Counter(neighbor_labels).most_common(1)[0][0]

def weighted_voting(neighbor_labels, distances):
    """距离加权投票：距离越近权重越大"""
    weights = 1.0 / (distances + 1e-10)
    label_weights = {}
    for label, weight in zip(neighbor_labels, weights):
        label_weights[label] = label_weights.get(label, 0) + weight
    return max(label_weights, key=label_weights.get)

# 示例
labels = np.array([1, 1, 0, 0, 0])
dists = np.array([0.5, 0.8, 1.0, 1.2, 1.5])

print(f"多数表决: {majority_voting(labels)}")
print(f"加权投票: {weighted_voting(labels, dists)}")

3.5 kd树：加速kNN搜索

3.5.1 暴力搜索的问题

暴力搜索需要计算测试点与所有训练点的距离，时间复杂度为 O(N·d)，其中 N 是训练样本数，d 是特征维度。当 N 很大时，预测效率很低。

3.5.2 kd树的构建

kd树（kd-tree）是一种二叉树结构，每个节点代表一个超矩形区域。构建过程：

选择方差最大的维度作为分割维度

选择该维度的中位数作为分割点

递归地对左右子区域构建子树

python

import numpy as np

class KDNode:
    def __init__(self, point, label, axis, left=None, right=None):
        self.point = point
        self.label = label
        self.axis = axis
        self.left = left
        self.right = right

def build_kdtree(X, y, depth=0):
    """构建kd树"""
    if len(X) == 0:
        return None
    
    # 选择分割维度
    axis = depth % X.shape[1]
    
    # 按该维度排序
    sorted_idx = np.argsort(X[:, axis])
    median_idx = len(sorted_idx) // 2
    
    # 创建节点
    node = KDNode(
        point=X[sorted_idx[median_idx]],
        label=y[sorted_idx[median_idx]],
        axis=axis
    )
    
    # 递归构建左右子树
    node.left = build_kdtree(X[sorted_idx[:median_idx]], y[sorted_idx[:median_idx]], depth + 1)
    node.right = build_kdtree(X[sorted_idx[median_idx + 1:]], y[sorted_idx[median_idx + 1:]], depth + 1)
    
    return node

# 示例
X = np.array([[2, 3], [5, 4], [9, 6], [4, 7], [8, 1], [7, 2]])
y = np.array([0, 1, 1, 0, 1, 0])

tree = build_kdtree(X, y)

def print_tree(node, depth=0):
    if node is None:
        return
    print_tree(node.right, depth + 1)
    print("  " * depth + f"({node.point[0]}, {node.point[1]}) axis={node.axis} label={node.label}")
    print_tree(node.left, depth + 1)

print("kd树结构:")
print_tree(tree)

3.5.3 kd树的搜索

kd树搜索kNN的过程：

从根节点出发，根据分割维度向下搜索到叶节点

回溯到父节点，检查另一子树是否可能有更近的点

维护一个k个最近点的列表

python

import numpy as np

def search_knn(node, target, k, best=None, depth=0):
    """在kd树中搜索k个最近邻"""
    if node is None:
        return best
    
    if best is None:
        best = []
    
    # 计算当前节点到目标的距离
    dist = np.linalg.norm(node.point - target)
    
    # 更新最近邻列表
    best.append((dist, node.label, node.point))
    best.sort(key=lambda x: x[0])
    if len(best) > k:
        best = best[:k]
    
    # 决定搜索方向
    axis = node.axis
    if target[axis] < node.point[axis]:
        near, far = node.left, node.right
    else:
        near, far = node.right, node.left
    
    # 先搜索近侧
    best = search_knn(near, target, k, best, depth + 1)
    
    # 检查是否需要搜索远侧
    if len(best) < k or abs(target[axis] - node.point[axis]) < best[-1][0]:
        best = search_knn(far, target, k, best, depth + 1)
    
    return best

# 测试
target = np.array([3, 4.5])
neighbors = search_knn(tree, target, k=3)

print(f"\n目标点: {target}")
print("3个最近邻:")
for dist, label, point in neighbors:
    print(f"  点 {point}, 标签 {label}, 距离 {dist:.4f}")

3.6 kNN的优缺点

优点：

简单直观，易于实现和理解
不需要训练过程（懒惰学习）
对非线性数据有效
天然支持多分类

缺点：

预测时需要计算与所有训练样本的距离，计算量大
对高维数据效果差（维度灾难）
对特征尺度敏感，需要标准化
对不平衡数据敏感

三、实战案例

3.1 鸢尾花数据集上的kNN

python

import numpy as np
from sklearn.datasets import load_iris
from sklearn.model_selection import cross_val_score
from collections import Counter

class KNNClassifier:
    def __init__(self, k=3):
        self.k = k
    
    def fit(self, X, y):
        self.X_train = X
        self.y_train = y
    
    def predict(self, X):
        predictions = []
        for x in X:
            distances = np.sqrt(np.sum((self.X_train - x) ** 2, axis=1))
            k_indices = np.argsort(distances)[:self.k]
            k_labels = self.y_train[k_indices]
            predictions.append(Counter(k_labels).most_common(1)[0][0])
        return np.array(predictions)

# 加载数据
iris = load_iris()
X, y = iris.data, iris.target

# 标准化
X = (X - X.mean(axis=0)) / X.std(axis=0)

# 交叉验证选择最优k
print(f"{'k值':>5} {'交叉验证准确率':>15}")
print("-" * 22)
for k in [1, 3, 5, 7, 9, 11, 15]:
    knn = KNNClassifier(k=k)
    scores = cross_val_score(knn, X, y, cv=5, scoring='accuracy')
    print(f"{k:>5} {scores.mean():>15.4f}")

3.2 维度灾难的演示

python

import numpy as np

def curse_of_dimensionality():
    """演示维度灾难：高维空间中所有点之间的距离趋于相同"""
    np.random.seed(42)
    n_points = 1000
    
    print(f"{'维度':>5} {'最小距离':>12} {'最大距离':>12} {'距离比(max/min)':>18}")
    print("-" * 50)
    
    for dim in [2, 5, 10, 50, 100, 500]:
        X = np.random.randn(n_points, dim)
        
        # 计算所有点对之间的距离
        distances = []
        for i in range(min(n_points, 100)):
            for j in range(i + 1, min(n_points, 100)):
                distances.append(np.linalg.norm(X[i] - X[j]))
        
        distances = np.array(distances)
        ratio = distances.max() / distances.min()
        
        print(f"{dim:>5} {distances.min():>12.4f} {distances.max():>12.4f} {ratio:>18.4f}")
    
    print("\n维度越高，距离比越接近1，kNN越难区分近邻和远邻")

curse_of_dimensionality()

3.3 特征标准化的影响

python

import numpy as np
from collections import Counter

class KNN:
    def __init__(self, k=3):
        self.k = k
    
    def fit(self, X, y):
        self.X_train = X
        self.y_train = y
    
    def predict(self, X):
        predictions = []
        for x in X:
            distances = np.sqrt(np.sum((self.X_train - x) ** 2, axis=1))
            k_indices = np.argsort(distances)[:self.k]
            k_labels = self.y_train[k_indices]
            predictions.append(Counter(k_labels).most_common(1)[0][0])
        return np.array(predictions)

# 生成特征尺度不同的数据
np.random.seed(42)
X = np.column_stack([
    np.random.randn(200) * 0.1,     # 特征1：范围 [−0.3, 0.3]
    np.random.randn(200) * 100,     # 特征2：范围 [−300, 300]
])
w = np.array([3, 0.01])  # 特征1更重要
y = (X @ w > 0).astype(int)

# 不标准化
split = 150
knn = KNN(k=5)
knn.fit(X[:split], y[:split])
acc_no_std = np.mean(knn.predict(X[split:]) == y[split:])

# 标准化
X_mean = X[:split].mean(axis=0)
X_std = X[:split].std(axis=0)
X_scaled = (X - X_mean) / X_std

knn_std = KNN(k=5)
knn_std.fit(X_scaled[:split], y[:split])
acc_std = np.mean(knn_std.predict(X_scaled[split:]) == y[split:])

print(f"不标准化准确率: {acc_no_std:.4f}")
print(f"标准化后准确率: {acc_std:.4f}")
print("特征2的尺度远大于特征1，不标准化时特征2主导距离计算")

四、本章小结

第3章介绍了k近邻法（kNN）：

kNN的三要素：距离度量、k值、分类决策规则。三者共同决定模型的性能。

距离度量：欧氏距离最常用，但对高维数据效果差；余弦相似度适用于文本等高维稀疏数据。

k值选择：k值过小过拟合，k值过大欠拟合。通过交叉验证选择最优k值。

kd树：通过空间划分加速kNN搜索，将搜索复杂度从 O(N) 降低到 O(log N)。

维度灾难：高维空间中距离趋于相同，kNN在高维数据上效果差。

特征标准化：kNN对特征尺度敏感，使用前必须进行标准化。

kNN的核心启示是：简单的方法也可以很有效。在很多实际问题中，kNN的表现不亚于复杂的模型。同时，kNN也揭示了"懒惰学习"的思想——将计算推迟到预测时。

五、思考与练习

思考题

kNN是"懒惰学习"的代表。还有哪些"懒惰学习"的方法？它们与"急切学习"（Eager Learning）有什么本质区别？

余弦相似度和欧氏距离在什么场景下各更合适？能否给出直觉上的解释？

kd树的时间复杂度是多少？在什么情况下kd树会退化为暴力搜索？

维度灾难的根源是什么？如何缓解维度灾难对kNN的影响？

kNN能否用于回归问题？如何实现？

编程练习

从零实现kNN分类器，在鸢尾花数据集上用交叉验证选择最优k值。

实现kd树，对比暴力搜索和kd树搜索在不同数据量下的效率差异。

实现加权kNN（距离越近权重越大），对比与标准kNN的效果差异。