Technische Samenvatting: Clusteren en dan Embedden: Een Modulaire Aanpak voor Visualisatie

Probleemstelling

Dimensiereductiemethoden, met name t-SNE en UMAP, worden veelvuldig gebruikt voor het visualiseren van hoogdimensionele data met latente geclusterde structuren. Hoewel deze methoden effectief datapunten groeperen en lokale informatie behouden, staan ze erom bekend de globale geometrie van de onderliggende data te vervormen. Specifiek falen ze vaak in het behoud van de relatieve posities, afstanden en groottes van verschillende clusters. Deze beperking komt voort uit het "crowding-probleem" (verdringingsprobleem), waarbij laagdimensionale embedding-ruimtes onvoldoende capaciteit hebben om alle punten op hun oorspronkelijke hoogdimensionale afstandsschalen te huisvesten, wat leidt tot het instorten van verre punten en de overlap van onderscheidende clusters. Bestaande methoden dwingen vaak een afweging af tussen het behoud van lokale structuur (het scheiden van clusters) en het behoud van globale afstanden.

Methodologie: Het Cluster+Embed (C+E) Framework

De auteurs stellen een modulair, driestaps framework voor genaamd Cluster+Embed (C+E) om de afweging tussen lokale en globale getrouwheid aan te pakken. De aanpak ontkoppelt clustering, lokale embedding en globale uitlijning, waardoor de analist specifieke algoritmen voor elke fase kan selecteren op basis van hun visualisatiedoelen.

Stap 1: Clustering

De data $\{x_i\}_{i=1}^n$ wordt eerst gepartitioneerd in $\kappa$ clusters ($C_1, \dots, C_\kappa$) met behulp van een gekozen clusteringalgoritme (bijv. Leiden, DBSCAN, k-means). Deze stap onthult expliciet de aanwezige clusterstructuur in de data. Punten die als ruis zijn geïdentificeerd, kunnen in deze fase worden verwijderd.

Stap 2: Individuele Cluster Embedding

Elke cluster $C_l$ wordt afzonderlijk geëmbed in een laagdimensionale ruimte (meestal $\mathbb{R}^2$) met behulp van een gekozen embedding-methode (bijv. PCA, Isomap, TriMap).

• Rationale: Het afzonderlijk embedden van clusters vermindert de vervorming vergeleken met het embedden van de gehele dataset tegelijkertijd, aangezien het "crowding-probleem" wordt gemitigeerd binnen kleinere, gelokaliseerde deelverzamelingen.
• Schaling: Als de embedding-methode steunt op ordinale informatie, wordt een schalingsfactor $\gamma_l$ toegepast op elke cluster om de kwadratische loss tussen geëmbedde afstanden en oorspronkelijke dissimilariteiten te minimaleniseren.

Stap 3: Globale Uitlijning

De geëmbedde clusters worden uitgelijnd in een enkele globale embedding met behulp van enkel rigide transformaties (translaties, rotaties en reflecties). Het doel is om de clusters ten opzichte van elkaar te positioneren zodanig dat de paarwijze dissimilariteiten tussen punten in verschillende clusters zo getrouw mogelijk worden behouden.

