Modern hierarchical, agglomerative clustering algorithms

By Daniel Müllner. arXiv.org, 2011

812 citations recorded by the source corpus.

This paper presents algorithms for hierarchical, agglomerative clustering which perform most efficiently in the general-purpose setup that is given in modern standard software. Requirements are: (1) the input data is given by pairwise dissimilarities between data points, but extensions to vector data are also discussed (2) the output is a "stepwise dendrogram", a data structure which is shared by all implementations in current standard software. We present algorithms (old and new) which perform clustering in this setting efficiently, both in an asymptotic worst-case analysis and from a practical point of view. The main contributions of this paper are: (1) We present a new algorithm which is suitable for any distance update scheme and performs significantly better than the existing algorithms. (2) We prove the correctness of two algorithms by Rohlf and Murtagh, which is necessary in each case for different reasons. (3) We give well-founded recommendations for the best current algorithms for the various agglomerative clustering schemes.

Subfields: Artificial Intelligence, Signal Processing

View Paper: https://www.semanticscholar.org/paper/3d28a83e86dc5ab0334ae014b1218f0ad856f76b

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. Sergey Levine
2. Quoc V. Le
3. Yoshua Bengio
4. Mohit Bansal
5. Percy Liang
6. Ruslan Salakhutdinov
7. Jianfeng Gao
8. Pieter Abbeel

In Signal Processing

1. Oriol Vinyals
2. Yoav Goldberg
3. Junichi Yamagishi
4. John Healy
5. Leland McInnes
6. Koray Kavukcuoglu
7. Jinyu Li
8. Andrew W. Senior

Citations in the corpus

• A high-bias, low-variance introduction to Machine Learning for physicists (2018, positive): “Efficient implementations achieve a typical computational complexity of O(N2) (Müllner, 2011), making the method suitable for small to medium-size datasets.”
• fastcluster: Fast Hierarchical, Agglomerative Clustering Routines for R and Python (2013, methodology): “R-project.org/package=fastcluster , builds upon the author’s work (M¨ullner 2011), where we identified three algorithms, including a new one by the author, as the most efficient current algorithms for the seven clustering schemes above, when the input is given by pairwise dissimilarities between…”
• Applying and improving AlphaFold at CASP14 (2021, methodology): “Clustering was performed by measuring similarity with TM score and then analyzed using scipy's cluster hierarchical linkage clustering algorithm 13,14 to give a maximum of three clusters.”
• Comprehensive survey on hierarchical clustering algorithms and the recent developments (2022, methodology): “Furthermore, it is also known that Rohlf’s algorithm MST-LINKAGE for single clustering, Murtagh’s algorithm NN-CHAIN-LINKAGE for the “complete”, “average”, “weighted” and “Ward” scenarios are the most efficient among algorithms based on distance dissimilarities (Müllner 2011).”
• ClusterNet: Deep Hierarchical Cluster Network With Rigorously Rotation-Invariant Representation for Point Cloud Analysis (2019, methodology): “In the area of unsupervised learning, hierarchical clustering [11] is a classical method to build a hierarchy (also called dendrogram) of clusters.”
• Accelerated Hierarchical Density Based Clustering (2017, methodology): “Such an approach is similar to the SLINK algorithm [31], [25] which essentially uses a modified version of Prim’s algorithm (that does not explicitly compute an MST).”
• Deep Learning for 3D Point Clouds: A Survey (2019, methodology): “ClusterNet [95] utilizes a rigorously rotation-invariant module to extract rotationinvariant features from k nearest neighbors for each point, and constructs hierarchical structures of a point cloud based on the unsupervised agglomerative hierarchical clustering method with ward-linkage criteria [96”
• Transformer Feed-Forward Layers Build Predictions by Promoting Concepts in the Vocabulary Space (2022, positive): “We use agglomerative clustering (Müllner, 2011) to learn 10k clusters for each model, based on the cosine distance matrix D, where D(l1,i1),(l2,i2) = 1 − cos(v1 i1 ,v l2 i2 ), ∀i1, i2 ∈ {1, · · · , dm}, ∀l1, l2 ∈ {1, · · · , L}.”
• Reasoning-Enhanced Healthcare Predictions with Knowledge Graph Community Retrieval (2024, unknown): “We employ agglomerative clustering (M¨ullner, 2011) with an automatically determined optimal threshold.”