Skip to content

K-means 聚类 ​

方法速览 ​

  • 主要用途 按特征相似度给无标签样本分组,并给出各组中心。
  • 必要输入 数值特征、可解释的欧氏距离尺度和候选簇数 K。
  • 适用条件 簇在欧氏空间中相对紧密,均值能够代表组内样本。
  • 典型不适用情况 簇形状明显弯曲、离群点主导距离,或主要特征为无序类别。
  • 最低限度的验证方式 比较不同初始化和相邻 K 的结果,核对成员稳定性与各组规模。

K-means 能回答什么 ​

有许多样本、没有现成标签时,可以先按已知特征把相近样本分组,得到每组的中心和一份成员名单。例如按客流量和停留时长对站点分群,随后为各群设计不同的调研方案。分群前要把“相近”说清楚。本例可以按标准化后两项特征的欧氏距离比较,但每个尺度都代表实际取舍。

它为什么交替做两件事 ​

给定群数 K,算法试图减小簇内平方距离之和。用 ci 表示第 i 个点的簇号,μk 表示第 k 簇中心。

J=∑i=1n∥xi−μci∥22.

先固定中心,让每个点加入最近的簇。再固定分组,把每个非空簇内各坐标的平均值当作新中心。这两步各自都不会使 J 增大。初始中心不同可能得到不同的局部结果,因此要用多次初始化并比较。若有空簇,需确认程序如何重新初始化该中心。scikit-learn 用户指南的 K-means 目标和迭代

适合哪些数据,何时换方法 ​

K-means 喜欢在欧氏空间中紧密、形状较规则且可用均值代表的组。离群点明显时,平方距离会把中心拉向极端值,可看看以样本为代表点的 K-medoids。若自然形状像两条弯曲的带状结构、还希望标记噪声点,比较 DBSCAN 并检查密度参数。若数据大多是无序类别,用整数把类别直接编码会引入虚假的大小和距离,宜选适合类别或混合变量的相异度及方法。

用等待时长做一个分组假设算例 ​

假设四个站点平均等待时长为 1,2,8,9 分钟,取 K=2,初始中心为 1 和 8。分配得到 {1,2} 与 {8,9},中心更新为 1.5 与 8.5。再次分配时成员不变,最终四个点离自己中心都差 0.5 分钟,故 J=4×0.52=1 分钟平方。若取 K=1,中心为 5,J=16+9+9+16=50。若取 K=4,每个点独占一组可使 J=0,但无法提供有价值的归纳。

如何选群数并核对结果 ​

固定特征定义和预处理,用几个相邻的 K 对比簇内距离、轮廓系数、各组规模与实际解释。再对样本重抽或对测量值加小幅扰动,看典型样本是否仍归在一起。簇号可以互换,先对齐簇或比较样本对是否同组。一组只有极少样本时,核对它是否由异常值形成。降到二维的图适合展示,但应回到原聚类空间验证。

容易影响解释的做法 ​

直接把米计的路程和分钟计的时长放在同一距离里,样本间数值差异较大的列容易主导距离。若两列近乎重复,它们会重复强调同一信息。固定一次随机种子便只留下单个结果,也无法观察稳定性。若决定沿用这次分群给新样本分组,应保存特征顺序、标准化参数和中心,并明确远离所有中心的样本如何处理。建议同时把中心转换回原始单位,方便解释两组在实际业务中的差异。

双语言实验 ​

假设九个服务点用两项同尺度指标描述。数据构造了三块紧密的区域,原始记录没有组名。固定 K=3,先按记录顺序选第 1、4、7 行为初始中心,再比较从第 1、2、7 行出发的过程。两次初始条件固定,便于在任一语言中重现整个轨迹。

为什么均值能让中心更新更好 ​

只看某个非空簇 S,记它的样本均值为 x¯S。对任意中心 μ 展开平方,有

∑i∈S∥xi−μ∥2=∑i∈S∥xi−x¯S∥2+|S|∥x¯S−μ∥2.

展开产生的交叉项因 ∑i∈S(xi−x¯S)=0 而消失。右侧第二项在 μ=x¯S 时取零,所以在固定分组时取均值最优。固定中心选择最近簇时,每个点也独立地取了最小距离。图中左侧连线表示中心如何移动,右侧从初始分配开始记录每一轮重新分配后的 J。观察下面的逐步演示,看看哪一步移动最大。

运行原理实现 ​

