K-Means partitions \(N\) data points into \(K\) non-overlapping clusters by iteratively assigning each point to the nearest centroid and then recomputing centroids as cluster means. The algorithm minimises the within-cluster sum of squared distances (inertia), converging to a local minimum.
Objective (minimise inertia):
\[J = \sum_{k=1}^{K} \sum_{\mathbf{x}_i \in C_k} \|\mathbf{x}_i - \boldsymbol{\mu}_k\|^2\]Assignment step (E-step):
\[c_i = \arg\min_k \|\mathbf{x}_i - \boldsymbol{\mu}_k\|^2\]Update step (M-step):
\[\boldsymbol{\mu}_k = \frac{1}{|C_k|}\sum_{\mathbf{x}_i \in C_k} \mathbf{x}_i\]Silhouette Score (cluster quality, \(\in[-1,1]\)):
\[s(i) = \frac{b(i) - a(i)}{\max\{a(i),\, b(i)\}}\]where \(a(i)\) = mean intra-cluster distance, \(b(i)\) = mean nearest-cluster distance
K-Means++ initialises centroids spread out across the data, greatly improving convergence quality. The Elbow Method plots inertia vs \(K\) to find the "knee" — the point where adding more clusters gives diminishing returns. The algorithm is sensitive to outliers and assumes spherical, equally-sized clusters. Mini-batch K-Means scales to millions of points. Always scale features before clustering since K-Means uses Euclidean distance.
A bank segments 50,000 customers into 5 groups by annual income, average balance, and transaction frequency for targeted product campaigns. Cluster 3 (high income, high balance) gets premium wealth management offers.
| Cluster | Income $k | Balance $k | Segment |
|---|---|---|---|
| 1 | 28 | 2.1 | Basic |
| 3 | 120 | 85 | Premium |
| 5 | 65 | 12 | Mid-tier |
Clustering 500 weather stations by annual temperature, rainfall, and frost days into 4 agro-climatic zones for crop suitability mapping. Each zone receives tailored agronomic recommendations.
| Zone | Temp°C | Rain mm | Frost days |
|---|---|---|---|
| 1 | 8 | 600 | 45 |
| 2 | 18 | 1200 | 5 |
| 3 | 24 | 400 | 0 |
Clustering 2,000 heart failure patients by BNP, EF, creatinine, and 6-min walk distance into 3 phenotypes with different prognosis and treatment response — enabling precision medicine protocols.
| Phenotype | BNP | EF% | Mortality% |
|---|---|---|---|
| A | 180 | 52 | 8 |
| B | 820 | 28 | 34 |
| C | 420 | 42 | 18 |
import numpy as np
import pandas as pd
from sklearn.cluster import KMeans
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import silhouette_score, davies_bouldin_score
np.random.seed(42)
# ── Simulate Customer Segmentation Data ───────────────────────
def make_segment(n, inc_mu, bal_mu, freq_mu, label):
return pd.DataFrame({
'income': np.random.normal(inc_mu, 10, n),
'balance': np.random.normal(bal_mu, bal_mu*0.15, n),
'freq': np.random.normal(freq_mu, 3, n),
'true_seg': [label]*n
})
df = pd.concat([
make_segment(1000, 28, 2.1, 8, 'Basic'),
make_segment(800, 65, 12, 15, 'Mid-tier'),
make_segment(500, 95, 42, 12, 'Affluent'),
make_segment(300, 120, 85, 9, 'Premium'),
make_segment(400, 45, 5, 22, 'Young-active')
]).reset_index(drop=True)
X = df[['income','balance','freq']].values
scaler = StandardScaler()
X_sc = scaler.fit_transform(X)
# ── Elbow Method ──────────────────────────────────────────────
print("=== K-Means — Elbow Method ===")
print(f"{'K':>4} | {'Inertia':>12} | {'Silhouette':>12} | {'DB Score':>10}")
print("-"*46)
for k in range(2, 9):
km = KMeans(n_clusters=k, init='k-means++', n_init=10, random_state=42)
labels = km.fit_predict(X_sc)
sil = silhouette_score(X_sc, labels)
db = davies_bouldin_score(X_sc, labels)
print(f"{k:4d} | {km.inertia_:12.2f} | {sil:12.4f} | {db:10.4f}")
# ── Fit with K=5 ─────────────────────────────────────────────
km5 = KMeans(n_clusters=5, init='k-means++', n_init=20, random_state=42)
df['cluster'] = km5.fit_predict(X_sc)
# ── Cluster profiles ──────────────────────────────────────────
print("\nCluster Profiles:")
print(df.groupby('cluster')[['income','balance','freq']].mean().round(2))
# ── Agreement with true segments ─────────────────────────────
from sklearn.metrics import adjusted_rand_score
ari = adjusted_rand_score(df['true_seg'], df['cluster'])
print(f"\nAdjusted Rand Index vs True Segments: {ari:.4f}")
library(cluster); set.seed(42)
# ── Simulate Customer Data ────────────────────────────────────
make_seg <- function(n, inc, bal, freq, lbl)
data.frame(income=rnorm(n,inc,10), balance=rnorm(n,bal,bal*.15),
freq=rnorm(n,freq,3), true_seg=rep(lbl,n))
df <- rbind(make_seg(1000,28,2.1,8,"Basic"), make_seg(800,65,12,15,"Mid-tier"),
make_seg(500,95,42,12,"Affluent"), make_seg(300,120,85,9,"Premium"),
make_seg(400,45,5,22,"Young-active"))
X <- scale(df[,1:3])
# ── Elbow + Silhouette ────────────────────────────────────────
cat("K | Inertia | Silhouette\n")
cat("---|---------------|----------\n")
for(k in 2:8) {
km <- kmeans(X, centers=k, nstart=10, iter.max=100)
sil <- mean(silhouette(km$cluster, dist(X))[,3])
cat(sprintf("%2d | %13.2f | %.4f\n", k, km$tot.withinss, sil))
}
# ── Fit K=5 ───────────────────────────────────────────────────
km5 <- kmeans(X, centers=5, nstart=25, iter.max=200)
df$cluster <- km5$cluster
# ── Cluster profiles ─────────────────────────────────────────
cat("\nCluster Profiles:\n")
print(aggregate(cbind(income,balance,freq)~cluster, data=df, FUN=mean))
cat(sprintf("\nTotal within-cluster SS: %.2f\n", km5$tot.withinss))
DBSCAN (Density-Based Spatial Clustering of Applications with Noise) groups together points that are closely packed in dense regions, marking isolated points in low-density regions as outliers/noise. It requires two parameters: \(\varepsilon\) (neighbourhood radius) and MinPts (minimum points for a core region). It can discover clusters of arbitrary shape and does not require specifying \(K\) in advance.
\(\varepsilon\)-neighbourhood: \(N_\varepsilon(\mathbf{p}) = \{\mathbf{q} \in \mathcal{D} \mid d(\mathbf{p},\mathbf{q}) \le \varepsilon\}\)
Core point: \(|N_\varepsilon(\mathbf{p})| \ge \text{MinPts}\)
Border point: not a core point but in the \(\varepsilon\)-neighbourhood of a core point
Noise point: neither core nor border
Direct density-reachability: \(\mathbf{q}\) is directly density-reachable from \(\mathbf{p}\) if \(\mathbf{q} \in N_\varepsilon(\mathbf{p})\) and \(\mathbf{p}\) is a core point
Density-connectivity: \(\mathbf{p}\) and \(\mathbf{q}\) are density-connected if \(\exists\, \mathbf{o}\) from which both are density-reachable
Optimal \(\varepsilon\): Use k-dist plot — find the "knee" in sorted distances to \(k\)-th nearest neighbour
DBSCAN's ability to detect noise and find non-convex clusters makes it ideal for geospatial and anomaly-detection tasks. Time complexity is \(O(N \log N)\) with an appropriate spatial index (KD-tree). The k-dist plot helps choose \(\varepsilon\): set MinPts \(= 2 \times d\) (twice the number of dimensions) and look for the elbow in sorted kNN distances. HDBSCAN is the hierarchical variant that automatically finds clusters across varying densities without a fixed \(\varepsilon\).
Transactions plotted in amount × frequency space show tight normal clusters; fraudulent transactions form sparse, unusual clusters or are flagged as noise. DBSCAN separates the dense legitimate core from sparse outliers without being told how many clusters to expect, and — unlike K-Means — it can label a point as noise rather than forcing it into the nearest cluster. That noise label is the fraud signal.
| Amount | Freq/hr | Label |
|---|---|---|
| $45–200 | 1–3 | Normal |
| $3,200+ | 15+ | Fraud cluster |
| $890 | 1 | Noise (suspect) |
Geospatial soil samples with GPS coordinates and pH values. DBSCAN identifies dense patches of acidic soil (pH<5.5) requiring lime treatment, plus isolated noise readings from measurement errors.
| Lat | Lon | pH | Result |
|---|---|---|---|
| 51.42 | -0.12 | 5.1 | Acid cluster |
| 51.45 | -0.18 | 6.8 | Normal cluster |
| 51.40 | -0.22 | 3.9 | Noise |
Single-cell RNA-seq data with thousands of cells embedded in 2D (UMAP). DBSCAN finds distinct cell-type clusters (T-cells, B-cells, macrophages) and marks transitional states as noise without pre-specifying \(K\).
| UMAP1 | UMAP2 | Cell Type |
|---|---|---|
| -8.2 | 3.1 | T-cell cluster |
| 4.5 | -6.8 | B-cell cluster |
| 0.1 | 0.3 | Noise |
import numpy as np
import pandas as pd
from sklearn.cluster import DBSCAN
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import NearestNeighbors
from sklearn.metrics import adjusted_rand_score
np.random.seed(42)
# ── Simulate Financial Transaction Data (2D: amount, frequency) ──
def ring_cluster(n, cx, cy, r, noise):
angles = np.random.uniform(0, 2*np.pi, n)
return np.column_stack([cx + r*np.cos(angles) + np.random.normal(0,noise,n),
cy + r*np.sin(angles) + np.random.normal(0,noise,n)])
# Normal transactions: two dense blobs
normal_a = np.random.multivariate_normal([80, 2], [[400,2],[2,0.5]], 2000)
normal_b = np.random.multivariate_normal([150, 4], [[900,5],[5,1.0]], 1500)
# Fraud: sparse, unusual region
fraud = np.random.multivariate_normal([3200, 18], [[1e5,50],[50,8]], 50)
# Noise transactions
noise_pts = np.column_stack([np.random.uniform(500, 2000, 30),
np.random.uniform(8, 14, 30)])
X = np.vstack([normal_a, normal_b, fraud, noise_pts])
y_true = np.array([0]*2000 + [0]*1500 + [1]*50 + [-1]*30) # 0=normal,1=fraud,-1=noise
X_sc = StandardScaler().fit_transform(X)
# ── k-dist plot to choose eps ─────────────────────────────────
nbrs = NearestNeighbors(n_neighbors=5).fit(X_sc)
dists, _ = nbrs.kneighbors(X_sc)
k_dists = np.sort(dists[:, 4])[::-1]
print("Top-10 k-distances (for eps selection):")
print(np.round(k_dists[:10], 3))
# ── DBSCAN ────────────────────────────────────────────────────
db = DBSCAN(eps=0.4, min_samples=10).fit(X_sc)
labels = db.labels_
n_clusters = len(set(labels)) - (1 if -1 in labels else 0)
n_noise = np.sum(labels == -1)
noise_pct = n_noise / len(labels) * 100
print(f"\n=== DBSCAN — Transaction Clustering ===")
print(f"Clusters found : {n_clusters}")
print(f"Noise points : {n_noise} ({noise_pct:.2f}%)")
print(f"Cluster sizes : {dict(zip(*np.unique(labels, return_counts=True)))}")
# ── Fraud recall ──────────────────────────────────────────────
fraud_idx = np.where(y_true == 1)[0]
fraud_labels = labels[fraud_idx]
print(f"\nFraud transactions label distribution:")
print(dict(zip(*np.unique(fraud_labels, return_counts=True))))
# ── Try different eps values ──────────────────────────────────
print("\nSensitivity to eps (min_samples=10):")
for eps in [0.2, 0.3, 0.4, 0.5, 0.7]:
lb = DBSCAN(eps=eps, min_samples=10).fit_predict(X_sc)
nc = len(set(lb)) - (1 if -1 in lb else 0)
nn = np.sum(lb==-1)
print(f" eps={eps:.1f}: {nc} clusters, {nn} noise pts")
library(dbscan); set.seed(42)
# ── Simulate Transaction Data ────────────────────────────────
normal_a <- MASS::mvrnorm(2000, mu=c(80,2),
Sigma=matrix(c(400,2,2,.5),2,2))
normal_b <- MASS::mvrnorm(1500, mu=c(150,4),
Sigma=matrix(c(900,5,5,1),2,2))
fraud <- MASS::mvrnorm(50, mu=c(3200,18),
Sigma=matrix(c(1e5,50,50,8),2,2))
noise_p <- cbind(runif(30,500,2000), runif(30,8,14))
X <- rbind(normal_a, normal_b, fraud, noise_p)
X_sc <- scale(X)
# ── k-NN distance plot (choose eps) ──────────────────────────
kNNdist_plot <- kNNdist(X_sc, k=5)
cat("Sorted 5-NN distances (first 10 largest):\n")
print(round(sort(kNNdist_plot, decreasing=TRUE)[1:10], 3))
# ── DBSCAN ────────────────────────────────────────────────────
res <- dbscan(X_sc, eps=0.4, minPts=10)
print(res)
# ── Summary ───────────────────────────────────────────────────
n_clusters <- max(res$cluster)
n_noise <- sum(res$cluster == 0)
cat(sprintf("Clusters: %d, Noise: %d (%.2f%%)\n",
n_clusters, n_noise, 100*n_noise/nrow(X_sc)))
# ── Sensitivity analysis ──────────────────────────────────────
cat("\neps sensitivity:\n")
for(eps in c(0.2,0.3,0.4,0.5,0.7)) {
r <- dbscan(X_sc, eps=eps, minPts=10)
cat(sprintf(" eps=%.1f: %d clusters, %d noise\n",
eps, max(r$cluster), sum(r$cluster==0)))
}
Hierarchical clustering builds a tree (dendrogram) of cluster merges. In the agglomerative (bottom-up) approach, each point starts as its own cluster, and the two most similar clusters are merged at each step. The dendrogram can then be cut at any height to obtain any desired number of clusters, without rerunning the algorithm.
Linkage Criteria (distance between clusters \(A\) and \(B\)):
\[d_{\text{single}}(A,B) = \min_{\mathbf{a}\in A,\mathbf{b}\in B} d(\mathbf{a},\mathbf{b})\] \[d_{\text{complete}}(A,B) = \max_{\mathbf{a}\in A,\mathbf{b}\in B} d(\mathbf{a},\mathbf{b})\] \[d_{\text{average}}(A,B) = \frac{1}{|A||B|}\sum_{\mathbf{a}\in A}\sum_{\mathbf{b}\in B} d(\mathbf{a},\mathbf{b})\]Ward's Method (minimises within-cluster variance):
\[d_{\text{ward}}(A,B) = \frac{|A||B|}{|A|+|B|}\|\boldsymbol{\mu}_A - \boldsymbol{\mu}_B\|^2\]Complexity: \(O(N^2 \log N)\) with optimised implementations
Ward's linkage is most commonly used — it tends to create compact, equally-sized clusters. Single linkage suffers from "chaining" (elongated chains), while complete linkage tends to produce compact clusters. The dendrogram visualises the entire hierarchical structure; cutting at different heights gives different numbers of clusters. The cophenetic correlation coefficient measures how well the dendrogram preserves original pairwise distances.
Hierarchically clustering 30 stocks by correlation of daily returns reveals sector groupings (technology, energy, healthcare), enabling portfolio diversification by selecting one stock from each cluster branch.
| Branch | Assets | Avg Corr |
|---|---|---|
| Tech | AAPL,MSFT,NVDA | 0.82 |
| Energy | XOM,CVX,BP | 0.76 |
| Healthcare | JNJ,PFE,MRK | 0.71 |
Clustering 50 plant varieties by 8 morphological traits (height, leaf area, seed weight) creates a dendrogram showing evolutionary similarity. Agronomists select distant branches for cross-breeding diversity.
| Variety | Height cm | LeafArea | Clade |
|---|---|---|---|
| Var_A | 82 | 28.4 | I |
| Var_B | 79 | 27.1 | I |
| Var_C | 124 | 41.2 | III |
Clustering 200 lupus patients by 12 clinical biomarkers reveals 4 subtypes with different organ involvement patterns. Cutting the dendrogram at height=2.5 gives the 4-subtype solution used for treatment stratification.
| Subtype | Organ Involvement | n |
|---|---|---|
| I | Skin + Joints | 68 |
| II | Renal | 42 |
| III | Neuro | 35 |
| IV | Multi-organ | 55 |
import numpy as np
import pandas as pd
from scipy.cluster.hierarchy import linkage, dendrogram, fcluster, cophenet
from scipy.spatial.distance import pdist
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import silhouette_score
np.random.seed(42)
# ── Simulate Lupus Patient Biomarker Data ─────────────────────
def subtype(n, means, label):
cov = np.diag([1.2]*len(means))
return pd.DataFrame(
np.random.multivariate_normal(means, cov, n),
columns=[f'bio{i}' for i in range(len(means))]
).assign(true=label)
n_bio = 8
df = pd.concat([
subtype(68, [2.1, 1.8, 0.5, 0.3, 1.2, 0.8, 0.4, 0.6], 'Skin+Joints'),
subtype(42, [0.8, 0.6, 2.9, 2.4, 0.7, 1.1, 0.3, 0.4], 'Renal'),
subtype(35, [0.4, 0.5, 0.6, 0.3, 2.8, 2.4, 1.8, 1.2], 'Neuro'),
subtype(55, [1.9, 1.7, 1.8, 1.6, 1.7, 1.5, 1.6, 1.8], 'Multi-organ')
]).reset_index(drop=True)
X = StandardScaler().fit_transform(df.drop('true', axis=1))
# ── Linkage methods comparison ────────────────────────────────
print("Linkage | Cophenetic r | Silhouette (k=4)")
print("----------|--------------|-----------------")
for method in ['ward','complete','average','single']:
Z = linkage(X, method=method)
c, _ = cophenet(Z, pdist(X))
labels = fcluster(Z, t=4, criterion='maxclust')
sil = silhouette_score(X, labels)
print(f"{method:10s}| {c:.4f} | {sil:.4f}")
# ── Ward linkage dendrogram cut at k=4 ───────────────────────
Z = linkage(X, method='ward')
labels4 = fcluster(Z, t=4, criterion='maxclust')
df['cluster'] = labels4
# ── Cluster purity ────────────────────────────────────────────
from sklearn.metrics import adjusted_rand_score
ari = adjusted_rand_score(df['true'], labels4)
print(f"\nAdjusted Rand Index (ward, k=4): {ari:.4f}")
# ── Cluster sizes ─────────────────────────────────────────────
print("Cluster sizes:", dict(zip(*np.unique(labels4, return_counts=True))))
print("\nCross-tabulation (cluster vs true subtype):")
print(pd.crosstab(df['cluster'], df['true']))
set.seed(42)
# ── Simulate Lupus Data ───────────────────────────────────────
make_sub <- function(n, mus, label) {
df <- as.data.frame(matrix(rnorm(n*length(mus), mean=rep(mus,n), sd=1.2), n, length(mus)))
df$true <- label; df
}
df <- rbind(make_sub(68, c(2.1,1.8,0.5,0.3,1.2,0.8,0.4,0.6), "Skin+Joints"),
make_sub(42, c(0.8,0.6,2.9,2.4,0.7,1.1,0.3,0.4), "Renal"),
make_sub(35, c(0.4,0.5,0.6,0.3,2.8,2.4,1.8,1.2), "Neuro"),
make_sub(55, c(1.9,1.7,1.8,1.6,1.7,1.5,1.6,1.8), "Multi-organ"))
X <- scale(df[,-ncol(df)])
# ── Compare linkage methods ───────────────────────────────────
for(method in c("ward.D2","complete","average","single")) {
hc <- hclust(dist(X), method=method)
cls <- cutree(hc, k=4)
# Cophenetic
coph <- cor(cophenetic(hc), dist(X))
cat(sprintf("%-10s: coph=%.4f\n", method, coph))
}
# ── Ward dendrogram, cut at k=4 ──────────────────────────────
hc4 <- hclust(dist(X), method="ward.D2")
labels <- cutree(hc4, k=4)
df$cluster <- labels
cat("\nCluster sizes:\n"); print(table(labels))
# ── Cross-tab ─────────────────────────────────────────────────
cat("\nCross-tabulation:\n"); print(table(df$cluster, df$true))
# ── ARI ───────────────────────────────────────────────────────
library(mclust)
cat(sprintf("\nARI = %.4f\n", adjustedRandIndex(labels, df$true)))
The same information as the assumption blocks above, side by side — this is the comparison that decides which method to reach for.
| Algorithm | Assumes | Breaks when |
|---|---|---|
| 2.1 K-Means Clustering | Clusters are roughly spherical, similar in size, and separated by variance | Clusters are elongated or nested — use DBSCAN or a GMM instead |
| 2.2 DBSCAN | Clusters are dense regions separated by sparser ones | Densities differ between clusters — one \(\varepsilon\) cannot fit both; use HDBSCAN |
| 2.3 Hierarchical / Agglomerative Clustering | A meaningful nested structure exists in the data | \(N\) is large — \(O(N^2)\) memory for the distance matrix becomes prohibitive |