🤖 machine learning

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

ScaleMAP est une nouvelle méthode de réduction de dimensionnalité qui préserve à la fois la densité locale et la structure du voisinage dans les plongements de faible dimension en normalisant les déplacements par paires avec des rayons locaux, récupérant ainsi efficacement les structures éparses et les larges variations de densité qui sont souvent perdues ou déformées par les techniques existantes telles que UMAP et DensMAP.

Auteurs originaux : Rajas Poorna (Georgia Institute of Technology), Marcus T. Cicerone (Georgia Institute of Technology)

Publié 2026-06-01

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Rajas Poorna (Georgia Institute of Technology), Marcus T. Cicerone (Georgia Institute of Technology)

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous avez une pièce géante et désordonnée remplie de milliers d'objets différents. Certains sont des rochers énormes, d'autres sont de minuscules cailloux, et certains sont des fils délicats reliant deux tas de sable. Votre objectif est de prendre une photo de cette pièce qui puisse tenir sur un petit morceau de papier (une carte en 2D) afin de voir comment tout cela est relié.

Le problème est que les outils que nous utilisons habituellement pour prendre cette photo (appelés UMAP et t-SNE) ont une drôle d'habitude : ils traitent chaque objet comme s'il avait la même taille. Ils écrasent les rochers et étirent les cailloux jusqu'à ce que tout semble avoir à peu près la même taille. C'est très bien pour voir quels objets sont proches les uns des autres, mais cela détruit l'information sur la façon dont les zones sont encombrées ou éparses. C'est comme prendre une photo où une forêt dense et un arbre solitaire semblent tous deux occuper le même espace.

Ce document présente un nouvel outil appelé ScaleMAP qui résout ce problème. Voici comment il fonctionne, en utilisant des analogies simples :

Le Problème : L'effet « Égaliseur »

Les outils existants (comme UMAP) agissent comme un égaliseur audio strict qui force chaque son à avoir le même volume.

Le problème : Si vous avez une foule dense de personnes (un « cluster ») et un groupe de personnes dispersées marchant sur un pont, les anciens outils écrasent la foule et étirent le pont jusqu'à ce qu'ils aient l'air de la même taille.
La conséquence : Vous perdez le « pont ». Dans les données réelles, ces ponts représentent des transitions importantes (comme une cellule changeant de type). Si l'outil écrase le pont, la transition disparaît et les données semblent brisées.

L'ancienne solution : Ajouter une « pénalité »

Un outil précédent appelé DensMAP a tenté de corriger cela en ajoutant une « pénalité » aux calculs. Il disait à l'ordinateur : « Hé, si la foule semble trop petite, écartez-les ! »

La faille : Cette pénalité lutte contre l'objectif principal qui est de maintenir les voisins ensemble. C'est comme essayer de se tenir la main avec un ami pendant que quelqu'un d'autre vous tire constamment dans la direction opposée. Résultat ? La foule est dispersée, et les gens se retrouvent loin de leurs véritables voisins, rendant la carte désordonnée et difficile à lire.

