Direkt zum Inhalt

Was ist Manhattan Distance?

Lerne anhand von Programmierbeispielen in Python und R, wie du die Manhattan-Distanz berechnest und anwendest, und erforsche ihre Verwendung beim maschinellen Lernen und bei der Pfadfindung.
Aktualisierte 16. Jan. 2025  · 8 Min. Lesezeit

Entfernungsmaße sind wichtige Instrumente, um zu messen, wie weit Objekte oder Punkte im Raum voneinander entfernt sind. Diese Metriken spielen in vielen Bereichen eine große Rolle, zum Beispiel beim maschinellen Lernen, in der Robotik und bei geografischen Informationssystemen. Durch die Quantifizierung von Entfernungen können wir Aufgaben wie Mustererkennung, Datenclustering und räumliche Analysen durchführen, die sowohl für gewinnorientierte Unternehmen als auch für Forscher wichtig sind. 

Die Manhattan-Distanz, auch L1-Distanz oder Taxi-Distanz genannt, ist ein besonders nützliches Maß für die Berechnung von Distanzen in gitterartigen Pfaden oder zwischen Punkten in mehrdimensionalen Räumen. Hier werden wir uns sowohl die mathematischen Grundlagen als auch die Implementierung der Manhattan-Distanz in Python und R ansehen. 

Manhattan distance image by Dall-E."Manhattan distance". Bild von Dall-E.

Vergiss nicht, dass die Manhattan-Distanz nur ein Teil des umfassenderen Themas der Distanzmetriken ist, die immer wieder in allen möglichen Bereichen auftauchen. Um ein Experte im Fernstudium zu werden, solltest du unseren Kurs Designing Machine Learning Workflows in Python oder unseren Kurs Cluster Analysis in R in Betracht ziehen, je nachdem, welche Sprache du bevorzugst. 

Definition der Manhattan-Distanz

Die Manhattan-Distanz ist eine Metrik, die verwendet wird, um den Abstand zwischen zwei Punkten in einem gitterartigen Pfad zu bestimmen. Im Gegensatz zum euklidischen Abstand, der die kürzestmögliche Linie zwischen zwei Punkten misst, misst der Manhattan-Abstand die Summe der absoluten Differenzen zwischen den Koordinaten der Punkte. Diese Methode wird "Manhattan-Distanz" genannt, weil sie wie ein Taxi, das durch die gitterartigen Straßen Manhattans fährt, entlang der Gitterlinien fahren muss. 

Mathematisch gesehen ist der Manhattan-Abstand zwischen zwei Punkten in einem n-dimensionalen Raum die Summe der absoluten Differenzen ihrer kartesischen Koordinaten. 

Manhattan-Abstandsformeln für 2- und 3-dimensionale Vektoren

Die Manhattan-Abstandsformel beinhaltet die Absolutwertfunktion, die negative Differenzen einfach in positive Werte umwandelt. Das ist wichtig für die Berechnung der Entfernung, da es sicherstellt, dass alle Entfernungsmessungen nicht negativ sind und die wahre skalare Entfernung unabhängig von der Fahrtrichtung widerspiegeln.

Berechnung und Visualisierung der Manhattan-Distanz

Wie wir bereits gesagt haben, wird die Manhattan-Distanz berechnet, indem die absoluten Differenzen zwischen den entsprechenden Koordinaten von zwei Punkten addiert werden. Das wollen wir nun anhand von Beispielen im 2D- und 3D-Raum untersuchen.

2D Beispiel

Betrachte zwei Punkte: A(1, 1) und B(4, 5):

  1. Berechne |x₁ - x₂| = |1 - 4| = 3
  2. Berechne |y₁ - y₂| = |1 - 5| = 4
  3. Fasse die Ergebnisse zusammen: 3 + 4 = 7

Die Manhattan-Distanz zwischen A und B beträgt also 7 Einheiten. 

Manhattan-Abstand von zwei VektorenManhattan-Abstand von zwei Vektoren. Bild vom Autor.

In diesem 2D-Gitter kannst du sehen, dass die Manhattan-Distanz dem Weg eines Taxis folgt, das sich nur horizontal und vertikal bewegt, um von Punkt A nach Punkt B zu kommen.

3D Beispiel

Betrachten wir nun zwei Punkte im 3D-Raum: A(1, 2, 3) und B(4, 5, 6):

  1. Berechne |x₁ - x₂| = |1 - 4| = 3
  2. Berechne |y₁ - y₂| = |2 - 5| = 3
  3. Berechne |z₁ - z₂| = |3 - 6| = 3
  4. Fasse die Ergebnisse zusammen: 3 + 3 + 3 = 9

