原型聚类prototype-based clustering假设聚类结构能通过一组原型刻画。

常见的原型聚类有：

1. k均值算法k-means
2. 学习向量量化算法Learning Vector Quantization：LVQ
3. 高斯混合聚类Mixture-of-Gaussian

一、k-means算法

1.k-means

1.1 给定样本集$D=\{X_1,X_2,...,X_N \}$，假设一个划分为$C=\{C_1,C_2,...,C_K\}$，定义该划分的平方误差为：

$err=\sum_{k=1}^K \sum_{x=1,X_i \in C_k} ||X_i - u_k||_2^2$，其中$u_k = \frac{1}{|C_k|} \sum_{X_i \in C_k}X_i$是簇$C_k$的均值向量。

$err$刻画了簇类样本围绕簇均值向量的紧密程度，其值越小，则簇内样本相似度越高。

k-means算法的优化目标为：最小化$err$。即：$min_C \sum_{k=1}^K \sum_{X_i \in C_k} ||X_i - u_k||_2^2$

1.2 k-means的优化目标需要考察$D$的所有可能的划分，这是一个NP难的问题。实际上k-means采用贪心策略，通过迭代优化来近似分解。

1. 首先假设一组均值向量。
2. 然后根据假设的均值向量给出了$D$的一个划分。
3. 再根据这个划分来计算真实的均值向量：
   1. 如果真实的均值向量等于假设的均值向量，则说明假设正确。根据假设均值向量给出的$D$的一个划分确实是原问题的解。
   2. 如果真实的均值向量不等于假设的均值向量，则可以将真实的均值向量作为新的假设均值向量，继续迭代求解。

1.3 给定一组假设的均值向量，如何计算出$D$的一个簇划分？

k-means算法的策略是：样本离哪个簇的均值向量最近，则该样本就划归到那个簇。

1.4 k-means算法：

输入：样本集$D=\{X_1,X_2,...,X_N \}$，聚类簇数$K$

输出：簇划分$C=\{C_1,C_2,...,C_K \}$

算法步骤：

1. 从$D$中随机选择$K$个样本作为初始均值向量$\{u_1,u_2,...,u_K \}$
2. 重复迭代直到算法收敛，迭代过程：
   1. 初始化阶段：取$C_k = \varnothing，k=1,2,...,K$
   2. 划分阶段：令$i=1,2,...,N$：
      1. 计算$X_i$的簇标记：$\lambda_{i}=\arg \min _{k}\left\|\overrightarrow{{x}}_{i}-\vec{\mu}_{k}\right\|_{2}, k \in\{1,2, \cdots, K\}$，即：将$X_i$离哪个簇的均值向量最近，则该样本就标记为那个簇
      2. 然后将样本$X_i$划入相应的簇：$C_{\lambda_i}=C_{\lambda_i} \cup {X_i}$
   3. 重计算阶段：计算$\hat{\vec{\mu}}_{k}: \hat{\vec{\mu}}_{k}=\frac{1}{\left|{C}_{k}\right|} \sum_{\vec{x}_{i} \in \mathbb{C}_{k}} \overrightarrow{{x}}_{i}$
   4. 终止条件判断：
      1. 如果对所有的$k \in \{1,2,...,K\}$，都有$\hat{u_k}=u_k$，则算法收敛，终止迭代
      2. 否则重赋值$u_k=\hat{u_k}$

1.5 k-means优点：

1. 计算复杂度低，为$O(NKq)$，其中$q$为迭代次数。通常$K$和$q$要远远小于$N$，此时复杂度相当于$O(N)$
2. 思想简单，容易实现。

1.6 k-means缺点：

1.7 k-means性质

2.k-means++

3.k-modes

4.k-medoids

5.mini-batch k-means

30(1).原型聚类---k-means

原文：https://www.cnblogs.com/nxf-rabbit75/p/11915779.html