Source-linked AI summary
Modern hierarchical, agglomerative clustering algorithms
Daniel Müllner
TL;DR
Hierarchical agglomerative clustering software often uses suboptimal algorithms in the standard pairwise-dissimilarity and stepwise-dendrogram setting. The paper develops and proves efficient algorithms, evaluates them theoretically and practically, and recommends the best options for different linkage schemes. Its main result is a scheme-specific set of efficient algorithms, including a new generic algorithm that is especially advantageous for centroid and median clustering.
Problem
Existing software implementations often use suboptimal clustering algorithms, leaving a gap between theoretical advances and widely used standard implementations.
Method
The paper develops a generic algorithm, analyzes Murtagh’s nearest-neighbor-chain and Rohlf’s minimum-spanning-tree algorithms, proves correctness, and compares their complexity and practical performance.
Results
The authors identify the most efficient current algorithms by linkage scheme and report that their new algorithm performs significantly better for centroid and median clustering.
Takeaways & Limitations
The recommendations provide practical algorithm choices for efficient agglomerative clustering with pairwise dissimilarity input and stepwise-dendrogram output.
Takeaways & Limitations
SLINK cannot correctly handle tied dissimilarities when producing stepwise dendrograms, although it is suitable when dissimilarities are made unique.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper targets efficient hierarchical agglomerative clustering in the modern standard setting, addressing suboptimal software implementations and the gap between theory and practice. It introduces a generic algorithm, correctness proofs, and recommendations across clustering schemes.
- Motivation: Modern implementations often use suboptimal algorithms despite theoretical improvements, motivating algorithms suitable for widely used software settings.The paper aims to bridge theoretical advances and existing implementations used in science and industry.
- Contributions: A new algorithm supports any distance update scheme and performs significantly better than existing algorithms for centroid and median clustering.The contribution is specifically reported for the centroid and median schemes.
- Scope: The paper studies SAHN clustering with pairwise dissimilarity input and a stepwise dendrogram output, reflecting common software conventions.Extensions to vector data are discussed separately.
- Contributions: The authors present a generic algorithm, Murtagh’s nearest-neighbor-chain algorithm, and Rohlf’s minimum-spanning-tree algorithm, and prove their correctness.The algorithms are discussed in the paper’s main algorithmic section.
- Contributions: The paper recommends the best currently available algorithms for different agglomerative clustering schemes based on asymptotic analysis and performance experiments.The recommendations follow the complexity analysis and use-case experiments.
2 Data structures and the algorithmic definition of SAHN clustering methods
The paper formalizes the pairwise-dissimilarity input and stepwise-dendrogram output used in modern software, then defines the procedural SAHN algorithm and its distance-update schemes. This setting exposes both information requirements and algorithmic constraints, including an Ω(N^2) input-processing lower bound.
- SAHN definition: SAHN clustering starts from singleton clusters and repeatedly merges the closest pair until one cluster remains, with schemes differing in distance updates.The paper specializes this procedural definition to modern software’s standard data structures.
- Input data structure: The input is a finite set with a reflexive, symmetric dissimilarity index, whose pairwise representation has size Θ(N^2).Dissimilarities need not satisfy triangle inequalities or be positive between distinct points.
- Input data structure: Ω(N^2) time is required in the general pairwise-dissimilarity setting because every input dissimilarity can affect the clustering output.This lower bound does not apply directly to vector-data input, whose size is Θ(ND).
- Output data structure: A stepwise dendrogram is a list of N−1 merge triples recording the joined nodes and their dissimilarity at each step.The final state is a single node containing all initial data points.
- Output data structure: Unlike a non-stepwise dendrogram, a stepwise dendrogram preserves merge order under ties and can represent inversions.This extra information affects algorithm correctness and can distinguish outputs for tied dissimilarities.
- Primitive algorithm: The primitive algorithm maintains pairwise cluster dissimilarities and cluster sizes, updating distances through formulas specific to each linkage scheme.Its direct implementation takes Θ(N^3) time.
3 Algorithms
The paper presents three efficient algorithms for SAHN clustering with stored pairwise dissimilarities, adapting them to modern stepwise-dendrogram output. It introduces a generic method, proves correctness for nearest-neighbor-chain and MST-based methods, and addresses ties and scheme-specific applicability.
- 3 Algorithms: Three algorithms are presented for SAHN clustering with stored pairwise dissimilarities: Generic_linkage, NN-chain, and an MST-based algorithm.The NN-chain and MST algorithms were previously described, while the paper develops the generic algorithm as a new method.
- 3.1 The generic clustering algorithm: Generic_linkage supports any distance update formula and is required for centroid and median methods because it alone handles dendrogram inversions.The algorithm is designed for the general case, whereas centroid and median formulas can produce inversions.
- 3.1 The generic clustering algorithm: Nearest-neighbor caching and priority-queue searches accelerate the generic algorithm, reducing best-case complexity from Θ(N 3) to Θ(N 2) while retaining O(N 3) worst-case complexity.The queue caches nearest-neighbor candidates, but repeated nearest-neighbor updates can still create the cubic worst case.
- 3.1 The generic clustering algorithm: The generic algorithm is correct because each iteration still finds a globally closest pair, producing an output valid under Primitive_clustering.If several closest pairs exist, the output is one of the valid possibilities permitted by the primitive algorithm.
- 3.2 The nearest-neighbor-chain algorithm: NN-chain produces valid stepwise dendrograms for the single, complete, average, weighted, and Ward update formulas.The proof relies on the relevant update schemes satisfying the required reducibility property.
- 3.3 The single linkage algorithm: The MST-linkage algorithm is correct for single linkage, yielding an output that Primitive_clustering can also generate.Its core output is an unsorted list of clustering steps that undergoes the same postprocessing used for NN-chain.
4 Performance
The paper compares SAHN algorithms using asymptotic analysis and synthetic-data experiments, then recommends algorithms by linkage scheme. The recommendations balance worst-case complexity, practical runtime, and memory requirements.
- 4.1 Asymptotic worst-case performance: MST-linkage and NN-chain-core both achieve Θ(N^2) overall complexity, matching the Ω(N^2) lower bound for pairwise-dissimilarity input.Both algorithms are therefore asymptotically optimal in the stored-matrix setting.
- 4.1 Asymptotic worst-case performance: The generic algorithm has Θ(N^2) best-case but O(N^3) worst-case complexity, except for single linkage, where its complexity is Θ(N^2).Repeated minimum searches create the generic algorithm’s worst-case bottleneck.
- 4.1 Asymptotic worst-case performance: The MST algorithm needs no working copy of the input array and uses only O(N) temporary memory, requiring asymptotically half as much memory as Generic_linkage and NN-chain-linkage.This advantage matters when the input array must be preserved.
- 4.3 Conclusions: For single linkage, MST is clearly fastest and is recommended because it combines the best worst-case complexity, practical performance, and memory requirements.The recommendation is supported by both the experiments and memory analysis.
- 4.3 Conclusions: For complete, average, weighted, and Ward linkage, NN-chain is preferred because it guarantees O(N^2) worst-case complexity without practical-performance or memory disadvantages.The generic, NN-chain, and Anderberg algorithms have similar performance for schemes without inversions.
- 4.3 Conclusions: For centroid and median linkage, Generic_linkage is recommended because observed performance remains quadratic while Anderberg’s algorithm regularly exhibits cubic behavior.Although their theoretical worst-case bounds are the same, the observed behavior differs substantially on these random test sets.
- 4.2 Use-case performance: The timing results depend on implementation, compiler optimization, machine architecture, and data-set choice, despite careful comparison in an identical environment.This qualifies the portability of the measured performance differences.
5 Alternative algorithms
The paper evaluates alternative algorithms for SAHN clustering, emphasizing memory behavior, input-order constraints, tie handling, and theoretical-versus-practical trade-offs. It finds that some alternatives are useful under specific conditions, while others have narrower applicability than commonly claimed.
- MST and SLINK: The MST algorithm uses only O(N) working memory while reading each input dissimilarity once, making it especially efficient for single linkage.Sibson’s SLINK offers related linear working-memory behavior and can benefit from favorable input order.
- MST and SLINK: SLINK cannot handle tied dissimilarities, because its output lacks enough information to recover different stepwise dendrograms during postprocessing.A secondary ordering can artificially make dissimilarities distinct, but this changes the input ordering convention.
- MST and SLINK: With artificially distinct dissimilarities, SLINK remains a suitable tool, although its extra comparisons may slightly reduce performance depending on software environment and input order.The reported timing difference is small and may be compensated or reversed under different conditions.
- Day and Edelsbrunner: Day and Edelsbrunner’s algorithm improves the worst-case bound to O(N^2 log N) for schemes where NN-chain cannot be applied, but maintaining N priority queues slows it in practice.Its measurements are included in Figure 7.
- Other alternatives: Křivánek’s claimed O(N^2) approach is challenged because locating insertion positions in an (a, b)-tree still costs O(log N) per element.The amortized linear insertion claim applies only when insertion positions are already known.
6 Extension to vector data
For vector data, the paper discusses how its clustering algorithms can exploit geometric structure while retaining general-purpose applicability. It recommends different algorithms by linkage scheme and notes important dimensionality and parallelization limits.
- Vector-data setting: Vector-data inputs remove the Ω(N^2) time lower bound that applies to pairwise-dissimilarity inputs, but dynamic nearest-neighbor searches remain necessary.This is especially relevant when cluster centers are removed and new centers are inserted during clustering.
- Scope and limitations: Fast nearest-neighbor methods lose their advantage as dimensionality increases, so the paper focuses on general-purpose methods rather than low-dimensional specialized solutions.The discussed approaches can reduce memory requirements to Θ(ND), but do not overcome the Ω(N^2) time bound in the stated general setting.
- Algorithm recommendations: The MST algorithm supports single linkage with on-the-fly dissimilarity computation and avoids storing the full dissimilarity matrix.Each pairwise dissimilarity is read only once, and in-process computation can reduce memory use.
- Algorithm recommendations: The NN-chain algorithm is suitable for Ward clustering when initial inter-point dissimilarities are Euclidean.Ward linkage is described as meaningful only in this Euclidean setting.
- Algorithm recommendations: The generic algorithm is suitable for Ward, centroid, and median schemes on Euclidean data, while its variant simplifies bookkeeping and can reduce nearest-neighbor recalculations.Which generic version is faster depends strongly on data structures and memory layout.
- Scope and limitations: Parallelization is outside the paper’s focus; for high-dimensional vector data, parallel nearest-neighbor searches appear promising, whereas the low-dimensional case is less clear.In high dimensions, nearest-neighbor searches and their distance computations dominate the advanced algorithms’ runtime.
7 Conclusion
The conclusion identifies three efficient algorithms for SAHN clustering with dissimilarity data, assigns them to linkage-scheme families, and highlights the paper’s new algorithm and correctness proofs.
- Algorithm recommendations: Rohlf’s MST-linkage is recommended for single linkage, while Murtagh’s NN-chain-linkage covers complete, average, weighted, and Ward schemes.The recommendations distinguish algorithms by their applicable clustering schemes.
- Algorithm recommendations: Generic_linkage is recommended for centroid, median, and flexible schemes, and it can also use an arbitrary distance update formula.The paper also presents Generic_linkage_variant as a simpler variant with fewer internal calculations in some settings.
- Contributions: The paper’s generic algorithm and variant are new, while the previously described MST-linkage and NN-chain-linkage algorithms receive correctness proofs for the first time.The conclusion identifies correctness proofs as a distinguishing contribution for the existing algorithms.