4、聚类算法基础：K-means、Louvain、Leiden归纳总结
说到单细胞空间转录组的聚类，其实就三种主流思路：基于距离的、基于模块度的、以及基于模块度的改进版。我最早接触的是 K-means，觉得简单粗暴好用。后来做 Visium 数据才发现，空间邻域关系一加进来，K-means 就有点力不从心了。这时候 Louvain 和 Leiden 就派上用场了。下面我把这三兄弟掰开揉碎讲清楚。
4.1 K-means：快，但不聪明
K-means 的核心就是「距离」。每个点属于离它最近的那个中心点。迭代几步就收敛了。你想想看，在普通表达矩阵上，这招效率很高。
适用场景：数据量不大、期望快速原型验证、聚类形状接近球形时可以用。
我曾在一次测试中用 scikit-learn 跑 5 万细胞，10 次迭代就出结果，秒级完成。但后来在 Visium 空间切片上试，效果一言难尽——明明相邻的 spot 因为表达差异大就被分到不同簇，完全不考虑空间连续性。
K-means 步骤很简单：
- 指定 K 值（簇数量）
- 随机初始化 K 个中心
- 每个点分配到最近中心
- 重新计算中心（均值）
- 重复直到中心不再变化
缺点也明显：K 要提前定好，对初始值敏感，而且它假设簇是凸形的。这在空间转录组里经常不成立。
注意：标准化步骤千万别省。我遇到过基因表达量尺度差几个数量级，结果 K-means 全被高表达基因带偏了，聚类结果完全失真。
4.2 Louvain：引入图结构，效果翻倍
Louvain 的出现让我眼前一亮。它不再算点之间的距离，而是把细胞/spot 看作图的节点，用边的权重表达相似性。然后通过最大化「模块度」来划分社区。
模块度是什么？说白了就是：同一簇内的边应该比随机分布情况下更密集。Louvain 用两步迭代实现：
- 局部移动：遍历每个节点，把它移到使模块度增量最大的邻居社区；
- 网络聚合：把社区压缩成新节点，构建更粗粒度的图；
- 重复直到模块度不再增加。
我最早在 Visium 数据上跑 Louvain 时，发现它对分辨率参数很敏感。调高 resolution 就碎成小社区，调低就合并成大块。这个参数我一般用 scanpy.tl.louvain(resolution=1.0) 做起点，然后根据先验解刨结构微调。
建议：先用 KNN 建图，neighbors 数量设 15~30。邻居太少图太稀疏，太多则噪声引入。我做过对比测试，15 个邻居在多数 Visium 切片上表现稳定。
但 Louvain 有一个坑：它可能产生「弱连接社区」——一个社区内部只有几条边连着，其实不该被合并。这在后来的 Leiden 算法里被修复了。
4.3 Leiden：扫清 Louvain 的盲区
Leiden 算法是 Louvain 的作者之一 Traag 在 2019 年提出的改进版。我读过那篇论文（Traag et al., Sci Rep 2019），核心改进有两点：
- 保证社区连通性：每次移动后做「细化」步骤，确保社区内部是连通的，不会出现 Louvain 那种「被一条边连起来的孤立子团」；
- 速度更快：因为多了随机性，收敛次数反而减少。
我自己用 scanpy.external.tl.leiden 在 Visium 样本上跑过对比，同样 5000 个 spot，Leiden 耗时 0.8 秒，Louvain 1.2 秒，而且 Leiden 的社区内部同质性更高。
Leiden 的步骤比 Louvain 多一步「细化」：
- 局部移动（同 Louvain）
- 细化：找到当前社区内的子社区，确保每个子社区是强连通的
- 聚合：基于细化后的子社区建新图
- 重复
选型建议：在 Visium 项目中，我个人首选 Leiden。原因很简单：空间转录组数据本身噪声大，Louvain 容易产出不稳定的微小社区，而 Leiden 的结果更鲁棒，复查时基本不需要重跑。
4.4 三种算法核心对比
| 特性 | K-means | Louvain | Leiden |
|---|---|---|---|
| 是否需要预设K | 是 | 否（分辨率参数调节社区大小） | 否 |
| 数据依赖 | 原始表达矩阵 | 图（邻接矩阵或KNN图） | 图 |
| 簇形状假设 | 凸形 / 球形 | 任意形状（基于图） | 任意形状 |
| 速度（万级节点） | 极快（<1s） | 快（~1s） | 更快（~0.5s） |
| 是否保证社区连通 | 不适用 | 否 | 是 |
| 在Visium上推荐 | 不推荐 | 可用，需调参 | 强烈推荐 |
从表格可以清楚看到：K-means 适用场景很有限；Louvain 是经典选择但需额外检查社区质量；Leiden 在速度和可靠性上都是最优解。
我个人习惯：在 pipeline 前期快速探索时先用 Louvain 粗筛一遍分辨率，确定大致社区数目后，再用 Leiden 跑一次最终版本。这样既避免了盲目调参，又能利用 Leiden 的稳定性。
避坑：无论 Louvain 还是 Leiden，建图步骤的 n_neighbors 和 metric（距离度量）非常关键。我曾经默认用 metric='euclidean' 在小样本上跑得好，但换到大样本（10万+spot）时，必须改用余弦距离或相关性，否则图会过密，聚类结果几乎无区分度。
从流程图可以看到三者的本质区别：K-means 是纯向量空间方法，而 Louvain 和 Leiden 是图论方法。Leiden 额外多了一个「细化」步骤，这就是它比 Louvain 更可靠的原因。