pyprobml 实战指南：基于样本的方法（Exemplar-based Methods）——KNN、核密度估计与核回归全解析

• 机器学习
• 深度学习

本指南围绕《Probabilistic Machine Learning》第 16 章 "Exemplar-based methods"（基于样本的方法）展开，梳理 pyprobml 仓库中与之对应的全部 Notebook 与源码脚本，覆盖 K 近邻分类、Voronoi 划分、维度灾难、核平滑、Parzen 窗密度估计以及 Nadaraya-Watson 核回归的完整实验复现。读完本文，你将掌握如何在本仓库中一键运行相关演示、理解每个实验的数学原理与实现细节，并能基于 sklearn / SciPy / NumPy 独立复现这些经典非参数方法。

第 16 章在 pyprobml 中的组织方式

pyprobml 仓库为书籍每一章维护了独立的 Notebook 目录，第 16 章的演示全部集中在 notebooks/book1/16/，目录下的 README.md 同时维护了「图号 ↔ Notebook ↔ 图文件」的映射表，这是快速定位每一章实验资源的标准入口。

该目录包含 7 个可直接运行的 Notebook：

| 文件 | 对应书籍图号 | 主题 | |--|--|--| | knn_voronoi_plot.ipynb | 图 16.1 | KNN 决策边界与 Voronoi 划分 | | knn_classify_demo.ipynb | 图 16.2 | 三分类 KNN 分类器演示 | | curse_dimensionality_plot.ipynb | 图 16.3 | 维度灾难 | | smoothingKernelPlot.ipynb | 图 16.8 | 常见平滑核函数 | | parzen_window_demo2.ipynb | 图 16.9 | Parzen 窗（核）密度估计 | | kernelRegressionDemo.ipynb | 图 16.10 | 核回归（Nadaraya-Watson） | | knn_demo.ipynb | 补充材料 | 基于 sklearn 的 KNN 分类器综合演示 |

其中图 16.4–16.7 在仓库中没有对应 Notebook，仅以书籍图文件形式存在于《Probabilistic Machine Learning》的 book1-figures 资源中，本文不展开。

这些 Notebook 大多脱胎于deprecated/scripts/目录下的同名 Python 脚本。脚本与 Notebook 互为印证：脚本是「可执行的最小单元」，Notebook 则在其基础上加入了可视化分步与交互式说明。例如 knn_demo.ipynb 的开头就明确注明其内容基于 deprecated/scripts/knn_classify_demo.py。

KNN 分类器：从数据生成到决策边界

数据准备

deprecated/scripts/knn_classify_demo.py 使用 sklearn 的make_blobs生成三团各向同性高斯簇作为分类数据：

from sklearn.neighbors import KNeighborsClassifier as KNN from sklearn.datasets import make_blobs X, y = make_blobs(n_samples=1000, centers=3, n_features=2, cluster_std=6, random_state=42) ntrain = 100 x_train, y_train = X[:ntrain], y[:ntrain] x_test, y_test = X[ntrain:], y[ntrain:]

要点：

• n_samples=1000：共 1000 个样本；
• centers=3：3 个类别中心，构成三分类问题；
• cluster_std=6：簇内标准差较大，三类数据有相当程度的重叠，方便观察 KNN 边界的敏感性；
• random_state=42：固定随机种子保证可复现；
• 前 100 个样本作为训练集，其余 900 个作为测试集，刻意拉开训练/测试规模差距以观察过拟合现象。

不同 k 值下的决策边界

脚本在测试集覆盖的二维平面上建立 200×200 的网格，对k = 1, 2, 5分别训练 KNN 并绘制预测结果的彩色区域（pcolormesh），叠加训练样本散点：

x = np.linspace(np.min(x_test[:, 0]), np.max(x_test[:, 0]), 200) y = np.linspace(np.min(x_test[:, 1]), np.max(x_test[:, 1]), 200) xx, yy = np.meshgrid(x, y) xy = np.c_[xx.ravel(), yy.ravel()] for k in [1, 2, 5]: knn = KNN(n_neighbors=k) knn.fit(x_train, y_train) y_predicted = knn.predict(xy) plt.pcolormesh(xx, yy, y_predicted.reshape(200, 200), cmap='jet', alpha=0.2) plt.title('k=%s' % k)

