hierarchical clustering trees have been widely accepted as a useful form of
clustering data, resulting in a prevalence of adopting fields including
phylogenetics, image analysis, bioinformatics and more. Recently, Dasgupta
(STOC 16') initiated the analysis of these types of algorithms
本文提出两种高效的分层聚类算法，针对 Dasgupta 成本函数。对于任何有明确集群结构的输入图 G，我们设计的算法在 G 的输入大小几乎为线性的时间内运行，并返回一个相对于 Dasgupta 成本函数的 O (1) 近似 HC 树。我们将我们的算法的性能与先前的最新技术在合成和真实世界的数据集上进行比较，并表明我们设计的算法在更短的运行时间内产生了相当或更好的 HC 树。