4.2 K-均值聚类

K-均值聚类

K-均值聚类（K-Means Clustering）是最常用的基于划分的聚类算法之一，它将数据集划分为 $K$ 个互不相交的簇，使得每个样本点归属于距离最近的簇中心。

算法步骤

K-均值聚类采用迭代优化的方式，主要步骤如下：

1. 初始化：随机选择 $K$ 个样本点作为初始簇中心（质心）
2. 分配：将每个样本点分配到距离最近的簇中心所在的簇
3. 更新：重新计算每个簇的质心（簇内所有样本的均值）
4. 重复：重复步骤2和3，直到簇中心不再发生显著变化（收敛）

距离度量

样本 ${\mathbf{x}}_i$ 与簇中心 ${\mu }_k$ 之间的欧氏距离为：

$$d_{ik}=\Vert {\mathbf{x}}_i-{\mu }_k{\Vert }_2=\sqrt{\sum _{j=1}^d(x_{ij}-{\mu }_{kj}{)}^2}$$

优化目标

K-均值算法极小化所有样本点到其所属簇中心距离的平方和（即簇内误差平方和）：

$$J=\sum _{k=1}^K\sum _{{\mathbf{x}}_i\in C_k}\Vert {\mathbf{x}}_i-{\mu }_k{\Vert }^2$$

局限性

• 异常值敏感：极端值会显著影响簇中心的计算，导致聚类结果偏差
• 初始种子敏感：不同的初始中心选择可能导致不同的聚类结果，通常需要多次运行取最优
• 数据分布不适应：K-均值假设簇呈球形分布，对非球形分布或密度差异大的数据效果不佳
• 需要预先指定 $K$ 值：在实际应用中 $K$ 值通常未知，需结合肘部法则等方法确定

改进方法

针对初始种子敏感问题，K-Means++ 算法改进了初始化策略，使初始中心尽可能分散，从而提高聚类的稳定性和质量。

链接到

• 上一个知识点：4.1 数据标准化
• 下一个知识点：4.3 层次聚类