实验观察：k=1时决策边界极度曲折、几乎完全贴合单个样本（典型的过拟合表现）；k=5时边界变得平滑、更具泛化性。这正是本书强调的「k 是 KNN 唯一的超参数，直接控制模型复杂度」的核心论点。

误分类率随 k 的变化

脚本进一步对ks = [1, 5, 10, 20, 50, 70, 79]分别计算训练误差与测试误差：

train_errs, test_errs = [], [] for k in ks: knn = KNN(n_neighbors=k) knn.fit(x_train, y_train) train_errs.append(1 - knn.score(x_train, y_train)) test_errs.append(1 - knn.score(x_test, y_test))

训练误差随 k 增大单调上升，而测试误差呈 U 形：k 过小（模型过复杂）与 k 过大（模型过于平滑）都会损害泛化性能。这是「偏差-方差权衡」在非参数方法上的直观体现。

交叉验证选 k

脚本使用 5 折交叉验证（cv=5）在训练集上自动挑选最优 k：

from sklearn.model_selection import cross_val_score scores = [] for k in ks: knn = KNN(n_neighbors=k) score = cross_val_score(knn, x_train, y_train, cv=5) scores.append(1 - score.mean()) min_k = ks[np.argmin(scores)]

交叉验证曲线的最低点对应的 k 即为推荐值，图中以竖线标出。该流程与 knn_demo.ipynb 中的实现完全一致（该 Notebook 共 9 个代码单元，依次覆盖数据生成、训练/测试集可视化、决策边界、误差曲线、交叉验证与概率热力图）。

类别概率输出

KNN 天然支持软分类。脚本最后用k=10训练模型，对网格调用predict_proba，并分别绘制每个类别的概率等高线（contourf）：

knn = KNN(n_neighbors=10) knn.fit(x_train, y_train) xy_predic = knn.predict_proba(xy) for i in range(3): plt.contourf(xy_predic[:, i].ravel().reshape(200, 200), levels=np.arange(0, 1.01, 0.1)) plt.colorbar() plt.title('p(y=%s | data, k=10)' % i)

其原理是：k 个近邻中属于类别 i 的样本占比即为该类别的后验概率估计，即p(y=i | x) ≈ (1/k) * Σ_{j∈N_k(x)} [y_j = i]。该热力图直观展示出类别概率在决策边界附近的平滑过渡。

KNN 与 Voronoi 划分：几何视角

knn_voronoi_plot.ipynb 及其脚本 deprecated/scripts/knn_voronoi_plot.py 从计算几何角度解释 KNN 的决策机制——1-NN 的决策边界恰好就是训练样本点集的 Voronoi 图。

from scipy.spatial import KDTree, Voronoi, voronoi_plot_2d import numpy as np np.random.seed(42) data = np.random.rand(25, 2) # 1. 用 scipy 直接绘制 Voronoi 划分 vor = Voronoi(data) voronoi_plot_2d(vor) # 2. 用 KDTree 查询最近邻，为网格着色 tree = KDTree(data) x = np.linspace(xlim[0], xlim[1], 200) y = np.linspace(ylim[0], ylim[1], 200) xx, yy = np.meshgrid(x, y) xy = np.c_[xx.ravel(), yy.ravel()] plt.pcolormesh(x, y, tree.query(xy)[1].reshape(200, 200), cmap='jet')

实现要点：

• scipy.spatial.Voronoi+voronoi_plot_2d：对 25 个随机二维点构造凸包划分，展示每个训练样本「独占」的邻域区域；
• scipy.spatial.KDTree.query：对 200×200 网格中的每个点返回最近邻索引[1]，据此为网格着色，其结果与 Voronoi 划分逐像素一致；
• 两者互为验证：Voronoi 图是 1-NN 分类器决策边界的精确几何表达，KDTree 则是实际查询时的高效数据结构（构建 O(N log N)、查询平均 O(log N)）。

