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

1. Probleemstelling

Het artikel behandelt de uitdagingen van het clusteren van hoogdimensionale data ($p \gg n$) die gekenmerkt worden door twee specifieke moeilijkheden:

1. Zwaarstaartige verdelingen en uitschieters: Klassieke methoden zoals K-means vertrouwen op het rekenkundig gemiddelde en kwadratische Euclidische verliezen, waardoor ze zeer gevoelig zijn voor uitschieters en zwaarstaartige ruis (bijvoorbeeld multivariate $t$-verdelingen).
2. Irrelevante variabelen: In hoogdimensionale settings dragen vaak een groot deel van de kenmerken geen cluster-discriminerende informatie. Het opnemen van deze "ruis"-variabelen verdunt het clustersignaal, wat leidt tot prestatiedegradatie, zelfs bij robuuste methoden, als ze alle dimensies gelijk behandelen.

Bestaande sparse clustermethoden (bijvoorbeeld Sparse K-means) gebruiken vaak continue shrinkage (L1-regularisatie) om irrelevante kenmerken minder zwaar te wegen, wat mogelijk geen expliciete uitsluiting van kenmerken oplevert en moeilijk te tunen kan zijn in robuuste settings. Bovendien missen standaard robuuste methoden (zoals K-medians) vaak rotatie-equivariantie, waardoor ze de onderliggende elliptische geometrie van clusters niet respecteren.

2. Methodologie

De auteurs stellen een unificerend kader voor genaamd Sparse K-spatial-median clustering, dat robuuste schatting van centra integreert met expliciete featureselectie. Het kader bestaat uit twee complementaire algoritmen:

A. Kernconcept: Ruimtelijk Mediaan

In plaats van het rekenkundig gemiddelde (K-means) of coördinaatgewijze medianen (K-medians), gebruikt de methode de ruimtelijke mediaan (geometrische mediaan) als clustercentrum.

• Definitie: De ruimtelijke mediaan $m$ minimaliseert de som van Euclidische afstanden: $m = \arg\min \sum \|x_i - m\|_2$.
• Voordeel: Het is rotatie-equivariant (respecteert multivariate geometrie) en robuust voor zware staarten omdat de verliesfunctie lineair groeit in plaats van kwadratisch.

B. Algoritme 1: SM–SSCM (Spatial-Median Clustering met Gemeenschappelijke Spatial-Sign Covariantie)

Deze variant adresseert heterogene schalen en feature-afhankelijkheid zonder expliciete uitsluiting van kenmerken.

• Toewijzingsstap: In plaats van standaard Euclidische afstand, gebruikt het een Mahalanobis-type metriek opgebouwd uit een gemeenschappelijke Spatial-Sign Covariantiematrix (SSCM).
• SSCM-schatting: De spreidingsmatrix wordt geschat met behulp van spatial signs ($u_i = r_i / \|r_i\|$) van residuen, geregulariseerd met een ridge-parameter om invertibiliteit te waarborgen.
• Voordeel: Dit past de afstandsmetriek aan aan de correlatiestructuur en schaal van de data, waardoor de toewijzingsnauwkeurigheid in hoge dimensies verbetert.

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

Deze variant adresseert het regime $p \gg n$ met irrelevante variabelen door hard-thresholding feature-uitsluiting in te voeren.

• Scheidingsscore: Bij elke iteratie wordt een score $s_j$ berekend voor elke feature $j$ op basis van de spreiding van clustercentra langs die coördinaat: $s_j = \sum_{k=1}^K |m_{kj} - \bar{m}_j|$.
• Harde Uitsluiting: Features met scores onder een drempel $\tau$ worden volledig uitgesloten uit de toewijzingsstap. Dit creëert een expliciete set actieve variabelen ($S(\tau)$) in plaats van gewichten continu te laten shrinken.
• Tuning (Gap-criterium): De drempel $\tau$ wordt automatisch geselecteerd met behulp van een permutatie-gebaseerde Gap-statistiek. Het algoritme vergelijkt de waargenomen tussen-cluster-scheiding met een referentieverdeling gegenereerd door kolommen te permuteren (waarbij clusterstructuur wordt vernietigd terwijl marginale verdelingen behouden blijven). De $\tau$ die de Gap maximaliseert, wordt geselecteerd.

D. Theoretische Eigenschappen

