Cos'è la distanza di Manhattan?

Le metriche di distanza sono strumenti essenziali per misurare quanto sono lontani tra loro oggetti o punti nello spazio. Queste metriche giocano un ruolo importante in molti campi, tra cui machine learning, robotica e sistemi informativi geografici. Quantificando le distanze, possiamo svolgere attività come il riconoscimento di pattern, il clustering dei dati e l’analisi spaziale, fondamentali sia per le aziende a scopo di lucro sia per i ricercatori.

La distanza di Manhattan, nota anche come distanza L1 o distanza del tassì, si distingue come misura particolarmente utile per calcolare le distanze in percorsi a griglia o tra punti in spazi multidimensionali. Qui esamineremo sia le basi matematiche sia come implementare la distanza di Manhattan in Python e R.

"Distanza di Manhattan." Immagine di Dall-E.

Ricorda: la distanza di Manhattan è solo una parte del più ampio tema delle metriche di distanza, che ricorrono in ogni tipo di ambito. Per diventare esperto nell’apprendimento basato sulla distanza, valuta il nostro corso Designing Machine Learning Workflows in Python o il corso Cluster Analysis in R, a seconda della tua lingua preferita.

Definire la distanza di Manhattan

La distanza di Manhattan è una metrica usata per determinare la distanza tra due punti lungo un percorso a griglia. A differenza della distanza euclidea, che misura la linea più corta tra due punti, la distanza di Manhattan misura la somma delle differenze assolute tra le coordinate dei punti. Questo metodo si chiama "distanza di Manhattan" perché, come un tassì che percorre le strade a griglia di Manhattan, deve muoversi lungo le linee della griglia.

Matematicamente, la distanza di Manhattan tra due punti in uno spazio n-dimensionale è la somma delle differenze assolute delle loro coordinate cartesiane.

La formula della distanza di Manhattan incorpora la funzione valore assoluto, che converte semplicemente eventuali differenze negative in valori positivi. Questo è fondamentale per il calcolo della distanza, poiché garantisce che tutte le misurazioni siano non negative, riflettendo la vera distanza scalare indipendentemente dalla direzione del movimento.

Calcolo e visualizzazione della distanza di Manhattan

Come abbiamo detto, la distanza di Manhattan si calcola sommando le differenze assolute tra le coordinate corrispondenti di due punti. Esploriamolo ora con esempi in 2D e 3D.

Esempio 2D

Considera due punti: A(1, 1) e B(4, 5):

1. Calcola |x₁ - x₂| = |1 - 4| = 3
2. Calcola |y₁ - y₂| = |1 - 5| = 4
3. Somma i risultati: 3 + 4 = 7

Quindi, la distanza di Manhattan tra A e B è 7 unità.

Distanza di Manhattan di due vettori. Immagine dell’autore.

In questa griglia 2D, puoi vedere che la distanza di Manhattan segue il percorso che farebbe un tassì, muovendosi solo orizzontalmente e verticalmente per andare dal punto A al punto B.

Esempio 3D

Ora, considera due punti nello spazio 3D: A(1, 2, 3) e B(4, 5, 6):

1. Calcola |x₁ - x₂| = |1 - 4| = 3
2. Calcola |y₁ - y₂| = |2 - 5| = 3
3. Calcola |z₁ - z₂| = |3 - 6| = 3
4. Somma i risultati: 3 + 3 + 3 = 9

La distanza di Manhattan tra questi punti 3D è 9 unità.

Confronto con la distanza euclidea

Mentre la distanza di Manhattan misura il percorso lungo le linee della griglia, la distanza euclidea misura la distanza in linea retta tra due punti, o, come si suol dire, "in linea d’aria".

Per il nostro esempio 2D:

• Distanza di Manhattan: 7 unità
• Distanza euclidea: √((1-4)^² + (1-5)^²) = 5 unità

Ecco un confronto visivo tra le distanze di Manhattan ed euclidea:

Distanza di Manhattan vs. distanza euclidea. Immagine dell’autore.

Nello spazio euclideo, la distanza euclidea è sempre minore o uguale alla distanza di Manhattan.

Scegliere tra distanza di Manhattan e distanza euclidea

La distanza di Manhattan è particolarmente utile negli scenari in cui:

1. Il movimento è limitato a percorsi a griglia (ad es. isolati cittadini, layout di circuiti stampati).
2. Il movimento diagonale non è consentito o è più costoso.
3. Lavori con dati ad alta dimensionalità nel machine learning, dove può essere computazionalmente più efficiente della distanza euclidea.
4. Analizzi differenze in dati discreti o ordinali.

Al contrario, la distanza euclidea è più appropriata quando:

1. Misuri distanze fisiche in spazi aperti.
2. Lavori con dati continui in cui i movimenti diagonali sono ugualmente validi.

Applicazioni della distanza di Manhattan

