基本思想：通过迭代寻找K个簇的一种划分方法，使得聚类结果对应的代价函数最小。特别地，代价函数可以定义为各个样本距离所属聚类中心的误差平方和

\[J(c, \mu) = \sum \limits_{i=1}{M}||x_i - \mu_{c_i}||^2​\]

具体步骤

• 数据预处理，如归一化、离群点处理等

• 随机选取K个簇中心，记为\(\mu_1^{(0)}, \cdots, u_k^{(0)}\)

• 定义代价函数：\(\begin{aligned} J(c, \mu) = \mathop{\min}_{\mu}\mathop{\min}_{c}\sum \limits_{i=1}{M}||x_i - \mu_{c_i}||^2 \end{aligned}\)

• 令\(t = 0, 1, \cdots\)为迭代步数，直到\(J\)收敛

  • 对于每一个样本\(x_i\)，将其分配到最近的簇

    \[\begin{aligned} c_i^{t} = \mathop{\arg \min}_k ||x_i - \mu_k^{(t)}||^2 \end{aligned}​\]

  • 对于每一个类簇k，重新计算该类簇的中心

    \[\begin{aligned} \mu_k^{t} = \mathop{\arg \min}_{\mu} \sum \limits_{i:c_i^{(t)=k}} ||x_i - \mu||^2 \end{aligned}\]

K均值算法在迭代时，假设当前\(J\)没有达到最小值，那么首先固定类簇中心，调整每个样例所属类别来使\(J\)减小。然后固定样例所属类别，调整类簇中心使\(J\)减少。

优缺点

• 优点：可伸缩、高效，复杂度\(O(NKt)\)
• 缺点：
  • 受初始值和离群点影响结果不稳定
  • 局部最优解
  • 数据簇分布差别特别大的情况（例如数量差距悬殊），需要手动设置K值
  • 样本点只能划分到单一类中（可用模糊C均值或高斯混合模型）

算法调优

• 数据归一化和离群点处理：基于欧式距离度量的数据划分方法
• K值的选择：手肘法、Gap Statistic方法
• 核K均值算法：增加数据点线性可分的概率

改进模型

• K-means++算法：初始值选择改进
  • 假设已经选择了n个初始簇中心，则在选择第n+1个时，距离当前n个中心越远的点会有更高的概率被选中
• ISODATA算法（迭代自组织数据分析法）
  • 当属于某个类别的样本数过少时，把该类别去掉
  • 当属于某个类别的样本数过多、分类程度较大时，分裂成两个子类别
  • 分裂操作、合并操作

收敛性证明

转换为概率模型，通过EM算法的收敛性得到证明