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

1. Enunciato del Problema

Il documento affronta le sfide del clustering di dati ad alta dimensionalità ($p \gg n$) caratterizzati da due difficoltà specifiche:

1. Distribuzioni a code pesanti e valori anomali: I metodi classici come K-means si basano sulla media aritmetica e sulla perdita euclidea quadratica, rendendoli altamente sensibili ai valori anomali e al rumore a code pesanti (ad esempio, distribuzioni $t$ multivariate).
2. Variabili irrilevanti: In contesti ad alta dimensionalità, una grande proporzione di caratteristiche spesso non trasporta informazioni discriminanti per i cluster. L'inclusione di queste variabili "rumorose" diluisce il segnale di clustering, causando un degrado delle prestazioni anche nei metodi robusti se trattano tutte le dimensioni in modo uguale.

I metodi di clustering sparsi esistenti (ad esempio, Sparse K-means) utilizzano spesso l'assottigliamento continuo (regolarizzazione L1) per ridurre il peso delle caratteristiche irrilevanti, il che potrebbe non produrre un'esclusione esplicita delle caratteristiche e può essere difficile da calibrare in contesti robusti. Inoltre, i metodi robusti standard (come K-medians) spesso mancano di equivarianza rispetto alla rotazione, non rispettando la geometria ellittica sottostante dei cluster.

2. Metodologia

Gli autori propongono un quadro unificato chiamato Sparse K-spatial-median clustering, che integra la stima robusta del centro con la selezione esplicita delle caratteristiche. Il quadro consiste in due algoritmi complementari:

A. Concetto Chiave: Mediana Spaziale

Invece della media aritmetica (K-means) o delle mediane coordinate per coordinate (K-medians), il metodo utilizza la mediana spaziale (mediana geometrica) come centro del cluster.

• Definizione: La mediana spaziale $m$ minimizza la somma delle distanze euclidee: $m = \arg\min \sum \|x_i - m\|_2$.
• Vantaggio: È equivariante rispetto alla rotazione (rispetta la geometria multivariata) e robusta rispetto alle code pesanti perché la funzione di perdita cresce linearmente anziché quadraticamente.

B. Algoritmo 1: SM–SSCM (Clustering a Mediana Spaziale con Matrice di Covarianza del Segno Spaziale Comune)

Questa variante affronta le scale eterogenee e la dipendenza delle caratteristiche senza un'esclusione esplicita delle caratteristiche.

• Passo di Assegnazione: Invece della distanza euclidea standard, utilizza una metrica di tipo Mahalanobis costruita a partire da una comune Matrice di Covarianza del Segno Spaziale (SSCM).
• Stima SSCM: La matrice di dispersione è stimata utilizzando i segni spaziali ($u_i = r_i / \|r_i\|$) dei residui, regolarizzati con un parametro di ridge per garantire l'invertibilità.
• Beneficio: Questo adatta la metrica di distanza alla struttura di correlazione e alla scala dei dati, migliorando l'accuratezza dell'assegnazione in alta dimensionalità.

C. Algoritmo 2: Sparse–SM (Clustering Spaziale a Mediana Spaziale Sparsa)

Questa variante affronta il regime $p \gg n$ con variabili irrilevanti introducendo l'esclusione delle caratteristiche tramite soglia dura.

• Punteggio di Separazione: Ad ogni iterazione, viene calcolato un punteggio $s_j$ per ogni caratteristica $j$ basato sulla dispersione dei centri del cluster lungo quella coordinata: $s_j = \sum_{k=1}^K |m_{kj} - \bar{m}_j|$.
• Esclusione Dura: Le caratteristiche con punteggi inferiori a una soglia $\tau$ sono completamente escluse dal passo di assegnazione. Questo crea un insieme esplicito di variabili attive ($S(\tau)$) invece di assottigliare i pesi in modo continuo.
• Calibrazione (Criterio Gap): La soglia $\tau$ viene selezionata automaticamente utilizzando una statistica Gap basata su permutazioni. L'algoritmo confronta la separazione tra cluster osservata con una distribuzione di riferimento generata permutando le colonne (distruggendo la struttura del cluster pur mantenendo le distribuzioni marginali). Viene selezionata la $\tau$ che massimizza il Gap.

D. Proprietà Teoriche

