MDS (Multi-Dimensional Scaling) : Guide complet — Principes, Exemples et Implémentation Python

Résumé

Le MDS (Multi-Dimensional Scaling), ou mise à l’échelle multidimensionnelle, est une famille de techniques de réduction de dimensionalité non supervisée dont l’objectif central est de projeter des données dans un espace de faible dimension (généralement 2D ou 3D) tout en préservant au mieux les distances par paires entre les observations. Contrairement à l’ACP qui maximise la variance projetée, le MDS part d’une matrice de dissimilarité et tente de reconstruire une configuration spatiale cohérente avec ces distances. Ce guide couvre en détail le principe mathématique, l’intuition géométrique, l’implémentation Python avec scikit-learn, les hyperparamètres clés, ainsi que quatre cas d’usage concrets.

Principe mathématique

La matrice de dissimilarité

Le point de départ du MDS est une matrice de dissimilarité D de taille n × n, où chaque élément d_ij représente la distance (ou la dissimilarité) entre les observations i et j. Cette matrice est symétrique (d_ij = d_ji), avec des zéros sur la diagonale (d_ii = 0), et tous les éléments sont non négatifs.

Ces distances peuvent être calculées de multiples façons : distance euclidienne, distance de Manhattan, dissimilarité cosinus, distances géodésiques (comme dans Isomap), ou toute mesure de dissimilarité adaptée au domaine d’application.

L’objectif fondamental

L’objectif du MDS est de trouver une configuration Z dans un espace de faible dimension p (typiquement p = 2 ou p = 3), où chaque observation i est représentée par un vecteur z_i ∈ ℝ^p, tel que les distances euclidiennes dans cet espace de projection approchent au mieux les distances originales :

||z_i − z_j|| ≈ d_ij pour tout couple (i, j)

Autrement dit, on cherche les coordonnées z_1, z_2, …, z_n qui reproduisent fidèlement la structure de distances connue.

La fonction de stress

Pour mesurer la qualité d’une configuration Z, on utilise une fonction de stress (également appelée fonction de critère ou fonction de perte). La forme la plus courante, proposée par Kruskal, est le stress-1 :

Stress = √[ Σ_{i<j} (d_ij − ||z_i − z_j||)² / Σ_{i<j} d_ij² ]

Une variante simplifiée, le stress brut (raw stress), s’écrit :

Stress brut = Σ_{i<j} (d_ij − ||z_i − z_j||)²

Le stress quantifie l’écart entre les distances originales et les distances dans l’espace de projection. Un stress proche de 0 indique une excellente préservation des distances, tandis qu’un stress élevé signale une perte d’information significative.

Minimisation par descente de gradient

La minimisation de la fonction de stress est un problème d’optimisation non linéaire. L’algorithme classique utilisé est l’algorithme SMACOF (Scaling by MAjorizing a COmplicated Function), qui repose sur une stratégie de majoration itérative :

1. Initialisation : on commence par une configuration aléatoire Z^(0) (ou une initialisation par ACP).
2. Majoration : à chaque itération t, on construit une fonction G_t(Z) qui majore le stress et qui coïncide avec lui en Z^(t).
3. Minimisation : on minimise G_t(Z), ce qui donne une nouvelle configuration Z^(t+1).
4. Convergence : on répète jusqu’à ce que la diminution du stress soit inférieure à un seuil ε ou que le nombre maximal d’itérations soit atteint.

Cette approche garantit une décroissance monotone du stress à chaque itération, conduisant à un minimum local (et souvent global grâce aux multiples initialisations via n_init).

MDS métrique vs MDS non-métrique

Il existe deux variantes fondamentales du MDS :

MDS métrique : on suppose que les distances d_ij sont mesurées sur une échelle d’intervalle ou de rapport. L’objectif est de minimiser directement le stress entre les distances originales et les distances projetées, éventuellement avec une transformation linéaire des distances originales : β · d_ij ≈ ||z_i − z_j||.

MDS non-métrique : on suppose que les distances d_ij ne sont connues que sur une échelle ordinale. Seuls les rangs des distances importent : si d_ij < d_kl, alors on s’attend à ce que ||z_i − z_j|| < ||z_k − z_l||. Pour réaliser cette contrainte, on utilise une régression monotone (monotonic regression ou isotonic regression) qui trouve la meilleure transformation monotone f telle que f(d_ij) ≈ ||z_i − z_j||. Le stress devient alors :

