📊 statistics

Cluster and then Embed: A Modular Approach for Visualization

Dieses Paper schlägt ein transparentes, modulares Visualisierungsframework vor, das Methoden wie t-SNE und UMAP dadurch verbessert, dass es die Daten sequenziell clustert, jeden Cluster einzeln einbettet und diese anschließend ausrichtet, um sowohl die lokale Struktur als auch die globale Geometrie zu bewahren.

Ursprüngliche Autoren: Elizabeth Coda, Ery Arias-Castro, Gal Mishne

Veröffentlicht 2026-07-13

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Elizabeth Coda, Ery Arias-Castro, Gal Mishne

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie haben eine riesige, unordentliche Kiste mit 3D-LEGO-Skulpturen. Einige sind winzige, filigrane Schlösser; andere sind weitläufige, flache Städte. Ihr Ziel ist es, von allen Fotos zu machen und sie auf einem flachen 2D-Tisch auszulegen, damit Sie sehen können, wie sie zueinander in Beziehung stehen.

Das Problem? Wenn Sie die ganze Kiste auf einmal auf den Tisch quetschen, werden die flachen Städte zerquetscht, und die Schlösser überlappen sich zu einem riesigen, verwirrenden Klumpen. Dies ist das „Crowding-Problem“, das populäre Werkzeuge wie t-SNE und UMAP plagt. Diese sind großartig darin, die winzigen Details jedes einzelnen Schlosses zusammenzuhalten, aber sie verzerren oft die Karte, sodass ferne Schlösser so aussehen, als lägen sie direkt nebeneinander.

Hier kommt der Cluster+Embed (C+E) Ansatz ins Spiel, eine neue Methode, die von Elizabeth Coda, Ery Arias-Castro und Gal Mishne vorgeschlagen wurde. Betrachten Sie diese Methode nicht als eine einzige magische Kamera, sondern als ein dreistufiges Fließband, das Ihre Daten wie eine Sammlung von unterschiedlichen Nachbarschaften behandelt.

Schritt 1: Die Sortierung der Nachbarschaften

Zuerst versucht die Methode nicht, die ganze Kiste auf einmal zu fotografieren. Stattdessen agiert sie wie ein super organisierter Bibliothekar, der die LEGO-Skulpturen basierend auf ihrer Form in separate Stapel sortiert. Wenn Sie einen Stapel Schlösser und einen Stapel Städte haben, werden diese in verschiedene Behälter getrennt. Die Autoren merken an, dass Sie jede beliebige Sortierungsmethode verwenden können (wie die populären Leiden- oder DBSCAN-Algorithmen), aber der entscheidende Punkt ist, dass Sie die Gruppen vor dem Fotografieren definieren.

Schritt 2: Die individuellen Fotos

Als Nächstes macht die Methode von jedem Stapel einzeln ein Foto. Da der Bibliothekar immer nur einen Stapel Schlösser zur Zeit betrachtet, kann er die Schlösser perfekt anordnen, um ihre filigranen Details zu zeigen, ohne dass sich die Städte in den Weg stellen. Dieser Schritt verwendet Standardwerkzeuge (wie PCA oder TriMap), um nur diese eine Gruppe zu ebnen. Das Ergebnis? Ein kristallklares, hochwertiges Foto der Schlösser und ein separates, ebenso klares Foto der Städte.

Schritt 3: Die globale Karte

Hier ist der clevere Teil. Jetzt haben Sie einen Stapel perfekter, separater Fotos. Im letzten Schritt kleben Sie diese Fotos auf eine riesige Wand, um eine große Karte zu erstellen. Aber anstatt sie einfach zufällig aufzukleben, nutzt die Methode eine „starre Transformation“ – stellen Sie sich vor, Sie nehmen ein ganzes Foto des Schloss-Stapels auf, schieben es, drehen es oder spiegeln es, aber niemals das Foto selbst zu dehnen oder zu quetschen.

Das Ziel ist es, diese Stapel so zu positionieren, dass der Abstand zwischen dem „Schloss-Stapel“ und dem „Städte-Stapel“ auf der Wand dem Abstand entspricht, den sie in der ursprüngigen Kiste hatten. Um das Crowding-Problem zu lösen (bei dem auf der Wand nicht genug Platz für alles ist), führt die Methode einen „Skalierungsregler“ (genannt $\alpha$ ) ein. Wenn die Stapel zu nah beieinander liegen und sich überlappen könnten, schlagen die Autoren vor, diesen Regler zu betätigen, um die Stapel sanft auseinanderzuschieben und so gerade genug Platz zu schaffen, damit jeder klar gesehen werden kann, ohne die internen Details der Fotos zu verzerren.

