🤖 machine learning

ScaleMAP: Preserving Local Density and Neighborhood Structure in Low-Dimensional Embeddings

ScaleMAP ist eine neuartige Methode zur Dimensionsreduktion, die sowohl die lokale Dichte als auch die Nachbarschaftsstruktur in niedrigdimensionalen Einbettungen bewahrt, indem sie paarweise Abstände mit lokalen Radien normalisiert und so dünn besiedelte Strukturen sowie weite Dichtevariationen effektiv wiederherstellt, die in bestehenden Techniken wie UMAP und DensMAP oft verloren gehen oder verzerrt werden.

Ursprüngliche Autoren: Rajas Poorna (Georgia Institute of Technology), Marcus T. Cicerone (Georgia Institute of Technology)

Veröffentlicht 2026-06-01

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Rajas Poorna (Georgia Institute of Technology), Marcus T. Cicerone (Georgia Institute of Technology)

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 hätten ein riesiges, unordentliches Zimmer voller tausender verschiedener Objekte. Einige sind riesige Felsbrocken, einige sind winzige Kieselsteine und einige sind zarte Fäden, die zwei Sandhaufen verbinden. Ihr Ziel ist es, ein Foto von diesem Raum zu machen, das auf ein kleines Stück Papier (eine 2D-Karte) passt, damit Sie sehen können, wie alles miteinander in Beziehung steht.

Das Problem ist, dass die Werkzeuge, die wir normalerweise verwenden, um ein solches Foto zu machen (genannt UMAP und t-SNE), eine seltsame Angewohnheit haben: Sie behandeln jedes Objekt so, als wäre es gleich groß. Sie stauchen die Felsbrocken zusammen und dehnen die Kieselsteine aus, bis alles etwa die gleiche Größe hat. Das ist großartig, um zu sehen, welche Objekte nah beieinander liegen, aber es zerstört die Information darüber, wie gedrängt oder dünn besiedelt verschiedene Bereiche sind. Es ist wie ein Foto, bei dem ein dichter Wald und ein einzelner einsamer Baum beide den gleichen Platz einzunehmen scheinen.

Dieses Paper stellt ein neues Werkzeug namens ScaleMAP vor, das dieses Problem löst. So funktioniert es, unter Verwendung einfacher Analogien:

Das Problem: Der „Equalizer“-Effekt

Bestehende Werkzeuge (wie UMAP) wirken wie ein strenger Audio-Equalizer, der jede Lautstärke auf das gleiche Niveau zwingt.

Das Problem: Wenn Sie eine dichte Menschenmenge (einen „Cluster“) haben und eine dünne Gruppe von Menschen, die über eine Brücke läuft, stauchen die alten Werkzeuge die Menge zusammen und dehnen die Brücke aus, bis sie gleich groß aussehen.
Die Konsequenz: Sie verlieren die „Brücke“. In echten Daten repräsentieren diese Brücken wichtige Übergänge (wie eine Zelle, die sich von einem Typ zu einem anderen verändert). Wenn das Werkzeug die Brücke zusammendrückt, verschwindet der Übergang, und die Daten wirken fehlerhaft.

Die alte Lösung: Das Hinzufügen einer „Strafe“

Ein früheres Werkzeug namens DensMAP versuchte, dieses Problem zu lösen, indem es eine „Strafe“ in die Mathematik einbaute. Es sagte dem Computer: „Hey, wenn die Menge zu klein aussieht, drücke sie auseinander!“

Der Fehler: Diese Strafe arbeitet gegen das Hauptziel, Nachbarn beieinander zu halten. Es ist, als würde man versuchen, Händchen mit einem Freund zu halten, während jemand anderes einen ständig in die entgegengesetzte Richtung zieht. Das Ergebnis? Die Menge wird zerstreut, und die Leute landen weit weg von ihren eigentlichen Nachbarn, was die Karte unordentlich und schwer lesbar macht.

Die neue Lösung: ScaleMAP (Die Kamera mit „variablem Zoom“)

ScaleMAP verfolt einen anderen Ansatz. Anstatt eine Strafe hinzuzufügen, die dem System entgegenwirkt, ändert es die Linse der Kamera.

Stellen Sie sich vor, Sie gehen durch eine Stadt:

