Manhattan Distance

Sommaire de l'article

Algorithmes et Mises à Jour : Distance de Manhattan (Manhattan Distance) – Concept Complet

Introduction

La distance de Manhattan, aussi appelée Manhattan distance, taxicab distance, L1-norm ou distance L1, est un concept mathématique fondamental utilisé dans de nombreux domaines : algorithmique, intelligence artificielle, apprentissage automatique, optimisation, robotique, analyse de données ou encore géomatique. Contrairement à la distance euclidienne plus familière, la distance de Manhattan mesure la séparation entre deux points en ne considérant que les déplacements le long des axes de coordonnées, comme si l’on se déplaçait dans un réseau de rues en quadrillage.

Dans cet article, nous présentons en détail la définition mathématique de la distance de Manhattan, ses propriétés, ses différences avec d’autres métriques (distance euclidienne, distance de Hamming, distance cosinus), ainsi que ses applications pratiques modernes : algorithmes de pathfinding (A*), KNN, clustering, recherche de plus proches voisins en dimension élevée, systèmes de recommandation, text mining et analyse de données creuses. Nous verrons également comment l’intégrer efficacement dans vos algorithmes et vos projets de data science ou de développement web.

Concepts Clés

Définition de la Distance de Manhattan (L1)

La distance de Manhattan est une manière de mesurer la distance entre deux points dans un espace à une ou plusieurs dimensions en additionnant les valeurs absolues des différences de coordonnées. Elle tire son nom de la façon dont un taxi se déplace dans un plan de ville quadrillé (comme Manhattan), où il ne peut circuler que le long des rues orientées nord–sud et est–ouest.

Dans le cas bidimensionnel, pour deux points P(x₁, y₁) et Q(x₂, y₂), la distance de Manhattan se calcule par :

D(P,Q) = |x₂ − x₁| + |y₂ − y₁|

Dans un espace de dimension n, pour deux points P = (p₁, …, p_n) et Q = (q₁, …, q_n), la formule générale est :

D(P,Q) = Σ_i=1..n |p_i − q_i|

Cette expression correspond exactement à la norme L1 sur ℝⁿ. En d’autres termes, la distance de Manhattan entre deux vecteurs est simplement la norme L1 de leur différence.

Exemples Numériques de Distance de Manhattan

Pour mieux comprendre, considérons quelques exemples simples :

Exemple 1 : P(1, 2) et Q(4, 6)
Distance de Manhattan : |4 − 1| + |6 − 2| = 3 + 4 = 7.
Exemple 2 : P(2, 3) et Q(5, 7)
Distance de Manhattan : |5 − 2| + |7 − 3| = 3 + 4 = 7.
Exemple 3 (comparaison L1 vs L2) : P(0, 0) et Q(3, 4)
Distance de Manhattan : |3 − 0| + |4 − 0| = 3 + 4 = 7.
Distance euclidienne : √(3² + 4²) = √(9 + 16) = √25 = 5.

On voit que la distance de Manhattan est généralement plus grande ou égale à la distance euclidienne pour un même couple de points, car elle « contourne » l’espace en suivant les axes, alors que la distance euclidienne suit la ligne droite.

Comparaison avec la Distance Euclidienne (L2)

La distance euclidienne (ou norme L2) mesure le plus court segment de droite reliant deux points. Elle est définie, en dimension 2, par :

D_euclidienne(P,Q) = √[(x₂ − x₁)² + (y₂ − y₁)²]

En dimension n :

D_euclidienne(P,Q) = √(Σ_i=1..n (p_i − q_i)²)

Distance	Formule (2D)	Interprétation
Manhattan (L1)	\|x₂ − x₁\| + \|y₂ − y₁\|	Plus court chemin sur une grille, déplacements horizontaux et verticaux uniquement
Euclidienne (L2)	√[(x₂ − x₁)² + (y₂ − y₁)²]	Plus court segment de droite entre deux points dans l’espace continu

