{ "id": "epz7najwbs", "slug": "agglomerative-hierarchical-clustering", "title": "Agglomerative hierarchical clustering", "updated": "2026-10-15", "topic_path": [ { "id": "technology", "label": "Technology and the built world", "api_url": "https://www.edgepedia.org/api/v1/topics/technology" }, { "id": "technology.computing", "label": "Computing and digital systems", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing" }, { "id": "technology.computing.ai", "label": "Artificial intelligence and data", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai" }, { "id": "technology.computing.ai.ml_computation", "label": "Machine learning and neural computation", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai.ml_computation" }, { "id": "technology.computing.ai.ml_methods", "label": "Machine learning methods", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai.ml_methods" }, { "id": "technology.computing.ai.supervised_unsupervised", "label": "Supervised, unsupervised, and semi-supervised learning", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai.supervised_unsupervised" }, { "id": "technology.computing.ai.supervised_unsupervised.clustering", "label": "Clustering algorithms", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai.supervised_unsupervised.clustering" } ], "geo": [ { "id": "geo.nongeo.t1946.technology.computing.ai.supervised_unsupervised", "label": "Non-geographic · 1946 to 2000: Supervised, unsupervised, and semi-supervised learning", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai.supervised_unsupervised", "path": [ { "id": "geo.nongeo", "label": "Non-geographic", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo" }, { "id": "geo.nongeo.t1946", "label": "Non-geographic · 1946 to 2000", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946" }, { "id": "geo.nongeo.t1946.technology", "label": "Technology and the built world", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology" }, { "id": "geo.nongeo.t1946.technology.computing", "label": "Computing and digital systems", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing" }, { "id": "geo.nongeo.t1946.technology.computing.ai", "label": "Artificial intelligence and data", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai" }, { "id": "geo.nongeo.t1946.technology.computing.ai.ml_computation", "label": "Machine learning and neural computation", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai.ml_computation" }, { "id": "geo.nongeo.t1946.technology.computing.ai.ml_methods", "label": "Machine learning methods", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai.ml_methods" }, { "id": "geo.nongeo.t1946.technology.computing.ai.supervised_unsupervised", "label": "Supervised, unsupervised, and semi-supervised learning", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai.supervised_unsupervised" } ] } ], "excerpt": "Agglomerative hierarchical clustering is a bottom-up clustering method that starts with each data point as its own cluster and merges the closest pairs, yielding a dendrogram.", "snippet": "Agglomerative hierarchical clustering is a bottom-up clustering method that starts with each data point as its own cluster and merges the closest pairs, yielding a dendrogram.", "node": "technology.computing.ai.supervised_unsupervised.clustering", "markdown": "# Agglomerative hierarchical clustering\n\nAgglomerative hierarchical clustering is a bottom-up clustering method that starts with every data point as its own cluster and repeatedly merges the two closest clusters until a single cluster remains, producing a hierarchy of nested groupings rather than one flat partition.[1](https://ar5iv.labs.arxiv.org/html/1012.3697) The result is a binary merge tree with exactly \\( n - 1 \\) merges for \\( n \\) points, usually drawn as a dendrogram; cutting the tree at a chosen height yields a flat clustering into any number of groups.[2](https://franknielsen.github.io/Clustering/BookChapter-HierarchicalClustering.pdf) The method is deterministic and greedy, and schemes differ only in how the distance between two clusters is defined and updated after each merge.[3](https://ar5iv.labs.arxiv.org/html/1109.2378)\n\n| Key fact | Detail |\n|---|---|\n| Output | A dendrogram (binary merge tree) from n − 1 merges; flat clusters come from cutting it[2](https://franknielsen.github.io/Clustering/BookChapter-HierarchicalClustering.pdf) |\n| Merge rule | At each step, merge the pair of clusters with the smallest inter-cluster dissimilarity[3](https://ar5iv.labs.arxiv.org/html/1109.2378) |\n| Common linkages | Single, complete, average (UPGMA), weighted (WPGMA), Ward, centroid, median[3](https://ar5iv.labs.arxiv.org/html/1109.2378) |\n| Ward criterion | Δ(A,B) = (n_A n_B/(n_A+n_B))·‖x̄_A − x̄_B‖², the increase in within-cluster sum of squares; Euclidean data only[4](https://lanselin.github.io/introbook_vol2/agglomerative-clustering.html) |\n| Complexity | Naive Θ(N³); NN-chain and MST-based algorithms O(N²)[5](https://nlp.stanford.edu/IR-book/pdf/17hier.pdf) • [3](https://ar5iv.labs.arxiv.org/html/1109.2378) |\n| Choosing k | Cut the dendrogram at a threshold, at the largest gap in merge heights, or stop at a distance threshold[6](https://www.math.kth.se/matstat/gru/sf2935/sf2935lect17a.pdf) • [7](https://scikit-learn.org/stable/modules/generated/sklearn.cluster.AgglomerativeClustering.html) |\n| Software defaults | scikit-learn defaults to Ward; R's hclust offers ward.D2 for Ward's actual criterion[7](https://scikit-learn.org/stable/modules/generated/sklearn.cluster.AgglomerativeClustering.html) • [8](https://search.r-project.org/R/refmans/stats/html/hclust.html) |\n\n## How it works\n\nThe algorithm is greedy: at every step it merges the pair of clusters that is currently closest, and it never revisits a merge. What \"closest\" means is the linkage criterion. Single linkage takes the minimum dissimilarity over all cross pairs, complete linkage the maximum, and average linkage ([UPGMA](https://www.edgepedia.org/upgma)) the mean over all n_A·n_B cross pairs.[9](https://www.stat.cmu.edu/~ryantibs/datamining/lectures/05-clus2.pdf) • [4](https://lanselin.github.io/introbook_vol2/agglomerative-clustering.html) Weighted average (WPGMA) and the centroid and median schemes complete the seven most common methods.[3](https://ar5iv.labs.arxiv.org/html/1109.2378) The first four operate on a dissimilarity matrix alone, while Ward, centroid, and median are geometric methods that need Euclidean coordinates.[10](https://jmlr.org/papers/volume19/18-117/18-117.pdf)\n\nAfter a merge, updated distances are usually computed with the Lance–Williams recurrence,\n\n\\[ d(I \\cup J, K) = \\alpha_{I}\\, d(I,K) + \\alpha_{J}\\, d(J,K) + \\beta\\, d(I,J) + \\gamma\\, |d(I,K) - d(J,K)|, \\]\n\nintroduced by Lance and Williams in 1967; setting \\( \\alpha_{I} = \\alpha_{J} = 1/2 \\), \\( \\beta = 0 \\) and \\( \\gamma = -1/2 \\) gives single linkage, and each linkage corresponds to its own coefficients.[3](https://ar5iv.labs.arxiv.org/html/1109.2378)\n\n**Ward's method** defines the distance between clusters A and B as the increase in the total within-cluster sum of squares caused by merging them,[11](https://www.stat.cmu.edu/~cshalizi/350/lectures/08/lecture-08.pdf)\n\n\\[ \\Delta(A,B) = \\frac{n_{A}\\, n_{B}}{n_{A}+n_{B}} \\lVert \\bar{x}_{A} - \\bar{x}_{B} \\rVert^{2}, \\]\n\nwhere n_A and n_B are the cluster sizes and x̄_A, x̄_B their centroids.[4](https://lanselin.github.io/introbook_vol2/agglomerative-clustering.html) This quantity is exactly the increase in k-means cost occasioned by merging the two clusters,[12](https://proceedings.neurips.cc/paper_files/paper/2003/file/f7696a9b362ac5a51c3dc8f098b73923-Paper.pdf) and by Huyghens' variance decomposition, minimizing within-cluster variance is the same as maximizing between-cluster variance.[13](https://arxiv.org/pdf/1111.6285.pdf)\n\n## How it is done\n\nA practitioner first chooses a distance metric and a linkage. Ward, centroid, and median are correctly defined only with the Euclidean metric;[14](https://docs.scipy.org/doc/scipy/reference/generated/scipy.cluster.hierarchy.linkage.html) single, complete, and average linkage work on any dissimilarity matrix and produce dendrograms with no inversions.[9](https://www.stat.cmu.edu/~ryantibs/datamining/lectures/05-clus2.pdf) The merges are then run, and the actual clustering is obtained by cutting the dendrogram at a threshold dissimilarity value.[6](https://www.math.kth.se/matstat/gru/sf2935/sf2935lect17a.pdf) Cutting rules include a prespecified similarity level or the height where the gap between successive merge distances is largest.[5](https://nlp.stanford.edu/IR-book/pdf/17hier.pdf) For Ward, a rule of thumb is to keep reducing k until the merge cost jumps and take the k right before the jump.[11](https://www.stat.cmu.edu/~cshalizi/350/lectures/08/lecture-08.pdf)\n\nIn software, scikit-learn defaults to Ward and accepts only euclidean or l2 metrics for it;[7](https://scikit-learn.org/stable/modules/generated/sklearn.cluster.AgglomerativeClustering.html) SciPy returns an \\( (n-1) \\times 4 \\) linkage matrix of merged cluster indices, merge distance, and cluster size.[14](https://docs.scipy.org/doc/scipy/reference/generated/scipy.cluster.hierarchy.linkage.html) In R's hclust, option \"ward.D\" does not implement Ward's 1963 criterion, whereas \"ward.D2\" does, per Murtagh and Legendre (2014).[8](https://search.r-project.org/R/refmans/stats/html/hclust.html)\n\n## Origin\n\nThe history of agglomerative clustering goes back at least to the 1950s, with biological taxonomy a driving force as the first biologists using computers to classify organisms discussed several agglomerative methods.[1](https://ar5iv.labs.arxiv.org/html/1012.3697) Ward's minimum-variance approach was published as Joe H. Ward, \"Hierarchical Grouping to Optimize an Objective Function\", Journal of the [American Statistical Association](https://www.edgepedia.org/american-statistical-association), 1963.[15](https://doi.org/10.1080/01621459.1963.10500845) McQuitty's weighted (WPGMA) linkage comes from Louis L. McQuitty's 1966 paper in [Educational and Psychological Measurement](https://www.edgepedia.org/educational-and-psychological-measurement).[16](https://doi.org/10.1177/001316446602600402) The dissimilarity update form is succinct, though the original paper does not consider the Ward criterion; the Ward algorithm was written in the Lance–Williams framework using squared dissimilarities.[13](https://arxiv.org/pdf/1111.6285.pdf) Gower and Ross (1969) observed that single linkage is related to the minimum spanning tree, and the class is characterized as SAHN (sequential, agglomerative, hierarchic, nonoverlapping).[3](https://ar5iv.labs.arxiv.org/html/1109.2378)\n\n## Variants\n\nWhen the input is an explicit dense dissimilarity matrix, it alone is Θ(N²) because all pairwise dissimilarities must be processed, so run time is bounded below by Ω(N²); sparse-graph or structured inputs need not store or process all pairwise dissimilarities, and the primitive algorithm on dense input takes Θ(N³).[3](https://ar5iv.labs.arxiv.org/html/1109.2378) The nearest-neighbor-chain algorithm, described by Fionn Murtagh in 1985, guarantees \\( O(N^{2}) \\) worst-case time for single, complete, average, weighted, and Ward;[3](https://ar5iv.labs.arxiv.org/html/1109.2378) maintaining nearest-neighbor lists (Anderberg, 1973) reduces best-case complexity from Θ(N³) to Θ(N²).[3](https://ar5iv.labs.arxiv.org/html/1109.2378) SciPy implements single linkage via an optimized MST algorithm and the other four main methods via nearest-neighbor chains, all \\( O(n^{2}) \\) time with \\( O(n^{2}) \\) memory.[14](https://docs.scipy.org/doc/scipy/reference/generated/scipy.cluster.hierarchy.linkage.html)\n\nFor very large datasets, BIRCH incrementally clusters incoming multi-dimensional points, typically finding good clusters in a single scan using its CF-tree in-memory summary.[17](https://dl.acm.org/doi/10.1145/235968.233324) • [18](https://research.ibm.com/publications/birch-a-new-data-clustering-algorithm-and-its-applications) Noise-tolerant variants include Wishart's method and CURE (Guha, Rastogi and Shim, 1998).[19](https://jmlr.org/papers/volume15/balcan14a/balcan14a.pdf) • [20](https://doi.org/10.1145/276305.276312) On graphs, Dhulipala and colleagues (2021) gave the first efficient Õ(m)-time exact algorithms for complete- and WPGMA-linkage HAC and a Õ(n√m)-time exact algorithm for average linkage, with an Õ(m) approximate average-linkage variant.[21](https://proceedings.mlr.press/v139/dhulipala21a.html)\n\nRecent work targets GPUs and approximation. A TSP-graph method approximates [Ward's method](https://www.edgepedia.org/wards-method), achieving a 25:1 speedup over the best exact Ward implementation with identical results, using \\( O(T \\cdot N) \\) memory instead of \\( O(N^{2}) \\).[22](https://link.springer.com/article/10.1186/s40537-024-01053-x) PANDORA is a fully parallel, work-optimal \\( O(n \\log n) \\) GPU algorithm for single-linkage dendrogram construction via recursive tree contraction on the MST, with speedups of 6–20x on AMD MI250X and 10–37x on Nvidia A100.[23](https://arxiv.org/html/2401.06089)\n\n## Applications\n\nAverage linkage is a standard tool for analyzing gene expression data.[12](https://proceedings.neurips.cc/paper_files/paper/2003/file/f7696a9b362ac5a51c3dc8f098b73923-Paper.pdf) [Biological taxonomy](https://www.edgepedia.org/taxonomy-biology) was a historical driving force of the method,[1](https://ar5iv.labs.arxiv.org/html/1012.3697) and BIRCH has been applied to building an interactive pixel classification tool and generating the initial codebook for image compression.[18](https://research.ibm.com/publications/birch-a-new-data-clustering-algorithm-and-its-applications)\n\n## Limitations and alternatives\n\n**Single linkage** defines cluster similarity by the most similar members, a local criterion that suffers from a chaining effect in which merges add single points or pairs and form chains.[5](https://nlp.stanford.edu/IR-book/pdf/17hier.pdf) **Complete linkage** uses the most dissimilar members, avoiding chaining but suffering from crowding and sensitivity to outliers.[5](https://nlp.stanford.edu/IR-book/pdf/17hier.pdf) • [9](https://www.stat.cmu.edu/~ryantibs/datamining/lectures/05-clus2.pdf) Average linkage strikes a balance, but its results can change under monotone transformations of the dissimilarities.[9](https://www.stat.cmu.edu/~ryantibs/datamining/lectures/05-clus2.pdf) Many classic agglomerative algorithms are not robust to noise; Wishart's method, CURE, and Ward are preferable in the presence of noise, but these lack theoretical robustness guarantees.[19](https://jmlr.org/papers/volume15/balcan14a/balcan14a.pdf)\n\n**Inversions.** The centroid and median formulas can produce non-monotonic dendrograms whose merge heights decrease, which are hard to interpret; the other five methods cannot.[3](https://ar5iv.labs.arxiv.org/html/1109.2378) • [8](https://search.r-project.org/R/refmans/stats/html/hclust.html) One reference work states the opposite for Ward, that \"The Ward AHC is not monotonous because there can exist inversions\".[2](https://franknielsen.github.io/Clustering/BookChapter-HierarchicalClustering.pdf) For the Ward criterion as defined in this article, implemented with squared Euclidean distances, merge heights are monotone; inversions arise only from variants or implementations that use a different distance convention.\n\n**Relation to k-means.** Ward's merge distance is exactly the increase in k-means cost from a merge,[12](https://proceedings.neurips.cc/paper_files/paper/2003/file/f7696a9b362ac5a51c3dc8f098b73923-Paper.pdf) and Ward's sum-of-squares for a given k is usually larger than k-means' minimum; a common trick is to run k-means starting from the clusters found by Ward's method.[11](https://www.stat.cmu.edu/~cshalizi/350/lectures/08/lecture-08.pdf) Unlike k-means, agglomerative clustering is greedy and deterministic and returns a sequence of nested partitions; single-link clustering can handle complicated cluster shapes but only wants separation, not compactness.[11](https://www.stat.cmu.edu/~cshalizi/350/lectures/08/lecture-08.pdf)\n\n## References\n\n1. [Analysis of Agglomerative Clustering (Algorithmica; preliminary version STACS 2011)](https://ar5iv.labs.arxiv.org/html/1012.3697)\n2. [Hierarchical Clustering (book chapter, Frank Nielsen)](https://franknielsen.github.io/Clustering/BookChapter-HierarchicalClustering.pdf)\n3. [Modern hierarchical, agglomerative clustering algorithms (Daniel Müllner, arXiv:1109.2378)](https://ar5iv.labs.arxiv.org/html/1109.2378)\n4. [An Introduction to Spatial Data Science with GeoDa, vol. 2, §5.3 Agglomerative Clustering (Anselin)](https://lanselin.github.io/introbook_vol2/agglomerative-clustering.html)\n5. [Introduction to Information Retrieval, Chapter 17: Hierarchical clustering](https://nlp.stanford.edu/IR-book/pdf/17hier.pdf)\n6. [Modern Methods of Statistical Learning sf2935, Hierarchic Clustering (Timo Koski, KTH)](https://www.math.kth.se/matstat/gru/sf2935/sf2935lect17a.pdf)\n7. [AgglomerativeClustering, scikit-learn documentation](https://scikit-learn.org/stable/modules/generated/sklearn.cluster.AgglomerativeClustering.html)\n8. [R: Hierarchical Clustering (hclust documentation)](https://search.r-project.org/R/refmans/stats/html/hclust.html)\n9. [CMU Data Mining Lecture 5: Hierarchical clustering (Tibshirani)](https://www.stat.cmu.edu/~ryantibs/datamining/lectures/05-clus2.pdf)\n10. [An Efficient and Effective Generic Agglomerative Hierarchical Clustering Approach (SNK-AHC, JMLR)](https://jmlr.org/papers/volume19/18-117/18-117.pdf)\n11. [CMU 36-350 Lecture 8: Hierarchical Clustering (Shalizi)](https://www.stat.cmu.edu/~cshalizi/350/lectures/08/lecture-08.pdf)\n12. [An Iterative Improvement Procedure for Hierarchical Clustering (NeurIPS 2003)](https://proceedings.neurips.cc/paper_files/paper/2003/file/f7696a9b362ac5a51c3dc8f098b73923-Paper.pdf)\n13. [Ward's Hierarchical Clustering Method: Clustering Criterion and Agglomerative Algorithm (Murtagh & Legendre)](https://arxiv.org/pdf/1111.6285.pdf)\n14. [scipy.cluster.hierarchy.linkage, SciPy v1.18.0 Manual](https://docs.scipy.org/doc/scipy/reference/generated/scipy.cluster.hierarchy.linkage.html)\n15. [Joe H. Ward (1963). Hierarchical Grouping to Optimize an Objective Function. Journal of the American Statistical Association.](https://doi.org/10.1080/01621459.1963.10500845)\n16. [Louis L. McQuitty (1966). Similarity Analysis by Reciprocal Pairs for Discrete and Continuous Data. Educational and Psychological Measurement.](https://doi.org/10.1177/001316446602600402)\n17. [BIRCH: an efficient data clustering method for very large databases (Zhang, Ramakrishnan, Livny; SIGMOD 1996)](https://dl.acm.org/doi/10.1145/235968.233324)\n18. [BIRCH: A new data clustering algorithm and its applications (IBM Research / Data Mining and Knowledge Discovery, 1997)](https://research.ibm.com/publications/birch-a-new-data-clustering-algorithm-and-its-applications)\n19. [Clustering (robust agglomerative clustering, JMLR)](https://jmlr.org/papers/volume15/balcan14a/balcan14a.pdf)\n20. [Sudipto Guha, Rajeev Rastogi, Kyuseok Shim (1998). CURE. ACM SIGMOD Record.](https://doi.org/10.1145/276305.276312)\n21. [Hierarchical Agglomerative Graph Clustering in Nearly-Linear Time (Dhulipala, Eisenstat, Łącki, Mirrokni, Shi; ICML 2021)](https://proceedings.mlr.press/v139/dhulipala21a.html)\n22. [Fast agglomerative clustering using approximate traveling salesman solutions (Journal of Big Data, 2024)](https://link.springer.com/article/10.1186/s40537-024-01053-x)\n23. [PANDORA: A Parallel Dendrogram Construction Algorithm for Single Linkage Clustering on GPU (2024)](https://arxiv.org/html/2401.06089)\n\n---\n*Topic: Encyclopedia › Technology and the built world › Computing and digital systems › Artificial intelligence and data › Machine learning and neural computation › Machine learning methods › Supervised, unsupervised, and semi-supervised learning › Clustering algorithms*\n\n*Initially written Sep 29, 2026 · Edited: Oct 15, 2026*\n\n*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*\n\nLicense: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license\n", "same_as": [ "https://www.stat.cmu.edu/~ryantibs/datamining/lectures/05-clus2.pdf", "https://www.stat.cmu.edu/~cshalizi/350/lectures/08/lecture-08.pdf" ], "url": "https://www.edgepedia.org/agglomerative-hierarchical-clustering", "markdown_url": "https://www.edgepedia.org/agglomerative-hierarchical-clustering.md", "license": { "name": "Edgepedia Community License 1.0", "url": "https://www.edgepedia.org/edgepedia/license", "summary": "Free with credit, commercial use included. AI training is open to everyone. For other uses, organizations over USD 100M in revenue or 100M monthly users license separately.", "spdx": "LicenseRef-Edgepedia-Community-1.0" }, "credit": "\"Agglomerative hierarchical clustering\", Edgepedia (EdgeChat), https://www.edgepedia.org/agglomerative-hierarchical-clustering. Edgepedia Community License 1.0.", "credit_md": "\"[Agglomerative hierarchical clustering](https://www.edgepedia.org/agglomerative-hierarchical-clustering)\", Edgepedia (EdgeChat), [https://www.edgepedia.org/agglomerative-hierarchical-clustering](https://www.edgepedia.org/agglomerative-hierarchical-clustering). [Edgepedia Community License 1.0](https://www.edgepedia.org/edgepedia/license).", "credit_html": "\"Agglomerative hierarchical clustering\", Edgepedia (EdgeChat), https://www.edgepedia.org/agglomerative-hierarchical-clustering. Edgepedia Community License 1.0.", "speakable": "Agglomerative hierarchical clustering is a bottom-up clustering method that starts with each data point as its own cluster and merges the closest pairs, yielding a dendrogram." }