Agglomerative hierarchical clustering

Start with singleton clusters and repeatedly merge the two clusters with the smallest chosen intercluster dissimilarity. Single-linkage clustering uses the smallest cross-pair distance; complete-linkage clustering uses the largest. Merge heights and sensitivity to ties help assess a proposed number of groups.

Ward clustering merges the pair causing the smallest increase in within-cluster sum of squares. Expanding each cluster's squared deviations about the merged mean gives the displayed increase. Its Euclidean sum-of-squares interpretation must not be asserted for arbitrary non-Euclidean dissimilarities.

Average linkage merges the pair with the smallest mean cross-pair dissimilarity. This differs from the minimum used by single-linkage clustering and the maximum used by complete-linkage clustering. The convention here weights individual cross-pairs equally; weighting already formed clusters equally is a different algorithm.

The min and max cross-pair definitions of single-linkage clustering and complete-linkage clustering remain meaningful for a symmetric nonnegative dissimilarity matrix that violates the triangle inequality. Such a calculation gives a valid algorithmic dendrogram, but does not turn the original matrix into Euclidean distances. A triangle-inequality counterexample identifies that source defect without requiring invented replacement data.

A dendrogram displays successive cluster merges, with the height of each merge equal to its intercluster dissimilarity. Cutting at a height gives a partition. Single-linkage clustering measures the closest cross-pair and can form chains, while complete-linkage clustering measures the farthest cross-pair and favors smaller within-cluster diameters.

The farthest cross-pair distance determines the next merge. It favors groups with small diameter and reduces the chaining effect of single-linkage clustering, but can be sensitive to isolated extreme observations. Ties can affect intermediate partitions.

The nearest cross-pair distance determines the next merge. At a threshold, clusters are connected components of the graph joining pairs below that threshold. This handles nonconvex shapes but can join otherwise separate groups through a chain of intermediate observations.