Hierarchical Clustering Dendrogram Agglomerative Methods
# Hierarchical Clustering: Dendrogram & Agglomerative Methods
## Introduction & Motivation
Hierarchical clustering builds tree of nested clusters via bottom-up (agglomerative) or top-down (divisive) approach. Dendrogram visualizes hierarchies; cut at different heights yields different granularities. No need to specify cluster count a priori.
Motivation: Visual dendrogram reveals hierarchical structure. Flexible—various linkage criteria. Complement to partitioning methods (K-means).
Applications: Gene sequencing, taxonomy, document clustering, hierarchical task decomposition.
---
## Core Concepts & Theory
### Linkage Criteria
Single: min distance between clusters.
Complete: max distance.
Average: mean distance.
Ward: minimize within-cluster variance.
---
## Mathematical Formulation
Ward linkage:
$$d(C_i, C_j) = \sqrt{\frac{n_i n_j}{n_i + n_j}} \|m_i - m_j\|^2$$
where n_i, m_i are cluster size and centroid.
---
## Computational Considerations
Training: O(n² log n) time, O(n²) memory.
---
## Practical Implementation Strategies
### Linkage Selection
Ward most common; complete for robustness to outliers.
### Distance Metric
Euclidean standard; Manhattan for axis-aligned clusters.
---
## Benchmark Datasets & Evaluation
Iris: 3 clusters; dendrogram visualization.
Synthetic: Blobs; verify hierarchy.
---
## Key Challenges & Limitations
### Memory
O(n²) distance matrix prohibitive for large n.
### Sensitivity
Linkage choice affects structure.
---
## Summary & Key Takeaways
Hierarchical clustering builds nested cluster structure via agglomerative approach, enabling flexible dendrogram-based analysis.
Principles:
1. Agglomerative bottom-up approach.
2. Linkage criteria define merge distance.
3. Dendrogram visualizes hierarchy.
4. No cluster count specification needed.
5. Computationally expensive for large n.
---
---
## Appendix: Practical Labs
### Lab 1: Agglomerative Clustering
from sklearn.cluster import AgglomerativeClustering
from sklearn.datasets import make_blobs
X, _ = make_blobs(n_samples=50, n_features=2, centers=3, random_state=42)
agg = AgglomerativeClustering(n_clusters=3, linkage='ward')
labels = agg.fit_predict(X)
print(f"Clusters: {len(set(labels))}")
assert len(set(labels)) == 3, "Should have 3 clusters"
print("✓ Agglomerative clustering working")
if __name__ == "__main__":
print("Lab 1: Agglomerative - PASSED")### Lab 2: Linkage Comparison
from sklearn.cluster import AgglomerativeClustering
from sklearn.datasets import make_blobs
X, _ = make_blobs(n_samples=50, n_features=2, centers=3, random_state=42)
for linkage in ['ward', 'complete', 'average', 'single']:
agg = AgglomerativeClustering(n_clusters=3, linkage=linkage)
labels = agg.fit_predict(X)
print(f"{linkage}: {len(set(labels))} clusters")
print("✓ Linkage comparison working")
if __name__ == "__main__":
print("Lab 2: Linkage - PASSED")### Lab 3: Dendrogram
from scipy.cluster.hierarchy import dendrogram, linkage
from sklearn.datasets import make_blobs
X, _ = make_blobs(n_samples=30, n_features=2, centers=2, random_state=42)
Z = linkage(X, method='ward')
print(f"Linkage matrix shape: {Z.shape}")
assert Z.shape[0] == len(X) - 1, "Should have n-1 merges"
print("✓ Dendrogram working")
if __name__ == "__main__":
print("Lab 3: Dendrogram - PASSED")### Lab 4: Distance Metrics
from sklearn.cluster import AgglomerativeClustering
from sklearn.datasets import make_blobs
X, _ = make_blobs(n_samples=50, n_features=2, centers=3, random_state=42)
for metric in ['euclidean', 'manhattan']:
agg = AgglomerativeClustering(n_clusters=3, linkage='average', metric=metric)
labels = agg.fit_predict(X)
print(f"{metric}: {len(set(labels))} clusters")
print("✓ Distance metrics working")
if __name__ == "__main__":
print("Lab 4: Distance Metrics - PASSED")