Choosing K With Silhouette and Gap Statistics

Why Choosing the Number of Clusters Requires a Comparison

A clustering algorithm can divide a set of genomic profiles into a specified number $K$ of groups, but the resulting partition does not by itself establish that those groups are well separated or meaningful. In K-means, for example, the within-cluster sum of squares cannot increase when $K$ increases: allowing more clusters makes it possible to fit the observed profiles more closely. A measure that only rewards a smaller within-cluster sum of squares would therefore tend to favor unnecessarily large $K$.

The silhouette and gap statistics address different versions of this problem. A silhouette compares each profile’s average dissimilarity within its assigned cluster with its dissimilarity to the nearest alternative cluster. The gap statistic compares observed within-cluster dispersion with dispersion expected under simulated reference data without the cluster structure being sought. Both are ways to compare candidate values of $K$; neither identifies a uniquely correct biological classification.

Silhouette Widths

Definition: For an observation $i$ assigned to a cluster, let $a(i)$ be its average dissimilarity to the other observations in that same cluster. For each other cluster, calculate the average dissimilarity from $i$ to observations in that cluster; let $b(i)$ be the smallest of these averages. The silhouette width of $i$ is $$ s(i)=\frac{b(i)-a(i)}{\max\{a(i),b(i)\}}. $$ For a singleton cluster, a common convention is to set its member’s silhouette to 0. The average silhouette width for a partition is the mean of $s(i)$ over all observations.

This definition applies when the chosen dissimilarity is meaningful for the profiles being compared. It is not restricted to Euclidean distance. When $a(i)$ is much smaller than $b(i)$, observation $i$ is, on average, closer to its own cluster than to its nearest alternative, and its silhouette is near 1. A value near 0 indicates that the two averages are similar. A negative value means $a(i)>b(i)$: the observation is, on average, closer to another cluster than to the cluster to which it was assigned.

The denominator keeps the scale bounded: because $a(i)$ and $b(i)$ are nonnegative, $s(i)$ lies between $-1$ and $1$ whenever the denominator is positive. If both averages are zero, the ratio is undefined; software implementations handle such degenerate cases by convention. The silhouette is undefined for a partition with only one cluster, because there is no alternative cluster from which to calculate $b(i)$.

Worked Example: Calculating a Mean Silhouette

Suppose four hypothetical profiles have one-dimensional measurements 0, 2, 8, and 10, and a candidate partition assigns $\{0,2\}$ to cluster A and $\{8,10\}$ to cluster B. Use absolute difference as the dissimilarity. Each cluster has two observations, so each observation’s $a(i)$ is the distance to its sole cluster-mate.

For the profile at 0, $a(0)=|0-2|=2$. Its average dissimilarity to cluster B is $(|0-8|+|0-10|)/2=(8+10)/2=9$, so $b(0)=9$. Thus $s(0)=(9-2)/9=7/9\approx0.778$.

For the profile at 2, $a(2)=|2-0|=2$, and its average dissimilarity to cluster B is $(|2-8|+|2-10|)/2=(6+8)/2=7$. Thus $s(2)=(7-2)/7=5/7\approx0.714$. By symmetry, the profiles at 8 and 10 have silhouettes approximately 0.714 and 0.778, respectively.

The mean silhouette is $(0.778+0.714+0.714+0.778)/4\approx0.746$. This indicates that the four observations are well separated under this particular dissimilarity and partition. It does not show that two clusters are scientifically correct: it summarizes separation in these measurements under the specified distance.

To select $K$ with this measure, calculate the mean silhouette for each candidate partition and compare the results. A common rule is to favor the $K$ with the largest mean silhouette, while also checking the distribution of individual widths. A high average can conceal a subset of profiles with near-zero or negative widths. Inspecting cluster-specific means and the range or pattern of widths can reveal whether apparent overall separation is driven by only some groups.

The Gap Statistic

The gap statistic uses a reference comparison rather than comparing each profile’s assigned cluster with its nearest alternative. For a candidate $K$, define within-cluster dispersion as

W_K=\sum_{r=1}^{K}\frac{1}{2n_r} \sum_{i,i'\in C_r} d(i,i')^2,

