Extending TCLUST to higher dimensions

Technische Samenvatting: Uitbreiding van TCLUST naar hogere dimensies via tHDDC

Probleemstelling
Outliers vervormen de resultaten van standaard clusteringmethoden aanzienlijk, wat vaak leidt tot onbetrouwbare partities waarbij betekenisvolle clusters worden samengevoegd of spuriële clusters worden gedetecteerd. Hoewel robuuste clusteringtechnieken gebaseerd op trimming, zoals TCLUST (Trimmed Clustering), zijn ontwikkeld om deze problemen te mitigeren, kampen zij met ernstige beperkingen in hoogdimensionale settings. Naarmate de dimensionaliteit $p$ toeneemt, worstelt TCLUST met twee primaire factoren: de computationele complexiteit van het schatten van een groot aantal parameters geassocieerd met volledige covariantiestructuren, en de moeilijkheid om het algoritme effectief te initialiseren. Daarentegen bieden alternatieve benaderingen zoals Robust Linear Grouping (RLG), die aannemen dat clusters nabij lagerdimensionale subruimten liggen, dimensionaliteitsreductie, maar lijden zij onder simplificerende aannames, zoals isotrope orthogonale fouten en problemen bij het afhandelen van snijdende subruimten.

Methodologie: De tHDDC-benadering
Om deze beperkingen aan te pakken, stellen de auteurs tHDDC (Trimmed High-Dimensional Data Clustering) voor, een methode die de robuustheid van TCLUST verenigt met de subruimte-modellering van HDDC (High-Dimensional Data Clustering).

• Modelkader: tHDDC neemt aan dat data voortkomen uit een mengeling van $G$ Gaussische componenten. In tegen tegenstelling tot TCLUST, dat volledige covariantie-matrices schat, hanteert tHDDC een parsimonieuze structuur waarbij elke cluster $g$ geconcentreerd is rond een affiene subruimte $B_g$ met een intrinsieke dimensie $q_g$ (waarbij $q_g < p$).
• Covariantiestructuur: De scattermatrix $\Sigma_g$ voor elke cluster wordt gedecomposeerd in een specifieke subruimte $B_g$ (gespannen door de $q_g$ eigenvectoren die overeenkomen met de grootste eigenwaarden $\lambda_{g1}, \dots, \lambda_{gq_g}$) en een orthogonaal complement $B_g^\perp$. In $B_g^\perp$ wordt de variantie gemodelleerd door één enkele gemeenschappelijke parameter $\lambda_g$. Dit vermindert het aantal parameters aanzienlijk vergeleken met het schatten van een volledige covariantie.
• Trimming en Constanten: De methode incorporeert een trimming-niveau $\alpha$ om de meest uitschietende observaties uit te sluiten. Om wiskundige welgesteldheid te garanderen en degeneratieve oplossingen te voorkomen, worden twee eigenwaarde-ratio-constanten opgelegd:
  1. Een constraint $c_1$ op de ratio van de grootste eigenwaarden binnen de subruimten.
  2. Een constraint $c_2$ op de ratio van de kleinste eigenwaarden (de gemeenschappelijke ruisvariantie $\lambda_g$) over de clusters heen.
• Algoritme: De auteurs presenteren een uitvoerbaar algoritme gebaseerd op "concentratiestappen" (C-stappen), een adaptatie van het EM-algoritme. De procedure omvat:
  1. Random Initialisatie: Het selecteren van kleine subsets van observaties om subruimteparameters te initialiseren.
  2. C-stappen: Iteratief updaten van lidmaatschapsgewichten (het trimmen van de observaties met de laagste likelihood), het updaten van clustergemiddelden en het updaten van subruimteparameters.
  3. Eigenwaarde-truncatie: Een specifieke procedure wordt geïntroduceerd om de eigenwaarde-constraints ($c_1, c_2$) af te dwingen na elke update, waarmee de truncatiemethoden die in TCLUST worden gebruikt, worden uitgebreid.
  4. Intrinsieke Dimensie Schatting: Een datagestuurde procedure gebaseerd op het Cattell-criterium is geïntegreerd om de intrinsieke dimensies $q_g$ automatisch te schatten, gebruikmakend van een complexiteitsstraf om overfitting te voorkomen.

Belangrijkste Bijdragen

1. Theoretische Uitbreiding: Het artikel stelt de existentie en consistentie van de tHDDC-schatters vast onder milde condities, waarbij bewezen wordt dat de populatiemaximalisator bestaat, zelfs voor heavy-tailed distributies, mits een strikt positief trimming-niveau wordt gebruikt.
2. Algoritmische Innovatie: Er is een nieuw C-stap algoritme ontwikkeld dat de specifieke parsimonieuze parametrisering van HDDC afhandelt, terwijl het de robuuste trimming en eigenwaarde-constraints van TCLUST integreert. Dit omvat een nieuwe eigenwaarde-truncatiemechanisme om de duale constraints ($c_1, c_2$) te voldoen.
3. Geautomatiseerde Dimensiekeuze: De auteurs stellen een methode voor om de intrinsieke dimensies $q_g$ van de subruimten automatisch te bepalen, wat de noodzaak voor handmatige specificatie vermindert en het risico op overfitting mitigeert via een complexiteitsgestrafte likelihood-criterium.
4. Diagnostische Instrumenten: Het artikel introduceert grafische diagnostische instrumenten, waaronder score-afstanden (score distances) en orthogonale afstanden (orthogonal distances), om de adequaatheid van clusters te beoordelen en anomalieën te detecteren, evenals "discriminant factoren" om de betrouwbaarheid van cluster-toezigningen en trimming-beslissingen te evalueren.

Resultaten

• Simulatiestudie: Experimenten op synthetische data in 200 dimensies ($p=200$) met variërende graden van clusteroverlap en subruimte-oriëntatie tonen aan dat tHDDC een bijna perfecte classificatienauwkeurigheid bereikt in alle scenario's. In contrast hiermee presteert TCLUST slecht in hoge dimensies, en faalt RLG wanneer subruimten snijden. Bovendien is tHDDC computationeel ongeveer 2,5 tot 3 keer sneller dan TCLUST onder vergelijkbare condities.
• Toepassing op Real-world Data: De methode werd toegepast op een dataset van handgeschreven cijfers (USPS358) die gecontamineerd was met kunstmatige en echte outliers. tHDDC bereikte een classificatiefout van ongeveer 7% (op niet-getrimde data), wat significant beter is dan TCLUST (fout > 38%) en de niet-robuuste HDDC (fout > 39%). De analyse identificeerde en verwijderde succesvol kunstmatige outliers terwijl de structuur van de cijferclusters behouden bleef.

Betekenis en Claims
Het artikel claimt dat tHDDC een robuuste en computationeel efficiënte oplossing biedt voor clustering in matig hoogdimensionale settings waar traditionele methoden zoals TCLUST falen door parameter-explosie en initialisatiesensitiviteit. Door de subruimte-aannames van HDDC te combineren met de robuuste trimming van TCLUST, biedt de methode een minder simplistische alternatief voor RLG, in staat om snijdende subruimten en niet-isotrope fouten te verwerken. De auteurs benadrukken dat de methodologie bijzonder waardevol is voor datasets met onbekende clusterstructuren en contaminatie, waarbij zowel verbeterde nauwkeurigheid als verminderde computationele kosten worden geboden vergeleken met bestaande robuuste hoogdimensionale clusteringtechnieken. Toekomstig werk omvat functionele data-extensies en cellwise trimming-strategieën.