Modern hierarchical, agglomerative clustering algorithms

Abstract

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.

29 pages

Cited by in corpus (50)

• A Map of the Inorganic Ternary Metal Nitrides
• A Survey on Graph-Based Deep Learning for Computational Histopathology
• Explainable Matrix -- Visualization for Global and Local Interpretability of Random Forest Classification Ensembles
• Supporting Analysis of Dimensionality Reduction Results with Contrastive Learning
• Genie: A new, fast, and outlier-resistant hierarchical clustering algorithm
• Changes to the extreme and erratic behaviour of cryptocurrencies during COVID-19
• Graph Kernels: State-of-the-Art and Future Challenges
• Machine learning for beam dynamics studies at the CERN Large Hadron Collider
• Target specific mining of COVID-19 scholarly articles using one-class approach
• Small-sample Brain Mapping: Sparse Recovery on Spatially Correlated Designs with Randomization and Clustering
• Deep Learning for 3D Point Clouds: A Survey
• Finding Trends in Software Research
• ELKI: A large open-source library for data analysis - ELKI Release 0.7.5 "Heidelberg"
• End-to-end Deep Learning from Raw Sensor Data: Atrial Fibrillation Detection using Wearables
• KnowledgeVIS: Interpreting Language Models by Comparing Fill-in-the-Blank Prompts
• Recursive nearest agglomeration (ReNA): fast clustering for approximation of structured signals
• Community detection based on first passage probabilities
• Automatic trajectory recognition in Active Target Time Projection Chambers data by means of hierarchical clustering
• Large-scale image segmentation based on distributed clustering algorithms
• Improving Problem Identification via Automated Log Clustering using Dimensionality Reduction
• Instance Segmentation in 3D Scenes using Semantic Superpoint Tree Networks
• Unsupervised Deep Learning-based clustering for Human Activity Recognition
• Representative optical turbulence profiles for ESO Paranal by hierarchical clustering
• Multiple-Perspective Clustering of Passive Wi-Fi Sensing Trajectory Data
• Hierarchical Correlation Clustering and Tree Preserving Embedding
• Neural Style Transfer Improves 3D Cardiovascular MR Image Segmentation on Inconsistent Data
• Systematic clustering algorithm for chromatin accessibility data and its application to hematopoietic cells
• The Gromov-Hausdorff distance between ultrametric spaces: its structure and computation
• Normalised clustering accuracy: An asymmetric external cluster validity measure
• Discovery of Natural Language Concepts in Individual Units of CNNs
• Recurrence analysis of meteorological data from climate zones in India
• Topic Extraction and Bundling of Related Scientific Articles
• Disambiguating Music Artists at Scale with Audio Metric Learning
• Eating Habits Discovery in Egocentric Photo-streams
• A Regionalisation Approach for Rainfall based on Extremal Dependence
• Improving Quality of Hierarchical Clustering for Large Data Series
• Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and Hierarchical Spatial Clustering
• ParChain: A Framework for Parallel Hierarchical Agglomerative Clustering using Nearest-Neighbor Chain
• Lightweight Multi-System Multivariate Interconnection and Divergence Discovery
• Detecting Patterns of Physiological Response to Hemodynamic Stress via Unsupervised Deep Learning
• Reliable Agglomerative Clustering
• Dissimilarity Clustering by Hierarchical Multi-Level Refinement
• Understanding Crowd Behaviors in a Social Event by Passive WiFi Sensing and Data Mining
• Constructing a Family Tree of Ten Indo-European Languages with Delexicalized Cross-linguistic Transfer Patterns
• Approximating a Target Distribution using Weight Queries
• Estimating Activity at Multiple Scales using Spatial Abstractions
• ReGroup: Recursive Neural Networks for Hierarchical Grouping of Vector Graphic Primitives
• Beam Measurements and Machine Learning at the CERN Large Hadron Collider
• Young stellar structures in four nearby galaxies
• Learning Unions of k-Testable Languages