K-Means 聚类

你不需要提前告诉它答案，它自己就能把相似的东西归到一堆——这就是 K-Means

01 核心原理（大白话版）

想象你走进一个糖果店，桌上散落着几百颗糖。老板让你把它们分成几堆，但没告诉你怎么分——你会怎么做？

直觉上，你会把看起来像的糖放在一起：颜色相近的、大小相似的……这就是 K-Means 在做的事情。

算法其实只有四步

1
随机插旗

在数据堆里随机选 K 个点，插上旗子，这就是 K 个"队长"（质心）。

2
各找各妈

每个数据点看看自己离哪个队长最近，就跟着那个队长走。

3
队长挪窝

每个队长移动到自己队员的中间位置（取平均），让自己更"居中"。

4
反复直到稳定

重复步骤 2 和 3，队长越来越少移动，最终定住——聚类完成。

为什么它能收敛？每次"队长挪窝"之后，总的"跑路距离"（每个点到队长的距离之和）只会减少，不会增加。减不动了就停了。

两个要注意的坑

K 值要自己定

你得告诉算法分几堆。K 选小了，不同类的东西混在一起；K 选大了，同类的又被拆散了。常用"肘部法则"找合适的 K。

初始位置影响结果

随机插旗的位置不同，最终结果可能不一样，有时会卡在局部最优。实际中常多跑几次取最好的结果。

一步步构建 K-Means

第一步 生成数据 + 随机插旗

生成三个自然簇，从数据中随机挑 K 个点作为初始质心。不同的初始位置可能导致不同的最终结果。

第二步 分配：各找各妈

每个点算出到所有质心的距离，归入最近的那个。这是 K-Means 的核心操作。

第三步 更新：队长挪窝

每个质心移到它所有成员的均值位置。每次移动后总距离只减不增，保证最终收敛。

第四步 迭代直到收敛

反复执行"分配 + 更新"，质心不再移动时停止。通常只需几轮即可收敛。

四段拼在一起，加上可视化，就是完整演示代码——看下面。

02 代码

03 学术性讲解

形式化定义

给定数据集 X = {x₁, x₂, ..., xₙ}，K-Means 的目标是找到 K 个簇 C = {C₁, C₂, ..., C_K} 及其对应质心 μ₁, ..., μ_K，使目标函数最小：

J = Σ_k Σ_{x∈C_k} ‖x − μ_k‖²

其中 ‖x − μ_k‖² 是欧氏距离的平方，J 也称为簇内平方误差和（SSE / Within-Cluster Sum of Squares）。

算法伪代码

初始化：随机选 K 个质心 μ₁, ..., μ_K 重复： 分配步骤：对每个 xᵢ，令 cᵢ = argmin_k ‖xᵢ − μ_k‖² 更新步骤：令 μ_k = (1/|C_k|) Σ_{i:cᵢ=k} xᵢ 直到质心不再变化

收敛性

每次迭代后目标函数 J 单调不增，且状态空间有限（分配方案有限），故算法必然收敛——但只保证收敛到局部最优，不保证全局最优。

实践中常用 K-Means++ 初始化：以概率正比于 d(x, 最近已选质心)² 选取下一个质心，显著减少陷入差局部最优的概率。

距离度量

d(x, μ) = √(Σᵢ (xᵢ − μᵢ)²)

标准 K-Means 使用欧氏距离，若数据各维度量纲差异大，需先做标准化（z-score），否则量纲大的维度会主导距离计算。

K 值选择

肘部法则（Elbow Method）

绘制 K 与 SSE 的关系曲线，SSE 下降变缓的拐点即为合适的 K 值。

轮廓系数（Silhouette Score）

衡量簇内紧密度与簇间分离度，取值 [−1, 1]，越接近 1 越好。

业务约束

实际场景中 K 往往由业务需求决定（如将用户分为 3 个等级）。

复杂度

  • 时间复杂度：O(n · K · d · T)，其中 n 为样本数，d 为维度，T 为迭代次数
  • 空间复杂度：O(n · d + K · d)
  • 对大规模数据可使用 Mini-Batch K-Means，每次只用随机子集更新质心，大幅提速。

局限性

  • 假设簇形状为凸形，对环形、月牙形等非凸分布效果差
  • 对离群点敏感（离群点会强烈拉偏质心）
  • 需预先指定 K，且结果依赖初始化