Technical Summary: Cluster LOCO: Feature Importance for Interpreting Clusters

Problem Statement

Clustering is a fundamental tool in unsupervised learning used for exploratory analysis, data compression, and scientific discovery across disciplines ranging from social sciences to genomics. However, as datasets grow in size and complexity, the reliability, auditability, and reproducibility of clustering solutions have become significant concerns. A primary challenge is the lack of robust methods to interpret why a specific clustering structure was discovered.

While feature importance is well-established in supervised learning (e.g., via permutation importance or SHAP values), it remains underdeveloped in clustering. Existing approaches generally fall into two categories:

1. Intrinsically interpretable algorithms: These constrain the clustering model itself (e.g., decision tree-based clustering), limiting flexibility and scalability.
2. Post-hoc explanations: These are often tied to specific algorithms (e.g., K-means) or rely on internal validity indices (e.g., silhouette scores) and stability metrics that may not accurately reflect the contribution of features to the generalizability of the solution.

Furthermore, common workflows in fields like single-cell genomics often suffer from "double dipping," where the same data is used to define clusters and then to identify distinguishing features (marker genes), inflating false discovery rates. There is a need for a model-agnostic, post-hoc framework that quantifies feature importance based on how much a feature contributes to the stability and generalizability of the clustering solution itself, rather than just its ability to distinguish groups after the fact.

Methodology: Cluster LOCO

The authors propose Cluster LOCO (Leave-One-Covariate-Out), a family of model-agnostic feature importance scores for clustering. The core intuition is derived from the supervised learning LOCO framework: if removing a feature significantly degrades the ability to generalize the clustering solution to held-out data, that feature is deemed important.

1. Core Concept: Generalizability via Feature Occlusion

Unlike methods that measure changes in internal validity indices (which often rely on geometric assumptions like compactness), Cluster LOCO measures the change in generalizability error.

• Generalizability: Defined as the ability of cluster labels learned on a training subset to be accurately predicted on a held-out calibration subset using a transfer classifier.
• Feature Occlusion: The importance of a feature is quantified by the increase in generalizability error when that feature is removed (occluded) from the dataset.

The framework introduces two primary algorithms:

A. Cluster LOCO-Split

This method relies on a standard data splitting approach:

1. Split: The data $X$ is divided into a training set ($X_{tr}$) and a calibration set ($X_{cal}$).
2. Cluster: A chosen clustering algorithm $C_\theta$ is applied to both sets to obtain labels $z_{tr}$ and $z_{cal}$.
3. Train Transfer Classifiers:
   • A base classifier $\hat{f}_{tr}$ is trained on $(X_{tr}, z_{tr})$.
   • A "without-feature-$j$" classifier $\hat{f}_{-j}^{tr}$ is trained on $(X_{tr, -j}, z_{tr})$.
4. Compute Score: The importance score $\hat{\Delta}_j$ is the difference in prediction error on the calibration set between the model trained without feature $j$ and the model trained with all features:
   $$\hat{\Delta}_j = \text{Error}(z_{cal}, \hat{f}_{-j}^{tr}(X_{cal, -j})) - \text{Error}(z_{cal}, \hat{f}_{tr}(X_{cal}))$$
   The error metric can be the negative Adjusted Rand Index (ARI), Hamming distance, or multi-class hinge loss.

B. Cluster LOCO-MP (Minipatch)

To address the computational limitations and instability of data splitting (especially with unbalanced clusters or high-dimensional data), the authors introduce Cluster LOCO-MP. This method leverages minipatch ensembles:

1. Minipatch Construction: Instead of a single split, the algorithm generates $B$ random minipatches, each subsampling a small number of observations ($n \ll N$) and features ($m \ll M$).
2. Consensus Clustering: Each minipatch is clustered, and labels are aligned to a reference clustering (or via pairwise overlap) to create a consensus label set.
3. Ensemble Prediction:
   • LOO (Leave-One-Out): An ensemble predictor $\hat{H}$ averages predictions from minipatches that exclude the target observation.
   • LOCO-LOO: An ensemble predictor $\hat{H}_{-j}$ averages predictions from minipatches that exclude both the target observation and feature $j$.
