Skip to the content

Algorithms on This Page

2.1 K-Means Clustering 2.2 DBSCAN 2.3 Hierarchical / Agglomerative Clustering

2.1  K-Means Clustering

Centroid-BasedPartitional
DEFINITION

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.

2.1.1  Mathematical Foundation

FORMULAE

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

2.1.2  How It Works

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.

2.1.3  Assumptions and Failure Modes

ASSUMES
  • Clusters are roughly spherical, similar in size, and separated by variance
  • \(K\) is known in advance
BREAKS WHEN
  • Clusters are elongated or nested — use DBSCAN or a GMM instead
  • Outliers are present — centroids are dragged toward them
  • Features are unscaled, or the run is not repeated with k-means++

2.1.4  Worked Examples

FINANCE

👥 Customer Segmentation

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.

ClusterIncome $kBalance $kSegment
1282.1Basic
312085Premium
56512Mid-tier
AGRICULTURE

🗺️ Regional Climate Zones

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.

ZoneTemp°CRain mmFrost days
1860045
21812005
3244000
MEDICINE

🫀 Patient Phenotype Clustering

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.

PhenotypeBNPEF%Mortality%
A180528
B8202834
C4204218

2.1.5  Code

K-Means
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))

2.2  DBSCAN

Density-BasedArbitrary Shapes
DEFINITION

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.

2.2.1  Mathematical Foundation

FORMULAE

\(\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

2.2.2  How It Works

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\).

2.2.3  Assumptions and Failure Modes

ASSUMES
  • Clusters are dense regions separated by sparser ones
BREAKS WHEN
  • Densities differ between clusters — one \(\varepsilon\) cannot fit both; use HDBSCAN
  • Dimensionality is high — the k-dist plot loses its knee
  • \(\varepsilon\) is guessed rather than read off a k-distance plot

2.2.4  Worked Examples

FINANCE

🚨 Fraud Cluster Detection

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.

AmountFreq/hrLabel
$45–2001–3Normal
$3,200+15+Fraud cluster
$8901Noise (suspect)
AGRICULTURE

📍 Spatial Soil Anomaly Mapping

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.

LatLonpHResult
51.42-0.125.1Acid cluster
51.45-0.186.8Normal cluster
51.40-0.223.9Noise
MEDICINE

🧫 Gene Expression Pattern Clustering

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\).

UMAP1UMAP2Cell Type
-8.23.1T-cell cluster
4.5-6.8B-cell cluster
0.10.3Noise

2.2.5  Code

DBSCAN
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)))
}

2.3  Hierarchical / Agglomerative Clustering

HierarchicalDendrogram
DEFINITION

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.

2.3.1  Mathematical Foundation

FORMULAE

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

2.3.2  How It Works

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.

2.3.3  Assumptions and Failure Modes

ASSUMES
  • A meaningful nested structure exists in the data
BREAKS WHEN
  • \(N\) is large — \(O(N^2)\) memory for the distance matrix becomes prohibitive
  • Single linkage is used on noisy data — clusters chain together
  • The cut height is chosen by eye without checking cophenetic correlation

2.3.4  Worked Examples

FINANCE

📈 Asset Correlation Clustering

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.

BranchAssetsAvg Corr
TechAAPL,MSFT,NVDA0.82
EnergyXOM,CVX,BP0.76
HealthcareJNJ,PFE,MRK0.71
AGRICULTURE

🌿 Species Phenotype Classification

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.

VarietyHeight cmLeafAreaClade
Var_A8228.4I
Var_B7927.1I
Var_C12441.2III
MEDICINE

🧬 Patient Similarity Trees

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.

SubtypeOrgan Involvementn
ISkin + Joints68
IIRenal42
IIINeuro35
IVMulti-organ55

2.3.5  Code

Hierarchical Clustering
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)))

At a Glance

The same information as the assumption blocks above, side by side — this is the comparison that decides which method to reach for.

AlgorithmAssumesBreaks when
2.1 K-Means ClusteringClusters are roughly spherical, similar in size, and separated by varianceClusters are elongated or nested — use DBSCAN or a GMM instead
2.2 DBSCANClusters are dense regions separated by sparser onesDensities differ between clusters — one \(\varepsilon\) cannot fit both; use HDBSCAN
2.3 Hierarchical / Agglomerative ClusteringA meaningful nested structure exists in the data\(N\) is large — \(O(N^2)\) memory for the distance matrix becomes prohibitive