Wogegen diese Methode „Nein“ sagt

Die Autoren sind sich sehr klar darüber, wogegen sie kämpfen. Sie argumentieren gegen die Vorstellung, dass ein einziges All-in-One-Werkzeug (wie t-SNE oder UMAP) zwei widersprüchliche Dinge gleichzeitig perfekt tun kann: die winzigen lokalen Details perfekt zu bewahren und die globalen Distanzen genau zu halten. Sie zeigen, dass t-SNE zwar großartig darin ist, Cluster zu trennen, aber die „Karte“ oft so stark verzerrt, dass man den Abständen zwischen den Gruppen nicht trauen kann. Sie schließen auch explizit die Idee aus, dass man einfach einen hierarchischen Baum auf eine Karte erzwingen kann, ohne einen strukturierten Prozess zu nutzen; ihre Methode ist eine bewusste, transparente dreistufige Pipeline, kein Blackbox-Verfahren.

Wie sicher sind sie sich?

Die Autoren behaupten nicht, dass dies ein magisches Heilmittel ist, das alles für immer löst. Stattdessen präsentieren sie starke Beweise aus Simulationen und Realdaten.

Auf synthetischen Daten: Sie testeten ihre Methode an einem 10-dimensionalen Gaußschen Mischmodell mit 5.000 Punkten. In diesen Simulationen zeigten sie, dass ihre Methode mit einem Skalierungsfaktor von $\alpha = 2$ das Überlappen vermeidet, das andere Methoden plagte, und so einen Ring aus Clustern erzeugte, der dem von t-SNE sehr ähnlich sah, aber durch einen transparenten, kontrollierbaren Prozess erreicht wurde.
Auf Realdaten: Sie wandten dies auf drei Datensätze an:
1. MNIST (Handschriftliche Ziffern): Ein Datensatz von 60.000 Bildern. Hier trennte C+E die Ziffern erfolgreich in Gruppen (wie etwa Vierer und Neuner, die nah beieinander liegen) und bewahrte die globale Struktur besser als t-SNE, welches dazu neigt, alles gleichmäßig zu verteilen.
2. Humane Gehirn-Organoide: Ein Datensatz von 20.272 Zellen. Die Methode enthüllte eine klare „Entwicklungs-Trajektorie“ (einen Pfad des Wachstums über die Zeit), die in ihrer Karte sichtbar war, in t-SNE und UMAP jedoch eher „diskret“ und weniger kontinuierlich erschien.
3. Maus-Cortex: Ein Datensatz von 23.822 Zellen. Hier enthüllte C+E eine „Grob-zu-Fein“-Struktur (große Gruppen, die sich in kleinere aufteilen), die andere Methoden übersehen haben.

Die Autoren geben zu, dass es einen Kompromiss gibt. Während C+E exzellent darin ist, globale Distanzen und lokale Formen zu bewahren, hat es manchmal Schwierigkeiten, die Fähigkeit von t-SNE zu erreichen, die absolut nächsten Nachbarn (kNN Recall) für kleine Werte von $k$ perfekt abzubilden. Sie deuten an, dass dies daran liegt, dass t-SNE eine mysteriöse Art hat, Daten in winzige Patches aufzubrechen, was C+E nicht repliziert. Sie argumentieren jedoch, dass für eine Visualisierung, die sowohl transparent als auch der Gesamtsform der Daten treu ist, C+E eine hochkompetitive und viel verständlichere Alternative darstellt.

Kurz gesagt legt das Paper nahe, dass wir durch das Aufteilen des Problems in „Sortieren, Ebnen, dann Ausrichten“ eine Karte erhalten können, die nicht lügt, wo die Dinge liegen, auch wenn es ein paar mehr Schritte braucht, um dorthin zu gelangen.

Technisches Resümee: Cluster und dann Embed: Ein modularer Ansatz zur Visualisierung

Problemstellung

