Wann würde man die Entfernung von Manhattan im Gegensatz zur euklidischen Entfernung verwenden?

18

Ich versuche nach einem guten Argument zu suchen, warum man beim maschinellen Lernen die Manhattan-Distanz über die euklidische Distanz verwenden sollte .

Das Nächste, was ich bisher zu einem guten Argument gefunden habe, ist diese MIT-Vorlesung .

Um 36:15 Uhr sehen Sie auf den Folien die folgende Aussage:

"Verwenden Sie normalerweise die euklidische Metrik. Manhattan ist möglicherweise geeignet, wenn unterschiedliche Dimensionen nicht vergleichbar sind. "

Kurz nachdem der Professor gesagt hat, dass die Anzahl der Beine eines Reptils von 0 bis 4 variiert (während die anderen Merkmale binär sind und nur von 0 bis 1 variieren), wird das Merkmal "Anzahl der Beine" viel höher ausfallen Gewicht, wenn der euklidische Abstand verwendet wird. Sicher genug, das ist in der Tat richtig. Man hätte aber auch dieses Problem, wenn man die Manhattan-Distanz verwendet (nur, dass das Problem etwas gemildert würde, weil wir den Unterschied nicht wie bei der euklidischen Distanz ausgleichen).

Ein besserer Weg, um das obige Problem zu lösen, besteht darin, die Funktion "Anzahl der Beine" zu normalisieren, sodass ihr Wert immer zwischen 0 und 1 liegt.

Da es daher einen besseren Weg gibt, das Problem zu lösen, schien es dem Argument, die Manhattan-Distanz zu verwenden, in diesem Fall zumindest meiner Meinung nach einen stärkeren Punkt zu fehlen.

Weiß eigentlich jemand, warum und wann jemand Manhattan-Distanz über Euklidisch nutzen würde? Kann mir jemand ein Beispiel geben, bei dem die Verwendung der Entfernung nach Manhattan bessere Ergebnisse liefert?

Tiago
quelle

Antworten:

4

Nach diesem interessanten Artikel ist der Manhattan-Abstand (L1-Norm) dem euklidischen Abstand (L2-Norm) für den Fall hochdimensionaler Daten vorzuziehen:

https://bib.dbvis.de/uploadedFiles/155.pdf

Die Autoren der Arbeit gehen sogar noch einen Schritt weiter und schlagen vor, Lk-Normabstände mit einem Bruchteil von k für sehr hochdimensionale Daten zu verwenden, um die Ergebnisse entfernungsbasierter Algorithmen wie Clustering zu verbessern.

Pablo Suau
quelle
stats.stackexchange.com/a/99191 bietet eine umfassendere Antwort
mic
3

Ich kann ein paar Ideen aus Wikipedia vorschlagen .

  1. Wenn Sie weniger Wert auf Ausreißer legen möchten, wird Manhattan Distance versuchen, alle Fehler gleichermaßen zu reduzieren, da der Gradient eine konstante Größe hat.
  2. Wenn Ihr Rauschen Laplace-verteilt ist, wird der MLE durch Minimieren der Manhattan-Schätzung gefunden.
Jacques Kvam
quelle
3

Ich habe im praktischen maschinellen Lernen mit Scikit-Learn und TensorFlow etwas gefunden, das möglicherweise eine Ahnung von diesem Problem hat

Sowohl der RMSE als auch der MAE sind Möglichkeiten, den Abstand zwischen zwei Vektoren zu messen: dem Vektor der Vorhersagen und dem Vektor der Zielwerte. Verschiedene Abstandsmaße oder Normen sind möglich:

  • Die Berechnung der Wurzel einer Quadratsumme (RMSE) entspricht der euklidischen Norm: Es ist der Begriff der Entfernung, mit der Sie vertraut sind. Es wird auch die ℓ2-Norm genannt (...)

  • Die Berechnung der Absolutsumme (MAE) entspricht der norm1-Norm (...). Es wird manchmal als Manhattan-Norm bezeichnet, weil es die Entfernung zwischen zwei Punkten in einer Stadt misst, wenn Sie nur auf orthogonalen Stadtblöcken fahren können.

  • Im Allgemeinen gibt (...) ℓ 0 nur die Anzahl der Nicht-Null-Elemente im Vektor an, und ℓ∞ gibt den maximalen Absolutwert im Vektor an.

  • Je höher der Normindex, desto mehr konzentriert er sich auf große Werte und vernachlässigt kleine. Aus diesem Grund ist der RMSE für Ausreißer empfindlicher als der MAE. Wenn jedoch Ausreißer exponentiell selten sind (wie bei einer glockenförmigen Kurve), arbeitet der RMSE sehr gut und wird im Allgemeinen bevorzugt.

Damian Melniczuk
quelle
2

Die Verwendung der Manhattan-Entfernung hängt stark von der Art des Koordinatensystems ab, das Ihr Datensatz verwendet. Während der euklidische Abstand den kürzesten oder minimalen Abstand zwischen zwei Punkten angibt, weist Manhattan spezifische Implementierungen auf.

Wenn wir beispielsweise einen Schachdatensatz verwenden, ist die Verwendung der Manhattan-Entfernung geeigneter als die der euklidischen Entfernung. Eine andere Verwendung wäre, wenn Sie den Abstand zwischen Häusern kennen möchten, die nur wenige Blocks voneinander entfernt sind.

Möglicherweise möchten Sie auch die Manhattan-Entfernung berücksichtigen, wenn die Eingabevariablen vom Typ her nicht ähnlich sind (z. B. Alter, Geschlecht, Größe usw.). Aufgrund des Fluchs der Dimensionalität wissen wir, dass der euklidische Abstand mit zunehmender Anzahl von Dimensionen eine schlechte Wahl wird.

Auf den Punkt gebracht: Manhattan-Distanz funktioniert im Allgemeinen nur, wenn die Punkte in Form eines Gitters angeordnet sind und das Problem, an dem wir arbeiten, der Distanz zwischen den Punkten nur zusammen mit den Gittern mehr Priorität einräumt, nicht jedoch der geometrischen Distanz.

Saurabh Jain
quelle