4. Score Calculation: The importance score is the difference in error between $\hat{H}_{-j}$ and $\hat{H}$. This approach naturally handles correlated features because different minipatches may include one feature of a correlated pair but not the other, preventing the underestimation of importance common in single-split methods.

C. Cluster LOCO-RAMPART

For high-dimensional applications where identifying the top-$k$ features is the goal, the authors integrate Cluster LOCO-MP with the RAMPART framework. This is an adaptive procedure that iteratively screens features, discarding the bottom half of ranked features at each round, thereby concentrating computational resources on the most promising candidates.

D. Extensions

The framework supports cluster-specific importance scores. By aggregating errors over specific clusters rather than the entire dataset, users can determine which features drive the formation of specific groups (e.g., specific cell types), offering local interpretability alongside global scores.

Key Contributions

1. Model-Agnostic Framework: Cluster LOCO is applicable to any clustering algorithm (e.g., K-means, Spectral Clustering, hierarchical clustering) and does not require retraining the clustering model from scratch in a specific way; it only requires the ability to cluster data and predict labels.
2. Generalizability-Based Metric: It shifts the focus from internal geometric validity to the generalizability of the clustering solution, providing a more robust measure of feature contribution.
3. Scalability: The introduction of Cluster LOCO-MP allows the method to scale to large, high-dimensional datasets through minipatch ensembling, overcoming the computational bottlenecks of traditional leave-one-out approaches.
4. Adaptive Screening: The integration with RAMPART provides an efficient pathway for feature selection in sparse, high-dimensional regimes.

Results

The authors evaluated Cluster LOCO against five baseline methods: Prototype-Based Feature Importance (PBFI), Fuzzy C-Means SHAP, Permutation Feature Importance (PFI), Layer-Wise Relevance Propagation (LRP), and IMPACC.

Synthetic Simulations

• Nonlinear Structures: In a synthetic dataset with interlaced half-circles (nonlinearly separable), standard methods like K-means-based PFI, SHAP, and LRP failed to identify the true signal features, often assigning high importance to noise. Cluster LOCO-Split successfully recovered the correct signal features and their relative importance ordering.
• High-Dimensional Regimes: In simulations with Gaussian mixtures, Gamma mixtures, and interlaced moons/circles with increasing noise dimensions ($p_{noise}$ up to 990), Cluster LOCO-MP and Cluster LOCO-RAMPART consistently outperformed existing methods. They demonstrated robust recovery of the top-10 true signal features even as the number of noise features increased, whereas methods like FCM-SHAP and PFI showed significant performance degradation.

Real-World Application: Single-Cell Transcriptomics

The framework was applied to a Peripheral Blood Mononuclear Cells (PBMC) dataset to identify gene markers for immune cell types.

• Global Importance: Cluster LOCO-MP identified a higher number of biologically validated marker genes (e.g., FTL for monocytes) compared to K-means-based methods (PBFI, PFI), which failed to identify known markers in their top rankings.
• Cluster-Specific Importance: When analyzing specific cell types (CD14+ monocytes, dendritic cells, NK cells, and CD34+ stem cells), Cluster LOCO-MP provided more consistent and biologically interpretable rankings than LRP and standard differential expression analysis (DEG).
• Handling Ambiguity: For difficult-to-cluster populations like CD34+ stem cells, Cluster LOCO-MP successfully ranked known markers (PRSS57, EGFL7, CYTL1) in the top 10, whereas LRP and standard DEG analysis failed to identify these markers, highlighting the method's ability to reflect the underlying clustering structure rather than just post-hoc statistical significance.

Significance and Claims

The paper claims that Cluster LOCO addresses a critical gap in the interpretability of unsupervised learning. By providing a post-hoc, model-agnostic measure of feature importance based on generalizability, it allows practitioners to:

• Audit clustering solutions to understand which features drive the discovered structure.
• Avoid the statistical pitfalls of "double dipping" in downstream analysis (e.g., marker gene discovery).
• Apply feature importance to complex, non-linear, and high-dimensional clustering workflows without being constrained to specific algorithmic assumptions.

The authors position Cluster LOCO not as a replacement for careful model selection, but as a necessary tool for validating and interpreting the results of chosen clustering models, thereby enhancing the reliability and reproducibility of clustering-driven scientific discovery. The method is implemented as an open-source Python library compatible with standard scikit-learn estimators.