5  Clustering

Chapter Aim

Clustering is one of the most common exploratory tools in high-dimensional biology. We use it to propose cell types, microbial community states, patient subgroups, gene modules, protein families, and perturbation-response classes. The word “propose” is important. A clustering algorithm assigns labels, but the labels are not automatically biological truth. They are hypotheses produced by a specific representation, distance, algorithm, and tuning parameter.

Chapter 04 described how normalized and transformed data become geometry. Chapter 05 asks what happens when this geometry is turned into groups. The representation may consist of log-normalized counts, variance-stabilized values, CLR-transformed compositions, residuals, PCA scores, or another deliberately chosen scale. Clustering is then applied to this representation, to a distance matrix \(D\in\mathbb{R}^{n\times n}\), or to a graph \(A\in\mathbb{R}^{n\times n}\) whose nodes are observations.

TipNotation convention

Notation follows the shared convention in the notation chapter. Vectors are columns by default, row vectors are written with transposes, and dimensions should be checked whenever matrices are multiplied, transformed, modeled, or decomposed.

NoteMain external reference

The main book reference is MSMB Clustering, which covers hierarchical clustering, \(k\)-means, \(k\)-medoids, density-based clustering, cluster validation, and bootstrap ideas. For the preprocessing and geometry that feed clustering, see MSMB Multivariate Analysis and MSMB Heterogeneous Data. Exercise Sheet 04 is the main practical companion for this chapter: it works through hierarchical clustering, heatmaps, HMP microbiome clustering, WSS, the gap statistic, shared-nearest-neighbor graphs, Louvain clustering, resolution parameters, UMAP, and t-SNE (Exercise Sheet 04 2026).

Learning Goals

After this chapter, students should be able to describe a clustering result as a function of preprocessing, distance, algorithm, and tuning choices; distinguish centroid-based, medoid-based, hierarchical, density-based, model-based, and graph-based clustering; write down the objective optimized by \(k\)-means and the linkage rules used in hierarchical clustering; explain WSS, silhouette, gap statistic, and stability as cluster validation tools; and interpret single-cell graph clustering as community detection on a nearest-neighbor graph rather than as direct clustering of raw counts.

5.1 What A Clustering Algorithm Returns

At the most basic level, clustering assigns each observation to one of \(K\) groups. We write the estimated cluster label for observation \(i\) as

\[\begin{equation} \hat{\eta}_i\in\{1,\ldots,K\}, \qquad i=1,\ldots,n. \label{eq:ch05-cluster-label} \end{equation}\]

The vector \(\hat{\eta}=(\hat{\eta}_1,\ldots,\hat{\eta}_n)^\top\) defines the estimated partition. The set of observations assigned to cluster \(k\) is

\[\begin{equation} \widehat{G}_k = \{i:\hat{\eta}_i=k\}, \qquad k=1,\ldots,K. \label{eq:ch05-cluster-set} \end{equation}\]

This notation deliberately uses \(\hat{\eta}_i\) rather than \(L_i\). In this lecture script, \(L_i\) is reserved for latent mixture-component labels when we write down generative models. The hat on \(\hat{\eta}_i\) reminds us that algorithmic cluster labels are estimated from the data and may change when preprocessing, feature selection, distance, random seed, or resolution changes.

The clustering workflow can be summarized as

\[\begin{equation} C \longrightarrow X \longrightarrow (D\ \text{or}\ A) \longrightarrow \hat{\eta}. \label{eq:ch05-clustering-workflow} \end{equation}\]

This is the same chain as Chapter 04 with one additional step. A clustering result is therefore not only a property of the biological system. It is a property of the full workflow.

5.2 Choosing The Object To Cluster

Clustering rows of \(X\) groups observations: cells, samples, patients, tissues, perturbations, or time points. Clustering columns of \(X\) groups features: genes, taxa, proteins, peaks, or metabolites. These are different scientific questions. Observation clustering uses an observation distance matrix

\[\begin{equation} D=(d_{ii'})_{i,i'=1}^n, \qquad d_{ii'}=d(x_i,x_{i'}), \label{eq:ch05-observation-distance} \end{equation}\]

