改进聚类算法，让化学指纹数据更快更准地分组。
Fast and explainable clustering in the Manhattan and Tanimoto distance
- 用向量范数排序+三角不等式剪枝，适配曼哈顿和泰明托距离。
- 在真实化学指纹数据上比Taylor-Butina快30倍，比DBSCAN快80倍。
- 适用于需要快速且可解释聚类的药物研发与分子分析场景。
CLASSIX算法是一种快速且可解释的数据聚类方法。其原始形式利用数据点第一主成分排序，通过欧氏距离定义邻近性来截断搜索。本文将其扩展至曼哈顿距离和泰明托距离：不再使用主成分，而以数据向量的适当范数作为排序依据，并结合三角不等式实现搜索终止。针对泰明托距离，引入一个可证明更紧的交集不等式，进一步提升性能。在真实世界化学指纹基准测试中，CLASSIX Tanimoto算法比Taylor-Butina快约30倍，比DBSCAN快约80倍，且生成的聚类质量更高。
原文摘要 · Abstract (English)
The CLASSIX algorithm is a fast and explainable approach to data clustering. In its original form, this algorithm exploits the sorting of the data points by their first principal component to truncate the search for nearby data points, with nearness being defined in terms of the Euclidean distance. Here we extend CLASSIX to other distance metrics, including the Manhattan distance and the Tanimoto distance. Instead of principal components, we use an appropriate norm of the data vectors as the sorting criterion, combined with the triangle inequality for search termination. In the case of Tanimoto distance, a provably sharper intersection inequality is used to further boost the performance of the new algorithm. On a real-world chemical fingerprint benchmark, CLASSIX Tanimoto is about 30 times faster than the Taylor--Butina algorithm, and about 80 times faster than DBSCAN, while computing higher-quality clusters in both cases.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。