Het artikel vestigt clustering-consistentie en featureselectie-consistentie voor de voorgestelde methoden onder een mengsel-elliptisch model met sub-Weibull- of polynoomstaarten.

• Consistentie: Naarmate $n \to \infty$, herstelt het algoritme de ware partitie en de ware set informatieve features met een waarschijnlijkheid die naar 1 nadert, mits de signaalscheiding voldoende sterk is ten opzichte van het ruisniveau.
• Robuustheid: Theoretische grenzen tonen aan dat de ruimtelijke mediaan en SSCM-metriek stabiliteit behouden zelfs onder zwaarstaartige contaminatie.

3. Belangrijkste Bijdragen

1. Robuust Kader: Ontwikkeling van een op partities gebaseerd clusterramenwerk met behulp van ruimtelijke medianen, wat superieure robuustheid biedt voor zware staarten en uitschieters in vergelijking met op gemiddelde gebaseerde of coördinaatgewijze mediaan-methoden.
2. Expliciete Featureselectie: Introductie van een hard-thresholding-mechanisme dat interpreteerbare, exacte sets van behouden en uitgesloten variabelen oplevert, waardoor de ambiguïteit van continue shrinkage wordt vermeden.
3. Data-gedreven Tuning: Voorstel van een permutatie-gebaseerd Gap-criterium specifiek ontworpen voor het selecteren van de sparsiteitsdrempel in robuuste, hoogdimensionale settings.
4. Theoretische Waarborgen: Bewijs van consistentie voor zowel de clustering-partitie als de support-herwinning (featureselectie) onder algemene elliptische modellen met zware staarten.

4. Experimentele Resultaten

De auteurs evalueerden de methoden tegen K-means, K-medians, Sparse K-means en Sparse K-medians met behulp van simulaties en echte data.

• Simulatiestudies:
  • Zware Staarten & Contaminatie: Onder multivariate $t$-verdelingen en verontreinigde Gaussische mengsels presteerden Sparse–SM en SM–SSCM aanzienlijk beter dan niet-robuste baselines. Sparse–SM behaalde de hoogste Adjusted Rand Index (ARI) in verontreinigde settings.
  • Hoge Dimensies: Naarmate de dimensie $p$ toenam (tot 400), verslechterden niet-sparse methoden snel. Sparse–SM behield hoge stabiliteit en nauwkeurigheid, wat de noodzaak van feature-uitsluiting aantoont.
  • Uitschieter-types: De methode toonde bijzondere veerkracht tegen cell-wise contaminatie (corruptie van individuele invoer), waarbij het consequent beter presteerde dan concurrenten.
• Toepassingen op Echte Data:
  • Mice Protein Data: Op een dataset van proteïne-expressieniveaus bereikten de voorgestelde methoden een hogere ARI en grotere stabiliteit over runs heen in vergelijking met klassieke methoden.
  • Benchmarks datasets: Getest op 8 UCI/KEEL datasets (bijvoorbeeld Iris, Wine, WDBC). De voorgestelde methoden waren concurrerend of superieur, waarbij SM–SSCM excelleerde in datasets met complexe correlaties en Sparse–SM het beste presteerde waar feature-sparsiteit voordelig was.

5. Betekenis

Dit artikel biedt een kritieke vooruitgang voor moderne data-analyse waar datasets zowel hoogdimensionaal zijn als vatbaar voor uitschieters.

• Praktische Impact: Het biedt een computerefficiënt, iteratief algoritme dat geen complexe optimalisatie-oplossers vereist (in tegenstelling tot sommige gepenaliseerde likelihood-benaderingen), maar wel rigoureuze featureselectie biedt.
• Theoretisch Inzicht: Het overbrugt de kloof tussen robuuste statistiek (spatial signs/medianen) en sparse learning, en bewijst dat hard-thresholding consistent kan zijn zelfs in aanwezigheid van zwaarstaartige ruis.
• Toepasbaarheid: De methode is bijzonder waardevol in gebieden zoals genomica, financiën en beeldanalyse, waar data vaak zware staarten, complexe correlaties en een hoog ratio van ruisvariabelen vertonen.

Kortom, Sparse K-spatial-median clustering biedt een robuuste, interpreteerbare en theoretisch onderbouwde oplossing voor het clusteren van hoogdimensionale data, die effectief omgaat met de dubbele uitdagingen van ruis/uitschieters en irrelevante features.