Depth-Based Local Center Clustering: A Framework for Handling Different Clustering Scenarios

Sintesi Tecnica: Depth-Based Local Center Clustering (DLCC)

Definizione del Problema
L'analisi di clustering è fondamentale per la scienza dei dati, eppure i metodi esistenti spesso faticano ad affrontare la diversità delle distribuzioni dei dati reali. Gli approcci tradizionali si dividono generalmente in due categorie, ciascuna con specifiche limitazioni:

• Metodi basati sui centri (es. k-means) assumono un singolo punto rappresentativo per cluster e forme sferiche, il che li rende sensibili agli outlier e all'inizializzazione, fallendo nel modellare geometrie non convesse.
• Metodi basati sulla densità (es. DBSCAN, Mean Shift) gestiscono forme arbitrarie ma si affidano alla stima della densità o a soglie fisse, che possono risultare instabili in spazi ad alta dimensionalità o quando i cluster presentano densità variabili.
• I metodi basati su grafi spesso affrontano proibizioni computazionali su dati su larga scala o rimangono sensibili alle scelte del metrica di distanza.

Una limitazione fondamentale in tutti questi paradigmi è la definizione di "exemplars" (punti esemplari). La maggior parte dei metodi lega gli esemplari a criteri di distanza o densità che potrebbero non generalizzarsi attraverso diverse dimensionalità e geometrie. Inoltre, sebbene la profondità statistica dei dati (statistical data depth) offra un ordinamento robusto centro-esterno dei dati multivariati, essa è stata storicamente utilizzata solo come strumento ausiliario (ad esempio, per l'inizializzazione) piuttosto che come meccanismo primario per identificare la struttura locale e la multimodalità. Le funzioni di profondità standard non riescono inoltre a catturare direttamente le caratteristiche multimodali.

Metodologia: Il Framework DLCC
Il documento propone il Depth-Based Local Center Clustering (DLCC), un framework che sfrutta la profondità statistica dei dati per definire centri locali e costruire misure di similarità senza fare affidamento su metriche di distanza globale o stime di densità.

1. Matrice di Similarità Basata sulla Profondità:
   Invece di utilizzare la distanza euclidea, DLCC costruisce una matrice di similarità $S$ basata sulla Profondità Spaziale (Spatial Depth - SD). Per localizzare il concetto di profondità, il metodo definisce un dataset riflesso $X_{Ri}$ per ogni osservazione $x_i$, costituito dal campione originale $X$ e dalla riflessione di tutti i punti attraverso $x_i$. Poiché $x_i$ è il centro di simmetria per $X_{Ri}$, la sua profondità è massima (1). La profondità di qualsiasi altro punto $x_j$ rispetto a $X_{Ri}$, denotata come $D(x_j | X_{Ri})$, funge da misura di similarità tra $x_j$ e $x_i$.

• Efficienza: Gli autori introducono un'implementazione basata su matrici per calcolare queste profondità in modo efficiente, riducendo i calcoli ridondanti precomputando le somme dei vettori unitari e le norme, sebbene la complessità teorica rimanga $O(n^3)$.

2. Identificazione dei Centri Locali:
   Per ogni punto $x_i$, viene definito un vicinato $N_i$ di dimensione $s$ tramite i suoi $s-1$ vicini più prossimi basati sulla similarità derivata dalla profondità. All'interno di ogni vicinato, il punto con il rango locale più alto (punto più profondo) viene identificato come centro locale.

• Filtraggio: Non tutti i centri locali sono utili. Il metodo filtra i candidati basandosi su due criteri: (1) il centro deve essere centrale all'interno del proprio vicinato (rango $\le 2$), e (2) deve apparire frequentemente in diversi vicinati (frequenza $f > 1$). Un criterio di stabilità, la Profondità Media Indotta dai Vicini (Average Neighbor-Induced Depth - AND), viene utilizzato per selezionare ulteriormente i centri robusti.

3. Strategie di Raggruppamento:
   I centri locali filtrati vengono raggruppati in cluster utilizzando due strategie distinte per gestire diverse geometrie dei dati:

• Strategia Min: Raggruppa i centri in modo conservativo basandosi sulla sovrapposizione dei vicinati. Questa è adatta per cluster convessi bilanciati, ben separati o sovrapposti.
• Strategia Max: Raggruppa i centri tramite catene di connettività dove la similarità tra i vicinati supera una soglia $\delta$. Questa strategia è progettata per strutture non convesse e dimensioni di cluster altamente sbilanciate. Include un meccanismo per segregare le regioni "ovunque non convesse" (es. spirali) identificando i centri locali isolati.

4. Formazione dei Cluster e Classificazione:
   Una volta formati i gruppi di centri locali, vengono creati dei cluster temporanei utilizzando i vicini unici di ogni gruppo. Ai punti vengono assegnati punteggi in base alla loro similarità rispetto ai centri del gruppo rispetto ad altri gruppi. I punti ambigui o non assegnati vengono poi classificati utilizzando classificatori integrati (k-Nearest Neighbors o Random Forests) addestrati sui label dei cluster temporanei, garantendo un'assegnazione robusta senza ulteriore tuning degli iperparametri.

Contributi Chiave

• Framework Innovativo: DLCC è il primo metodo che pone la profondità dei dati al centro sia dell'identificazione degli esemplari che della costruzione della similarità, affrontando direttamente la multimodalità.
• Calcolo Efficiente: Il documento sviluppa un'implementazione basata su matrici per costruire matrici di similarità basate sulla profondità sotto la profondità spaziale, accelerando significativamente il calcolo rispetto alle implementazioni naive.
• Raggruppamento Flessibile: L'approccio a doppia strategia (Min/Max) permette al framework di adattarsi a diverse forme di cluster (convesse vs non convesse) e distribuzioni di densità.
• Valutazione Completa: Gli autori forniscono una procedura end-to-end completa, inclusi i criteri di selezione dei parametri (utilizzando l'indice CVDD e la visualizzazione) e ampie valutazioni empiriche.

Risultati Sperimentali
Gli autori hanno valutato DLCC su 12 dataset sintetici e 13 benchmark del mondo reale (inclusi dati ad alta dimensionalità di immagini e microarray).

• Performance: DLCC ha ottenuto un recupero perfetto su 7 dataset sintetici e si è posizionato costantemente nei primi tre posti in tutti i benchmark del mondo reale. Ha dimostrato una performance superiore nel gestire forme non convesse, densità variabili e squilibrio delle classi rispetto ai competitor come LW-k-means, EKM, R-MDPC e ACLR.
• Limitazioni Osservate: Il metodo ha faticato con strutture "tipo manifold" dove i vicinati locali sono intrinsecamente non convesse (es. il dataset "Atom" e le strutture a spirale in "Blend"). In questi casi, l'assunzione che i centri locali risiedano in vicinati approssimativamente convessi è fallita.
• Scalabilità: Sebbene efficace per dataset fino a $\sim 10^4$ osservazioni, la complessità $O(n^3)$ della costruzione della matrice di similarità rimane un collo di bottiglia per dati su scala molto grande.

Significato e Rivendicazioni
Il documento afferma che DLCC offre un'alternativa flessibile ai metodi di clustering tradizionali superando le rigide assunzioni dei metodi basati sui centri e l'instabilità dei metodi basati sulla densità in alta dimensione. Utilizzando la profondità dei dati per definire la geometria locale, DLCC potenzia le capacità di analisi dei dati in un'ampia gamma di scenari senza richiedere un numero predefinito di cluster o rigide assunzioni distributive. Gli autori posizionano DLCC come uno strumento robusto per l'analisi esplorativa dei dati, particolarmente laddove le forme dei cluster sono complesse o sconosciute, pur riconoscendo che è necessario ulteriore lavoro per migliorare la scalabilità e automatizzare la selezione dei parametri.