Dendrograms are tree-like visualizations that show the hierarchical structure of how clusters merge in aglomerative clustering. Linkage methods define how we measure the distance between clusters (not just points), fundamentally controlling the shape and quality of the hierarchy.
Why this matters: Different linkage methods produce drastically different clusterings from the same data. Choosing the right linkage is as important as choosing the clustering algorithm itself.
Intuition Why we need linkage methodsWe know how to measure distance between points (Euclidean, Manhattan, etc.). But in hierarchical clustering, we merge clusters (groups of points).
The problem: A cluster contains multiple points. Which points do we use to compute the distance between two clusters?
The solution: Linkage methods give us a systematic rule. They answer: "Given cluster A with points {a₁, a₂, ...} and cluster B with points {b₁, b₂, ...}, what is d(A, B)?"
Each linkage method defines cluster distance differently. Let's derive the distance formula for each from first principles.
Worked example Single Linkage ExampleSetup: Cluster A = {(0, 0), (1, 1)}, Cluster B = {(5, 5), (6, 6)}
Step 1: Compute all pairwise distances
d((0,0), (5,5)) = √50 ≈ 7.07
d((0,0), (6,6)) = √72 ≈ 8.49
d((1,1), (5,5)) = √32 ≈ 5.66
d((1,1), (6,6)) = √50 ≈ 7.07
Step 2: Take minimum
d single ( A , B ) = min ( 7.07 , 8.49 , 5.66 , 7.07 ) = 5.66 d_{\text{single}}(A, B) = \min(7.07, 8.49, 5.66, 7.07) = 5.66 d single ( A , B ) = min ( 7.07 , 8.49 , 5.66 , 7.07 ) = 5.66
Why this step? Single linkage uses the closest pair , so we pick the smallest distance.
Properties:
**Creates Long, chain-like clusters (sufers from chaining effect )
Sensitive to: Noise and outliers (one outlier can bridge distant clusters)Best for: Non-globular, elongated natural clusters
Worked example Complete Linkage ExampleSame clusters: A = {(0, 0), (1, 1)}, B = {(5, 5), (6, 6)}
Step 1: Same pairwise distances as before
d((0,0), (5,5)) = 7.07
d((0,0), (6,6)) = 8.49
d((1,1), (5,5)) = 5.66
d((1,1), (6,6)) = 7.07
Step 2: Take maximum
d complete ( A , B ) = max ( 7.07 , 8.49 , 5.66 , 7.07 ) = 8.49 d_{\text{complete}}(A, B) = \max(7.07, 8.49, 5.66, 7.07) = 8.49 d complete ( A , B ) = max ( 7.07 , 8.49 , 5.66 , 7.07 ) = 8.49 Why this step? Complete linkage uses the farthest pair to be conservative about merging.
Properties:
Creates: Compact, roughly spherical clustersResistant to: Chaining effectSensitive to: Outliers (one outlier makes the cluster "far" from others)Best for: Well-separated, globular clusters
Worked example Average Linkage ExampleSame clusters: A = {(0, 0), (1, 1)}, B = {(5, 5), (6, 6)}
Step 1: Sum all pairwise distances
Sum = 7.07 + 8.49 + 5.66 + 7.07 = 28.29 \text{Sum} = 7.07 + 8.49 + 5.66 + 7.07 = 28.29 Sum = 7.07 + 8.49 + 5.66 + 7.07 = 28.29
Step 2: Count pairs
∣ A ∣ × ∣ B ∣ = 2 × 2 = 4 |A| \times |B| = 2 \times 2 = 4 ∣ A ∣ × ∣ B ∣ = 2 × 2 = 4
Step 3: Compute average
d average ( A , B ) = 28.29 4 = 7.07 d_{\text{average}}(A, B) = \frac{28.29}{4} = 7.07 d average ( A , B ) = 4 28.29 = 7.07
Why this step? We want the mean distance, so divide the sum by the number of pairs.
Properties:
Creates: Moderate compactness, compromise between single and completeMore robust: Less sensitive to outliers than single/completeComputational cost: O(n²) for each merge (must compute all pairs)Best for: General-purpose clustering when you don't know the cluster shape
Worked example Ward's Linkage ExampleSetup: A = {(0, 0), (2, 0), (1, 1)}, B = {(6, 6), (7, 7)}
Step 1: Compute centroids
μ A = 1 3 [ ( 0 , 0 ) + ( 2 , 0 ) + ( 1 , 1 ) ] = ( 1 , 0.33 ) \mu_A = \frac{1}{3}[(0,0) + (2,0) + (1,1)] = (1, 0.33) μ A = 3 1 [( 0 , 0 ) + ( 2 , 0 ) + ( 1 , 1 )] = ( 1 , 0.33 ) μ B = 1 2 [ ( 6 , 6 ) + ( 7 , 7 ) ] = ( 6.5 , 6.5 ) \mu_B = \frac{1}{2}[(6,6) + (7,7)] = (6.5, 6.5) μ B = 2 1 [( 6 , 6 ) + ( 7 , 7 )] = ( 6.5 , 6.5 )
Step 2: Compute squared distance between centroids
∥ μ A − μ B ∥ 2 = ( 1 − 6.5 ) 2 + ( 0.33 − 6.5 ) 2 = 30.25 + 38.03 = 68.28 \|\mu_A - \mu_B\|^2 = (1 - 6.5)^2 + (0.33 - 6.5)^2 = 30.25 + 38.03 = 68.28 ∥ μ A − μ B ∥ 2 = ( 1 − 6.5 ) 2 + ( 0.33 − 6.5 ) 2 = 30.25 + 38.03 = 68.28
Step 3: Apply size weighting
d Ward ( A , B ) = 3 × 2 3 + 2 × 68.28 = 6 5 × 68.28 = 81.94 d_{\text{Ward}}(A, B) = \frac{3 \times 2}{3 + 2} \times 68.28 = \frac{6}{5} \times 68.28 = 81.94 d Ward ( A , B ) = 3 + 2 3 × 2 × 68.28 = 5 6 × 68.28 = 81.94
Why this step? Ward's linkage penalizes merging clusters that would greatly increase variance. The size weighting ensures we don't unfairly penalize small clusters.
Properties:
Creates: Very compact, spherical clusters (similar to k-means)Minimizes: Within-cluster variance at each stepSensitive to: Cluster size (prefers balanced merges)Best for: When you want tight, homogeneous clusters and know they're roughly spherical
Worked example Dendrogram InterpretationConsider this dendrogram structure:
Height
8 | ┌─────┴─────┐
| │ │
5 | ┌───┴───┐ │
| │ │ │
2 |┌───┴───┐ │ │
| │ │ │ │
0 | A B C D E
Reading top-to-bottom:
Height 2: Points A and B merge (they're close, distance≈ 2)Height 5: Cluster (AB) merges with C (distance ≈ 5)Height 8: Cluster (ABC) merges with D, and separately, this large cluster merges with E
How to cut for k clusters:
Draw a horizontal line at some height h
The number of vertical lines it crosses = number of clusters
Example: Cut at height 6 → crosses 2 lines → 2 clusters: {A,B,C,D} and {E}
Why this works? The height represents dissimilarity. Cutting low (small h) = many small clusters. Cutting high (large h) = few large clusters.
Linkage
Distance Formula
Cluster Shape
Chaining?
Outlier Sensitivity
Best Use Case
Single min distance
Elongated
Yes
High
Non-globular natural shapes
Complete max distance
Compact spheres
No
Moderate
Well-separated globular
Average mean distance
Moderate
No
Low
General purpose
Ward's variance increase
Very compact
No
Moderate
Homogeneous spherical
Common mistake Mistake 1: Thinking linkage doesn't matterWrong idea: "Hierarchical clustering is hierarch—the algorithm is the same regardless of linkage."
Why it feels right: The algorithm (agglomerative merging) is indeed the same procedurally.
The truth: Linkage fundamentally changes which clusters merge at each step . Same data + different linkage = completely different hierarchies.
Example: With single linkage, two clusters with one close pair of outliers will merge early. With complete linkage, those same clusters might never merge because their farthest points are very far apart.
Fix: Always state your linkage method and justify it based on expected cluster shape.
Common mistake Mistake 2: Confusing dendrogram height with actual data scaleWrong idea: "If the dendrogram shows height 5, that means points are 5 units apart in my data."
Why it feels right: The y-axis is labeled with numbers, so it seems like a direct measurement.
The truth: Dendrogram height represents dissimilarity at merge time , which depends on:
The distance metric (Euclidean? Manhattan?)
The linkage method (single? complete?)
The scale of your features
Example: With Ward's linkage, height represents variance increase, not raw distance. With single linkage on normalized data, height is the minimum distance between normalized points.
Fix: Always check your distance metric and linkage. Consider normalizing features before clustering if they have different scales.
Common mistake Mistake 3: Using single linkage for globular clustersWrong idea: "Single linkage is fastest and simplest, so I'll use it for all my data."
Why it feels right: Single linkage is computationally efficient and easy to understand.
The truth: Single linkage creates the chaining effect —long, stringy clusters that connect through just one or two points.
Example: For clearly separated spherical clusters (like k-means would find), single linkage might create one long chain connecting them all instead of separating them.
Fix: Use complete or Ward's linkage for compact clusters, single linkage only for elongated or irregularly shaped natural clusters.
Worked example Complete Worked ExampleData: Points A(0,0), B(1,0), C(5,0), D(6,0)
Goal: Build a dendrogram using complete linkage with Euclidean distance.
Step 1: Compute initial distance matrix
A B C D
A 0 1 5 6
B 0 4 5
C
Intuition Hinglish mein samjhoChalo is concept ko simple tarike se samajhte hain. Hierarchical clustering mein hum points ko groups (clusters) mein merge karte jaate hain. Ab problem yeh hai ki do single points ke beech distance measure karna toh easy hai (Euclidean formula se), par jab clusters mein multiple points ho, tab hum poore cluster ke beech distance kaise nikalein? Yahi cheez linkage methods solve karte hain — yeh ek rule dete hain ki cluster A aur cluster B ke beech distance kaise calculate karna hai. Aur dendrogram ek tree-jaisa diagram hai jo dikhata hai ki kaunse clusters kis distance par merge hue — jitni upar (height) line hogi, utne door ke clusters merge hue.
Ab main types samajh lo. Single linkage mein hum dono clusters ke sabse paas wale points ka distance lete hain (minimum). Isse lambe, chain-jaise clusters bante hain, par yeh outliers se easily fool ho jaata hai — ek galat point do door ke clusters ko jod sakta hai. Iske ulta, complete linkage mein hum sabse door wale points ka distance lete hain (maximum), jisse compact aur round-shape ke clusters bante hain, aur chaining problem nahi aati. Example mein dekha na — same clusters ke liye single linkage ne 5.66 diya (closest pair) jabki complete linkage ne 8.49 (farthest pair). Same data, alag rule, alag answer.
Yeh cheez itni important kyun hai? Kyunki same data par alag-alag linkage method choose karne se bilkul alag-alag clustering result milta hai. Matlab sirf algorithm choose karna kaafi nahi hai — linkage method choose karna bhi utna hi critical decision hai. Agar tumhare paas elongated ya natural non-round clusters hai toh single linkage sahi rahega, par agar clean aur well-separated groups chahiye toh complete linkage better hai. Isliye jab bhi hierarchical clustering use karo, apne data ki shape samajh kar linkage choose karna — warna galat clusters mil jaayenge.