Editing Hierarchical clustering (section)

== Cluster Linkage ==
In order to decide which clusters should be combined (for agglomerative), or where a cluster should be split (for divisive), a measure of dissimilarity between sets of observations is required. In most methods of hierarchical clustering, this is achieved by use of an appropriate [[distance]] ''d'', such as the Euclidean distance, between ''single'' observations of the data set, 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, where the lower level metric determines which objects are most [[similarity measure|similar]], whereas the linkage criterion influences the shape of the clusters <ref name=":5" />. For example, complete-linkage tends to produce more spherical clusters than single-linkage.

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

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
|-
| Maximum or [[complete-linkage clustering]]
| <math> \max_{a\in A,\, b\in B} d(a,b) </math>
|-
| Minimum or [[single-linkage clustering]]
| <math> \min_{a\in A,\, b\in B} d(a,b) </math>
|-
| Unweighted average linkage clustering (or [[UPGMA]])
| <math> \frac{1}{|A|\cdot|B|} \sum_{a \in A }\sum_{ b \in B} d(a,b). </math>
|-
| Weighted average linkage clustering (or [[WPGMA]])
| <math> d(i \cup j, k) = \frac{d(i, k) + d(j, k)}{2}. </math>
|-
| Centroid linkage clustering, or UPGMC
| <math>\lVert \mu_A-\mu_B\rVert^2</math> where <math>\mu_A</math> and <math>\mu_B</math> are the centroids of ''A'' resp. ''B''.
|-
|Median linkage clustering, or WPGMC 
|<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.}}</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
- \sum_{x\in A} \lVert x - \mu_{A} \rVert^2
- \sum_{x\in B} \lVert x - \mu_{B} \rVert^2</math>
|-
|Minimum Error Sum of Squares (MNSSQ)<ref name=":0" />
|<math>\sum_{x\in A\cup B} \lVert x - \mu_{A\cup B} \rVert^2</math>
|-
|Minimum Increase in Variance (MIVAR)<ref name=":0" />
|<math>\frac{1}{|A\cup B|}\sum_{x\in A\cup B} \lVert x - \mu_{A\cup B} \rVert^2
- \frac{1}{|A|}\sum_{x\in A} \lVert x - \mu_{A} \rVert^2
- \frac{1}{|B|}\sum_{x\in B} \lVert x - \mu_{B} \rVert^2</math><math>= \text{Var}(A\cup B) - \text{Var}(A) - \text{Var}(B)</math>
|-
|Minimum Variance (MNVAR)<ref name=":0" />
|<math>\frac{1}{|A\cup B|}\sum_{x\in A\cup B} \lVert x - \mu_{A\cup B} \rVert^2 = \text{Var}(A\cup B)</math>
|-
|Hausdorff linkage<ref>{{Cite journal |last1=Basalto |first1=Nicolas |last2=Bellotti |first2=Roberto |last3=De Carlo |first3=Francesco |last4=Facchi |first4=Paolo |last5=Pantaleo |first5=Ester |last6=Pascazio |first6=Saverio |date=2007-06-15 |title=Hausdorff clustering of financial time series |url=https://www.sciencedirect.com/science/article/pii/S0378437107001124 |journal=Physica A: Statistical Mechanics and Its Applications |language=en |volume=379 |issue=2 |pages=635–644 |doi=10.1016/j.physa.2007.01.011 |arxiv=physics/0504014 |bibcode=2007PhyA..379..635B |s2cid=27093582 |issn=0378-4371}}</ref>
|<math>\max_{x\in A\cup B} \min_{y\in A\cup B} d(x,y)</math>
|-
|Minimum Sum Medoid linkage<ref name=":1">{{Cite conference |last=Schubert |first=Erich |date=2021 |title=HACAM: Hierarchical Agglomerative Clustering Around Medoids – and its Limitations |url=http://star.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-2993/paper-19.pdf |conference=LWDA’21: Lernen, Wissen, Daten, Analysen September 01–03, 2021, Munich, Germany |pages=191–204 |via=CEUR-WS}}</ref>
|<math>\min_{m\in A\cup B} \sum_{y\in A\cup B} d(m, y)</math> such that m is the medoid of the resulting cluster
|-
|Minimum Sum Increase Medoid linkage<ref name=":1" />
|<math>\min_{m\in A\cup B} \sum_{y\in A\cup B} d(m,y)
- \min_{m\in A} \sum_{y\in A} d(m,y)
- \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>{{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
|-
| [[Energy distance|Minimum energy clustering]]
| <math>  \frac {2}{nm}\sum_{i,j=1}^{n,m} \|a_i- b_j\|_2 - \frac {1}{n^2}\sum_{i,j=1}^{n} \|a_i-a_j\|_2 - \frac{1}{m^2}\sum_{i,j=1}^{m} \|b_i-b_j\|_2 </math>
|}
Some of these can only be recomputed recursively (WPGMA, WPGMC), for many a recursive computation with Lance-Williams-equations is more efficient, while for other (Hausdorff, Medoid) the distances have to be computed with the slower full formula. Other linkage criteria include:

* 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 |hdl=2142/99597 |s2cid=4591894 |hdl-access=free }}</ref>