K-means 是一种常用的基于距离的聚类算法，核心目标是将数据集划分为 K 个簇，使得每个数据点属于距离最近的簇中心。通过反复迭代调整质心位置，算法不断优化簇内的紧密度，最终获得紧凑且彼此分离的簇。
1. 核心思想与工作流程
简单来说，K-means 就是'物以类聚'。它的流程可以概括为两个主要动作：分配和更新。
- 初始化：随机选择 K 个点作为初始质心（Centroids）。
- 分配：计算每个数据点到所有质心的距离，将其归入最近的那个簇。
- 更新：重新计算每个簇内所有点的均值，作为新的质心。
- 收敛：重复上述步骤，直到质心不再变化或达到最大迭代次数。
这个过程就像是在不断调整几个'磁铁'的位置，把周围的铁屑吸到离自己最近的地方，然后磁铁根据铁屑分布再移动一下，直到稳定下来。
算法步骤详解
假设我们要将二维数据点分为 K=2 个簇。首先随机选定两个点作为初始质心，比如 C1=(1,2) 和 C2=(8,8)。接下来计算每个点到这两个中心的欧氏距离：
$$d = \sqrt{\sum_{j=1}^{n}(x_j - \mu_j)^2}$$
| 数据点 | 到 C1 距离 | 到 C2 距离 | 归属 |
|---|---|---|---|
| 点 1 | 0 | 8.49 | 簇 1 |
| 点 2 | 1.41 | 8.06 | 簇 1 |
| 点 3 | 4.24 | 5.0 | 簇 1 |
| 点 4 | 5.0 | 4.24 | 簇 2 |
| 点 5 | 8.49 | 0 | 簇 2 |
分配完成后，我们计算新质心。例如簇 1 的新质心是其中所有点的平均值。接着用新质心再次计算距离，重复此过程，直到质心坐标基本稳定。
2. 数学基础与复杂度
K-means 的目标函数是最小化簇内平方误差和（WCSS）：
$$J = \sum_{i=1}^{K} \sum_{x \in C_i} ||x - \mu_i||^2$$
其中 $\mu_i$ 是第 i 个簇的质心，$C_i$ 是该簇的点集。这个公式本质上就是在追求簇内点越聚集越好。
关于性能，如果数据量是 n，簇数是 K，迭代次数是 T，那么总时间复杂度大约是 $O(n \cdot K \cdot T)$。对于大规模数据，这通常是可以接受的，但要注意每次迭代都要遍历所有点。
3. 优缺点分析
在实际项目中，我们需要权衡它的利弊：
- 优点：简单高效，适合处理大数据集；收敛速度通常较快。
- 缺点：对初始值敏感，容易陷入局部最优；假设簇是凸形（球形），对非凸形状（如月牙形）效果差；对噪声和离群点比较敏感。
4. K 值的选择
确定最佳的 K 值是个难点。常用的方法有：
