Hierarchical Clustering

By Vincent Cohen-Addad, Varun Kanade, Frederik Mallmann-Trenn, Claire Mathieu. ACM-SIAM Symposium on Discrete Algorithms, 2017

707 citations recorded by the source corpus.

Hierarchical clustering is a recursive partitioning of a dataset into clusters at an increasingly finer granularity. Motivated by the fact that most work on hierarchical clustering was based on providing algorithms, rather than optimizing a specific objective, Dasgupta framed similarity-based hierarchical clustering as a combinatorial optimization problem, where a “good” hierarchical clustering is one that minimizes a particular cost function [23]. He showed that this cost function has certain desirable properties: To achieve optimal cost, disconnected components (namely, dissimilar elements) must be separated at higher levels of the hierarchy, and when the similarity between data elements is identical, all clusterings achieve the same cost. We take an axiomatic approach to defining “good” objective functions for both similarity- and dissimilarity-based hierarchical clustering. We characterize a set of admissible objective functions having the property that when the input admits a “natural” ground-truth hierarchical clustering, the ground-truth clustering has an optimal value. We show that this set includes the objective function introduced by Dasgupta. Equipped with a suitable objective function, we analyze the performance of practical algorithms, as well as develop better and faster algorithms for hierarchical clustering. We also initiate a beyond worst-case analysis of the complexity of the problem and design algorithms for this scenario.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics, Signal Processing

View Paper: https://www.semanticscholar.org/paper/25f01197a09bccaa7eaa70dba6e3adad53772cf7

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Tomas Krilavičius
2. Mark L. Blaxter
3. Justina Mandravickaite

In Statistical and Nonlinear Physics

1. Tomas Krilavičius
2. Justina Mandravickaite

In Signal Processing

1. Tomas Krilavičius
2. Justina Mandravickaite

Citations in the corpus

• How many biological replicates are needed in an RNA-seq experiment and which differential expression tool should you use? (2015, methodology): “…and sequencing The RNA-seq experiment described here implements a “ balanced blockdesign ” inordertocontrolfortechnicalartifactssuchaslibrary batch effects (Kaisers et al. 2014), barcoding biases, and lane effects via randomization of the libraries (Colbourn and Dinitz 2007; Auer and Doerge 2010).”
• Stylometric Analysis of Parliamentary Speeches: Gender Dimension (2017, methodology): “The goal is identifying stylistic dissimilarities and mapping positions of the text samples in relation to each other, not classifying female/male legislators, hence hierarchical clustering with Ward linkage (it minimizes total variance within-cluster (Everitt et al., 2011)) was chosen.”
• Statistical Considerations in the Creation of Realistic Synthetic Power Grids for Geomagnetic Disturbance Studies (2017, methodology): “Hierarchical clustering is used to combine smaller generators, depending on the level of detail desired for a specific case [19].”