13.2 原型方法

在本章全部篇幅中，我们的训练集为 $N$ 个组合 $(x_1,g_1),\dots,(x_N,g_N)$，其中的 $g_i$ 为取值在 $\{1,2,\dots,K\}$ 上的类别标签。原型方法（prototype method） 是用特征空间上的一组点来代表整个训练集。除稍后介绍的 1-最近邻分类模型外，这些原型一般不是训练集中已有的点。

每个原型都有对应的类别标签，而一个新样本点会被分类到距离最近的原型所对应的类别。”距离最近“通常指的是在特征空间上，在所有特征变量都已按训练集标准化为均值 0 和方差 1 后，的欧式距离。对数量的特征变量欧式距离是适用的。第十四章将会讨论定性特征以及其他类型特征值所使用的距离测度。

如果原型的位置很好地捕捉到每个类别的分布情况，那么这类方法可能非常有效。特征空间上足够多的正确位置上的原型点，就可以表现出一些不规则的类别边界。所以需要解决的主要问题就是需要使用多少个原型以及它们位于哪里。根据原型选择的数量和方式不同，便有了不同的方法。

13.2.1 K 均值聚类

K 均值聚类（K-means clustering） 是在一组无标签（未分类的）数据上寻找簇（cluster）和簇中心（cluster center）的一种方法。选择了所需要的簇中心个数后，例如是 $R$，则 K 均值的计算过程会逐步迭代地移动簇中心从而将簇内方差的总和最小化。¹给定了初始的簇中心后，K 均值的算法重复以下两个步骤：

• 为每个簇中心寻找它在训练集上的簇，即与这个簇中心的距离小于其他簇中心的样本点。
• 在每个簇中计算每个特征的样本均值，这个均值向量就是这个簇的新的簇中心。

重复这两个步骤，直到最终收敛。初始簇中心通常是在训练集中随机选取的 $R$ 个样本。关于 K 均值的计算过程、针对不同变量类型的推广、以及更一般的距离测度，会在第十四章介绍。

而对有标签（已分类的）数据应用的 K 均值聚类，步骤如下：

• 在训练集的每个类别中分别使用 K 均值聚类，每个类别都有 $R$ 个原型（簇中心）。
• 给每个 $K\times R$ 个原型分配对应的类别标签。
• 一个新的样本点 $x$ 的分类是与其最近原型的分类。

图 13.1（上图）演示了三个类别和两个特征变量的模拟例子。我们为每个类别指定了 $R=5$ 个原型，画出了分类区域和决策边界。注意到有一些原型处于类别边界附近，会导致边界附近的样本点可能会被错误地分类。这是由这个方法的一个明显的缺陷导致的：对每个类别来说，其他类别对这个类别的原型的位置没有任何影响。接下来介绍一个更好的方法，可以在定位所有的原型时使用所有的样本。

13.2.2 学习向量量化

学习向量量化（learning vector quantization，LVQ） 来自 Kohonen (1989)，它以一种根据样本特定的（ad-hoc）方式针对（当前的）决策边界而放置原型点。LVQ 是一个在线算法：样本是一个一个地进行处理。

算法 13.1 学习向量量化（LVQ）

1. 为每个类别选择 $R$ 个初始原型： $$m_1(k), m_2(k), \dots, m_R(k), k=1,2,\dots,K$$ 例如可为每个类别随机抽取 $R$ 个训练样本。
2. （有放回地）随机抽取一个训练样本 $x_i$，令 $(j,k)$ 标记距离 $x_i$ 最近的原型 $m_j(k)$。
   1. 若 $g_i=k$（即它们类别相同），将该原型向这个训练样本点移动： $$m_j(k) \leftarrow m_j(k) + \epsilon(x_i-m_j(k))$$ 其中 $\epsilon$ 为学习率（learning rate）。
   2. 若 $g_i\neq k$（即它们类别不同），将该原型向这个训练样本点反方向移动： $$m_j(k) \leftarrow m_j(k) - \epsilon(x_i-m_j(k))$$
3. 重复步骤（2），每次迭代降低学习率 $\epsilon$。

这个方法的思路是让训练样本靠近正确类型的原型，而排开其他的原型。当迭代过程逐渐停止下来，原型应该接近于该类别的训练集样本点。随着每次迭代，学习率 $\epsilon$ 逐渐下降到零，这遵循了随机逼近（stochastic approximation）学习率的准则（第 11.4 节）。

图 13.1（下图）展示了使用 K 均值的解作为初始化点的 LVQ 的结果。原型点倾向于远离决策边界，同时也就远离了其他类别的原型。

上述的方法实际上被称为 LVQ1。一些改动版本（LVQ2、LVQ3、等等）有时能改善模型效果。学习向量量化的一个缺点是它完全由算法定义，而不是对某个固定的准则进行最优化。这样就不好理解它的性质。

13.2.3 高斯混合

高斯混合模型（Gaussian mixture model） 也可以被看成是一种原型方法，其思想与 K 聚类和学习向量量化是相似的。我们在第 6.8 节、第 8.5 节、和 第 12.7 节介绍了高斯混合的内容。每个簇被描述为一个高斯分布密度函数，有一个中心点（与 K 均值相同）以及一个协方差矩阵。如果将成分高斯分布限制为有常数的协方差矩阵，这个类比就会更为清晰（练习 13.1）。EM 算法中交替的两个步骤与 K 均值中的两个步骤非常相似：

• 在 E 步骤中，根据每个对应的高斯分布的似然度为每个样本对每个类别分配一个“责任值”或权重。位于一个类别中心附近的样本点会很可能对这个类别的权重为 1，而对别的类别的权重为 0。位于两个类别中间位置的样本点会相应地按类别分配权重。
• 在 M 步骤中，用所有的样本点为每个类别计算加权均值（以及协方差矩阵）。

高斯混合模型也因此通常被称作一个“软性”聚类方法，而 K 均值被称作“硬性”聚类方法。

类似地，当使用高斯混合模型来描述每个类别中特征变量的密度函数时，它可输出用于对 $x$ 分类的平滑的后验密度函数 $\hat{p}(x)=\{\hat{p}_1(x),\dots,\hat{p}_K(x)\}$（参考第 12.7 节式 12.60）。这常常被理解为“软性”分类，不过实际上分类规则是 $\hat{G}(x)=\operatorname{argmax}_k\hat{p}_k(x)$。

图 13.2 在第二章中模拟的混合数据问题中比较了 K 均值和高斯混合的结果。图中可见虽然两个决策边界大体上是相似的，但混合模型的边界更平滑（即使两者的原型基本都位于相同的位置）。同时也注意到虽然两个方法都（错误地）在左上区域放置了一个蓝色的原型，高斯混合分类器最终可以忽略掉这个区域，不过 K 均值不能忽略。LVQ 在这个例子上的结果与 K 均值很相似，就不以展示。

本节练习

练习 13.1

假设有一个高斯混合模型，协方差矩阵为常数矩阵：$\mathbf{\Sigma}_r=\sigma\mathbf{I}, \forall r=1,\dots,R$，其中 $\sigma$ 是一个固定的参数。详细说明 K 均值聚类算法和 EM 算法在拟合这个混合模型时的相似关联。证明在 $\sigma\rightarrow0$ 的极限情况下，两个方法完全相同。