Cluster Validation with Silhouette

Let a dataset be partitioned into clusters $C_1, \dots, C_k$ by any clustering algorithm — K-Means Clustering, hierarchical clustering, DBSCAN, or otherwise. Fix a point $i$ belonging to cluster $C_i$ (overloading notation: $C_i$ denotes the cluster containing point $i$). Define two quantities. The intra-cluster distance $a(i)$ is the mean distance from $i$ to every other point in its own cluster:

This measures cohesion: small $a(i)$ means $i$ sits comfortably among its cluster-mates. If $|C_i| = 1$ (a singleton cluster), $a(i)$ is undefined and by convention $s(i) = 0$. The nearest-cluster distance $b(i)$ is the smallest, over all other clusters $C_k \neq C_i$, of the mean distance from $i$ to the points of $C_k$:

This measures separation: $b(i)$ is the distance to $i$'s "next-best" cluster — the one it would most plausibly be reassigned to if it were not in $C_i$. Note that $b(i)$ only looks at the single closest rival cluster, not an average over all other clusters — this is deliberate, since a point's real competitor is whichever neighboring cluster it is most likely to be confused with. The silhouette coefficient for point $i$ is then

The numerator $b(i) - a(i)$ is positive exactly when the point is, on average, closer to its own cluster than to its nearest rival — the intuitive definition of "correctly clustered." The denominator normalizes the score into $[-1, 1]$ regardless of the underlying distance scale, which is what makes silhouette comparable across datasets, feature scalings, and values of $k$. The mean silhouette coefficient over all $n$ points,

is used as a single scalar for comparing entire clusterings, e.g. choosing $k$ by maximizing $\bar{s}$ over a grid of candidate values.

Computing silhouette scores requires only pairwise distances and cluster labels — it is a post-hoc validation metric, applied after any clustering algorithm has produced an assignment. The procedure below computes $s(i)$ for every point, then aggregates. ``` ALGORITHM SilhouetteScores(X, labels, dist) Input: X[1..n] — data points labels[1..n] — cluster assignment for each point, values in {1..k} dist(x, y) — distance function (e.g. Euclidean) Output: s[1..n] — silhouette score per point

# Step 1: group point indices by cluster clusters <- empty map from cluster-id to list of indices for i in 1..n: clusters[labels[i]].append(i)

# Step 2: precompute all pairwise distances (or reuse from clustering step) D <- n x n matrix where D[i][j] = dist(X[i], X[j])

# Step 3: compute a(i) and b(i) for every point for i in 1..n: own <- clusters[labels[i]] if size(own) == 1: s[i] <- 0 # singleton cluster: undefined cohesion, define as 0 continue

# cohesion: mean distance to all OTHER points in own cluster a_i <- (sum of D[i][j] for j in own, j != i) / (size(own) - 1)

# separation: for every other cluster, mean distance to its points;

# b(i) is the minimum over those cluster-means b_i <- +infinity for each cluster c != labels[i]: members <- clusters[c] mean_dist <- (sum of D[i][j] for j in members) / size(members) b_i <- min(b_i, mean_dist) s[i] <- (b_i - a_i) / max(a_i, b_i) return s ALGORITHM MeanSilhouette(s) return sum(s) / length(s) ``` To choose $k$, wrap this in an outer loop over candidate values: ``` ALGORITHM ChooseKBySilhouette(X, dist, k_min, k_max, cluster_fn) best_k <- null best_score <- -infinity for k in k_min..k_max: # note: k >= 2 required, s(i) undefined for k=1 labels <- cluster_fn(X, k) # e.g. run k-means with this k s <- SilhouetteScores(X, labels, dist) score <- MeanSilhouette(s) if score > best_score: best_score <- score best_k <- k return best_k, best_score ``` A crucial practical step, often visualized rather than computed as a single number, is the silhouette plot: within each cluster, sort points by $s(i)$ descending and draw a horizontal bar chart. This reveals not just the average but the distribution — a cluster with many negative bars is a red flag even if the global average $\bar s$ looks acceptable.

Time complexity. Computing all pairwise distances costs $O(n^2 d)$ for $n$ points in $d$ dimensions (or $O(n^2)$ if a precomputed distance matrix from the clustering step is reused). Given the distance matrix, computing $a(i)$ and $b(i)$ for a single point requires summing over all $n$ points (partitioned by cluster), so computing scores for all $n$ points costs $O(n^2)$ total — each pairwise distance $D[i][j]$ is touched a constant number of times across the accumulation. Hence the overall cost is

dominated by the pairwise distance computation. This is the same asymptotic order as a single iteration of naive $k$-means (which also computes $O(nk d)$ or, for pairwise-distance-based methods, $O(n^2 d)$), so validating a clustering costs no more asymptotically than producing it, though the constant factors matter: silhouette needs the full $n \times n$ distance matrix, not just distances to $k$ centroids, so it is markedly more expensive than a single k-means iteration when $n \gg k$. This quadratic cost is the main practical limitation: for $n$ in the hundreds of thousands, exact silhouette computation becomes infeasible, motivating sampled or approximate variants (e.g. computing silhouette on a random subsample, or using simplified separation measures).