La distanza di Manhattan trova applicazione in vari campi dell’informatica, dell’analisi dei dati e della tecnologia geospaziale. Ecco alcune aree chiave in cui è particolarmente utile.

Algoritmi di pathfinding (ad es. algoritmo A*) 

In ambienti basati su griglie, la distanza di Manhattan fornisce un’euristica rapida ed efficace per stimare la distanza tra due punti. È particolarmente utile nell’algoritmo A*, dove può guidare la ricerca verso l’obiettivo in modo più efficiente in scenari in cui il movimento è limitato alle direzioni orizzontale e verticale. Pensa al routing nelle strade cittadine, agli algoritmi per risolvere labirinti e a certi tipi di pathfinding nell’IA dei videogiochi.

Tecniche di clustering (ad es. K-Means clustering) 

La distanza di Manhattan può essere usata come metrica nei metodi di clustering, soprattutto con dati ad alta dimensionalità. Nel clustering K-Means, usare la distanza di Manhattan invece di quella euclidea può produrre risultati migliori, specialmente con dati sparsi ad alta dimensionalità o in presenza di outlier. Inoltre, è spesso preferita nella classificazione di testi e nel clustering di documenti grazie alla sua efficacia con spazi vettoriali sparsi. La minore sensibilità della distanza di Manhattan ai valori estremi in singole dimensioni può portare a risultati di clustering più equilibrati in certi dataset.

Riconoscimento di immagini 

La distanza di Manhattan può essere usata per confrontare valori di pixel o vettori di caratteristiche. È particolarmente utile nel template matching, quando cerchi occorrenze di una piccola immagine all’interno di una più grande. È preziosa anche nei sistemi di riconoscimento facciale, nel rilevamento di oggetti in flussi video o nel pattern matching in grandi database di immagini, dove la velocità è cruciale e la lieve perdita di precisione rispetto alla distanza euclidea è spesso trascurabile.

Rilevamento di outlier 

La distanza di Manhattan può essere utilizzata per identificare punti dati significativamente diversi dagli altri in un dataset perché è meno sensibile ai valori estremi in singole dimensioni rispetto alla distanza euclidea. Questa proprietà la rende utile nei sistemi di rilevamento delle anomalie, come quelli usati per il rilevamento di frodi o la sicurezza di rete. Nei sistemi finanziari, per esempio, la distanza di Manhattan può aiutare a identificare pattern di transazioni insoliti senza essere eccessivamente influenzata da valori estremi in un singolo attributo, riducendo potenzialmente gli errori.

Sistemi Informativi Geografici (GIS) 

Nelle applicazioni GIS, la distanza di Manhattan può modellare il movimento lungo una rete stradale a griglia, risultando utile per la pianificazione urbana e la logistica. È utilizzata in problemi di localizzazione-allocazione, come determinare le posizioni ottimali per strutture minimizzando la distanza totale percorsa in una città. La distanza di Manhattan può essere applicata anche in compiti di analisi spaziale, come la creazione di buffer attorno a elementi lineari come strade o fiumi. I pianificatori urbani potrebbero usarla per analizzare l’accessibilità dei servizi pubblici, mentre le aziende di logistica potrebbero impiegarla per ottimizzare i percorsi di consegna in città.

Proprietà matematiche della distanza di Manhattan

La distanza di Manhattan possiede diverse importanti proprietà matematiche che la rendono particolarmente utile. Esploriamo due aspetti chiave: le sue proprietà di spazio metrico e la sua robustezza agli outlier.

Proprietà di spazio metrico

La distanza di Manhattan è una metrica vera e propria, il che significa che soddisfa tutte e quattro le condizioni richieste per una funzione di distanza in uno spazio metrico:

1. Non negatività: La distanza tra due punti è sempre non negativa. d(x, y) ≥ 0 per tutti x e y.
2. Identità degli indiscernibili: La distanza tra un punto e se stesso è zero e, se la distanza tra due punti è zero, essi coincidono. d(x, y) = 0 se e solo se x = y.
3. Simmetria: La distanza dal punto A al punto B è la stessa che da B ad A. d(x, y) = d(y, x) per tutti x e y.
4. Disuguaglianza triangolare: La distanza tra due punti è sempre minore o uguale alla somma delle distanze tra quei punti e un terzo punto. d(x, z) ≤ d(x, y) + d(y, z) per tutti x, y e z.

A differenza della distanza coseno, che non soddisfa la disuguaglianza triangolare, l’aderenza della distanza di Manhattan a tutte queste proprietà la rende utile in varie applicazioni matematiche e computazionali. Per esempio:

• Negli algoritmi di ottimizzazione, la disuguaglianza triangolare può essere usata per potare efficientemente gli spazi di ricerca.
• In strutture dati come gli alberi metrici, queste proprietà consentono ricerche del vicino più prossimo più veloci.
• Nel machine learning, gli algoritmi che si basano su metriche di distanza (come k-nearest neighbors) possono sfruttare queste proprietà per garanzie teoriche e implementazioni efficienti.

