Hierarchical Clustering Agglomerative Dendrogram
# Hierarchical Clustering: Agglomerative & Dendrogram
## Introduction & Motivation
Hierarchical Clustering: build tree of clusters. Agglomerative: bottom-up merging. Dendrogram visualizes structure. Applications: taxonomy creation, hierarchical segmentation, document clustering.
Motivation: Reveals cluster hierarchy; interpretable.
Applications: Taxonomy, dendrogram visualization.
---
## Core Concepts & Theory
### Linkage Criteria
Define inter-cluster distance.
### Dendrogram
Tree visualization of merging process.
### Cutoff Threshold
Determines final cluster count.
---
## Mathematical Formulation
Single Linkage (Min):
$$d(C_i, C_j) = \min_{x \in C_i, y \in C_j} d(x, y)$$
Complete Linkage (Max):
$$d(C_i, C_j) = \max_{x \in C_i, y \in C_j} d(x, y)$$
Average Linkage:
$$d(C_i, C_j) = \frac{1}{|C_i||C_j|} \sum_{x \in C_i, y \in C_j} d(x, y)$$
---
## Advanced Theory & Extensions
### Ward Linkage
Minimize within-cluster variance.
### Time Complexity
O(N²) to O(N³) depending on linkage.
### Divisive Clustering
Top-down hierarchical approach.
---
## Computational Considerations
Agglomerative: O(N²) to O(N³).
Space: O(N²) distance matrix.
Dendrogram: O(N) visualization.
---
## Practical Implementation Strategies
### Distance Metric
Euclidean, Manhattan, cosine.
### Linkage Selection
Single/Complete/Average/Ward; domain choice.
### Distance Matrix
Precompute and cache.
---
## Benchmark Datasets & Evaluation
Iris: Classic hierarchical benchmark.
Gene Expression: Biological clustering.
Document Similarity: Text clustering.
---
## Key Challenges & Limitations
### Computational Cost
O(N²) or higher; prohibits large datasets.
### Linkage Sensitivity
Different linkage yields different trees.
### No K Parameter
Tree cutting required for final clusters.
---
## Hyperparameter Tuning
Linkage: Single, Complete, Average, Ward.
Distance metric: Euclidean or other.
Cutoff height: Dendrogram interpretation.
---
## Real-World Applications & Case Studies
Gene Clustering: Biological taxonomy.
Document Hierarchies: Information organization.
Customer Segmentation: Nested groups.
---
## Integration with Other Methods
Hierarchical + Feature Reduction → dendrogram vis.
Hierarchical + Thresholding → flat clusters.
---
## Summary & Key Takeaways
Hierarchical Clustering via agglomerative merging enables interpretable multi-level cluster discovery with dendrogram visualization.
Principles:
1. Linkage: inter-cluster distance.
2. Agglomerative: bottom-up merging.
3. Dendrogram: tree visualization.
4. Cutoff: cluster determination.
5. Interpretability: hierarchical structure.
---
---
## Appendix: Practical Labs
### Lab 1: Pairwise Distances
import numpy as np
def pairwise_distances(X, metric='euclidean'):
"""Compute pairwise distances"""
N = len(X)
distances = np.zeros((N, N))
for i in range(N):
for j in range(i+1, N):
if metric == 'euclidean':
dist = np.linalg.norm(X[i] - X[j])
else: # cosine
dist = 1 - (X[i] @ X[j]) / (np.linalg.norm(X[i]) * np.linalg.norm(X[j]) + 1e-8)
distances[i, j] = dist
distances[j, i] = dist
return distances
# Test
np.random.seed(42)
X = np.random.randn(10, 3)
distances = pairwise_distances(X)
assert distances.shape == (10, 10), "Distance matrix shape"
assert np.allclose(distances, distances.T), "Matrix symmetric"
print("✓ Pairwise distances working")
if __name__ == "__main__":
print("Lab 1: PairwiseDistances - PASSED")### Lab 2: Linkage Criteria
import numpy as np
def compute_linkage(dist_matrix, cluster1, cluster2, linkage='average'):
"""Compute distance between two clusters"""
distances = []
for i in cluster1:
for j in cluster2:
distances.append(dist_matrix[i, j])
if linkage == 'single':
return np.min(distances)
elif linkage == 'complete':
return np.max(distances)
elif linkage == 'average':
return np.mean(distances)
else:
raise ValueError(f"Unknown linkage: {linkage}")
# Test
np.random.seed(42)
dist_matrix = np.random.rand(5, 5)
dist_matrix = (dist_matrix + dist_matrix.T) / 2
cluster1 = [0, 1]
cluster2 = [2, 3]
for linkage_type in ['single', 'complete', 'average']:
dist = compute_linkage(dist_matrix, cluster1, cluster2, linkage_type)
assert 0 <= dist <= 1, f"Distance in [0,1] for {linkage_type}"
print("✓ Linkage criteria working")
if __name__ == "__main__":
print("Lab 2: LinkageCriteria - PASSED")### Lab 3: Agglomerative Clustering
import numpy as np
def agglomerative_clustering(dist_matrix, num_clusters=3):
"""Simple agglomerative hierarchical clustering"""
N = len(dist_matrix)
clusters = [[i] for i in range(N)] # Start with singleton clusters
while len(clusters) > num_clusters:
# Find two closest clusters
min_dist = np.inf
merge_i, merge_j = 0, 1
for i in range(len(clusters)):
for j in range(i+1, len(clusters)):
# Average linkage
dist = 0
for pi in clusters[i]:
for pj in clusters[j]:
dist += dist_matrix[pi, pj]
dist /= len(clusters[i]) * len(clusters[j])
if dist < min_dist:
min_dist = dist
merge_i, merge_j = i, j
# Merge clusters
clusters[merge_i].extend(clusters[merge_j])
del clusters[merge_j]
return clusters
# Test
np.random.seed(42)
dist_matrix = np.random.rand(10, 10)
dist_matrix = (dist_matrix + dist_matrix.T) / 2
clusters = agglomerative_clustering(dist_matrix, num_clusters=3)
assert len(clusters) == 3, "Correct number of clusters"
assert sum(len(c) for c in clusters) == 10, "All points assigned"
print("✓ Agglomerative clustering working")
if __name__ == "__main__":
print("Lab 3: AgglomerativeClustering - PASSED")### Lab 4: Dendrogram Preparation
import numpy as np
def build_dendrogram_linkage(dist_matrix, num_steps=None):
"""Build linkage matrix for dendrogram"""
N = len(dist_matrix)
if num_steps is None:
num_steps = N - 1
linkage_matrix = []
clusters = [[i] for i in range(N)]
cluster_idx = N
for step in range(num_steps):
# Find closest clusters
min_dist = np.inf
merge_i, merge_j = 0, 1
for i in range(len(clusters)):
for j in range(i+1, len(clusters)):
dist = 0
for pi in clusters[i]:
for pj in clusters[j]:
dist += dist_matrix[pi, pj]
dist /= len(clusters[i]) * len(clusters[j])
if dist < min_dist:
min_dist = dist
merge_i, merge_j = i, j
# Record linkage
cluster_id_i = merge_i if merge_i < N else merge_i + N
cluster_id_j = merge_j if merge_j < N else merge_j + N
linkage_matrix.append([cluster_id_i, cluster_id_j, min_dist, len(clusters[merge_i]) + len(clusters[merge_j])])
# Merge
clusters[merge_i].extend(clusters[merge_j])
del clusters[merge_j]
return np.array(linkage_matrix)
# Test
np.random.seed(42)
dist_matrix = np.random.rand(5, 5)
dist_matrix = (dist_matrix + dist_matrix.T) / 2
linkage = build_dendrogram_linkage(dist_matrix)
assert linkage.shape[0] == 4, "Linkage matrix rows"
assert linkage.shape[1] == 4, "Linkage matrix columns"
print("✓ Dendrogram preparation working")
if __name__ == "__main__":
print("Lab 4: DendrogramPreparation - PASSED")