Source-linked AI summary
Methods of Hierarchical Clustering
Fionn Murtagh, Pedro Contreras
TL;DR
The paper surveys practical hierarchical clustering methods and implementations across agglomerative, self-organizing-map, mixture-model, and grid-based approaches. It highlights a linear-time m-adic clustering algorithm for large data sets while noting that dendrogram interpretations can vary by application and that some algorithmic properties require stated assumptions.
Problem
The paper addresses how hierarchical clustering can remain practical across diverse data sizes, representations, algorithms, and application domains.
Method
The paper surveys agglomerative algorithms, efficient nearest-neighbor implementations, hierarchical self-organizing maps, mixture models, and grid- and density-based methods.
Results
The survey describes m-adic clustering as a linear-time algorithm for large data sets and reports applications of its Baire distance in chemoinformatics, astronomy, and text retrieval.
Takeaways & Limitations
Hierarchical clustering remains applicable across many domains, with m-adic clustering offering a particularly efficient approach for large data sets.
Takeaways & Limitations
Dendrograms can yield different answers about useful groups and salient relationships depending on the application, and inversion is subject to stated conditions.
Abstract
from arXiv · showhide
We survey agglomerative hierarchical clustering algorithms and discuss efficient implementations that are available in R and other software environments. We look at hierarchical self-organizing maps, and mixture models. We review grid-based clustering, focusing on hierarchical density-based approaches. Finally we describe a recently developed very efficient (linear time) hierarchical clustering algorithm, which can also be viewed as a hierarchical grid-based algorithm.
1 Introduction
The article surveys hierarchical clustering methods with emphasis on practical efficiency, effectiveness, and implementation choices. It covers agglomerative algorithms, self-organizing maps, mixture models, and grid- and density-based approaches.
- Motivation: Agglomerative hierarchical clustering is presented as a dominant approach for constructing embedded classification schemes.The article distinguishes a clustering method’s criterion and target structure from the implementation details used to realize it.
- Motivation: The survey targets algorithms that are computationally and storage efficient while remaining effective for applications.
- Data representation: The data are treated as rows of a numerical matrix, whose vectors occupy a multidimensional space defined by the variables.Constructing a suitable matrix may be necessary when numerical measurements are not initially available.
- Article scope: The survey discusses normalization, agglomerative algorithms, nearest-neighbor implementations, hierarchical self-organizing maps, mixture models, and grid- or density-based clustering.
2 Data Entry: Distance, Similarity and Their Use
Clustering begins by representing observations and measuring their relationships through distances, dissimilarities, or similarities. The section reviews common metric families and transformations used before hierarchy induction.
- Measurement: Clustering requires measurements of elements and their pairwise relationships to determine group membership.These relationships may be expressed as similarities, dissimilarities, or stronger distance measures.
- Distances and similarities: A distance is characterized by symmetry, positive definiteness, and the triangular inequality, whereas omitting the triangular inequality yields a dissimilarity.
- Metric choices: Minkowski distance provides a metric family whose special cases include Manhattan, Euclidean, and Chebyshev distance.The corresponding cases are p = 1, p = 2, and p →∞.
- Similarity choices: Cosine similarity compares vectors by their angle and is widely used in text retrieval, where smaller angles indicate closer query-document matches.
- Embedding: Correspondence analysis can map frequency counts, mixed qualitative and quantitative values, ranks, and scores into a Euclidean factor space for subsequent clustering.The mapping treats input objects as equiweighted in the resulting Euclidean space.
3 Agglomerative Hierarchical Clustering Algorithms: Motivation
Agglomerative clustering greedily builds a hierarchy through irreversible pairwise merges, yielding equivalent partition, dendrogram, poset, and ultrametric representations. Dendrograms support several interpretations, but their answers can depend on the application.
- Agglomerative structure: Agglomerative algorithms repeatedly merge a pair of clusters, producing n−1 partitions from singleton classes to one class.
- Agglomerative structure: The same hierarchy can be represented as a binary dendrogram, a poset over subsets, or an ultrametric topology.
- Ultrametric representation: An ultrametric strengthens the ordinary triangular inequality into d(i, j) ≤max{d(i, k), d(k, j)}.
- Interpretations and methods: Single linkage defines intercluster dissimilarity by the least dissimilarity between members of the two clusters and produces connected components at successive thresholds.
- Interpretations and methods: Dendrograms support set-inclusion, partition, significant-cluster, and evolutionary interpretations, including methods for identifying important clusters at varying hierarchy levels.
- Interpretations and methods: The number of useful groups and salient interrelationships inferred from a dendrogram can vary with the application.
4 Agglomerative Hierarchical Clustering Algorithms
Agglomerative methods differ in how they represent and update intercluster dissimilarities, including linkage and cluster-center criteria. The section also describes minimum-variance clustering and storage-conscious implementations.
- Method families: Hierarchical methods divide into linkage methods, which admit graph representations, and cluster-center methods such as centroid, median, and minimum variance.
- Dissimilarity updates: The Lance-Williams formula updates the dissimilarity between a newly merged cluster and another object or cluster using criterion-specific coefficients.The coefficients α_i, α_j, β, and γ determine the agglomerative criterion.
- Dissimilarity updates: Using alternative update formulas allows several agglomerative methods to be implemented similarly to single linkage.
- Cluster-center methods: Cluster-center methods use center coordinates and dissimilarities between centers, with Euclidean distance required for the described formulation.
- Implementation: The stored-dissimilarities algorithm repeatedly finds the closest pair, replaces it with a representative point or fragment, and continues until all objects form one cluster.For n initial objects, the described implementation uses O(n) storage for the objects and at most n−1 clusters.
- Minimum variance: Minimum-variance clustering seeks merges that minimize the decrease in within-class variance, equivalently maximizing between-class variance while promoting compactness and isolation.The selected agglomerands are the pair of classes with minimum resulting dissimilarity.
- Minimum variance: For singleton classes, the variance of a pair equals half their squared Euclidean distance.
5 Efficient Hierarchical Clustering Algorithms Using Nearest Neighbor Chains
Nearest-neighbor chains and reciprocal nearest neighbors provide efficient alternatives to classical agglomerative implementations, with exact replication possible under suitable reducibility conditions. The section also relates these algorithms to storage, parallelization, and practical software implementations.
- Implementations: Earlier implementations achieved O(n^2) time, while several approaches also reduced storage to O(n).The cited results cover single-link, complete-link, Ward, centroid, median, and average-linkage methods.
- Correctness and efficiency: Nearest-neighbor and reciprocal-nearest-neighbor methods can potentially replicate classical hierarchical results while reducing computational expense.Their equivalence depends on conditions preventing inversions in the hierarchy.
- Nearest-neighbor chains: NN-chain algorithms construct chains of nearest neighbors until reciprocal nearest neighbors are found, then agglomerate that pair.The procedure repeats until one point remains, updating the relevant nearest neighbors after each agglomeration.
- Correctness and efficiency: Minimum variance and linkage methods avoid inversions, whereas centroid and median methods are not guaranteed to do so.This distinction is tied to Bruynooghe’s reducibility property and determines when reciprocal-nearest-neighbor agglomerations are justified.
- Implementations: Nearest-neighbor-chain construction and reciprocal-neighbor agglomeration support distributed implementations, and NN-chain methods are available in CLUSTAN and R packages.The R ecosystem includes hclust and flashClust implementations for minimum-variance agglomeration.
- Applications: The methods accept coordinate data and graph or dissimilarity data, with Ward’s method used on data sets containing a few hundred thousand molecules.The cited application concerns chemical structure databases.
6 Hierarchical Self-Organizing Maps and Hierarchical Mixture Modeling
The section surveys hierarchical self-organizing maps, probabilistic hierarchical models, Gaussian mixture approaches, and divisive alternatives. These methods organize representations or probability models hierarchically, with model selection criteria used in mixture-based clustering.
- Hierarchical self-organizing maps: Kohonen self-organizing maps can represent hierarchies through layered maps and have been applied to character recognition.Several cited works develop hierarchical representations of Kohonen maps.
- Hierarchical self-organizing maps: Generative Topographic Mapping combines a growing hierarchical map with an explicit probability density model.The hierarchy can grow in both layers and grid points within layers.
- Hierarchical mixture modeling: Hierarchical mixture modeling includes Gaussian mixture models and Bayesian alternatives to Kohonen self-organizing maps.These approaches are presented as probabilistic hierarchical models.
- Hierarchical mixture modeling: Alternating Gaussian mixture modeling with principal component analysis can produce a hierarchy of model-based clusters, using AIC to select the overall cluster model.The cited method alternates between mixture modeling and principal component analysis.
- Hierarchical mixture modeling: A divisive Gaussian-mixture cluster tree can use PLIC at the top level and BIC for subsequent marginal-distribution models.The criteria support cluster selection and identifiability at different hierarchical levels.
- Divisive alternatives: Divisive hierarchical clustering is especially feasible when graph cuts matter, and divisive Ward is closely related to bisecting k-means.The section contrasts this divisive perspective with the agglomerative algorithms discussed earlier.
7 Density and Grid-Based Clustering Techniques
Grid- and density-based clustering organize data through cells, density estimates, or dense regions, offering scalable approaches for large and noisy data sets. The surveyed methods range from hierarchical grids and recursive partitions to image-based and density-connected procedures.
- Grid-based clustering: Grid-based clustering partitions the data space into cells, computes cell densities, sorts cells, and identifies cluster centers.The general workflow separates dense grid regions from less dense regions to form groups.
- Grid-based methods: STING stores rectangular spatial cells hierarchically with O(K) complexity, but its cell count makes high-dimensional scaling difficult.When each cell has four children, the second level contains 2^m cells for dimensionality m.
- Grid-based methods: OptiGrid recursively partitions high-dimensional noisy data with density-minimizing hyperplanes and has O(n · m) time complexity.Each cutting plane separates two dense half-spaces before recursion continues on the resulting subsets.
- Grid-based methods: GRIDCLUS organizes the surrounding space into a multidimensional grid, computes block densities, and clusters blocks through topological neighbor searches.Its workflow begins by inserting points into the grid and calculating density indices.
- Grid-based methods: WaveCluster converts point counts in a two-dimensional grid into a grayscale image and uses wavelets for multiscale noise-reducing segmentation.The clustering task is transformed into image segmentation.
- Density-based clustering: Density-based methods find dense regions separated by low-density regions, support arbitrary cluster shapes, handle noise, and do not require an initial cluster count.DBSCAN is highlighted as a widely used example with multiple variations.
- Density-based clustering: BRIDGE combines k-means partitioning with DBSCAN, while DENCLUE and CUBN use density or neighbor operations for large or non-spherical data.CUBN is reported with O(n) computational complexity.
8 A New, Linear Time Grid Clustering Method: m-Adic Clustering
m-adic clustering uses an ultrametric based on shared digit prefixes to organize large data sets hierarchically through grid-like cells. The approach is described as linear-time and has been applied in chemoinformatics, astronomy, and text retrieval.
- m-Adic clustering: m-adic expansion enables a linear-time clustering algorithm for large data sets.The usual decimal and binary systems are presented as special cases of m-adic representations.
- Baire distance: The Baire distance measures the longest common prefix of two finite-precision strings, assigning smaller distances to longer shared prefixes.This longest-common-prefix metric is an ultrametric.
- Baire distance: For 0.478 and 0.472, the first two decimal positions match, giving a Baire distance of 10^-2 in base 10.The distance is determined by the first decimal position at which the values differ.
- Hierarchical grid structure: The Baire distance creates a 10-way hierarchy for decimal values, with leaves interpretable as grid cells.All pairwise distances among points assigned to the same cell are equal.
- Applications: Baire-distance clustering has been applied to chemoinformatics, astronomy, and text retrieval.These applications are cited as successful uses of the method.
9 Conclusions
Hierarchical clustering remains an important and continually developing family of methods, spanning traditional agglomerative and newer grid- or cell-based approaches. The survey also examines algorithmic properties and applications across several domains.
- Hierarchical clustering methods remain central to many important problems and are deployed across numerous application domains.
- The survey covers traditional agglomerative clustering alongside newer grid- or cell-based approaches.
- It discusses well-definedness, including inversions, and computational properties of clustering algorithms.
- Applications considered include chemoinformatics and information retrieval, areas with longstanding connections to clustering.