Il est important de souligner que la distance de Manhattan n’est pas égale à la distance euclidienne : les deux métriques mesurent des notions différentes de « proximité ». La distance euclidienne donne la plus courte distance géométrique, tandis que la distance de Manhattan donne le plus court chemin dans un environnement quadrillé où seuls les déplacements alignés sur les axes sont autorisés.

Propriétés Mathématiques : une Vraie Métrique

La distance de Manhattan est une métrique au sens mathématique. Elle satisfait donc les quatre propriétés fondamentales :

Non-négativité : D(P,Q) ≥ 0 pour tous les points P et Q.
Symétrie : D(P,Q) = D(Q,P).
Identité des indiscernables : D(P,Q) = 0 si et seulement si P = Q.
Inégalité triangulaire : pour tout P, Q, R, D(P,R) ≤ D(P,Q) + D(Q,R).

Contrairement à certaines idées reçues, il est donc faux de dire que la distance de Manhattan n’est pas une vraie métrique ou qu’elle ne respecte pas l’inégalité triangulaire. C’est précisément parce qu’elle est métrique qu’elle est utilisée dans de nombreux algorithmes de recherche de voisins, d’indexation et de clustering.

Invariance et Rotation : une Différence Importante avec L2

La distance euclidienne est invariante par rotation : si l’on effectue une rotation du repère, la distance L2 entre deux points reste identique. Ce n’est pas le cas de la distance de Manhattan : la valeur de la distance L1 dépend de l’orientation des axes de coordonnées.

Concrètement, si l’on effectue une rotation de 45° du système de coordonnées, la distance de Manhattan entre deux points peut changer, alors que la distance euclidienne ne change pas. Cela a des conséquences pratiques en feature engineering et en modélisation : le choix de la base et la transformation des variables peuvent influencer fortement la distance L1.

Robustesse aux Valeurs Extrêmes (Outliers)

La distance de Manhattan est souvent considérée comme moins sensible aux valeurs extrêmes que la distance euclidienne. En effet, la norme L2 élève les écarts au carré, ce qui amplifie la contribution des dimensions ayant de très grandes différences. La norme L1, elle, additionne les valeurs absolues sans les mettre au carré, ce qui limite l’impact des outliers. Cette propriété explique son adoption fréquente en apprentissage automatique, notamment pour des données bruitées ou contenant des points atypiques.

Différences avec d’Autres Distances (Hamming, Cosinus, etc.)

Il est essentiel de ne pas confondre la distance de Manhattan avec d’autres mesures de similarité ou de dissemblance :

Distance de Hamming : compte uniquement le nombre de positions où deux vecteurs diffèrent (0 ou 1 par position), sans tenir compte de l’ampleur de la différence. Elle est utilisée pour les chaînes de caractères, les codes binaires ou les vecteurs catégoriels.
Distance cosinus : mesure principalement l’angle entre deux vecteurs, indépendamment de leur norme, ce qui est très utile en text mining et en représentation de documents. Elle ne mesure pas une distance au sens métrique usuel dans tous les cas.
Distance euclidienne (L2) : mesure la « vraie » distance géométrique en ligne droite.

Aucune de ces distances ne doit être assimilée à la distance de Manhattan : chacune correspond à une hypothèse géométrique et statistique différente.

Applications Pratiques de la Distance de Manhattan

Pathfinding et Recherche de Chemin sur Grille (A*)

Dans les algorithmes de recherche de chemin sur des grilles, tels que l’algorithme A* en jeux vidéo, robotique mobile ou simulation, la distance de Manhattan joue un rôle central. Lorsque les mouvements autorisés sont uniquement horizontaux et verticaux (4 directions), la distance de Manhattan est une heuristique admissible pour A* : elle ne surestime jamais le plus court chemin possible sur la grille. Cela garantit la correction et l’optimalité de l’algorithme.

En revanche, si les mouvements diagonaux sont permis et ont un coût comparable aux mouvements horizontaux/verticaux, la distance de Manhattan n’est plus une heuristique idéale ; on lui préfère alors d’autres mesures, comme la distance de Chebyshev ou une heuristique adaptée au coût des mouvements diagonaux.

