3. k-means 算法 | Colommar Blog

来源：原始 Jupyter Notebook。内容已转换为网页阅读格式；下载原文件。

k均值（k-means）算法最初由 MacQueen 在 1967 年提出，是最著名的原型聚类算法之一。假设样本集被划分为 k 类 $\{C_1, C_2, \dots, C_k\}$ ，我们可以计算出每个类的均值向量，也就是类的中心位置：

\mu_i = \frac{\sum_{x \in C_i}x}{|C_i|}

得到每个类的均值向量后，可以计算出每个样本到均值向量的平方误差之和：

E(C_i) = \sum_{x \in C_i} \|x-\mu_i\|^2_2

将 k 个类的平方误差之和累加起来，就是 k 均值聚类算法的损失函数：

E(C) = \sum_{i=1}^k E(C_i)

函数 $E(C)$ 也称为能量，它表示簇内样本围绕簇均值向量的紧密程度，E 值越小，表示簇内样本相似度越高，k 均值算法就是试图最小化该函数。不过要计算该函数的最小值，必须计算出样本集所有可能的簇划分，这是一个 NP 难问题，因此 k 均值算法采用贪心策略，通过迭代优化来近似求解。

k 均值算法流程如下：

从样本集 D 中随机选择 k 个样本作为初始簇，每个样本的值就是该簇的均值向量
计算每个样本到均值向量的距离，选择距离最近的均值向量将每个样本划分到相应的簇里
根据每个簇里的样本，重新计算每个簇的均值向量
不断重复上述过程，直到迭代收敛或达到停止条件

k 均值聚类算法的时间复杂度是 O(mnk)，其中 m 是样本维数，n 是样本个数，k 是类别个数。

学习向量量化

学习向量量化（Learning Vector Quantization，简称 LVQ）和 k-means 一样，也是一种原型聚类算法。不过 LVQ 假设数据样本带有类别标记，学习过程利用样本的这些监督信息来辅助聚类。

首先随机初始化一组原型向量 $\{p_1, p_2, \dots, p_q\}$ ，q 是一个超参数，代表簇的个数，然后从样本集中随机选择一个样本 $(x_j, y_j)$ ，计算样本 $x_j$ 和原型向量中每个向量的距离，找出和 $x_j$ 距离最近的向量 $p_{i^*}$ ，如果样本 $x_j$ 的类别 $y_j$ 和原型向量 $p_{i^*}$ 的类别相同，则使用下面的公式更新原型向量：

p' = p_{i^*} + \eta \cdot (x_j - p_{i^*})

如果样本 $x_j$ 的类别 $y_j$ 和原型向量 $p_{i^*}$ 的类别不同，则使用下面的公式更新原型向量：

p' = p_{i^*} - \eta \cdot (x_j - p_{i^*})

直观上看，如果样本和原型向量类别相同，就让原型向量向样本靠拢，否则就远离样本。

重复上面的迭代步骤，一直到满足停止条件为止（达到最大迭代次数，或者原型向量更新幅度很小甚至不再更新）。

最终学的原型向量可以实现对样本空间的簇划分，将每个样本划入与其距离最近的原型向量即可，也就是说每个原型向量对应一个划分区域，在这个区域里，每个样本和原型向量的距离不大于它和其他原型向量的距离，这样的划分通常称为 Voronoi 剖分（Voronoi tessellation）。

如果使用原型向量来表示划分区域中的样本，则可以实现数据的 有损压缩（lossy compression），这称为 向量量化（vector quantization），这就是 LVQ 名字的由来。

学习向量量化#

学习向量量化