In einem überfüllten Markt: Machen Sie kleine Schritte, weil so viele Menschen da sind.
In einem leeren Park: Machen Sie riesige Sprünge, weil viel Platz vorhanden ist.

ScaleMAP macht dies mathematisch. Es schaut darauf, wie überfüllt ein Bereich im Originaldatensatz ist, und sagt der Karte: „Wenn dieser Bereich überfüllt war, behandle den Abstand zwischen den Punkten als ‚klein‘. Wenn dieser Bereich leer war, behandle den Abstand als ‚groß‘.“

Es sagt im Grunde: „Ändere nicht die Regeln des Spiels; ändere nur die Größe des Spielfelds basierend auf der Menge.“

Was dies erreicht

Durch diesen „variablen Zoom“-Ansatz schafft es ScaleMAP, zwei Dinge gleichzeitig zu tun, die andere Werkzeuge nicht konnten:

Nachbarn zusammenhalten: Genau wie UMAP hält es Freunde nah bei ihren Freunden.
Die Größe der Menge bewahren: Genau wie DensMAP sorgt es dafür, dass dichte Mengen dicht aussehen und dünn besiedelte Bereiche dünn besiedelt aussehen.

Reale Beispiele aus dem Paper

Die Autoren haben dies an drei Arten von „Räumen“ (Datensätzen) getestet:

Die „Zelluläre Stadt“ (Transkriptomik): In Daten über Immunzellen gibt es „Brücken“, die verschiedene Zelltypen verbinden (wie einen Pfad von einer Baby-Zelle zu einer erwachsenen Zelle). UMAP staucht diese Pfade so sehr zusammen, dass sie verschwinden. ScaleMAP hält diesen Pfad breit und sichtbar und zeigt die gesamte Reise der Zelle.
Das „Spektralbild“ (Hyperspektrale Bildgebung): Stellen Sie sich ein Bild eines Wurms vor, bei dem der Großteil eine einzige Farbe hat, aber es gibt einen winzigen, scharfen Ausschlag einer anderen Farbe. UMAP verschmiert diesen Ausschlag in den Hintergrund. ScaleMAP hält diesen Ausschlag scharf und deutlich, wie eine Nadel im Heuhaufen, die man tatsächlich sehen kann.
Die „Durchflusszytometrie“ (Zellzählung): Diese Daten haben einen massiven Bereich an Dichten – einige Bereiche haben Millionen von Zellen, andere fast gar keine. UMAP und DensMAP werden durch diesen riesigen Unterschied verwirrt. ScaleMAP bewältigt dies perfekt und zeigt eine Struktur, die 17 Größenordnungen abdeckt (das ist so, als würde man die Größe eines Sandkorns mit der eines Berges vergleichen, alles auf einer einzigen Karte).

Das Fazit

ScaleMAP ist eine intelligentere Art, 3D- (oder 100D-) Daten in ein 2D-Bild zu projizieren. Es erzwingt keine Gleichförmigkeit der Daten. Stattdessen respektiert es die natürliche „Größe“ verschiedener Gruppen und stellt sicher, dass dichte Mengen dicht bleiben, dünne Brücken sichtbar bleiben und niemand in der Menge verloren geht. Es kombiniert die besten Teile früherer Werkzeuge, ohne deren unordentliche Nebenwirkungen.

Technisches Resümee: ScaleMAP

Problemstellung
Nichtlineare Methoden zur Dimensionsreduktion (DR), insbesondere UMAP, PaCMAP und t-SNE, sind Standardwerkzeuge für die explorative Analyse hochdimensionaler Daten. Diese Methoden konstruieren approximative $k$ -nächste-Nachbarn-Graphen (kNN-Graphen) und normalisieren lokale Distanzen mittels adaptiver Bandbreiten, um Variationen in der lokalen Dichte zu bewältigen. Während diese Normalisierung die Robustheit gegenüber Dichtevariationen sicherstellt, löscht sie unbeabsichtigt die absolute Skala der Nachbarschaften aus. Infolgedessen versagen diese Methoden dabei, die relativen Größen von Clustern zu bewahren und spärliche Strukturen – wie etwa Brücken zwischen Übergangszelltypen, schmale spektrale Spitzen in hyperspektralen Bildern oder Dichtevariationen, die viele Größenordnungen umfassen (z. B. in der Durchflusszytometrie) – darzustellen.

