Linkage methods are among the most popular algorithms for hierarchical
clustering. Despite their relevance the current knowledge regarding the quality
of the clustering produced by these methods is limited. Here, we improve the
currently available bounds on the maximum diameter of the clustering obtained
by complete-link for metric spaces.
One of our new bounds, in contrast to the existing ones, allows us to
separate complete-link from single-link in terms of approximation for the
diameter, which corroborates the common perception that the former is more
suitable than the latter when the goal is producing compact clusters.
We also show that our techniques can be employed to derive upper bounds on
the cohesion of a class of linkage methods that includes the quite popular
average-link.

我们改进了关于完全连接法在度量空间中得到的聚类最大直径的现有限制，其中一种新的限制能够在直径的近似度上将完全连接法与单连接法进行区分，从而验证了当目标是生成紧凑聚类时，前者比后者更适用。我们还展示了我们的技术可以用于推导包括非常流行的平均连接法在内的一类连结法的凝聚度的上限。