Il documento stabilisce la consistenza del clustering e la consistenza nella selezione delle caratteristiche per i metodi proposti sotto un modello ellittico di miscela con code sub-Weibull o polinomiali.

• Consistenza: Quando $n \to \infty$, l'algoritmo recupera la partizione vera e l'insieme vero delle caratteristiche informative con probabilità che tende a 1, a condizione che la separazione del segnale sia sufficientemente forte rispetto al livello di rumore.
• Robustezza: I limiti teorici mostrano che la mediana spaziale e la metrica SSCM mantengono la stabilità anche in presenza di contaminazione a code pesanti.

3. Contributi Chiave

1. Quadro Robusto: Sviluppo di un quadro di clustering basato sulla partizione che utilizza mediane spaziali, offrendo una robustezza superiore rispetto alle code pesanti e ai valori anomali rispetto ai metodi basati sulla media o sulle mediane coordinate.
2. Selezione Esplicita delle Caratteristiche: Introduzione di un meccanismo di soglia dura che produce insiemi interpretabili ed esatti di variabili mantenute ed escluse, evitando l'ambiguità dell'assottigliamento continuo.
3. Calibrazione Guidata dai Dati: Proposta di un criterio Gap basato su permutazioni specificamente progettato per selezionare la soglia di sparsità in contesti robusti e ad alta dimensionalità.
4. Garanzie Teoriche: Dimostrazione della consistenza sia per la partizione di clustering che per il recupero del supporto (selezione delle caratteristiche) sotto modelli ellittici generali con code pesanti.

4. Risultati Sperimentali

Gli autori hanno valutato i metodi confrontandoli con K-means, K-medians, Sparse K-means e Sparse K-medians utilizzando simulazioni e dati reali.

• Studi di Simulazione:
  • Code Pesanti e Contaminazione: Sotto distribuzioni $t$ multivariate e miscele gaussiane contaminate, Sparse–SM e SM–SSCM hanno superato significativamente i baseline non robusti. Sparse–SM ha ottenuto il più alto Indice Rand Aggiustato (ARI) in contesti contaminati.
  • Alta Dimensionalità: All'aumentare della dimensionalità $p$ (fino a 400), i metodi non sparsi si sono deteriorati rapidamente. Sparse–SM ha mantenuto alta stabilità e accuratezza, dimostrando la necessità dell'esclusione delle caratteristiche.
  • Tipi di Outlier: Il metodo ha mostrato particolare resilienza contro la contaminazione cella-per-cella (corruzione di singole voci), dove ha costantemente superato i concorrenti.
• Applicazioni su Dati Reali:
  • Dati sulle Proteine dei Topi: Su un dataset di livelli di espressione proteica, i metodi proposti hanno ottenuto un ARI più alto e una maggiore stabilità tra le esecuzioni rispetto ai metodi classici.
  • Dataset di Riferimento: Testati su 8 dataset UCI/KEEL (ad esempio, Iris, Wine, WDBC). I metodi proposti sono stati competitivi o superiori, con SM–SSCM che ha eccellito nei dataset con correlazioni complesse e Sparse–SM che ha ottenuto i migliori risultati dove la sparsità delle caratteristiche era vantaggiosa.

5. Significato

Questo documento rappresenta un avanzamento critico per l'analisi dei dati moderna, dove i dataset sono sia ad alta dimensionalità che soggetti a valori anomali.

• Impatto Pratico: Offre un algoritmo iterativo computazionalmente efficiente che non richiede risolutori di ottimizzazione complessi (a differenza di alcuni approcci di verosimiglianza penalizzata) ma fornisce una selezione rigorosa delle caratteristiche.
• Insight Teorico: Colma il divario tra statistica robusta (segni/mediane spaziali) e apprendimento sparso, dimostrando che la soglia dura può essere consistente anche in presenza di rumore a code pesanti.
• Applicabilità: Il metodo è particolarmente prezioso in campi come la genomica, la finanza e l'analisi delle immagini, dove i dati spesso presentano code pesanti, correlazioni complesse e un alto rapporto di variabili rumorose.

In sintesi, il Sparse K-spatial-median clustering offre una soluzione robusta, interpretabile e teoricamente fondata per il clustering di dati ad alta dimensionalità, gestendo efficacemente le sfide duali di rumore/valori anomali e caratteristiche irrilevanti.