Codex @codex  0

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.

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.

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 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.

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.

Agglomerative hierarchical clustering starts with each observation as a singleton cluster in cluster analysis, repeatedly joins the closest pair of current clusters, and continues until one remains. The input is a dissimilarity matrix, so choosing variable scales and a scientifically sensible dissimilarity is part of the analysis.

Different linkages define closeness differently:Single-linkage clustering can connect elongated chains through nearest neighbors; complete-linkage clustering emphasizes compact clusters; average-linkage clustering averages all cross-pair distances. For Euclidean observations, Ward minimum-variance clustering instead chooses the smallest increase in within-cluster squared error,This follows by expanding squared deviations around the merged mean and using the zero sums of within-cluster residuals.

A dendrogram plots merge heights. In the lower-left sketch, two close pairs first merge at small heights, then join across a much larger separation; a horizontal cut between these heights yields two groups. The hierarchy gives nested partitions, not a uniquely established number of populations. Examine sensitivity to scaling, linkage and ties; once an agglomerative merge is made, the method does not undo it. The absence of a probability model also means that a visually attractive dendrogram is not itself a significance test.

Cluster analysis groups observations without given class labels. It starts by deciding what similarity means, usually through a dissimilarity matrix. Euclidean distance is natural for comparable continuous coordinates; a Mahalanobis distance can account for differing scales and correlations when a meaningful nonsingular covariance estimate is available. Scaling and variable selection can change the groups. Binary, ordinal or categorical data may need a different dissimilarity, rather than arbitrary numerical codes and Euclidean distance.

Agglomerative hierarchical clustering begins with singleton groups, repeatedly merges the pair with smallest intergroup dissimilarity, and records the merges in a dendrogram. The height represents the algorithm's merge criterion. Cutting the dendrogram gives partitions at different resolutions, and merges cannot subsequently be reversed. In single-linkage clustering, the criterion is the nearest cross-pair distance; this detects chains and nonconvex groups, but a thin bridge can connect otherwise separated clouds. Complete-linkage clustering uses the farthest cross-pair distance and tends to produce compact groups, at the cost of sensitivity to extreme points. Average-linkage clustering uses the mean cross-pair distance, lying between these two criteria for a given pair of clusters.

For squared Euclidean geometry, Ward clustering merges the pair that least increases the within-group sum of squares. Expanding deviations about the merged mean givesThis favors low within-group dispersion, but interpreting it as a sum-of-squares increase requires Euclidean data. Different software may plot a rescaled height, so the vertical units of a dendrogram from Ward clustering must be stated.

A nonhierarchical alternative is k-means clustering. For a prescribed $K$, minimizeAt fixed assignments, expanding squared distances or differentiating shows that the minimizing $m_k$ is the group mean. At fixed centroids, each point is assigned to a nearest centroid. Alternating these operations does not increase $W_K$; with a consistent tie rule and nonempty groups it reaches a locally stable partition. Initialization matters, so use multiple starts, and give an explicit rule for empty groups. It favors roughly spherical clusters and is sensitive to outliers and scaling. It cannot be expected to reproduce a nonconvex single-linkage partition.

The sketch displays a constructed point configuration and the complete-linkage merges computed from its actual Euclidean distances. A cut between the within-pair and between-pair merge heights yields three groups. Such visual separation is useful evidence, not proof of a uniquely correct number of populations. Select a resolution using subject knowledge, stability under resampling, separation diagnostics or the change of $W_K$ with $K$. Clustering always gives a partition even for unstructured data, and different distance or linkage choices can yield different sensible summaries. Clustering is an exploratory construction whose conclusions depend on the geometry and the chosen resolution.

There is a defect in the stated geometric interpretation of the data. The supplied numbers cannot be Euclidean distances, becauseThey violate the triangle inequality; independently, $d(C,D)=10.3>5.9+1.2$. Nevertheless, both clustering algorithms are defined for this symmetric dissimilarity matrix. The calculations below retain the supplied numbers and use agglomerative clustering of nonmetric dissimilarities, rather than silently inventing Euclidean replacement data.

In single-linkage clustering, the intercluster dissimilarity isThe closest pair is $A,D$, merging at $1.2$. Among the remaining clusters the next closest pair is $B,E$, merging at $2.6$. The three intercluster dissimilarities are nowConsequently $AD$ merges with $BE$ at $4.2$, using the cross-pair $A,B$. The remaining point $C$ joins at $\min (5.9,7.6,10.3,5.4)=5.4$, using $C,E$. The dendrogram thus hasThe close pairs $AD$ and $BE$ are the clearest early groupings. A cut between $2.6$ and $4.2$ produces these two pairs and the singleton $C$; a cut between $4.2$ and $5.4$ produces $ADBE$ and $C$. Single-linkage clustering builds chains through close cross-pairs, so the merge at $4.2$ does not mean every pair in $ADBE$ is that close: $d(D,E)=7.8$. The data alone do not prescribe a unique number of clusters.

For complete-linkage clustering, replace the minimum by the maximum:The first two merges remain $AD$ at $1.2$ and $BE$ at $2.6$. SubsequentlyThus $C$ joins $BE$ at $7.6$. The final maximum between $AD$ and $BCE$ is $d(D,C)=10.3$, givingBoth the topology and the later heights of the dendrogram change: complete-linkage clustering attaches $C$ to $BE$ before joining that group to $AD$, rather than merging the two pairs first. Its control of the largest within-cluster separation makes it less susceptible to the chaining seen with single-linkage clustering.

In agglomerative hierarchical clustering, start with eight singleton groups. Single-linkage clustering uses the smallest distance between cross-pairs; complete-linkage clustering uses the largest. Updating these cluster distances after each merge, one valid order of the tied merges givesThe merges at height $0.6$ may be reordered; they give the same requested three-cluster cuts. For example, the single-link distance from $AC$ to $BD$ is $\min (1.2,1.4,0.6,0.8)=0.6$, while its complete-link distance is their maximum $1.4$. After forming $EG$, its single-link distance to $H$ is $\min (0.9,1.2)=0.9$. The complete-link distance between $EG$ and $FH$ is $\max (1.2,0.9,1.5,1.2)=1.5$. Finally the closest cross-pair between $ABCD$ and $EFGH$ is $CG$ at $1.9$, while the farthest is $BF$ at $3.8$.

At three groups the partitions are thereforeTwo groups, $\{A,B,C,D\}$ and $\{E,F,G,H\}$, are more strongly supported by the merge heights. For single linkage the three-to-two merge is at $1.0$, close to the preceding height $0.9$, whereas the two-to-one merge is delayed until $1.9$. For complete linkage the three-to-two merge at $1.5$ is close to $1.4$, whereas the final merge jumps to $3.8$. Both methods agree on the two-group partition but split its second group differently when forced to return three groups. A three-group choice is possible if required substantively, but is not particularly compelling from these dissimilarities alone.