Algorithmes de Machine Learning : KNN et Clustering

Dans le domaine du machine learning, la distance de Manhattan est largement utilisée comme métrique de similarité :

k-plus proches voisins (KNN) : au lieu de la distance euclidienne, on peut utiliser la distance de Manhattan pour mesurer la proximité entre un point à classer et les points du jeu d’entraînement. Cela peut être particulièrement avantageux pour des données de grande dimension et/ou sparse (creuses), comme les représentations bag-of-words en traitement de texte.
Clustering : des algorithmes de regroupement comme k-medoids, k-means avec centre médian (variante L1) ou d’autres méthodes basées sur la médiane peuvent utiliser la distance de Manhattan pour définir la similarité entre points et centres de clusters. La norme L1 tend à produire des clusters plus robustes aux valeurs extrêmes que la norme L2.

Dans les problèmes de text mining, de représentation vectorielle de documents ou de profil utilisateur, où les vecteurs sont souvent très dimensionnels et très creux (beaucoup de zéros), la distance de Manhattan est fréquemment préférée, car elle gère mieux ce type de structure de données.

Recherche de Voisins en Grande Dimension

En haute dimension, la distance euclidienne souffre parfois du « curse of dimensionality » : les distances tendent à se concentrer, rendant la distinction entre proches et lointains moins pertinente. La distance de Manhattan est souvent mieux adaptée dans certains contextes de haute dimension, notamment en raison de sa robustesse aux outliers et de sa capacité à mieux représenter l’écart sur plusieurs dimensions, sans surpondérer les différences très marquées sur quelques dimensions seulement.

Il serait donc trompeur de dire que la distance de Manhattan est « toujours pire » que la distance euclidienne en grande dimension. Le choix dépend du type de données, de leur sparsité, de la présence d’outliers et des objectifs de l’analyse.

Optimisation Combinatoire et Problèmes sur Grille

De nombreux problèmes d’optimisation combinatoire peuvent être modélisés avec une distance de Manhattan, en particulier lorsque l’espace des solutions a une structure de type grille ou réseau régulier. C’est le cas par exemple :

des problèmes d’affectation (assigner des ressources, des tâches ou des agents à des positions sur une grille),
de certains modèles de placement d’installations en logistique ou en urbanisme,
du Quadratic Assignment Problem (QAP) et de variantes où le coût dépend des déplacements en L1,
de l’optimisation de réseaux de transport structurés en blocs (villes planifiées en damier, circuits électroniques, etc.).

La distance de Manhattan fournit alors une mesure réaliste du coût de déplacement ou d’acheminement.

Applications en Data Science et Analyse de Données

En data science, la distance de Manhattan est utilisée pour mesurer la similarité ou la dissimilarité entre vecteurs de caractéristiques :

Analyse de données tabulaires : pour des données numériques où chaque dimension représente une variable (âge, revenu, consommation, etc.), la distance de Manhattan peut être utilisée pour trouver des profils similaires, segmenter des clients ou détecter des anomalies.
Text mining : dans la représentation bag-of-words ou TF-IDF, les vecteurs de texte sont souvent creux. La norme L1 permet de comparer la fréquence des termes entre documents sans être trop dominée par quelques mots très fréquents.
Systèmes de recommandation : la distance de Manhattan peut mesurer la similarité entre profils d’utilisateurs (notes, clics, achats) ou entre produits (caractéristiques, attributs) dans des systèmes de recommandation basés sur la proximité.
Détection d’anomalies : en comparant la distance L1 d’un point à un centre de référence ou à ses voisins, on peut mettre en évidence des comportements atypiques, tout en limitant l’influence d’un attribut extrême.

Bonnes Pratiques pour l’Intégration de la Distance de Manhattan

Choisir entre Distance de Manhattan (L1) et Euclidienne (L2)

Le choix entre la distance de Manhattan et la distance euclidienne doit être guidé par :