whereas feature clustering uses

\[\begin{equation} D_f=(d^f_{jj'})_{j,j'=1}^p, \qquad d^f_{jj'}=d_f(x_{\cdot j},x_{\cdot j'}). \label{eq:ch05-feature-distance} \end{equation}\]

Heatmaps often cluster both rows and columns. This is visually useful, but it combines two different clustering problems. Rows may be clustered with a sample distance, while columns may be clustered with correlation, Euclidean distance on standardized expression, or another feature-wise dissimilarity. The dendrograms should therefore be interpreted as ordering devices unless the clustering choices have been justified biologically.

For transformed continuous data, Euclidean or correlation-based distances are common. For compositional microbiome data, Aitchison distance after CLR transformation is often more principled. For binary presence-absence or mutation data, Hamming or Jaccard distances may be more appropriate. Chapter 04 gave the formulas; Chapter 05 uses them as inputs.

5.3 Centroid-Based Clustering: k-Means

The most familiar clustering method is \(k\)-means. It assumes that the observations can be represented by \(K\) centroids in Euclidean space. For a proposed partition, the centroid of cluster \(k\) is

\[\begin{equation} \hat{\mu}_k = \frac{1}{|\widehat{G}_k|} \sum_{i\in\widehat{G}_k}x_i \in\mathbb{R}^{p}. \label{eq:ch05-cluster-centroid} \end{equation}\]

The within-cluster sum of squares for \(K\) clusters is

\[\begin{equation} W_K = \sum_{k=1}^{K} \sum_{i\in\widehat{G}_k} \|x_i-\hat{\mu}_k\|_2^2. \label{eq:ch05-wss} \end{equation}\]

\(k\)-means chooses cluster labels and centroids to minimize this quantity:

\[\begin{equation} (\hat{\eta},\hat{\mu}_1,\ldots,\hat{\mu}_K) = \underset{\eta,\mu_1,\ldots,\mu_K}{\operatorname{argmin}} \sum_{i=1}^{n} \|x_i-\mu_{\eta_i}\|_2^2. \label{eq:ch05-kmeans-objective} \end{equation}\]

Given centroids, each observation is assigned to the nearest centroid:

\[\begin{equation} \hat{\eta}_i = \underset{k\in\{1,\ldots,K\}}{\operatorname{argmin}} \ \|x_i-\hat{\mu}_k\|_2^2. \label{eq:ch05-kmeans-assignment} \end{equation}\]

Given labels, each centroid is updated by taking the mean in Equation \(\ref{eq:ch05-cluster-centroid}\). Alternating these two steps decreases the objective until convergence to a local optimum.

The assumptions hidden inside \(k\)-means are strong. It uses Euclidean squared distance, represents each cluster by a mean, favors roughly spherical clusters of comparable variance, and requires \(K\) to be chosen in advance. These assumptions can be reasonable for transformed continuous data in a low-dimensional representation, such as selected PCA scores. They are usually not appropriate for raw sequencing counts, sparse compositional data, or highly elongated trajectories.

5.4 Medoids And Robust Representatives

A centroid need not be an observed data point. In some settings, especially when the distance is not Euclidean or outliers are influential, it is preferable to represent each cluster by a medoid: an actual observation whose average dissimilarity to the other observations in its cluster is small. For cluster \(\widehat{G}_k\), the medoid is

\[\begin{equation} \hat{m}_k = \underset{i\in\widehat{G}_k}{\operatorname{argmin}} \sum_{i'\in\widehat{G}_k} d_{ii'}. \label{eq:ch05-medoid} \end{equation}\]

The \(K\)-medoids objective can be written as

\[\begin{equation} (\hat{\eta},\hat{m}_1,\ldots,\hat{m}_K) = \underset{\eta,m_1,\ldots,m_K}{\operatorname{argmin}} \sum_{i=1}^{n} d_{i,m_{\eta_i}}. \label{eq:ch05-kmedoids-objective} \end{equation}\]

