@Alias(value={"complete","clink","complete-link","farthest-neighbor","de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical.CompleteLinkageMethod"}) @Priority(value=100) @Reference(authors="T. S\u00f8rensen",title="A method of establishing groups of equal amplitude in plant sociology based on similarity of species and its application to analyses of the vegetation on Danish commons",booktitle="Biologiske Skrifter 5 (4)",bibkey="journals/misc/Sorensen48") @Reference(authors="P. Macnaughton-Smith",title="Some statistical and other numerical techniques for classifying individuals",booktitle="Home Office Res. Rpt. No. 6, H.M.S.O., London",bibkey="journals/misc/MacnaughtonSmith65") @Reference(authors="G. N. Lance, W. T. Williams",title="A general theory of classificatory sorting strategies 1. Hierarchical systems",booktitle="The Computer Journal 9.4",url="https://doi.org/10.1093/comjnl/9.4.373",bibkey="doi:10.1093/comjnl/9.4.373") @Reference(authors="S. C. Johnson",title="Hierarchical clustering schemes",booktitle="Psychometrika 32",url="https://doi.org/10.1007/BF02289588",bibkey="doi:10.1007/BF02289588") public class CompleteLinkage extends java.lang.Object implements Linkage
The distance of two clusters is simply the maximum of all pairwise distances between the two clusters.
The distance of two clusters is defined as: \[d_{\max}(A,B):=\max_{a\in A}\max_{b\in B} d(a,b)\]
This can be computed recursively using: \[d_{\max}(A\cup B,C) = \max(d(A,C), d(B,C))\]
Note that with similarity functions, one would need to use the minimum instead to get the same effect.
The algorithm CLINK is a faster algorithm to find such clusterings,
but it is very much order dependent and tends to find worse solutions.
References:
This is attributed to different sources that are not easily verifiable. Lance and Williams (1967) attribute the idea to Macnaughton-Smith, albeit he may have suggested a divisive rather than agglomerative procedure, but Sørensen may have used this already in 1948 (and is credited, e.g., by Johnson 1967).
T. Sørensen
A method of establishing groups of equal amplitude in plant sociology based
on similarity of species and its application to analyses of the vegetation on
Danish commons
Biologiske Skrifter 5 (4)
P. Macnaughton-Smith
Some statistical and other numerical techniques for classifying
individuals
Home Office Res. Rpt. No. 6, H.M.S.O., London
G. N. Lance, W. T. Williams
A general theory of classificatory sorting strategies
1. Hierarchical systems
The Computer Journal 9.4
S. C. Johnson
Hierarchical clustering schemes
Psychometrika 32
| Modifier and Type | Class and Description |
|---|---|
static class |
CompleteLinkage.Parameterizer
Class parameterizer.
|
| Modifier and Type | Field and Description |
|---|---|
static CompleteLinkage |
STATIC
Static instance of class.
|
| Constructor and Description |
|---|
CompleteLinkage()
Deprecated.
use the static instance
STATIC instead. |
| Modifier and Type | Method and Description |
|---|---|
double |
combine(int sizex,
double dx,
int sizey,
double dy,
int sizej,
double dxy)
Compute combined linkage for two clusters.
|
public static final CompleteLinkage STATIC
@Deprecated public CompleteLinkage()
STATIC instead.public double combine(int sizex,
double dx,
int sizey,
double dy,
int sizej,
double dxy)
Linkagecombine in interface Linkagesizex - Size of first cluster x before mergingdx - Distance of cluster x to j before mergingsizey - Size of second cluster y before mergingdy - Distance of cluster y to j before mergingsizej - Size of candidate cluster jdxy - Distance between clusters x and y before mergingCopyright © 2019 ELKI Development Team. License information.