K-Means 聚类详解：算法原理 + 迭代过程图解 + C++ 实现 + 如何选 K（肘部法则）

一、引言

如果你手上只有一堆数据点，但没有任何标签，想让机器自己把相似的点归到一起，这就是「聚类」要做的事。K-Means 是无监督学习里最常用、也最容易讲清楚的聚类算法。本文从原理、两步迭代过程、完整可编译的 C++ 代码、复杂度，到「如何选 K」和算法局限，一次讲透。文中过程图来自码路星球的可视化演示（C++算法可视化，免费）。

二、算法原理：无监督聚类

K-Means 解决的问题是：给定 n 个二维点，把它们自动分成 k 组，使组内的点尽量靠近——事先不知道标签，所以是「无监督」。

它的全部精髓就是反复做两件事：

1. 分配（Assignment）：把每个点，分给离它最近的那个中心（按欧氏距离）。
2. 更新（Update）：把每个中心，移动到「分给它的那些点」的平均位置（质心）。

两步交替迭代，直到中心不再移动——聚类就稳定了。

三、分配 / 更新两步迭代图解

把演示里发生的事拆开看：

• 初始化：放下 k 个簇中心（可视化里是菱形），所有点暂时是灰色、未分配。
• 分配步：一个点一个点地，算它到各中心的距离，归到最近的中心并染上对应颜色——你能看到点逐个「选边站」。
• 更新步：每个中心「滑」到自己那堆同色点的中间（质心）。
• 然后再分配、再更新……几轮之后没有点再换簇、中心也不动，聚类完成。
  
  

为什么一定会收敛？每一步都在让「点到自己中心的总距离」变小（不会变大），而这个值有下界，所以一定会停下来。

四、完整可编译的 C++ 实现（带注释）

下面是核心骨架，对应演示里展示的kmeans流程，并补全成可直接编译运行的完整片段：

#include<bits/stdc++.h>usingnamespacestd;structPoint{doublex,y;intcluster=-1;};// 欧氏距离的平方（比较大小用平方即可，省一次开方）doubledist2(constPoint&a,constPoint&b){doubledx=a.x-b.x,dy=a.y-b.y;returndx*dx+dy*dy;}// 找离 p 最近的中心，返回其下标intnearest(constPoint&p,constvector<Point>&centers){intbest=0;doublebd=numeric_limits<double>::max();for(intj=0;j<(int)centers.size();j++){doubled=dist2(p,centers[j]);if(d<bd){bd=d;best=j;}}returnbest;}// 把第 j 个中心移到簇 j 的均值（质心）；移动了返回 trueboolmoveToMean(Point&center,constvector<Point>&pts,intj){doublesx=0,sy=0;intcnt=0;for(constauto&p:pts)if(p.cluster==j){sx+=p.x;sy+=p.y;cnt++;}if(cnt==0)returnfalse;// 空簇：本轮不动（工程上需特殊处理）doublenx=sx/cnt,ny=sy/cnt;boolmoved=(nx!=center.x||ny!=center.y);center.x=nx;center.y=ny;returnmoved;}voidkmeans(vector<Point>&pts,vector<Point>&centers,intk){while(true){for(auto&p:pts)// ① 分配p.cluster=nearest(p,centers);// 归到最近的中心boolmoved=false;for(intj=0;j<k;j++)// ② 更新moved|=moveToMean(centers[j],pts,j);// 中心移到簇均值if(!moved)break;// 中心不动 → 收敛}}intmain(){vector<Point>pts={{60,60},{90,55},{270,60},{300,55},{60,232},{90,225},{270,232},{300,228}};vector<Point>centers={{120,55},{150,58},{180,55},{210,58}};// 4 个初始中心intk=(int)centers.size();kmeans(pts,centers,k);for(auto&p:pts)printf("(%.0f,%.0f) -> 簇 %d\n",p.x,p.y,p.cluster);return0;}

代码与演示里展示的核心循环一致：for (auto& p : pts) p.cluster = nearest(...)是分配，moved |= move(centers[j], mean(pts, j))是更新，if (!moved) break;是收敛判定。

五、复杂度分析

每轮迭代要算 n 个点到 k 个中心的距离，是O(n·k)；跑 t 轮就是O(n·k·t)（n 点、k 簇、t 轮迭代）。空间O(n + k)。通常 t 不大，所以很快——这也是它流行的原因之一。

六、如何选 K（肘部法则）与局限

• K 要你自己定：K-Means 不会告诉你该分几类。常用「肘部法则」——画出不同 k 对应的簇内误差，找误差下降明显放缓的「拐点」，就是合适的 k；也可用轮廓系数辅助。
• 初始值敏感：初始中心选得不好，可能收敛到差的局部最优。工程上常随机多跑几次取最优，或用k-means++更聪明地选初始点。
• 形状假设：它假设簇是「球形、大小相近」的。遇到环形、长条形的簇会失灵——那时考虑DBSCAN、谱聚类。
• 量纲问题：不同特征量纲差太多（比如「年龄 0-100」和「收入 0-100万」），距离会被大尺度特征主导，先做归一化。

七、小结

K-Means = 分配 + 更新两步交替，迭代到收敛；复杂度 O(n·k·t)，简单高效；关键在于选对 K、处理好初始化、注意球形假设和归一化。把这两步「画出来」看，比读十遍公式都直观。本文的过程图来自码路星球的 C++ 算法可视化：（我不慌----成长杂货铺：https://wobuhuang.com）