📊 statistics

Cluster Analysis with Resampling for Validation and Exploration (CARVE)

The paper introduces CARVE, an open-source Python and R package that addresses the reproducibility crisis in clustering by utilizing resampling-based stability and generalizability diagnostics to outperform traditional geometric validation indices on complex, high-dimensional biomedical data.

Original authors: Kai R. Wycik, Tiffany M. Tang, Tarek M. Zikry, Genevera I. Allen

Published 2026-06-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Kai R. Wycik, Tiffany M. Tang, Tarek M. Zikry, Genevera I. Allen

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to sort a massive pile of mixed-up evidence (like thousands of different types of leaves, or thousands of unique fingerprints) into distinct groups. You want to find the "natural" groups hidden inside the mess. This is what scientists call clustering.

However, there's a big problem: How do you know you sorted them correctly?

If you ask five different experts to sort the same pile of leaves, they might come up with five completely different groupings. One expert might say, "These are all 'Oak' leaves," while another says, "No, these are 'Maple' and 'Birch'." In the world of data science, this is a nightmare. If the results change just because you tweaked a setting or picked a different sorting algorithm, can you trust the discovery?

The Old Way: The "Perfect Sphere" Rule

For a long time, scientists used a set of rules called Clustering Validation Indices (CVIs) to decide which sorting was best. Think of these indices like a rigid checklist that only works if the evidence looks like perfect, round balls.

The Problem: Real-world data (like biological cells or social behaviors) is messy. It's heavy-tailed, non-linear, and irregular. It's not a perfect sphere; it's a squiggly noodle or a jagged rock.
The Result: When you use these old "perfect sphere" rules on messy data, they often fail. They might tell you there are only 2 groups when there are actually 10, or they might invent groups that don't exist. It's like trying to measure a cloud with a ruler; the tool just doesn't fit the shape.

The New Solution: CARVE

The authors of this paper introduce a new tool called CARVE (Cluster Analysis with Resampling for Validation and Exploration).

Instead of asking, "Does this look like a perfect sphere?", CARVE asks, "If we shuffle the deck and deal the cards again, do we get the same groups?"

Here is how CARVE works, using a simple analogy:

1. The "Shuffle and Deal" Test (Resampling)

Imagine you have a deck of cards representing your data.

The Old Way: You look at the whole deck once and make a guess.
The CARVE Way: You shuffle the deck, deal out a small hand, sort those cards, and see what groups you get. Then you shuffle again, deal a different hand, and sort those. You do this hundreds of times.
The Goal: If a group of cards (say, all the Kings) keeps ending up together no matter how you shuffle the deck, that group is Stable. If the Kings keep getting split up randomly, that group is Unstable and probably not real.

2. The "Prediction" Test (Generalizability)

CARVE also checks if the groups make sense for new data.

Imagine you teach a robot to sort the first hand of cards you dealt.
Then, you show the robot a brand new hand it has never seen before.
The Question: Can the robot correctly guess which group the new cards belong to?
If the robot gets it right, the groups are Generalizable. If the robot is confused, the groups might be an accident of that specific shuffle.

Why CARVE is Better

The paper tested CARVE against the old "perfect sphere" rules using two types of tests:

Fake Data (Synthetic Benchmarks): They created computer-generated data with known "true" groups.
- Result: When the data was messy, heavy-tailed, or shaped like a twisted ribbon (non-linear), the old rules failed miserably. CARVE, however, consistently found the correct groups, even when the data was very noisy.
Real Biological Data: They tested CARVE on real scientific data, specifically:
- Mouse Stem Cells: They looked at cells changing over time. The old rules said there were only 2 big groups of cells. CARVE found 4 distinct stages, matching the actual biological timeline of how the cells develop. The old rules missed the middle steps entirely.
- Leukemia Cells: They analyzed blood cells from leukemia patients. The old rules grouped three very different types of immune cells into one big, messy bucket. CARVE correctly separated them into 10 distinct groups, revealing a much clearer picture of the disease.

The Takeaway

CARVE is like a quality control inspector for data sorting.

It doesn't care if your data looks like a perfect ball.
It cares if your groups are reliable (they show up every time you shuffle the data) and useful (they can predict new data).
It gives you a report card not just for the whole pile, but for each specific group and each specific item, telling you which ones are solid and which ones are shaky.

The authors have made this tool available as free software (in both Python and R) so that scientists can stop guessing which sorting method is right and start trusting the groups they find.

Technical Summary: CARVE (Cluster Analysis with Resampling for Validation and Exploration)

Problem Statement

Clustering is a foundational unsupervised learning technique used to partition data into similar groups across diverse scientific fields, including genomics, neuroscience, and social sciences. However, clustering results are notoriously sensitive to methodological choices, including the specific algorithm, preprocessing steps, and the number of clusters ( $k$ ). Small variations in these choices can lead to qualitatively different groupings, resulting in non-reproducible scientific claims.

