3 How cluster evaluation methods work
3.1 What a validation score can measure
Suppose there are \(n\) observations
\[x_1,\ldots,x_n.\]
A clustering assigns each observation to one of \(K\) clusters. Let \(C(i)\) denote the cluster containing observation \(i\). Let
\[d(x_i,x_j)\]
denote the distance between observations \(i\) and \(j\). Different evaluation methods now inspect different properties of the partition. Silhouette and Gap use geometry. Consensus and bootstrap Jaccard use repeated fits. ARI and AMI use only completed label assignments.
3.2 Silhouette
Take observation \(i\). First measure how far it is from the other members of its assigned cluster:
\[a(i) = \frac{1}{|C(i)|-1} \sum_{\substack{j\in C(i)\\j\neq i}} d(x_i,x_j).\]
Here, \(C(i)\) is the current cluster of observation \(i\). The notation \(|C(i)|\) means the number of observations in that cluster, so \(|C(i)|-1\) is the number of other observations. Thus \(a(i)\) is the mean distance from \(i\) to its assigned cluster. A small value means that \(i\) fits tightly among its current neighbours.
Fitting the current cluster is only half of the question. For any other cluster \(C\), define the mean distance from \(i\) to that cluster as
\[d(i,C) = \frac{1}{|C|} \sum_{j\in C}d(x_i,x_j).\]
The most relevant competitor is the closest alternative cluster:
\[b(i) = \min_{C\neq C(i)} d(i,C).\]
The desired relation is now clear:
\[a(i)<b(i).\]
Observation \(i\) should be closer to its assigned group than to its best alternative. The silhouette coefficient puts this comparison on a common scale:
\[s(i) = \frac{b(i)-a(i)}{\max\{a(i),b(i)\}}.\]
The numerator compares the current assignment with the closest alternative. The denominator scales the difference by the larger of the two distances. This produces values from \(-1\) to \(1\).
If \(a(i)\) is much smaller than \(b(i)\), then \(s(i)\) is close to 1. If the two distances are similar, \(s(i)\) is close to 0. If \(a(i)>b(i)\), the coefficient is negative because another cluster is closer on average. For a singleton cluster, \(a(i)\) has no ordinary mean. The original convention and cluster::silhouette assign a silhouette of zero to that observation.
The mean across all observations is
\[\bar{s} = \frac{1}{n} \sum_{i=1}^{n}s(i).\]
Candidate values of \(K\) can be compared through \(\bar{s}\), but the average compresses the clusterwise distribution. The profile remains necessary for identifying weak clusters and negative observations.
3.2.1 A numerical silhouette
Consider an observation \(A=(0,0)\) assigned to a cluster with \(B=(0,2)\) and \(C=(2,0)\). Its Euclidean distances to both cluster mates are 2, so
\[a(A)=\frac{2+2}{2}=2.\]
The only competing cluster contains \(D=(5,0)\) and \(E=(5,2)\). The two distances are
\[d(A,D)=5\]
and
\[d(A,E)=\sqrt{5^2+2^2}=\sqrt{29}\approx 5.385.\]
Therefore
\[b(A)=\frac{5+\sqrt{29}}{2}\approx 5.193.\]
Since \(b(A)>a(A)\), the scaled difference is
\[s(A) = \frac{5.193-2}{5.193} \approx 0.615.\]
This positive value says that \(A\) fits its current cluster better than its nearest alternative. Repeating the calculation for every observation produces the bars in a silhouette plot.
The criterion rewards observations that are internally close and externally separated under the chosen \(d\). It does not establish that the biological system is discrete.
3.3 Gap statistic
Silhouette starts from observation level distances. Gap begins with the total within cluster dispersion. Let a partition contain clusters
\[C_1,\ldots,C_K.\]
Let \(n_r=|C_r|\) be the size of cluster \(r\). One form of within cluster dispersion is
\[W_K = \sum_{r=1}^{K} \frac{1}{2n_r} \sum_{i,j\in C_r} \lVert x_i-x_j\rVert^2.\]
The inner sum includes both ordered pairs \((i,j)\) and \((j,i)\), which explains the factor 2. Dividing by \(n_r\) gives an equivalent centroid based expression.
Let the centroid of cluster \(r\) be
\[\bar{x}_r=\frac{1}{n_r}\sum_{i\in C_r}x_i.\]
Expand the pairwise squared distances:
\[\sum_{i,j\in C_r}\lVert x_i-x_j\rVert^2 = \sum_{i,j\in C_r} \left(\lVert x_i\rVert^2+\lVert x_j\rVert^2-2x_i^\top x_j\right).\]
The first two terms each repeat every squared norm \(n_r\) times. The cross products collect into the squared norm of the sum. After division by \(2n_r\), this becomes
\[\frac{1}{2n_r} \sum_{i,j\in C_r}\lVert x_i-x_j\rVert^2 = \sum_{i\in C_r}\lVert x_i-\bar{x}_r\rVert^2.\]
Pairwise spread and spread around the centroid are therefore two views of the same Euclidean quantity.
The problem is that \(W_K\) usually decreases as \(K\) increases. Gap asks whether that decrease is stronger than one produced by partitioning data with no comparable cluster structure. Generate \(B\) reference datasets. For reference replicate \(b\) at candidate \(K\), calculate \(W^*_{Kb}\). Then define
\[\operatorname{Gap}(K) = \frac{1}{B}\sum_{b=1}^{B}\log W^*_{Kb} - \log W_K.\]
The first term is the average log dispersion under the reference distribution. The second is the observed log dispersion. A large positive difference means the observed clusters are more compact than reference partitions at the same \(K\).
To quantify Monte Carlo uncertainty, first define the mean reference log dispersion
\[\bar{\ell}_K = \frac{1}{B}\sum_{b=1}^{B}\log W^*_{Kb}.\]
Its simulated standard deviation is
\[sd_K = \sqrt{ \frac{1}{B} \sum_{b=1}^{B} \left(\log W^*_{Kb}-\bar{\ell}_K\right)^2 }.\]
The corrected standard error used by the method is
\[s_K=sd_K\sqrt{1+\frac{1}{B}}.\]
The additional factor accounts for uncertainty from using a finite set of reference simulations in addition to the reference variability itself.
The original rule chooses the smallest \(K\) such that
\[\operatorname{Gap}(K) \geq \operatorname{Gap}(K+1)-s_{K+1}.\]
Stop increasing \(K\) when the next candidate is not convincingly better after allowing for its simulation uncertainty.
3.3.1 A numerical Gap table
The following small table uses four candidate values. The column \(\bar{\ell}_K\) is the mean reference log dispersion.
| \(K\) | Observed \(W_K\) | \(\bar{\ell}_K\) | Gap | \(s_K\) |
|---|---|---|---|---|
| 2 | 120 | 5.10 | 0.313 | 0.08 |
| 3 | 65 | 4.70 | 0.526 | 0.07 |
| 4 | 42 | 4.45 | 0.712 | 0.09 |
| 5 | 34 | 4.28 | 0.754 | 0.10 |
At \(K=3\), the left side of the rule is \(0.526\). The right side is \(0.712-0.09=0.622\), so the rule continues. At \(K=4\), the comparison is
\[0.712 \geq 0.754-0.10=0.654.\]
The rule therefore selects \(K=4\), even though the largest displayed Gap occurs at \(K=5\). The extra split is not supported beyond reference uncertainty.
3.4 Consensus clustering
Suppose clustering is repeated over \(H\) resamples. For pair \((i,j)\) in resample \(h\), define a joint presence indicator
\[I_{ij}^{(h)} = \begin{cases} 1 & \text{if }i\text{ and }j\text{ are both present in resample }h,\\ 0 & \text{otherwise.} \end{cases}\]
Define a joint clustering indicator
\[M_{ij}^{(h)} = \begin{cases} 1 & \text{if }i\text{ and }j\text{ are both present and in the same cluster},\\ 0 & \text{otherwise.} \end{cases}\]
The consensus value is
\[C_{ij} = \frac{\sum_{h=1}^{H}M_{ij}^{(h)}} {\sum_{h=1}^{H}I_{ij}^{(h)}}.\]
The denominator is not automatically \(H\). If two samples appear together in 70 of 100 runs and share a cluster in 63 of those joint appearances, then
\[C_{ij}=\frac{63}{70}=0.9,\]
not (63/100). The collection of pairwise values forms the consensus matrix
\[C=[C_{ij}].\]
An idealized stable partition has values near 1 inside its blocks and near 0 between blocks. Intermediate values locate pairwise ambiguity.
3.4.1 PAC counts ambiguous pairs
Let \(u_l\) be a lower ambiguity bound and \(u_u\) an upper ambiguity bound, with \(u_l<u_u\). A common descriptive choice is
\[u_l=0.1,\qquad u_u=0.9.\]
For all off diagonal pairs, PAC is
\[\operatorname{PAC} = \frac{ \sum_{i<j} \mathbf{1}\left(u_l<C_{ij}<u_u\right) }{\binom{n}{2}}.\]
The indicator is 1 when a pair falls strictly inside the ambiguous interval and 0 otherwise. Consensus near 0 is unambiguous separation. Consensus near 1 is unambiguous co-clustering. Lower PAC therefore means fewer ambiguous pairs. If some pairwise consensus values are unavailable, the denominator must be the number of evaluated pairs rather than all \(\binom{n}{2}\) pairs.
For ten consensus values
\[0.02,0.05,0.10,0.20,0.40,0.50,0.88,0.90,0.96,0.99,\]
four lie strictly between 0.1 and 0.9. Thus PAC is (4/10=0.4). Changing the bounds changes this value.
3.4.2 The consensus CDF
For one candidate \(K\), let \(m\) denote the number of available off diagonal consensus values and let \(c_1,\ldots,c_m\) denote those values. The empirical cumulative distribution function at value \(z\) is
\[F_K(z) = \frac{1}{m}\sum_{q=1}^{m}\mathbf{1}(c_q\leq z).\]
It reports the proportion of pairwise consensus values at or below \(z\). A relatively flat middle region means that few pairs have intermediate consensus. ConsensusClusterPlus also reports area under this CDF and change in area across \(K\). These summaries have historical value, but PAC connects more directly to an explicit ambiguity interval.
Minimizing PAC or obtaining a flat CDF middle does not prove cluster existence. A deterministic rule can repeatedly bisect a unimodal distribution. Consensus measures reproducibility of the fitted partitioning procedure.
3.5 Bootstrap Jaccard stability
Consensus follows pairs. Bootstrap Jaccard stability follows the membership of an original cluster. Let that cluster be \(C_r\). In bootstrap replicate \(b\), suppose reclustering returns
\[B_1^{(b)},\ldots,B_{K_b}^{(b)}.\]
For one candidate bootstrap cluster, define Jaccard similarity as
\[J(C_r,B_s^{(b)}) = \frac{|C_r\cap B_s^{(b)}|}{|C_r\cup B_s^{(b)}|}.\]
The numerator counts shared members. The denominator counts all members appearing in either set. If
\[C_r=\{1,2,3,4\}\]
and
\[B_s^{(b)}=\{2,3,4,5,6\},\]
then the intersection has three members and the union has six, giving
\[J(C_r,B_s^{(b)})=\frac{3}{6}=0.5.\]
Cluster numbers can change between fits. Match the original cluster to whichever bootstrap cluster overlaps most:
\[J_r^{(b)} = \max_s J(C_r,B_s^{(b)}).\]
Average over \(B\) bootstrap replicates:
\[\bar{J}_r = \frac{1}{B}\sum_{b=1}^{B}J_r^{(b)}.\]
The bootstrap cluster named 4 can be the best match for original cluster 1. Membership, not numeric name, determines the match.
Bootstrap sampling uses replacement, so observations may occur more than once and others may be absent. They are not new independent biological units. Implementations must define how duplicates are mapped and how the bootstrap fitted partition is compared with the original. fpc::clusterboot reports the mean Jaccard similarity for each original cluster, counts a cluster as dissolved when similarity falls below the dissolve threshold, and counts it as recovered when similarity exceeds the recover threshold. Report the definitions used by the implementation.
Mean values near 0.75 are often treated as reasonably stable, above about 0.85 as highly stable, and below about 0.6 as concerning. These are heuristic guides. Stability remains conditional on the algorithm and perturbation.
3.6 Adjusted Rand index
Now consider two partitions, \(U\) and \(V\), of the same \(n\) observations. Every pair has four possibilities:
- together in both partitions
- separate in both partitions
- together in \(U\) but separate in \(V\)
- separate in \(U\) but together in \(V\)
The ordinary Rand index is
\[RI = \frac{\text{number of agreeing pairs}}{\binom{n}{2}}.\]
It is useful as a stepping stone, but it includes agreement expected by chance. It can also be dominated by the many pairs separated in both partitions.
Construct a contingency table. Let \(n_{ij}\) be the number of observations in cluster \(i\) under \(U\) and cluster \(j\) under \(V\). Let the row totals be
\[a_i=\sum_j n_{ij}\]
and the column totals be
\[b_j=\sum_i n_{ij}.\]
The number of pairs placed together in both partitions is
\[\sum_{ij}\binom{n_{ij}}{2}.\]
The number of within cluster pairs under \(U\) is
\[\sum_i\binom{a_i}{2},\]
while the corresponding number under \(V\) is
\[\sum_j\binom{b_j}{2}.\]
The chance calculation keeps both sets of cluster sizes fixed. Imagine leaving the row totals \(a_i\) unchanged and randomly assigning the labels from \(V\) while preserving every column total \(b_j\). The memberships change, but neither partition gains or loses a cluster member. This is the generalized hypergeometric model.
There are \(\binom{n}{2}\) possible sample pairs. Partition \(U\) places \(\sum_i\binom{a_i}{2}\) of them together. Partition \(V\) places \(\sum_j\binom{b_j}{2}\) of them together. Under random overlap with fixed cluster sizes, the probability that a pair joined by \(U\) is also joined by \(V\) is
\[ \frac{\sum_j\binom{b_j}{2}}{\binom{n}{2}}. \]
Multiplying this probability by the number of pairs joined by \(U\) gives the expected number joined by both partitions:
\[\text{Expected Index} = \frac{ \left[\sum_i\binom{a_i}{2}\right] \left[\sum_j\binom{b_j}{2}\right] }{\binom{n}{2}}.\]
This expected value is not an arbitrary penalty. It is the overlap produced by random label assignments that retain the observed cluster sizes. Large clusters create many joined pairs by construction, so their chance overlap is larger. Small clusters create fewer such pairs, so their chance overlap is smaller.
The maximum index for these margins is
\[\text{Maximum Index} = \frac{1}{2} \left[ \sum_i\binom{a_i}{2} + \sum_j\binom{b_j}{2} \right].\]
Adjusted Rand index is then
\[ARI = \frac{ \sum_{ij}\binom{n_{ij}}{2}-\text{Expected Index} }{ \text{Maximum Index}-\text{Expected Index} }.\]
The numerator is observed shared pair membership minus the shared pair membership expected by chance. The denominator is the largest attainable index for the margins minus that same chance expectation. This rescales the available improvement above chance to 1. ARI is 1 for identical partitions up to arbitrary cluster names. Values around zero represent chance level agreement under this fixed size model. Negative values mean that the observed partitions share fewer joined pairs than the model expects.
3.6.1 An eight observation ARI
Let
\[U=(A,A,A,B,B,B,C,C)\]
and
\[V=(1,1,1,2,2,3,3,3).\]
Their contingency table is
| \(V=1\) | \(V=2\) | \(V=3\) | Row total | |
|---|---|---|---|---|
| \(U=A\) | 3 | 0 | 0 | 3 |
| \(U=B\) | 0 | 2 | 1 | 3 |
| \(U=C\) | 0 | 0 | 2 | 2 |
| Column total | 3 | 2 | 3 | 8 |
Pairs together in both are
\[\sum_{ij}\binom{n_{ij}}{2} = \binom{3}{2}+\binom{2}{2}+\binom{1}{2}+\binom{2}{2} =3+1+0+1=5.\]
Both sets of marginal within cluster pair counts equal
\[\binom{3}{2}+\binom{3}{2}+\binom{2}{2}=3+3+1=7.\]
Since \(\binom{8}{2}=28\), expected agreement is
\[\frac{7\times 7}{28}=1.75,\]
and the maximum index is
\[\frac{7+7}{2}=7.\]
Therefore
\[ARI=\frac{5-1.75}{7-1.75}=\frac{3.25}{5.25}\approx 0.619.\]
Renaming \(V\) from \((1,2,3)\) to \((red,blue,green)\) leaves every contingency count unchanged, so ARI remains 0.619. It is not 61.9 percent classification accuracy.
3.7 Mutual information and AMI
Mutual information compares two completed partitions by asking how much one label reduces uncertainty about the other. The calculation has three stages. First calculate uncertainty. Then calculate how much uncertainty disappears. Finally place that reduction on a common scale and remove the amount expected by chance.
3.7.1 Begin with the contingency table
Use the same eight observations as in the ARI example. The row partition is \(U\) and the column partition is \(V\).
| \(V=1\) | \(V=2\) | \(V=3\) | Row total | |
|---|---|---|---|---|
| \(U=A\) | 3 | 0 | 0 | 3 |
| \(U=B\) | 0 | 2 | 1 | 3 |
| \(U=C\) | 0 | 0 | 2 | 2 |
| Column total | 3 | 2 | 3 | 8 |
Let \(n_{ij}\) be a cell count, \(a_i\) a row total, \(b_j\) a column total, and \(n\) the total number of observations. Dividing by \(n\) gives the joint and marginal probabilities
\[ p_{ij}=\frac{n_{ij}}{n}, \qquad p_i=\frac{a_i}{n}, \qquad q_j=\frac{b_j}{n}. \]
3.7.2 Step 1: Measure uncertainty with entropy
The surprise associated with an event of probability \(p\) is \(-\log_2(p)\). A rare label is more surprising than a common label. Entropy is the average surprise before the label is observed.
\[ H(U)=-\sum_i p_i\log_2(p_i), \qquad H(V)=-\sum_j q_j\log_2(q_j). \]
Both partitions in the example have cluster proportions \(3/8\), \(3/8\), and \(2/8\). Therefore
\[ \begin{aligned} H(U)=H(V) &=-\left[ \frac{3}{8}\log_2\left(\frac{3}{8}\right) +\frac{3}{8}\log_2\left(\frac{3}{8}\right) +\frac{2}{8}\log_2\left(\frac{2}{8}\right) \right]\\ &\approx 1.561\text{ bits}. \end{aligned} \]
This is the uncertainty about \(V\) before \(U\) is known.
3.7.3 Step 2: Calculate the uncertainty left after learning the other partition
Now suppose the value of \(U\) is revealed.
If \(U=A\), all three observations have \(V=1\). No uncertainty remains. If \(U=C\), both observations have \(V=3\). Again no uncertainty remains. If \(U=B\), two observations have \(V=2\) and one has \(V=3\). The entropy within that row is
\[ H(V\mid U=B) = -\left[ \frac{2}{3}\log_2\left(\frac{2}{3}\right) +\frac{1}{3}\log_2\left(\frac{1}{3}\right) \right] \approx 0.918\text{ bits}. \]
The \(U=B\) row contains three of the eight observations. The average uncertainty remaining after \(U\) is known is therefore
\[ \begin{aligned} H(V\mid U) &=\frac{3}{8}(0)+\frac{3}{8}(0.918)+\frac{2}{8}(0)\\ &\approx 0.344\text{ bits}. \end{aligned} \]
Mutual information is the uncertainty removed by learning \(U\).
\[ \begin{aligned} MI(U,V) &=H(V)-H(V\mid U)\\ &=1.561-0.344\\ &=1.217\text{ bits}. \end{aligned} \]
Thus, knowing \(U\) removes about 1.217 bits of the original 1.561 bits of uncertainty about \(V\). Mutual information is symmetric, so reversing the roles of \(U\) and \(V\) gives the same value.
The equivalent cell formula is
\[ MI(U,V) = \sum_{i,j}p_{ij} \log_2\left(\frac{p_{ij}}{p_iq_j}\right). \]
The product \(p_iq_j\) is the joint probability expected if the two labels are independent. A cell contributes positively when its observed joint probability is larger than this independence value. It contributes negatively when it is smaller. Empty cells contribute zero. Although individual terms can be negative, their sum cannot be negative.
3.7.4 Step 3: Normalize mutual information
Raw mutual information is measured in bits and its scale changes with the entropies of the partitions. A value of one bit can represent all available information in a simple partition but only part of the available information in a more complex partition. A normalizer is needed before values from different comparisons can be interpreted on a common scale.
The arithmetic normalizer is
\[ M(U,V)=\frac{H(U)+H(V)}{2}. \]
Dividing by this reference produces normalized mutual information.
\[ NMI(U,V)=\frac{MI(U,V)}{M(U,V)}. \]
This choice has three useful properties. It treats \(U\) and \(V\) symmetrically. It removes the units. If the partitions are identical, then \(H(U)=H(V)=MI(U,V)\), so
\[ NMI(U,U) = \frac{H(U)}{\{H(U)+H(U)\}/2} =1. \]
For the worked example,
\[ M(U,V)=\frac{1.561+1.561}{2}=1.561, \]
and
\[ NMI(U,V)=\frac{1.217}{1.561}\approx 0.779. \]
Other software may use the minimum, maximum, or geometric mean of the two entropies. The normalization convention must therefore be reported. Normalization solves the scale problem. It does not solve the chance agreement problem.
3.7.5 Step 4: Find the information expected by chance
Unrelated partitions can have positive mutual information in a finite sample. This becomes especially important when there are many clusters because small accidental overlaps are easier to create.
The chance model keeps the cluster sizes fixed. Hold the labels of \(U\) in place and randomly shuffle the labels of \(V\). Every shuffle still has row sizes \(3,3,2\) and column sizes \(3,2,3\), but the cells of the table change.
For one cell, let the row contain \(a_i\) observations and the column contain \(b_j\) observations. Under random shuffling, the cell count \(N_{ij}\) follows a hypergeometric distribution.
\[ P(N_{ij}=k) = \frac{ \binom{a_i}{k}\binom{n-a_i}{b_j-k} }{ \binom{n}{b_j} }. \]
The first combination chooses the \(k\) observations shared by the row and column. The second chooses the remaining \(b_j-k\) column members from outside the row. The denominator counts every possible column of size \(b_j\).
For every cell, multiply each possible count by its probability and by its contribution to mutual information. Summing those quantities gives
\[ E[MI] = \sum_{i,j} \sum_k P(N_{ij}=k) \frac{k}{n} \log_2\left(\frac{nk}{a_i b_j}\right). \]
The possible values of \(k\) run from \(\max(1,a_i+b_j-n)\) to \(\min(a_i,b_j)\). A count of zero can be omitted because it contributes zero. This exact calculation has the same interpretation as averaging MI across every possible shuffle, but it does not require simulation.
For the margins in this example,
\[ E[MI]\approx 0.549\text{ bits}. \]
this is the amount of information that the fixed cluster sizes produce on average under random label alignment.
3.7.6 Step 5: Derive adjusted mutual information
First subtract the chance expectation from the observed information.
\[ \text{information beyond chance}=MI-E[MI]. \]
Then subtract the same expectation from the normalization reference.
\[ \text{available information beyond chance}=M-E[MI]. \]
Dividing the first quantity by the second gives adjusted mutual information.
\[ AMI(U,V) = \frac{MI(U,V)-E[MI]} {M(U,V)-E[MI]}. \]
For the worked example,
\[ \begin{aligned} AMI(U,V) &=\frac{1.217-0.549}{1.561-0.549}\\ &=\frac{0.668}{1.012}\\ &\approx 0.660. \end{aligned} \]
The numerator says that the observed partitions share 0.668 bits more information than expected by chance. The denominator says that 1.012 bits are available above that chance baseline under the arithmetic normalization. AMI reports the fraction of that available improvement that was achieved.
The transformation explains the main reference values. Identical partitions have AMI equal to 1. Chance level agreement has AMI near 0 because \(MI\approx E[MI]\). AMI can be negative when the observed mutual information is smaller than its chance expectation.
AMI is not the percentage of labels that match, and it does not use distances between observations. It compares only the two completed label assignments. It is generally more suitable than NMI when the candidate partitions contain different numbers of clusters because it removes the information expected from their cluster size structures.
3.8 Validation categories
| Method | Main question | Uses distances | Needs true or reference labels | Uses resampling | Can help select \(K\) | Main limitation |
|---|---|---|---|---|---|---|
| Silhouette | Are samples close to their assigned group and far from the nearest alternative? | Yes | No | No | Yes | Inherits representation, distance, and compactness preference |
| Gap statistic | Is compactness stronger than in reference data? | Usually | No | Reference simulation | Yes | Depends on dispersion and reference distribution |
| Consensus and PAC | Do pairwise assignments recur under subsampling? | Indirectly | No | Yes | Yes | Stable chance partitions can occur |
| Bootstrap Jaccard | Does each cluster’s membership recur? | Indirectly | No | Yes | Sometimes | Conditional on perturbation and matching convention |
| ARI | Do two hard partitions agree in pair status beyond chance? | No | A second partition | No | No | Does not explain geometry or biological meaning |
| NMI | How much normalized information do two partitions share? | No | A second partition | No | No | Normalization varies and chance is not removed |
| AMI | How much information do two partitions share beyond chance? | No | A second partition | No | No | Depends on the chance model and hard labels |
3.8.1 Avoiding label leakage
If known labels are repeatedly used to choose preprocessing, \(K\), resolution, and algorithm, they are no longer independent external validation. The simulated and NCI60 workflows first use silhouette, Gap, consensus, PAC, and bootstrap stability. Labels are revealed only after a shortlist has been selected. A separate cohort is preferable when external evaluation will influence further tuning.
3.9 Other measures you may encounter
The elbow method plots within cluster sum of squares against \(K\) and looks for a bend where additional groups give diminishing improvement. It is easy to display but the bend can be subjective. Gap makes the comparison explicit through reference data.
The Calinski-Harabasz index compares between cluster dispersion with within cluster dispersion. Larger values favour separated, compact groups. The Davies-Bouldin index compares each cluster’s spread with its most similar competitor, with smaller values preferred. The Dunn index uses a ratio of minimum between cluster separation to maximum within cluster diameter. It can be sensitive to extremes.
The Fowlkes-Mallows index compares two partitions through pairwise precision and recall without the same chance correction as ARI. Variation of information is an information theoretic distance between partitions and is closely related to entropy and mutual information.