• 「原型 (prototype)」：指的是样本空间中具有代表性的点。
• 基于原型的聚类：通过一组原型刻画聚类的结构。一般的方法是对原型进行迭代更新求解。

A K-Means 算法

A1 K-Means 算法概念

• 簇心点：要划分出 $K$ 个簇，每个簇 $C_k$ 中都有一个簇心点 $\boldsymbol c_k$（不一定要与某样本重合）。

  • 下面可以看到，K-Means 中本质上将簇的质心作为簇心点，但现在可以不考虑。

• 簇的划分规则：对每个样本点而言，取其最近的一个簇心点作为它当前所属的簇，即：

  $$ \lambda[j] = \argmin_{k=1}^K {\rm dist} (\boldsymbol x^{(j)}, \boldsymbol c_k) $$

  • 因而确认了每个簇的簇心点，就完成了聚类任务。

  • Voronoi 剖分：如对样本空间中所有点都进行如上公式所示的簇标记，将得到对样本空间的「Voronoi 剖分」。

    

  • 这种思想被称为「胜者通吃 (winner-take-all)」。

• 优化目标：设法最小化所有样本点到其所属簇簇心点的距离平方和（总体误差）：

  $$ E(\boldsymbol \lambda) = \sum_{j=1}^{|X|} {\rm dist}^2(\boldsymbol x^{(j)}, \boldsymbol c_{\lambda[j]}) $$

A2 K-Means 算法流程

• 算法综述：通过逐渐迭代簇心点，以求得一种与初始状态有关的局部最优解。
  • **初始值：**随机选择 $K$ 个不同的样本点作为初始簇心点 $\boldsymbol c_1^{(t=0)}, \boldsymbol c_2^{(t=0)}, \cdots, \boldsymbol c_K^{(t=0)}$ 。
  • 迭代过程：
    1. 更新所属关系：对每个样本点 $\boldsymbol x^{(j)}$ ：求得其到各个簇心点的距离，并选择最近的一个簇心点作为它当前所属的簇心点。
    2. 计算当前误差：利用误差 $E(\boldsymbol \lambda)$ 公式，计算当前方案的总体误差。
    3. 更新簇心点：将每个簇的簇心点重新更新为其内所有点的质心 $\boldsymbol c_k^{(\rm new)} = \boldsymbol \mu_k = \frac 1 {|C_k|} \sum_{\boldsymbol x \in C_k} \boldsymbol x$。
  • **结束条件：**当所属关系不再改变，或者误差降低的速率低于某个阈值，便可以停止算法。
  • 枚举全空间中所有可能的簇划分当然是一个 NP 难问题，因而上述算法是使用了贪心策略。

• 代码

A3 最临近搜索 (Nearest Neighbour Search, NNS)

• 类似于上面所述的在 Voronoi 剖分的空间中搜索任意点对应的簇心点 $\argmin_{k=1}^K {\rm dist} (\boldsymbol x, \boldsymbol c_k)$ 的问题，被称为「最临近搜索」。有很多方法进行加速。

A4 K-Means 的变体

• K-Modes。
• 核 K-Means 方法 [Schölkopf et al., 1998]。
• 采用 Bregman 距离（不满足对称性和三角不等式），以增强对非凸簇结构上的适用性 [Banerjee et al., 2005]。
• 确定簇数目 $K$ 的方法：① 多次运行后选取最佳结果；② 启发式搜索最优 $K$ 值。

B 学习向量量化 (Learning Vector Quantization, LVQ)