K-Means 聚类K-Means Clustering
没有标签也能学习？质心迭代、Voronoi 划分 — 首个无监督学习算法
K-Means 聚类 · 交互演示
为什么学这步？
之前所有算法都需要标签（监督学习），但现实中标注数据又贵又少——无监督学习能从数据自身的结构里挖出规律。K-Means 是最经典的无监督算法：给定一堆没标签的点，它自动把它们分成 K 个"团"，每个团由一个质心代表。应用极广：客户分群、图像压缩、异常检测、推荐系统。这一步从"有标准答案"转向"自己找结构"，是理解一切聚类与无监督方法的基础。
📌 发生了什么
- 没有标签！算法只知道点的坐标，自己找结构。
- 第1步（分配）：每个点归最近质心；第2步（更新）：质心移到簇中心。
- 重复两步直到质心不动，形成 Voronoi 区域划分。
⚠️ 常见陷阱
- K 是算法自己学的？不是，K 是人定的超参数，选错全盘皆错。
- K-Means 能分任意形状？不能，只擅长球形簇，月牙形/环形会失败。
- WCSS 越小越好？不对，K 越大 WCSS 必然越小，要找收益变小的拐点。
✅ 本章小结
- 无监督学习：没有标签，从数据几何结构找模式。
- 两步迭代：分配 + 更新，循环到收敛。
- 肘部法则：WCSS 由陡降转平缓的拐点，是选 K 的启发式参考。
① WCSS：簇有多"紧"，一个数说清
WCSS（Within-Cluster Sum of Squares，簇内平方和）= 每个数据点到自己所属簇的质心的距离平方，全部加起来。它用一个数字衡量聚类结果有多"紧"：WCSS 越小，点离自己的质心越近，簇越紧凑。K-Means 的"分配 + 移动质心"两步，每一步都在让 WCSS 变小（或不变）——所以右侧运行状态里的 WCSS 数字就是收敛进度条：它一路下降、不再变化时，算法就收敛了。
② 为什么不能只看 WCSS 选 K
既然 WCSS 越小越好，那直接把 K 开到最大不就行了？问题在于：K 越大，WCSS 必然越小，这跟聚类质量无关。极端情况：K 等于样本数时，每个点自己一个簇，质心就是点本身，WCSS=0——"完美"但毫无意义。所以"WCSS 最小"不能作为选 K 的标准，真正要找的是收益开始明显变小的那个点。
③ 肘部曲线：找"性价比"拐点
做法：对 K=1, 2, …, 8 分别把 K-Means 跑到收敛，记下每个 K 对应的 WCSS，连成曲线（左下图）。曲线通常先陡降——簇数不够时，多分一个簇收益很大；然后变平缓——簇够用了，再加只是把大簇硬拆开，收益骤减。由陡变平的拐点看起来像手臂的肘部，故称肘部法则，肘部对应的 K 就是推荐的簇数。点击下方「📐 计算肘部曲线」即可生成这条曲线，"最优 K 候选"由程序用二阶差分（下降幅度衰减最明显处）自动标出。本页数据由 3 个真实簇生成，可以验证肘部是否落在 K=3 附近。注意：真实数据的肘部常常并不明显，肘部法则只是启发式的参考经验，不是铁律。
📐 K-Means 目标函数与更新规则
K-Means 通过最小化簇内平方和来寻找最优聚类。以下是目标函数与交替优化的推导。
固定中心 μ_k，最优分配是将每个点分到最近的簇（分配步）：
固定分配，最优中心是簇内均值（更新步）。对 μ_k 求导令其为零：
两步交替执行直到收敛（中心不再变化）。这是 EM 算法的特例：
🎛 K 值选择与肘部法则
K 是 K-Means 唯一的核心超参数。肘部法则通过观察 J 随 K 的变化来选择最优 K。
| K 值 | 表现 | 结果 |
|---|---|---|
| K = 2 | 簇太少，不同群体被合并 | 欠分割 |
| K = 5 | 与真实簇数吻合，聚类清晰 | 推荐 |
| K = 10 | 大簇被过度拆分，J 下降变缓 | 过分割 |
| K = n | 每点一簇，J=0 但无意义 | 退化 |
💡 肘部法则：画 J-K 曲线，选"拐点"处的 K。也可用轮廓系数辅助判断。
💻 K-Means 主循环
分配步 + 更新步的交替执行（Python）：
# K-Means 主循环
def kmeans(data, k, max_iter):
# 1. 随机初始化 k 个中心
centers = [p.copy() for p in data[:k]]
labels = [0] * len(data)
for _ in range(max_iter):
# 2. 分配步：每个点找最近中心
for i in range(len(data)):
min_dist, best = float('inf'), 0
for j in range(k):
d = dist(data[i], centers[j])
if d < min_dist:
min_dist, best = d, j
labels[i] = best
# 3. 更新步：中心 = 簇内均值
changed = False
for j in range(k):
pts = [data[i] for i in range(len(data)) if labels[i] == j]
new_center = mean(pts)
if dist(new_center, centers[j]) > 1e-6:
changed = True
centers[j] = new_center
if not changed:
break # 收敛
return centers, labels📚 参考文献与延伸阅读
- MacQueen, J. (1967). Some methods for classification and analysis of multivariate observations. — K-Means 算法的原始论文
- scikit-learn: KMeans — K-Means++ 初始化的工业实现
- Arthur, D. & Vassilvitskii, S. (2007). K-Means++: The Advantages of Careful Seeding. SODA — 改进初始化避免局部最优
- Wikipedia: K-means clustering — 算法变体与收敛性证明
📝 课后练习
检验你的理解——答对为止