Hierarchical clustering: Difference between revisions

Revision as of 02:22, 7 May 2025

Latest revision as of 00:47, 31 July 2025

(17 intermediate revisions by 10 users not shown)

Line 3:

{{Machine learning|Clustering}}

In [[data mining]] and [[statistics]], '''hierarchical clustering'''<ref (alsoname="HC">{{cite calledbook '''hierarchical|first=Frank cluster|last=Nielsen analysis'''| or '''HCA''') is a method of [[cluster analysis]] that seekstitle=Introduction to buildHPC awith [[hierarchy]]MPI offor clusters.Data Strategies forScience hierarchical| clustering generallyyear=2016 fall| intopublisher=Springer two|isbn=978-3-319-21903-5 categories:|pages=195–211

|chapter=8. Hierarchical Clustering | url=https://www.springer.com/gp/book/9783319219028 |chapter-url=https://www.researchgate.net/publication/314700681 }}</ref> are(also usuallycalled presented'''hierarchical incluster analysis''' or '''HCA''') is a method of [[dendrogramcluster analysis]] that seeks to build a [[hierarchy]] of clusters. Strategies for hierarchical clustering generally fall into two categories:

* '''Agglomerative''': Agglomerative clustering, often referred to as a "bottom-up" approach, begins with each data point as an individual cluster. At each step, the algorithm merges the two most similar clusters based on a chosen distance metric (e.g., Euclidean distance) and linkage criterion (e.g., single-linkage, complete-linkage).<ref name=":4">{{Cite journal |last1=Murtagh |first1=Fionn |last2=Contreras |first2=Pedro |date=2012 |title=Algorithms for hierarchical clustering: an overview |url=https://wires.onlinelibrary.wiley.com/doi/10.1002/widm.53 |journal=WIREs Data Mining and Knowledge Discovery |language=en |volume=2 |issue=1 |pages=86–97 |doi=10.1002/widm.53 |issn=1942-4795|url-access=subscription }}</ref> This process continues until all data points are combined into a single cluster or a stopping criterion is met. Agglomerative methods are more commonly used due to their simplicity and computational efficiency for small to medium-sized datasets.<ref>{{Cite journal |last=Mojena |first=R. |date=1977-04-01 |title=Hierarchical grouping methods and stopping rules: an evaluation |url=https://academic.oup.com/comjnl/article-lookup/doi/10.1093/comjnl/20.4.359 |journal=The Computer Journal |language=en |volume=20 |issue=4 |pages=359–363 |doi=10.1093/comjnl/20.4.359 |issn=0010-4620}}</ref>

* '''Divisive''': Divisive clustering, known as a "top-down" approach, starts with all data points in a single cluster and recursively splits the cluster into smaller ones. At each step, the algorithm selects a cluster and divides it into two or more subsets, often using a criterion such as maximizing the distance between resulting clusters. Divisive methods are less common but can be useful when the goal is to identify large, distinct clusters first.

In general, the merges and splits are determined in a [[greedy algorithm|greedy]] manner. The results of hierarchical clustering<ref>{{cite book |firstname=Frank"HC" |last=Nielsen/> |are title=Introductionusually topresented HPCin witha MPI[[dendrogram]]. for Data Science | year=2016 | publisher=Springer |isbn=978-3-319-21903-5 |pages=195–211

|chapter=8. Hierarchical Clustering | url=https://www.springer.com/gp/book/9783319219028 |chapter-url=https://www.researchgate.net/publication/314700681 }}</ref> are usually presented in a [[dendrogram]].

Hierarchical clustering has the distinct advantage that any valid measure of distance can be used. In fact, the observations themselves are not required: all that is used is a [[distance matrix|matrix of distances]]. On the other hand, except for the special case of single-linkage distance, none of the algorithms (except exhaustive search in <math>\mathcal{O}(2^n)</math>) can be guaranteed to find the optimum solution.{{cn|date=October 2024}}

== Greedy Nature of the Algorithm ==

Hierarchical clustering is often described as a greedy algorithm because it makes a series of locally optimal choices without reconsidering previous steps. At each iteration, it merges the two clusters that are closest together based on a selected distance metric, always choosing the best immediate option available. This approach is "greedy" because it seeks to optimize the current decision rather than planning for the best possible overall clustering. Once two clusters are merged, the decision is final and irreversible, without the possibility of backtracking, which can lead to suboptimal results if earlier choices were not ideal. Despite this, the greedy nature of hierarchical clustering makes it computationally efficient and simple to implement, though it may not always capture the true underlying structure of complex datasets.

== Complexity ==

The standard algorithm for '''hierarchical agglomerative clustering''' (HAC) has a [[time complexity]] of <math>\mathcal{O}(n^3)</math> and requires <math>\Omega(n^2)</math> memory, which makes it too slow for even medium data sets. However, for some special cases, optimal efficient agglomerative methods (of complexity <math>\mathcal{O}(n^2)</math>) are known: '''SLINK'''<!--boldface per WP:R#PLA--><ref name="SLINK">{{cite journal | author=R. Sibson | title=SLINK: an optimally efficient algorithm for the single-link cluster method | journal=The Computer Journal | volume=16 | issue=1 | pages=30–34 | year=1973 | publisher=British Computer Society | url=http://www.cs.gsu.edu/~wkim/index_files/papers/sibson.pdf | doi=10.1093/comjnl/16.1.30| doi-access=free }}</ref> for [[Single-linkage clustering|single-linkage]] and CLINK<ref name="CLINK">{{cite journal | author=D. Defays | title=An efficient algorithm for a complete-link method | journal=The Computer Journal | volume=20 | issue=4 | pages=364–6 | year=1977 | publisher=British Computer Society | doi=10.1093/comjnl/20.4.364| doi-access= }}</ref> for [[complete-linkage clustering]]. With a [[heap (data structure)|heap]], the runtime of the general case can be reduced to <math>\mathcal{O}(n^2 \log n)</math>, an improvement on the aforementioned bound of <math>\mathcal{O}(n^3)</math>, at the cost of further increasing the memory requirements. In many cases, the memory overheads of this approach are too large to make it practically usable. Methods exist which use [[quadtree]]s that demonstrate <math>\mathcal{O}(n^2)</math> total running time with <math>\mathcal{O}(n)</math> space.<ref name=":2"DE>{{Cite journal |last=Eppstein |first=David |date=2001-12-31 |title=Fast hierarchical clustering and other applications of dynamic closest pairs |url=https://dl.acm.org/doi/10.1145/351827.351829 |journal=ACM Journal of Experimental Algorithmics |volume=5 |pages=1–es |doi=10.1145/351827.351829 |issn=1084-6654|arxiv=cs/9912014 }}</ref>

Divisive clustering with an exhaustive search is <math>\mathcal{O}(2^n)</math>, but it is common to use faster heuristics to choose splits, such as [[k-means clustering|''k''-means]].

== DecidingCluster Linkage Criteria ==

In hierarchicalorder clustering,to whetherdecide agglomerativewhich (bottom-up)clusters orshould divisivebe combined (top-downfor agglomerative), decisionsor aboutwhere merginga orcluster splittingshould clustersbe dependsplit on(for divisive), a measure of dissimilarity between sets of observations is required. ThisIn dissimilaritymost ismethods typicallyof definedhierarchical clustering, this is achieved by twouse components:of aan appropriate [[distance]] metric''d'', (such as the Euclidean distance), appliedbetween to''single'' individualobservations of the data pointsset, and a '''linkage criterion, which specifies the dissimilarity of ''sets'' as a function of the pairwise distances of observations in the sets. The choice of metric as well as linkage can have a major impact on the result of the clustering, whichwhere the lower level metric determines howwhich distancesobjects betweenare most [[similarity measure|similar]], whereas the linkage criterion influences the shape of the clusters. areFor computedexample, fromcomplete-linkage thesetends pairwiseto pointproduce distancesmore spherical clusters than single-linkage.

The '''linkage criterion''' plays a central role in shaping the resulting cluster structure. It defines the distance between clusters as a function of the distances between observations they contain. The combination of the metric and linkage choice influences both the granularity and the geometry of the final clusters. For instance, some linkage methods emphasize compactness, while others favor connectivity, potentially resulting in elongated or irregular clusters.

=== Common Linkage Criteria ===

'''Single linkage''' (nearest neighbor) defines the distance between two clusters as the shortest distance between any pair of points, one from each cluster. This method is computationally efficient and capable of detecting non-convex cluster shapes. However, it is highly sensitive to noise and can lead to a "chaining effect," where distant points are merged due to a connected sequence of close neighbors.

The linkage criterion determines the distance between sets of observations as a function of the pairwise distances between observations.

# '''Complete linkage''' (farthest neighbor) uses the maximum distance between any pair of observations across two clusters. This approach tends to produce more compact, spherical clusters and is less prone to chaining. However, it can be overly sensitive to outliers and may split larger clusters prematurely if internal variance is high.

# '''Average linkage''' (also known as UPGMA—Unweighted Pair Group Method with Arithmetic Mean) calculates the mean of all pairwise distances between points in two clusters. It strikes a balance between the tightness of complete linkage and the flexibility of single linkage. This method typically yields clusters of moderate size and variance, making it suitable when cluster homogeneity is expected.

# '''Ward’s method''' takes a different approach by focusing on minimizing the total within-cluster variance at each step. It merges the pair of clusters whose union results in the smallest increase in the sum of squared distances to the cluster centroids. This often leads to compact, evenly-sized clusters and is particularly effective for datasets with continuous variables.

# '''Centroid linkage''' defines cluster distance based on the Euclidean distance between their centroids (mean vectors). While intuitive, it may produce '''inversions'''—situations where the merged cluster appears closer to another cluster than the original components were—potentially distorting the hierarchy. This makes centroid linkage less robust in some contexts, particularly with non-convex clusters.

Each linkage method has its advantages and trade-offs. The optimal choice depends on the characteristics of the dataset and the objectives of the clustering. For example, Ward's method is preferred when variance minimization is crucial, while single linkage might be selected for detecting complex, non-globular shapes. Visualization tools such as '''dendrograms''' can be particularly helpful in comparing the results of different linkage criteria and understanding their effect on the clustering structure. Some commonly used linkage criteria between two sets of observations ''A'' and ''B'' and a distance ''d'' are:<ref>{{cite web | title=The CLUSTER Procedure: Clustering Methods | url=https://support.sas.com/documentation/cdl/en/statug/63033/HTML/default/statug_cluster_sect012.htm | work=SAS/STAT 9.2 Users Guide | publisher= [[SAS Institute]] | access-date=2009-04-26}}</ref><ref>{{cite journal |last1=Székely |first1=G. J. |last2=Rizzo |first2=M. L. |year=2005 |title=Hierarchical clustering via Joint Between-Within Distances: Extending Ward's Minimum Variance Method |journal=Journal of Classification |volume=22 |issue=2 |pages=151–183 |doi=10.1007/s00357-005-0012-9 |s2cid=206960007 }}</ref>

{| class="wikitable"

! Names

! Formula

Line 56 ⟶ 45:

|<math>d(i\cup j, k) = d(m_{i\cup j}, m_k)</math> where <math>m_{i\cup j} = \tfrac{1}{2}\left(m_i + m_j\right)</math>

|-

|Versatile linkage clustering<ref name=":6">{{cite journal | doi=10.1007/s00357-019-09339-z | last1=Fernández | first1=Alberto | last2=Gómez | first2=Sergio | title=Versatile linkage: a family of space-conserving strategies for agglomerative hierarchical clustering | journal=Journal of Classification | volume=37 | year=2020 | issue=3 | pages=584–597| arxiv=1906.09222 | s2cid=195317052 }}</ref>

| <math>\sqrt[p]{\frac{1}{|A|\cdot|B|} \sum_{a \in A }\sum_{ b \in B} d(a,b)^p}, p\neq 0</math>

|-

|[[Ward's method|Ward linkage]],<ref name="wards method">{{cite journal |last=Ward |first=Joe H. |year=1963 |title=Hierarchical Grouping to Optimize an Objective Function |journal=Journal of the American Statistical Association |volume=58 |issue=301 |pages=236–244 |doi=10.2307/2282967 |jstor=2282967 |mr=0148188}}</ref> Minimum Increase of Sum of Squares (MISSQ)<ref name=":0">{{Citation |last=Podani |first=János |title=New combinatorial clustering methods |date=1989 |url=https://doi.org/10.1007/978-94-009-2432-1_5 |work=Numerical syntaxonomy |pages=61–77 |editor-last=Mucina |editor-first=L. |place=Dordrecht |publisher=Springer Netherlands |language=en |doi=10.1007/978-94-009-2432-1_5 |isbn=978-94-009-2432-1 |access-date=2022-11-04 |editor2-last=Dale |editor2-first=M. B.|url-access=subscription }}</ref>

|<math>\frac{|A|\cdot|B|}{|A\cup B|} \lVert \mu_A - \mu_B \rVert ^2

= \sum_{x\in A\cup B} \lVert x - \mu_{A\cup B} \rVert^2

Line 87 ⟶ 76:

- \min_{m\in B} \sum_{y\in B} d(m,y)</math>

|-

|Medoid linkage<ref>{{Cite conference |last1=Miyamoto |first1=Sadaaki |last2=Kaizu |first2=Yousuke |last3=Endo |first3=Yasunori |date=2016 |title=Hierarchical and Non-Hierarchical Medoid Clustering Using Asymmetric Similarity Measures |url=https://ieeexplore.ieee.org/document/7801678 |conference=2016 Joint 8th International Conference on Soft Computing and Intelligent Systems (SCIS) and 17th International Symposium on Advanced Intelligent Systems (ISIS) |pages=400–403 |doi=10.1109/SCIS-ISIS.2016.0091}}</ref><ref name=":3">{{Cite conference |date=2016 |title=Visual Clutter Reduction through Hierarchy-based Projection of High-dimensional Labeled Data| conference=Graphics Interface |url=https://graphicsinterface.org/wp-content/uploads/gi2016-14.pdf | first1=Dominik|last1=Herr|first2=Qi|last2=Han|first3=Steffen|last3=Lohmann| first4=Thomas |last4=Ertl |access-date=2022-11-04 |website=Graphics Interface |language=en-CA |doi=10.20380/gi2016.14}}</ref>

|<math>d(m_A, m_B)</math> where <math>m_A</math>, <math>m_B</math> are the medoids of the previous clusters

|-

Line 97 ⟶ 86:

* The probability that candidate clusters spawn from the same distribution function (V-linkage).

* The product of in-degree and out-degree on a k-nearest-neighbour graph (graph degree linkage).<ref>{{Cite book|last1=Zhang|first1=Wei|last2=Wang|first2=Xiaogang|last3=Zhao|first3=Deli|last4=Tang|first4=Xiaoou|title=Computer Vision – ECCV 2012 |chapter=Graph Degree Linkage: Agglomerative Clustering on a Directed Graph |date=2012|editor-last=Fitzgibbon|editor-first=Andrew|editor2-last=Lazebnik|editor2-first=Svetlana|editor2-link= Svetlana Lazebnik |editor3-last=Perona|editor3-first=Pietro|editor4-last=Sato|editor4-first=Yoichi|editor5-last=Schmid|editor5-first=Cordelia|series=Lecture Notes in Computer Science|language=en|publisher=Springer Berlin Heidelberg|volume=7572|pages=428–441|doi=10.1007/978-3-642-33718-5_31|isbn=9783642337185|arxiv=1208.5092|bibcode=2012arXiv1208.5092Z|s2cid=14751}} See also: https://github.com/waynezhanghk/gacluster</ref>

* The increment of some cluster descriptor (i.e., a quantity defined for measuring the quality of a cluster) after merging two clusters.<ref>{{cite journal |first1=W. |last1=Zhang |first2=D. |last2=Zhao |first3=X. |last3=Wang |title=Agglomerative clustering via maximum incremental path integral |journal=Pattern Recognition |volume=46 |issue=11 |pages=3056–65 |date=2013 |doi=10.1016/j.patcog.2013.04.013 |citeseerx=10.1.1.719.5355 |bibcode=2013PatRe..46.3056Z}}</ref><ref>{{cite book |last1=Zhao |first1=D. |last2=Tang |first2=X. |chapter=Cyclizing clusters via zeta function of a graph |chapter-url= |title=NIPS'08: Proceedings of the 21st International Conference on Neural Information Processing Systems |date=2008 |isbn=9781605609492 |pages=1953–60 |publisher=Curran |citeseerx=10.1.1.945.1649}}</ref><ref>{{cite journal |first1=Y. |last1=Ma |first2=H. |last2=Derksen |first3=W. |last3=Hong |first4=J. |last4=Wright |title=Segmentation of Multivariate Mixed Data via Lossy Data Coding and Compression |journal=IEEE Transactions on Pattern Analysis and Machine Intelligence |volume=29 |issue=9 |pages=1546–62 |date=2007 |doi=10.1109/TPAMI.2007.1085 |pmid=17627043 |bibcode=2007ITPAM..29.1546M |hdl=2142/99597 |s2cid=4591894 |hdl-access=free }}</ref>

== Agglomerative clustering example ==

Line 151 ⟶ 140:

The dendrogram of DIANA can be constructed by letting the splinter group <math>C_\textrm{new}</math> be a child of the hollowed-out cluster <math>C_*</math> each time. This constructs a tree with <math>C_0</math> as its root and <math>n</math> unique single-object clusters as its leaves.

== Choosing the Number of Clusters in Hierarchical Clustering ==

Determining the appropriate number of clusters in hierarchical clustering is challenging because the algorithm produces a tree-like structure (dendrogram) rather than a fixed partition. Several visual and quantitative methods can help guide this decision. A common approach is to '''cut the dendrogram''' at a specific height. The number of vertical lines intersected by the cut corresponds to the number of clusters formed. The height at which to cut can be guided by identifying '''large vertical gaps''' between successive merges—these gaps often indicate natural divisions in the data, where clusters are relatively distinct from one another.

Beyond visual inspection, '''internal validation metrics''' can provide more objective guidance:

* '''Elbow Method''': By plotting a measure of within-cluster variation against the number of clusters, the "elbow" point—where the rate of improvement sharply drops—can suggest a suitable number of clusters.

* '''Silhouette Score''': This evaluates how similar a data point is to its own cluster compared to other clusters. Higher average silhouette scores indicate better-defined clusters.

* '''Gap Statistic''': This compares the observed within-cluster dispersion to that expected under a null reference distribution. The optimal number of clusters is often where the gap statistic is highest, adjusted for variability.

No single method guarantees the "correct" answer. Often, the best approach combines multiple methods with ___domain-specific insight to arrive at a clustering that is both statistically sound and contextually meaningful.

== Limitations ==

# '''Time Complexity''': Hierarchical clustering, especially in its basic agglomerative form, has a high time complexity of  O(n³). This becomes a significant bottleneck for large datasets, limiting its scalability <ref name="CLINK" />.   

# '''Scalability''': Due to the time and space complexity, hierarchical clustering algorithms struggle to handle very large datasets efficiently <ref name=":2" />.   

# '''Sensitivity to Noise and Outliers''': Hierarchical clustering methods can be sensitive to noise and outliers in the data, which can lead to the formation of inaccurate or misleading cluster hierarchies <ref name="SLINK" />.   

# '''Difficulty with High-Dimensional Data''': In high-dimensional spaces, hierarchical clustering can face challenges due to the curse of dimensionality, where data points become sparse, and distance measures become less meaningful. This can result in poorly defined clusters <ref name=":3" />.   

# '''Inability to Handle Non-Convex Shapes and Varying Densities''': Traditional hierarchical clustering methods, like many other clustering algorithms, often assume that clusters are convex and have similar densities. They may struggle to accurately identify clusters with non-convex shapes or varying densities <ref>{{Cite journal |last=Wani |first=Aasim Ayaz |date=2024-08-29 |title=Comprehensive analysis of clustering algorithms: exploring limitations and innovative solutions |journal=PeerJ Computer Science |language=en |volume=10 |pages=e2286 |doi=10.7717/peerj-cs.2286 |doi-access=free |issn=2376-5992 |pmc=11419652 |pmid=39314716}}</ref>. 

== Software ==