53  Introduction to Clustering and Evaluation Metrics

Supervised learning derives mappings from labeled instances to generalize predictions onto unseen data. Unsupervised learning operates on unlabeled data to discover underlying structure: grouping similar instances, uncovering latent factors, or constructing low-dimensional representations (Hastie et al. 2009; Bishop 2006).

Clustering is the primary unsupervised learning task. Given observations \(\mathbf{x}_1,\dots,\mathbf{x}_n\in\mathbb{R}^p\), the objective is partitioning them into clusters \(C_1,\dots,C_k\) such that within-cluster similarity is maximized relative to between-cluster separation (Aggarwal and Reddy 2013).

1 The Clustering Problem

Let \(\mathcal{D}=\{\mathbf{x}_1,\dots,\mathbf{x}_n\}\) denote \(n\) instances in \(\mathbb{R}^p\). A \(k\)-cluster assignment is defined by mapping:

\[ \ell:\{1,\dots,n\}\to\{1,\dots,k\}, \]

where cluster \(C_j\) contains instances assigned to label \(j\):

\[ C_j=\{\mathbf{x}_i\mid \ell(i)=j\}. \]

2 Distance and Similarity Measures

Definition. Metric Function Properties: 1. \(d(\mathbf{x},\mathbf{y})\geq 0\) and \(d(\mathbf{x},\mathbf{y})=0\Leftrightarrow\mathbf{x}=\mathbf{y}\) (positive definiteness), 2. \(d(\mathbf{x},\mathbf{y})=d(\mathbf{y},\mathbf{x})\) (symmetry), 3. \(d(\mathbf{x},\mathbf{z})\leq d(\mathbf{x},\mathbf{y})+d(\mathbf{y},\mathbf{z})\) (triangle inequality).

2.1 Minkowski Distance Family

Definition. Minkowski Distance of order \(p\ge 1\): \[ d_p(\mathbf{x},\mathbf{y}) = \left(\sum_{j=1}^{d}|x_j-y_j|^p\right)^{1/p}. \tag{1}\]

• \(p=1\): Manhattan (\(L^1\)) distance.
• \(p=2\): Euclidean (\(L^2\)) distance.
• \(p\to\infty\): Chebyshev (\(L^\infty\)) distance.

import numpy as np
from sklearn.preprocessing import StandardScaler
from sklearn.metrics.pairwise import euclidean_distances

rng = np.random.default_rng(42)
X = rng.normal(loc=[0, 0], scale=[1, 100], size=(50, 2))

X_std = StandardScaler().fit_transform(X)

print("Unscaled mean Euclidean distance:", euclidean_distances(X).mean().round(2))
print("Scaled mean Euclidean distance:", euclidean_distances(X_std).mean().round(2))

Unscaled mean Euclidean distance: 81.02
Scaled mean Euclidean distance: 1.76

Distance Metrics Explorer
Adjust sliders A, B, and Minkowski parameter p

A = (1, 1)

B = (3, -1)

p = 2

3 Internal Evaluation Metrics

3.1 Silhouette Coefficient

Definition. Silhouette Coefficient \(s(i)\): \[ s(i) = \frac{b(i)-a(i)}{\max\{a(i),b(i)\}}. \tag{2}\]

where \(a(i)\) is mean intra-cluster distance, and \(b(i)\) is mean nearest-cluster distance (Rousseeuw 1987).

3.2 Davies-Bouldin Index

Definition. Davies-Bouldin Index: \[ \text{DB} = \frac{1}{K}\sum_{k=1}^{K}\max_{l\neq k}\frac{\bar{d}_k+\bar{d}_l}{d(k,l)}. \tag{3}\]

Lower DB values indicate superior cluster compactness and separation (Davies and Bouldin 1979).

3.3 Calinski-Harabasz Index

Definition. Calinski-Harabasz Index: \[ \text{CH} = \frac{\text{SS}_B/(K-1)}{\text{SS}_W/(n-K)}. \tag{4}\]

Higher CH values denote distinct, dense cluster separations (Caliński and Harabasz 1974).

from sklearn.datasets import make_blobs
from sklearn.cluster import KMeans
from sklearn.metrics import silhouette_score, davies_bouldin_score, calinski_harabasz_score

X, y_true = make_blobs(n_samples=300, centers=4, cluster_std=0.8, random_state=42)

for k in range(2, 6):
    km = KMeans(n_clusters=k, random_state=42, n_init=10)
    labels = km.fit_predict(X)
    s = silhouette_score(X, labels)
    db = davies_bouldin_score(X, labels)
    ch = calinski_harabasz_score(X, labels)
    print(f"k={k} | Silhouette: {s:.3f} | Davies-Bouldin: {db:.3f} | Calinski-Harabasz: {ch:.1f}")

k=2 | Silhouette: 0.603 | Davies-Bouldin: 0.504 | Calinski-Harabasz: 341.9
k=3 | Silhouette: 0.778 | Davies-Bouldin: 0.334 | Calinski-Harabasz: 1381.9
k=4 | Silhouette: 0.834 | Davies-Bouldin: 0.232 | Calinski-Harabasz: 5285.6
k=5 | Silhouette: 0.698 | Davies-Bouldin: 0.625 | Calinski-Harabasz: 4361.4

4 External Evaluation Metrics

4.1 Adjusted Rand Index (ARI)

Definition. Adjusted Rand Index: \[ \text{ARI} = \frac{\text{RI} - \mathbb{E}[\text{RI}]}{\max(\text{RI}) - \mathbb{E}[\text{RI}]}. \tag{5}\]

ARI measures pair agreement against ground-truth partition, adjusted for chance (Hubert and Arabie 1985).

5 Summary

Unsupervised clustering organizes unlabeled data using geometric or probabilistic distance metrics. Internal evaluation metrics (Silhouette, Davies-Bouldin, Calinski-Harabasz) validate cluster quality without ground-truth labels, while external metrics (ARI, NMI) measure agreement against reference partitions.

6 References

Aggarwal, Charu C., and Chandan K. Reddy. 2013. Data Clustering: Algorithms and Applications. CRC Press.

Bishop, Christopher M. 2006. Pattern Recognition and Machine Learning. Information Science and Statistics. Springer.

Caliński, Tadeusz, and Józef Harabasz. 1974. “A Dendrite Method for Cluster Analysis.” Communications in Statistics 3 (1): 1–27.

Davies, David L., and Donald W. Bouldin. 1979. “A Cluster Separation Measure.” IEEE Transactions on Pattern Analysis and Machine Intelligence 1 (2): 224–27.

Hastie, Trevor, Robert Tibshirani, and Jerome Friedman. 2009. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. 2nd ed. Springer Series in Statistics. Springer. https://doi.org/10.1007/978-0-387-84858-7.

Hubert, Lawrence, and Phipps Arabie. 1985. “Comparing Partitions.” Journal of Classification 2 (1): 193–218.

Rousseeuw, Peter J. 1987. “Silhouettes: A Graphical Aid to the Interpretation and Validation of Cluster Analysis.” Journal of Computational and Applied Mathematics 20: 53–65.