Maggiore discriminazione degli outlier 

La distanza di Manhattan, con il suo approccio di somma lineare, offre spesso una migliore discriminazione degli outlier rispetto alla distanza euclidea, che eleva al quadrato le differenze. Questa distinzione nasce perché la distanza di Manhattan accumula indipendentemente le differenze assolute in ciascuna dimensione, riducendo l’influenza eccessiva di grandi discrepanze in una singola dimensione.

Considera due punti in uno spazio 2D: A(0, 0) e B(10, 0). Ora introduciamo un punto outlier C con coordinate (0, 100):

• Distanza di Manhattan tra A e C: |0 - 0| + |0 - 100| = 100
• Distanza euclidea tra A e C: √((0 - 0)^² + (0 - 100)^²) = 100
• Distanza di Manhattan tra B e C: |10 - 0| + |0 - 100| = 110
• Distanza euclidea tra B e C: √((10 - 0)^² + (0 - 100)^²) ≈ 100,5

Distanza di Manhattan vs distanza euclidea con outlier. Immagine dell’autore

In questo esempio, la distanza di Manhattan distingue chiaramente tra le distanze AC e BC, mentre la distanza euclidea le mostra quasi uguali a causa dell’effetto dominante dell’outlier nella coordinata y.

Questa proprietà rende la distanza di Manhattan particolarmente utile in:

1. Spazi ad alta dimensionalità in cui gli outlier sono comuni, come nell’elaborazione di immagini o nell’analisi di testi.
2. Algoritmi di clustering in cui si vuole ridurre l’impatto degli outlier sui centroidi dei cluster.
3. Sistemi di rilevamento delle anomalie in cui si desidera identificare outlier senza sovrastimarne eccessivamente l’importanza.

Essendo meno sensibile ai valori estremi in singole dimensioni, la distanza di Manhattan può fornire una misura più equilibrata di dissimilarità in molti dataset reali, specialmente quelli rumorosi o imperfetti.

Distanza di Manhattan in Python e R

Qui esploreremo come calcolare la distanza di Manhattan usando Python e R. Ogni esempio mostrerà approcci diversi, da funzioni personalizzate a metodi di libreria.

Esempi in Python

Python offre diversi modi per calcolare la distanza di Manhattan. Vediamo due metodi differenti.

1. Calcolo usando array NumPy:

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}")Offerto da

Output: 

Manhattan distance (NumPy): 12Offerto da

Questo metodo usa direttamente gli array NumPy, che possono essere molto efficienti, soprattutto con dataset di grandi dimensioni o quando stai già lavorando con array NumPy nella tua analisi.

2. Calcolo usando la funzione cityblock() di 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}")Offerto da

Output:

Manhattan distance (SciPy): 12Offerto da

SciPy fornisce la funzione cityblock(), che calcola la distanza di Manhattan. Questo metodo è semplice ed efficiente, soprattutto quando utilizzi SciPy nel tuo progetto.

Esempi in R

Anche R offre più modi per calcolare la distanza di Manhattan. Esaminiamo due approcci diversi.

1. Creazione di una funzione personalizzata

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))Offerto da

Output:

"Manhattan distance (custom function): 6"Offerto da

In questo esempio, creiamo una funzione personalizzata chiamata manhattan_distance. Questa funzione prende in input le coordinate di due punti e trova la distanza di Manhattan sommando le differenze assolute delle rispettive coordinate.

2. Utilizzo della libreria stats

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))Offerto da

Output: 

"Manhattan distance: 12"Offerto da

Nel secondo esempio, utilizziamo la funzione dist() del pacchetto stats per calcolare la distanza di Manhattan. Questo approccio è utile quando si lavora con matrici o più punti, poiché semplifica notevolmente il processo.

Conclusione

L’importanza della distanza di Manhattan risiede nella sua semplicità, efficienza computazionale e robustezza agli outlier in certi scenari. A differenza della distanza euclidea, spesso fornisce risultati più intuitivi nei sistemi a griglia e può essere più efficiente da calcolare, soprattutto in spazi ad alta dimensionalità.

Inoltre, la distanza di Manhattan e le altre metriche di distanza compaiono in un’ampia varietà di contesti. Oltre al nostro corso Designing Machine Learning Workflows in Python, che include un capitolo sull’apprendimento basato sulla distanza, e al corso Cluster Analysis in R, che usa metriche di distanza per classificazione e riduzione della dimensionalità, puoi anche dare un’occhiata al corso Anomaly Detection in Python, che utilizza metriche di distanza per il rilevamento di outlier e lo scaling delle feature.

Ricorda: la scelta della metrica di distanza può influire in modo significativo sulle prestazioni e sui risultati dei tuoi algoritmi. Capendo quando e come usare la distanza di Manhattan, aggiungi un potente strumento al tuo toolkit di data science. Continua a sperimentare, imparare e spingere i confini di ciò che è possibile con gli algoritmi basati sulla distanza!