• Optimalisatie: De uitlijning minimaliseert een stressfunctie (Kruskal's stress) gedefinieerd als:
  $$\min_{T_1, \dots, T_\kappa} \sum_{1 \le i < j \le \kappa} \sum_{l \in C_i} \sum_{m \in C_j} (\delta_{lm} - \|T_i(y_l) - T_j(y_m)\|)^2$$
  waarbij $\delta_{lm}$ de oorspronkelijke dissimilariteit is en $T$ rigide transformaties vertegenwoordigt.
• Crowding Mitigatie via Schaling ($\alpha$): Om overlap in de uiteindelijke visualisatie te voorkomen, introduceren de auteurs een tuningparameter $\alpha \ge 1$. De doelafstand tussen clusters wordt geschaald naar $\alpha \delta_{lm}$. Dit vergroot effectief de ruimte tussen clusters in de laagdimensionale kaart, waardoor het crowding-probleem wordt vermeden.
  • $\alpha$ kan handmatig of automatisch worden afgestemd. Een automatische heuristiek wordt voorgesteld: $\alpha = \max(1, \frac{\kappa \tau}{2\pi \Delta})$, waarbij $\tau$ de gemiddelde clusterdiameter is en $\Delta$ de gemiddelde afstand tussen clusters.

Belangrijkste Bijdragen

1. Modulair Framework: Het artikel introduceert een transparante, modulaire aanpak waarbij clustering, embedding en uitlijning afzonderlijke stappen zijn. Dit stelt gebruikers in staat om specifieke algoritmen voor elke fase te kiezen om specifieke visualisatie-eigenschappen te targeten (bijv. TriMap voor kNN-recall of PCA voor afstandbehoud).
2. Expliciete Controle over Globale Geometrie: In tegenstelling tot t-SNE en UMAP, die globale structuur impliciet en vaak opaak afhandelen via force-directed dynamica, optimaliseert C+E expliciet voor het behoud van inter-cluster afstanden via rigide uitlijning.
3. Oplossing voor het Crowding-probleem: De methode pakt het crowding-probleem aan, niet door de kernel te wijzigen (zoals t-SNE doet met de Cauchy-kernel), maar door de inter-cluster afstanden expliciet te schalen via de parameter $\alpha$, wat ervoor zorgt dat onderscheidende clusters niet overlappen terwijl hun relatieve organisatie behouden blijft.
4. Transparantie: De aanpak is interpreteerbaarder dan end-to-end methoden omdat het behoud van lokale structuur (binnen clusters) en globale structuur (tussen clusters) wordt afgehandeld door aparte, controleerbare mechanismen.

Experimentele Resultaten

De auteurs evalueerden C+E op synthetische en real-world datasets (MNIST, menselijke hersenorganoïde data, muis cortex data) tegen baselines inclusief t-SNE, UMAP, PCA, Isomap, PHATE en TriMap.

• Synthetische Vormen Dataset: C+E bereikte perfecte lokale metrieken (het herstellen van exacte clusterconfiguraties) en behield de globale oriëntatie, terwijl t-SNE en UMAP significante lokale vervorming introduceerden.
• MNIST: C+E slaagde erin clusters te scheiden en ze in betekenisvolle groeperingen te organiseren (bijv. het groeperen van vergelijkbare cijfers). Terwijl t-SNE een superieure kNN-recall vertoonde voor kleine $k$, presteerde C+E beter dan t-SNE en UMAP op globale metrieken (klassebehoud en inter-cluster afstandbehoud).
• Menselijke Hersenorganoïde Data: C+E embeddings onthulden een duidelijke temporele ontwikkelingsbaan en onderscheidende celtype-groeperingen. Het behield globale metrieken die vergelijkbaar met of beter dan PCA en L-Isomap waren, terwijl het verbeterde lokale structuur en minder instorting bood dan t-SNE of UMAP.
• Muis Cortex Data: C+E onthulde een coarse-to-fine structuur (het scheiden van inhibitoire/excitatoire neuronen en niet-neuronen) die niet aanwezig was bij andere methoden. Hoewel de schaal van de embedding werd opgeblazen (wat leidde tot hogere genormaliseerde stress), bevoordeelden schaal-invariante globale metrieken C+E boven UMAP en t-SNE.

Betekenis en Claims

Het artikel claimt dat C+E een concurrerend alternatief biedt voor bestaande visualisatiemethoden door een balans te vinden tussen getrouwe lokale embeddings en een getrouwe globale organisatie.

• Beheer van de Afweging: De methode erkent de inherente afweging tussen lokaal en globaal behoud, maar biedt een mechanisme (de parameter $\alpha$) om deze afweging expliciet te beheren.
• Flexibiliteit: Het framework stelt gebruikers in staat om specifieke metrieken te prioriteren (bijv. kNN-recall via TriMap of afstandbehoud via PCA) zonder de globale ordening van clusters op te offeren.
• Beperkingen: De auteurs merken bescheiden op dat t-SNE nog steeds de state-of-the-art is voor het maximaliseren van kNN-recall voor kleine $k$. Ze suggereren dat de kNN-recall van C+E kan worden verbeterd door $\alpha$ te verhogen of meer clusters te creëren, hoewel dit het risico op het introduceren van valse clusters met zich meebrengt. De computationele complexiteit van de uitlijningsstap schaalt kwadratisch met het aantal punten, hoewel subsampling-strategieën worden ingezet om dit te mitigeren.

Concluderend stellen de auteurs dat C+E een transparanter en controleerbaarder proces biedt voor het visualiseren van geclusterde data, waarbij zowel de interne geometrie van clusters als de relatieve positionering van de clusters zelf wordt behouden, iets wat vaak verloren gaat bij populaire niet-lineaire dimensionaliteitsreductietechnieken.