Hierarchical Clustering

1. Two Strategies

• Agglomerative (bottom-up): start with each point in its own cluster, repeatedly merge the closest pair until one cluster remains. Most common.
• Divisive (top-down): start with all points in one cluster, recursively split. Rare in practice.

2. The Agglomerative Algorithm

3. Linkage Methods — How "Closest" is Defined

• Single: min distance between any two points. Can produce long, chain-like clusters.
• Complete: max distance. Produces compact, spherical clusters; sensitive to outliers.
• Average: mean of all pairwise distances. Balanced.
• Ward: merge the pair that minimizes the increase in total within-cluster variance. Default in scikit-learn; works best with Euclidean distance.

4. Dendrograms & Cutting the Tree

A dendrogram visualizes the merge sequence; the y-axis shows the distance at which clusters were joined. To get K clusters, "cut" the tree at a horizontal level that crosses K vertical lines — the largest vertical gap is often a natural cut point.

5. Python Implementation

from sklearn.cluster import AgglomerativeClustering
from scipy.cluster.hierarchy import linkage, dendrogram
from sklearn.preprocessing import StandardScaler
import matplotlib.pyplot as plt

X = StandardScaler().fit_transform(X_raw)

# 1) Fit + get labels
agg = AgglomerativeClustering(n_clusters=3, linkage="ward").fit(X)
labels = agg.labels_

# 2) Or build the full linkage matrix for a dendrogram
Z = linkage(X, method="ward")
dendrogram(Z, truncate_mode="lastp", p=30)
plt.show()

Cutting at a distance instead of fixed K

agg = AgglomerativeClustering(
    n_clusters=None,
    distance_threshold=4.0,   # cut the dendrogram at this height
    linkage="ward",
).fit(X)

6. Complexity

Standard agglomerative is O(N² log N) time and O(N²)memory — heavy for large datasets. Use mini-batch methods or BIRCH for N > 50k.

7. Strengths & Weaknesses

Strengths

• No need to pre-specify K — choose visually from the dendrogram.
• Produces a hierarchy — useful for taxonomies, gene expression, document clustering.
• Deterministic (no random init).

Weaknesses

• Quadratic time & memory — slow for large N.
• Merges are greedy and irreversible — early mistakes propagate.
• Single-linkage can chain; complete-linkage is outlier-sensitive.