下载 Python 源码 · 下载 MATLAB 源码

  • Python 环境安装 python -m pip install numpy matplotlib 后,在下载目录运行 python mmf_kmeans.py。
  • MATLAB 在下载目录运行 result = mmf_kmeans(),用到基础 MATLAB 的隐式扩展,建议 R2016b 或更新版本,无需工具箱。

执行分配和均值更新,直到中心稳定。最终中心为 0.5、7.5,组内平方距离和 1;空簇保留其原中心。

最简版依赖 Python:NumPy。MATLAB:基础功能,无需额外工具箱。

在源码所在目录运行 python mmf_min_kmeans.py

py
import json
import numpy as np

x = np.array([0., 1., 7., 8.])
centers = np.array([0., 7.])
for _ in range(20):
    # 广播出「样本×中心」距离矩阵,每行选最近的一列。
    squared = (x[:, None] - centers) ** 2
    labels = squared.argmin(axis=1)
    updated = centers.copy()
    for cluster in range(len(centers)):
        members = x[labels == cluster]
        if members.size:
            updated[cluster] = members.mean()
    if np.array_equal(updated, centers):
        break
    centers = updated
else:
    raise RuntimeError("中心未稳定")
sse = float(((x - centers[labels]) ** 2).sum())
assert np.array_equal(centers, [.5, 7.5]) and sse == 1
result = {"centers": centers.tolist(), "groups": (labels + 1).tolist(), "sse": sse}
print("LAB_RESULT " + json.dumps(result, ensure_ascii=False))
下载当前源码

Python 用三维广播一次生成所有点与中心的坐标差;MATLAB 逐列填充“样本 × 簇”的距离矩阵,对整批样本减同一个中心。Python 索引从 0 开始,MATLAB 索引从 1 开始;两者都在距离相同时取最先出现的中心。实现遇空簇时保留原中心。比较两次运行先看 objective_trace 的首尾与轨迹,再看 same_cluster 矩阵。若某点从“簇 1”变成“簇 2”,但所有与它同组的点都没变,划分仍相同。

用标准函数复核 ​

Python 额外安装 scikit-learn。在两种语言里都明确给出初始中心、只拟合一次,并关掉重新选择初始化的比较干扰。MATLAB 的 kmeans 需 Statistics and Machine Learning Toolbox。这个数据中没有距离并列和空簇,终点可比较总簇内平方和 4 与同簇矩阵;成熟库的收敛判据和空簇策略需要单独查看。 scikit-learn KMeans 参数 · MathWorks kmeans 参数

python
import numpy as np
from sklearn.cluster import KMeans

# 每行一个点,两列是无须额外换算尺度的数值特征。
x = np.array([[1, 1], [1, 2], [2, 1], [4, 1], [4, 2], [5, 1],
              [8, 6], [8, 7], [9, 6]], dtype=float)
# Python 下标从零开始;采用给定三中心做一次 Lloyd 迭代求解。
model = KMeans(n_clusters=3, init=x[[0, 3, 6]], n_init=1, algorithm="lloyd").fit(x)
# inertia_ 是所有点到各自中心的平方距离和;同簇矩阵允许交换簇号。
print(model.inertia_)
print((model.labels_[:, None] == model.labels_).astype(int))
matlab
% 行是样本,列是特征;引号内的参数名用来对齐初值及距离类型。
X = [1, 1; 1, 2; 2, 1; 4, 1; 4, 2; 5, 1; 8, 6; 8, 7; 9, 6];
% MATLAB 行号从 1 开始,取第 1、4、7 行为中心。idx 存储每条记录的归属。
[idx, ~, sumd] = kmeans(X, 3, 'Start', X([1, 4, 7], :), ...
    'Replicates', 1, 'Distance', 'sqeuclidean');
% sumd 按簇存储平方距离和;再求和才得到全体目标值。
disp(sum(sumd))
disp(double(idx == idx.'))

参数练习 ​

看图中的两条轨迹。若初始中心选在同一区域,起始 J 更大,终点一定更差吗?运行两份代码的固定初值对照,再把横坐标特征乘以 10,保持中心仍从变换后的样本选取。

参考答案

原始样本的第一组初值给出 6→4,第二组为 37→14.8333→5.4583→4,最终划分相同。更差的初值在这个案例增加了更新次数。横坐标乘以 10 后,该列在平方距离里的权重相当于变为原来的 100 倍,哪怕分组相同,重新计算出的 J 也不能直接与原尺度的 J 比高低。实际业务需要先确定特征尺度,再比较初始化带来的变化。

关联文章 ​

MathModel FAQ · 数学建模知识库