k-means 在生物信息学中的应用

快速概览

k-means 是一种经典的划分式聚类算法，旨在将数据点分配到 k 个簇中，使每个点到其所属簇中心的平方距离之和最小。在生物信息学中，它常用于初步探索基因表达模式。

掌握 Lloyd 算法的"分配-更新"迭代过程
理解平方误差和（SSE）作为目标函数的物理意义
了解 k-means 在处理高维表达数据时的优势与局限
对比层次聚类与 k-means 的适用场景

所属板块 分析方向与案例

把基础对象与算法方法重新放回真实分析任务与工作流。

阅读目标 帮助建立阅读上下文

先判断这页与你当前问题的关系，再决定是否深入展开。

建议前置 先建立相关基础对象与方法直觉

建议先建立相关基础对象与方法直觉，再进入本页。

1. 要解决什么生物信息学问题？

在生物信息学中，k-means 要解决的核心问题是：如何在无标签的高维生物数据中自动发现具有相似行为的模式组？ 具体场景包括：

基因共表达分析：将成千上万个基因按照它们在多个实验条件（如不同时间点、不同组织、不同处理）下的表达模式进行分组，从而推断潜在的共同调控机制。
样本分型：在癌症研究中，将患者的表达谱聚类为不同的分子亚型，指导精准治疗。
单细胞转录组分群：将表达谱相似的细胞归为一类，识别不同的细胞类型或状态。

k-Means 聚类问题：给定一组高维向量（如基因在不同时间点的表达值）和簇数 $k$ ，找到一种划分方案，使平方误差和（Sum of Squared Errors, SSE） 达到最小。

2. 输入与输出

输入

一个 $n \times d$ 的数据矩阵 $X$ ，其中 $n$ 是样本（基因或细胞）数量， $d$ 是维度（实验条件或基因数量）。
预设的簇数 $k$ （ $1 \leq k \leq n$ ）。

输出

每个样本的簇分配标签 $\{1, 2, \ldots, k\}$ 。
$k$ 个簇中心 $\mu_1, \mu_2, \ldots, \mu_k$ 。

3. 核心思想与数学模型

k-means 的目标是找到一个划分 $C_1, C_2, \ldots, C_k$ ，使以下目标函数最小化：

$Cost(C_1, \dots, C_k) = \sum_{i=1}^{k} \sum_{x \in C_i} \| x - \mu_i \|^2$

其中 $\mu_i$ 是第 $i$ 个簇的几何中心（均值向量）：

$\mu_i = \frac{1}{|C_i|} \sum_{x \in C_i} x$

$\| x - \mu_i \|^2$ 是欧几里得距离的平方。这个目标函数也被称为组内平方和（Within-Cluster Sum of Squares, WCSS）。

与信息论的关联

目标函数可以重新解释为最小化数据点与其簇中心之间的”编码损失”。如果把每个数据点用其簇中心来”编码”（即用 $\mu_i$ 近似表示 $x$ ），那么 SSE 就是编码误差的总和。从这个角度看，k-means 本质上是在做向量量化（Vector Quantization）——用 $k$ 个原型向量来近似表示整个数据集。

4. 核心算法：Lloyd 算法

由于精确寻找全局最优解是 NP-难的，实际中通常使用启发式的 Lloyd 算法。

算法步骤

初始化：随机选择 $k$ 个点作为初始簇中心。
分配（Assignment）：将每个基因分配到距离其最近的中心所在的簇： $C_i = \{ x : \| x - \mu_i \| \leq \| x - \mu_j \|, \forall j \neq i \}$
更新（Update）：计算每个新簇中所有成员的平均值，将其设为新的簇中心。
收敛：重复步骤 2 和 3，直到中心不再发生显著变化（或达到最大迭代次数）。

算法特性

收敛性：算法保证在有限步内收敛。这是因为每次迭代中 SSE 是单调不增的，而可能的划分方案数量是有限的。
但不保证全局最优：结果高度依赖初始中心的选择。不同的初始化可能导致完全不同的聚类结果。
复杂度：每轮迭代的时间复杂度为 $O(n \cdot k \cdot d)$ ，其中 $d$ 是数据维度。在大规模表达矩阵上运行非常高效。

5. Worked Example：基因表达聚类

假设有 6 个基因在 2 个时间点的表达值如下：

基因	时间点 1	时间点 2
$g_1$	1	2
$g_2$	1	3
$g_3$	2	1
$g_4$	8	9
$g_5$	9	8
$g_6$	9	10

设 $k = 2$ 。

初始化：随机选择 $\mu_1 = g_1 = (1, 2)$ ， $\mu_2 = g_4 = (8, 9)$ 。

第一轮分配：