Bestehende Versuche, dies zu korrigieren, wie etwa DensMAP, führen einen Strafterm in die Verlustfunktion ein, um die Korrelation zwischen den lokalen Dichten im Originalraum und im Einbettungsraum zu maximieren. Das Paper argumentiert jedoch, dass dieser Ansatz ein konkurrierendes Ziel einführt: Der Dichtestrafterm bekämpft die inhärenten Anziehungs- und Abstoßungskräfte von UMAP. Dieser Konflikt streut Punkte von ihren wahren Nachbarschaften weg, was zu einem hohen Anteil an „diskonnektierten Punkten“ führt und spärliche Regionen schwer interpretierbar macht.

Methodik
ScaleMAP schlägt einen anderen Ansatz vor: Anstatt einen konkurrierenden Verlustterm hinzuzufügen, wird die Skaleninformation durch einen Wechsel der Variablen (Change of Variables) wieder eingeführt, der auf die Distanzmetrik innerhalb der bestehenden UMAP-Zielformulierung angewendet wird.

Definition des lokalen Radius: ScaleMAP nutzt den „lokalen Radius“ ( $r_i$ ), eine gewichtete Wurzel-Mittelwert-Quadrat-Distanz eines Punktes zu seinen Nachbarn im Originalraum, als Maß für die lokale Skala.
Reskalierte Distanz: Anstatt der euklidischen quadrierten Distanz $d_{ij}^2 = \|y_i - y_j\|^2$ in der Verlustfunktion verwendet ScaleMAP eine reskalierte quadrierte Distanz:
$\tilde{d}_{ij}^2 = \frac{d_{ij}^2}{r_i r_j}$
wobei $r_i$ und $r_j$ die lokalen Radien der beiden Endpunkte sind.
Kraftmodifikation: Diese Substitution modifiziert den Gradienten der Kreuzentropie-Verlustfunktion. Die Aktualisierungsregeln für sowohl attraktive (Nachbarn) als auch repulsive (Nicht-Nachbarn) Kräfte werden um einen Faktor von $1/(r_i r_j)$ $1/ (r_{i} r_{j})$ skaliert.
- Symmetrie: Entscheidend ist, dass die Reskalierung symmetrisch auf sowohl attraktive als als auch repulsive Kräfte angewendet wird. Dies bewahrt das lokale Gleichgewicht, das die Nachbarschaftserhaltungseigenschaften von UMAP ermöglicht.
- Effekt: Punkte in spärlichen Regionen (großes $r_i, r_j$ ) erfahren pro Einheit euklidischer Verschiebung schwächere Kräfte, was dazu führt, dass die Einbettung sie auseinanderzieht. Punkte in dichten Regionen bleiben eng gepackt.
Normalisierung: Um die unabhängigen Distanzskalen der Originaldaten und der Einbettung zu handhaben, werden die lokalen Radien unter Verwendung des 95. Perzentils ( $P_{95}$ ) der Radienverteilung vor der Substitution normalisiert.
Erweiterung auf PaCMAP: Dasselbe Prinzip wird auf PaCMAP angewendet (bezeichnet als Scale-PaCMAP), indem das geometrische Mittel der Radien durch das Produkt der PaCMAP-pro-Punkt-Distanzskalen ( $\sigma_i \sigma_j$ ) ersetzt wird.

Kernbeiträge

Neuartige Formulierung: Die Einführung von ScaleMAP, einer Modifikation von UMAP, die lokale Skaleninformationen durch einen Wechsel der Variablen statt durch einen zusätzlichen Verlustterm injiziert.
Leistungsbalance: Der Nachweis, dass ScaleMAP eine UMAP-ähnliche Nachbarschaftserhaltung erreicht und gleichzeitig DensMAP in der Dichteerhaltung entspricht oder dieses übertrifft, wobei signifikant weniger gestreute („diskonnektierte“) Punkte auftreten.
Strukturrekonstruktion: Erfolgreiche Rekonstruktion spärlicher Strukturen, die UMAP kollabieren lässt (z. B. transkriptomische Brücken), sowie die Bewahrung multiskalarer Dichtestrukturen (z. B. Durchflusszytometrie-Daten, die 17 Größenordnungen umfassen).
Generalisierbarkeit: Beleg dafür, dass sich das Prinzip des Variablenwechsels auf andere Methoden, spezifisch PaCMAP, verallgemeinern lässt.

