Calcola la matrice della distanza di un insieme di siti dalle loro coordinate in Python | di Carlos J.Uribe | Intelligenza-Artificiale

Per costruire una matrice delle distanze, dobbiamo ottenere la distanza tra qualsiasi coppia di posizioni. Sembra semplice, ma la “distanza” dipende davvero dal contesto. Consideriamo il numero riportato dalle applicazioni di mappatura, come Google Maps, che tengono conto della rete stradale, dei ponti, dei parchi, eccetera.? Se sì, prendiamo la distanza che un pedone camminerebbe o che un’auto percorrerebbe? O forse semplicemente la buona vecchia lunghezza di una linea retta che collega i due punti? Chiaramente abbiamo molte possibili distanze tra cui scegliere, con diversi gradi di precisione. La prima domanda a cui dobbiamo rispondere è: come dovremmo definire la “distanza” nel particolare contesto di il nostro problemae a questa fase?

3.1. Dovrei fare il possibile per guadagnare un metro in più?

È naturale sentirsi tentati di utilizzare dati accurati. Alla fine, sappiamo tutti che l’accuratezza è intrinsecamente preziosa, e quindi siamo propensi a ricercare dati accurati, più sono, meglio è. Ma dobbiamo anche ricordare che dati più accurati comportano codice e dipendenze più complessi, e quindi tempi di sviluppo e manutenzione più lunghi. Poiché stiamo seguendo un approccio agilenon lasciamo che il migliore essere il nemico del BeneCOSÌ inizieremo nel modo più semplice possibile, per poi aggiungere gradualmente la complessità, solo se è giustificato.

A questo punto, dovendo trovare le distanze tra le località, potremmo fare come fanno molti e passare direttamente a soluzioni basate su API di terze parti che richiedono chiavi dell’app, credenziali o persino numeri di carta di credito per i fornitori di servizi cloud. Questo approccio va bene, ma spesso è inefficiente, perché possiamo dimenticarlo informazioni accurate apportano valore aggiunto, ma comportano anche costi aggiuntivi.

👁️ Non esiste la “precisione gratuita”

Ricordando che in generale si “paga sempre un prezzo” per accedere a dati accurati (che è strettamente correlato al concetto di Valore delle informazioni) è un altro motivo per cui adottare un approccio agile al problema è una linea d’azione più snella. Di partendo da semplici presupposti sul “livello di precisione richiesto”, e verificandone la validità sui dati relativi ai nostri problemici stiamo assicurando che, se alla fine avremo bisogno di aumentare la precisione dei nostri dati, “pagheremo un prezzo” ne vale la pena (previsto) risultati migliorati.

Quindi iniziamo in modo molto semplice. Abbiamo le coordinate. Prima idea: queste coordinate sono distribuite su particelle della Terra molto piccolo rispetto al raggio della Terra, quindi potremmo trattare le latitudini come coordinate Y e le longitudini come coordinate X su un piano 2D, e quindi calcolare semplicemente la distanza euclidea (termine di fantasia per la solita “linea retta”).

• Pro: formula semplice per la distanza, nessuna nuova dipendenza o dato, le relazioni spaziali tra i luoghi vengono conservate.
• Contro: latitudini e longitudini sono numeri adimensionali, quindi i numeri che otterremmo risolvendo il problema non sarebbero le distanze effettive. Ciò significa che alcune informazioni che ci interessano, come la distanza totale percorsa, non sarebbero disponibili, anche se riuscissimo a ottenere il tour ottimale.

I contro prevalgono sui pro, quindi abbiamo bisogno di un approccio più complesso (ma pur sempre semplice). Seconda idea: tratta le coordinate per quello che sono, punti sulla Terra, ma approssima la Terra come una sfera. Una sfera non ha la familiare geometria euclidea, quindi avremo bisogno di una formula non banale che consideri questa geometria sferica nel calcolo della distanza in “linea retta” tra due punti. Quindi ora è solo questione di implementare quella formula utilizzando il raggio della Terra. Potremmo farlo, ma ci affideremo invece a una famosa libreria che già lo fa, e anche meglio.

3.2. Utilità di geolocalizzazione con geopy

Se questa serie di articoli fosse focalizzata in particolare sulla scienza dei dati geospaziali, sarebbe utile dedicare del tempo a spiegare e implementare la formula per la distanza del cerchio massimouna bella opzione di base per calcolare le distanze “in linea retta” tra i punti su una sfera. Tuttavia, questa serie di articoli riguarda la creazione di un file sistema di pianificazione turistica basato sull’ottimizzazionequindi, invece di creare le nostre formule per i servizi geospaziali, faremo affidamento su Geopia fare il lavoro pesante per noi. In questo modo, continuiamo a concentrarci sul raggiungimento rapido di una soluzione.