Here \(m_k\) indexes an observed row rather than an arbitrary point in \(\mathbb{R}^p\). This makes medoid methods compatible with many dissimilarities, including ecological dissimilarities, and gives each cluster a real representative observation. The \(k\)-medoids and PAM alternatives to \(k\)-means are useful when a distance matrix is the natural input (see MSMB Clustering).

5.5 Hierarchical Clustering

Hierarchical clustering does not require choosing \(K\) before fitting. Agglomerative hierarchical clustering starts with each observation as its own cluster and repeatedly merges the two closest clusters. The initial partition is

\[\begin{equation} \mathcal{P}^{(0)} = \{\{1\},\{2\},\ldots,\{n\}\}. \label{eq:ch05-initial-hierarchical-partition} \end{equation}\]

At step \(t\), two clusters \(A\) and \(B\) are merged according to a linkage function \(\delta(A,B)\). The resulting sequence of merges is displayed as a dendrogram. The crucial choice is how to define the distance between sets of observations.

Single linkage uses the smallest pairwise distance:

\[\begin{equation} \delta_{\mathrm{single}}(A,B) = \min_{i\in A,\ i'\in B} d_{ii'}. \label{eq:ch05-single-linkage} \end{equation}\]

Complete linkage uses the largest pairwise distance:

\[\begin{equation} \delta_{\mathrm{complete}}(A,B) = \max_{i\in A,\ i'\in B} d_{ii'}. \label{eq:ch05-complete-linkage} \end{equation}\]

Average linkage uses the mean pairwise distance:

\[\begin{equation} \delta_{\mathrm{average}}(A,B) = \frac{1}{|A||B|} \sum_{i\in A} \sum_{i'\in B} d_{ii'}. \label{eq:ch05-average-linkage} \end{equation}\]

Ward’s linkage is defined for Euclidean data and merges clusters that cause the smallest increase in within-cluster sum of squares. If \(\bar{x}_A\) and \(\bar{x}_B\) are the centroids of clusters \(A\) and \(B\), the increase caused by merging them is

\[\begin{equation} \Delta_{\mathrm{Ward}}(A,B) = \frac{|A||B|}{|A|+|B|} \|\bar{x}_A-\bar{x}_B\|_2^2. \label{eq:ch05-ward-linkage} \end{equation}\]

These linkage choices can produce visibly different dendrograms from the same distance matrix. Single linkage can create chains because one close pair is enough to merge two groups. Complete linkage favors compact clusters because all cross-cluster distances must be small. Average linkage is a compromise. Ward’s method is tied to Euclidean variance and is often useful for heatmaps of transformed continuous data.

To obtain a flat clustering from a dendrogram, one cuts the tree at a height \(h\):

\[\begin{equation} \hat{\eta}^{(h)} = \operatorname{cut}\left(\mathcal{T},h\right), \label{eq:ch05-tree-cut-height} \end{equation}\]

or chooses a desired number of clusters:

\[\begin{equation} \hat{\eta}^{(K)} = \operatorname{cut}\left(\mathcal{T},K\right). \label{eq:ch05-tree-cut-k} \end{equation}\]

Exercise Sheet 04 begins with this exact sensitivity: the same species distance matrix gives different dendrograms under single, complete, and average linkage (Exercise Sheet 04 2026). The exercise then uses hierarchical clustering and heatmaps for microbiome data, emphasizing that the clustering result depends on preprocessing, distance, linkage, and annotation.

5.6 Heatmaps As Clustered Views

A heatmap is a visualization of a matrix after rows and columns have been ordered. Let \(R\) be a permutation matrix that orders observations, and let \(Q\) be a permutation matrix that orders features. The displayed matrix is

\[\begin{equation} X_{\mathrm{heatmap}} = R X Q^\top. \label{eq:ch05-heatmap-permutation} \end{equation}\]

When rows and columns are clustered independently, \(R\) is obtained from a row dendrogram and \(Q\) from a feature dendrogram. The colors in a heatmap can reveal blocks, gradients, and outliers, but the visual impression depends strongly on scaling. A common feature-wise standardized heatmap uses