维度灾难：高维空间中 KNN 失效的原因

deprecated/scripts/curse_dimensionality_plot.py 用一段极简代码量化「维度灾难」：

ds = [1., 3., 5., 7., 10.] s = np.linspace(0, 1, 100) for d in ds: y = s ** (1 / d) plt.plot(s, y, 'b-') plt.text(0.3, 0.3**(1/d), 'd=%d' % d) plt.xlabel('Fraction of data in neighborhood') plt.ylabel('Edge length of cube')

数学推导：在 d 维单位超立方体中，要覆盖总体中比例为 s 的数据，所需立方体的边长约为e_d(s) = s^(1/d)。从曲线可以读出：

• d=1时，覆盖 10% 数据只需边长 0.1 的区间；
• d=10时，覆盖同样 10% 数据需要边长约0.1^(1/10) ≈ 0.79的超立方体——几乎占据了整个空间。

这意味着高维空间中「近邻」不再近，样本间距离趋于均匀，KNN 等基于距离的方法性能急剧下降。这一结论直接支撑了书中「KNN 只在低维或数据量巨大时有效」的论断，也解释了为什么需要特征降维（如 PCA）或核方法。

平滑核函数族：KNN 的连续化

KNN 的决策是分段常数（不连续）的，核方法将其推广为连续加权。图 16.8 对应的 smoothingKernelPlot.ipynb（脚本 deprecated/scripts/smoothingKernelPlot.py）在同一坐标系下对比了 4 种常见核：

| 核函数 | 数学定义 | 支撑区间 | |--|--|--| | Boxcar（矩形窗） |K(u) = ½ · I(|u| ≤ 1)| 紧支撑 | | Epanechnikov |K(u) = ¾(1 − u²) · I(|u| ≤ 1)| 紧支撑，统计效率最优 | | Tricube（三次立方） |K(u) = (70/81)(1 − |u|³)³ · I(|u| ≤ 1)| 紧支撑，光滑 | | Gaussian |K(u) = (1/√(2π)) · exp(−u²/2)| 全实数域 |

脚本中的实现：

def box(u): return (1/2)*(abs(u) <= 1) def epa(u): return ((3/4)*(1 - np.power(u, 2))*(abs(u) <= 1)) def tri(u): return (70/81)*np.power((1 - np.power(abs(u), 3)), 3)*(abs(u) <= 1) def gauss(u): return (1/np.sqrt(2*np.pi)) * np.exp(-np.power(u, 2)/2)

这些核是后续 Parzen 窗密度估计与核回归的「积木」，其共同性质包括非负、随 |u| 递减、且积分归一（脚本中通过sum(fx)打印了数值积分验证）。

Parzen 窗（核）密度估计

图 16.9 对应的 parzen_window_demo2.ipynb 与脚本 deprecated/scripts/parzen_window_demo2.py 展示了非参数密度估计的最经典形式：用核函数在样本点周围「堆叠」出连续的密度曲线。

脚本对 6 个一维样本[-2.1, -1.3, -0.4, 1.9, 5.1, 6.2]构造 2×2 子图网格，对比两种核 × 两个带宽：

def p1(x, X, h): # 单位超立方体（矩形窗）核 N, D = X.shape u = ((x - X.T) / h).reshape(D, xden, N) ku = K(u).sum(axis=1) / (N * h ** D) return ku def kdeg(x, X, h, return_components=False): # 高斯核 u = norm(xhat - Xhat, ord=2, axis=0) ** 2 / (2 * h ** 2) px = np.exp(-u) px = px / (N * h * np.sqrt(2 * np.pi)) return px

实验结论一目了然：

• 带宽 h 是唯一超参数：h=1时曲线多峰、贴合样本；h=2时曲线更平滑、细节被抹平——h 控制偏差-方差权衡；
• 矩形窗核产生阶梯状（step）密度，高斯核产生光滑曲线；
• 高斯核版本额外提供了return_components=True选项，可叠加显示每个样本贡献的单峰成分（红色虚线），直观展示「密度 = 各核峰之和」。