Installalo eseguendo un prompt di Anaconda (o all’interno dell’ambiente conda che abbiamo creato nel file primo articolose l’hai creato tu) quanto segue:

conda install -y -c conda-forge geopy=2.3.0

Ora facciamo una dimostrazione con geopy solo per due sedi.

3.3. Arrivare ai punti

Date le coordinate di due punti, il geodesic funzione di geopy calcola la distanza della geodetica che li collega attraverso la superficie terrestre. In Geometria, il geodetico è il percorso di distanza minima tra punti su un dato spazio metrico. Nel nostro familiare spazio euclideo, linee rette sono le geodetiche. In uno spazio sferico, grandi cerchi Sono. Lo “spazio” sottostante che è Geopy geodesic la funzione considera è un modello ellissoidale accurato della Terra.

👁 Un cerchio massimo è fantastico, ma un’ellisse lo è ancora di più

Prima ho detto che considereremmo la Terra come una sfera, perché era l’approssimazione più semplice e praticabile. In realtà la Terra non è una sfera, ma un ellissoide, un solido dalla geometria più complessa. Ora che geopy ci eviterà di codificare le nostre funzioni per geometrie non euclidee, possiamo migliorare la nostra approssimazione della Terra e impiegare metodi più accurati distanza ellissoidale tra due punti, invece della distanza ortodromica. Un modello terrestre migliore per le stesse righe di codice. Questa è davvero precisione gratuita, quindi perché non accettarla?

Ecco una funzione che calcola la distanza ellissoidale tra il punto 1 e il punto 2, in metri:

from geopy.distance import geodesic
def ellipsoidal_distance(p1, p2) -> float:
""" Calculate distance (in meters) between p1 and p2, where 
each point is represented as a tuple (lat, lon) """
return geodesic(p1, p2).meters

Qual è la distanza tra la Tour Eiffel e il Louvre?

p1 = df_sites.loc('Tour Eiffel')
p2 = df_sites.loc('Louvre')
ellipsoidal_distance(p1, p2)  # output: 3173.119635531859

3173 metri, circa 3,2 km. Google Maps dice che sono 3,5 km. IL calcolato la distanza è inferiore dell’8,6% rispetto al “vero“distanza. Le nostre gambe si preoccupano solo di errori assoluti di distanza, però, che in questo caso ammonta a soli 330 metri in più da percorrere, rispetto alla distanza stimata. Non sembra un errore significativo per un turista che si aspetta di passeggiare tutto il giorno in una grande città.

E tra la Tour Eiffel e Port de Suffren?

ellipsoidal_distance(
df_sites.loc('Tour Eiffel'),
df_sites.loc('Port de Suffren')
)  # output: 328.3147101635456

328 metri, questa volta più bassi del 6% (solo 22 metri in meno) rispetto ai 350 metri forniti da Google Maps. Non è poi così male per applicare una formula. Come ci si aspetterebbe, più i punti sono vicini, minore è la possibilità che le strade vadano a zigzag e appaiano delle svolte, e quindi minore è l’errore commesso dal modello ellissoidale. Sembra abbastanza buono per i nostri scopi attuali.

Ora dobbiamo applicare questa funzione a tutte le coppie di posizioni, ottenendo così la matrice delle distanze necessaria al modello TSP.

3.4. Dalle coordinate alla matrice delle distanze

Questa è la parte facile, in cui dobbiamo semplicemente ripetere il ciclo su tutti i siti due volte e calcolare e memorizzare la distanza tra ciascuna coppia. La funzione seguente fa questo. Tieni presente che la metrica della distanza viene passata come argomento facoltativo, essendo la distanza ellissoidale che abbiamo utilizzato prima del valore predefinito. Lasciamo la porta aperta a migliori parametri di distanza da adottare in futuro.

def compute_distance_matrix(df_sites, dist_metric=ellipsoidal_distance):
""" Creates an N x N distance matrix from a dataframe of N locations 
with a latitute column and a longitude column """
df_dist_matrix = pd.DataFrame(index=df_sites.index, 
columns=df_sites.index)
for orig, orig_loc in df_sites.iterrows():  # for each origin
for dest, dest_loc in df_sites.iterrows():  # for each destination
df_dist_matrix.at(orig, dest) = dist_metric(orig_loc, dest_loc)
return df_dist_matrix
df_distances = compute_distance_matrix(df_sites)
display(df_distances)

E ce l’abbiamo! Come previsto, la diagonale della matrice è zero e la matrice è simmetrica. L’indice e le colonne del dataframe di output contengono i nomi dei siti di input.

Funzionalità dimostrata. Ora possiamo fare di meglio per facilitare l’uso di questa funzione. Racchiudiamo questa funzionalità all’interno di una classe in modo conveniente, per un facile riutilizzoe, cosa più importante, per integrazione più semplice con il modello di ottimizzazione del TSP che abbiamo costruito nello sprint precedente.