Extending TCLUST to higher dimensions

Sintesi Tecnica: Estensione di TCLUST a dimensioni superiori tramite tHDDC

Enunciato del Problema
Gli outlier distorcono significativamente i risultati dei metodi di clustering standard, portando spesso a partizioni inaffidabili in cui cluster significativi vengono fusi o vengono rilevati cluster spuri. Sebbene siano state sviluppate tecniche di clustering robuste basate sul trimming, come TCLUST (Trimmed Clustering), per mitigare questi problemi, esse presentano gravi limitazioni in contesti ad alta dimensionalità. Man mano che la dimensionalità $p$ aumenta, TCLUST fatica a causa di due fattori primari: la complessità computazionale della stima di un gran numero di parametri associati alle strutture di covarianza complete e la difficoltà di inizializzare efficacementamente l'algoritmo. Al contrario, approcci alternativi come il Robust Linear Grouping (RLG), che assumono che i cluster giacciano vicino a sottospazi a dimensionalità inferiore, offrono una riduzione della dimensionalità ma soffrono di assunzioni semplificative, come errori ortogonali isotropici e difficoltà nel gestire sottospazi intersecanti.

Metodologia: L'approccio tHDDC
Per affrontare queste limitazioni, gli autori propongono tHDDC (Trimmed High-Dimensional Data Clustering), un metodo che unifica la robustezza di TCLUST con la modellazione di sottospazi di HDDC (High-Dimensional Data Clustering).

• Framework del Modello: tHDDC assume che i dati derivino da un mix di $G$ componenti gaussiane. A differenza di TCLUST, che stima matrici di covarianza complete, tHDDC adotta una struttura parsimoniosa in cui ogni cluster $g$ è concentrato attorno a un sottospazio affine $B_g$ di dimensione intrinseca $q_g$ (dove $q_g < p$).
• Struttura di Covarianza: La matrice di dispersione $\Sigma_g$ per ogni cluster è decomposta in un sottospazio specifico $B_g$ (spaziatura dai $q_g$ autovettori corrispondenti ai più grandi autovalori $\lambda_{g1}, \dots, \lambda_{gq_g}$) e un complemento ortogonale $B_g^\perp$. In $B_g^\perp$, la varianza è modellata da un singolo parametro comune $\lambda_g$. Ciò riduce significativamente il numero di parametri rispetto alla stima della covarianza completa.
• Trimming e Vincoli: Il metodo incorpora un livello di trimming $\alpha$ per escludere le osservazioni più anomale. Per garantire la ben posta matematica e prevenire soluzioni degenerate, vengono imposti due vincoli sul rapporto tra autovalori:
  1. Un vincolo $c_1$ sul rapporto tra i più grandi autovalori all'interno dei sottospazi.
  2. Un vincolo $c_2$ sul rapporto tra i più piccoli autovalori (la varianza del rumore comune $\lambda_g$) tra i cluster.
• Algoritmo: Gli autori presentano un algoritmo fattibile basato su "step di concentrazione" (C-steps), un adattamento dell'algoritmo EM. La procedura prevede:
  1. Inizializzazione Casuale: Selezione di piccoli sottoinsiemi di osservazioni per inizializzare i parametri del sottospazio.
  2. C-steps: Aggiornamento iterativo dei pesi di appartenenza (effettuando il trimming delle osservazioni con la verosimiglianza più bassa), aggiornamento delle medie dei cluster e aggiornamento dei parametri del sottospazio.
  3. Troncamento degli Autovalori: Una procedura specifica viene introdotta per imporre i vincoli sugli autovalori ($c_1, c_2$) dopo ogni aggiornamento, estendendo i metodi di troncamento utilizzati in TCLUST.
  4. Stima della Dimensione Intrinseca: Una procedura guidata dai dati basata sul criterio di Cattell è integrata per stimare automaticamente le dimensioni intrinseche $q_g$, utilizzando una penalità di complessità per evitare l'overfitting.

Contributi Chiave

1. Estensione Teorica: Il documento stabilisce l'esistenza e la coerenza degli stimatori tHDDC sotto condizioni lievi, dimostrando che il massimizzatore della popolazione esiste anche per distribuzioni a code pesanti, a condizione che venga utilizzato un livello di trimming strettamente positivo.
2. Innovazione Algoritmica: È sviluppato un nuovo algoritmo C-step che gestisce la specifica parametrizzazione parsimoniosa di HDDC integrando al contempo il robusto trimming e i vincoli sugli autovalori di TCLUST. Ciò include un nuovo meccanismo di troncamento degli autovalori per soddisfare i doppi vincoli ($c_1, c_2$).
3. Selezione Automatica della Dimensione: Gli autori propongono un metodo per determinare automaticamente le dimensioni intrinseche $q_g$ dei sottospazi, riducendo la necessità di specifiche manuali e mitigando il rischio di overfitting attraverso un criterio di verosimiglianza penalizzato per complessità.
4. Strumenti Diagnostici: Il documento introduce strumenti diagnostici grafici, inclusi i punteggi di distanza (score distances) e le distanze ortogonali, per valutare l'adeguatezza dei cluster e rilevare anomalie, nonché i "fattori discriminanti" per valutare l'affidabilità delle assegnazioni ai cluster e delle decisioni di trimming.

Risultati

• Studio di Simulazione: Esperimenti su dati sintetici in 200 dimensioni ($p=200$) con diversi gradi di sovrapposizione dei cluster e orientamento dei sottospazi mostrano che tHDDC raggiunge un'accuratezza di classificazione quasi perfetta in tutti gli scenari. Al contrario, TCLUST si comporta scarsamente in alta dimensionalità e RLG fallisce quando i sottospazi si intersecano. Inoltre, tHDDC è computazionalmente circa 2,5 o 3 volte più veloce di TCLUST in condizioni comparabili.
• Applicazione su Dati Reali: Il metodo è stato applicato a un dataset di cifre scritte a mano (USPS358) contaminate da outlier artificiali e reali. tHDDC ha ottenuto un errore di classificazione di circa il 7% (su dati non sottoposti a trimming), superando significativamente TCLUST (errore > 38%) e l'HDDC non robusto (errore > 39%). L'analisi ha identificato e rimosso con successo gli outlier artificiali preservando la struttura dei cluster delle cifre.

Significatività e Rivendicazioni
Il documento afferma che tHDDC fornisce una soluzione robusta ed efficiente dal punto di vista computazionale per il clustering in contesti di dimensionalità moderatamente elevata dove i metodi tradizionali come TCLUST falliscono a causa dell'esplosione dei parametri e della sensibilità all'inizializzazione. Combinando le assunzioni di sottospazio di HDDC con il robusto trimming di TCLUST, il metodo offre un'alternativa meno semplicistica a RLG, capace di gestire sottospazi intersecanti e errori non isotropici. Gli autori sottolineano che la metodologia è particolarmente preziosa per dataset con strutture di cluster sconosciute e contaminazione, offrendo sia una migliore accuratezza che una riduzione del costo computazionale rispetto alle tecniche di clustering robusto in alta dimensionalità esistenti. Si nota che il lavoro futuro includerà estensioni ai dati funzionali e strategie di trimming cellwise.