2.5.5
Dendrograms tree-like visualizations hain jo dikhate hain ki agglomerative clustering mein clusters kis tarah se hierarchical structure mein merge hote hain. Linkage methods define karte hain ki hum clusters ke beech distance kaise measure karte hain (sirf points ke beech nahi), aur yahi fundamentally hierarchy ki shape aur quality ko control karta hai.
Yeh kyun zaroori hai: Alag-alag linkage methods ek hi data se bilkul alag clustering produce karte hain. Sahi linkage choose karna utna hi important hai jitna clustering algorithm choose karna.
Intuition Hume linkage methods ki zaroorat kyun haiHum jaante hain ki points ke beech distance kaise measure karte hain (Euclidean, Manhattan, etc.). Lekin hierarchical clustering mein hum clusters (points ke groups) ko merge karte hain.
Problem: Ek cluster mein multiple points hote hain. Do clusters ke beech distance compute karne ke liye hum kaunse points use karein?
Solution: Linkage methods hume ek systematic rule dete hain. Yeh answer karte hain: "Diya gaya cluster A jisme points {a₁, a₂, ...} hain aur cluster B jisme points {b₁, b₂, ...} hain, toh d(A, B) kya hai?"
Har linkage method cluster distance ko alag tarike se define karta hai. Chaliye har ek ke liye first principles se distance formula derive karte hain.
Worked example Single Linkage ExampleSetup: Cluster A = {(0, 0), (1, 1)}, Cluster B = {(5, 5), (6, 6)}
Step 1: Saare pairwise distances compute karo
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: Minimum lo
d single ( A , B ) = min ( 7.07 , 8.49 , 5.66 , 7.07 ) = 5.66
Yeh step kyun? Single linkage closest pair use karta hai, isliye hum sabse chhoti distance choose karte hain.
Properties:
Banata hai: Lambe, chain-jaise clusters (chaining effect se pareshan)Sensitive hai: Noise aur outliers ke liye (ek outlier door ke clusters ko bridge kar sakta hai)Best hai: Non-globular, elongated natural clusters ke liye
Worked example Complete Linkage ExampleSame clusters: A = {(0, 0), (1, 1)}, B = {(5, 5), (6, 6)}
Step 1: Pehle jaise hi pairwise distances
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: Maximum lo
d complete ( A , B ) = max ( 7.07 , 8.49 , 5.66 , 7.07 ) = 8.49 Yeh step kyun? Complete linkage merging ke baare mein conservative rehne ke liye farthest pair use karta hai.
Properties:
Banata hai: Compact, roughly spherical clustersResistant hai: Chaining effect seSensitive hai: Outliers ke liye (ek outlier cluster ko doosron se "door" bana deta hai)Best hai: Well-separated, globular clusters ke liye
Worked example Average Linkage ExampleSame clusters: A = {(0, 0), (1, 1)}, B = {(5, 5), (6, 6)}
Step 1: Saare pairwise distances ka sum karo
Sum = 7.07 + 8.49 + 5.66 + 7.07 = 28.29
Step 2: Pairs count karo
∣ A ∣ × ∣ B ∣ = 2 × 2 = 4
Step 3: Average compute karo
d average ( A , B ) = 4 28.29 = 7.07
Yeh step kyun? Hume mean distance chahiye, isliye sum ko pairs ki sankhya se divide karte hain.
Properties:
Banata hai: Moderate compactness, single aur complete ke beech compromiseZyada robust: Single/complete se outliers ke liye kam sensitiveComputational cost: Har merge ke liye O(n²) (saare pairs compute karne padte hain)Best hai: General-purpose clustering ke liye jab cluster shape pata na ho
Worked example Ward's Linkage ExampleSetup: A = {(0, 0), (2, 0), (1, 1)}, B = {(6, 6), (7, 7)}
Step 1: Centroids compute karo
μ A = 3 1 [( 0 , 0 ) + ( 2 , 0 ) + ( 1 , 1 )] = ( 1 , 0.33 ) μ B = 2 1 [( 6 , 6 ) + ( 7 , 7 )] = ( 6.5 , 6.5 )
Step 2: Centroids ke beech squared distance compute karo
∥ μ A − μ B ∥ 2 = ( 1 − 6.5 ) 2 + ( 0.33 − 6.5 ) 2 = 30.25 + 38.03 = 68.28
Step 3: Size weighting apply karo
d Ward ( A , B ) = 3 + 2 3 × 2 × 68.28 = 5 6 × 68.28 = 81.94
Yeh step kyun? Ward's linkage un clusters ko merge karne par penalty deta hai jo variance bahut zyada badhayenge. Size weighting ensure karta hai ki chhote clusters ke saath unfair na ho.
Properties:
Banata hai: Bahut compact, spherical clusters (k-means jaisa)Minimize karta hai: Har step par within-cluster varianceSensitive hai: Cluster size ke liye (balanced merges prefer karta hai)Best hai: Jab aapko tight, homogeneous clusters chahiye aur pata ho ki woh roughly spherical hain
Worked example Dendrogram InterpretationIs dendrogram structure ko consider karo:
Height
8 | ┌─────┴─────┐
| │ │
5 | ┌───┴───┐ │
| │ │ │
2 |┌───┴───┐ │ │
| │ │ │ │
0 | A B C D E
Upar se neeche padhna:
Height 2: Points A aur B merge hote hain (yeh close hain, distance ≈ 2)Height 5: Cluster (AB) aur C merge hote hain (distance ≈ 5)Height 8: Cluster (ABC) aur D merge hote hain, aur alag se, yeh bada cluster E ke saath merge hota hai
k clusters ke liye kaise cut karein:
Kisi height h par ek horizontal line kheecho
Jitni vertical lines cross hoti hain = utne clusters
Example: Height 6 par cut karo → 2 lines cross hoti hain → 2 clusters: {A,B,C,D} aur {E}
Yeh kyun kaam karta hai? Height dissimilarity represent karta hai. Neeche cut karna (chhota h) = bahut saare chhote clusters. Upar cut karna (bada h) = kuch bade clusters.
Linkage
Distance Formula
Cluster Shape
Chaining?
Outlier Sensitivity
Best Use Case
Single min distance
Elongated
Haan
High
Non-globular natural shapes
Complete max distance
Compact spheres
Nahi
Moderate
Well-separated globular
Average mean distance
Moderate
Nahi
Low
General purpose
Ward's variance increase
Bahut compact
Nahi
Moderate
Homogeneous spherical
Common mistake Mistake 1: Yeh sochna ki linkage matter nahi kartaGalat idea: "Hierarchical clustering hierarchical hai—algorithm same rehta hai chahe linkage kuch bhi ho."
Kyun sahi lagta hai: Algorithm (agglomerative merging) procedurally actually same hota hai.
Sachai: Linkage fundamentally change karta hai ki har step par kaunse clusters merge hote hain . Same data + alag linkage = bilkul alag hierarchies.
Example: Single linkage ke saath, do clusters jinka ek close pair of outliers ho, jaldi merge ho jayenge. Complete linkage ke saath, wahi clusters kabhi merge nahi ho sakte kyunki unke farthest points bahut door hain.
Fix: Hamesha apna linkage method batao aur expected cluster shape ke basis par justify karo.
Common mistake Mistake 2: Dendrogram height ko actual data scale samajhnaGalat idea: "Agar dendrogram height 5 dikhata hai, toh matlab points mere data mein 5 units door hain."
Kyun sahi lagta hai: Y-axis par numbers likhe hote hain, isliye yeh direct measurement lagta hai.
Sachai: Dendrogram height merge ke waqt dissimilarity represent karta hai, jo depend karta hai:
Distance metric par (Euclidean? Manhattan?)
Linkage method par (single? complete?)
Aapke features ke scale par
Example: Ward's linkage ke saath, height variance increase represent karta hai, raw distance nahi. Normalized data par single linkage ke saath, height normalized points ke beech minimum distance hai.
Fix: Hamesha apna distance metric aur linkage check karo. Agar features ke alag-alag scales hain toh clustering se pehle features normalize karne par consider karo.
Common mistake Mistake 3: Globular clusters ke liye single linkage use karnaGalat idea: "Single linkage sabse fast aur simple hai, isliye main ise apne saare data par use karunga."
Kyun sahi lagta hai: Single linkage computationally efficient aur samajhne mein aasan hai.
Sachai: Single linkage chaining effect create karta hai—lambe, stringy clusters jo sirf ek ya do points ke through connect hote hain.
Example: Clearly separated spherical clusters ke liye (jaise k-means dhundta hai), single linkage unhe alag karne ki jagah ek lamba chain bana sakta hai jo sabko connect kar de.
Fix: Compact clusters ke liye complete ya Ward's linkage use karo, single linkage sirf elongated ya irregularly shaped natural clusters ke liye use karo.
Worked example Complete Worked ExampleData: Points A(0,0), B(1,0), C(5,0), D(6,0)
Goal: Euclidean distance ke saath complete linkage use karke dendrogram banana.
Step 1: Initial distance matrix compute karo
A B C D
A 0 1 5 6
B 0 4 5
C