Centroid Linkage: Distance Between Cluster Means

Why Centroids Matter in Hierarchical Clustering

In agglomerative hierarchical clustering, each step combines the pair of current clusters judged closest by a chosen linkage rule. The rule matters because different definitions of “closest” can lead to different merge sequences. Centroid linkage represents each cluster by its mean feature vector and measures the distance between those means. Thus a cluster’s size and the locations of all its observations determine where its centroid lies.

This tutorial uses Euclidean distance for centroid linkage. Each observation is a vector with the same $p$ measured features, and the features must be on scales suitable for Euclidean distance. If features have very different scales, their numerical ranges can dominate the distance; feature scaling should be addressed before interpreting the resulting clustering.

Definition: Let $C$ be a nonempty cluster containing $n_C$ observations $\mathbf{x}_1,\ldots,\mathbf{x}_{n_C}$, each in $p$-dimensional feature space. Its centroid is the vector of feature means: $$ \boldsymbol{\mu}_C=\frac{1}{n_C}\sum_{i\in C}\mathbf{x}_i. $$ For two current clusters $C$ and $D$, their centroid-linkage distance is the Euclidean distance between their centroids: $$ d_{\mathrm{cent}}(C,D)=\left\|\boldsymbol{\mu}_C-\boldsymbol{\mu}_D\right\|_2 =\sqrt{\sum_{j=1}^{p}(\mu_{C,j}-\mu_{D,j})^2}. $$

At each step, calculate this distance for every eligible pair of current clusters and merge a pair with the smallest value. After a merge, the new cluster contains all original observations from both clusters. Its centroid is therefore the mean over all those observations, not generally the unweighted average of the two old centroids. Recalculate distances from the new centroid to every other current cluster before selecting the next merge.

How a Merged Centroid Is Updated

Suppose clusters $C$ and $D$ have sizes $n_C$ and $n_D$, with centroids $\boldsymbol{\mu}_C$ and $\boldsymbol{\mu}_D$. Their union has $n_C+n_D$ observations. Splitting the sum of its observations into the two original clusters gives the size-weighted update:

\boldsymbol{\mu}_{C\cup D} =\frac{n_C\boldsymbol{\mu}_C+n_D\boldsymbol{\mu}_D}{n_C+n_D}.

This formula applies coordinate by coordinate. For example, the first coordinate of the merged centroid is the weighted mean of the first-coordinate means, with weights equal to the numbers of observations. If the two cluster sizes are equal, the update is the ordinary average of their centroids. If their sizes differ, the larger cluster’s centroid receives greater weight.

Why the update formula holds: By the definition of a centroid, $\sum_{i\in C}\mathbf{x}_i=n_C\boldsymbol{\mu}_C$, and likewise $\sum_{i\in D}\mathbf{x}_i=n_D\boldsymbol{\mu}_D$. The sum of observations in the union is the sum of these two sums. Dividing by the union’s size gives $$ \boldsymbol{\mu}_{C\cup D} =\frac{\sum_{i\in C}\mathbf{x}_i+\sum_{i\in D}\mathbf{x}_i}{n_C+n_D} =\frac{n_C\boldsymbol{\mu}_C+n_D\boldsymbol{\mu}_D}{n_C+n_D}. $$

Centroid linkage is not the mean of all pairwise distances between two clusters. It compares only their centroids. That distinction can matter when a cluster is spread out or has an irregular shape: observations far from the center do not enter the distance as separate pairs, though they do contribute to the centroid.

Worked Example: Updating a Centroid After a Merge

A hypothetical insurer has three current clusters of policyholder risk profiles, recorded on two scaled features: claim frequency score and severity score. Cluster $A$ contains $(0,0)$ and $(2,0)$. Cluster $B$ contains $(4,0)$, $(4,2)$, and $(4,4)$. Cluster $C$ contains the single profile $(7,2)$. Using Euclidean centroid linkage, determine the first merge and the distance from the resulting cluster to the remaining cluster.

Method. Find each current centroid, compare all three pairwise centroid distances, merge the closest pair, and then calculate the merged centroid using the cluster sizes.

1. Find the centroids and sizes. Cluster $A$ has size $2$ and centroid $((0+2)/2,(0+0)/2)=(1,0)$. Cluster $B$ has size $3$ and centroid $((4+4+4)/3,(0+2+4)/3)=(4,2)$. Cluster $C$ has size $1$ and centroid $(7,2)$.

2. Compare the current distances.

d_{\mathrm{cent}}(A,B)=\sqrt{(4-1)^2+(2-0)^2}=\sqrt{13}\approx 3.6056,

d_{\mathrm{cent}}(B,C)=\sqrt{(7-4)^2+(2-2)^2}=3,

