Sparse $K$-spatial-median clustering for high-dimensional data

1. Problem Statement

The paper addresses the challenges of clustering high-dimensional data ($p \gg n$) characterized by two specific difficulties:

1. Heavy-tailed distributions and outliers: Classical methods like K-means rely on the arithmetic mean and squared Euclidean loss, making them highly sensitive to outliers and heavy-tailed noise (e.g., multivariate $t$-distributions).
2. Irrelevant variables: In high-dimensional settings, a large proportion of features often carry no cluster-discriminating information. Including these "noise" variables dilutes the clustering signal, causing performance degradation even in robust methods if they treat all dimensions equally.

Existing sparse clustering methods (e.g., Sparse K-means) often use continuous shrinkage (L1 regularization) to down-weight irrelevant features, which may not yield explicit feature exclusion and can be difficult to tune in robust settings. Furthermore, standard robust methods (like K-medians) often lack rotation equivariance, failing to respect the underlying elliptical geometry of clusters.

2. Methodology

The authors propose a unified framework called Sparse K-spatial-median clustering, which integrates robust center estimation with explicit feature selection. The framework consists of two complementary algorithms:

A. Core Concept: Spatial Median

Instead of the arithmetic mean (K-means) or coordinate-wise medians (K-medians), the method uses the spatial median (geometric median) as the cluster center.

• Definition: The spatial median $m$ minimizes the sum of Euclidean distances: $m = \arg\min \sum \|x_i - m\|_2$.
• Advantage: It is rotation-equivariant (respects multivariate geometry) and robust to heavy tails because the loss function grows linearly rather than quadratically.

B. Algorithm 1: SM–SSCM (Spatial-Median Clustering with Common Spatial-Sign Covariance)

This variant addresses heterogeneous scales and feature dependence without explicit feature exclusion.

• Assignment Step: Instead of standard Euclidean distance, it uses a Mahalanobis-type metric constructed from a common Spatial-Sign Covariance Matrix (SSCM).
• SSCM Estimation: The scatter matrix is estimated using spatial signs ($u_i = r_i / \|r_i\|$) of residuals, regularized with a ridge parameter to ensure invertibility.
• Benefit: This adapts the distance metric to the data's correlation structure and scale, improving assignment accuracy in high dimensions.

C. Algorithm 2: Sparse–SM (Sparse Spatial-Median Clustering)

This variant addresses the $p \gg n$ regime with irrelevant variables by introducing hard-thresholding feature exclusion.

• Separation Score: At each iteration, a score $s_j$ is computed for each feature $j$ based on the dispersion of cluster centers along that coordinate: $s_j = \sum_{k=1}^K |m_{kj} - \bar{m}_j|$.
• Hard Exclusion: Features with scores below a threshold $\tau$ are completely excluded from the assignment step. This creates an explicit set of active variables ($S(\tau)$) rather than shrinking weights continuously.
• Tuning (Gap Criterion): The threshold $\tau$ is selected automatically using a permutation-based Gap statistic. The algorithm compares the observed between-cluster separation against a reference distribution generated by permuting columns (destroying cluster structure while preserving marginal distributions). The $\tau$ maximizing the Gap is selected.

D. Theoretical Properties

The paper establishes clustering consistency and feature-selection consistency for the proposed methods under a mixture elliptical model with sub-Weibull or polynomial tails.

• Consistency: As $n \to \infty$, the algorithm recovers the true partition and the true set of informative features with probability approaching 1, provided the signal separation is sufficiently strong relative to the noise level.
• Robustness: Theoretical bounds show that the spatial median and SSCM metric maintain stability even under heavy-tailed contamination.

3. Key Contributions

1. Robust Framework: Development of a partition-based clustering framework using spatial medians, offering superior robustness to heavy tails and outliers compared to mean-based or coordinate-wise median methods.
2. Explicit Feature Selection: Introduction of a hard-thresholding mechanism that yields interpretable, exact sets of retained and excluded variables, avoiding the ambiguity of continuous shrinkage.
3. Data-Driven Tuning: Proposal of a permutation-based Gap criterion specifically designed for selecting the sparsity threshold in robust, high-dimensional settings.
4. Theoretical Guarantees: Proof of consistency for both the clustering partition and the support recovery (feature selection) under general elliptical models with heavy tails.

4. Experimental Results

The authors evaluated the methods against K-means, K-medians, Sparse K-means, and Sparse K-medians using simulations and real data.

• Simulation Studies:
  • Heavy Tails & Contamination: Under multivariate $t$-distributions and contaminated Gaussian mixtures, Sparse–SM and SM–SSCM significantly outperformed non-robust baselines. Sparse–SM achieved the highest Adjusted Rand Index (ARI) in contaminated settings.
  • High Dimensions: As dimension $p$ increased (up to 400), non-sparse methods deteriorated rapidly. Sparse–SM maintained high stability and accuracy, demonstrating the necessity of feature exclusion.
  • Outlier Types: The method showed particular resilience against cell-wise contamination (corruption of individual entries), where it consistently outperformed competitors.
• Real-Data Applications:
  • Mice Protein Data: On a dataset of protein expression levels, the proposed methods achieved higher ARI and greater stability across runs compared to classical methods.
  • Benchmark Datasets: Tested on 8 UCI/KEEL datasets (e.g., Iris, Wine, WDBC). The proposed methods were competitive or superior, with SM–SSCM excelling in datasets with complex correlations and Sparse–SM performing best where feature sparsity was beneficial.

5. Significance

This paper provides a critical advancement for modern data analysis where datasets are both high-dimensional and prone to outliers.

• Practical Impact: It offers a computationally efficient, iterative algorithm that does not require complex optimization solvers (unlike some penalized likelihood approaches) but provides rigorous feature selection.
• Theoretical Insight: It bridges the gap between robust statistics (spatial signs/medians) and sparse learning, proving that hard-thresholding can be consistent even in the presence of heavy-tailed noise.
• Applicability: The method is particularly valuable in fields like genomics, finance, and image analysis, where data often exhibit heavy tails, complex correlations, and a high ratio of noise variables.

In summary, Sparse K-spatial-median clustering offers a robust, interpretable, and theoretically sound solution for clustering high-dimensional data, effectively handling the dual challenges of noise/outliers and irrelevant features.