La distance Manhattan, aussi appelée distance en norme L1, est une métrique incontournable dans le monde de l’analyse de données, de l’optimisation et de l’intelligence artificielle. Son nom provient de la géométrie des rues en damier de Manhattan, où l’on ne peut se déplacer que le long de blocs rectilignes. Cette contrainte cartésienne donne naissance à une notion simple et puissante : la somme des écarts absolus entre les coordonnées de deux points. Dans cet article, nous allons explorer en profondeur la distance Manhattan, ses fondements mathématiques, ses propriétés, ses applications et ses variantes. L’objectif est de proposer une ressource claire et complète pour les professionnels, les étudiants et les passionnés qui souhaitent maîtriser cette métrique et l’appliquer de manière efficace.
Définition et intuition de la distance Manhattan
La distance Manhattan entre deux points x et y dans un espace à d dimensions est définie comme la somme des valeurs absolues des différences entre les composantes correspondantes :
Distance Manhattan(x, y) = ∑i |xi – yi|
Dans un plan 2D, cela se lit comme la distance parcourue en suivant les axes x et y, en privilégiant les trajets en blocs parallèles aux axes. Cette intuition est particulièrement utile dans les environnements gridés, tels que les cartes de ville ou les grilles de jeux vidéo, où les déplacements se font sur des lignes rectilignes et non en diagonale.
Formulation mathématique et notations
La distance Manhattan est aussi appelée distance L1 ou norme L1 lorsque l’on considère l’espace vectoriel équipé de la norme L1. Pour des points x et y du même espace vectoriel R^n, on peut écrire :
- Distance Manhattan(x, y) = ∑i |xi – yi|
- Distance L1(x, y) = ∥x – y∥1
Cette métrique vérifie les propriétés classiques d’une métrique : positivité, identité des indiscernables (distance nulle uniquement si x = y), symétrie et inégalité triangulaire. De nombreuses variantes existent toutefois lorsque l’on introduit des poids, des contraintes ou des métriques sur des structures abstraites.
L1 et l’invariance géométrique
La distance Manhattan se distingue par des propriétés d’invariance intéressantes. Elle est invariante par permutation des coordonnées et par changement de signe des coordonnées séparément. Autrement dit, si l’on réordonne les axes ou que l’on applique des transformations coordonnées xi → ±xi, la valeur de la distance reste inchangée. Cette caractéristique en fait une métrique adaptée aux données où les dimensions portent une signification distincte et indépendante.
Exemples simples et visualisation
Prenons deux points dans R^2 : A = (2, 3) et B = (5, 1).
- Différences: Δx = 3, Δy = -2
- Distance Manhattan(A, B) = |3| + |-2| = 3 + 2 = 5
Imaginons maintenant une grille : on peut relier A à B en se déplaçant de 3 unités sur l’axe x et 2 unités sur l’axe y, totalisant 5 unités de déplacement dans une configuration typique en damier. Cette intuition est particulièrement utile pour les algorithmes de recherche et les heuristiques dans les environnements gridés.
Comparaison avec d’autres métriques
Quelques comparaisons utiles permettent de comprendre pourquoi la distance Manhattan peut être préférable dans certains contextes :
- Distance euclidienne (norme L2) : ∥x – y∥2 = √∑i (xi – yi)^2. Plus naturelle pour les distances “à vol d’oiseau”, mais plus sensible aux grandes variations et aux angles. Moins adaptée lorsque les déplacements suivent des grilles rectilignes.
- Distance de Chebyshev (norme L∞) : ∥x – y∥∞ = maxi |xi – yi|. Utile lorsque le coût est dominé par le déplacement le plus long sur une seule coordonnée.
La distance Manhattan est particulièrement adaptée lorsque les trajets doivent respecter des axes parallèles et que l’on travaille sur des grilles ou des espaces discrets. En revanche, si l’on cherche des proximités sous des rotations ou des distances “à vol d’oiseau”, la norme L2 peut mieux refléter l’intuition humaine de la distance réelle.
Calcul pratique et algorithmes
Calcul direct en espace d dimensions
Pour deux points x et y dans R^n, le calcul est simple et rapide : on additionne les écarts absolus de chaque coordonnée. Cette opération est O(n) en complexité temporelle et ne nécessite pas de prétraitement particulier, si l’espace est discret et les données déjà standardisées.
Calcul dans des environnements discrets et gridés
Dans les grilles 2D ou 3D, la distance Manhattan est fréquemment utilisée pour estimer des coûts dans les algorithmes de planification de trajets, tels que A*. Pour un point courant s=(xs, ys) et un objectif t=(xt, yt), l’heuristique admissible est :
h(s) = |xs – xt| + |ys – yt|
Cette valeur ne surestime jamais le coût réel optimal dans une grille où les déplacements diagonaux ne sont pas autorisés, et elle guide efficacement la recherche vers l’objectif.
Formules pondérées et généralisées
Il est courant d’introduire des poids par dimension pour adapter la distance Manhattan à des coûts différents selon les axes ou les types de données. Si l’on associe des poids w = (w1, w2, …, wn) à chaque coordonnée, la distance Manhattan pondérée devient :
Distance Manhattan pondérée(x, y) = ∑i wi · |xi – yi|
Cette variante est utile lorsque certaines dimensions représentent des coûts plus élevés ou lorsque l’on souhaite privilégier certaines directions dans l’espace des données.
Applications pratiques de la distance Manhattan
Apprentissage automatique et clusters
Dans l’apprentissage automatique, la distance Manhattan joue un rôle clé dans des méthodes basées sur les distances, telles que les k-plus proches voisins (kNN) et les médianes de k-médoïdes. En comparaison à la distance euclidienne, la distance Manhattan peut être plus robuste face à des données fortement éparses ou à des valeurs extrêmes dans certaines dimensions. Elle peut également offrir des performances supérieures lorsque les caractéristiques se comportent de manière additive et indépendante.
Analyse de similarité et recommandation
Pour mesurer la similarité entre des profils utilisateurs, des vecteurs de préférences ou des caractéristiques hétérogènes, la distance Manhattan permet une agrégation simple et interprétable des écarts. Les systèmes de recommandation basés sur des distances peuvent bénéficier de la clarté de l’addition des écarts sur chaque attribut.
Planification de trajets et robotique
Les robots mobiles opérant dans des environnements structurés en grilles s’appuient souvent sur la distance Manhattan pour estimer les coûts de déplacement et pour la conception d’heuristiques efficaces dans les algorithmes de recherche de chemin. Cela est particulièrement utile dans les entrepôts, les usines automatisées et les jeux vidéo qui manipulent des mondes rectilignes.
Analyse de données catégorielles et métriques mixtes
Lorsque les données combinent des variables continues et des variables binaires ou catégorielles, la distance Manhattan peut être utilisée dans des cadres mixtes après avoir pré-traité les données (par exemple, une standardisation ou une encodage binaire). Des variantes de la distance, comme la distance de Manhattan pondérée ou les distances adaptées à des données mixtes, permettent de conserver les propriétés intuitives de L1 tout en gérant la nature des données.
Manhattan distance dans les graphes et les réseaux
Dans les graphes, la distance Manhattan peut être assimilée à la longueur du plus court chemin sur une grille où les arêtes ne permettent que des mouvements horizontaux ou verticaux. Cette approche est utile pour les métriques de proximité dans les réseaux urbains ou les maillages structurés. En planification de réseaux, l’analyse des distances Manhattan peut aider à estimer les coûts de diffusion ou de transport et à optimiser la localisation d’infrastructures.
Variantes et généralisations avancées
Distance Manhattan sur des espaces non uniformes
Quand les dimensions ont des échelles différentes, il peut être nécessaire d’omettre l’uniformité et d’appliquer des normalisations ou des pondérations pour que chaque dimension contribue de manière équitable à la distance. Les techniques de standardisation (z-score) ou de normalisation min-max sont couramment utilisées avant de calculer la distance Manhattan dans des ensembles de données hétérogènes.
Distances mixtes et métriques hybrides
Dans certaines applications, on combine la distance Manhattan avec d’autres métriques pour obtenir une mesure plus robuste. Par exemple, on peut utiliser une combinaison linéaire de la distance Manhattan et de la distance euclidienne pour tirer parti des propriétés des deux métriques, ou employer des métriques entièrement différentes selon le type de données (par exemple, L1 pour les coûts, L2 pour les similarités, et des mesures discrètes pour les données catégorielles).
Distance Manhattan en apprentissage profond
Bien que les réseaux de neurones utilisent majoritairement des distances continues et differentiables dans les pertes, la distance Manhattan peut apparaître dans des contextes spécifiques, comme les distances de dissimilarité pour l’évaluation des reconstructions ou pour guider des algorithmes de clustering dans des couches intermédiaires. Dans les systèmes de recommandation ou de semi-supervision, le cadre L1 peut être préféré pour favoriser la sparsité et la robustesse.
Implémentation et bonnes pratiques
Implémentations dans différents langages
La distance Manhattan est simple à implémenter et ne requiert pas de bibliothèques spécialisées pour des cas basiques. En Python, par exemple, elle peut être calculée en une ligne :
distance = sum(abs(a – b) for a, b in zip(x, y))
En R, on peut utiliser la fonction dist avec la méthode = « manhattan » pour des ensembles de données : dist(matrix, method = « manhattan »).
Dans des bases de données SQL, il est possible de calculer la distance Manhattan entre des vecteurs stockés sous forme de colonnes ou de lignes en utilisant des expressions arithmétiques sur les coordonnées.
Prétraitement des données et normalisation
Pour obtenir des résultats cohérents, il est souvent nécessaire de normaliser ou standardiser les données avant d’appliquer la distance Manhattan. Cela évite qu’une dimension avec une échelle très élevée domine le calcul de la distance. Des techniques simples comme la standardisation (centrer à zéro et ramener à l’unité variance) ou la normalisation min–max peuvent être utilisées selon le contexte.
Gestion des valeurs manquantes et des outliers
La présence de valeurs manquantes peut compliquer le calcul. Des approches courantes incluent l’imputation des valeurs manquantes (par la moyenne, médiane ou mode selon le type de données) ou l’utilisation de distances partielle lorsqu’un attribut est manquant. Les outliers peuvent influencer fortement la distance, surtout en distance Manhattan pondérée; il peut être judicieux d’adapter les poids ou d’employer des méthodes robustes lors du prétraitement.
Cas d’usage concrets et conseils pratiques
Quand privilégier la distance Manhattan
Optez pour la distance Manhattan lorsque :
- Les déplacements s’effectuent sur une grille rectiligne ou un réseau urbain, où les coûts de déplacement se décomposent en écarts par dimension.
- Vous travaillez avec des données où chaque dimension représente une contribution additive indépendante au coût total.
- Vous souhaitez favoriser la robustesse et la sparsité dans les modèles, notamment lorsqu’on combine des caractéristiques hétérogènes.
Quand préférer d’autres métriques
Préférez la distance euclidienne ou d’autres métriques lorsque :
- Les distances réelles ne suivent pas une grille et que les directions diagonales ou les rotations sont pertinentes.
- Les données sont fortement corrélées entre les dimensions et que la norme L2 reflète mieux l’irradiation de l’erreur globale.
- Vous travaillez sur des géométries non cartésiennes ou des espaces qui nécessitent des mesures plus isotropes.
FAQ et mythes courants
La distance Manhattan est-elle adaptée aux images et à la vision par ordinateur ?
Dans le traitement d’images, la distance Manhattan peut être utilisée comme métrique de similarité entre des vecteurs de caractéristiques extraits, mais les images elles-mêmes bénéficient souvent de distances plus complexes fondées sur des représentations apprises (réseaux convolutifs) ou de distances basées sur des descripteurs plus adaptés à la perception visuelle. Néanmoins, pour des signatures simples, des espaces de features ou des représentations binaires, la distance Manhattan peut être utile et efficace.
La distance Manhattan est-elle plus rapide que la distance euclidienne ?
En général, oui, le calcul de la distance Manhattan est plus simple et peut être plus rapide, notamment car il évite le calcul de racines. Cela peut être un avantage dans des environnements en temps réel ou lorsque l’on traite d’énormes ensembles de données sur des ressources limitées.
Peut-on combiner distance Manhattan et techniques de normalisation pour le clustering ?
Absolument. Une approche fréquente consiste à normaliser les données puis appliquer un algorithme de clustering utilisant la distance Manhattan comme métrique. Cela peut produire des clusters plus cohérents lorsque les dimensions portent des échelles différentes et que l’on souhaite que chaque dimension contribue de manière égale au regroupement.
Conclusion : maîtriser la distance Manhattan en pratique
La distance Manhattan est une métrique simple en apparence mais riche dans ses usages. Sa connexion avec la géométrie des grilles, son invariance par permutation des axes et son interprétation intuitive en termes de déplacements en blocs en font un outil précieux pour l’analyse de données, l’optimisation et l’intelligence artificielle. Qu’il s’agisse de classifier, de regrouper, de planifier des trajets ou d’évaluer des similarités, la distance Manhattan offre une approche robuste et efficace lorsque les conditions s’y prêtent. En comprenant ses propriétés, en adaptant les weights et en choisissant les contextes adaptés, vous pourrez exploiter pleinement cette métrique et obtenir des résultats clairs, reproductibles et performants.
Ressources et perspectives
Pour approfondir, explorez les notions liées à la norme L1, les variantes pondérées et les extensions à des espaces à dimension infinie ou à des graphes. L’étude des propriétés géométriques de la distance Manhattan, son rôle dans les heuristiques des algorithmes de recherche et son intégration dans des pipelines d’apprentissage automatique constituent des domaines riches et en constante évolution. En restant attentif aux besoins spécifiques de vos données et de vos objectifs, vous pourrez tirer le meilleur parti de la distance Manhattan et de ses nombreuses variantes.