3. K-means 算法原理简介

聊 K-means 之前，我先问大家一个问题：给你一堆点，你怎么把它们分成几堆？

这其实是我们做构象聚类的核心需求。分子动力学跑出几千几万个构象，你得找出哪些构象本质上是同一类。K-means 就是干这个的——它简单、高效，也是我入行时学的第一个聚类算法。

嗯，咱们先把它最核心的思想说清楚。

3.1 核心思想：近朱者赤

K-means 的想法特别直白：

• 假设我想把数据分成 K 个簇（群组）。
• 每个簇有一个「中心点」，叫质心（centroid）。
• 每个数据点属于离它最近的质心所在的簇。
• 然后不断调整质心的位置，直到簇不再变化。

说白了，就是让簇内的点尽量靠近，簇间的点尽量远离。

我在项目里第一次用 K-means 聚类蛋白构象时，心里还挺没底——这么简单的逻辑真的能区分开生物大分子的不同状态吗？结果跑完一看，嘿，效果出奇好。当然，前提是参数调对了。

3.2 距离度量：怎么才算「近」？

K-means 依赖距离来判断归属。最常见的距离是 欧氏距离（Euclidean distance）。

假设两个点在 n 维空间里的坐标分别是 x 和 y，那么：

d(x, y) = sqrt((x₁ - y₁)² + (x₂ - y₂)² + ... + (xₙ - yₙ)²)

你看，就是初中勾股定理的升级版。在构象聚类里，每个点往往代表一个构象的 RMSD 矩阵向量，或者主成分降维后的坐标。所以大家默认用欧氏距离。

距离类型	适用场景	个人经验
欧氏距离	连续型数值，构象坐标	大多数情况够用
曼哈顿距离	高维稀疏数据	我用过，聚类结果偏「方块」
余弦相似度	方向敏感，构象角度	不太常见，容易丢失幅度信息

3.3 算法步骤：四步走

K-means 的步骤非常清晰，我就直接上流程了。你想想看，它其实是在做一件很机械的事——反复猜测和修正。

1. 初始化：随机选 K 个点作为初始质心。
2. 分配：把每个数据点分配给最近的质心。
3. 更新：重新计算每个簇的质心（取所有点的均值）。
4. 检查收敛：如果质心不再变化（或变化极小），停止；否则回到第 2 步。

注意，这里每一步都很关键。我曾经因为初始化选到了离群点，导致整个算法陷入局部最优，跑了半天结果一团糟。后来我养成了习惯——每次初始化多跑几次，选效果最好的那一次。

下面这张图能帮你直观理解整个过程：

3.4 收敛条件与停止准则

怎么才算「收敛」？一般有三种判断方式：

• 质心变化很小：新旧质心之间的欧氏距离小于某个阈值（比如 1e-4）。
• 簇分配不再变化：所有点的归属和上一次完全相同。
• 达到最大迭代次数：以防死循环，我一般设 100 或 300 次。

3.5 算法的核心数学

K-means 的优化目标其实是一个损失函数——簇内平方和（Within-Cluster Sum of Squares, WCSS）。

J = Σ_{i=1}^{K} Σ_{x∈C_i} ||x - μ_i||²

其中 μ_i 是第 i 个簇的质心，C_i 是该簇所有点的集合。你想想看，这个 J 越小，说明簇内的点越紧凑，聚类效果理论上越好。

但这里有个坑：K-means 并不能保证找到 J 的全局最小值，它只保证收敛到一个局部最优。为什么？因为初始化质心的位置全靠运气。

我记得做第一个生物信息学项目时，同样的数据跑了 10 次 K-means，得到了 8 个不同的聚类结果。当时吓我一跳，后来才知道这是正常的——解决方案就是多跑几次，挑 J 最小的那一次用。

3.6 K 值的选择：一个永恒难题

K-means 需要你提前指定 K——你要分几类。但你事先可能根本不知道构象到底有几个状态。

常用方法：

方法	思想	我的评价
肘部法	画 J-K 曲线，找拐点	直观，但人工判断有主观性
轮廓系数	计算簇内紧密度 + 簇间分离度	更客观，但计算量大
Gap 统计量	比较真实数据与随机数据的 J 差距	理论扎实，码起来略复杂

3.7 优缺点一览

优点	缺点
算法简单，实现快	对初始质心敏感
适合大数据	只能发现球形簇，不能处理长条形簇
收敛速度快	K 值需要人为指定
可解释性强	对离群点敏感

3.8 避坑小结

• 标准化数据：不同维度的量级可能差很多，比如角度和距离放在一起，角度的小波动会把距离维的信息淹没。记得做归一化。
• 多次运行求最佳：前面说了，跑 10~20 次，每次用不同的随机种子，选 J 最小的结果。
• 小心空簇：如果一开始 K 设得太大，可能某些簇里一个点都没有。我的处理方式是：如果出现空簇，就重新初始化该簇。