Wat is de Manhattan-afstand?

Afstandsmaatstaven zijn onmisbare hulpmiddelen om te meten hoe ver objecten of punten in de ruimte van elkaar verwijderd zijn. Deze maatstaven spelen een grote rol in veel vakgebieden, waaronder machine learning, robotica en geografische informatiesystemen. Door afstanden te kwantificeren kunnen we taken uitvoeren zoals patroonherkenning, data-clustering en ruimtelijke analyse, die zowel voor bedrijven als voor onderzoekers belangrijk zijn. 

De Manhattan-afstand, ook bekend als L1-afstand of taxiafstand, springt eruit als een bijzonder nuttige maat om afstanden te berekenen langs roosterachtige paden of tussen punten in multidimensionale ruimten. Hier kijken we zowel naar de wiskundige basis als naar hoe je de Manhattan-afstand implementeert in zowel Python als R. 

"Manhattan distance." Afbeelding door Dall‑E.

Onthoud dat de Manhattan-afstand slechts één onderdeel is van het bredere onderwerp afstandsmaatstaven, die in allerlei vakgebieden telkens weer opduiken. Wil je een expert worden in distance-based learning, bekijk dan onze cursus Designing Machine Learning Workflows in Python of onze cursus Cluster Analysis in R, afhankelijk van je voorkeurs­taal. 

De Manhattan-afstand definiëren

De Manhattan-afstand is een maatstaf om de afstand tussen twee punten langs een roosterachtig pad te bepalen. In tegenstelling tot de Euclidische afstand, die de kortste rechte lijn tussen twee punten meet, meet de Manhattan-afstand de som van de absolute verschillen tussen de coördinaten van de punten. Deze methode heet "Manhattan-afstand" omdat, net als een taxi die door de rechte straten van Manhattan rijdt, er alleen langs de roosterlijnen bewogen wordt. 

Wiskundig gezien is de Manhattan-afstand tussen twee punten in een n-dimensionale ruimte de som van de absolute verschillen van hun cartesische coördinaten. 

De formule voor de Manhattan-afstand gebruikt de absolutewaardefunctie, die negatieve verschillen simpelweg omzet in positieve waarden. Dit is cruciaal voor afstandsberekening, omdat zo alle afstanden niet-negatief zijn en de werkelijke scalair‑afstand weergeven, ongeacht de richting van de verplaatsing.

Manhattan-afstand berekenen en visualiseren

Zoals gezegd, wordt de Manhattan-afstand berekend door de absolute verschillen tussen de overeenkomstige coördinaten van twee punten op te tellen. Laten we dit verkennen met voorbeelden in 2D en 3D.

2D‑voorbeeld

Neem twee punten: A(1, 1) en B(4, 5):

1. Bereken |x₁ - x₂| = |1 - 4| = 3
2. Bereken |y₁ - y₂| = |1 - 5| = 4
3. Tel de resultaten op: 3 + 4 = 7

De Manhattan-afstand tussen A en B is dus 7 eenheden. 

Manhattan‑afstand van twee vectoren. Afbeelding door auteur.

In dit 2D‑rooster zie je dat de Manhattan‑afstand het pad volgt dat een taxi zou nemen, alleen horizontaal en verticaal bewegend om van punt A naar punt B te komen.

3D‑voorbeeld

Beschouw nu twee punten in 3D‑ruimte: A(1, 2, 3) en B(4, 5, 6):

1. Bereken |x₁ - x₂| = |1 - 4| = 3
2. Bereken |y₁ - y₂| = |2 - 5| = 3
3. Bereken |z₁ - z₂| = |3 - 6| = 3
4. Tel de resultaten op: 3 + 3 + 3 = 9

De Manhattan‑afstand tussen deze 3D‑punten is 9 eenheden.

Vergelijking met Euclidische afstand

Waar de Manhattan‑afstand het pad langs roosterlijnen meet, meet de Euclidische afstand de rechte lijn tussen twee punten — zoals ze zeggen: "as the crow flies" (hemelsbreed). 

Voor ons 2D‑voorbeeld:

• Manhattan‑afstand: 7 eenheden
• Euclidische afstand: √((1-4)^² + (1-5)^²) = 5 eenheden

Hier is een visuele vergelijking tussen de Manhattan‑ en Euclidische afstanden: 

Manhattan‑afstand vs. Euclidische afstand. Afbeelding door auteur.

In de Euclidische ruimte is de Euclidische afstand altijd kleiner dan of gelijk aan de Manhattan‑afstand. 

Kiezen tussen Manhattan‑ en Euclidische afstand

De Manhattan‑afstand is vooral nuttig in situaties waarin:

1. Beweging beperkt is tot roosterachtige paden (bijv. stadsblokken, printplaat‑layouts).
2. Diagonale beweging niet is toegestaan of duurder is.
3. Je werkt met hoog-dimensionale data in machine learning, waar het computationeel efficiënter kan zijn dan de Euclidische afstand.
4. Je verschillen in discrete of ordinale data analyseert.

Daarentegen is de Euclidische afstand geschikter wanneer:

1. Je fysieke afstanden in open ruimten meet.
2. Je werkt met continue data waarbij diagonale bewegingen even geldig zijn.

Toepassingen van de Manhattan‑afstand

De Manhattan‑afstand vindt toepassingen in diverse domeinen van informatica, data‑analyse en geospatiale technologie. Hier zijn enkele belangrijke gebieden waar de Manhattan‑afstand bijzonder nuttig is.

Padvindalgoritmen (bijv. A*‑algoritme) 

In roostergebaseerde omgevingen biedt de Manhattan‑afstand een snelle en effectieve heuristiek om de afstand tussen twee punten te schatten. Het is vooral nuttig in het A*‑algoritme, waar het kan helpen de zoekrichting efficiënter naar het doel te sturen in scenario’s waar beweging beperkt is tot horizontale en verticale richtingen. Denk aan routering in stadsstraten, doolhofoplossende algoritmen en bepaalde vormen van padvinden in videogame‑AI. 

Clusteringtechnieken (bijv. K‑means‑clustering) 

De Manhattan‑afstand kan worden gebruikt als afstandsmaat in clusteringalgoritmen, vooral bij hoog-dimensionale data. In K‑means‑clustering kan het gebruik van de Manhattan‑afstand in plaats van de Euclidische afstand betere resultaten opleveren, met name bij schaarse hoog-dimensionale data of in aanwezigheid van uitschieters. Ook in tekstclassificatie en documentclustering wordt het vaak geprefereerd vanwege de effectiviteit in schaarse vectorruimten. De lagere gevoeligheid van de Manhattan‑afstand voor extreme waarden in individuele dimensies kan in bepaalde datasets tot meer gebalanceerde clusters leiden.

Beeldherkenning 

De Manhattan‑afstand kan worden gebruikt om pixelwaarden of feature‑vectoren te vergelijken. Het is vooral handig bij template matching, waarbij je voorkomens van een kleine afbeelding binnen een grotere probeert te vinden. Het is ook waardevol in gezichtsherkenningssystemen, objectdetectie in videostreams of patroonmatching in grote afbeeldingsdatabases, waar snelheid cruciaal is en het kleine precisieverlies ten opzichte van de Euclidische afstand vaak verwaarloosbaar is.

Detectie van uitschieters 

De Manhattan‑afstand kan worden gebruikt om datapunten te identificeren die significant afwijken van andere punten in een dataset, omdat deze minder gevoelig is voor extreme waarden in afzonderlijke dimensies dan de Euclidische afstand. Deze eigenschap maakt het nuttig in anomaliedetectiesystemen, zoals bij fraudedetectie of netwerkbeveiliging. In financiële systemen kan de Manhattan‑afstand bijvoorbeeld ongebruikelijke transactiepatronen helpen identificeren zonder buitensporig beïnvloed te worden door een extreme waarde in één attribuut, wat mogelijk tot minder fouten leidt.

Geografische informatiesystemen (GIS) 