Space complexity. Storing the full distance matrix costs $O(n^2)$, which can dominate memory usage well before it dominates runtime. In memory-constrained settings the matrix is not materialized; instead $a(i)$ and $b(i)$ are accumulated cluster-by-cluster in $O(n d)$ streaming passes at the cost of recomputing distances, trading memory for time.

Correctness / bounds argument. We verify $s(i) \in [-1, 1]$ directly from the formula. Since $a(i), b(i) \geq 0$ (distances are non-negative) and the denominator is $\max\{a(i), b(i)\} \geq 0$:

• If $a(i) < b(i)$ (point closer to its own cluster — the desirable case), then $s(i) = (b(i)-a(i))/b(i) = 1 - a(i)/b(i)$. Since $0 \le a(i) < b(i)$, this ratio $a(i)/b(i) \in [0,1)$, so $s(i) \in (0, 1]$.
• If $a(i) > b(i)$ (point closer to a foreign cluster — likely misassigned), then $s(i) = (b(i)-a(i))/a(i) = b(i)/a(i) - 1 \in (-1, 0)$ by the symmetric argument.
• If $a(i) = b(i)$, $s(i) = 0$: the point is exactly on the boundary between two clusters, equally well-explained by either.

This confirms the promised interpretation: $s(i)$ near $+1$ signals strong, unambiguous cluster membership ($a(i) \ll b(i)$); $s(i)$ near $0$ signals a borderline point sitting between two clusters; $s(i) < 0$ signals a point that is, on average, closer to a different cluster than to its own — strong evidence of a genuine misassignment (or an inherently bad choice of $k$).

Why $b(i)$ uses the minimum over other clusters, not the average. If $b(i)$ were instead defined as the mean distance to all other clusters, a point could receive a favorable score simply because it is far from many irrelevant clusters, even though it sits right at the boundary of one specific nearby cluster. Taking the minimum forces the comparison against the single most plausible alternative assignment — the only comparison that actually tests whether the current label is defensible.

Tradeoffs. Silhouette is intrinsic (no ground-truth labels needed), which is its main strength versus supervised cluster-validation metrics like the Adjusted Rand Index, but it also means it can be fooled: any distance-based cohesion/separation score inherits the biases of the chosen metric, and it structurally favors convex, well-separated, roughly spherical clusters — the same geometric assumption that k-means itself makes. Density-based or manifold-shaped clusters (e.g. two interleaving spirals) can be correctly identified by an algorithm like DBSCAN yet receive poor average silhouette, because points near the shared boundary of two curved-but-close clusters are penalized even when the underlying structure is genuine. Silhouette should therefore be read alongside domain knowledge and, where available, the elbow curve — not treated as ground truth on its own.

Consider six 1-D points clustered into two groups by some algorithm:

Use Euclidean distance ($d(x,y) = |x-y|$ on the line). Compute $s(i)$ for $p_3$ and for $p_4$ — the two points nearest the cluster boundary, where silhouette does the most interesting work.

For $p_3$ (value 3, cluster A): Cohesion $a(p_3)$: mean distance to the other two points of A, namely $p_1=1$ and $p_2=2$.

Separation $b(p_3)$: only one other cluster (B) exists, so $b(p_3)$ is the mean distance to all of B $= \{9,10,25\}$:

A strong positive score: $p_3$ is much closer to its own cluster than to B, despite being the "rightmost" point of A.

For $p_4$ (value 9, cluster B): Cohesion $a(p_4)$: mean distance to the other two points of B, $p_5=10$ and $p_6=25$.

Separation $b(p_4)$: mean distance to all of A $= \{1,2,3\}$:

A negative score. This is the interesting case: $p_4=9$ was assigned to cluster B (containing the far outlier $p_6=25$), but $p_4$'s own cluster-mate $p_6$ drags its cohesion measure up so much that $p_4$ ends up, on average, closer to cluster A than to its own cluster. Silhouette correctly flags this as a questionable assignment — the outlier $p_6=25$ is contaminating cluster B's cohesion for every other member. Repeating the computation for all six points and averaging gives the overall $\bar s$; if a rerun with $p_6$ placed in its own cluster (or as a detected outlier) raises $\bar s$ substantially, that is direct quantitative evidence that $k=2$ with this partition is suboptimal, exactly the kind of diagnosis the elbow curve alone cannot deliver.

Silhouette analysis is built into standard machine learning toolkits (`sklearn.metrics.silhouette_score`, `silhouette_samples`, and equivalents in R and MATLAB) and is a default diagnostic step after any clustering job. In customer segmentation pipelines at retail and marketing companies, silhouette scores are used to justify a chosen number of segments before those segments drive targeted campaigns. In bioinformatics, silhouette validates clusters of gene-expression profiles or single-cell RNA-seq clusters before biological interpretation is attached to them. In document and topic clustering, it is used alongside coherence scores to check whether discovered topic clusters are well-separated in embedding space. It also appears as a component metric in automated machine learning (AutoML) pipelines that need to select clustering hyperparameters without human supervision, and in anomaly detection systems where persistently negative silhouette scores flag points worth manual review. Because it requires no ground-truth labels, it remains one of the few validation tools usable in genuinely unsupervised settings, complementing model-based approaches like Gaussian Mixture Models, where cluster "goodness" can instead be assessed via likelihood and information criteria rather than geometric cohesion and separation.

Ask the tutor: How would silhouette scores change if I standardized my features before clustering versus leaving them on raw scales?