Hierarchical clustering (agglomerative - divisive)

2.5.4 · AI-ML › Unsupervised Learning

Hierarchical Clustering Kya Hai?

Ye Kyun Zaroori Hai

Woh problem jo K-Means poorly solve karta hai: Tumhare paas customer data hai lekin tum nahi jaante ki 3, 5, ya 10 groups mein segment karna chahiye. K-Means tumhe K guess karne par majboor karta hai, phir galat hone par dobara start karna padta hai.

Hierarchical solution: Poora tree EK BAAR banao, phir natural number of clusters choose karne ke liye use examine karo. Tree tumhe dikhata hai ki BDE separations KAHAN hote hain.

Do Approaches

1. Agglomerative Clustering (Bottom-Up)

Complexity ki Derivation:

$n$ points, iteration $k$ mein $(n - k + 1)$ clusters hain
Saare pairwise distances compute karna: $(2 n - k + 1) = O ((n - k)^{2})$ comparisons
Total: $\sum_{k = 1}^{n - 1} (n - k)^{2} = O (n^{3})$ naive implementation ke liye
Priority queue (heap) ke saath: $O (n^{2} lo g n)$

2. Divisive Clustering (Top-Down)

Linkage Criteria (Agglomerative ka Dil)

Linkage criterion $L (C_{p}, C_{q})$ define karta hai "clusters ke beech distance". Ye choice drastically cluster shapes change kar deta hai.

Formula Chaar Main Linkage Methods

Given clusters $C_{p} = {x_{i}}$ aur $C_{q} = {x_{j}}$ :

Single Linkage (MIN, nearest neighbor): $L_{s in g l e} (C_{p}, C_{q}) = min_{x_{i} \in C_{p}, x_{j} \in C_{q}} d (x_{i}, x_{j})$ → Distance = clusters ke beech closest pair of points
Complete Linkage (MAX, farthest neighbor): $L_{co m pl e t e} (C_{p}, C_{q}) = max_{x_{i} \in C_{p}, x_{j} \in C_{q}} d (x_{i}, x_{j})$ → Distance = clusters ke beech farthest pair of points
Average Linkage (UPGMA): $L_{a v g} (C_{p}, C_{q}) = \frac{1}{∣ C _{p} ∣∣ C _{q} ∣} \sum_{x_{i} \in C_{p}} \sum_{x_{j} \in C_{q}} d (x_{i}, x_{j})$ → Distance = saare pairwise distances ka average
Ward's Method (minimum variance): $L_{w a r d} (C_{p}, C_{q}) = \frac{∣ C _{p} ∣∣ C _{q} ∣}{∣ C _{p} ∣ + ∣ C _{q} ∣} ∣ μ_{p} - μ_{q} ∣ ∣^{2}$ jahan $μ_{p} = \frac{1}{∣ C _{p} ∣} \sum_{x \in C_{p}} x$ cluster centroid hai → Woh clusters merge karo jo within-cluster variance increase minimize karein

Ward's Formula ki Derivation:

Merged cluster $C_{p} \cup C_{q}$ ke liye within-cluster sum of squares: $S S_{m er g e d} = \sum_{x \in C_{p} \cup C_{q}} ∣∣ x - μ_{m er g e d} ∣ ∣^{2}$

jahan $μ_{m er g e d} = \frac{∣ C _{p} ∣ μ _{p} + ∣ C _{q} ∣ μ _{q}}{∣ C _{p} ∣ + ∣ C _{q} ∣}$

Expanding: $S S_{m er g e d} = \sum_{x \in C_{p}} ∣∣ x - μ_{m er g e d} ∣ ∣^{2} + \sum_{x \in C_{q}} ∣∣ x - μ_{m er g e d} ∣ ∣^{2}$

Parallel axis theorem use karke: $\sum ∣∣ x - μ_{n e w} ∣ ∣^{2} = \sum ∣∣ x - μ_{o l d} ∣ ∣^{2} + n ∣ μ_{o l d} - μ_{n e w} ∣ ∣^{2}$

Algebra ke baad: $Δ S S =_{m er g e d} - (S S_{p} + S S_{q}) = \frac{∣ C _{p} ∣∣ C _{q} ∣}{∣ C _{p} ∣ + ∣ C _{q} ∣} ∣ μ_{p} - μ_{q} ∣ ∣^{2}$

Ye kyun matter karta hai: Ward's merging se total within-cluster variance mein INCREASE minimize karta hai, compact, roughly equal-sized clusters produce karta hai.

Dendrogram: Tree Padhna

Number of clusters kaise choose karein:

Bade vertical gaps dekho (merge distance mein bada increase)
Bade jump se thoda pehle cut karo
Jitni vertical lines tum cut karte ho = utne clusters

Worked example Dendrogram Cutting

