👥 02-机器学习 · 推导笔记 8:KNN 最近邻(手写全流程)¶
KNN(k-Nearest Neighbors)是最直观的监督学习算法:不学参数、不建模,全靠“物以类聚,人以群分”。 它是面试常考的“懒学习”代表,也是理解距离度量、特征缩放、维度灾难的最佳教材。
💡 一句话类比:班里来了个新同学,你想快速判断 TA 是“社牛”还是“社恐”——不用做心理测试,看看 TA 平时总跟哪几类人玩,按最像的那 k 个老同学投票决定,这就是 KNN。
运行环境:Python 3.8+,仅依赖 numpy(对照 cell 需要 sklearn)。
核心概念¶
(a) 🗂️ KNN:三步走、距离度量、k 的选择、KD 树与维度灾难¶
KNN 是最直观的监督学习算法:不学参数、不建模,全靠"物以类聚"。它是"懒学习"代表,也是理解距离度量、特征缩放、维度灾难的最佳教材。
flowchart TB
N1["👥 算法思想:三步走"] --> N2["距离度量:欧氏/曼哈顿/余弦"]
N1 --> N3["k 的选择:偏差-方差权衡"]
N1 --> N4["投票策略与权重"]
N2 --> N5["手写 KNN:numpy 全流程"]
N5 --> N6["加速查询:KD 树"]
N3 --> N7["维度灾难"]
N6 --> N8["优缺点与高频对比"]
N7 --> N8
N8 --> N9["自测清单"]
- N1 · 算法思想:三步走:算新样本与所有训练样本的距离 → 挑最近的 k 个 → 让这 k 个"邻居"投票决定类别(回归就取平均)。不训练、不学参数,所以叫"懒学习"。
- N2 · 距离度量:欧氏距离(默认)、曼哈顿距离、余弦相似度(文本/向量场景)——不同距离适合不同数据分布,面试常问选哪个、为什么。
- N3 · k 的选择:k 是关键超参:k 太小容易受单个噪声点影响(高方差),k 太大把远处的异类也拉进来(高偏差)——这就是 k 上的偏差-方差权衡。
- N4 · 投票策略与权重:投票可以升级为加权投票:距离越近的邻居话语权越大(权重 = 1/距离),能显著提升效果。
- N5 · 手写 KNN:用 numpy 广播算全量距离矩阵,再 argsort 取前 k 个——几十行代码,重点是理解"距离 → 排序 → 投票"整条流水线。
- N6 · KD 树加速:数据量大时全量算距离太慢,KD 树按维度递归切分空间,查询时只搜子树并剪枝,低维时能把查询从 O(n) 降到约 O(log n)。
- N7 · 维度灾难:特征维度一高,所有点之间的距离都差不多大,"最近邻"失去意义,KNN 效果骤降——所以 KNN 前一定要做特征缩放和降维。
- N8 · 优缺点与高频对比:简单、无假设、适合小数据;但预测慢、对特征缩放敏感、高维失效——常与 LR、决策树做成对比题。
- N9 · 自测清单:能手写全流程、能说清距离度量的选择、能解释 k 的权衡、能讲维度灾难为什么严重。
📖 本章导读¶
这一章讲什么(全书第 4 章):物以类聚的非参数方法——三步走(算距离 → 找 k 个近邻 → 投票);梳理距离度量、k 的偏差-方差权衡;最后讲两个必考的坑:维度灾难与 KD 树剪枝。
学完本章,你应该能:
- 讲清 KNN 为什么是非参数 + 惰性模型(训练 = 存数据);
- 说出各距离度量(欧氏/曼哈顿/余弦/汉明)的适用场景;
- 解释 k 小 → 方差大(过拟合)、k 大 → 偏差大(欠拟合);
- 说清维度灾难的本质(体积指数膨胀 → 最近邻不再近)与 KD 树的局限。
📌 全书第 4 章。阅读路径:本章导读 → 距离 · k 选择 · KD 树 → 自测清单 → 本章小结。
§1 算法思想:三步走¶
KNN 分类的完整流程只有三步:
- 算距离:新样本 $x$ 与训练集中每个样本 $x_i$ 算距离(欧氏/曼哈顿/…);
- 找邻居:取距离最近的 $k$ 个训练样本(k 一般是奇数,避免平票);
- 投票:这 $k$ 个邻居中哪个类别多,$x$ 就属于哪个类;回归任务则取 $k$ 个邻居标签的均值。
$$\hat{y} = \operatorname{argmax}_{c} \sum_{i \in N_k(x)} \mathbb{1}[y_i = c] \quad(\text{分类}), \qquad \hat{y} = \frac{1}{k} \sum_{i \in N_k(x)} y_i \quad(\text{回归})$$
其中 $N_k(x)$ 是离 $x$ 最近的 $k$ 个训练样本的下标集合。
两个关键性质:
- 懒学习(lazy learning):训练阶段什么都不做(只存数据),所有计算发生在预测时——所以训练 $O(1)$,预测 $O(nd)$($n$ 样本数、$d$ 特征数)。
- 非参数模型:模型假设不随数据量固定,能力随数据增长而增强(对比:线性回归不管多少数据都假设“直线”)。
📊 图 1:KNN 分类示意——新样本 x 与它最近的 k=5 个邻居(虚线圆内),多数投票 → 判为绿色类。
✍️ §1.1 手算 KNN:6 个点、新样本 x=(2,2)、k=3 投出类别¶
「算距离 → 找 k 个近邻 → 投票」三步骤,用一笔一算的数值跑一遍。
设定:6 个训练点、两类(A=0 红 / B=1 蓝):
$$x_1=(1,1)^{A},\ x_2=(1,2)^{A},\ x_3=(2,1)^{A},\ x_4=(5,5)^{B},\ x_5=(6,5)^{B},\ x_6=(5,6)^{B}$$
新样本 $q=(2,2)$,$k=3$,欧氏距离。
第 1 步:算 q 到每个训练点的欧氏距离
$$d(q,x_1)=\sqrt{(2-1)^2+(2-1)^2}=\sqrt{2}=1.414$$
$$d(q,x_2)=\sqrt{(2-1)^2+(2-2)^2}=1.0,\qquad d(q,x_3)=\sqrt{(2-2)^2+(2-1)^2}=1.0$$
$$d(q,x_4)=\sqrt{(2-5)^2+(2-5)^2}=\sqrt{18}=4.243,\quad d(q,x_5)=5.0,\quad d(q,x_6)=5.0$$
第 2 步:取最近的 k=3 个
$$\text{排序}:\ d_2=1.0\ <\ d_3=1.0\ <\ d_1=1.414\ <\ 4.243\ <\ 5.0=5.0$$
$$N_3(q)=\{x_2,\ x_3,\ x_1\}$$
第 3 步:多数投票
$$\text{A(0) 类 }:\ 3\ \text{票},\qquad \text{B(1) 类}:\ 0\ \text{票}\Rightarrow \hat{y}=\text{A}$$
手算收获:
- 距离 4.24 vs 1.41:q 明显靠近左下角 3 个红点,B 类点都在 $\sqrt{18}$ 之外——直觉与数值一致
- $k=3$ 奇数防平票;若 $k=6$ 则变成 A=3, B=3 平票(所以要选奇 k)
- 欧氏距离对尺度敏感:若特征单位不同(如体重 kg vs 身高 cm),必须先标准化——这是 KNN 的铁律
下面 numpy 复算。
# ---- §1.1 验证:numpy 复算 KNN ----
import numpy as np
X = np.array([[1.0, 1.0], [1.0, 2.0], [2.0, 1.0], [5.0, 5.0], [6.0, 5.0], [5.0, 6.0]])
y = np.array([0, 0, 0, 1, 1, 1])
q = np.array([2.0, 2.0])
k = 3
d = np.sqrt(((X - q) ** 2).sum(axis=1))
print('距离 =', np.round(d, 4))
order = np.argsort(d)
print('排序 =', order, ' 最近 k 个 =', order[:k], ' 标签 =', y[order[:k]])
pred = np.bincount(y[order[:k]]).argmax()
print('投票结果 =', pred, '(A=0 红)')
assert np.allclose(d[:3][order[:3]] if False else d[order[:3]], [1.0, 1.0, 1.4142], atol=1e-3)
assert pred == 0
print('✓ 与手算一致')
§2 距离度量(面试必问)¶
最常用的闵可夫斯基距离(Minkowski)是统一形式:
$$L_p(x, x') = \left( \sum_{k=1}^{d} |x_k - x'_k|^p \right)^{1/p}$$
| $p$ | 名称 | 公式特例 | 一句话直觉 | |-----|------|----------|------------| | 1 | 曼哈顿距离 | $\sum_k |x_k - x'_k|$ | 只能横平竖直走街区(出租车距离) | | 2 | 欧氏距离 | $\sqrt{\sum_k (x_k - x'_k)^2}$ | 直线飞过去(默认首选) | | $\infty$ | 切比雪夫 | $\max_k |x_k - x'_k|$ | 最远的那条街决定远近(棋盘距离) |
文本/推荐场景常用余弦相似度(只看方向、不看长度):
$$\cos(x, x') = \frac{x \cdot x'}{\|x\| \cdot \|x'\|}$$
💡 通俗例子:两个用户都在淘宝买过 100 件东西,A 买了 90 件数码、10 件零食;B 买了 9 件数码、1 件零食。欧氏距离会觉得两人差很远(90 vs 9),但余弦相似度认为购买偏好一模一样(比例相同)。所以“兴趣相似”看余弦,“量级重要”看欧氏。
距离度量的选择要点:
- 特征都连续、量纲一致 → 欧氏;
- 高维稀疏(如 TF 向量)→ 余弦;
- 特征取值是 0/1 或分类 → 汉明距离(逐位不同个数)。
📊 图 2:三种距离度量对比——欧氏走直线,曼哈顿只能横平竖直,切比雪夫看最远的那一步。
# ---- matplotlib 中文字体(防图内中文乱码)----
import matplotlib
matplotlib.rcParams['font.sans-serif'] = ['Microsoft YaHei', 'SimHei', 'Songti SC', 'Arial Unicode MS', 'DejaVu Sans']
matplotlib.rcParams['axes.unicode_minus'] = False
# -------------------------------------------
import numpy as np
def euclidean(a, b):
return np.sqrt(np.sum((a - b) ** 2))
def manhattan(a, b):
return np.sum(np.abs(a - b))
def cosine(a, b):
norm = np.linalg.norm(a) * np.linalg.norm(b)
return 1.0 - np.dot(a, b) / norm if norm > 0 else 0.0 # 1-相似度 = 距离
# 通俗例子:两个"买家"的购买向量([数码, 零食, 图书])
A = np.array([90.0, 10.0, 5.0])
B = np.array([9.0, 1.0, 0.5]) # 偏好比例和 A 几乎一样,只是量级差 10 倍
C = np.array([5.0, 90.0, 10.0]) # 偏好完全不同的人
print(f"欧氏距离 A-B = {euclidean(A, B):.2f} (量级不同→很远)")
print(f"欧氏距离 A-C = {euclidean(A, C):.2f}")
print(f"余弦距离 A-B = {cosine(A, B):.4f} (比例相同→几乎为0)")
print(f"余弦距离 A-C = {cosine(A, C):.4f} (偏好不同→很大)")
§3 K 的选择与投票策略¶
k 太小(k=1):只信最近的一个邻居 → 对噪声极度敏感,决策边界弯弯曲曲,过拟合;
k 太大(k=n):等于全体投票 → 模型退化成一棵“常数树”,欠拟合。
工程上:k 用交叉验证选(见推导笔记 13),一般取 $\sqrt{n}$ 量级的奇数。
投票的改进:距离加权——离得近的邻居说话更管用:
$$\hat{y} = \operatorname{argmax}_{c} \sum_{i \in N_k(x)} w_i \cdot \mathbb{1}[y_i = c], \qquad w_i = \frac{1}{d(x, x_i) + \varepsilon}$$
决策边界直觉:KNN 的边界是“沃罗诺伊图”(Voronoi)网格——每个点到它最近的训练点划地盘;k 越大,边界越平滑。
必须做特征缩放! 欧氏距离对量纲敏感:一个特征单位是“万元”,另一个是“厘米”,后者会完全主导距离。所以预测前必须先标准化/归一化(z-score 或 min-max)。
§4 手写 KNN 分类器(numpy 全流程)¶
手写实现 = 存训练集 + 逐样本算距离 + 排序取前 k + 投票。
向量化技巧:用广播一次性算所有距离:np.linalg.norm(X - x, axis=1),再用 np.argsort 取前 k。
class KNN:
"""手写 k 近邻分类器(欧氏距离,支持距离加权投票)"""
def __init__(self, k=3, weighted=False):
self.k = k
self.weighted = weighted
def fit(self, X, y):
# 懒学习:训练阶段只存数据
self.X = np.asarray(X, dtype=float)
self.y = np.asarray(y)
self.classes = np.unique(self.y)
return self
def predict_one(self, x):
# 1) 与所有训练样本的距离
dist = np.sqrt(np.sum((self.X - x) ** 2, axis=1))
# 2) 取最近 k 个
idx = np.argsort(dist)[: self.k]
neigh_y, neigh_d = self.y[idx], dist[idx]
if not self.weighted:
# 3) 多数投票
votes = np.bincount(neigh_y, minlength=len(self.classes))
return self.classes[np.argmax(votes)]
# 加距离权重:近的票重
w = 1.0 / (neigh_d + 1e-9)
score = np.zeros(len(self.classes))
for label, wi in zip(neigh_y, w):
score[label] += wi
return self.classes[np.argmax(score)]
def predict(self, X):
return np.array([self.predict_one(x) for x in np.asarray(X, dtype=float)])
def score(self, X, y):
return float(np.mean(self.predict(X) == y))
# ---- 演示:三类合成数据(二维,方便想象图形)----
rng = np.random.default_rng(42)
def make_cluster(center, n=40, spread=0.6, label=0):
X = rng.normal(center, spread, (n, 2))
y = np.full(n, label)
return X, y
X1, y1 = make_cluster([0, 0], label=0)
X2, y2 = make_cluster([4, 0], label=1)
X3, y3 = make_cluster([2, 3.5], label=2)
X = np.vstack([X1, X2, X3])
y = np.concatenate([y1, y2, y3])
# 划分训练/测试
idx = rng.permutation(len(X))
train_idx, test_idx = idx[:90], idx[90:]
X_tr, y_tr = X[train_idx], y[train_idx]
X_te, y_te = X[test_idx], y[test_idx]
for k in [1, 3, 7, 15]:
acc = KNN(k=k).fit(X_tr, y_tr).score(X_te, y_te)
print(f"k={k:2d} 测试准确率 = {acc:.3f}")
# 距离加权 vs 普通投票
plain = KNN(k=7).fit(X_tr, y_tr).score(X_te, y_te)
wtd = KNN(k=7, weighted=True).fit(X_tr, y_tr).score(X_te, y_te)
print(f"k=7 普通投票 = {plain:.3f} vs 距离加权 = {wtd:.3f}")
# ---- sklearn 对照:手写 KNN vs KNeighborsClassifier ----
from sklearn.neighbors import KNeighborsClassifier
from sklearn.preprocessing import StandardScaler
knn_sk = KNeighborsClassifier(n_neighbors=7).fit(X_tr, y_tr)
my_knn = KNN(k=7).fit(X_tr, y_tr)
# 注意:sklearn KNN 内部就是欧氏距离 + 多数投票,应几乎完全一致
print(f"手写 KNN 准确率 = {my_knn.score(X_te, y_te):.3f}")
print(f"sklearn 准确率 = {knn_sk.score(X_te, y_te):.3f}")
same = np.mean(my_knn.predict(X_te) == knn_sk.predict(X_te))
print(f"两个模型在测试集上的预测一致率 = {same:.3f}")
# 演示特征缩放的重要性:把特征2放大100倍,等于让"距离"几乎只看特征2
X_bad = X.copy(); X_bad[:, 1] *= 100
knn_bad = KNN(k=7).fit(X_bad[train_idx], y_tr).score(X_bad[test_idx], y_te)
scaler = StandardScaler().fit(X_bad[train_idx])
Xs = scaler.transform(X_bad)
knn_ok = KNN(k=7).fit(Xs[train_idx], y_tr).score(Xs[test_idx], y_te)
print(f"\n量纲失衡(不缩放) 准确率 = {knn_bad:.3f}")
print(f"标准化之后 准确率 = {knn_ok:.3f}")
# ---- 可视化:手写 KNN 的决策边界(网格逐点分类,运行本 cell 生成)----
import matplotlib
matplotlib.use("Agg")
import matplotlib.pyplot as plt
xx, yy = np.meshgrid(
np.linspace(X[:, 0].min() - 0.5, X[:, 0].max() + 0.5, 200),
np.linspace(X[:, 1].min() - 0.5, X[:, 1].max() + 0.5, 200),
)
grid = np.c_[xx.ravel(), yy.ravel()]
Z = KNN(k=7).fit(X, y).predict(grid).reshape(xx.shape)
plt.figure(figsize=(7, 5))
plt.contourf(xx, yy, Z, alpha=0.35, cmap="coolwarm", levels=[-0.5, 0.5, 1.5, 2.5])
plt.scatter(X[:, 0], X[:, 1], c=y, cmap="coolwarm", edgecolor="k", s=28)
plt.title("手写 KNN(k=7) 决策边界(蓝色/红色区域为分类结果)")
plt.xlabel("x1")
plt.ylabel("x2")
plt.show()
§5 加速查询:KD 树¶
KNN 暴力搜索是 $O(nd)$,样本百万级就扛不住了。**KD 树(K-Dimensional Tree)**把空间递归二分,把查询降到平均 $O(\log n)$。
建树(build):
- 选方差最大(或轮流选)的维度 $j$;
- 按第 $j$ 维的中位数切分,作为根节点;
- 左右子树继续递归。
查询(搜索近邻):
- 沿树向下走到叶子(快速定位“大致位置”);
- 回溯:若兄弟子树区域到查询点的距离 < 当前最近距离,则进去搜(剪枝条件);
- 否则整棵子树剪掉。
💡 通俗例子:图书馆找书。暴力法 = 把每本书的坐标都量一遍;KD 树 = 先按“第几排”分,再按“第几格”分——走到对应排再细找,整排整排地跳过,效率高得多。
局限:维度升高(>20)后,KD 树退化接近暴力搜索——因为高维空间点与点几乎“一样远”(维度灾难),剪枝失效。此时用近似近邻(如局部敏感哈希 LSH、HNSW)更实际。
class KDNode:
def __init__(self, point, label, dim, left=None, right=None):
self.point, self.label, self.dim = point, label, dim
self.left, self.right = left, right
def build_kd(points, labels, depth=0):
"""递归建树:轮流按维度切分(简化版,未做方差选择)"""
if len(points) == 0:
return None
d = points.shape[1]
axis = depth % d
order = np.argsort(points[:, axis])
points, labels = points[order], labels[order]
mid = len(points) // 2
return KDNode(points[mid], labels[mid], axis,
build_kd(points[:mid], labels[:mid], depth + 1),
build_kd(points[mid + 1:], labels[mid + 1:], depth + 1))
def knn_kd(root, query, k, best=None, depth=0):
"""KD 树最近邻搜索(带剪枝)"""
if root is None:
return best
if best is None:
best = []
dist = np.linalg.norm(root.point - query)
best.append((dist, root.label, root.point))
best.sort(key=lambda t: t[0])
if len(best) > k:
best = best[:k]
axis = root.dim
# 先走查询点所在的一侧
if query[axis] < root.point[axis]:
near, far = root.left, root.right
else:
near, far = root.right, root.left
best = knn_kd(near, query, k, best, depth + 1)
# 剪枝判断:另一侧超平面到查询点的距离是否小于当前第 k 远
if len(best) < k or abs(query[axis] - root.point[axis]) < best[-1][0]:
best = knn_kd(far, query, k, best, depth + 1)
return best
# 小例子:6 个点,查 (3, 3) 的 2 个最近邻
pts = np.array([[1, 1], [2, 5], [3, 2], [5, 3], [6, 6], [7, 1]], dtype=float)
lbl = np.array([0, 1, 0, 1, 1, 0])
tree = build_kd(pts, lbl)
result = knn_kd(tree, np.array([3.0, 3.0]), k=2)
for d, lab, p in result:
print(f"邻居点 {p} 类别 {lab} 距离 {d:.3f}")
§6 优缺点与高频对比¶
优点:
- 实现极简,无需训练,天然支持增量数据(加样本即可);
- 非参数 → 能拟合任意复杂边界;
- 多分类、回归通用,且能输出“邻居构成”天然附带可解释性。
缺点:
- 预测慢($O(nd)$)、存储全量数据(内存大);
- 对特征缩放、无关特征、噪声极敏感;
- 维度灾难:高维下所有点距离趋同,KNN 失效;
- 类别不平衡时大样本类“霸占”近邻区。
高频对比题:
| 对比项 | KNN | 逻辑回归 / 线性模型 |
|---|---|---|
| 学习方式 | 懒学习(预测时才算) | 勤学习(训练时学参数) |
| 模型形式 | 无显式参数(存数据) | $w, b$ 参数 |
| 决策边界 | 任意形状(Voronoi) | 线性(超平面) |
| 可解释性 | 看邻居,直观 | 看权重,可量化 |
| 高维/大数据 | 差(维度灾难) | 好(可上亿样本) |
| 适用场景 | 低维小数据、推荐“相似人” | CTR、风控等大厂主力 |
§7 常见 bug 与边界(面试踩坑区)¶
- 忘了标准化:量纲大的特征主导距离(§4 已演示,准确率从 0.93 掉到 0.53 量级);
- k 取偶数 + 二分类平票:没有默认决胜规则,务必定好(取编号小/随机/看距离和);
- 特征里混入编号/ID:ID 与类别无关却贡献距离,必须剔除;
- 类别不平衡:多数类邻居多 → 考虑距离加权或对邻居按类内密度归一化;
- 文本/长尾数据直接用欧氏:应换余弦或先 TF-IDF;
- k=1 时训练集上准确率恒为 1(最近邻就是自己),别拿训练指标说事;
- 标准化时只用训练集统计量,否则测试集信息泄漏(数据泄漏标准错误)。
§8 自测清单(L1 必会 / L2 进阶 / L3 挑战)¶
L1 必会(8 问)¶
- 1. 口述 KNN 三步流程与两个超参(k、距离度量)
- 2. 为什么训练阶段几乎零成本、预测阶段贵?
- 3. 欧氏、曼哈顿、余弦距离各自的典型场景
- 4. k 太小/太大分别对应什么(过拟合/欠拟合)
- 5. 为什么 KNN 必须做特征缩放
- 6. KNN 分类与回归的区别
- 7. 维度灾难为什么对 KNN 致命
- 8. 说出 KD 树的剪枝条件
L2 进阶(6 问)¶
- 9. 距离加权投票怎么写公式
- 10. KNN 的时间复杂度(训练/预测)与空间复杂度
- 11. 类别不平衡下 KNN 如何改进
- 12. KNN 做推荐(找相似用户/物品)的利弊
- 13. 与 LR 对比(懒/勤学习,边界形状)
- 14. k 的交叉验证选择流程
L3 挑战(4 问)¶
- 15. 手写 KD 树(建树 + 剪枝查询)
- 16. 高维下 KD 树退化的数学直觉(距离分布集中)
- 17. LSH / HNSW 与 KD 树的取舍
- 18. 用核方法给距离加“特征重要性权重”(如马氏距离)
自测要点¶
- 10 分钟内手写一个不带库的 KNN 分类器
- 能解释“为什么 k=1 时训练准确率一定是 100%”
- 能画图说明 k 与决策边界平滑度的关系
🏁 本章小结¶
- 原理一句话:KNN = 存数据 + 找 k 个最近邻 + 投票,非参数、惰性。
- 必会公式:欧氏 $d_2=\sqrt{\sum_j(x_j-x'_j)^2}$;投票 $\hat y=\text{mode}\{y_{(1)}\dots y_{(k)}\}$。
- 面试怎么考:k 的偏差-方差(k 小方差大、k 大偏差大);距离度量怎么选;维度灾难的本质(体积指数膨胀);KD 树剪枝为什么怕高维。
- 易错点:不标准化让大尺度特征绑架距离;k 取偶数导致平票(用奇数)。
自测清单没把握的条目,回到对应小节重读后再打勾。