提出新型聚类距离度量,显著提升层次聚类效果。
Chamfer-Linkage for Hierarchical Agglomerative Clustering
- 用点云距离的Chamfer距离定义簇间相似性
- 在多个数据集上优于平均链接和Ward方法
- 计算效率与传统方法相当,可直接替换使用
层次聚合聚类(HAC)通过反复合并最近的簇对来构建聚类结构,其性能高度依赖于链接函数的选择。现有经典链接函数如单链接、平均链接和Ward方法在真实数据集上表现不稳定,难以持续生成高质量聚类。本文提出新链接函数Chamfer-linkage,利用机器学习与计算机视觉中常用的点云距离度量——Chamfer距离来衡量簇间距离。理论分析表明,Chamfer-linkage HAC可在$O(n^2)$时间内实现,与经典方法效率相当。实验显示,在多样化数据集上,Chamfer-linkage始终优于平均链接和Ward方法。结果证明该方法是经典链接函数的实用替代方案,拓展了层次聚类的理论与实践工具箱。
原文摘要 · Abstract (English)
Hierarchical Agglomerative Clustering (HAC) is a widely-used clustering method based on repeatedly merging the closest pair of clusters, where inter-cluster distances are determined by a linkage function. Unlike many clustering methods, HAC does not optimize a single explicit global objective; clustering quality is therefore primarily evaluated empirically, and the choice of linkage function plays a crucial role in practice. However, popular classical linkages, such as single-linkage, average-linkage and Ward's method show high variability across real-world datasets and do not consistently produce high-quality clusterings in practice. In this paper, we propose \emph{Chamfer-linkage}, a novel linkage function that measures the distance between clusters using the Chamfer distance, a popular notion of distance between point-clouds in machine learning and computer vision. We argue that Chamfer-linkage satisfies desirable concept representation properties that other popular measures struggle to satisfy. Theoretically, we show that Chamfer-linkage HAC can be implemented in $O(n^2)$ time, matching the efficiency of classical linkage functions. Experimentally, we find that Chamfer-linkage consistently yields higher-quality clusterings than classical linkages such as average-linkage and Ward's method across a diverse collection of datasets. Our results establish Chamfer-linkage as a practical drop-in replacement for classical linkage functions, broadening the toolkit for hierarchical clustering in both theory and practice.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。