Merge heights: [1.0, 1.1, 1.2, 5.8, 6.0]

    |          6.0  ---- (final merge)
    |          5.8  ---- (big jump from 1.2!)
    |          1.2  --
    |          1.1  --
    |          1.0  --
  A B C D E F

Analysis: Heights 1.0-1.2 similar hain (internal cluster merging), phir 5.8 par JUMP (different clusters merging).

Decision: Height 4.0 par cut karo (1.2 aur 5.8 ke beech) → 2 clusters

Ye kyun kaam karta hai: Chhote heights = similar points. Bada jump = ab tum dissimilar groups merge kar rahe ho.

Implementation Details

Distance Metric (usually Euclidean): $d (x_{i}, x_{j}) = ∣∣ x_{i} - x_{j} ∣ ∣_{2} = \sum_{k = 1}^{d} (x_{ik} - x_{j k})^{2}$

High-dimensional data ke liye, consider karo:

Manhattan: $d = \sum ∣ x_{ik} - x_{j k} ∣$ (outliers ke liye robust)
Cosine: $d = 1 - \frac{x _{i} \cdot x _{j}}{∣∣ x _{i} ∣∣∣∣ x _{j} ∣}$ (angle-based, text ke liye achha)

Update Formula (Lance-Williams): Clusters $C_{i}$ aur $C_{j}$ ko $C_{k}$ mein merge karne ke baad, baaki cluster $C_{m}$ ke distances update karo:

$d (C_{k}, C_{m}) = α_{i} d (C_{i}, C_{m}) + α_{j} d (C_{j}, C_{m}) + β d (C_{i}, C_{j}) + γ ∣ d (C_{i}, C_{m}) - d (C_{j}, C_{m}) ∣$

Different linkages ke liye parameters:

Single: $α_{i} = α_{j} = 0.5, β = 0, γ = - .5$ (do distances ka min)
Complete: $α_{i} = α_{j} = 0.5, β = 0, γ = 0.5$ (do distances ka max)
Average: $α_{i} = \frac{∣ C _{i} ∣}{∣ C _{i} ∣ + ∣ C _{j} ∣}, α_{j} = \frac{∣ C _{j} ∣}{∣ C _{i} ∣ + ∣ C _{j} ∣}, β = γ = 0$

Common mistake Common Mistake: "Hierarchical clustering globally optimal clusters dhundta hai"

Ye sahi kyun lagta hai: Hum ek complete tree bana rahe hain, saare merge possibilities consider kar rahe hain, toh ye exhaustive lagta hai.

Ye galat kyun hai: Har step par, hum ek greedy local decision lete hain (closest pair merge karo). Ek baar merge hone ke baad, clusters kabhi split nahi hote. Agar ek early merge suboptimal tha, hum use undo nahi kar sakte.

Example: Points do close pairs {A,B} aur {C,D} banate hain, lekin A thoda B se zyada C ke paas hai.

Single linkage A-C pehle merge kar sakta hai (galat!)
Ab B ko (AC) ke saath merge karna padega, aur D ko (ABC) ke saath
Humne permanently {A,B}, {C,D} structure kho diya

Fix:

Hierarchical distance metric aur linkage ke hisaab se deterministic hai, lekin globally optimal nahi
Multiple linkage criteria try karo aur dendrograms compare karo
True global optimization ke liye, spectral clustering jaise methods use karo (lekin interpretability kho jaogi)

Common mistake Common Mistake: "Sabhi cases ke liye single linkage use karo — ye sabse simple hai"

Ye sahi kyun lagta hai: Single linkage ka "connect nearest neighbors" logic intuitive hai aur computationally update karna simpler hai.

Ye galat kyun hai: Single linkage chaining se suffer karta hai: outliers ya noise distinct clusters ko bridge kar sakte hain, compact groups ki jagah lambe chains create karte hain.

Kab fail karta hai: Noise wala data, elongated clusters jo touch kar rahe hon, ya unequal densities.

Example: Do circular clusters jisme unke beech ek outlier ho. Single linkage:

Pehle do clusters sahi se banata hai
Eventually unhe outlier ke through connect karta hai
Final result: do circles ki jagah ek elongated chain

Fix:

Complete linkage use karo compact, well-separated clusters ke liye (sabse robust)
Ward's method use karo jab clusters ka similar size aur low variance hona chahiye
Average linkage use karo balanced compromise ke liye
Single linkage use karne par outliers hatane ke liye preprocess karo

Common mistake Common Mistake: "Dendrogram ko fixed height threshold par cut karo"

Ye sahi kyun lagta hai: Objective lagta hai — "distance 5 se upar ke saare merges separate clusters hain."

Ye galat kyun hai: Merge heights tumhare distance metric scale aur data normalization par depend karte hain. Height 5 ek dataset mein huge ho sakta hai, doosre mein tiny.

