Clustering

What is Clustering?

Clustering is an unsupervised task: group unlabeled data points so that points within a group (cluster) are more similar to each other than to points in other groups. There are no ground-truth labels — the algorithm discovers structure.

Applications: customer segmentation, document grouping, image compression, anomaly detection, data exploration, biological taxonomy, recommendation pre-processing.

k-Means Clustering

The most widely used clustering algorithm. Partitions data into exactly k clusters by minimizing the within-cluster sum of squares (WCSS):

WCSS = Σₖ Σᵢ∈Cₖ ‖xᵢ − μₖ‖²

where μₖ is the centroid of cluster k.

The Algorithm (Lloyd's Algorithm)

1. Initialize k centroids (randomly or with k-means++)
2. Assignment step: assign each point to the nearest centroid
3. Update step: recompute centroids as mean of assigned points
4. Repeat 2–3 until centroids stop moving

Convergence is guaranteed (WCSS can only decrease), but to a local minimum — results depend on initialization.

k-Means++ Initialization

Smarter initialization that spreads initial centroids apart: 1. Choose first centroid uniformly at random 2. Choose each subsequent centroid with probability proportional to d(x)² — squared distance to the nearest existing centroid

k-means++ is the default in sklearn and gives much better results on average.

from sklearn.cluster import KMeans
import numpy as np

kmeans = KMeans(
    n_clusters=5,
    init="k-means++",   # default
    n_init=10,          # number of random initializations
    max_iter=300,
    random_state=42
)
kmeans.fit(X)

labels  = kmeans.labels_            # cluster assignment per point
centers = kmeans.cluster_centers_   # shape (k, n_features)
inertia = kmeans.inertia_           # WCSS (lower = tighter clusters)

Choosing k — The Elbow Method

Run k-means for k = 1, 2, …, 20. Plot WCSS vs. k. Look for the "elbow" where WCSS stops decreasing rapidly.

import matplotlib.pyplot as plt

wcss = []
K_range = range(1, 15)
for k in K_range:
    km = KMeans(n_clusters=k, n_init=10, random_state=42)
    km.fit(X)
    wcss.append(km.inertia_)

plt.plot(K_range, wcss, "bo-")
plt.xlabel("k"); plt.ylabel("WCSS"); plt.title("Elbow Method")
plt.show()

Silhouette Score

Quantifies cluster quality without ground truth:

s(i) = (b(i) − a(i)) / max(a(i), b(i))

• a(i) = mean distance to other points in the same cluster (cohesion)
• b(i) = mean distance to points in the nearest other cluster (separation)

Range [−1, 1]. Higher is better. s ≈ 1 = tight, well-separated; s ≈ 0 = on boundary; s < 0 = wrong cluster.

from sklearn.metrics import silhouette_score

score = silhouette_score(X, kmeans.labels_)
print(f"Silhouette: {score:.3f}")

Limitations of k-means: - Requires specifying k - Assumes roughly equal-sized, spherical clusters - Sensitive to outliers (centroid gets pulled) - Requires scaling (uses Euclidean distance)

Hierarchical Clustering

Builds a tree of clusters (dendrogram) without needing to specify k in advance.

Agglomerative (Bottom-Up)

1. Start with each point as its own cluster
2. Merge the two closest clusters
3. Repeat until one cluster remains

Linkage criteria (defines "distance between clusters"):

Ward linkage is usually the best default.

from sklearn.cluster import AgglomerativeClustering
from scipy.cluster.hierarchy import dendrogram, linkage

# Fit and cut the tree at k clusters
agg = AgglomerativeClustering(n_clusters=4, linkage="ward")
labels = agg.fit_predict(X)

# Plot dendrogram (for small datasets)
Z = linkage(X, method="ward")
dendrogram(Z, truncate_mode="lastp", p=20)
plt.title("Dendrogram")
plt.show()

Advantages: no k needed, dendrogram reveals hierarchy, deterministic. Disadvantages: O(n²) memory, O(n³) time (or O(n² log n) with optimizations), cannot undo merges.

DBSCAN (Density-Based Spatial Clustering)

Groups points that are densely packed together; marks low-density points as noise. Does not require specifying k and finds arbitrarily-shaped clusters.

Parameters

• ε (eps): neighborhood radius
• MinPts: minimum neighbors within ε to be a core point

Point Types

• Core point: has ≥ MinPts points within ε
• Border point: within ε of a core point but fewer than MinPts neighbors itself
• Noise/outlier: not within ε of any core point (labeled −1)

Algorithm

1. For each unvisited point, check if it is a core point
2. If yes, start a cluster: expand by recursively adding all density-reachable points
3. Mark unclassifiable points as noise

from sklearn.cluster import DBSCAN
from sklearn.preprocessing import StandardScaler

X_scaled = StandardScaler().fit_transform(X)

dbscan = DBSCAN(eps=0.5, min_samples=5, metric="euclidean")
labels = dbscan.fit_predict(X_scaled)

n_clusters = len(set(labels)) - (1 if -1 in labels else 0)
n_noise    = (labels == -1).sum()
print(f"Clusters: {n_clusters}, Noise points: {n_noise}")

Choosing ε: plot k-nearest-neighbor distances for k=MinPts; look for the "knee".

Advantages: finds arbitrary shapes, robust to outliers, no k needed. Disadvantages: fails on varying-density data, ε hard to choose in high dimensions, O(n²) without spatial indexing.

HDBSCAN

Hierarchical DBSCAN — builds a full density hierarchy and extracts stable clusters without needing to tune ε. More robust than DBSCAN. Recommended over DBSCAN in most cases.

import hdbscan  # pip install hdbscan

clusterer = hdbscan.HDBSCAN(min_cluster_size=20, min_samples=5)
labels = clusterer.fit_predict(X_scaled)

Gaussian Mixture Models (GMM)

A probabilistic clustering model: assume data is generated by a mixture of K Gaussian distributions. Unlike k-means, GMM provides: - Soft assignments: probability that point i belongs to cluster k - Elliptical clusters: covariance matrix per cluster - Model selection via BIC/AIC

GMM is fit with the Expectation-Maximization (EM) algorithm: - E-step: compute P(cluster k | point i) using current parameters - M-step: update cluster parameters (μ, Σ, π) using soft assignments

from sklearn.mixture import GaussianMixture

gmm = GaussianMixture(
    n_components=4,
    covariance_type="full",  # full, tied, diag, spherical
    n_init=5,
    random_state=42
)
gmm.fit(X)

labels = gmm.predict(X)           # hard cluster assignment
probs  = gmm.predict_proba(X)     # soft probabilities
print(f"BIC: {gmm.bic(X):.1f}")  # lower BIC = better (penalizes complexity)

Covariance types:

Spectral Clustering

Uses the eigenstructure of a similarity graph to cluster in a lower-dimensional space. Handles non-convex clusters that fool k-means.

Algorithm: 1. Build similarity matrix W (Gaussian kernel: Wᵢⱼ = exp(−‖xᵢ−xⱼ‖²/2σ²)) 2. Compute graph Laplacian L = D − W (D is degree matrix) 3. Compute first k eigenvectors of L 4. Run k-means in the eigenvector space

from sklearn.cluster import SpectralClustering

sc = SpectralClustering(n_clusters=4, affinity="rbf", gamma=1.0,
                         assign_labels="kmeans", random_state=42)
labels = sc.fit_predict(X)

Use when clusters have a ring, concentric, or other non-convex shape.

Cluster Evaluation Metrics

When Ground Truth Labels Are Available

from sklearn.metrics import (
    adjusted_rand_score, normalized_mutual_info_score,
    homogeneity_completeness_v_measure
)

ari = adjusted_rand_score(y_true, labels)
nmi = normalized_mutual_info_score(y_true, labels)
h, c, v = homogeneity_completeness_v_measure(y_true, labels)

When Ground Truth Is Not Available

Algorithm Comparison

Practical Tips

• Always scale features before clustering (unless using tree-based distances)
• Reduce dimensionality (PCA to 10–50 dims) before clustering in high dimensions — curse of dimensionality makes all distances similar
• Visualize with t-SNE or UMAP after clustering to sanity check
• Run multiple initializations and pick the best result (for k-means)
• Check silhouette plots per sample to identify ambiguous assignments
• Combine with domain knowledge: a technically good k may not make business sense