K-means 聚类 · 最简单的"自己分组"

三行算法

K-means 是机器学习里最简单又最实用的算法之一。1957 年 Stuart Lloyd 在贝尔实验室设计，目的就是把信号样本量化压缩 —— 几乎所有的”自动分组”问题都用它打底。

算法本体只有三件事，反复做：

1. 随机放 k 个质心
2. 把每个点归到离它最近的质心 → 形成 k 个组
3. 把每个质心挪到它所辖点的平均位置 → 回到 2

直到质心不再动。完结。

数学上它在干什么

K-means 在最小化总惯量（也叫 within-cluster sum of squares, WCSS）：

$$\text{WCSS} = \sum_{i=1}^{k} \sum_{x \in C_i} \|x - \mu_i\|^2$$

每个点对自己所在簇的质心 $\mu_i$ 的平方距离之和。

为什么算法能让 WCSS 下降？

• 归属步：每个点选最近的质心 → 它对总损失的贡献变小
• 更新步：质心 = 所辖点的均值 → 这正是使该组平方距离之和最小的位置（一阶条件）

所以每一步 WCSS 严格不增。配合”状态有限”，算法必然收敛。

试一下：在右边看”总惯量”那一行，每点一次”下一步”，看数字怎么下降。

何时灵 / 何时翻车

✅ 灵：簇大致是凸的、密度相近、大小相近。

试 “三团” 数据：三个明显的高斯团，k=3 几步就完美对齐。

❌ 翻车场景：

1. 非凸簇

试 “双月” 数据，k=2：两个新月形状本应该是两个簇，但 k-means 用直线切分，把两个月各切一半。

• 原因：归属步用欧氏距离 —— 只看”是不是最近”，不看”是不是同一形状”。
• 工程上换 DBSCAN（密度聚类）或 谱聚类。

2. 紧密缠绕

试 “螺旋”：两条交织的螺旋，k=2 永远找不到这个结构。

3. 簇大小差距大

如果有一个大簇 + 一个小簇，k-means 倾向于把大簇切两半让总损失最小。

4. 簇密度不同

稀疏的”小但远”的簇可能被吞进密的”大但近”的簇里。

5. 没有 ground truth 时怎么选 k？

不知道有几个簇！工程上用肘部法则（elbow method）：画 WCSS-vs-k 曲线，找折弯。或者用轮廓系数（silhouette）。

局部最优陷阱

K-means 几乎肯定会陷入局部最优。试这个：在”三团”数据上，反复按”重置质心”+ 运行 ——

• 多数时候三个质心各占一团（全局最优）
• 偶尔会有两个质心挤一团、一个质心独占两团（局部最优）—— 总惯量明显更大

工程对策：

1. k-means++ 初始化：先选第一个质心随机；后续质心选远离已有质心的点 → 大大降低陷入差解的概率
2. 多次重启：跑 10-20 次随机初始化，取 WCSS 最低那次
3. 小批量 mini-batch：处理大数据集，scikit-learn 的 MiniBatchKMeans 是工业级

真实世界的 k-means

• 图像分割：每个像素 = (R, G, B)；k-means 把图像压缩到 k 种颜色（GIF 调色板就是这么算的）
• 客户细分：电商把用户按购买行为聚成 5-10 组，每组推不同营销
• 新闻分组：把抓取的几万条新闻按 TF-IDF 向量聚类，自动出”主题板块”
• 天文学：把恒星按观测特征聚类，发现新的星族
• 生信：基因表达谱聚类，找”行为相似”的基因
• 量化交易：把股票按多日收益向量聚类，发现”同向运动”的板块
• 压缩：将语音波形 → 矢量量化（VQ） → 码本（每个码字就是一个质心）

K-means 这个 1957 年的简单想法，今天还在 Spotify 推荐、Netflix 搜索、Google Photos 自动相册分类的核心循环里跑。

一个不显然的洞察

K-means 是一个特殊的 EM 算法（期望-最大化）实例。

• E 步（Expectation）= 归属步：给定参数，求点的归属
• M 步（Maximization）= 更新步：给定归属，最优化参数

把这个框架推广 —— 每个簇是个高斯分布而不是一个点 —— 就得到高斯混合模型 GMM。GMM 能拟合椭圆簇、可变密度的簇、软分配（一个点同时属于多个簇，有不同概率）。

更进一步，变分推断（VI）、变分自编码器（VAE）也是 EM 框架的衍生。一根线从 1957 年的 k-means 一直拉到 2014 年的深度生成模型。