K-means 聚类的原理是什么？

简化版

K-means 是最经典的聚类算法：把数据分成 K 个簇，让每个点归到离它最近的簇中心，并使簇内样本到中心的距离平方和最小。算法是迭代的两步走：① 分配——把每个点分到最近的簇中心；② 更新——把每个簇中心移动到该簇所有点的均值位置。重复这两步直到中心不再变化（收敛）。它简单、快、可扩展，但需要预先指定 K、对初始中心和离群点敏感、更适合发现紧凑、近似球形且尺度相近的簇、依赖特征缩放。目标函数（SSE / inertia）非凸，只能收敛到局部最优。

详细版

目标函数（最小化簇内平方和 SSE / inertia）：

minimize  J = Σₖ Σ_{x∈Cₖ} ‖x - μₖ‖²
   Cₖ = 第 k 个簇，μₖ = 第 k 簇的中心（均值）

迭代流程（Lloyd 算法）：

1. 初始化：随机选 K 个点作为初始簇中心
2. 重复直到收敛：
   ① 分配：每个点分到最近的簇中心 argminₖ ‖x-μₖ‖²
   ② 更新：每个簇中心更新为该簇所有点的均值
3. 中心不再移动（或达最大迭代）→ 停止

关键性质：

性质	说明
需指定 K	超参数，需肘部法/轮廓系数选
用欧氏距离	默认球形簇；需特征缩放
局部最优	SSE 非凸，结果依赖初始化
复杂度	O(n·K·d·迭代)，高效可扩展

保证收敛：每步都使 J 单调不增，有限步收敛（到局部最优）。

完整版教学

一、K-means 要解决什么——把数据分成 K 堆

K-means 是无监督聚类：没有标签，目标是把 n 个样本自动分成 K 个簇，使同一簇内的样本尽量相似（靠得近）、不同簇之间尽量不同（离得远）。

它用「到簇中心的距离」来衡量相似度：每个簇有一个中心（质心），一个点属于哪个簇，就看它离哪个中心最近。整个算法的目标是找到一组簇中心和分配方式，让所有点到各自簇中心的距离平方和（SSE）最小——SSE 越小，说明每个簇越紧凑。

二、目标函数：最小化簇内平方和

形式化目标是最小化簇内平方和（Within-Cluster Sum of Squares, 也叫 inertia / SSE）：

J = Σₖ₌₁ᴷ Σ_{x∈Cₖ} ‖x - μₖ‖²

内层：第 k 簇里每个点 x 到该簇中心 μₖ 的距离平方。
外层：对所有 K 个簇求和。
J 越小，簇越紧凑、聚类越好。

直接求最优分配是 NP 难的（组合爆炸），所以用迭代近似——这就是 Lloyd 算法。

三、迭代两步走：分配 + 更新

K-means 用一个简洁的交替优化过程逼近最优：

1. 初始化：随机选 K 个点当初始簇中心 μ₁...μ_K
2. 重复：
   ① 分配步（E 步）：固定中心，把每个样本分到离它最近的中心所在的簇
        cluster(x) = argminₖ ‖x - μₖ‖²
   ② 更新步（M 步）：固定分配，把每个簇中心移到该簇所有点的均值
        μₖ = (1/|Cₖ|) Σ_{x∈Cₖ} x
3. 直到簇中心不再变化（或分配不再改变）→ 收敛

直觉：先按当前中心分堆（分配），再把每堆的中心挪到堆的正中间（更新），如此往复——每挪一次中心，堆就更紧凑一点，直到稳定。

为什么更新步取均值？ 因为在平方距离下，使一组点到某点距离平方和最小的那个点，正是它们的均值（质心）。所以「中心 = 簇内均值」是每一步的最优解，这也是名字「means（均值）」的由来。

四、为什么一定收敛（但只到局部最优）

收敛性：分配步和更新步每一步都让目标 J 单调不增——分配步把点归到更近的中心（J 不增），更新步把中心移到均值（J 不增）。J 有下界（≥0）且单调不增，加上分配方式有限，所以有限步内必然收敛。

但只是局部最优：J 关于「分配 + 中心」是非凸的，不同的初始中心会收敛到不同的局部最优。所以 K-means 的结果依赖初始化——初始中心选得不好，可能得到很差的聚类。解决办法是多次随机初始化取最优，或用 K-means++ 智能初始化（详见 K-means 缺点专题）。