Ergebnisse
Die Autoren evaluierten ScaleMAP anhand von Standard-Benchmarks (MNIST, Fashion-MNIST, COIL-20, Mammoth) und drei wissenschaftlichen Datensätzen (Tabula Sapiens Transkriptomik, BCARS Hyperspektralbildgebung und menschliche Knochenmark-Durchflusszytometrie).

Quantitative Metriken:
- Dichterhaltung: ScaleMAP erreicht eine Dichterhaltung ( $R^2$ des Log-Log-Fits) vergleichbar mit DensMAP über die meisten Datensätze hinweg (z. B. $R^2 \approx 0,51$ auf Fashion-MNIST gegenüber $0,58$ bei DensMAP). Auf Datensätzen mit extremen Dynamikbereichen übertrifft ScaleMAP DensMAP (z. B. Durchflusszytometrie: $R^2 = 0,80$ vs. $0,68$; Hyperspektralbildgebung: $R^2 = 0,81$ vs. $0,59$).
- Nachbarschaftserhaltung: ScaleMAP hält eine kNN-Recall vergleichbar mit UMAP (z. B. 14,3 % gegenüber 13,3 % bei UMAP auf Fashion-MNIST) und ist signifikant besser als DensMAP (7,1 %).
- Diskonnektierte Punkte: ScaleMAP hält den Anteil diskonnektierter Punkte niedrig und vergleichbar mit UMAP (z. B. 0,19 % gegenüber 0,11 % bei UMAP), während DensMAP einen um eine Größenordnung höheren Anteil diskonnektierter Punkte aufweist (3,48 %).
- Klassenmischung: ScaleMAP reduziert die Klassenmischung im Vergleich zu beiden Baselines.
Qualitative Beobachtungen:
- Transkriptomik: ScaleMAP rekonstruiert spärliche Brücken zwischen Zellpopulationen (z. B. Monozyten-Neutrophile, B-T-Zellen), die in UMAP kollabieren oder unsichtbar sind.
- Hyperspektralbildgebung: Es offenbart spärliche spektrale Spitzen und kleine Cluster, die UMAP komprimiert oder im Hintergrund absorbiert.
- Durchflusszytometrie: Es stellt die multiskalare Struktur über 17 Größenordnungen getreu dar und bewahrt eine dichte „Bulbus“-Struktur von Marker-negativen Zellen, die in der Einbettung als winziges Merkmal erscheint, im Gegensatz zu UMAP/DensMAP, denen es an dieser multiskalaren Treue mangelt.
- Synthetische Diagnostika: Auf „XOI“- und „Bridge“-Datensätzen bewahrt ScaleMAP korrekt die relativen Größen und spärlichen Verbindungen, während DensMAP Formen verzerrt und Punkte streut.

Bedeutung und Behauptungen
Das Paper behauptet, dass ScaleMAP eine fundamentale Verbesserung darstellt, wie nachbarschaftserhaltende Einbettungen mit Skalen umgehen. Indem ScaleMAP die Reskalierung als Wechsel der Variablen statt als konkurrierendes Ziel behandelt, vermeidet es den Trade-off zwischen Dichtetreue und Nachbarschaftsintegrität, der DensMAP belastet.

Die Autoren behaupten, dass ScaleMAP die einzige getestete Methode ist, die nicht eine Achse der Einbettungsqualität zugunsten einer anderen opfert: Es behält die Nachbarschaftserhaltung von UMAP bei, erreicht die Dichtetreue von DensMAP und verbessert die Bewahrung der globalen Distanzordnung (es übertrifft PaCMAP auf Datensätzen mit weiten Dynamikbereichen). Das Paper kommt zu dem Schluss, dass die Wiederherstellung der lokalen Skala eine allgemeine, fehlende Komponente in nachbarschaftserhaltenden Einbettungen ist, und schlägt ScaleMAP als Standardmethode vor, wenn die getreue Darstellung der Skala kritisch ist. Der Ansatz wird als recheneffizient beschrieben, mit einem zusätzlichen Overhead von nur $O(n)$ für die Vorberechnung der Radien und einer Gesamtlaufzeit, die etwa doppelt so hoch wie die von UMAP ist.