From Measurements to a Hierarchy
A dendrogram is the final picture of a sequence of pairwise cluster merges. To construct one from raw data, the calculation must be consistent from start to finish: first put the features on the chosen scale, then calculate the dissimilarities, then apply one linkage rule, and finally plot each merge at its dissimilarity height. A mistake in an early distance can change the merge sequence and therefore the entire hierarchy.
This worked tutorial uses sample-standardized numeric features, Euclidean dissimilarity, and complete linkage. These choices define the calculation in the examples; they are not universal requirements for every clustering problem.
For this procedure, the observations must have numeric feature values, and each feature being standardized must have a nonzero sample standard deviation. If a feature is constant, its sample standard deviation is zero and its z-scores are undefined. The examples use complete observations, so no rule for handling missing values is needed.
Worked Example: Standardize Raw Features and Build the Dendrogram
Worked Example: Standardize Raw Features and Build the Dendrogram
A hypothetical analyst records two numeric measurements for four fictional customer profiles. Standardize both features using sample standard deviations, calculate all Euclidean dissimilarities, and construct the complete-linkage dendrogram. Report dissimilarities to four decimal places.
| Profile | Feature 1 | Feature 2 |
|---|---|---|
| A | 3 | -10 |
| B | 0 | 0 |
| C | 9 | 20 |
| D | 6 | 50 |
Method. Calculate the sample mean and sample standard deviation for each feature, convert each row to z-scores, calculate pairwise Euclidean distances, and repeatedly merge the clusters with the smallest complete-linkage distance. This avoids comparing raw measurements in their original units or switching linkage rules midway through the schedule.
Step 1: Standardize Feature 1. Its mean is \((3+0+9+6)/4=18/4=4.5\). The deviations from the mean are \(-1.5,-4.5,4.5,1.5\), so their squared sum is \(2.25+20.25+20.25+2.25=45\). The sample variance is \(45/(4-1)=15\), and the sample standard deviation is \(\sqrt{15}\).
Step 2: Standardize Feature 2. Its mean is \((-10+0+20+50)/4=60/4=15\). The deviations are \(-25,-15,5,35\), whose squared sum is \(625+225+25+1225=2100\). The sample variance is \(2100/3=700\), and the sample standard deviation is \(\sqrt{700}\).
Step 3: Obtain the standardized coordinates. The exact coordinates are shown as expressions in the sample standard deviations; decimal values are shown to six places for checking.
| Profile | Feature 1 z-score | Feature 2 z-score |
|---|---|---|
| A | \(-1.5/\sqrt{15}\approx-0.387298\) | \(-25/\sqrt{700}\approx-0.944911\) |
| B | \(-4.5/\sqrt{15}\approx-1.161895\) | \(-15/\sqrt{700}\approx-0.566947\) |
| C | \(4.5/\sqrt{15}\approx1.161895\) | \(5/\sqrt{700}\approx0.188982\) |
| D | \(1.5/\sqrt{15}\approx0.387298\) | \(35/\sqrt{700}\approx1.322876\) |
Step 4: Calculate the six pairwise dissimilarities. For example, the squared distance between A and B is the sum of the squared standardized differences in the two features:
Thus \(d(A,B)=\sqrt{26/35}\approx0.8619\). The same calculation for every pair gives the following squared distances and distances. Exact squared values are retained until the final rounding.
| Pair | Squared dissimilarity | Euclidean dissimilarity |
|---|---|---|
| A, B | \(26/35\approx0.7429\) | 0.8619 |
| A, C | \(129/35\approx3.6857\) | 1.9198 |
| A, D | \(201/35\approx5.7429\) | 2.3964 |
| B, C | \(209/35\approx5.9714\) | 2.4437 |
| B, D | \(209/35\approx5.9714\) | 2.4437 |
| C, D | \(66/35\approx1.8857\) | 1.3732 |
Step 5: Make the complete-linkage merges. Initially every profile is its own cluster, so complete linkage agrees with the pairwise distances. The smallest distance is \(d(A,B)=0.8619\), and A and B merge first. The distance from cluster \(\{A,B\}\) to C is the larger of \(d(A,C)\) and \(d(B,C)\), which is 2.4437. The distance from \(\{A,B\}\) to D is the larger of \(d(A,D)\) and \(d(B,D)\), also 2.4437. The remaining singleton distance is \(d(C,D)=1.3732\). Therefore C and D merge next.
For the last merge, complete linkage takes the largest of the four cross-cluster distances between \(\{A,B\}\) and \(\{C,D\}\). Those distances are 1.9198, 2.3964, 2.4437, and 1.3732. Their maximum is 2.4437, so the final merge is at height 2.4437.
| Merge | Clusters joined | Height |
|---|---|---|
| 1 | A and B | 0.8619 |
| 2 | C and D | 1.3732 |
| 3 | \(\{A,B\}\) and \(\{C,D\}\) | 2.4437 |
Dendrogram structure. Draw A and B joining at height 0.8619, and C and D joining at height 1.3732. Draw the resulting two branches joining at height 2.4437. The labels are the heights on the dissimilarity axis, not observations or cluster identifiers.
Check. The merge heights increase: \(0.8619<1.3732<2.4437\). At each step the selected pair has the smallest available complete-linkage dissimilarity, and the final height equals the largest cross-cluster distance. Both checks agree with the schedule.
Why the Calculations Work
Sample-standardization subtracts the same feature mean from every observation, so that mean cancels when two standardized values are subtracted. Dividing by the feature's sample standard deviation then rescales the difference. This gives a direct raw-data expression for each term in the squared Euclidean distance:
The expression explains why the worked example can calculate distances from raw differences divided by sample variances, without first rounding the displayed z-scores. Complete linkage follows directly from its definition: for clusters \(G\) and \(H\), it sets \(D(G,H)=\max_{i\in G,\,j\in H}d(i,j)\). After a merge, this means the cluster distance is the greatest cross-cluster pair distance, not the smallest or the average.
Worked Example: Check a Distance and Identify the First Merge
For the four-profile data above, verify \(d(B,D)\), compare it with \(d(C,D)\), and identify the first complete-linkage merge. This calculation guards against rounding a squared distance incorrectly before taking its square root.
Method. Use the raw feature differences divided by the sample variances already calculated. For B and D, the Feature 1 difference is \(0-6=-6\), and the Feature 2 difference is \(0-50=-50\). Therefore,
Taking the square root of the unrounded result gives \(d(B,D)=\sqrt{209/35}\approx2.4436507\), which rounds to 2.4437 to four decimal places. Also, \(d(C,D)^2=66/35\), so \(d(C,D)=\sqrt{66/35}\approx1.3732\). Since \(d(A,B)\approx0.8619\) is smaller than both and than every other pairwise distance in the table, A and B make the first merge.
Common mistake avoided. The calculation \(\sqrt{5.9714}\approx2.4436\) is incorrectly rounded: the unrounded squared distance is \(209/35\), and its square root is approximately 2.4436507. It rounds upward to 2.4437. The equal B-C distance has the same correct rounded value; neither distance is the first merge because A-B is smaller.
Worked Example: Standardize a Second Small Dataset
Three fictional service sites have two recorded numeric features: Site P has values \((0,0)\), Site Q has \((2,0)\), and Site R has \((4,3)\). Use sample-standardization and Euclidean distance, then determine the complete-linkage merge sequence and heights.
Method. For Feature 1, the mean is \((0+2+4)/3=2\). The squared deviations total \(4+0+4=8\), so the sample variance is \(8/2=4\) and the sample standard deviation is 2. Its z-scores for P, Q, and R are \(-1,0,1\).
For Feature 2, the mean is \((0+0+3)/3=1\). The squared deviations total \(1+1+4=6\), so the sample variance is \(6/2=3\) and the sample standard deviation is \(\sqrt{3}\). The z-scores are \(-1/\sqrt{3},-1/\sqrt{3},2/\sqrt{3}\). Thus the standardized coordinates are \(P=(-1,-1/\sqrt{3})\), \(Q=(0,-1/\sqrt{3})\), and \(R=(1,2/\sqrt{3})\).
The pairwise distances are \(d(P,Q)=1\), \(d(Q,R)=\sqrt{1^2+(\sqrt{3})^2}=2\), and \(d(P,R)=\sqrt{2^2+(\sqrt{3})^2}=\sqrt{7}\approx2.6458\). The smallest is P-Q, so they merge at height 1. The complete-linkage distance from \(\{P,Q\}\) to R is \(\max(d(P,R),d(Q,R))=\max(\sqrt{7},2)=\sqrt{7}\). The final merge is therefore at height approximately 2.6458. The check is that the second merge height is at least the first and uses the larger, not the smaller, distance to R.
Reading and Cutting the Resulting Dendrogram
The vertical position of a branch joining two groups records the dissimilarity at which the groups merge. In the first example, the dendrogram first contains the two groups \(\{A,B\}\) and \(\{C,D\}\); these groups become one only at height 2.4437. A horizontal cut at height 2.0 intersects two branches, so it gives two clusters, \(\{A,B\}\) and \(\{C,D\}\). A cut above the final merge gives one cluster; a cut below the first merge gives four single-observation clusters.
Worked Example: Interpret a Cut and a Pair's Merge Height
Using the first example's schedule, an analyst cuts the dendrogram at dissimilarity 2.0. State the resulting partition and the height at which A and C first belong to the same cluster.
Method. Include all merges at or below the cut height. The first merge, A-B at 0.8619, is below 2.0; the second, C-D at 1.3732, is also below 2.0. The final merge at 2.4437 is above the cut and is not included. The partition is therefore \(\{A,B\}\) and \(\{C,D\}\).
A and C first belong to the same cluster when the two pairs merge, at height 2.4437. This is their cophenetic height in this dendrogram. It is not the original pairwise Euclidean distance \(d(A,C)=1.9198\): complete linkage can place two observations in the same cluster only after their clusters merge, and that merge height is determined by the largest cross-cluster distance. The check is that a cut at 2.0 separates A from C, while a cut at any height at least 2.4437 joins them.
Common Errors to Avoid
- Using a population standard deviation without saying so. This tutorial uses the sample standard deviation, with squared deviations divided by \(n-1\). A different standardization convention can produce different numerical distances.
- Rounding intermediate values. Keep exact squared distances or adequate precision through the square root and linkage steps. In the first example, \(\sqrt{209/35}\) rounds to 2.4437, not 2.4436.
- Updating complete linkage with a minimum. The complete-linkage distance is the largest cross-cluster pair distance. Taking the smallest would use a different rule.
- Confusing a pairwise distance with a merge height. After the first merge, a cluster-to-cluster distance is defined by the linkage rule and can differ from an individual pairwise distance.
- Reading labels as heights. The dendrogram's horizontal labels identify observations; the vertical coordinate of a joining branch gives its dissimilarity.
Check Your Understanding
Work each short problem through its stated calculation before checking the answer.
- A feature has observations 2, 4, and 6. Using the sample standard deviation, find the z-score of the observation 6. (Answer: \(1\))
- Two observations have standardized coordinates \((0,1)\) and \((2,4)\). Find their Euclidean dissimilarity, rounded to four decimal places. (Answer: \(\sqrt{13}\approx3.6056\))
- Under complete linkage, the four cross-cluster dissimilarities between clusters \(G\) and \(H\) are 1.2, 2.4, 1.8, and 3.1. What is \(D(G,H)\)? (Answer: \(3.1\))
- A dendrogram has merges A-B at 0.9, C-D at 1.4, and \(\{A,B\}\)-\(\{C,D\}\) at 2.5. What partition results from a horizontal cut at 2.0? (Answer: \(\{A,B\}\) and \(\{C,D\}\))
- Two profiles differ by 12 units on a feature with sample standard deviation 8, and by 1.5 standardized units on a second feature. Find their two-feature Euclidean dissimilarity, rounded to four decimal places. (Answer: \(\sqrt{(12/8)^2+1.5^2}=\sqrt{4.5}\approx2.1213\))