where $C_r$ is cluster $r$, $n_r$ is its number of observations, and $d(i,i')$ is the chosen dissimilarity. The inner sum is over ordered pairs, including the zero-distance self-pairs; the factor $1/(2n_r)$ gives the usual pairwise-dispersion convention. With squared Euclidean distance, $W_K$ equals the sum of squared distances from profiles to their cluster centroids. Smaller $W_K$ means tighter clusters, but—as with the K-means objective—$W_K$ generally decreases as $K$ increases.

Definition: Generate $B$ reference data sets under a specified no-cluster reference model. For each reference data set $b$, apply the same clustering procedure and calculate $W_{K,b}^{*}$. The gap statistic is $$ \operatorname{Gap}(K)=\frac{1}{B}\sum_{b=1}^{B}\log W_{K,b}^{*}-\log W_K. $$ If $\ell_{K,b}^{*}=\log W_{K,b}^{*}$, define $s_K$ as the sample standard deviation of the $B$ values $\ell_{K,b}^{*}$, multiplied by $\sqrt{1+1/B}$. This quantity summarizes reference-simulation variability with an adjustment for estimating the reference mean.

A positive gap means the observed dispersion is smaller than the mean dispersion under the chosen reference model on the log scale. A larger gap is not automatically a reason to choose the largest candidate $K$: the reference dispersions also change with $K$. A widely used rule selects the smallest $K$ satisfying

\operatorname{Gap}(K)\geq \operatorname{Gap}(K+1)-s_{K+1}.

This rule asks whether the increase in the gap at the next cluster count is large enough to exceed its reference-simulation uncertainty. It is a practical stopping rule, not a hypothesis test at a specified significance level and not a guarantee that the selected partition reflects biological subtypes.

Worked Example: Applying the Gap Rule

Suppose a hypothetical analysis of standardized profiles obtains the following observed dispersions and reference means. The reference means shown are averages of $\log W_K^{*}$ over $B$ simulated data sets. All dispersions are positive, and the same preprocessing, distance, and clustering procedure were used for the observed and reference profiles.

$K$	Observed $W_K$	Mean reference $\log W_K^{*}$	$s_K$
1	100	4.800	—
2	40	4.500	0.100
3	25	4.300	0.150
4	18	4.150	0.250

For $K=2$, $\log(40)\approx3.6889$, so $\operatorname{Gap}(2)=4.500-3.6889=0.8111$. For $K=3$, $\log(25)\approx3.2189$, giving $\operatorname{Gap}(3)=4.300-3.2189=1.0811$. For $K=4$, $\log(18)\approx2.8904$, giving $\operatorname{Gap}(4)=4.150-2.8904=1.2596$. For completeness, $\operatorname{Gap}(1)=4.800-\log(100)\approx4.800-4.6052=0.1948$.

At $K=2$, the rule asks whether $0.8111\geq1.0811-0.150=0.9311$, which is false. At $K=3$, it asks whether $1.0811\geq1.2596-0.250=1.0096$, which is true. The rule therefore selects $K=3$, the first candidate meeting the criterion. The increasing gaps alone would not yield this conclusion; the comparison includes the uncertainty adjustment.

Justification and Practical Choices

The gap statistic’s comparison can be understood by rearranging its definition:

\operatorname{Gap}(K) =\log\left(\frac{\exp\left\{\frac{1}{B}\sum_{b=1}^{B}\log W_{K,b}^{*}\right\}}{W_K}\right).

Thus, the gap is the log ratio of the geometric mean reference dispersion to the observed dispersion. If the observed profiles have much smaller dispersion than reference profiles at the same $K$, the ratio is large and the gap is positive. This comparison addresses why a small observed $W_K$ should be considered notable relative to the chosen reference, rather than rewarding its size in isolation.

Specify the analysis.
Choose the profiles, feature transformations or scaling, distance, candidate $K$ values, and clustering procedure. Use these choices consistently for observed and reference data.

Compute the criterion.
For silhouettes, calculate the widths and their mean for each candidate partition. For the gap statistic, calculate $W_K$, simulate reference data, and estimate the mean and variability of reference log-dispersion.

Assess sensitivity and interpret.
Check individual silhouettes or the gap-rule comparisons, then ask whether conclusions are sensitive to reasonable preprocessing, distance, reference-model, or clustering-start choices.

The reference model is a substantive choice. A common approach simulates profiles uniformly within a bounding region of the observed data, sometimes after rotating coordinates to account for their orientation. Other reference choices are possible, but they answer different questions about what “no cluster structure” means. In high-dimensional genomic data, a simple uniform reference can have unrealistic feature dependence, marginal distributions, or sparsity. A gap value should therefore be interpreted relative to the specified reference, not as an absolute measure of biological evidence.

Reading the Results for High-Dimensional Profiles

For genomic profiles, the distance and preprocessing can materially affect both criteria. Features measured on different scales can cause large-scale variables to dominate Euclidean distances; standardization may help, but can also give noisy or low-variance features undue influence. The earlier material on distance concentration is relevant: in many dimensions, distances can become similar in magnitude. If within- and between-cluster distances are nearly indistinguishable, silhouette widths may cluster near zero, making the average a weak discriminator among candidate $K$ values.

A concrete negative silhouette is a useful diagnostic. Suppose a hypothetical profile at 0 is assigned to a cluster containing 6, while another cluster contains only the profile at 2. With absolute difference, $a(0)=6$, $b(0)=2$, and $s(0)=(2-6)/6=-0.667$. This observation is substantially closer on average to the alternative cluster. A few such values can point to questionable assignments, an unsuitable distance, or a structure that is not well represented by the chosen partition. They do not, by themselves, prove that moving the profile is appropriate.

The silhouette and gap statistic are complementary, not interchangeable. The silhouette is based on relative distances for individual observations and can flag poorly placed profiles; the gap statistic summarizes total dispersion relative to simulated data and depends directly on a reference model. If both favor similar $K$, that agreement is useful but not independent confirmation, since both can depend on the same distance and clustering choices. If they disagree, investigate the source rather than averaging the recommendations.

Both measures have limitations. Silhouette means can favor compact, separated groups and may be less informative for non-spherical or uneven-density structure. The gap statistic depends on how the reference data are generated and on the stability of the clustering procedure. For K-means comparisons in particular, local minima can make $W_K$ and derived summaries depend on initialization; use the same careful optimization strategy for observed and reference data and check whether conclusions persist across starts. Neither criterion accounts for whether a cluster has a plausible biological interpretation, and neither should be treated as proof that a particular number of natural populations exists.

Common Mistakes

Choosing the largest gap or the smallest $W_K$. Dispersion usually falls as $K$ rises. Use the stated gap-rule comparison, or compare silhouette means across candidates, rather than assuming that more clusters are better.
Calling a negative silhouette a probability. It is a scaled distance comparison, not the probability that an observation belongs to another cluster.
Treating a positive gap as proof of clusters. It says that observed dispersion is small relative to a particular reference model, not that the reference model is uniquely correct or that the groups are biological entities.
Comparing incompatible analyses. Changing scaling, distance, or optimization between observed and reference data can make the gap comparison uninterpretable. State these choices and apply them consistently.
Relying only on a single average. A respectable mean silhouette can hide poorly separated profiles. Examine individual widths and cluster-specific patterns as well.

Key takeaway: A silhouette compares within-cluster and nearest-alternative dissimilarities for each observation; the gap statistic compares observed dispersion with a simulated reference. Both help choose among candidate $K$ values, but their conclusions are conditional on distance, preprocessing, clustering, and—for the gap statistic—the reference model.

Check Your Understanding

Work through these questions, then compare your reasoning with the solutions.

An observation has $a(i)=3$ and $b(i)=9$. Calculate its silhouette width and interpret it.
Why does a decreasing $W_K$ by itself not justify selecting the largest candidate $K$?
In the worked gap example, does $K=2$ meet the uncertainty-adjusted rule? Show the comparison.
What does a positive gap statistic mean, and what does it not establish?
Why can a simple uniform reference distribution be problematic for high-dimensional genomic profiles?

Solutions. 1. $s(i)=(9-3)/9=6/9\approx0.667$. The observation is, on average, closer to its assigned cluster than to its nearest alternative. 2. Additional clusters can reduce within-cluster dispersion even when they do not provide a useful partition, so the decrease must be judged against a comparison criterion. 3. No: $\operatorname{Gap}(2)=0.8111$, while $\operatorname{Gap}(3)-s_3=1.0811-0.150=0.9311$; since $0.8111<0.9311$, the rule fails at $K=2$. 4. Observed dispersion is smaller on the log scale than the reference mean dispersion at that $K$. It does not prove that clusters are biologically real or that the reference model is appropriate. 5. A uniform reference can fail to reflect feature dependence, marginal distributions, or sparsity, so the gap result may depend strongly on an unrealistic baseline.