La structure de l’espace : sur une grille ou quand les mouvements diagonaux sont impossibles ou coûteux, la distance de Manhattan est plus naturelle.
Le type de données : pour des données discrètes, ordinales ou très creuses, la distance de Manhattan est souvent plus adaptée.
La sensibilité aux outliers : si l’on souhaite réduire l’impact des valeurs extrêmes, la norme L1 constitue un bon choix.
Les propriétés géométriques recherchées : si l’on a besoin d’une distance invariante par rotation, la distance euclidienne reste la référence.

Implémenter Efficacement la Distance de Manhattan

Pour implémenter efficacement la distance de Manhattan dans vos algorithmes, quelques bonnes pratiques s’imposent :

Structures de données adaptées : utilisez des structures optimisées pour le calcul de distances, comme des tableaux contigus (par exemple via NumPy) ou des représentations vectorielles creuses si vos données contiennent beaucoup de zéros.
Vectorisation : dans des langages comme Python, privilégiez les opérations vectorisées (NumPy, Pandas) plutôt que des boucles explicites, afin de profiter des optimisations internes.
Indexation et pré-calculs : dans des systèmes où l’on effectue de nombreuses requêtes de plus proches voisins, il peut être utile de construire des structures d’indexation pour métriques (arbres, partitions de l’espace, etc.) adaptées à la distance L1.
Surveillance des bibliothèques : vérifiez régulièrement les mises à jour de vos bibliothèques mathématiques et de machine learning (par exemple SciPy, scikit-learn, TensorFlow, PyTorch), qui proposent souvent des implémentations optimisées de la distance de Manhattan, parfois sous le nom de cityblock ou L1.

Intégrer la Distance de Manhattan dans des Projets Web et SEO

Dans le contexte du développement web et des applications SEO, la distance de Manhattan intervient surtout au niveau des algorithmes sous-jacents : systèmes de recommandation, moteurs de recherche internes, scoring de similarité entre contenus, etc.

Systèmes de recommandation : en représentant chaque utilisateur et chaque contenu (article, produit, vidéo) par un vecteur de caractéristiques (thèmes, catégories, historique d’interactions), on peut utiliser la distance de Manhattan pour mesurer la proximité entre profils et proposer des contenus similaires.
Analyse des parcours utilisateurs : en codant les interactions sur un site (pages vues, clics, actions) sous forme de vecteurs, la distance de Manhattan permet de comparer différents parcours et d’identifier des comportements proches.
Personnalisation de contenu : les algorithmes de personnalisation peuvent s’appuyer sur la distance de Manhattan pour ajuster la recommandation de contenus, de produits ou de services, en fonction de la similarité entre le profil d’un visiteur et ceux des segments existants.

Améliorer la Structure Algorithmique Autour de L1

Pour tirer pleinement parti de la distance de Manhattan dans vos algorithmes, il est utile de :

Concevoir des structures de données alignées avec la métrique L1 (par exemple, index adaptés aux normes L1 plutôt qu’aux normes L2).
Réduire la complexité algorithmique en évitant de calculer des distances complètes lorsque ce n’est pas nécessaire (pruning, bornes inférieures, etc.).
Normaliser ou standardiser les variables pour éviter qu’une dimension ne domine artificiellement la distance totale.
Tester plusieurs métriques (L1, L2, cosine, Hamming) sur un même problème pour choisir empiriquement celle qui offre les meilleurs résultats.

Rédiger du Contenu de Qualité sur la Distance de Manhattan

Lorsque vous écrivez sur des sujets techniques comme la distance de Manhattan, quelques bonnes pratiques éditoriales renforcent la clarté et la valeur pour le lecteur :

Séparer le jargon mathématique des explications accessibles, en introduisant progressivement les notions (métrique, norme L1, haute dimension).
Inclure des exemples concrets et visuels (chemin sur une grille, parcours de taxi, comparaisons L1 vs L2) pour ancrer les concepts abstraits.
Mettre en avant les avantages pratiques : robustesse aux outliers, pertinence pour les données sparse, adéquation aux modèles de villes en damier, etc.
Contextualiser par rapport aux applications : machine learning, recommandation, robotique, jeux vidéo, urbanisme, optimisation de réseaux.