Dimensionsreduktionsmethoden, insbesondere t-SNE und UMAP, werden weit verbreitet zur Visualisierung hochdimensionaler Daten mit latenten Clustereigenschaften eingesetzt. Obwohl diese Methoden Datenpunkte effektiv gruppieren und lokale Informationen bewahren, sind sie dafür bekannt, die globale Geometrie der zugrunde liegenden Daten zu verzerren. Speziell versagen sie oft dabei, die relativen Positionen, Abstände und Größen verschiedener Cluster zu bewahren. Diese Einschränkung resultiert aus dem „Crowding-Problem“, bei dem niedrigdimensionale Einbettungsräume nicht über genügend Kapazität verfügen, um alle Punkte auf ihren ursprünglichen hochdimensionalen Distanzskalen unterzubringen, was zum Kollaps entfernter Punkte und zur Überlappung distinkter Cluster führt. Bestehende Methoden erzwingen oft einen Kompromiss zwischen der Bewahrung lokaler Strukturen (Trennung von Clustern) und der Bewahrung globaler Distanzen.

Methodik: Das Cluster+Embed (C+E) Framework

Die Autoren schlagen ein modulares, dreistufiges Framework namens Cluster+Embed (C+E) vor, um den Zielkonflikt zwischen lokaler und globaler Treue zu adressieren. Der Ansatz entkoppelt Clustering, lokale Einbettung und globale Ausrichtung, wodurch der Analyst in der Lage ist, für jede Stufe spezifische Algorithmen basierend auf seinen Visualisierungszielen auszuwählen.

Schritt 1: Clustering

Die Daten $\{x_i\}_{i=1}^n$ werden zunächst in $\kappa$ Cluster ( $C_1, \dots, C_\kappa$ ) unter Verwendung eines beliebigen gewählten Clustering-Algorithmus (z. B. Leiden, DBSCAN, k-means) partitioniert. Dieser Schritt macht die im Datensatz vorhandene Clusterstruktur explizit sichtbar. Als Rauschen identifizierte Punkte können in dieser Phase verworfen werden.

Schritt 2: Individuelle Cluster-Einbettung

Jeder Cluster $C_l$ wird separat in einen niedrigdimensionalen Raum (typischerweise $\mathbb{R}^2$ ) eingebettet, wobei eine gewählte Einbettungsmethode (z. B. PCA, Isomap, TriMap) verwendet wird.

Begründung: Die separate Einbettung von Clustern reduziert die Verzerrung im Vergleich zur Einbettung des gesamten Datensatzes auf einmal, da das „Crowding-Problem“ innerhalb kleinerer, lokalisierter Teilmengen gemildert wird.
Skalierung: Wenn die Einbettungsmethode auf ordinalen Informationen basiert, wird ein Skalierungsfaktor $\gamma_l$ auf jeden Cluster angewendet, um den quadratischen Verlust zwischen eingebetteten Distanzen und ursprünglichen Unähnlichkeiten zu minimieren.

Schritt 3: Globale Ausrichtung

Die eingebetteten Cluster werden unter Verwendung rein starrer Transformationen (Translationen, Rotationen und Reflexionen) in eine einzige globale Einbettung ausgerichtet. Das Ziel ist es, die Cluster so zu positionieren, dass die paarweisen Unähnlichkeiten zwischen Punkten in verschiedenen Clustern so getreu wie möglich bewahrt werden.

Optimierung: Die Ausrichtung minimiert eine Stressfunktion (Kruskal-Stress), definiert 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$
wobei $\delta_{lm}$ die ursprüngliche Unähnlichkeit ist und $T$ für starre Transformationen steht.
Crowding-Minderung durch Skalierung ( $\alpha$ ): Um Überlappungen in der finalen Visualisierung zu verhindern, führen die Autoren einen Tuning-Parameter $\alpha \ge 1$ $α \geq 1$ ein. Die Zieldistanz zwischen Clustern wird auf $\alpha \delta_{lm}$ $α δ_{l m}$ skaliert. Dies bläht den Raum zwischen den Clustern in der niedrigdimensionalen Karte effektiv auf und verhindert so das Crowding-Problem.
- $\alpha$ kann manuell oder automatisch abgestimmt werden. Eine automatische Heuristik wird vorgeschlagen: $\alpha = \max(1, \frac{\kappa \tau}{2\pi \Delta})$ , wobei $\tau$ der durchschnittliche Clusterdurchmesser und $\Delta$ die durchschnittliche Inter-Cluster-Distanz ist.

Zentrale Beiträge