La nouvelle solution : ScaleMAP (L'appareil photo à « zoom variable »)

ScaleMAP adopre une approche différente. Au lieu d'ajouter une pénalité qui combat le système, il change l'objectif de l'appareil photo.

Imaginez que vous marchez dans une ville :

Dans un marché bondé : Vous faites de petits pas car il y a beaucoup de monde.
Dans un parc désert : Vous faites de grandes enjambées car il y a beaucoup de place.

ScaleMAP fait cela mathématiquement. Il regarde à quel point une zone est encombrée dans les données d'origine et dit à la carte : « Si cette zone était encombrée, traitez la distance entre les points comme étant "petite". Si cette zone était vide, traitez la distance comme étant "grande". »

Il dit essentiellement : « Ne changez pas les règles du jeu ; changez simplement la taille du terrain de jeu en fonction de la foule. »

Ce que cela permet d'accomplir

En utilisant cette approche de « zoom variable », ScaleMAP parvient à faire deux choses à la fois que les autres outils ne pouvaient pas faire :

Garder les voisins ensemble : Tout comme UMAP, il garde les amis proches de leurs amis.
Préserver la taille de la foule : Tout comme DensMAP, il garde les foules denses denses et les zones éparses éparses.

Exemples concrets tirés de l'article

Les auteurs ont testé cela sur trois types de « pièces » (jeux de données) :

La « Ville Cellulaire » (Transcriptomique) : Dans les données sur les cellules immunitaires, il existe des « ponts » reliant différents types de cellules (comme un chemin allant d'une cellule bébé à une cellule adulte). UMAP écrase ces chemins si finement qu'ils disparaissent. ScaleMAP maintient le chemin large et visible, montant ainsi le voyage complet de la cellule.
L'« Image Spectrale » (Imagerie hyperspectrale) : Imaginez une image d'un ver où la majeure partie est d'une couleur, mais où il y a un minuscule pic très net d'une autre couleur. UMAP étale ce pic dans l'arrière-plan. ScaleMAP garde ce pic net et distinct, comme une aiguille dans une botte de foin que l'on peut réellement voir.
La « Cytométrie en flux » (Comptage de cellules) : Ces données présentent une gamme immense de densités — certaines zones comptent des millions de cellules, d'autres presque aucune. UMAP et DensMAP sont confus par cette énorme différence. ScaleMAP le gère parfaitement, montrant une structure qui s'étend sur 17 ordres de grandeur (c'est-à-dire comparer la taille d'un grain de sable à celle d'une montagne, le tout sur une seule carte).

L'essentiel

ScaleMAP est une manière plus intelligente de aplatir des données 3D (ou 100D) en une image 2D. Il ne force pas les données à paraître uniformes. Au lieu de cela, il respecte la « taille » naturelle des différents groupes, garantissant que les foules denses restent denses, que les ponts épars restent visibles, et que personne ne se perde dans la foule. Il combine les meilleurs aspects des outils précédents sans leurs effets secondaires désordonnés.

Résumé technique : ScaleMAP

Énoncé du problème
Les méthodes de réduction de dimensionnalité (DR) non linéaires, particulièrement UMAP, PaCMAP et t-SNE, sont des outils standards pour l'analyse exploratoire de données de haute dimension. Ces méthodes construisent des graphes de $k$ -plus proches voisins ( $k$ NN) approximatifs et normalisent les distances locales à l'aide de bandes passantes adaptatives pour gérer les variations de densités locales. Bien que cette normalisation assure la robustesse face aux variations de densité, elle efface par inadvertance l'échelle absolue des voisinages. Par conséquent, ces méthodes ne parviennent pas à préserver les tailles relatives des clusters et suppriment les structures éparses, telles que les ponts entre des types cellulaires en transition, les pics spectraux étroits dans l'imagerie hyperspectrale, ou les variations de densité couvrant de nombreux ordres de grandeur (par exemple, en cytométrie de flux).

Les tentatives existantes pour corriger cela, comme DensMAP, introduisent un terme de pénalité dans la fonction de perte afin de maximiser la corrélation entre les densités locales de l'espace original et de l'espace d'intégration. Cependant, l'article soutient que cette approche crée un objectif concurrent : la pénalité de densité lutte contre les forces d'attraction-répulsion inhérentes à UMAP. Ce conflit disperse les points loin de leurs véritables voisinages, ce qui rend les régions éparses difficiles à interpréter et augmente la fraction de « points déconnectés ».

Méthodologie
ScaleMAP propose une approche différente : plutôt que d'ajouter un terme de perte concurrent, il réintroduit l'information d'échelle par un changement de variables appliqué à la métrique de distance au sein de l'objectif UMAP existant.

Définition du rayon local : ScaleMAP utilise le « rayon local » ( $r_i$ ), une distance racine carrée moyenne pondérée d'un point par rapport à ses voisins dans l'espace original, comme mesure de l'échelle du voisinage.
Distance rescalée : Au lieu d'utiliser la distance euclidienne au carré $d_{ij}^2 = \|y_i - y_j\|^2$ dans la fonction de perte, ScaleMAP définit une distance au carré rescalée :
$\tilde{d}_{ij}^2 = \frac{d_{ij}^2}{r_i r_j}$
où $r_i$ et $r_j$ sont les rayons locaux des deux extrémités.
Modification de la force : Cette substitution modifie le gradient de la perte d'entropie croisée. Les règles de mise à jour des forces attractives (voisins) et répulsives (non-voisins) sont mises à l'échelle par un facteur de $1/(r_i r_j)$ $1/ (r_{i} r_{j})$ .
- Symétrie : Crucialement, le rescalage s'applique de manière symétrique aux forces attractives et répulsives. Cela préserve l'équilibre local qui confère à UMAP ses propriétés de préservation du voisinage.
- Effet : Les points dans les régions éparses (grands $r_i, r_j$ ) subissent des forces plus faibles par unité de déplacement euclidien, ce qui provoque l'étalement de l'intégration. Les points dans les régions denses restent étroitement regroupés.
Normalisation : Pour gérer les échelles de distance indépendantes des données originales et de l'intégration, les rayons locaux sont normalisés à l'aide du 95e percentile ( $P_{95}$ ) de la distribution des rayons avant la substitution.
Extension à PaCMAP : Le même principe est appliqué à PaCMAP (nommé Scale-PaCMAP) en remplaçant la moyenne géométrique des rayons par le produit des échelles de distance par point de PaCMAP ( $\sigma_i \sigma_j$ ).

Contributions clés

Formulation novatrice : L'introduction de ScaleMAP, une modification d'UMAP qui injecte l'information d'échelle locale via un changement de variables plutôt qu'un terme de perte supplémentaire.
Équilibre des performances : Démonstration que ScaleMAP atteint une préservation du voisinage de niveau UMAP tout en égalant ou dépassant DensMAP sur la préservation de la densité, avec nettement moins de points dispersés (déconnectés).
Récupération de structure : Récupération réussie des structures éparses que UMAP réduit (ex: ponts transcriptomiques) et préservation des structures de densité multi-échelles (ex: données de cytométrie de flux couvrant 17 ordres de grandeur).
Généralisabilité : Preuve que le principe de changement de variables se généralise à d'autres méthodes, spécifiquement PaCMAP.

Résultats
Les auteurs ont évalué ScaleMAP sur des benchmarks standards (MNIST, Fashion-MNIST, COIL-20, Mammoth) et trois jeux de données scientifiques (transcriptomique Tabula Sapiens, imagerie hyperspectrale BCARS et cytométrie de flux de moelle osseuse humaine).

Métriques quantitatives :
- Préservation de la densité : ScaleMAP atteint une préservation de la densité (ajustement log-log $R^2$ ) comparable à DensMAP sur la plupart des jeux de données (ex: $R^2 \approx 0,51$ sur Fashion-MNIST contre $0,58$ pour DensMAP). Sur les jeux de données avec des plages dynamiques extrêmes, ScaleMAP surpasse DensMAP (ex: Cytométrie de flux : $R^2 = 0,80$ contre $0,68$ pour DensMAP ; Imagerie hyperspectrale : $R^2 = 0,81$ contre $0,59$ pour DensMAP).
- Préservation du voisinage : ScaleMAP maintient un rappel kNN comparable à UMAP (ex: 14,3 % contre 13,3 % pour UMAP sur Fashion-MNIST) et nettement meilleur que DensMAP (7,1 %).
- Points déconnectés : ScaleMAP maintient la fraction de points déconnectés faible et comparable à UMAP (ex: 0,19 % contre 0,11 % pour UMAP), tandis que DensMAP présente un ordre de grandeur de plus en points déconnectés (3,48 %).
- Mélange de classes : ScaleMAP réduit le mélange de classes par rapport aux deux bases de référence.
Observations qualitatives :
- Transcriptomique : ScaleMAP récupère les ponts éparses entre les populations cellulaires (ex: monocytes-neutrophiles, cellules B-T) qui sont effondrés ou invisibles dans UMAP.
- Imagerie hyperspectrale : Il révèle des pics spectraux éparses et de petits clusters que UMAP comprime ou absorbe dans le bruit de fond.
- Cytométrie de flux : Il représente fidèlement la structure multi-échelle sur 17 ordres de grandeur, préservant un « bulbe » dense de cellules marqueur-négatives qui apparaît comme une infime caractéristique dans l'intégration, contrairement à UMAP/DensMAP qui manquent de cette fidélité multi-échelle.
- Diagnostics synthétiques : Sur les jeux de données « XOI » et « Bridge », ScaleMAP préserve correctement les tailles relatives et les connexions éparses, alors que DensMAP déforme les formes et disperse les points.

Signification et affirmations
L'article affirme que ScaleMAP représente une amélioration fondamentale de la manière dont les intégrations préservant le voisinage gèrent l'échelle. En traitant le rescalage comme un changement de variables plutôt que comme un objectif concurrent, ScaleMAP évite le compromis entre la fidélité de la densité et l'intégrité du voisinage qui affecte DensMAP.

Les auteurs affirment que ScaleMAP est la seule méthode testée qui ne sacrifie pas un axe de qualité de l'intégration au profit d'un autre : il conserve la préservation du voisinage d'UMAP, égale la fidélité de densité de DensMAP, et améliore la préservation de l'ordre des distances globales (surpassant PaCMAP sur les jeux de données avec de larges plages dynamiques). L'article conclut que la restauration de l'échelle locale est un ingrédient manquant général dans les intégrations préservant le voisinage et suggère ScaleMAP comme méthode par défaut lorsque la représentation fidèle de l'échelle est critique. L'approche est notée comme étant efficace sur le plan computationnel, n'ajoutant qu'un surcoût de $O(n)$ pour le précalcul des rayons, avec un temps d'exécution total environ deux fois supérieur à celui de UMAP.