Stress non-métrique = √[ Σ_{i<j} (f(d_ij) − ||z_i − z_j||)² / Σ_{i<j} d_ij² ]

où f est une fonction monotone croissante optimisée par régression isotone (algorithme PAVA — Pool Adjacent Violators Algorithm).

Intuition géométrique

Imaginez que vous souhaitez dessiner une carte de la France, mais vous n’avez aucune coordonnée GPS des villes. En revanche, vous disposez d’un tableau complet des distances routières entre chaque paire de villes connues.

Le MDS, c’est exactement cela : à partir du seul tableau des distances, l’algorithme va « reconstruire » la carte. Il place chaque ville sur un plan de telle sorte que les distances entre les points sur le papier correspondent au plus près aux distances routières réelles.

Si la distance Paris–Lyon est de 465 km et que la distance Paris–Marseille est de 775 km, le MDS va positionner Lyon plus près de Paris que Marseille sur la carte reconstruite. Et si la distance Lyon–Marseille est de 315 km, le MDS va former naturellement un triangle cohérent.

Ce qui est remarquable, c’est que le MDS n’a jamais besoin des coordonnées originales. Il ne travaille qu’avec les distances. Si les distances proviennent d’un espace à 100 dimensions, le MDS les projette en 2D tout en préservant la structure relative des proximités. C’est cette propriété qui rend le MDS si puissant pour la visualisation et l’exploration de données complexes.

Implémentation Python avec scikit-learn

Exemple de base avec MDS de sklearn

L’implémentation la plus simple utilise la classe MDS de scikit-learn :

from sklearn.manifold import MDS
from sklearn.datasets import load_iris
import matplotlib.pyplot as plt
import numpy as np

# Charger les données Iris
iris = load_iris()
X = iris.data
y = iris.target

# MDS métrique en 2D
mds = MDS(n_components=2, metric=True, random_state=42,
          n_init=4, max_iter=300)
Z = mds.fit_transform(X)

# Visualisation
plt.figure(figsize=(10, 6))
for label, marker, color in zip(range(3), ['o', 's', 'D'],
                                 ['blue', 'green', 'red']):
    plt.scatter(Z[y == label, 0], Z[y == label, 1],
                marker=marker, c=color,
                label=iris.target_names[label],
                alpha=0.7, edgecolors='k', s=80)
plt.title('MDS métrique sur Iris', fontsize=14)
plt.xlabel('Dimension 1')
plt.ylabel('Dimension 2')
plt.legend()
plt.tight_layout()
plt.show()

# Afficher le stress final
print(f"Stress final : {mds.stress_:.4f}")

MDS à partir d’une matrice de dissimilarité custom

Le MDS accepte directement une matrice de dissimilarité pré-calculée, ce qui est extrêmement utile quand vos distances ne sont pas euclidiennes :

from sklearn.metrics import pairwise_distances

# Calculer une matrice de dissimilarité avec distance de Manhattan
D = pairwise_distances(X, metric='cityblock')

# MDS avec dissimilarité pré-calculée
mds_custom = MDS(n_components=2, metric=True,
                 dissimilarity='precomputed',
                 random_state=42, n_init=4, max_iter=300)
Z_custom = mds_custom.fit_transform(D)

print(f"Stress avec distance de Manhattan : {mds_custom.stress_:.4f}")

Comparaison MDS métrique vs non-métrique

Comparons les deux variantes pour voir leur impact sur la qualité de projection :

# MDS métrique
mds_metric = MDS(n_components=2, metric=True, random_state=42,
                 n_init=4, max_iter=300,
                 normalized_stress=True)
Z_metric = mds_metric.fit_transform(X)
stress_metric = mds_metric.stress_

# MDS non-métrique
mds_nonmetric = MDS(n_components=2, metric=False, random_state=42,
                    n_init=4, max_iter=300,
                    normalized_stress=True)
Z_nonmetric = mds_nonmetric.fit_transform(X)
stress_nonmetric = mds_nonmetric.stress_

print(f"Stress MDS métrique     : {stress_metric:.6f}")
print(f"Stress MDS non-métrique : {stress_nonmetric:.6f}")

# Visualisation comparée
fig, axes = plt.subplots(1, 2, figsize=(14, 5))

