求助：百万级分子成对距离矩阵的Taylor-Butina类聚类实现

一、优先选Taylor-Butina聚类（适配你的需求场景） #

作为 cheminformatics 领域的标准球形聚类算法，Taylor-Butina完全匹配你的需求：

• 直接基于预计算的距离矩阵运行，不需要重新计算分子相似度
• 输出的聚类结果自带明确的中心（即你要的「最具代表性」分子）
• 时间复杂度和内存占用相对可控，适配10万级分子规模

二、实操指南（基于RDKit工具链） #

RDKit内置了成熟的Taylor-Butina实现，操作步骤清晰：

1. 数据预处理：将你的100000×100000距离矩阵转换为算法需要的格式——提取下三角（或上三角）的所有非对角线距离值，整理为一维列表（因为算法不需要完整矩阵，只需要两两分子的距离对）
2. 调用聚类函数：使用rdkit.ML.Cluster.Butina.ClusterData，关键参数说明：
   • dist_list：预处理后的一维距离列表
   • nPts：分子总数（100000）
   • cutoff：聚类阈值（根据你的相似度定义，比如选0.7-1.0，需要结合业务场景调整，阈值越小聚类越细）
   • isDistData：必须设为True，告知算法输入的是距离数据而非特征向量
3. 提取聚类中心：算法返回的每个聚类列表中，第一个元素就是该类的中心（算法逻辑是优先选择被最多邻近分子覆盖的点作为中心）

简化示例代码：

from rdkit.ML.Cluster import Butina
import numpy as np

# 假设你的距离矩阵是numpy数组dist_matrix
# 提取下三角非对角线的距离值
dist_list = dist_matrix[np.tril_indices(dist_matrix.shape[0], k=-1)].tolist()
n_mols = dist_matrix.shape[0]
cutoff = 0.8  # 可根据分子相似性需求调整

# 执行聚类
clusters = Butina.ClusterData(dist_list, n_mols, cutoff, isDistData=True)

# 获取所有聚类中心的索引（对应你的分子ID）
cluster_centers = [cluster[0] for cluster in clusters]

三、10万级规模的优化技巧 #

1. 内存压缩：10万×10万的float64矩阵占80GB内存，换成float32可压缩到40GB；只存储下三角部分能再减半，大幅降低内存压力
2. 分块聚类：如果内存仍不够，先将分子分成若干子块，在子块内完成聚类，再对所有子块的中心做二次聚类，最终得到全局的代表性分子
3. 性能加速：用RDKit的C++接口实现聚类，比Python版本快数倍；或者对距离矩阵的预处理步骤用多线程并行完成

四、替代方案 #

如果Taylor-Butina不符合预期，可尝试：

• Sphere-Exclusion聚类：RDKit的rdSimDivFilters.MaxMinPicker类可实现该逻辑，适合需要严格控制聚类中心间距的场景
• 近似聚类：用局部敏感哈希（LSH）先将相似分子预分组，再在组内用Taylor-Butina聚类，以微小精度损失换取内存和速度提升

内容的提问来源于stack exchange，提问作者Philipp O.