Better approach: Absolute values nahi, merge heights mein relative jumps dekho.

Dendrograms ke liye elbow method:

Merge heights vs merge step plot karo
Woh "elbow" dhundo jahan slope drastically change ho
Elbow se thoda pehle cut karo Example: Merge heights [0.5, 0.6, 0.7, 3.2, 3.5]

Galat: "Height 2.0 par cut karo" (arbitrary)
Sahi: "0.7→3.2 jump se pehle cut karo" (4-5x increase signal karta hai ki different clusters merge ho rahe hain)

Advantages & Disadvantages

Advantages:

K pehle se specify karne ki zaroorat nahi — ek tree se multiple granularities explore karo
Interpretable output — dendrogram cluster relationships aur hierarchy dikhata hai
Deterministic — same data hamesha same tree deta hai (K-Means ke random init ke unlike)
Kisi bhi distance metric ke saath kaam karta hai — Euclidean space tak limited nahi

Disadvantages:

Computational cost: $O (n^{2} lo g n)$ time, $O (n^{2})$ space (distance matrix)
- K-Means $O (nk d \cdot i)$ hai jahan $i$ = iterations, usually bahut faster
Greedy aur irreversible — early merge mistakes ko undo nahi kiya ja sakta
Outliers ke liye sensitive (especially single linkage)
Scalable nahi — approximations ke bina $n > 10, 000$ points ke liye impractical

Hierarchical kab use karein:

Small-to-medium datasets ( $n < 10, 000$ )
Sirf flat partition nahi, cluster hierarchy chahiye
Natural K determine karne ke liye exploratory analysis
Biological taxonomy, document hierarchies (true hierarchical structure)

Kab avoid karein:

Large datasets (K-Means, DBSCAN, ya mini-batch variants use karo)
Complex shapes wale clusters (DBSCAN use karo)
Naya data aane par clusters update karne ki zaroorat ho (hierarchical mein full rebuild chahiye)

Worked example Full Walkthrough: 1D Data

Data: $x = [2, 4, 10, 12, 18]$

Complete linkage use karke: Iteration 1: Saare points separate clusters hain Distance matrix:

    2   4   10  12  18
2    0   2   8   10  16
4        0   6   8   14
10           0   2   8
12               0   6
18                   0

Minimum distance: $d (2, 4) = 2$ → {2} aur {4} ko {2,4} mein merge karo Iteration 2: Clusters {2,4}, {10}, {12}, {18} Distances update karo (complete linkage = max):

$d ({2, 4}, {10}) = max (d (2, 10), d (4, 10)) = max (8, 6) = 8$
$d ({2, 4}, {12}) = max (10, 8) = 10$
$d ({2, 4}, {18}) = max (16, 14) = 16$
$d ({10}, {12}) = 2$ (unchanged)
$d ({10}, {18}) = 8$ (unchanged)
$d ({12}, {18}) = 6$ (unchanged)

Minimum: $d (10, 12) = 2$ → {10} aur {12} ko {10,12} mein merge karo

Iteration 3: Clusters {2,4}, {10,12}, {18}

$d ({2, 4}, {10, 12}) = max (8, 10) = 10$
$d ({2, 4}, {18}) = 16$
$d ({10, 12}, {18}) = max (8, 6) = 8$ Minimum: $d ({10, 12}, {18}) = 8$ → {10,12,18} mein merge karo

Iteration 4: Clusters {2,4}, {10,12,18}

$d ({2, 4}, {10, 12, 18}) = max (8, 10, 16) = 16$ Final merge: Sab kuch {2,4,10,12,18} mein height 16 par merge karo

Dendrogram interpretation:

Merge heights: [2, 2, 8, 16]
8→16 ka bada jump suggest karta hai height 12 par cut karo
Result: 2 clusters {2,4} aur {10,12,18} ✓

Recall 12-saal ke bachche ko explain karo

Socho tumhare paas zameen par bahut saare LEGO bricks bikre hue hain, alag-alag colors aur sizes ke. Hierarchical clustering unhe groups mein organize karne jaisa hai.

Agglomerative (bottom-up): Tum har brick uthana shuru karte ho. Phir tum do MOST similar bricks dhundhte ho (shayad dono red, ya dono 2x4 size) aur unhe saath rakh dete ho. Phir tum ye karte rehte ho: do groups dhundho jo sabse zyada similar hain aur combine karo. Shayad tum do red piles combine karo, ya ek red pile ko ek pink pile ke saath (woh kinda similar hain!). Eventually, tumhare saare bricks ek giant pile mein aa jaate hain.

Cool part? Tumne poora time video liya. Ab tum kisi bhi point par rewind aur stop kar sakte ho alag groupings dekhne ke liye. Shayad tum 3 piles chahte ho (primary colors), ya 10 piles (har shade), ya 100 piles (almost har brick alag). Jab tak video na dekho choose nahi karna padta!