d_{\mathrm{cent}}(A,C)=\sqrt{(7-1)^2+(2-0)^2}=\sqrt{40}\approx 6.3246.

The smallest distance is $3$, so $B$ and $C$ merge first.

3. Update the centroid. The new cluster $B\cup C$ has size $3+1=4$. Its centroid is $$ \boldsymbol{\mu}_{B\cup C} =\left(\frac{3(4)+1(7)}{4},\frac{3(2)+1(2)}{4}\right) =\left(\frac{19}{4},2\right)=(4.75,2). $$

4. Calculate the next available distance. The only two current clusters are $A$ and $B\cup C$, so $$ d_{\mathrm{cent}}(A,B\cup C) =\sqrt{(4.75-1)^2+(2-0)^2} =\sqrt{18.0625}=4.25. $$ The arithmetic checks: $(3.75)^2+2^2=14.0625+4=18.0625=4.25^2$. The common mistake to avoid is averaging the two old centroids equally; their cluster sizes are $3$ and $1$, not equal.

Cluster Sizes Can Change the Next Merge

The size-weighted update is not a minor bookkeeping detail. A centroid based on many observations can sit much closer to the larger cluster’s old centroid than an unweighted average would. That change can alter which pair is nearest at the following step. The next example isolates this effect in one dimension, where Euclidean distance is absolute difference.

Worked Example: A Size Error Reverses the Next Merge

At a particular stage of a hypothetical risk-profile analysis, four current clusters have one-dimensional feature values $A=\{0,2,4\}$, $B=\{5\}$, $C=\{9\}$, and $D=\{-3\}$. Use centroid linkage to find the first merge and then the next merge. Show what an unweighted centroid update would incorrectly suggest.

Method. Treat each listed set as one current cluster. Compare their centroids, merge the closest pair, and update the union using the number of observations in each cluster.

1. Compute initial centroids and distances. The centroids are $\mu_A=2$, $\mu_B=5$, $\mu_C=9$, and $\mu_D=-3$, with sizes $3,1,1,1$, respectively. The pairwise distances are:

$d(A,B)=|2-5|=3$
$d(A,C)=|2-9|=7$
$d(A,D)=|2-(-3)|=5$
$d(B,C)=|5-9|=4$
$d(B,D)=|5-(-3)|=8$
$d(C,D)=|9-(-3)|=12$

The unique minimum is $d(A,B)=3$, so $A$ and $B$ merge.

2. Update the merged centroid correctly. The union has four observations, whose sum is $0+2+4+5=11$. Thus $$ \mu_{A\cup B}=\frac{3(2)+1(5)}{3+1}=\frac{11}{4}=2.75. $$

3. Compare the distances to the remaining clusters. The current clusters are $A\cup B$, $C$, and $D$. Their distances are $$ d(A\cup B,C)=|2.75-9|=6.25,\qquad d(A\cup B,D)=|2.75-(-3)|=5.75,\qquad d(C,D)=|9-(-3)|=12. $$ The next merge is therefore $(A\cup B)$ with $D$, at distance $5.75$.

Common mistake and correction. An incorrect unweighted update gives $(2+5)/2=3.5$. From that wrong centroid, the distances to $C$ and $D$ would be $5.5$ and $6.5$, incorrectly selecting $C$. The correct weighted centroid $2.75$ makes $D$ the nearer cluster. The check is that the merged cluster contains four observations with mean $11/4$, not two equally weighted cluster representatives.

A Multivariate Merge with Noninteger Centroids

The same procedure applies in any number of dimensions. Calculate means separately for each feature, use the Euclidean formula for the distance, and update each coordinate with the cluster-size weights. Keep exact expressions during the calculation where practical, then round only the reported decimal distances.

Worked Example: Comparing Three Two-Feature Clusters

A hypothetical portfolio segmentation currently has clusters $P$, $Q$, and $R$. Cluster $P$ contains $(1,1)$ and $(3,1)$. Cluster $Q$ contains $(5,1)$, $(5,3)$, and $(7,2)$. Cluster $R$ contains $(4,5)$. Determine which pair merges, update its centroid, and find the distance from the merged cluster to the remaining cluster. Report decimal distances to four places.

Method. Calculate the three centroids and all three distances, merge the pair with the smallest distance, then use a size-weighted update and recalculate the remaining distance.

1. Calculate centroids. Cluster $P$ has size $2$ and centroid $(2,1)$. Cluster $Q$ has size $3$ and centroid $(17/3,2)$, because its coordinate sums are $5+5+7=17$ and $1+3+2=6$. Cluster $R$ has size $1$ and centroid $(4,5)$.

2. Calculate the initial distances.

d(P,Q)=\sqrt{\left(\frac{17}{3}-2\right)^2+(2-1)^2} =\frac{\sqrt{130}}{3}\approx 3.8006,