Current state-of-the-art validation relies heavily on Clustering Validation Indices (CVIs) such as Silhouette, Davies–Bouldin, and Calinski–Harabasz. These indices summarize clustering quality via geometric assumptions (e.g., compactness, spherical shapes, and specific density distributions). The authors argue that these assumptions frequently break down in biomedical research, where data often exhibit heavy-tailed distributions, high dimensionality, and non-linear structures. Consequently, CVIs often fail to identify suitable solutions, leading to systematic over- or under-clustering. Furthermore, existing resampling-based alternatives (focusing on stability and generalizability) are scattered across specialized, non-unified tools, lacking a cohesive software framework for systematic comparison.

Methodology

The paper introduces CARVE (Cluster Analysis with Resampling for Validation and Exploration), a unified framework that evaluates clustering solutions based on stability and generalizability rather than geometric assumptions.

Core Algorithm:
For a user-specified grid of clustering algorithms and hyperparameters (including $k$ ), CARVE performs $B$ resampling iterations:

Subsampling: Two independent subsamples ( $P_1, P_2$ ) of size $\lfloor \rho n \rfloor$ are drawn, along with a held-out test set ( $P_{test}$ ).
Clustering: The candidate clustering method $f(\cdot, \theta)$ is applied to $P_1$ , $P_2$ , and $P_{test}$ .
Stability Metric ( $S^{(b)}$ ): The Adjusted Rand Index (ARI) is computed between the clusterings of $P_1$ and $P_2$ on their intersection. This measures the robustness of the grouping under data perturbation.
Generalizability Metric ( $G^{(b)}$ ): A classifier (default: Random Forest) is trained on $P_1$ using its cluster labels. The classifier predicts labels for $P_{test}$ , and the ARI between these predictions and the actual clustering of $P_{test}$ is computed. This measures whether the structure learned on one subset transfers to held-out data.
Aggregation: Metrics are aggregated across iterations to produce means, standard errors, and confidence intervals. A consensus matrix is also constructed from co-clustering frequencies to derive sample-level and cluster-level diagnostics (e.g., Gini index, cross-entropy, proportion of ambiguous clusters).

Selection Rules:
To select the optimal $k$ and method, CARVE employs three selection rules:

Max Rule: Selects the $k$ maximizing the metric.
1-SE Rule: Selects the largest $k$ whose score lies within one standard error of the maximum (a principle borrowed from supervised learning).
Quantile Rule: Selects the largest $k$ whose score lies within the central 95% of the score distribution observed at the maximizing $k$ .

Multi-Level Diagnostics:
CARVE provides diagnostics at three granularities:

Global: Overall stability and generalizability scores across the dataset.
Cluster: Identification of which specific clusters are stable or ambiguous.
Sample: Identification of individual samples with uncertain membership (dubious samples).

Key Contributions

Unified Framework: CARVE is the first open-source package (available in Python and R) to jointly evaluate multiple clustering algorithms and hyperparameters using both stability and generalizability metrics within a single workflow.
Model-Agnostic Validation: By relying on resampling rather than geometric assumptions, CARVE is robust to non-spherical, heavy-tailed, and high-dimensional data common in genomics.
Principled Selection: The paper proposes and validates the use of the 1-SE rule applied to stability metrics as a default selection strategy, which often outperforms simple maximization or CVI-based selection.
Software Implementation: CARVE offers a scikit-learn-compatible Python API and an R interface compatible with Seurat and SingleCellExperiment workflows, facilitating integration into existing pipelines.

Results

The authors evaluated CARVE on six synthetic benchmarks and two real-world biomedical case studies.

Synthetic Benchmarks:
Across isotropic Gaussian mixtures, heavy-tailed $t$ -mixtures, mixtures with nuisance features, and non-linear manifolds (Swiss rolls, circles, moons), CARVE consistently recovered near-optimal clusterings where classical CVIs degraded significantly.

In heavy-tailed and non-linear settings, CVIs (particularly Gap statistic, Calinski–Harabasz, and Davies–Bouldin) often failed to identify the true $k$ or selected solutions with low ARI against ground truth.
CARVE's stability metric with the 1-SE rule was the most consistent performer across all tasks.

Case Studies:

Droplet-based scRNA-seq (Klein et al.): CARVE identified a 4-cluster solution corresponding to four distinct differentiation stages of mouse embryonic stem cells. In contrast, CVIs (Silhouette, CH, DB) selected a 2-cluster solution that collapsed distinct biological stages, missing the continuous transcriptional progression.
Mass Cytometry (Levine et al.): CARVE selected a 10-cluster solution that recovered fine-grained bone-marrow population structures (separating CD4+ T, CD8+ T, and NK cells). CVIs selected a 7-cluster solution that merged these distinct populations. The CARVE-selected solution achieved significantly higher ARI against reported manual labels compared to all CVI-selected solutions.

Significance and Claims

The paper claims that CARVE addresses a critical gap in the reproducibility of unsupervised learning. By moving away from geometric assumptions and toward resampling-based stability and generalizability, CARVE provides a more reliable foundation for scientific discovery in complex biomedical data.

The authors emphasize that while stability is a necessary condition for trustworthy data-driven discoveries, it is not sufficient on its own; generalizability is required to ensure insights extend beyond the specific sample. CARVE's multi-level diagnostics allow researchers to not only select a model but also to identify which specific clusters or samples are robust and which are dubious, thereby preventing the misinterpretation of artifacts as biological signal. The paper concludes that CARVE offers a practical path toward improving the trust and replicability of clustering results in computational biology and beyond.