分析平均链接聚类在度量空间中的凝聚与分离性能，证明其优于其他方法。
On the cohesion and separability of average-link for hierarchical agglomerative clustering
- 从凝聚性和分离性出发，重新评估平均链接聚类的性能。
- 理论与实验表明其在保持簇内紧密、簇间分离上表现更优。
- 适合需要兼顾簇内一致性和簇间差异性的聚类任务。
平均链接是层次聚合聚类中最常用且有效的算法之一。现有理论分析表明，它在逼近达斯古普塔成本函数的变体方面，优于单链接和完全链接等启发式方法。然而，这些分析未能将平均链接与随机层次结构区分开，且在度量空间中缺乏说服力，因为任何层次聚类对所用变体的成本函数都有至少1/2的近似比 [Moseley and Yang 2020]。本文针对度量空间中多个自然的凝聚性与分离性标准，对平均链接的性能进行了全面研究。结合真实数据集的实验结果与理论分析，我们发现当凝聚性与分离性均重要时，平均链接显著优于其他相关方法。
原文摘要 · Abstract (English)
Average-link is widely recognized as one of the most popular and effective methods for building hierarchical agglomerative clustering. The available theoretical analyses show that this method has a much better approximation than other popular heuristics, as single-linkage and complete-linkage, regarding variants of Dasgupta's cost function [STOC 2016]. However, these analyses do not separate average-link from a random hierarchy and they are not appealing for metric spaces since every hierarchical clustering has a 1/2 approximation with regard to the variant of Dasgupta's function that is employed for dissimilarity measures [Moseley and Yang 2020]. In this paper, we present a comprehensive study of the performance of average-link in metric spaces, regarding several natural criteria that capture separability and cohesion and are more interpretable than Dasgupta's cost function and its variants. We also present experimental results with real datasets that, together with our theoretical analyses, suggest that average-link is a better choice than other related methods when both cohesion and separability are important goals.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。