Der Manhattan-Abstand zwischen diesen 3D-Punkten beträgt 9 Einheiten.

Vergleich mit euklidischem Abstand

Während die Manhattan-Distanz den Weg entlang von Gitterlinien misst, misst die euklidische Distanz die geradlinige Entfernung zwischen zwei Punkten oder "Luftlinie", wie man sagt. 

Für unser 2D-Beispiel:

  • Manhattan Entfernung: 7 Einheiten
  • Euklidischer Abstand: √((1-4 + (1-5) = 5 Einheiten

Hier ist ein visueller Vergleich zwischen der Manhattan- und der Euklidischen Distanz: 

Vergleich des Manhattan-Abstands und des Euklidischen Abstands zweier Vektoren auf einer kartesischen KoordinatenebeneManhattan-Abstand vs. Euklidischer Abstand. Bild vom Autor.

Im euklidischen Raum ist der euklidische Abstand immer kleiner als oder gleich dem Manhattan-Abstand. 

Die Wahl zwischen Manhattan-Distanz und Euklidischer Distanz

Die Manhattan-Distanz ist besonders nützlich in Szenarien, in denen:

  1. Die Bewegung ist auf gitterartige Pfade beschränkt (z. B. Stadtblöcke, Platinenlayouts).
  2. Diagonale Bewegungen sind nicht erlaubt oder kosten mehr Geld.
  3. Du arbeitest beim maschinellen Lernen mit hochdimensionalen Daten, bei denen es rechnerisch effizienter sein kann als der euklidische Abstand.
  4. Du analysierst Unterschiede in diskreten oder ordinalen Daten.

Im Gegensatz dazu ist der euklidische Abstand besser geeignet, wenn:

  1. Du misst physikalische Entfernungen in offenen Räumen.
  2. Du arbeitest mit kontinuierlichen Daten, bei denen diagonale Bewegungen ebenso gültig sind.

Anwendungen der Manhattan-Distanz

Die Manhattan-Distanz findet in verschiedenen Bereichen der Informatik, der Datenanalyse und der Geospatialtechnologie Anwendung. Hier sind einige Schlüsselbereiche, in denen die Manhattan-Distanz besonders nützlich ist.

Pfadfindungsalgorithmen (z. B. A*-Algorithmus) 

In rasterbasierten Umgebungen bietet die Manhattan-Distanz eine schnelle und effektive Heuristik zur Schätzung der Entfernung zwischen zwei Punkten. Sie ist besonders nützlich im A*-Algorithmus, wo sie dabei helfen kann, die Suche in Szenarien, in denen die Bewegung auf horizontale und vertikale Richtungen beschränkt ist, effizienter zum Ziel zu führen. Denke an die Straßenführung in Städten, Algorithmen zum Lösen von Labyrinthen und bestimmte Arten der Wegfindung in Videospielen. 

Clustering-Techniken (z. B. K-Means-Clustering) 

Die Manhattan-Distanz kann als Abstandsmaß in Clustering-Algorithmen verwendet werden, vor allem wenn es um hochdimensionale Daten geht. Beim K-Means-Clustering kann die Verwendung des Manhattan-Abstands anstelle des Euklidischen Abstands zu besseren Ergebnissen führen, vor allem wenn es sich um spärliche hochdimensionale Daten handelt oder Ausreißer vorhanden sind. Auch bei der Textklassifizierung und dem Clustering von Dokumenten wird es aufgrund seiner Effektivität bei spärlichen Vektorräumen oft bevorzugt. Die geringere Empfindlichkeit der Manhattan-Distanz gegenüber Extremwerten in einzelnen Dimensionen kann in bestimmten Datensätzen zu ausgewogeneren Clustering-Ergebnissen führen.

Bilderkennung 

Der Manhattan-Abstand kann verwendet werden, um Pixelwerte oder Merkmalsvektoren zu vergleichen. Sie ist besonders nützlich beim Vorlagenabgleich, wenn du versuchst, ein kleines Bild in einem größeren Bild zu finden. Sie ist auch bei Gesichtserkennungssystemen, bei der Objekterkennung in Videostreams oder beim Musterabgleich in großen Bilddatenbanken nützlich, wo es auf Geschwindigkeit ankommt und der geringe Präzisionsverlust im Vergleich zur euklidischen Distanz oft vernachlässigbar ist.

Ausreißer-Erkennung 

Der Manhattan-Abstand kann verwendet werden, um Datenpunkte zu identifizieren, die sich signifikant von anderen in einem Datensatz unterscheiden, da er im Vergleich zum euklidischen Abstand weniger empfindlich auf Extremwerte in einzelnen Dimensionen reagiert. Diese Eigenschaft macht sie nützlich für Systeme zur Erkennung von Anomalien, wie sie zum Beispiel bei der Betrugserkennung oder der Netzwerksicherheit eingesetzt werden. In Finanzsystemen zum Beispiel kann die Manhattan-Distanz dabei helfen, ungewöhnliche Transaktionsmuster zu erkennen, ohne von extremen Werten in einem einzelnen Attribut übermäßig beeinflusst zu werden, was zu weniger Fehlern führen kann.

Geografische Informationssysteme (GIS) 

In GIS-Anwendungen kann die Manhattan-Distanz die Bewegung entlang eines gitterartigen Straßennetzes modellieren, was sie für die Stadtplanung und Logistik nützlich macht. Sie wird bei Standortverteilungsproblemen eingesetzt, z. B. bei der Bestimmung optimaler Standorte für Einrichtungen, die die Gesamtentfernung in einer Stadt minimieren. Die Manhattan-Distanz kann auch bei räumlichen Analyseaufgaben eingesetzt werden, z. B. bei der Erstellung von Pufferzonen um lineare Merkmale wie Straßen oder Flüsse. Stadtplaner könnten die Manhattan-Distanz nutzen, um die Erreichbarkeit öffentlicher Dienstleistungen zu analysieren, während Logistikunternehmen sie einsetzen könnten, um Lieferrouten in Städten zu optimieren.

Mathematische Eigenschaften der Manhattan-Distanz

Die Manhattan-Distanz besitzt mehrere wichtige mathematische Eigenschaften, die sie besonders nützlich machen. Untersuchen wir zwei wichtige Aspekte: die Eigenschaften des metrischen Raums und seine Robustheit gegenüber Ausreißern.

Eigenschaften des metrischen Raums

Der Manhattan-Abstand ist eine echte Metrik, das heißt, er erfüllt alle vier Bedingungen, die für eine Abstandsfunktion in einem metrischen Raum erforderlich sind:

  1. Nicht-Negativität: Der Abstand zwischen zwei Punkten ist immer nicht-negativ. d(x, y) ≥ 0 für alle x und y.
  2. Die Identität der Unsichtbaren: Der Abstand zwischen einem Punkt und sich selbst ist gleich Null. Wenn der Abstand zwischen zwei Punkten gleich Null ist, sind sie derselbe Punkt. d(x, y) = 0, wenn und nur wenn x = y.
  3. Symmetrie: Die Entfernung von Punkt A zu Punkt B ist die gleiche wie die Entfernung von B zu A. d(x, y) = d(y, x) für alle x und y.
  4. Ungleichheit im Dreieck: Der Abstand zwischen zwei Punkten ist immer kleiner oder gleich der Summe der Abstände zwischen diesen Punkten und einem dritten Punkt. d(x, z) ≤ d(x, y) + d(y, z) für alle x, y und z.

Im Gegensatz zur Kosinusdistanz, die die Dreiecksungleichung nicht erfüllt, ist die Manhattan-Distanz aufgrund ihrer Übereinstimmung mit all diesen Eigenschaften in verschiedenen mathematischen und rechnerischen Anwendungen nützlich. Zum Beispiel:

  • In Optimierungsalgorithmen kann die Dreiecksungleichung genutzt werden, um Suchräume effizient zu beschneiden.
  • In Datenstrukturen wie metrischen Bäumen ermöglichen diese Eigenschaften eine schnellere Suche nach den nächsten Nachbarn.
  • Beim maschinellen Lernen können Algorithmen, die auf Abstandsmetriken (wie k-nearest neighbors) beruhen, diese Eigenschaften für theoretische Garantien und effiziente Implementierungen nutzen.

Verbesserte Ausreißerunterscheidung 

Die Manhattan-Distanz mit ihrem linearen Summationsansatz bietet oft eine bessere Unterscheidung von Ausreißern als die euklidische Distanz, bei der die Unterschiede quadriert werden. Dieser Unterschied ergibt sich daraus, dass die Manhattan-Distanz die absoluten Unterschiede in jeder Dimension unabhängig voneinander akkumuliert und so den überwältigenden Einfluss großer Diskrepanzen in einer einzelnen Dimension reduziert.

Betrachte zwei Punkte in einem 2D-Raum: A(0, 0) und B(10, 0). Nun wollen wir einen Ausreißerpunkt C mit den Koordinaten (0, 100) einführen:

  • Manhattan-Abstand zwischen A und C: |0 - 0| + |0 - 100| = 100
  • Euklidischer Abstand zwischen A und C: √((0 - 0 + (0 - 100) = 100
  • Manhattan-Entfernung zwischen B und C: |10 - 0| + |0 - 100| = 110
  • Euklidischer Abstand zwischen B und C: √((10 - 0 + (0 - 100) ≈ 100,5

Veranschaulichung der Manhattan- gegenüber der euklidischen Distanz zwischen PunktenManhattan- gegenüber der euklidischen Distanz mit Ausreißern. Bild vom Autor

In diesem Beispiel unterscheidet der Manhattan-Abstand deutlich zwischen den Abständen AC und BC, während der euklidische Abstand sie aufgrund des dominanten Effekts des Ausreißers in der y-Koordinate als fast gleich anzeigt.

Diese Eigenschaft macht die Manhattan-Distanz besonders nützlich in:

  1. Hochdimensionale Räume, in denen Ausreißer häufig vorkommen, wie z.B. in der Bildverarbeitung oder Textanalyse.
  2. Clustering-Algorithmen, bei denen du die Auswirkungen von Ausreißern auf die Clusterschwerpunkte reduzieren willst.
  3. Systeme zur Erkennung von Anomalien, bei denen du Ausreißer identifizieren willst, ohne ihre Bedeutung überzubewerten.

Da die Manhattan-Distanz weniger empfindlich auf Extremwerte in einzelnen Dimensionen reagiert, kann sie in vielen realen Datensätzen ein ausgewogeneres Maß für die Unähnlichkeit liefern, vor allem in solchen mit verrauschten oder unvollkommenen Daten.

Manhattan Distance in Python und R

Hier erfahren wir, wie man den Manhattan-Abstand mit Python und R berechnet. Jedes Beispiel zeigt verschiedene Ansätze, von eigenen Funktionen bis hin zu Bibliotheksmethoden.

Python Beispiele

Python bietet mehrere Möglichkeiten, den Manhattan-Abstand zu berechnen. Lass uns zwei verschiedene Methoden ausprobieren.

1. Berechnungen mit NumPy-Arrays:

import numpy as np
point_a_np = np.array([1, 1, 1])
point_b_np = np.array([4, 5, 6])
distance_numpy = np.sum(np.abs(point_a_np - point_b_np))
print(f"Manhattan distance (NumPy): {distance_numpy}")

Output: 

Manhattan distance (NumPy): 12

Diese Methode verwendet NumPy-Arrays direkt, was sehr effizient sein kann, vor allem wenn du mit großen Datensätzen arbeitest oder wenn du bereits mit NumPy-Arrays in deiner Analyse arbeitest.

2. Berechnung mit der cityblock()-Funktion von SciPy: 

from scipy.spatial.distance import cityblock
point_a = (1, 1, 1)
point_b = (4, 5, 6)
distance_scipy = cityblock(point_a, point_b)
print(f"Manhattan distance (SciPy): {distance_scipy}")

Output:

Manhattan distance (SciPy): 12

SciPy bietet die Funktion cityblock(), mit der du den Manhattan-Abstand berechnen kannst. Diese Methode ist einfach und effizient, besonders wenn du in deinem Projekt mit SciPy arbeitest. 

R Beispiele

R bietet auch mehrere Möglichkeiten, den Manhattan-Abstand zu berechnen. Schauen wir uns zwei verschiedene Ansätze an.

1. Erstellen einer benutzerdefinierten Funktion

manhattan_distance <- function(x1, y1, x2, y2) {
  abs(x1 - x2) + abs(y1 - y2)
}
# Example points 
point1 <- c(3, 5) # (x1, y1) 
point2 <- c(1, 9) # (x2, y2) 
# Calculate Manhattan distance between point1 and point2 
distance <- manhattan_distance(point1[1], point1[2], point2[1], point2[2]) 
print(paste("Manhattan distance (custom function):", distance))

Output:

"Manhattan distance (custom function): 6"

In diesem Beispiel erstellen wir eine eigene Funktion namens manhattan_distance. Diese Funktion nimmt die Koordinaten von zwei Punkten als Eingaben und findet den Manhattan-Abstand, indem sie die absoluten Differenzen ihrer jeweiligen Koordinaten addiert.

2. Verwendung der Statistikbibliothek

point_a <- c(1, 1, 1)
point_b <- c(4, 5, 6)
distance_builtin <- stats::dist(rbind(point_a, point_b), method = "manhattan")
print(paste("Manhattan distance:", distance_builtin))

Output: 

"Manhattan distance: 12"

Im zweiten Beispiel verwenden wir die Funktion dist() aus dem Paket stats, um den Manhattan-Abstand zu berechnen. Dieser Ansatz ist nützlich, wenn du mit Matrizen oder mehreren Punkten arbeitest, da er den Prozess erheblich vereinfacht.

Fazit

Die Bedeutung der Manhattan-Distanz liegt in ihrer Einfachheit, ihrer Berechnungseffizienz und ihrer Robustheit gegenüber Ausreißern in bestimmten Szenarien. Im Gegensatz zur euklidischen Distanz liefert die Manhattan-Distanz in rasterbasierten Systemen oft intuitivere Ergebnisse und kann effizienter berechnet werden, vor allem in hochdimensionalen Räumen. 

Außerdem werden die Manhattan-Distanz und andere Entfernungsmaße an vielen verschiedenen Stellen angegeben. Neben unserem Kurs Designing Machine Learning Workflows in Python, der ein Kapitel über distanzbasiertes Lernen enthält, und dem Kurs Cluster Analysis in R, der distanzbasierte Metriken für die Klassifizierung und Dimensionalitätsreduktion verwendet, kannst du auch unseren Kurs Anomaly Detection in Python besuchen, der distanzbasierte Metriken für die Erkennung von Ausreißern und die Skalierung von Merkmalen verwendet.  

Denke daran, dass die Wahl der Distanzmetrik die Leistung und die Ergebnisse deiner Algorithmen erheblich beeinflussen kann. Wenn du verstehst, wann und wie du die Manhattan-Distanz nutzen kannst, erhältst du ein mächtiges Werkzeug für dein Data Science Toolkit. Experimentiere weiter, lerne und verschiebe die Grenzen dessen, was mit distanzbasierten Algorithmen möglich ist!


Vinod Chugani's photo
Author
Vinod Chugani
LinkedIn

Als erfahrener Experte für Data Science, maschinelles Lernen und generative KI widmet sich Vinod der Weitergabe von Wissen und der Befähigung angehender Data Scientists, in diesem dynamischen Bereich erfolgreich zu sein.

Häufig gestellte Fragen

Wie ist die Manhattan-Distanz im Vergleich zur euklidischen Distanz?

Während die Manhattan-Distanz den Weg entlang von Gitternetzlinien (wie Stadtblöcken) misst, misst die euklidische Distanz die geradlinige Entfernung zwischen zwei Punkten. Der Manhattan-Abstand eignet sich oft besser für rasterbasierte Systeme oder hochdimensionale Daten, während der euklidische Abstand besser für offene Räume oder kontinuierliche Daten geeignet ist.

Warum wird die Manhattan-Entfernung "Taxidistanz" genannt?

Sie heißt Taxi-Entfernung, weil sie die Entfernung darstellt, die ein Taxi in einer Stadt mit einem gitterähnlichen Muster (wie Manhattan) fahren würde, wo die Route nur aus horizontalen und vertikalen Segmenten besteht.

Welche Vorteile hat die Manhattan-Distanz gegenüber anderen Distanzmetriken?

Die Manhattan-Distanz ist rechnerisch effizient, weniger empfindlich gegenüber Ausreißern in hochdimensionalen Räumen und liefert oft intuitivere Ergebnisse in rasterbasierten Systemen. Sie ist außerdem eine echte Metrik und erfüllt alle vier Bedingungen, die für eine Distanzfunktion in einem metrischen Raum erforderlich sind.

Kann die Manhattan-Distanz für das Clustering beim maschinellen Lernen verwendet werden?

Ja, die Manhattan-Distanz kann in Clustering-Algorithmen wie K-means verwendet werden, vor allem wenn es um hochdimensionale oder spärliche Daten geht. In diesen Szenarien kann sie im Vergleich zur euklidischen Distanz manchmal robustere Ergebnisse liefern.

Kann die Manhattan-Distanz mit negativen Koordinatenwerten verwendet werden?

Ja, die Manhattan-Distanz kann mit negativen Koordinaten verwendet werden. Die Formel verwendet absolute Werte, d.h. sie funktioniert mit allen realen Zahlen, ob positiv oder negativ.

Themen

Lernen mit DataCamp

Zertifizierung verfügbar

Kurs

Intermediate Python

4 hr
1.2M
Verbessere deine Data Science-Fähigkeiten, indem du mit Matplotlib Visualisierungen erstellst und DataFrames mit Pandas manipulierst.
Siehe DetailsRight Arrow
Kurs starten
Mehr anzeigenRight Arrow