Divisive (top-down): Ye ulta karna jaisa hai. Ek pile mein saare bricks se shuru karo, phir use do groups mein split karo (shayad "red-ish" vs "blue-ish"). Phir un dono groups mein se har ek ko dobara split karo, aur baar baar, jab tak har brick akela na ho jaye.

"Dendrogram" tumhare LEGO bricks ka family tree jaisa hai, jo dikhata hai ki kaun se bricks "related" (similar) hain aur kaun se "distant cousins" hain (bahut different). Har branch ki height dikhati hai ki jab tum unhe combine kar rahe the tab groups KITNE different the.

Connections

K-Means Clustering — flat clustering jo K upfront maangta hai; hierarchical K choose karne mein help karta hai
DBSCAN — density-based alternative; non-convex clusters ke liye better, hierarchical interpretability ke liye better
Distance Metrics — Euclidean, Manhattan, Cosine ka choice drastically clustering affect karta hai
Dendrogram Visualization — cluster hierarchy ki tree representation
Elbow Method — optimal K determine karne ke liye use hota hai; dendrogram merge heights par apply hota hai
Single-Link vs Complete-Link — chaining vs outliers ke sensitivity ke beech trade-off
Time Complexity Analysis — $O (n^{3})$ naive, $O (n^{2} lo g n)$ optimized vs K-Means $O (nk d)$
Greedy Algorithms — hierarchical greedy merging use karta hai, globally optimal nahi
Within-Cluster Sum of Squares — Ward's method WCSS increase minimize karta hai

#flashcards/ai-ml

Hierarchical clustering ke do main types kya hain? :: Agglomerative (bottom-up merging) aur Divisive (top-down splitting)

Hierarchical clustering ka output kya hota hai?

Ek dendrogram (tree structure) jo saare levels of granularity par cluster relationships dikhata hai, sirf ek single partition nahi

Priority queue ke saath agglomerative clustering ki time complexity kya hai?

O (n^{2} lo g n)

time aur

O (n^{2})

space distance matrix ke liye

Single linkage criterion kya hai?

Clusters ke beech distance = do clusters ke kisi bhi do points ke beech minimum distance:

min_{x_{i} \in C_{p}, x_{j} \in C_{q}} d (x_{i}, x_{j})

Complete linkage criterion kya hai?

Clusters ke beech distance = do clusters ke kisi bhi do points ke beech maximum distance:

max_{x_{i} \in C_{p}, x_{j} \in C_{q}} d (x_{i}, x_{j})

Ward's linkage criterion kya hai?

Woh clusters merge karo jo total within-cluster variance mein increase minimize karein:

\frac{∣ C _{p} ∣∣ C _{q} ∣}{∣ C _{p} ∣ + ∣ C _{q} ∣} ∣ μ_{p} - μ_{q} ∣ ∣^{2}

Single linkage mein chaining effect kya hota hai?

Single linkage clusters ko outlier bridges ya noise points ke through connect karta hai, compact clusters ki jagah elongated chains banata hai

Dendrogram se clusters ki number kaise choose karein?

Bade vertical gaps (merge height mein bade jumps) dekho aur dendrogram ko horizontally bade jump se thoda pehle cut karo

K-Means ke muqable hierarchical clustering ka main advantage kya hai?

K upfront specify karne ki zaroorat nahi — tumhe saari granularities par cluster structure milta hai aur tum dendrogram examine karke K choose kar sakte ho

Hierarchical clustering globally optimal kyun nahi hai?

Ye har merge step par greedy local decisions use karta hai. Ek baar do clusters merge ho jaayein toh kabhi split nahi hote, isliye early mistakes propagate ho jaati hain

Complete linkage single linkage ke upar kab use karein?

Complete linkage tab use karo jab compact, well-separated clusters chahiye aur data mein noise ya outliers hon. Single linkage in cases mein chaining se suffer karta hai

Large datasets ke liye hierarchical clustering ka main disadvantage kya hai?

Distance matrix ke liye

O (n^{2})

space aur

O (n^{2} lo g n)

time use karne ki wajah se

n > 10, 000

points ke liye impractical ho jaata hai

Dendrogram mein merge ki height kya represent karti hai?

Us step par merge ho rahe do clusters ke beech distance ya dissimilarity

Average linkage single aur complete linkage se kaise different hai?

Average linkage clusters ke beech saare pairwise distances ka mean use karta hai, single (minimum) aur complete (maximum) ke beech ek compromise provide karta hai

Ward's method balanced clusters banane ke liye kyun achha hai?

Ye within-cluster variance increase minimize karta hai, jo naturally similar size aur low internal variance wale compact clusters produce karta hai