基因	到 $\mu_1$ 的距离	到 $\mu_2$ 的距离	分配
$g_1$ (1,2)	0	$\approx 9.9$	簇 1
$g_2$ (1,3)	1	$\approx 9.2$	簇 1
$g_3$ (2,1)	$\approx 1.4$	$\approx 9.2$	簇 1
$g_4$ (8,9)	$\approx 9.9$	0	簇 2
$g_5$ (9,8)	$\approx 9.9$	$\approx 1.4$	簇 2
$g_6$ (9,10)	$\approx 11.3$	$\approx 1.4$	簇 2

第一轮更新：

$\mu_1 = \frac{(1,2) + (1,3) + (2,1)}{3} = (1.33, 2.0)$
$\mu_2 = \frac{(8,9) + (9,8) + (9,10)}{3} = (8.67, 9.0)$

第二轮分配：结果不变，算法收敛。

最终聚类： $\{g_1, g_2, g_3\}$ （低表达簇）和 $\{g_4, g_5, g_6\}$ （高表达簇）。

6. 在基因表达分析中的应用

k-means 特别适合处理”扁平”的聚类任务：

共表达发现：将具有相似时间序列波动的基因聚在一起，暗示它们可能受相同的调控因子控制。
亚型识别：在癌症研究中，通过样本聚类识别具有不同表达特征的亚群。

实际使用建议

在生物信息学中应用 k-means 时，通常需要先对数据进行预处理：

标准化（Standardization）：对不同基因的表达值进行 Z-score 标准化，消除绝对表达水平的差异，聚焦于表达模式的相似性。
降维：在聚类前使用 PCA 等方法降低维度，减少噪声维度对距离计算的干扰。
多次运行：由于 k-means 对初始化敏感，应运行多次（如 50—100 次）并选择 SSE 最小的结果。

7. 局限性：生物学数据的复杂性

尽管常用，但 k-means 在生物信息学中面临以下挑战：

k 值的选择：用户必须预先指定 $k$ 。而在生物学实验中，真实的细胞类型或调控模块数量通常是未知的。
球形簇假设：k-means 假设簇在空间中呈球形分布。如果基因群的分布是长条形或螺旋形的，k-means 的效果会很差。
孤立点敏感：极端的表达值（离群点）会剧烈拉动簇中心的位置。
等大小簇假设：k-means 倾向于产生大小相近的簇，但生物学中的簇往往大小差异很大。

k 值选择方法

在实践中，以下方法常用于确定合适的 $k$ 值：

肘部法则（Elbow Method）：绘制 SSE 随 $k$ 变化的曲线，寻找 SSE 下降速度显著减缓的”拐点”。
轮廓系数（Silhouette Score）：衡量每个样本与其所属簇的紧密程度以及与最近邻簇的分离程度，范围是 $[-1, 1]$ 。
Gap Statistic：将实际数据的 SSE 与来自均匀分布的参考数据的 SSE 进行比较。

8. 复杂度与适用前提

时间复杂度

Lloyd 算法每轮迭代： $O(n \cdot k \cdot d)$
总时间复杂度（ $t$ 轮迭代）： $O(t \cdot n \cdot k \cdot d)$
空间复杂度： $O(n \cdot d + k \cdot d)$

适用前提

数据可以使用欧几里得距离进行有意义的比较。
簇的形状近似球形。
没有太多极端的离群点。

9. 与其他聚类方法的对比

特性	k-means	层次聚类	CAST
需要预设 k	是	否	否
距离度量	欧几里得	任意	任意
噪声鲁棒性	差	中等	较好
时间复杂度	$O(n \cdot k \cdot d)$	$O(n^2)$	$O(n^3)$

常见误区

"k-means 适用于所有类型的生物数据"：
k-means 使用欧几里得距离，这意味着它假设所有维度是等权重的且可比较的。对于基因表达数据，不同基因的表达量级可能差异巨大，如果不进行标准化，高表达基因会主导聚类结果。
"SSE 最小化等价于找到生物学上正确的聚类"：
SSE 是一个纯数学的优化目标，它并不直接反映生物学的"正确性"。一个 SSE 很低的聚类可能只是因为数据中存在一些技术性批次效应（Batch Effect），而非真实的生物学分组。
"k-means 结果可以用来直接推断基因调控网络"：
k-means 只能告诉你哪些基因的表达模式相似，但不能直接告诉你它们是否受到同一转录因子的调控。共表达是共调控的必要条件而非充分条件。

11. 与真实工具的连接

R 语言 stats::kmeans(): R 内置的 k-means 实现，使用 Hartigan-Wong 算法（Lloyd 算法的改进版本），适合中小规模数据。
scikit-learn KMeans: Python 中最常用的 k-means 实现，支持多种初始化策略（如 k-means++），并提供丰富的评估指标。
MCLUST: 基于高斯混合模型（GMM）的聚类工具。MCLUST 可以看作 k-means 的概率推广版本，不要求簇是球形等大小的。