for ax, Z, stress, title in [
    (axes[0], Z_metric, stress_metric, 'MDS métrique'),
    (axes[1], Z_nonmetric, stress_nonmetric, 'MDS non-métrique')
]:
    for label, marker, color in zip(range(3), ['o', 's', 'D'],
                                     ['blue', 'green', 'red']):
        ax.scatter(Z[y == label, 0], Z[y == label, 1],
                   marker=marker, c=color,
                   label=iris.target_names[label],
                   alpha=0.7, edgecolors='k', s=80)
    ax.set_title(f'{title}\nStress = {stress:.4f}', fontsize=12)
    ax.legend()

plt.tight_layout()
plt.show()

Tracé du stress en fonction du nombre de dimensions

Un outil diagnostique essentiel pour choisir le nombre optimal de dimensions :

stresses = []
dimensions = range(1, 8)

for dim in dimensions:
    mds = MDS(n_components=dim, metric=True, random_state=42,
              n_init=4, max_iter=300, normalized_stress=True)
    mds.fit(X)
    stresses.append(mds.stress_)

plt.figure(figsize=(8, 5))
plt.plot(dimensions, stresses, 'bo-', linewidth=2, markersize=8)
plt.xlabel('Nombre de dimensions', fontsize=12)
plt.ylabel('Stress normalisé', fontsize=12)
plt.title('Scree plot du stress — MDS sur Iris', fontsize=14)
plt.xticks(dimensions)
plt.grid(True, alpha=0.3)
plt.tight_layout()
plt.show()

Ce graphique permet d’identifier le « coude » — le point au-delà duquel ajouter des dimensions ne réduit plus significativement le stress.

Hyperparamètres clés

Comprendre les hyperparamètres de MDS dans scikit-learn est essentiel pour obtenir des résultats optimaux :

n_components (int, défaut : 2)
Nombre de dimensions de l’espace de projection. Typiquement 2 ou 3 pour la visualisation. Un nombre plus élevé préserve mieux les distances mais réduit l’interprétabilité visuelle.

metric (bool, défaut : True)
True pour le MDS métrique, False pour le MDS non-métrique (avec régression monotone). Le MDS non-métrique est plus robuste quand les distances ne sont que des jugements ordinaux.

n_init (int, défaut : 4)
Nombre d’initialisations aléatoires réalisées. L’initialisation avec le meilleur stress est conservée. Augmenter cette valeur améliore les chances de trouver le minimum global, au prix d’un temps de calcul accru.

max_iter (int, défaut : 300)
Nombre maximal d’itérations de l’algorithme SMACOF pour chaque initialisation. Si l’algorithme atteint cette limite sans convergence, il faut soit augmenter max_iter, soit vérifier que le seuil eps n’est pas trop strict.

verbose (int, défaut : 0)
Niveau de verbosité. 0 = silencieux, 1 = informations basiques sur la convergence, 2+ = détails itératifs complets. Utile pour le débogage.

eps (float, défaut : 1e-3)
Seuil de convergence sur la variation relative du stress. Si le stress diminue de moins que eps entre deux itérations consécutives, l’algorithme s’arrête.

n_jobs (int, défaut : None)
Nombre de threads parallélisés pour les calculs de distance et les initialisations multiples. -1 utilise tous les cœurs disponibles.

dissimilarity (str, défaut : ‘euclidean’)
Type de dissimilarité : 'euclidean' (calcule automatiquement les distances euclidiennes à partir des données) ou 'precomputed' (utilise directement la matrice de dissimilarité fournie en entrée).

normalized_stress (bool/str, défaut : ‘auto’)
Utilise le stress normalisé (stress-1) au lieu du stress brut. Recommandé pour comparer des jeux de données de tailles différentes. La valeur 'auto' active le stress normalisé automatiquement.

Avantages et limites

Avantages

• Flexibilité des distances : le MDS accepte n’importe quelle mesure de dissimilarité, pas seulement la distance euclidienne. On peut utiliser des distances custom, des similarités transformées, ou même des jugements humains de similarité.
• Interprétabilité géométrique : les axes de la projection ont une interprétation directe — la proximité spatiale reflète la similarité des observations.
• Pas d’hypothèse de linéarité : contrairement à l’ACP, le MDS n’assume pas que les relations sont linéaires. Le MDS non-métrique en particulier est entièrement non paramétrique.
• Applicable aux données non numériques : dès lors qu’on peut définir une mesure de dissimilarité, le MDS peut être appliqué (textes, graphes, données catégorielles).
• Diagnostic par le stress : la fonction de stress fournit une mesure quantitative directe de la qualité de la projection.

Limites