In GIS‑toepassingen kan de Manhattan‑afstand beweging langs een roosterachtig straatnetwerk modelleren, wat het nuttig maakt voor stadsplanning en logistiek. Het wordt gebruikt in locatie‑allocatieproblemen, zoals het bepalen van optimale locaties voor voorzieningen door de totale reisafstand in een stad te minimaliseren. De Manhattan‑afstand kan ook worden toegepast in ruimtelijke analysetaken, zoals het creëren van bufferzones rond lineaire kenmerken zoals wegen of rivieren. Stedenbouwkundigen kunnen de Manhattan‑afstand gebruiken om de toegankelijkheid van openbare diensten te analyseren, terwijl logistieke bedrijven deze kunnen inzetten om bezorgroutes in steden te optimaliseren.

Wiskundige eigenschappen van de Manhattan‑afstand

De Manhattan‑afstand heeft verschillende belangrijke wiskundige eigenschappen die haar bijzonder nuttig maken. Laten we twee kerneaspecten verkennen: de metrische ruimteeigenschappen en de robuustheid tegen uitschieters.

Eigenschappen van een metrische ruimte

De Manhattan‑afstand is een echte metriek, wat betekent dat ze voldoet aan alle vier de voorwaarden die vereist zijn voor een afstandsfunctie in een metrische ruimte:

1. Niet‑negativiteit: De afstand tussen twee punten is altijd niet‑negatief. d(x, y) ≥ 0 voor alle x en y.
2. Identiteit van ononderscheidbaren: De afstand tussen een punt en zichzelf is nul, en als de afstand tussen twee punten nul is, zijn het dezelfde punten. d(x, y) = 0 als en alleen als x = y.
3. Symmetrie: De afstand van punt A naar punt B is hetzelfde als van B naar A. d(x, y) = d(y, x) voor alle x en y.
4. Driehoeksongelijkheid: De afstand tussen twee punten is altijd kleiner dan of gelijk aan de som van de afstanden tussen die punten en een derde punt. d(x, z) ≤ d(x, y) + d(y, z) voor alle x, y en z.

In tegenstelling tot cosinusafstand, die niet voldoet aan de driehoeksongelijkheid, maakt het voldoen van de Manhattan‑afstand aan al deze eigenschappen haar nuttig in diverse wiskundige en computationele toepassingen. Bijvoorbeeld:

• In optimalisatie‑algoritmen kan de driehoeksongelijkheid worden gebruikt om zoekruimten efficiënt te snoeien.
• In datastructuren zoals metrische bomen maken deze eigenschappen snellere nearest‑neighbor‑zoektochten mogelijk.
• In machine learning kunnen algoritmen die op afstandsmaatstaven steunen (zoals k‑nearest neighbors) deze eigenschappen benutten voor theoretische garanties en efficiënte implementaties.

Betere discriminatie van uitschieters 

De Manhattan‑afstand biedt, met haar lineaire optelsom, vaak een betere discriminatie van uitschieters dan de Euclidische afstand, die de verschillen kwadrateert. Dit komt doordat de Manhattan‑afstand de absolute verschillen in elke dimensie onafhankelijk optelt, waardoor de overweldigende invloed van grote afwijkingen in één enkele dimensie afneemt.

Beschouw twee punten in een 2D‑ruimte: A(0, 0) en B(10, 0). Introduceer nu een uitschieter C met coördinaten (0, 100):

• Manhattan‑afstand tussen A en C: |0 - 0| + |0 - 100| = 100
• Euclidische afstand tussen A en C: √((0 - 0)^² + (0 - 100)^²) = 100
• Manhattan‑afstand tussen B en C: |10 - 0| + |0 - 100| = 110
• Euclidische afstand tussen B en C: √((10 - 0)^² + (0 - 100)^²) ≈ 100,5

Manhattan‑ vs. Euclidische afstand met uitschieters. Afbeelding door auteur

In dit voorbeeld onderscheidt de Manhattan‑afstand duidelijk de afstanden AC en BC, terwijl de Euclidische afstand ze bijna gelijk toont door het dominante effect van de uitschieter in de y‑coördinaat.