更严谨地说，标准 Lloyd 算法在固定距离、确定的并列处理和恰当处理空簇时，会在有限种分配间到达固定点；工程实现也常因容差或最大迭代数提前停止。若出现空簇，不同库可能保留旧中心或重新播种，因此结论要说明实现约定。

分配步：固定中心，选最近中心 -> J 不增
更新步：固定分配，平方欧氏损失下均值最优 -> J 不增
结论：目标不增；不等于达到全局最小值

五、关键特性与限制

必须预先指定 K：K 是超参数，选错簇数聚类就没意义。怎么选 K（肘部法、轮廓系数）是单独的问题。
用欧氏距离 → 只擅长球形簇：K-means 假设簇是凸的、大小相近的球形。对非球形（如月牙形、环形）、密度不均、大小悬殊的簇效果差——这类要用 DBSCAN 等。
对特征缩放敏感：距离被大尺度特征主导，量纲不可比时通常应标准化/归一化。
对离群点敏感：均值容易被离群点拉偏，一个极端点能把中心带跑（可用 K-medoids 用中位点缓解）。
高效可扩展：复杂度约 O(n·K·d·迭代)，对大数据友好，是它最大的实用优点。

六、常见追问

K-means 为什么可能得到差结果？ 目标非凸、依赖初始中心，可能陷入差的局部最优——多次初始化或 K-means++ 缓解。
更新步为什么用均值？ 平方距离下均值是使 SSE 最小的中心。
K-means 要标准化吗？ 要——基于欧氏距离，尺度不一会被大特征主导。
能稳定处理明显非凸簇吗？ 通常不能，用 DBSCAN、谱聚类等。
和 KNN 的区别？ K-means 是无监督聚类、K 是簇数、有训练（迭代求中心）；KNN 是有监督分类/回归、K 是邻居数、无训练（详见 K-means vs KNN 专题）。
inertia 能用来选 K 吗？ 能配合肘部法，但 inertia 随 K 增大单调下降，不能只看它（详见选 K 专题）。

七、用四个点算一轮 Lloyd 迭代

对一维点 [0,2,8,10] 取 K=2，初始中心为 0 和 10。分配后得到 C₁={0,2}、C₂={8,10}，更新中心为 1 和 9；此时 SSE 为 (0-1)²+(2-1)²+(8-9)²+(10-9)²=4。再次分配不变，因此达到一个固定点。

环节	固定什么	当前步骤为何不增大 SSE
分配	中心 μ	为每个点选平方距离最小的中心
更新	簇分配 C	均值最小化簇内平方距离和
停止	分配或改变量	达到容差、固定点或迭代上限

中心(0,10) → 分配 {0,2}/{8,10}
            → 均值更新 (1,9)
            → 分配不变 → 停止

实际实现还要处理空簇：某个中心若没有样本，均值无从计算，库可能重置到远点或采用自己的策略。精确 Lloyd 在确定 tie-breaking 下只有有限种分配，最终停止；浮点实现通常按中心变化或目标改善容差判断。

易错点：每一步对当前子问题最优，只能推出目标不增和收敛，不能推出全局最优。

八、常见误区与追问

误区：SSE 每轮下降就证明最后是全局最优。 交替优化面对非凸联合目标，只保证到达局部固定点。
误区：K-means 可以直接换成任意距离。 均值更新与平方欧氏距离配套；其他距离通常对应 K-medians 或 K-medoids。
追问：出现空簇怎么办？ 需按实现重置中心、拆分大簇或重新初始化，并记录可复现策略。
追问：停止条件有哪些？ 常见是标签不变、中心移动小于容差、目标改善很小或达到迭代上限。
追问：为什么多次初始化仍有价值？ 不同初始中心可能落到不同局部解，可降低一次坏初始化的风险。

九、加强记忆

K-means 把数据分成 K 个簇，目标是最小化簇内平方和 SSE Σ‖x-μₖ‖²（簇越紧凑越好）。用迭代两步（Lloyd）：① 分配——每点归到最近的簇中心；② 更新——中心移到簇内均值（因为平方距离下均值使 SSE 最小，这也是「means」由来）。每步 J 单调不增，必收敛但只到局部最优（J 非凸、依赖初始化，需多次随机或 K-means++）。关键限制：必须先定 K、用欧氏距离只擅长球形簇、对特征缩放和离群点敏感、必须标准化；优点是简单、快、可扩展。区别于 KNN：K-means 无监督、K 是簇数、要迭代训练。

简化版

详细版