Outils et Ressources pour Travailler avec la Distance de Manhattan

Outils Logiciels

Pour calculer et visualiser la distance de Manhattan dans vos projets, plusieurs outils et bibliothèques sont utiles :

Bibliothèques Python (NumPy, SciPy, scikit-learn) : NumPy permet de calculer facilement des sommes de valeurs absolues entre vecteurs. SciPy propose des fonctions de distance telles que cityblock, qui implémentent directement la distance de Manhattan. Scikit-learn permet de choisir metric="manhattan" ou metric="l1" dans de nombreux algorithmes (KNN, clustering, etc.).
Frameworks de deep learning (TensorFlow, PyTorch) : la norme L1 est souvent utilisée comme fonction de coût (L1 loss) ou comme régularisation (L1 regularization) afin de favoriser la parcimonie des poids.
Outils de data science (R, Julia, MATLAB) : ces environnements proposent également des fonctions natives pour calculer des distances L1 entre vecteurs ou matrices.

Ressources Éducatives

Pour approfondir vos connaissances sur la distance de Manhattan et sur les métriques de distance en général, vous pouvez vous tourner vers :

Des cours en ligne sur l’algorithmique, la géométrie des espaces de données et le machine learning.
Des ouvrages de référence en apprentissage automatique, statistiques et optimisation, qui consacrent souvent un chapitre aux différentes distances.
Des articles techniques et billets de blog spécialisés en data science, expliquant les cas d’usage de L1 vs L2, ou comparant diverses métriques.

FAQ sur la Distance de Manhattan

Qu’est-ce que la distance de Manhattan ?

La distance de Manhattan est une métrique qui mesure la séparation entre deux points en ne permettant que des déplacements le long des axes des coordonnées. Elle est égale à la somme des valeurs absolues des différences de coordonnées entre ces deux points.

En quoi diffère-t-elle de la distance euclidienne ?

La distance euclidienne mesure la longueur du segment de droite reliant deux points (norme L2), tandis que la distance de Manhattan mesure le plus court chemin en escalier sur une grille, en ne considérant que des mouvements horizontaux et verticaux (norme L1). Elles ne sont pas égales et ne modélisent pas le même type de distance.

La distance de Manhattan est-elle une vraie métrique ?

Oui. Elle satisfait toutes les propriétés d’une métrique : non-négativité, symétrie, identité des indiscernables et inégalité triangulaire.

La distance de Manhattan est-elle invariante par rotation ?

Non. Contrairement à la distance euclidienne, la distance de Manhattan dépend de l’orientation des axes. Une rotation du repère peut donc modifier la distance L1 entre deux points.

Où utilise-t-on principalement la distance de Manhattan ?

On utilise la distance de Manhattan dans de nombreux domaines : algorithmes de pathfinding sur grilles (comme A*), machine learning (KNN, clustering, recherche de voisins en haute dimension), text mining, systèmes de recommandation, optimisation combinatoire, urbanisme et logistique sur réseaux de type grille.

Peut-on utiliser la distance de Manhattan en haute dimension ?

Oui. Elle est même fréquemment utilisée en grande dimension, notamment pour des données creuses, car elle se montre souvent plus robuste aux valeurs extrêmes que la norme L2 et mieux adaptée à certains types de structure de données.

La distance de Manhattan est-elle identique à la distance de Hamming ?

Non. La distance de Hamming compte le nombre de positions différentes entre deux vecteurs (0 ou 1 par dimension), tandis que la distance de Manhattan additionne les écarts absolus sur chaque dimension. Ce sont deux distances conceptuellement distinctes.

Peut-on calculer la distance de Manhattan avec des coordonnées négatives ?

Oui. La formule utilise des valeurs absolues, elle fonctionne donc pour tout couple de nombres réels, positifs ou négatifs.