\[\begin{equation} z_{ij} = \frac{x_{ij}-\bar{x}_{\cdot j}}{\hat{\sigma}_j}. \label{eq:ch05-heatmap-zscore} \end{equation}\]

This standardization changes the scientific question. It asks which observations are high or low relative to the feature’s own distribution, not which observations have large absolute abundance. For count and compositional data, the transformation from \(C\) to \(X\) should already have been handled before heatmap scaling is applied.

The classic genome-wide expression heatmap of Eisen and colleagues helped establish clustering as a central exploratory tool in genomics (Eisen et al. 1998). The same caution still applies: clustered heatmaps are excellent for seeing structure, but the dendrogram is not a confirmatory model.

5.7 Choosing The Number Of Clusters

Many clustering methods require a choice of \(K\), a tree-cut height, or a graph resolution parameter. This is model selection in an unsupervised setting, which is inherently difficult because there is no observed response variable that defines the correct answer.

For \(k\)-means, \(W_K\) always decreases as \(K\) increases. Indeed, allowing more clusters cannot make the optimal within-cluster sum of squares worse:

\[\begin{equation} W_{K+1} \leq W_K. \label{eq:ch05-wss-monotonicity} \end{equation}\]

The elbow heuristic looks for a value of \(K\) after which the decrease in \(W_K\) becomes small. This is useful as a diagnostic, but it is not a statistical guarantee.

The gap statistic compares the observed within-cluster dispersion to what would be expected under a reference distribution with no obvious cluster structure (Tibshirani et al. 2001). If \(W_K^{*(b)}\) is the within-cluster dispersion for bootstrap reference dataset \(b=1,\ldots,B\), then the estimated gap is

\[\begin{equation} \widehat{\operatorname{Gap}}(K) = \frac{1}{B} \sum_{b=1}^{B} \log W_K^{*(b)} - \log W_K. \label{eq:ch05-gap-statistic} \end{equation}\]

The Monte Carlo standard error is often estimated as

\[\begin{equation} \widehat{\operatorname{SE}}(K) = \left(1+\frac{1}{B}\right)^{1/2} \operatorname{sd}_{b=1,\ldots,B} \left(\log W_K^{*(b)}\right). \label{eq:ch05-gap-standard-error} \end{equation}\]

One common rule chooses the smallest \(K\) such that the gap at \(K\) is within one standard error of the gap at \(K+1\):

\[\begin{equation} \widehat{K} = \min\left\{ K: \widehat{\operatorname{Gap}}(K) \geq \widehat{\operatorname{Gap}}(K+1)-\widehat{\operatorname{SE}}(K+1) \right\}. \label{eq:ch05-gap-selection-rule} \end{equation}\]

Exercise Sheet 04 uses WSS and the gap statistic for the HMP microbiome data (Exercise Sheet 04 2026). The important lesson is that these criteria are aids to judgment. Different criteria can prefer different values of \(K\), especially when the data contain gradients rather than discrete groups.

5.8 Silhouette And Cluster Separation

The silhouette value of an observation compares its average dissimilarity to its own cluster with its average dissimilarity to the nearest other cluster (Rousseeuw 1987). For observation \(i\), let

