K-Means 聚类算法：理论推导、核心公式与实战解析
，无监督学习（Unsupervised Learning）扮演着的角色。其中，K-Means（K-均值）聚类算法因其简洁性、高效性和可扩展性，成为了最经典且应用最广泛的聚类算法之一。
这篇文章将深入剖析 K-Means 的数学理论基础，详细推导其核心公式，并通过表格对比不同初始化策略及数据示例，帮助读者从原理到实践全面掌握这一算法。
什么是 K-Means？
K-Means 是一种基于距离的迭代型聚类算法。其核心思想是：将数据集中的 个样本划分为 个簇（Cluster），使得每个样本属于与其最近的均值（Centroid）所代表的簇，从而最小化簇内样本与簇中心之间的距离平方和。
基本假设
1. 簇是凸形的：即簇内的样本在空间中聚集在一起。 2. 簇的大小相近：K-Means 对球状分布的数据效果最好。 3. 数据需要数值型特征：因为算法依赖于距离计算。K-Means 数学理论
K-Means 的目标是找到一个最优的聚类划分，使得簇内误差平方和（Within-Cluster Sum of Squares, WCSS）最小化。
1 目标函数（Objective Function）
假设我们将数据集 划分为 个簇 ，其中 是第 个样本， 是特征维度。
令 为第 个簇 的质心（Centroid），则 K-Means 的最小化目标函数为：
其中：- 采用欧几里得距离（Euclidean Distance）的平方。
- 越小，表明簇内样本越紧密，聚类效果越好。
2 质心的更新公式
对于任意一个簇 ，其质心 定义为该簇中所有样本的均值：
其中 是簇 中的样本数量。
算法流程与推导
K-Means 凭借交替优化两个步骤来最小化目标函数 ：
1. 分配步骤（Assignment Step）：固定质心 ，将每个样本分配给最近的质心。
2. 更新步骤（Update Step）：固定样本归属，重新计算每个簇的质心。
1 分配步骤推导
对于每个样本 ，我们寻找使其距离最小的质心索引 ：
然后将 归入簇 。这一步是在构建 Voronoi 图（Voronoi Diagram），将空间划分为多个区域。
2 更新步骤推导
当样本归属确定后，我们需要找到新的质心 以最小化该簇内的距离平方和。对目标函数 关于 求偏导并令其为 0：
解得：
这证明了质心就是簇内样本的几何中心。
K-Means++ 初始化策略
标准的 K-Means 对初始质心的选择十分敏感，导致算法收敛到局部最优解。K-Means++ 是一种改进的初始化方法，旨在使初始质心尽分散。
K-Means++ 步骤：
1. 从数据集中随机选择一个点作为个质心 。 2. 对于数据集中的每个点 ，计算其与最近已选质心的距离 。 3. 从数据集中选择一个新点作为下一个质心 ，选择的概率与 成正比。 4. 重复步骤 2-3，直到选出 个质心。
为什么选择 作为权重？
- 距离当前质心越远的点，被选为新质心的概率越大。
- 平方关系确保了距离远的点有显著更高的概率被选中，从而避免初始质心聚集在一起。
数据说明与示例
为了直观理解 K-Means 的工作过程，我们构建一个简单的二维数据集示例。
1 示例数据集
假设我们有 6 个二维数据点，希望将其分为 个簇。
| 样本 ID | 特征 X (x坐标) | 特征 Y (y坐标) | 备注 |
|---|---|---|---|
| A | 1.0 | 1.0 | 潜在簇 1 |
| B | 1.5 | 2.0 | 潜在簇 1 |
| C | 3.0 | 4.0 | 潜在簇 2 |
| D | 5.0 | 4.0 | 潜在簇 2 |
| E | 4.0 | 5.0 | 潜在簇 2 |
| F | 3.5 | 3.5 | 潜在簇 2 |
2 迭代过程演示
初始状态：随机选择 A(1.0, 1.0) 和 C(3.0, 4.0) 作为初始质心 和 。
第 1 轮迭代：
1. 分配步骤：- 计算各点到 和 的欧氏距离平方：
- 点 A: , . 归入簇 1
- 点 B: , . 归入簇 1
- 点 C: , . 归入簇 2
- 点 D: , . 归入簇 2
- 点 E: , . 归入簇 2
- 点 F: , . 归入簇 2
- 当前簇划分：
- 新质心
- 新质心
第 2 轮迭代：
1. 分配步骤：- 使用新的质心 和 重新计算距离。
- 经过计算，所有点的归属未发生改变（A, B 仍离 更近；C, D, E, F 仍离 更近）。
- 质心不再变化，或簇分配不再改变，算法收敛。
3 结果对比表
| 策略 | 初始质心选择 | 收敛速度 | WCSS | 稳定性 |
|---|---|---|---|---|
| 随机初始化 | 任意选择 | 较慢 | 较大 | 低（依赖运气） |
| K-Means++ | 分散选择 | 较快 | 较小 | 高（结果一致性好） |
| K-Means (手动) | 如上例所示 | 中等 | 局部最优 | 中等 |
优缺点分析
优点
1. 简单易懂：算法逻辑清晰，易于实现。 2. 高效：时间复杂度近似为 ，其中 是样本数， 是簇数， 是迭代次数。对于大规模数据集表现良好。 3. 可扩展性：适合处理大规模数据。缺点
1. 需预先指定 K 值：用户必须事先知道簇的数量，这在实际问题中未知。 2. 对异常值敏感：异常值会显著拉动质心位置，影响聚类效果。 3. 仅适用于球形簇：对于非凸形状（如环形、月牙形）的数据集效果较差。 4. 局部最优：收敛到局部最小值，而非全局最小值。如何确定最佳 K 值？
常用的方法囊括：
1. 肘部法则（Elbow Method）：- 绘制不同 K 值对应的 WCSS。
- 选择 WCSS 下降幅度明显变缓的“肘部”点作为 K。
- 衡量簇内紧密度和簇间分离度。
- 取值范围 [-1, 1]，越接近 1 体现聚类效果越好。
K-Means 作为聚类算法的基石，其理论简洁而强大。尽管存在局限性，但凭借改进初始化策略（如 K-Means++）、结合其他算法（如二分 K-Means）或用于预处理步骤，它依然在数据挖掘、图像分割、客户细分等领域发挥着独特的作用。
理解其背后的数学公式，不仅有助于正确应用算法，更能帮助我们在面对复杂数据时，做出更合理的模型选择和参数调整。
参考文献：
1. MacQueen, J. (1967). "Some methods for classification and analysis of multivariate observations".
2. Arthur, D., & Vassilvitskii, S. (2007). "k-means++: The Advantages of Careful Seeding".
