A Characterization of Linkage-Based Hierarchical Clustering

Margareta Ackerman, Shai Ben-DavidJMLR 2016

TL;DR

This paper provides a formal, property-based characterization of linkage-based hierarchical clustering algorithms. It proves that these algorithms are precisely those that are both "local" and "outer-consistent," distinguishing them from other hierarchical methods and explaining why some divisive algorithms cannot be simulated by linkage-based ones.

What Problem Does This Paper Address?

Choosing the right clustering algorithm can be a daunting task, often relying on ad-hoc decisions rather than a deep understanding of how different algorithms work and what their outputs represent. While many clustering algorithms exist, this paper focuses on hierarchical clustering, which produces dendrograms that allow users to explore clusterings at various granularities. A common class of hierarchical algorithms is "linkage-based," which iteratively merge the closest clusters. However, the distinction between linkage-based and other hierarchical methods (like divisive algorithms) isn't always clear, leading to potential confusion and misapplication. This paper aims to clarify this distinction by identifying fundamental properties that uniquely define linkage-based hierarchical clustering.

Methods

The authors introduce two key properties: Locality and Outer-Consistency.

  • Locality: This property states that if you take a subset of data that has already been clustered by a hierarchical algorithm and re-run the algorithm on just that subset, the resulting dendrogram should be consistent with the original. Essentially, the clustering of a subset should be preserved within the larger dendrogram.
  • Outer-Consistency: This property is a relaxation of Kleinberg's consistency axiom for partitional clustering. It ensures that if you "pull apart" clusters (increase distances between them) in a way that makes a particular clustering more pronounced, that clustering should still appear in the dendrogram produced by the algorithm.

The paper then proves that a hierarchical clustering function is linkage-based if and only if it satisfies both Locality and Outer-Consistency. They also define linkage functions and hierarchical clustering functions formally, and demonstrate that divisive algorithms, particularly those that are "context-sensitive," often violate Locality and thus cannot be simulated by linkage-based methods.

Datasets

Not discussed in the paper. The paper focuses on theoretical properties and formal definitions rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Linkage-based clustering has a unique "fingerprint": The combination of Locality and Outer-Consistency precisely characterizes linkage-based hierarchical clustering. This provides a formal way to distinguish them from other hierarchical methods.
  • Divisive algorithms are fundamentally different: The paper shows that many divisive algorithms (like bisecting k-means) are "context-sensitive," meaning their splitting decisions depend on the global structure of the data. This often leads them to violate Locality, making them inherently different from linkage-based methods and impossible to simulate.
  • Understanding properties aids algorithm selection: By formalizing these differences, the paper aims to help users make more informed choices about which clustering algorithm to use based on their specific needs and domain knowledge.

Key Results

  • Theorem 10: A hierarchical function F is linkage-based if and only if it is outer-consistent and local.
  • Lemma 21 & 22: All linkage-based hierarchical clustering functions are local and outer-consistent.
  • Theorem 25: Context-sensitive 2-clustering functions lead to F-divisive functions that are not local.
  • Corollary 26: Context-sensitive F-divisive functions are not linkage-based.
  • The paper demonstrates the necessity of both properties by showing examples of hierarchical functions that satisfy one but not the other, and are thus not linkage-based.

Limitations and Future Work

The authors acknowledge that their characterization is not intended to declare linkage-based methods superior but rather to enable informed trade-offs. Future work could involve investigating other important properties to build a more comprehensive taxonomy of clustering methods, helping users select suitable algorithms for a wider range of applications. The paper also highlights that divisive algorithms, particularly context-sensitive ones, represent a distinct class of hierarchical clustering that cannot be simulated by linkage-based methods.

Summary updated

BibTeX
@article{ackerman2016characterization,
  author = {Margareta Ackerman and Shai Ben-David},
  title = {{A Characterization of Linkage-Based Hierarchical Clustering}},
  journal = {J. Mach. Learn. Res.},
  year = {2016},
}

Loading related content...

Figure