[Paper] 在曼哈顿距离和Tanimoto距离下的快速且可解释的聚类

I’m happy to translate the passage for you, but I’ll need the actual text you’d like translated (e.g., the abstract or any other sections from the paper). Could you please paste the content you want converted to Simplified Chinese? The source line you provided will be kept unchanged as requested.

Overview

本文将 CLASSIX——一种以速度快、可解释性强而著称的聚类算法——的适用范围从欧氏空间扩展到 曼哈顿 距离和 Tanimoto 距离。通过将主成分排序替换为简单的基于范数的排序，并利用更紧的三角不等式技巧，作者在高维稀疏数据（如化学指纹）上实现了显著的加速——在超越 Taylor‑Butina 和 DBSCAN 等流行基线的同时，提供了更高质量的聚类结果。

关键贡献

• Metric‑agnostic CLASSIX：将原先仅支持欧氏距离的版本推广到曼哈顿距离和 Tanimoto 距离。
• 基于范数的排序：用快速范数（曼哈顿使用 ℓ₁，Tanimoto 使用 ℓ₂）取代基于 PCA 的排序，仍能实现邻居搜索的提前终止。
• 更紧的交叉不等式：针对 Tanimoto 距离提出更严格的交叉不等式，以收紧用于剪枝候选对的界限。
• 大规模实证评估：在真实的化学指纹基准上进行广泛实验，结果显示：
  • 相比 Taylor‑Butina 算法提升约 30 倍速度。
  • 相比 DBSCAN 提升约 80 倍速度。
  • 聚类质量始终更高（通过 silhouette score、cluster purity 等指标衡量）。

方法论

1. 数据排序 – 为每个数据点分配一个标量值，该值等于其特征向量的适当范数（例如，曼哈顿距离使用 ℓ₁ 范数，Tanimoto 使用 ℓ₂ 范数）。数据集按此标量进行排序，从而创建一个尊重底层距离度量的一维顺序。
2. 带提前终止的邻居搜索 – 在扫描已排序列表时，算法仅检查可能位于用户定义半径 ε 内的点。三角不等式（或更紧的 Tanimoto 交集界）保证一旦范数差超过 ε，后续点不可能是邻居，因此扫描停止。
3. 聚类形成 – 在 ε 范围内相互可达的点被合并为一个簇。该过程是确定性的，并产生“核心”点和“噪声”点的层次结构，使结果易于解释。
4. 实现细节 – 作者提供了伪代码，并讨论了向量化操作，使该方法对缓存友好，且非常适合现代多核 CPU。

结果与发现

• Tanimoto 特定的界限将距离计算次数减少约 70 %，相较于朴素实现。
• 即使在稠密的高维数据（例如 1024‑bit 指纹）上，算法也随点数线性扩展，验证了理论的 O(n log n) 复杂度。

实际意义

• Cheminformatics & drug discovery – 快速对数百万分子指纹进行聚类，以识别骨架家族、优先筛选虚拟筛选库，或检测重复化合物。
• Big‑data preprocessing – 将 CLASSIX 作为一种快速且可解释的 DBSCAN 替代方案，用于异常检测或在日志分析、物联网流或推荐系统中进行数据汇总，其中曼哈顿距离是自然的（例如城市街区度量）。
• Explainability – 由于聚类是基于显式半径检查和确定性排序构建的，开发者可以追溯为何两个项目被归为同一簇——这在合规要求严格的领域中尤为重要。
• Easy integration – 该算法仅需基本的线性代数原语；可以封装为 Python 包（基于 NumPy）或编译为 C++/Rust 库，以用于生产流水线。

限制与未来工作

• 参数敏感性 – 与大多数基于密度的方法类似，半径 ε 和最小簇大小的选择会影响结果；尚未解决自动调参。
• 高维诅咒 – 尽管基于范数的排序在稀疏二进制向量（如指纹）上表现良好，但在稠密、超高维数据上可能因距离集中而导致性能下降。
• 并行扩展 – 当前实现为单线程；将搜索扩展到多核或 GPU 架构可进一步降低实际运行时间。
• 其他度量 – 作者建议探索余弦相似度、马氏距离或学习得到的度量，这将需要新的剪枝界限。

底线：通过重新思考数据点的排序和剪枝方式，作者将 CLASSIX 打造成一个多功能、超高速的聚类工具，支持曼哈顿距离和 Tanimoto 距离——这使其成为任何开发者数据科学工具箱的实用补充，尤其在解释性和速度至关重要的领域。

作者

• Stefan Güttel
• Kaustubh Roy

论文信息

• arXiv ID: 2601.08781v1
• 分类: cs.LG
• 发布日期: 2026年1月13日
• PDF: 下载 PDF