• Complexité computationnelle élevée : le calcul de la matrice de dissimilarité est en O(n²) et chaque itération de SMACOF est en O(n²). Pour n = 10 000, la matrice contient déjà 100 millions d’éléments. Le MDS ne passe pas à l’échelle sur de très grands jeux de données.
• Sensibilité aux minima locaux : l’optimisation du stress est non convexe. Différentes initialisations peuvent donner des résultats différents, d’où l’importance de n_init.
• Perte d’information en forte compression : projeter de 100 dimensions en 2D implique inévitablement une perte. Un stress élevé signale que la structure des données ne peut pas être fidèlement représentée en 2D.
• Pas de fonction de projection inversible : contrairement à l’ACP, le MDS ne produit pas de matrice de projection réutilisable pour transformer de nouvelles données. Il faut recalculer le MDS complet ou utiliser des techniques d’approximation (out-of-sample extension).
• Rotation arbitraire : la solution du MDS n’est pas unique — toute rotation ou réflexion de la configuration préserve les distances et donc le stress. L’orientation des axes n’a pas de sens intrinsèque.

Cas d’usage concrets

Cas 1 : Cartographie de similarité entre produits

Une entreprise de commerce en ligne souhaite visualiser la similarité perçue entre ses produits pour optimiser son catalogue. En calculant une matrice de dissimilarité basée sur les co-achats (combien de fois deux produits sont achetés ensemble), le MDS permet de projeter les produits sur un plan 2D. Les produits similaires se regroupent naturellement, révélant des clusters invisibles dans les données brutes. Cette visualisation guide les décisions de merchandising et de recommandation.

# Concept : similarité de produits à partir de co-achats
from sklearn.metrics import pairwise_distances
from sklearn.manifold import MDS
import numpy as np

# Matrice binaire client × produit (1 = acheté, 0 = non acheté)
# Dissimilarité = 1 − coefficient de Jaccard
# Après calcul de la matrice D :
mds = MDS(n_components=2, metric=True,
          dissimilarity='precomputed', random_state=42)
Z = mds.fit_transform(D)

Cas 2 : Analyse de perception en marketing sensoriel

Dans une étude sur les perceptions olfactives, des participants évaluent la similarité perçue entre 50 parfums sur une échelle de 1 à 10. Le MDS non-métrique est idéal ici car les jugements humains sont ordinaux (on sait que le parfum A est plus proche de B que de C, mais pas dans quelle proportion exacte). La projection révèle les dimensions sous-jacentes de la perception olfactive (floral vs boisé, frais vs chaud, etc.) sans les avoir prédéfinies.

# matrice_jugements : matrice 50×50 de similarités perçues
# Convertir en dissimilarité
dissimilarite = np.max(matrice_jugements) - matrice_jugements

mds = MDS(n_components=2, metric=False,
          random_state=42, n_init=10)
Z = mds.fit_transform(dissimilarite)

Cas 3 : Visualisation de distances génétiques entre espèces

En biologie évolutive, on dispose de distances génétiques (nombre de mutations par paire de bases) entre de nombreuses espèces. Ces distances ne sont pas euclidiennes — elles reflètent des processus évolutifs complexes. Le MDS permet de les visualiser en 2D ou 3D, révélant des groupes taxonomiques cohérents et des relations évolutives inattendues.

# D_genetique : matrice de distances entre espèces
mds = MDS(n_components=2, metric=True,
          dissimilarity='precomputed',
          random_state=42, n_init=8)
Z = mds.fit_transform(D_genetique)

# Colorer par clade taxonomique pour vérifier la cohérence

Cas 4 : Exploration de données de santé multidimensionnelles

Dans un dossier médical, chaque patient est décrit par des centaines de variables : résultats sanguins, antécédents, mesures vitales, données génomiques. Calculer une matrice de distance (par exemple la distance de Gower, adaptée aux variables mixtes continues et catégorielles) puis appliquer le MDS non-métrique permet de visualiser l’hétérogénéité de la cohorte et d’identifier des sous-groupes de patients similaires pour la médecine personnalisée.

from sklearn.manifold import MDS
# D_gower : matrice de distances de Gower entre patients
mds = MDS(n_components=2, metric=False,
          dissimilarity='precomputed',
          random_state=42, n_init=10,
          normalized_stress=True)
Z = mds.fit_transform(D_gower)
print(f"Stress : {mds.stress_:.4f}")

Voir aussi

• Devenez ‘Trillionaire’ en Codant : Comment Python Peut Révolutionner Vos Projets Financiers
• Maîtriser les Graphiques Colorés en Python : Guide Complet pour Débutants et Experts