K-Means Clustering

K-means 聚类是一种无监督学习算法，会将数据划分为 k 个组，每组由其质心表示，也就是分配到该组的点的均值。它会寻找组内距离平方和最小的划分方式，这个量称为惯性，因此同一组中的点会靠近其质心。标准流程是 Lloyd 算法；Stuart Lloyd 于 1957 年在贝尔实验室为信号量化开发了该算法，而“k-means”这个名称则源自 James MacQueen 1967 年发表的论文。由于简单、快速并且可扩展到数百万个数据点，k-means 是数据挖掘、压缩和探索未标注数据结构的常用工具。

算法的工作原理#

选择初始质心后，Lloyd 算法会交替执行分配步骤和更新步骤，直到簇不再变化：

1. 初始化： 选择 k 个初始质心。Scikit-learn 的默认方法 k-means++会随机选择第一个质心；之后每个质心的选取概率与它到最近已选质心的距离平方成正比，从而让初始点彼此分散。
2. 分配： 通常根据欧氏距离，将每个点分配给最近的质心。
3. 更新： 将每个质心移至当前分配给它的所有点的均值位置。
4. 重复： 返回分配步骤，直到没有点更换簇，或质心的移动距离小于容差。

这两个步骤都不会增加惯性，因此循环总会收敛，但只会收敛到由初始质心决定的局部最小值。寻找全局最优解属于 NP-hard 问题，因此实现通常会运行多次初始化，并保留惯性最低的结果。在 scikit-learn 的 KMeans中，使用 k-means++ 初始化时，默认的 n_init="auto" 只运行一次；随机初始化时则运行 10 次。

如何选择簇的数量#

K-means 需要预先指定 k。随着 k 增大，惯性总会下降，因为更多质心离数据点更近。因此，肘部法会绘制惯性随 k 变化的图表，并寻找下降趋势趋于平缓的位置。轮廓系数会比较每个点到所属簇的平均距离与到最近其他簇的平均距离，范围为 -1 到 1；簇越紧凑、分隔越清晰，分数就越高。以下示例针对从 2 到 6 的 k 计算分数，数据采样自四个中心周围：

from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
from sklearn.metrics import silhouette_score

# 600 unlabeled points drawn around 4 hidden centers
X, _ = make_blobs(n_samples=600, centers=4, cluster_std=1.0, random_state=7)

# Fit k-means for several k and score each partition
for k in range(2, 7):
    kmeans = KMeans(n_clusters=k, n_init="auto", random_state=0)
    labels = kmeans.fit_predict(X)
    print(f"k={k}  inertia={kmeans.inertia_:8.0f}  silhouette={silhouette_score(X, labels):.3f}")

惯性从 k=2 时的 18,363 降至 k=3 时的 5,241、k=4 时的 1,127，之后仅降至 k=5 时的 1,039 和 k=6 时的 922，因此肘部位于 k=4。轮廓系数也印证了这一点：它在 k=4 时达到峰值 0.811，在 k=5 时降至 0.687，从而找回数据采样时所用的四个中心。

假设和变体#

当簇大致呈球形、大小相近，并且在欧氏空间中彼此分离时，K-means 效果最佳。较大尺度的特征会对距离产生更大影响，因此通常会先对数据进行标准化。每个点都会被分到某个簇，少数极端离群点可能会将质心拉离所属数据组。以下几种变体可以放宽这些限制：

• 小批量 K-means： 根据随机抽取的小批量更新质心，以少量精度为代价，大幅加快大型数据集上的训练。
• K-medoids： 使用实际数据点作为簇中心，因此对离群点更稳健，并且适用于任意距离度量。
• 模糊 C-means： 受模糊逻辑启发，为每个点分配其属于各个簇的隶属度，而不是只将其硬性分配到一个簇。
• 高斯混合模型： 为每个簇拟合一个概率分布，因此可以表示大小各异的椭圆形簇，并返回软性概率分配。

在 AI 和计算机视觉中的应用#

• 颜色量化：对图像像素的颜色进行聚类，并将每个像素替换为其质心，可将拥有数千种颜色的照片缩减为包含 k 种颜色的调色板，从而压缩图像，并快速实现粗略的图像分割。
• 码本与向量量化：这些质心构成一个码本，每个向量都以其最近质心的索引形式存储。经典的视觉词袋图像检索方法，就是通过这种方式从局部图像描述符中构建词汇表的。
• 锚框设计：YOLOv2 对训练框的宽度和高度运行 k-means，并将 1 减去 IoU 作为距离，以选择其锚框。
• 权重量化调色板：使用 quantize=8 将 YOLO26 导出为 Core ML 时，会用 k-means 将每个大型权重张量中的值聚类为 256 个质心，因此导出的模型会为每个权重存储一个 8 位索引，以及一个小型查找表。
• 客户细分：零售商根据购买频率、购物篮规模和近期购买时间对客户分组，从而针对不同群体定制优惠。

K-Means 与相关算法的比较#

• K 近邻（KNN）：两者共用字母“k”，容易造成混淆。KNN 是一种监督算法，根据距离最近的 k 个已标记样本为新点分类；而 k-means 是无监督算法，k 表示它创建的簇数。
• DBSCAN：它按密度对点进行分组，自行确定簇的数量，能识别任意形状的簇，并将稀疏点标记为噪声，而不是强行将它们归入某个簇。
• 层次聚类：通过反复合并距离最近的组来构建嵌套簇树，因此之后可以在任意层级切割树来选择 k；代价是计算量至少会随点的数量呈二次增长。