dropClust：高效聚类大规模单细胞RNA数据
在现代单细胞研究中，动辄数十万甚至上百万细胞的数据集已成为常态。面对如此庞杂的基因表达矩阵——每行是一个细胞，每列是一个基因，绝大多数数值为零（dropout事件频繁发生）——如何快速、准确地识别出不同的细胞类型？尤其是那些丰度极低、却可能具有关键生物学意义的稀有细胞群体？
这正是dropClust试图解决的核心问题。
传统的聚类方法在处理超大规模单细胞RNA测序（scRNA-seq）数据时往往力不从心。以Seurat为代表的基于最近邻图的方法虽然精度高，但其两两细胞间相似度计算的时间复杂度接近 $O(n^2)$，当细胞数量突破数万后，内存和时间开销迅速变得不可接受。而简单的随机采样虽能降维提速，却极易丢失稀有细胞类型的代表性样本，导致后续分析出现偏差。
dropClust 提出了一种全新的“先结构保持采样，再扩展分配”的两阶段范式，在保证聚类质量的同时实现了显著的效率提升。它不仅跑得快，还能“看得清”那些容易被忽略的小簇。
整个流程围绕四个关键技术点展开：局部敏感哈希加速近邻搜索、结构保持采样（SPS）、GMM驱动的关键基因筛选，以及层次聚类与后验标签传播的结合。下面我们一步步拆解这个设计精巧的算法框架。
以经典的68k PBMC 数据集为例，原始数据包含68,579 cells × 32,738 genes，其中高达98.33% 的表达值为0，典型的高维稀疏场景。dropClust 的处理流程始于标准预处理步骤：
- 基因过滤：仅保留至少在3个细胞中表达量≥3 UMI的基因，将基因数从约3.2万压缩至约7000；
- 细胞标准化：采用总UMI归一化策略，即每个细胞的表达值除以其自身总UMI数，再乘以所有细胞总UMI数的中位数，消除文库大小差异；
- 高变基因选择（HVGs）：选取变异系数（CV = 标准差 / 均值）最高的前1000个基因，聚焦最具生物学异质性的信号；
- 对数变换：使用 $\log_2(x + 1)$ 缓解极端值影响，使分布更平稳。
至此，我们得到了一个相对干净且信息丰富的子矩阵，为后续高效聚类打下基础。
真正的创新始于Structure Preserving Sampling（SPS）策略。不同于传统随机采样“一刀切”，SPS的目标是：在有限采样预算下，尽可能保留原始数据中的拓扑结构，特别是小簇的完整性。
具体分为两步：
首先，从全集中抽取约1/3或不少于20,000个细胞作为初始子集 $C_s$。在这个子集上，dropClust 使用LSHForest（局部敏感哈希森林）构建近邻图。LSHForest是一种近似最近邻搜索技术，通过多棵哈希前缀树实现快速候选邻居定位，避免了全量距离计算。相比暴力搜索，其查询效率可达 $O(n \log n)$ 量级。
接着，基于LSHForest生成的相似性关系构建加权图，并应用Louvain社区发现算法进行初步聚类。此时得到的可能是粗粒度的大簇，例如原本14种细胞类型被合并成6个组，但重要的是——所有细胞类型都已被初步捕获，没有因采样偏差而完全丢失。
第二步才是SPS的灵魂所在：指数递减采样。
在每个初聚类簇 $i$ 中，采样比例由如下函数决定：
$$
r_i = r_{\min} + (r_{\max} - r_{\min}) \cdot e^{-\alpha \cdot s_i}
$$
其中 $s_i$ 是该簇的细胞数量，$\alpha$ 控制衰减速率，$r_{\min}$ 和 $r_{\max}$ 设定采样率边界。显然，簇越小，采样率越高。这种机制确保了即使某个细胞类型只占整体的1%，也能在最终采样子集中获得足够的代表。
参数 $\alpha, r_{\min}, r_{\max}$ 可通过模拟退火等优化策略自动调整，使得最终采样总数满足用户设定目标（如5,000个细胞）。实验表明，这种策略显著提升了 minor cell types 的检出率，远优于均匀采样。
完成结构保持采样后，接下来是对基因维度的进一步压缩。毕竟，即便只剩5,000个细胞，若仍保留上千个基因，聚类成本依然可观。
dropClust 在此引入了一个巧妙的设计：PCA + 高斯混合模型（GMM）联合筛选判别性最强的基因。
具体做法是：
1. 对采样后的表达矩阵进行主成分分析（PCA），提取前50个主成分（PCs）；
2. 对每个PC上的投影值拟合GMM，判断其是否呈现多模态分布（组件数 ≥3）；
3. 仅保留那些能够区分多种模式的PC；
4. 将这些PC反向映射回基因空间，选出贡献最大的前200个基因。
直观来看，如果某个PC能清晰分隔不同细胞状态，则其所依赖的基因大概率是关键调控因子。这种方法比单纯按方差排序更具生物学解释性，也更能捕捉非线性结构。
最终，数据被压缩至一个“小而精”的矩阵，例如5,000 × 200，为下一步聚类扫清障碍。
在此精简数据上，dropClust 直接运行平均连接层次聚类（Average-Linkage Hierarchical Clustering）。
- 使用欧氏距离衡量细胞间差异；
- 合并策略采用 average linkage：两个簇之间的距离定义为成员间所有成对距离的均值，相较于单连接更稳健，不易产生链式效应；
- 自底向上构建聚类树（dendrogram），并通过动态剪枝或肘部法则确定最优簇数。
由于数据规模已大幅缩减，即使是 $O(n^2)$ 复杂度的算法也能在合理时间内完成。更重要的是，由于输入数据经过SPS和基因筛选双重优化，聚类结果的质量反而更高。
聚类完成后，真正的挑战才开始：如何将剩余的六万多未采样细胞归属到已有类别中？
直接重新聚类显然不可行。dropClust 采用了一种高效的后验标签传播机制：
- 利用已聚类的采样细胞训练一个新的 LSHForest 模型，建立索引；
- 对每个未采样细胞 $c_u$，执行 LSH 查询，返回其 k=5 个最近邻；
- 统计这5个邻居所属的聚类标签频次；
- 将 $c_u$ 分配给出现频率最高的那个簇。
本质上，这是一种基于投票的局部一致性假设：相似的细胞应属于同一类。由于LSH查询本身非常高效，整个分配过程可批处理完成，时间复杂度远低于重新建图聚类。
这一机制实现了“以小见大”的效果——用少量高质量样本引导全局分类，既节省资源又保持连贯性。
那么，dropClust 的实际表现究竟如何？
在68k PBMC数据集上，它成功识别出14个稳定簇，分别对应CD4+/CD8+ T细胞、B细胞、NK细胞、单核细胞、树突状细胞、巨核细胞等主要免疫细胞类型。t-SNE和UMAP可视化显示各簇边界清晰，结构分明。
更重要的是，它的聚类一致性（Adjusted Rand Index, ARI）达到0.87，显著优于Seurat（0.82）、基于KMeans的方法（0.76）和随机采样（0.71）。尤其在稀有细胞检测方面，dropClust 在Jurkat + 293T 混合体系中，即使目标细胞占比仅1%，仍能准确识别，而Seurat和KMeans在低于5%时就开始漏检。
计算效率方面，dropClust 仅耗时18分钟（Intel Xeon E5-2670 v2, 20核, 100GB RAM），远快于Seurat（45分钟）、KMeans（22分钟），更是比完整层次聚类（>120分钟）快了一个数量级。
此外，在无真实标签的真实数据集上也表现出良好泛化能力：
- 小鼠视网膜细胞（n=49,300）：识别出12个主要簇，轮廓系数达0.68；
- 小鼠胚胎干细胞（n=2,700）：识别出6个发育亚群，轮廓系数0.71。
轮廓系数公式如下：
$$
s(i) = \frac{b(i) - a(i)}{\max(a(i), b(i))}
$$
其中 $a(i)$ 表示细胞 $i$ 到同簇其他细胞的平均距离，$b(i)$ 是到最近其他簇所有细胞的平均距离。整体轮廓系数为所有 $s(i)$ 的均值，越接近1表示聚类内聚性和分离性越好。
为了验证聚类的生物学意义，作者还进行了差异表达分析（Differential Expression Analysis）。结果显示，dropClust 成功识别出多个已知 marker genes：
-CD3D富集于T细胞簇；
-MS4A1（即CD20）特异性表达于B细胞；
-GNLY和NKG7在NK细胞中高表达。
这些结果与已知功能高度一致，证明其聚类结果具备明确的生物学解释力。
| 模块 | 功能亮点 |
|---|---|
| LSHForest | 替代 $O(n^2)$ 全局相似度计算，实现近似 $O(n \log n)$ 近邻搜索 |
| SPS采样 | 小簇优先采样，显著增强稀有细胞代表性 |
| GMM基因选择 | 联合PCA与多模态检测，保留最具判别力的基因 |
| 两阶段聚类 | 先小样本精细聚类，再通过LSH扩展分配，兼顾精度与效率 |
这套组合拳使得 dropClust 特别适用于以下场景：
- ✅ 单细胞数量 > 50,000 的超大规模数据；
- ✅ 关注稀有细胞类型（<5%）的研究；
- ✅ 需要快速原型分析或大规模筛查任务；
- ⚠️ 对于小样本（<5,000 cells）的精细注释，Seurat等传统工具依然足够胜任。
如果你希望尝试 dropClust，安装和使用也非常简便：
pip install dropclustimport scanpy as sc from dropclust import DropClust # 加载数据 adata = sc.read_10x_h5("pbmc_68k.h5") # 标准预处理 sc.pp.filter_genes(adata, min_cells=3) sc.pp.normalize_total(adata) sc.pp.log1p(adata) sc.pp.highly_variable_genes(adata, n_top_genes=1000) adata = adata[:, adata.var['highly_variable']] # 运行 dropClust clustering = DropClust(n_sample=5000, n_genes=200) labels = clustering.fit_predict(adata.X) # 可视化 sc.tl.umap(adata) sc.pl.umap(adata, color=labels)简洁几行代码，即可完成对数十万细胞的高效聚类。
对于今天的单细胞研究者而言，数据规模不再是瓶颈，如何在速度与精度之间取得平衡，才是真正考验算法智慧的地方。dropClust 正是在这一点上做出了出色回答：它没有追求极致的数学复杂度，而是通过工程思维巧妙整合现有技术（LSH、Louvain、PCA、GMM、层次聚类），构建出一条高效、鲁棒、可扩展的分析路径。
尤其是在临床单细胞图谱构建、肿瘤微环境解析、发育轨迹推断等需要处理海量数据的应用中，dropClust 提供了一种兼具速度、精度与实用性的理想选择。
它不是最复杂的，但很可能是最聪明的那个。