Modulares Framework: Die Arbeit führt einen transparenten, modularen Ansatz ein, bei dem Clustering, Einbettung und Ausrichtung distinkte Schritte sind. Dies ermöglicht es Nutzern, spezifische Algorithmen für jede Stufe zu wählen, um gezielt bestimmte Visualisierungseigenschaften zu steuern (z. B. TriMap für kNN-Recall oder PCA für Distanzbewahrung).
Explizite Kontrolle über die globale Geometrie: Im Gegensatz zu t-SNE und UMAP, die die globale Struktur implizit und oft opak über kraftgesteuerte Dynamiken handhaben, optimiert C+E die inter-cluster Distanzen explizit über starre Ausrichtung.
Lösung des Crowding-Problems: Die Methode adressiert das Crowding-Problem nicht durch Änderung des Kernels (wie t-SNE mit dem Cauchy-Kernel), sondern durch die explizite Skalierung der Inter-Cluster-Distanzen via des Parameters $\alpha$ , wodurch sichergestellt wird, dass sich distinkte Cluster nicht überlappen, während ihre relative Organisation erhalten bleibt.
Transparenz: Der Ansatz ist interpretierbarer als End-to-End-Methoden, da die Bewahrung der lokalen Struktur (innerhalb von Clustern) und der globalen Struktur (zwischen Clustern) durch separate, kontrollierbare Mechanismen gehandhabt wird.

Experimentelle Ergebnisse

Die Autoren evaluierten C+E auf synthetischen und realen Datensätzen (MNIST, menschliche Organoid-Daten, Maus-Cortex-Daten) gegenüber Baselines wie t-SNE, UMAP, PCA, Isomap, PHATE und TriMap.

Synthetischer Shapes-Datensatz: C+E erreichte perfekte lokale Metriken (Rekonstruktion exakter Cluster-Konfigurationen) und bewahrte die globale Orientierung, während t-SNE und UMAP signifikante lokale Verzerrungen aufwiesen.
MNIST: C+E trennte Cluster erfolgreich und organisierte sie in sinnvolle Gruppierungen (z. B. Zusammenfassung ähnlicher Ziffern). Während t-SNE einen überlegenen kNN-Recall für kleine $k$ zeigte, übertraf C+E t-SNE und UMAP bei globalen Metriken (Klassenerhaltung und Inter-Cluster-Distanzbewahrung).
Menschliche Organoid-Daten: C+E-Einbettungen offenbarten eine klare zeitliche Entwicklungsbahn und distinkte Zelltyp-Gruppierungen. Es bewahrte globale Metriken, die vergleichbar mit oder besser als PCA und L-Isomap waren, bot jedoch eine verbesserte lokale Struktur und weniger Kollaps als t-SNE oder UMAP.
Maus-Cortex-Daten: C+E offenbarte eine grob-zu-fein Struktur (Trennung von inhibitorischen/exzitatorischen Neuronen und Nicht-Neuronen), die bei anderen Methoden nicht vorhanden war. Obwohl die Skala der Einbettung aufgebläht wurde (was zu höherem normalisiertem Stress führte), favorisierten skaleninvariante globale Metriken C+E gegenüber UMAP und t-SNE.

Bedeutung und Behauptungen

Das Paper behauptet, dass C+E eine wettbewerbsfähige Alternative zu bestehenden Visualisierungsmethoden bietet, indem es ein Gleichgewicht zwischen treuer lokaler Einbettung und einer treuen globalen Organisation herstellt.

Management des Zielkonflikts: Die Methode erkennt den inhärenten Trade-off zwischen lokaler und globaler Bewahrung an, bietet aber einen Mechanismus (den Parameter $\alpha$ ), um diesen Konflikt explizit zu steuern.
Flexibilität: Das Framework erlaubt es Nutzern, spezifische Metriken zu priorisieren (z. B. kNN-Recall via TriMap oder Distanzbewahrung via PCA), ohne die globale Anordnung der Cluster zu opfern.
Limitierungen: Die Autoren merken bescheiden an, dass t-SNE weiterhin der Goldstandard für die Maximierung des kNN-Recalls für kleine $k$ bleibt. Sie schlagen vor, dass der kNN-Recall von C+E durch Erhöhung von $\alpha$ oder die Erstellung von mehr Clustern verbessert werden kann, was jedoch das Risiko birgt, künstliche Cluster zu erzeugen. Die Rechenkomplexität des Alignment-Schritts skaliert quadratisch mit der Anzahl der Punkte, wobei Subsampling-Strategien zur Milderung eingesetzt werden.

Zusammenfassend argumentieren die Autoren, dass C+E einen transparenteren und kontrollierbaren Ansatz zur Visualisierung geclusterter Daten bietet, der sowohl die interne Geometrie der Cluster als auch die relative Positionierung der Cluster selbst bewahrt – eine Eigenschaft, die in populären nichtlinearen Dimensionsreduktionstechniken oft verloren geht.