13 第十三章原型方法和最邻近

在统计学习和机器学习中，原型方法（Prototype Methods） 是一类基于“代表性样本”进行分类或回归的算法。

简单来说，它的核心思想是：与其记住所有的训练数据，不如选出（或计算出）一组具有代表性的“原型”来概括数据的特征。 当新样本出现时，通过比较它与这些原型的相似度来进行决策。

原型方法（Prototype Methods）在系统层面本质上是一个“以空间换时间，再以计算复杂度换取缓存命中率”的权衡过程。

[逻辑架构图]

动机层 (Motivation)：解决 $k$ -NN 的存储开型 ( $O (N)$ ) 与计算开销 ( $O (Np)$ ) 的维数灾难。
构造层 (Construction)：
- 无监督构造：K-Means / K-Medoids（基于质心的拓扑空间划分）。
- 有监督构造：LVQ（基于决策边界的动态向量调整）。
决策层 (Inference)：基于 Voronoi 图（泰森多边形）的最近邻搜索。
系统优化层 (Systems)：数据压缩、缓存局部性优化、分支预测友好性。

在统计学习中， $k$ -最近邻（ $k$ -NN）被归类为懒惰学习 (Lazy Learning)，它将所有的决策推迟到预测阶段。

原本内容：k-NN 需要存储所有训练样本。原型方法是对其的优化，通过找到数量更少的点（原型）来实现压缩性和代表性。
扩充部分：{从系统架构角度看， $k$ -NN 的瓶颈在于 Memory Wall（存储墙）。当数据集 $N$ 极大时，每一次预测都会触发海量的非连续内存访问，导致严重的 Cache Miss 和 TLB Thrashing。原型方法通过构造一组 $K ≪ N$ 的原型向量，将模型规模从 $O (N)$ 降低到 $O (K)$ ，使得原型向量能够完整驻留在 L2 甚至 L1 Cache 中，从而将 I/O 密集型任务转化为计算密集型任务。}

原本内容：K-Means 是典型的原型方法。每个簇的质心（Centroid）就是该簇的原型，用 K 个点来代表数据。
扩充部分：{K-Means 的本质是在最小化重构误差（Reconstruction Error）。在实现上，它是 Lloyd 算法的迭代过程。为了在底层提高执行效率，专家级实现会利用 SIMD (Single Instruction, Multiple Data) 指令集（如 AVX-512）并行计算样本到 $K$ 个质心的欧氏距离。

$J = \sum_{n = 1}^{N} \sum_{k = 1}^{K} r_{nk} ∥ x_{n} - μ_{k} ∥^{2}$

同时，在硬件加速中，我们会使用 半精度浮点数 (FP16) 甚至 INT8 量化来存储质心向量，以进一步榨取内存带宽。}

原本内容：这是一种有监督方法。如果原型正确预测了样本，向样本靠近；预测错误，则远离样本。
扩充部分：{LVQ（尤其是 LVQ2.1）是在修正 Bayes 决策边界。它的更新法则遵循随机梯度下降（SGD）的变体：
- 正确分类： $w_{j} \leftarrow w_{j} + ϵ (x - w_{j})$
- 错误分类： $w_{j} \leftarrow w_{j} - ϵ (x - w_{j})$
  
  这种“推拉”机制在底层实现时，对分支预测器 (Branch Predictor) 极不友好，因为更新逻辑取决于标签匹配的条件判断。在高性能实现中，我们通常采用 Predication（谓词化指令） 或掩码操作来消除条件跳转，保持指令流水线的平滑。}

原本内容：
- 质心分类器：每个类一个均值，简单但高效。
- K-Medoids：必须是真实样本点，对异常值鲁棒。
- RNN (Reduced Nearest Neighbor)：删掉不影响准确率的样本，为 k-NN 瘦身。
扩充部分：{K-Medoids 的优势在于它不要求特征空间满足欧氏空间的公理化假设，仅需定义距离矩阵 $D_{ij}$ 。这在处理非数值型对象（如进程系统调用序列）时极具价值。从 OS 调度的角度看，RNN 留下的样本点可以被视为 Support Vectors 的原型版，它们决定了内核中分类器所需的最小驻留集大小（Working Set Size）。}

原本内容：
- 数据压缩：降低存储，适合嵌入式。
- 降噪与提速：抵消异常值，降低推理延迟。
- 可解释性：观察原型即代表类别特征。
扩充部分：{在嵌入式实时系统（如你关注的健康监测 Rust 项目 hGuard）中，原型方法的应用涉及 Interrupt Latency。
- 快速路径优化：通过线性扫描极少量的原型（ $K = 10 \sim 50$ ），可以将判别延迟控制在微秒级，避免了 $k$ -NN 在检索树（KD-Tree）查找时可能产生的最坏情况 $O (N)$ 时间复杂度。
- 冷热数据分离：常用的原型放在高速 SRAM 中，次要原型放在 Flash 中，利用存储层级结构最大化能效比。}

CPU 缓存（L1/L2/L3）：
- $k$ -NN 的随机访问模式会导致大量的 Cache Miss；而原型方法通过缩减参数规模，使原型向量集符合 Temporal Locality（时间局部性），显著提升了 CPU 的计算吞吐量（IPC）。
虚拟内存与 TLB：
- 大规模数据集在进行全量搜索时会频繁触发 Page Fault。原型方法将数据集压缩后，模型通常小于一个内存页（4KB）或驻留在少数几个大页（Huge Pages）中，极大地减少了 TLB Miss。
编译器优化（Vectorization）：
- 在计算欧氏距离 $∥ x - w ∥^{2}$ 时，现代编译器（如 LLVM/Clang 或 Rust 的 rustc）能自动将循环展开并应用 Auto-Vectorization。如果原型数量 $K$ 是 8 或 16 的倍数，将完美对齐 SIMD 寄存器宽度。
统计学习理论 (ESL 视角)：
- 原型方法本质上是 高度非线性的降维。它将高维流形通过 Voronoi 划分投影到了低维的离散代表点上，这与 Vector Quantization (VQ) 在信号处理中的有损压缩原理完全一致。