核回归：Nadaraya-Watson 估计器

图 16.10 对应的 kernelRegressionDemo.ipynb 与脚本 deprecated/scripts/kernelRegressionDemo.py 实现了非参数回归的经典形式——Nadaraya-Watson 核回归：

$$\hat{f}(x) = \frac{\sum_{i=1}^{N} K_h(x - x_i), y_i}{\sum_{i=1}^{N} K_h(x - x_i)}$$

即预测值是训练标签关于核权重的加权平均，权重由查询点到各训练点的距离决定。

数据与特征

N = 100 x = 10 * np.linspace(-1, 1, 100).reshape(-1, 1) ytrue = np.array([math.sin(abs(el)) / (abs(el)) for el in x]).reshape(-1, 1) noise = 0.1 y = ytrue + noise * np.random.randn(N, 1) x = (x - x.mean()) / x.std() # 标准化

目标函数为 sinc 形状的sin(|x|)/|x|，叠加高斯噪声，并对输入做标准化（均值 0、标准差 1），这是保证距离度量合理的必要预处理。

RBF 核与自选带宽

def rbf_features(X, centers, sigma): dist_mat = cdist(X, centers, 'minkowski', p=2.) return np.exp((-0.5 / (sigma ** 2)) * (dist_mat ** 2))

核函数选用 RBF（高斯）核，带宽由sigma控制。脚本中的NdwkernelReg类在gammas=np.linspace(0.1, 1, 10)的候选集上，通过**留一交叉验证（leave-one-out cross-validation）**自动选择带宽：

def select_gamma(self, gammas): mse = [] for gamma in gammas: K = rbf_features(self.X, self.X, gamma) K = K - np.diag(np.diag(K)) # 抹掉对角线，等价于留一 y_pred = (K * self.y).sum(axis=0) / K.sum(axis=0) mse.append(((y_pred[:, np.newaxis] - self.y) ** 2).mean()) return gammas[np.argmin(mse)]

注意其中的技巧：将核矩阵对角线置零后做加权平均，每个点的预测不再包含自身，从而以 O(N²) 一次计算近似实现留一交叉验证，这是核方法调参中的常见工程做法。

最终绘制「真实曲线 / 带噪数据 / 核回归估计」三者的对比，验证 Nadaraya-Watson 估计器能在不假设任何参数形式的前提下逼近 sinc 型目标函数。

运行环境与复现方式

所有第 16 章 Notebook 可直接在 Jupyter 中运行，核心依赖为：

• scikit-learn（KNN 分类器、make_blobs、cross_val_score）
• scipy（KDTree、Voronoi、cdist、norm）
• numpy/matplotlib

仓库根目录的 requirements.txt 与 requirements-dev.txt 已覆盖上述依赖。Notebook 中的绘图逻辑与deprecated/scripts/下同名脚本一一对应，若只想快速验证某个实验，可直接运行对应脚本：

python deprecated/scripts/knn_classify_demo.py python deprecated/scripts/knn_voronoi_plot.py python deprecated/scripts/curse_dimensionality_plot.py python deprecated/scripts/parzen_window_demo2.py python deprecated/scripts/kernelRegressionDemo.py

脚本依赖仓库内的 deprecated/scripts/superimport.py（以import superimport形式引入）与 deprecated/scripts/pyprobml_utils.py（提供savefig等绘图工具），请确保在仓库根目录或已配置PYTHONPATH的环境下执行。

小结

第 16 章的资源链完整覆盖了基于样本方法的核心图谱：从 KNN 分类（决策边界、误差曲线、交叉验证选 k、概率输出）、Voronoi 几何解释、维度灾难的量化，到核平滑、Parzen 窗密度估计与 Nadaraya-Watson 核回归，每一环节都有可直接运行的 Notebook 与对应源码脚本可供对照实验。理解这些非参数方法，是后续理解高斯过程、核 SVM 与各类局部模型的基础。

• 机器学习
• 深度学习