d(Q,R)=\sqrt{\left(\frac{17}{3}-4\right)^2+(2-5)^2} =\frac{\sqrt{106}}{3}\approx 3.4319,

d(P,R)=\sqrt{(4-2)^2+(5-1)^2} =\sqrt{20}\approx 4.4721.

The smallest is $d(Q,R)$, so $Q$ and $R$ merge.

3. Update and verify the merged centroid. The union has size $3+1=4$: $$ \boldsymbol{\mu}_{Q\cup R} =\left(\frac{3(17/3)+1(4)}{4},\frac{3(2)+1(5)}{4}\right) =\left(\frac{21}{4},\frac{11}{4}\right)=(5.25,2.75). $$ This also matches the coordinate sums of the four observations: $17+4=21$ and $6+5=11$.

4. Find the updated distance. The only remaining pair is $P$ and $Q\cup R$: $$ d(P,Q\cup R) =\sqrt{\left(\frac{21}{4}-2\right)^2+\left(\frac{11}{4}-1\right)^2} =\frac{\sqrt{218}}{4}\approx 3.6912. $$ The squared coordinate differences are $169/16$ and $49/16$, totaling $218/16$; the reported distance is rounded to four decimal places.

Check. The initial minimum, $3.4319$, is less than the other initial distances, $3.8006$ and $4.4721$. The merged centroid is pulled toward $Q$, which has three observations, rather than giving the singleton $R$ equal influence.

What to Keep Straight

Centroid linkage is a greedy procedure: at each stage it chooses the currently closest pair under the centroid-distance rule. It does not search all possible sequences of future merges. A correct calculation therefore has two distinct parts: choosing the current minimum and updating the cluster representation before the next comparison.

For a reliable exam calculation, use the following sequence:

Record cluster sizes and centroids.
Each size counts original observations represented by the current cluster. Each centroid is the mean of those observations feature by feature.

Compare every current pair.
Use the specified feature distance consistently. Under Euclidean centroid linkage, take the square root of the sum of squared coordinate differences between centroids.

Merge the nearest pair.
State the distance and identify the two clusters. If a tie occurs, more than one immediate merge may be possible unless a tie-breaking rule is specified.

Update and recalculate.
Use the size-weighted centroid formula, then calculate distances from that new centroid to all other current clusters. Do not reuse the old distances.

The most common errors are using an unweighted mean of centroids when cluster sizes differ, forgetting that a merged cluster represents all its original observations, and continuing to compare distances from before the merge. Another trap is to substitute the mean of pairwise observation distances for the centroid distance. Those are different linkage definitions and need not select the same pair.

Key takeaway: Centroid linkage compares cluster means, and every merged mean must retain the original observations’ relative weights. A correct update can change the next nearest pair, so recalculate distances after each merge.

Check Your Understanding

For each problem, use Euclidean centroid linkage and show the centroid update before deciding any subsequent merge.

Current clusters are $U=\{(2,0),(4,2)\}$, $V=\{(6,1)\}$, and $W=\{(0,1),(0,3)\}$. Identify the first merge and find the distance from the merged cluster to the remaining cluster. (Answer: $U$ and $V$ merge at distance $3$; the updated centroid is $(4,1)$, and its distance to $W$, centered at $(0,2)$, is $\sqrt{17}\approx4.1231$.)
In one dimension, $A=\{1,3\}$ and $B=\{5,7,9\}$ merge. Find the centroid of the union and state the unweighted average of the old centroids that would be incorrect. (Answer: the union centroid is $5$; the incorrect unweighted average is $4.5$.)
Three singleton clusters have coordinates $A=(0,0)$, $B=(3,0)$, and $C=(0,4)$. Which pair merges first, and what is the distance from its updated centroid to the remaining cluster? (Answer: $A$ and $B$ merge at distance $3$; their centroid is $(1.5,0)$, at distance $\sqrt{18.25}=\sqrt{73}/2\approx4.2720$ from $C$.)
Current one-dimensional clusters are $L=\{-4,-2,0,2\}$, $M=\{3\}$, and $N=\{8\}$. Find the first merge and the distance from the resulting cluster to the remaining cluster after updating. (Answer: $L$ and $M$ merge first at distance $4$; the union centroid is $(-4-2+0+2+3)/5=-0.2$, and its distance to $N$ is $8.2$.)
Clusters $E=\{(0,0),(2,0),(4,0)\}$ and $F=\{(8,0)\}$ are merged. Calculate the correct new centroid, then calculate the distance to a third cluster $G=\{(0,6)\}$. (Answer: the new centroid is $(14/4,0)=(3.5,0)$; its distance to $G$'s centroid $(0,6)$ is $\sqrt{48.25}\approx6.9462$.)

What You'll Learn