Deze eigenschap maakt de Manhattan‑afstand vooral nuttig in:

1. Hoog-dimensionale ruimten waar uitschieters vaak voorkomen, zoals bij beeldverwerking of tekstanalyse.
2. Clusteringalgoritmen waarbij je de impact van uitschieters op clustercentra wilt verminderen.
3. Anomaliedetectiesystemen waarin je uitschieters wilt identificeren zonder hun belang buitensporig te vergroten.

Doordat ze minder gevoelig is voor extreme waarden in afzonderlijke dimensies, kan de Manhattan‑afstand in veel realistische datasets — zeker die met ruis of onvolmaakte data — een meer gebalanceerde maat voor ongelijkheid bieden.

Manhattan‑afstand in Python en R

Hier verkennen we hoe je de Manhattan‑afstand berekent met Python en R. Elk voorbeeld toont verschillende benaderingen, van maatwerkfuncties tot library‑methoden.

Python‑voorbeelden

Python biedt meerdere manieren om de Manhattan‑afstand te berekenen. Laten we twee methoden bekijken.

1. Berekening met 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}")Mogelijk gemaakt door

Output: 

Manhattan distance (NumPy): 12Mogelijk gemaakt door

Deze methode gebruikt NumPy‑arrays rechtstreeks, wat zeer efficiënt kan zijn, vooral bij grote datasets of wanneer je in je analyse al met NumPy‑arrays werkt.

2. Berekening met SciPy’s cityblock()‑functie: 

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}")Mogelijk gemaakt door

Output:

Manhattan distance (SciPy): 12Mogelijk gemaakt door

SciPy biedt de functie cityblock(), die de Manhattan‑afstand berekent. Deze methode is eenvoudig en efficiënt, zeker wanneer je met SciPy in je project werkt. 

R‑voorbeelden

Ook R biedt meerdere manieren om de Manhattan‑afstand te berekenen. We bekijken twee benaderingen.

1. Een eigen functie maken

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))Mogelijk gemaakt door

Output:

"Manhattan distance (custom function): 6"Mogelijk gemaakt door

In dit voorbeeld maken we een eigen functie genaamd manhattan_distance. Deze functie neemt de coördinaten van twee punten als invoer en vindt de Manhattan‑afstand door de absolute verschillen van hun respectieve coördinaten op te tellen.

2. Gebruikmaken van de stats‑bibliotheek

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))Mogelijk gemaakt door

Output: 

"Manhattan distance: 12"Mogelijk gemaakt door

In het tweede voorbeeld gebruiken we de functie dist() uit het stats‑pakket om de Manhattan‑afstand te berekenen. Deze aanpak is handig bij matrices of meerdere punten, omdat het het proces aanzienlijk vereenvoudigt.

Conclusie

Het belang van de Manhattan‑afstand ligt in de eenvoud, computationele efficiëntie en robuustheid tegen uitschieters in bepaalde situaties. In tegenstelling tot de Euclidische afstand levert de Manhattan‑afstand vaak meer intuïtieve resultaten op in roostersystemen en kan ze efficiënter te berekenen zijn, vooral in hoog-dimensionale ruimten. 

Bovendien duiken de Manhattan‑afstand en andere afstandsmaatstaven op in een breed scala aan contexten. Naast onze cursus Designing Machine Learning Workflows in Python, met een hoofdstuk over distance‑based learning, en de cursus Cluster Analysis in R, die afstandsmaatstaven gebruikt voor classificatie en dimensionale reductie, kun je ook onze cursus Anomaly Detection in Python bekijken, die afstandsmaatstaven inzet voor uitschieterdetectie en feature scaling.  

Onthoud: de keuze van afstandsmaatstaf kan de prestaties en resultaten van je algoritmen sterk beïnvloeden. Door te begrijpen wanneer en hoe je de Manhattan‑afstand gebruikt, voeg je een krachtig hulpmiddel toe aan je data science‑toolkit. Blijf experimenteren, leren en de grenzen verleggen van wat mogelijk is met afstandsgebaseerde algoritmen!