\[\begin{equation} a_i = \frac{1}{|\widehat{G}_{\hat{\eta}_i}|-1} \sum_{\substack{i'\in\widehat{G}_{\hat{\eta}_i}\\ i'\neq i}} d_{ii'} \label{eq:ch05-silhouette-a} \end{equation}\]

be the average dissimilarity to observations in the same cluster. For another cluster \(k\neq\hat{\eta}_i\), define

\[\begin{equation} b_i(k) = \frac{1}{|\widehat{G}_{k}|} \sum_{i'\in\widehat{G}_{k}} d_{ii'}. \label{eq:ch05-silhouette-bk} \end{equation}\]

The nearest-other-cluster dissimilarity is

\[\begin{equation} b_i = \min_{k\neq\hat{\eta}_i} b_i(k). \label{eq:ch05-silhouette-b} \end{equation}\]

The silhouette value is

\[\begin{equation} s_i = \frac{b_i-a_i}{\max(a_i,b_i)}. \label{eq:ch05-silhouette-value} \end{equation}\]

Values near 1 indicate that observation \(i\) is much closer to its own cluster than to the nearest other cluster. Values near 0 indicate boundary points. Negative values suggest possible misassignment. Average silhouette values can help compare clusterings, but they inherit the chosen distance and can favor compact, well-separated clusters over trajectories or nested biological structure.

5.9 Stability As Validation

Cluster validation should ask whether the result is reproducible under small perturbations of the data or workflow. Stability-based validation makes this idea explicit (Lange et al. 2004). Suppose we draw \(B\) subsamples of the observations, cluster each subsample, and compare whether pairs of observations are repeatedly assigned together. A co-clustering matrix can be written as

\[\begin{equation} \widehat{\Pi}_{ii'} = \frac{ \sum_{b=1}^{B} \mathbf{1}\{i,i'\in S_b\} \mathbf{1}\{\hat{\eta}^{(b)}_i=\hat{\eta}^{(b)}_{i'}\} }{ \sum_{b=1}^{B} \mathbf{1}\{i,i'\in S_b\} }, \label{eq:ch05-coclustering-matrix} \end{equation}\]

where \(S_b\) is the set of observations included in subsample \(b\). If a cluster is stable, pairs of observations inside it should have high co-clustering probabilities across resamples. If the apparent clusters are artifacts of noise, feature selection, or initialization, the co-clustering matrix will be diffuse.

Stability can also be assessed across preprocessing choices: different feature sets, different distance metrics, different numbers of principal components, and different random seeds. In high-dimensional biological data this is often more informative than reporting a single clustering run.

5.10 Density-Based Clustering

Density-based methods define clusters as dense regions separated by lower-density regions. DBSCAN is the classical example (Ester et al. 1996). Given a radius \(\varepsilon>0\), the \(\varepsilon\)-neighborhood of observation \(i\) is

\[\begin{equation} \mathcal{B}_{\varepsilon}(i) = \{i':d_{ii'}\leq \varepsilon\}. \label{eq:ch05-epsilon-neighborhood} \end{equation}\]

Observation \(i\) is a core point if

\[\begin{equation} |\mathcal{B}_{\varepsilon}(i)| \geq M, \label{eq:ch05-dbscan-core-point} \end{equation}\]

where \(M\) is the minimum number of neighbors. Clusters are formed by connecting core points whose neighborhoods overlap, and points not density-reachable from any cluster are treated as noise.

Density-based clustering can find non-spherical clusters and can leave outliers unlabeled. Its parameters are also interpretable: \(\varepsilon\) sets the neighborhood radius, and \(M\) sets the local density threshold. But in high-dimensional biological data, distances can concentrate, densities can vary across cell states, and preprocessing has a large effect. This is why density-based clustering is often applied after dimension reduction or manifold learning rather than directly to raw high-dimensional counts.

5.11 Model-Based Clustering

The mixture models from Chapter 02 give a probabilistic view of clustering. In a finite mixture model, each observation is generated from one of \(K\) components:

\[\begin{equation} p(x_i) = \sum_{k=1}^{K} \pi_k f(x_i;\theta_k), \qquad \pi_k\geq 0, \qquad \sum_{k=1}^{K}\pi_k=1. \label{eq:ch05-mixture-density} \end{equation}\]

The posterior probability that observation \(i\) belongs to component \(k\) is

\[\begin{equation} \tau_{ik} = \Pr(L_i=k\mid x_i) = \frac{ \pi_k f(x_i;\theta_k) }{ \sum_{\ell=1}^{K} \pi_\ell f(x_i;\theta_\ell) }. \label{eq:ch05-mixture-posterior} \end{equation}\]

A hard cluster assignment can then be obtained by maximum posterior probability:

\[\begin{equation} \hat{\eta}_i = \underset{k\in\{1,\ldots,K\}}{\operatorname{argmax}} \ \tau_{ik}. \label{eq:ch05-map-mixture-assignment} \end{equation}\]

This probabilistic notation is useful because it separates latent component membership \(L_i\) from the estimated clustering label \(\hat{\eta}_i\). It also gives uncertainty through the posterior probabilities \(\tau_{ik}\). The limitation is that the model family must be appropriate for the data. A Gaussian mixture on PCA scores and a Dirichlet-multinomial mixture on counts answer different biological and statistical questions.

5.12 Graph-Based Clustering In Single-Cell Workflows

Modern single-cell RNA-seq workflows usually do not cluster raw gene expression vectors directly. A typical workflow normalizes counts, selects variable genes, scales or residualizes features, computes PCA, constructs a nearest-neighbor graph in PCA space, and then runs community detection. Chapter 04 introduced the \(q\)-nearest-neighbor graph

\[\begin{equation} A^{\mathrm{kNN}}_{ii'} = \mathbf{1}\{i'\in\mathcal{N}_q(i)\}. \label{eq:ch05-knn-graph} \end{equation}\]

Many single-cell methods use a shared-nearest-neighbor graph. The shared-neighbor weight between observations \(i\) and \(i'\) can be written as

\[\begin{equation} S_{ii'} = |\mathcal{N}_q(i)\cap\mathcal{N}_q(i')|. \label{eq:ch05-snn-weight} \end{equation}\]

The graph nodes are cells. The weighted edges encode neighborhood similarity in the chosen representation, usually PCA space. Clustering then becomes community detection on this graph.

The Louvain algorithm optimizes modularity or a related community-detection objective (Blondel et al. 2008). For an undirected weighted graph with adjacency \(A\), node degrees \(d_i=\sum_{i'}A_{ii'}\), and total edge weight

\[\begin{equation} m = \frac{1}{2}\sum_{i=1}^{n}\sum_{i'=1}^{n}A_{ii'}, \label{eq:ch05-total-edge-weight} \end{equation}\]

a resolution-parameterized modularity objective is

\[\begin{equation} Q_{\gamma}(\eta) = \frac{1}{2m} \sum_{i=1}^{n} \sum_{i'=1}^{n} \left( A_{ii'} - \gamma \frac{d_i d_{i'}}{2m} \right) \mathbf{1}\{\eta_i=\eta_{i'}\}. \label{eq:ch05-modularity-objective} \end{equation}\]

The parameter \(\gamma>0\) controls resolution. Larger \(\gamma\) generally favors more, smaller communities; smaller \(\gamma\) favors fewer, larger communities. This is why a single-cell clustering result should always report the resolution parameter, the number of PCs used, the number of neighbors, and the graph construction method.

Leiden clustering modifies Louvain-style community detection to improve connectivity and local optimality guarantees (Traag et al. 2019). In practice, Leiden and Louvain often produce similar-looking single-cell annotations at broad resolution, but Leiden is preferred in many modern Python workflows because it avoids some disconnected-community pathologies of Louvain.

Some software uses the Constant Potts Model (CPM) objective. If \(e_k\) is the total weight of edges inside cluster \(k\) and \(n_k=|\widehat{G}_k|\), a simplified CPM objective is

\[\begin{equation} H_{\mathrm{CPM}}(\eta) = \sum_{k=1}^{K} \left[ e_k - \gamma \frac{n_k(n_k-1)}{2} \right]. \label{eq:ch05-cpm-objective} \end{equation}\]

Again, \(\gamma\) is a resolution parameter. The exact objective depends on software and graph construction, but the interpretive point is stable: single-cell clusters are communities in a constructed graph, and the graph is downstream of preprocessing and dimension reduction.

Exercise Sheet 04 makes this concrete by constructing an SNN graph, running Louvain clustering, and varying the resolution parameter in a Seurat workflow (Exercise Sheet 04 2026). The resulting clusters should be annotated using marker genes, metadata, batch information, and biological knowledge rather than accepted solely from the algorithm.

5.13 What To Report

A clustering result is only interpretable if the workflow is reported. At minimum, one should state what matrix was clustered, how features were filtered or selected, what transformation and normalization were used, what distance or graph was used, what algorithm was used, what tuning parameters were chosen, and how the result was validated.

Mathematically, this means that the label vector should be viewed as a function

\[\begin{equation} \hat{\eta} = \mathcal{C}_{\lambda} \left( X,\ d,\ A \right), \label{eq:ch05-clustering-as-function} \end{equation}\]

where \(\mathcal{C}_{\lambda}\) denotes the clustering method and \(\lambda\) collects tuning parameters such as \(K\), linkage, tree-cut height, \(\varepsilon\), \(M\), number of neighbors, number of PCs, random seed, or graph resolution. This notation is intentionally broad. It reminds us that changing \(\lambda\) or changing the representation can change the labels.

Biological validation comes after algorithmic clustering. Marker genes, known cell-type annotations, external phenotypes, perturbations, replicate structure, batch labels, and held-out data should be used to decide whether clusters are meaningful. A cluster that is reproducible but explained by sequencing technology is not a new biological state; it is a technical effect with a stable signature.

Summary

Clustering turns geometry into labels. \(k\)-means minimizes within-cluster squared Euclidean distances and is best understood as centroid-based clustering. \(k\)-medoids uses observed representatives and can work directly with dissimilarity matrices. Hierarchical clustering builds a dendrogram by repeatedly merging clusters according to linkage rules. Heatmaps use clustering as an ordering device for rows and columns. Gap statistic, silhouette, and stability analyses help assess clustering choices, but none of them removes the need for scientific judgment. Density-based methods look for dense regions and can treat some observations as noise. Model-based clustering treats groups as latent mixture components. Graph-based single-cell clustering detects communities in a nearest-neighbor graph built from a chosen representation.

The central message is the same as in Chapter 04: clusters are not discovered in a vacuum. They are produced by a chain from raw counts to transformed matrix, distance or graph, algorithm, tuning parameter, and validation. Good clustering analysis makes that chain explicit.

References

Blondel, Vincent D., Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. 2008. “Fast Unfolding of Communities in Large Networks.” Journal of Statistical Mechanics: Theory and Experiment 2008 (10): P10008. https://doi.org/10.1088/1742-5468/2008/10/p10008.
Eisen, Michael B., Paul T. Spellman, Patrick O. Brown, and David Botstein. 1998. “Cluster Analysis and Display of Genome-Wide Expression Patterns.” Proceedings of the National Academy of Sciences 95 (25): 14863–68. https://doi.org/10.1073/pnas.95.25.14863.
Ester, Martin, Hans-Peter Kriegel, Joerg Sander, and Xiaowei Xu. 1996. “A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise.” Proceedings of the Second International Conference on Knowledge Discovery and Data Mining, 226–31.
Exercise Sheet 04. 2026. Exercise Sheet 04 Solutions: Hierarchical Clustering and Graph-Based Clustering of High-Dimensional Biological Data. https://bio-datascience.github.io/ahbd/assets/exercises/AHDBD_SS26_Exercise04_Solution.html.
Lange, Tilman, Volker Roth, Mikio L. Braun, and Joachim M. Buhmann. 2004. “Stability-Based Validation of Clustering Solutions.” Neural Computation 16 (6): 1299–323. https://doi.org/10.1162/089976604773717621.
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. https://doi.org/10.1016/0377-0427(87)90125-7.
Tibshirani, Robert, Guenther Walther, and Trevor Hastie. 2001. “Estimating the Number of Clusters in a Data Set via the Gap Statistic.” Journal of the Royal Statistical Society Series B: Statistical Methodology 63 (2): 411–23. https://doi.org/10.1111/1467-9868.00293.
Traag, V. A., L. Waltman, and N. J. van Eck. 2019. “From Louvain to Leiden: Guaranteeing Well-Connected Communities.” Scientific Reports 9 (5233). https://doi.org/10.1038/s41598-019-41695-z.