注明：
原理部分的内容均来自周志华的西瓜书，真正的大师之作。
其他内容来自开源包文档、开源电子书、ipynb文档等。

# 原型聚类

原型¹聚类也称为 “基于原型的聚类(prototype-based clustering)”，此类算法假设聚类结构能够通过一组原型刻画，在现实聚类任务中极为常用。通常情形下，算法先对原型进行初始化，然后对原型进行迭代更新求解。采用不同的原型表示、不同的求解方式，将产生不同的算法。

## $k$ 均值聚类算法

给定样本集 $D = {x_1, \ldots, x_m }$ ，“$k$ 均值($k$-means)” 算法针对聚类所得簇划分 $\mathcal{C} = {C_1, \ldots, C_k }$ 最小化平方误差 $$ \tag{9.24} E = \sum^k_{i=1} \sum_{x \in C_i} ||x - \mu_i||^2_2 , $$ 其中，$\mu_i = {1 \over |C_i|} \sum_{x \in C_i} x$ 是簇 $C_i$ 的均值向量。直观来看，式(9.24)在一定程度上刻画了簇内样本围绕簇均值向量的紧密程度，$E$ 值越小则簇内样本相似度越高。

最小化式(9.24)并不容易，找到它的最优解需考察样本集 $D$ 的所有可能簇划分，这是一个 NP 难问题² 。因此，$k$ 均值算法采用了贪心策略，通过迭代优化来近似求解式(9.24)。算法流程如下，其中第1行对均值向量进行初始化，在第4-8行与第9-16行依次对当前簇划分及均值向量迭代更新，若迭代更新后聚类结果保持不变，则在第18行将当前的簇划分结果返回。

k 均值算法流程

输入：样本集 $D = {x_1, \ldots, x_m }$ ；