机器学习学习笔记|K-means 聚类:从中心点到迭代优化(懒人only一张图版)
- 2026-05-10 14:31:11
0. 写在前面
最近学习了无监督学习中的 K-means 聚类算法。和监督学习不同，聚类问题没有提前给定标签，算法需要自己从数据中发现结构。可以先想一个简单例子：小明手里有一堆水果，比如苹果、香蕉和西瓜，但这些水果没有提前贴好标签。也就是说，小明只看到了“样本”，却不知道每个样本属于哪一类。此时，如果想把相似的水果自动分到一起，就可以使用聚类方法。K-means 就是其中非常经典的一种。（图像来自AI，憧憬美好生活）。
K-means 是最经典的聚类算法之一。它的思想非常直观：
给定聚类数 K，找到 K 个中心点，然后把每个样本分配给离它最近的中心。
简单来说，K-means 做的是：
用 K 个中心点代表整批数据，并让每个样本尽可能接近自己所属的中心。
这篇文章主要整理 K-means 的基本思想、目标函数、E-step、M-step，以及它在图像压缩中的应用。注意，第一次找到的中心点并不是说就是不同类的，举一个极端的例子，小明手里有苹果、香蕉、西瓜，选了3个中心点，全部都是西瓜，那么接下来如何解决分类呢？且看下面。
1. K-means 想解决什么问题？
假设我们有一批没有标签的数据：
每个样本都是一个向量。比如在二维空间中，一个样本可以表示为：
K-means 的目标是把这些样本分成 个簇：
理想情况下：
同一个簇内部的样本尽量相似； 不同簇之间的样本尽量不同。
例如，在二维平面上，如果数据天然形成几团，K-means 就希望自动把这些点分成几类。
那么接下来我们就会很自然想到几个问题：
k为多少时，分类效果最好
在给定k时，如何得到最好的分类效果
2. K-means 的基本思想：找 K 个中心
K-means 的核心思想是：
每个簇都可以用一个中心点来代表。
第 个簇的中心通常记作：，其中， 表示第 个聚类中心。
算法会反复做两件事：
把每个样本分配给最近的中心； 根据当前分配结果，重新计算每个簇的中心。
也就是说：
初始化中心↓分配样本↓更新中心↓再次分配样本↓再次更新中心↓直到中心基本不变3. 0-1 指示变量
为了使用数学形式来表示样本属于哪个簇，即我们把样本分到哪个类，我们引入一个0-1指示变量：
其中：
表示第 个样本；
表示第 个簇；
如果样本属于第 个簇，则;
如果样本不属于第 个簇，则;
例如，如果有 个簇，某个样本 属于第 2 个簇，那么：
这就是所谓的 1-of-K coding。
因为 K-means 是硬聚类，每个样本只能属于一个簇，所以对任意样本 ，都有：
这表示：
每个样本在 个簇中必须且只能选择一个。
这种分配方式也叫：
也就是硬分配。
那么同理，也有软分配，在软分配中，在软分配中，每个数据点可以被分配到多个不同的类别或簇，并且分配是基于概率或权重的。 这意味着每个数据点可以以不同程度属于不同的类别或簇，而不仅仅是一个类别。
简单举一个例子，一张图片中的某个像素也可以有“属于红色类 70%，属于橙色类 30%”这样的概率式归属。
4. Distortion Measure：K-means 的目标函数
K-means 的目标函数通常叫 distortion measure，可以翻译成“失真度量”。
它衡量的是：
所有样本到自己所属聚类中心的距离平方和。
K-means 的目标函数写作：
逐项解释：
：总失真，也就是 K-means 要最小化的目标； ：样本总数； ：聚类数量； ：第 个样本； ：第 个聚类中心； ：样本 是否属于第 个簇； ：样本 到中心 的平方欧氏距离。
由于 只有 0 或 1，所以对每个样本来说，只有它所属的那个簇会产生距离损失。
例如，如果 属于第 2 个簇，那么：
其他：
于是目标函数中和 有关的部分只剩：
所以 K-means 实际上是在最小化：
每个样本到自己所属中心的平方距离总和。
也就是：
5. 为什么不能直接一次求出最优解？
从目标函数看，K-means 要同时求两类变量：
样本的分配变量：
聚类中心：
问题在于，这两个量互相依赖。
如果我们知道了聚类中心 ，那么样本应该分给哪个簇就很容易判断：
离哪个中心最近，就属于哪个簇。
但如果我们知道了样本分配 ，那么每个簇的中心也很容易计算：
中心就是该簇样本的均值。
所以 K-means 采用交替优化的方法：
固定中心，更新样本分配固定样本分配，更新中心这就对应 K-means 中的 E-step 和 M-step。
6. E-step：固定中心，更新分配
在 E-step 中，我们假设聚类中心已经固定：
此时要做的是：对每个样本 ，决定它应该属于哪个簇。
对样本 ，分别计算它到每个中心的距离：
然后选择距离最近的那个中心。
数学上写作：
这句话的意思是：
如果第 个中心是离 最近的中心，那么 ；否则 。
所以 E-step 可以理解成：
中心不动，让每个样本重新选择最近的中心。
7. M-step：固定分配，更新中心
在 M-step 中，我们假设样本分配已经固定：
此时要做的是：重新计算每个簇的中心。
第 个簇的目标是最小化：
对 求导。
先展开思路：当 时，说明样本 属于第 个簇；当 时，该样本不会影响第 个中心。
所以第 个中心只由属于第 个簇的样本决定。
对目标函数求导：
可以得到：
整理：
由于 对 不变，所以：
因此：
这个公式非常直观：
新中心 = 当前簇中所有样本的平均值。
所以 K-means 中的 “means” 指的就是均值。
M-step 可以理解成：
样本归属不动，让每个中心移动到当前簇样本的平均位置。
8. K-means 完整算法流程
K-means 的完整流程如下：
输入：样本数据 X，聚类数 K1. 随机初始化 K 个聚类中心 μ1, μ2, ..., μK2. 重复以下步骤： E-step： 对每个样本 xn，计算它到每个中心的距离， 并把它分配给最近的中心。 M-step： 对每个簇 Ck，重新计算簇内样本均值， 并把该均值作为新的中心 μk。3. 直到聚类中心基本不变，或者目标函数 J 的变化很小。输出：聚类中心 μk 和每个样本的簇标签。用公式表示，就是反复执行：
和：
9. 一个一维小例子
假设有 6 个一维样本：
我们希望把它们分成：
一开始随机选择两个中心：
第一次 E-step
计算每个样本离两个中心的距离。
显然：
离 更近； 离 更近。
所以得到：
第一次 M-step
更新中心：
所以新的中心是：
再次执行 E-step，样本分配不会变化。
于是算法收敛。
最终结果是：
10. 为什么 K-means 会收敛？
K-means 每一步都会让目标函数 不增加。
10.1 E-step 为什么不会让 变大？
在 E-step 中，中心固定。
对每个样本来说，把它分配给最近的中心，一定不会比把它分配给其他中心更差。
也就是说：
一定小于等于任意一个固定分配带来的距离。
所以 E-step 会让 下降或保持不变。
10.2 M-step 为什么不会让 变大？
在 M-step 中，样本分配固定。
对于每个簇，最小化簇内平方误差的中心点就是该簇样本的均值。
也就是说：
是当前分配下使平方误差最小的点。
所以 M-step 也会让 下降或保持不变。
10.3 收敛到哪里？
由于每一步都会让目标函数不增加，K-means 会逐渐稳定。
但是需要注意：
K-means 只能保证收敛到局部最优，不保证找到全局最优。
原因是它是一个迭代优化算法，最终结果会受到初始中心的影响。
11. K-means 的时间复杂度
假设：
是样本数； 是聚类数； 是迭代次数； 是特征维度。
每一轮 E-step 需要计算每个样本到每个中心的距离，复杂度大约是：
如果迭代 轮，则总复杂度大约是：
如果维度 固定，可以简写为：
这也是 K-means 比较高效的原因。
12. K-means 的优点
K-means 的优点主要有：
12.1 思想简单
K-means 的核心就是：
找中心分配样本更新中心非常容易理解。
12.2 计算速度快
K-means 每一轮主要是距离计算和均值更新，因此效率较高。
12.3 容易实现
用 Python 或 sklearn 几行代码就可以完成基本聚类。
12.4 适合球形簇
如果数据本身是一团一团的、近似球形的，K-means 通常效果不错。
13. K-means 的缺点
K-means 虽然经典，但也有明显限制。
13.1 需要提前指定
K-means 必须提前给定聚类数：
但在真实任务中，我们往往不知道数据应该分成几类。
常见选择 的方法有：
常见选择 的方法主要有以下几种。
13.1.1 肘部法则
肘部法则的核心思想是观察不同 下的簇内误差平方和，也就是 SSE：
一般来说，随着 增大，SSE 会不断下降。
这是因为簇的数量越多，每个样本离自己的聚类中心通常越近。
极端情况下，如果：
也就是每个样本自己成为一个簇，那么 SSE 可以降到 0。
但是我们不能简单选择 SSE 最小的 ，否则会得到过多的簇。
所以肘部法则关注的是：
当 增大时，SSE 的下降速度在哪个位置开始明显变慢。
这个位置就像曲线上的“手肘”，因此叫肘部法则。
例如：
可以看到，从 到 ，SSE 下降很快；但从 之后，下降幅度明显变小。
因此我们可能选择：
肘部法则的优点是直观，缺点是有时候“肘部”并不明显，需要结合经验判断。
13.1.2 轮廓系数
轮廓系数，也叫 Silhouette Coefficient，通常记作 SC。
它同时考虑两个方面：
簇内是否紧密； 簇间是否分离。
对于样本 ，定义
表示样本 到同簇其他样本的平均距离。再定义：
表示样本 到最近的其他簇中所有样本的平均距离。那么样本 的轮廓系数为：
整体聚类结果的轮廓系数为：
轮廓系数的取值范围是：
一般来说：
因此，我们可以尝试多个 ，计算每个 对应的平均轮廓系数，然后选择 SC 较大的 。
例如：
这时可以选择：
因为它对应的轮廓系数最高。
需要注意的是，轮廓系数更偏好紧凑、分离明显的簇。如果数据是非凸形状，比如月牙形、环形，那么 SC 可能会误判聚类效果。
13.1.3 CH 指数
CH 指数全称是 Calinski-Harabasz Index。
它的核心思想是比较：
类间离散度 和 类内离散度 的比例。
简单来说：
类内越紧凑越好； 类间越分散越好。
CH 指数可以写成：
其中：
表示类间平方和； 表示类内平方和； 是聚类数； 是样本数。
类间平方和可以理解为：
每个簇的中心和整体数据中心之间的距离平方和。
类内平方和可以理解为：
每个样本到自己所属簇中心的距离平方和。
所以 CH 指数越大，说明：
簇内越紧凑，簇间越分离。
因此，在选择 时，可以尝试多个 ，选择 CH 指数较大的那个（说实话，长得有点像ANOVA的F）。
例如：
这时可以选择：
因为它对应的 CH 指数最大。
CH 指数的优点是计算速度快，适合比较不同 下的聚类效果。但它和 SSE、SC 一样，也更适合近似球形、分离明显的数据。
13.1.4 DB 指数
DB 指数全称是 Davies-Bouldin Index。
它衡量的是：
每个簇和与它最相似的另一个簇之间的平均相似程度。
DB 指数的形式可以写成：
其中：
表示第 个簇内部样本到簇中心的平均距离； 表示第 个簇内部样本到簇中心的平均距离； 表示两个簇中心之间的距离。
可以看到，如果簇内部很分散，那么 和 会变大。
如果两个簇中心很近，那么 会变小。
这两种情况都会让 DB 指数变大。
因此：
DB 指数越小，说明聚类效果越好。
例如：
这时可以选择：
因为它对应的 DB 指数最小。
13.1.5 业务经验
除了数学指标，业务经验也很重要。
因为聚类本身是无监督学习，没有绝对正确的标签。
有时候某个指标认为 最好，但从实际解释角度看， 可能更合理。
比如用户分群中，我们可能希望把用户分成：
高价值用户； 普通用户； 低活跃用户。
这时即使某些指标推荐更多类别，业务上也可能更倾向于选择：
再比如图像压缩中， 的选择往往和图像质量、压缩率有关：
小，压缩率高，但图像失真明显； 大，图像更接近原图，但压缩效果变弱。
所以选择 时，不应该只看一个指标，而应该结合：
肘部法则； 轮廓系数； CH 指数； DB 指数； 可视化结果； 业务解释性。
更稳妥的做法是：
用多个指标作为参考，再结合实际任务选择一个可解释、稳定、效果较好的 。
13.2 对初始化敏感
K-means 的初始中心通常是随机选的。
不同初始中心可能导致不同结果。
如果初始中心选得不好，算法可能收敛到较差的局部最优。
为了解决这个问题，实践中常用：
K-means++ 的思想是：
初始中心尽量分散一些，避免多个中心一开始落在同一片区域。
13.3 对异常点敏感
K-means 使用平方距离：
平方距离会放大远离中心的点。
例如，正常点到中心的距离是 2，则平方距离是：
异常点到中心的距离是 20，则平方距离是：
一个异常点可能对中心产生很大影响。
因此，K-means 对噪声和离群点比较敏感。
13.4 不适合非凸形状
K-means 假设每个簇可以用一个中心点表示。
这意味着它更适合：
球形簇； 凸形簇； 大小差不多的簇； 密度差不多的簇。
但它不适合：
月牙形； 环形； 长条形； 螺旋形； 复杂流形结构。
例如两个弯月形簇，K-means 可能会按照中心距离把它们切错。
这种情况下，可以考虑：
DBSCAN（如果用一个make_moon数据的python库会发现挺有意思的）； HDBSCAN； Spectral Clustering； Kernel K-means。
13.5 不适合不同规模和不同密度的簇
如果一个簇很大，另一个簇很小，K-means 可能会偏向把大簇切开。
如果一个簇很密，另一个簇很稀疏，K-means 也可能分得不好。
原因是 K-means 使用统一的距离中心原则，不能很好处理不同密度结构。
14. K-means 和 KNN 的区别
K-means 和 KNN 名字很像，但它们完全不同。
一句话区分：
K-means 是找中心分组，KNN 是找邻居投票。
15. K-means 和 EM 的关系
从形式上看，K-means 的迭代过程和 EM 算法很像。
K-means 中有：
E-step：固定中心，更新样本属于哪个簇； M-step：固定样本分配，更新聚类中心。
但是 K-means 是硬分配：
也就是说，每个样本只能属于一个簇。
而在 GMM(高斯混合模型，可以粗略认为是混在一起的正态分布) 中，样本属于某个高斯成分的概率通常写作：
其中：
这是一种软分配。
对比一下：
所以可以把 K-means 理解为一种特殊的 hard EM。
16. K-means 在图像压缩中的应用
K-means 还可以用于图像压缩。
一张彩色图片由很多像素组成，每个像素都有 RGB 三个通道：
因此，每个像素都可以看成一个三维样本点。
如果一张图片有很多像素，那么就可以得到一个样本集合：
其中每个 都是一个 RGB 向量。
16.1 用 K-means 压缩颜色
假设设置：
那么 K-means 会在 RGB 空间中找到 8 个颜色中心：
然后，每个像素都被替换成离它最近的颜色中心。
也就是说：
原来可能有几十万种颜色↓K-means 找到 K 个代表颜色↓每个像素替换成最近的代表颜色↓图像颜色数量大幅减少这样就实现了图像颜色压缩。
16.2 为什么这是有损压缩？
这种压缩是有损的。
因为多个不同颜色会被替换成同一个中心颜色。
例如，原来三个像素颜色是：
压缩后可能都变成：
此时再想恢复原始颜色，就已经不可能了。
所以 K-means 图像压缩只能恢复近似图像，不能完全还原原图。
17. Python 简单实现
下面用 sklearn 实现一个简单的 K-means 聚类。
from sklearn.datasets import make_blobsfrom sklearn.cluster import KMeansimport matplotlib.pyplot as plt# 生成模拟数据X, y_true = make_blobs( n_samples=520,##### centers=4, cluster_std=0.60, random_state=0)# 建立 K-means 模型kmeans = KMeans( n_clusters=4, random_state=0, n_init=10)# 训练并预测聚类标签labels = kmeans.fit_predict(X)# 获取聚类中心centers = kmeans.cluster_centers_# 可视化plt.scatter(X[:, 0], X[:, 1], c=labels, s=50, cmap="viridis")plt.scatter(centers[:, 0], centers[:, 1], c="black", s=200)plt.show()这段代码做了几件事：
使用 make_blobs生成二维聚类数据；设置聚类数 n_clusters=4；使用 K-means 训练模型； 得到每个样本的聚类标签； 画出聚类结果和聚类中心。
18. 总结
K-means 是一种经典的无监督聚类算法。
它的核心思想是：
用 个中心点代表数据，并让每个样本尽可能接近自己所属的中心。
它的目标函数是：
其中：
是 0-1 指示变量； 是第 个聚类中心； 衡量所有样本到所属中心的距离平方和。
K-means 的迭代过程可以概括为：
E-step：固定中心，分配样本M-step：固定分配，更新中心它简单、高效、容易实现，但也有明显缺点：
需要提前指定 ； 对初始化敏感； 对异常点敏感； 不适合非凸簇； 不适合不同规模、不同密度的簇。
如果一句话总结 K-means：
K-means 就是在不断调整“样本属于哪个中心”和“中心应该移动到哪里”，直到簇内距离尽可能小。
