UPD: Comme demandé dans les commentaires, j'ajoute un lien vers le schéma tournant Javascript
Malheureusement, le code javascript n'a pas pu être inséré dans le corps du message
Bon après-midi Récemment, j'ai lu le blog d'un urbaniste qui discutait de ce à quoi devrait ressembler un schéma de métro idéal. Le schéma de métro peut être dessiné selon deux principes:
- Le circuit doit être pratique et facile à mémoriser et à orienter.
- Le schéma doit correspondre à la géographie de la ville
De toute évidence, ces principes s'excluent mutuellement et le premier principe nécessite une distorsion importante de la réalité géographique.
Il suffit de rappeler à quoi ressemble le schéma du métro de Moscou avec de beaux anneaux et des lignes droites:
et comparer avec un plan géographiquement précis:
Le plan montre que les anneaux ne sont pas du tout parfaitement lisses et concentriques, les lignes se plient beaucoup plus que dans le schéma et la densité des stations dans le centre-ville est si élevée qu'il est presque impossible de comprendre le plan.
Et bien que la deuxième image reflète la réalité de manière beaucoup plus précise, il est clair qu’il est plus pratique d’utiliser le premier schéma pour planifier un itinéraire dans le métro.
Et puis la pensée suivante m'est venue à l'esprit: "À quoi ressemblerait le métro si le critère de construction du circuit était le temps nécessaire pour passer d'une station à une autre?" Autrement dit, si vous pouvez vous rendre rapidement d'une station à une autre, alors spatialement, ils seront situés à proximité sur le diagramme.
De toute évidence, dans un espace à deux dimensions, il est impossible de dessiner un tel schéma dans lequel la distance entre deux stations serait égale au temps de trajet de l'une à l'autre en raison de la topologie complexe du graphique du métro.
Il y a également un pressentiment que cela est exactement possible lors de la construction d'un schéma dans un espace avec une dimension élevée (l'estimation supérieure est n-1, où n est le nombre de stations). Pour un espace avec un petit nombre de dimensions, un tel schéma ne peut être construit qu'environ.
La tâche de construire une carte du métro en fonction du temps de trajet ressemble à une tâche d'optimisation typique.
Supposons que nous ayons un ensemble initial de coordonnées de toutes les stations (X, Y, Z) et une matrice cible de temps par paires (distances). Il est possible de construire la métrique «inexactitude» d'un ensemble de coordonnées donné puis de la minimiser par la méthode de descente en gradient pour chacune des coordonnées de chaque station. En tant que métrique, nous pouvons prendre une fonction simple de l'écart type des distances.
Eh bien, la seule chose qui reste est d'obtenir des données sur le temps à consacrer au trajet de n'importe quelle station du métro de Moscou à une autre.
La première pensée a été de vérifier l'API du métro Yandex et d'extraire ces données de là . Malheureusement, la description de l'API est introuvable. Regardez les heures manuellement dans l'application pendant une longue période (dans le métro, il y a 268 stations et la taille de la matrice de temps est de 268 * 268 = 71824). Par conséquent, j'ai décidé de comprendre les données sources de Yandex Metro. Puisqu'il n'y a pas d'accès au serveur, un fichier apk avec l'application a été téléchargé et les données nécessaires ont été trouvées. Toutes les informations sur le métro sont remarquablement structurées et stockées au format JSON dans le dossier d'archives actifs / metrokit / apk de l'application. Toutes les données sont stockées dans des structures auto-explicatives. Meta.json contient des informations sur les villes dont les schémas sont présents dans l'application, ainsi que l'ID de ces schémas.
{ "id": "sc77792237", "name": { "en": "Nizhny Novgorod", "ru": " ", "tr": "Nizhny Novgorod", "uk": "Ń– " }, "size": { "packed": 30300, "unpacked": 145408 }, "tags": [ "published" ], "aliases": [ "nizhny-novgorod" ], "logoUrl": "https://avatars.mds.yandex.net/get-bunker/135516/f2f0e33d8def90c56c189cfb57a8e6403b5a441c/orig", "version": "2c27fe1", "geoRegion": { "delta": { "lat": 0.168291, "lon": 0.219727 }, "center": { "lat": 56.326635, "lon": 43.992153 } }, "countryCode": "RU", "defaultAlias": "nizhny-novgorod" }
Par l'id du schéma, nous trouvons le dossier avec JSON lié à Moscou.
Le fichier data.json contient des informations de base sur le graphique du métro, y compris les noms des nœuds du graphique, les ID de nœud, les coordonnées géographiques des nœuds, des informations sur les transitions d'une station à une autre (id, temps de transition, type de transition - que ce soit en voiture ou à pied, dans la rue ou non, heure Nous sommes intéressés par les secondes) et aussi beaucoup d'informations supplémentaires sur les entrées et sorties de la gare. C'est assez facile à comprendre. Commençons à écrire du code pour construire notre circuit.
Nous importons les bibliothèques nécessaires:
import numpy as np import json import codecs import networkx as nx import matplotlib.pyplot as plt import pandas as pd import itertools import keras import keras.backend as K from mpl_toolkits.mplot3d import Axes3D from mpl_toolkits.mplot3d.proj3d import proj_transform from matplotlib.text import Annotation import pickle
La structure des dictionnaires et des listes python est entièrement cohérente avec la structure du format json, nous lisons donc les informations metro et créons des objets qui correspondent aux objets json.
names = json.loads(codecs.open( "l10n.json", "r", "utf_8_sig" ).read() ) graph = json.loads(codecs.open( "data.json", "r", "utf_8_sig" ).read() )
Nous créons un dictionnaire qui mappe les nœuds du graphique et la station (cela est nécessaire car les stations sont affectées aux noms, pas aux nœuds du graphique)
De plus, juste au cas où, nous enregistrerons les coordonnées des nœuds pour la possibilité de construire une carte géographique (normalisée à une plage de 0-1)
nodeStdict={} for stop in graph['stops']['items']: nodeStdict[stop['nodeId']]=stop['stationId'] coordDict={} for node in graph['nodes']['items']: coordDict[node['id']]=(node['attributes']['geoPoint']['lon'],node['attributes']['geoPoint']['lat']) lats=[] longs=[] for value in coordDict.values(): lats.append(value[1]) longs.append(value[0]) for k,v in coordDict.items(): coordDict[k]=((v[0]-np.min(longs))/(np.max(longs)-np.min(longs)),(v[1]-np.min(lats))/(np.max(lats)-np.min(lats)))
Créez un graphe de métro avec des connexions. Nous fixons le poids de chaque connexion. Le poids correspond au temps de trajet. Nous allons supprimer les nœuds qui ne sont pas des stations (à mon avis, ce sont des sorties du métro et les connexions sont nécessaires pour les cartes Yandex lors du calcul de l'heure, mais ne l'ont pas compris exactement), créer un dictionnaire d'ID de nœud - le vrai nom en russe
G=nx.Graph() for node in graph['nodes']['items']: G.add_node(node['id'])
Nous définissons à quelle branche (à quelle id de branche) chaque nœud appartient (cela sera nécessaire plus tard pour colorier les lignes de métro dans le diagramme)
def getlines(graph, G): nodetoline={} id_from={} id_to={} for lk in graph['tracks']['items']: id_from[lk['id']]=lk['fromNodeId'] id_to[lk['id']]=lk['toNodeId'] for line in graph['linesToTracks']['items']: if line['trackId'] in id_from.keys(): nodetoline[id_from[line['trackId']]]=line['lineId'] nodetoline[id_to[line['trackId']]]=line['lineId'] return nodetoline lines=getlines(graph,G)
La bibliothèque networkx vous permet de trouver la longueur de chemin la plus courte d'un nœud à un autre à l'aide de la fonction nx.shortest_path_length (G, id1, id2, weight = 'length'), afin que nous puissions supposer que nous avons terminé la préparation des données. La prochaine chose à faire est de préparer un modèle qui optimisera les coordonnées des stations.
Pour ce faire, nous allons déterminer ce qui sera donné à l'entrée, à la sortie, et comment nous allons optimiser la matrice de coordonnées de la station.
Supposons que nous ayons une matrice de toutes les coordonnées (3x268). La multiplication d'un vecteur à chaud (un vecteur où 0 est partout sauf une coordonnée unitaire à la place de n) de dimension 268 par cette matrice de coordonnées donnera 3 coordonnées correspondant à la station n. Si nous prenons une paire de vecteurs un-chaud et les multiplions par la matrice nécessaire, nous obtenons deux triplets de coordonnées. À partir d'une paire de coordonnées, vous pouvez calculer la distance euclidienne entre les stations. Ainsi, nous pouvons déterminer l'architecture de notre modèle:
à l'entrée, nous donnons quelques stations, à la sortie, nous obtenons la distance entre elles.
Après avoir décidé du format de données pour la formation du modèle, nous préparerons les données en utilisant la recherche de distance sur le graphique:
myIDs=list(G.nodes()) listofinputs1=[] listofinputs2=[] listofoutputs=[] for pair in itertools.product(G.nodes(), repeat=2): vec1=np.zeros((len(myIDs))) vec2=np.zeros((len(myIDs))) vec1[myIDs.index(pair[0])]=1 vec2[myIDs.index(pair[1])]=1 listofinputs1.append(vec1) listofinputs2.append(vec2)
Nous optimisons la matrice de coordonnées de la station en utilisant la méthode de descente en gradient.
Si nous utilisons le framework keras pour l'apprentissage automatique, nous obtenons ce qui suit:
np.random.seed(0) initweightmatrix=np.zeros((len(myIDs),3)) for i in range(len(myIDs)): initweightmatrix[i,:2]=coordDict[myIDs[i]] initweightmatrix[i,2]=np.random.randn()*0.001 def euclidean_distance(vects): x, y = vects sum_square = K.sum(K.square(x - y), axis=1, keepdims=True) return K.sqrt(K.maximum(sum_square, K.epsilon())) def eucl_dist_output_shape(shapes): shape1, shape2 = shapes return (shape1[0], 1) inp1=keras.layers.Input((len(myIDs),)) inp2=keras.layers.Input((len(myIDs),)) layer1=keras.layers.Dense(3,use_bias=None, activation=None) x1=layer1(inp1) x2=layer1(inp2) x=keras.layers.Lambda(euclidean_distance, output_shape=eucl_dist_output_shape)([x1, x2]) out=keras.layers.Dense(1,use_bias=None,activation=None)(x) model=keras.Model(inputs=[inp1,inp2],outputs=out) model.layers[2].set_weights([initweightmatrix]) model.layers[2].trainable=False model.compile(optimizer=keras.optimizers.Adam(lr=0.01), loss='mse')
notons que nous utilisons des coordonnées géographiques réelles comme coordonnées initiales dans layer1 - cela est nécessaire afin de ne pas tomber dans le minimum local de la fonction d'écart type. Nous initialisons la troisième coordonnée à une non nulle pour obtenir un gradient non nul (si au début la carte est absolument plate, le décalage de n'importe quelle station vers le haut ou vers le bas sera le même, donc le gradient est 0 et z ne sera pas optimisé). Le dernier élément de notre modèle (Dense (1)) affecte la mise à l'échelle du schéma pour s'adapter à la chronologie.
Nous mesurerons la distance en heures, pas en secondes, car les ordres de distances sont d'environ 1 heure, et pour un entraînement plus efficace du modèle, il est important que toutes les valeurs (données d'entrée, poids, cibles) soient approximativement du même ordre de grandeur. Si ces valeurs sont proches de 1, vous pouvez utiliser les valeurs de pas standard pour l'optimisation (0,001-0,01).
La ligne model.layers [2] .trainable = False fige les coordonnées des stations et au premier stade, un paramètre varie - l'échelle. Après avoir sélectionné l'échelle de notre schéma, nous dégelons les coordonnées et les optimisons déjà :
hist=model.fit([listofinputs1,listofinputs2],listofoutputs,batch_size=71824,epochs=200) model.layers[2].trainable=True model.layers[-1].trainable=False model.compile(optimizer=keras.optimizers.Adam(lr=0.01), loss='mse') hist2=model.fit([listofinputs1,listofinputs2],listofoutputs,batch_size=71824,epochs=200)
nous voyons que nous alimentons toutes les paires de stations à la fois, à la sortie toutes les distances et notre optimisation est la descente en gradient de lots complet (une étape sur toutes les données). La fonction de perte dans ce cas est l'écart-type, et vous pouvez voir qu'il était de 0,015 à la fin de la formation, ce qui signifie l'écart-type de moins de 1 minute pour n'importe quelle paire de stations. En d'autres termes, le schéma résultant vous permet de connaître avec précision la distance nécessaire pour se rendre d'une station à une autre par la distance en ligne droite entre les stations avec une précision de + -1 minute!
Mais voyons Ă quoi ressemble notre circuit!
obtenir les coordonnées des stations, prendre le codage couleur des lignes et construire une image 3D avec des signatures (le code pour un bel affichage des signatures est tiré
d'ici ):
class Annotation3D(Annotation): '''Annotate the point xyz with text s''' def __init__(self, s, xyz, *args, **kwargs): Annotation.__init__(self,s, xy=(0,0), *args, **kwargs) self._verts3d = xyz def draw(self, renderer): xs3d, ys3d, zs3d = self._verts3d xs, ys, zs = proj_transform(xs3d, ys3d, zs3d, renderer.M) self.xy=(xs,ys) Annotation.draw(self, renderer) def annotate3D(ax, s, *args, **kwargs): '''add anotation text s to to Axes3d ax''' tag = Annotation3D(s, *args, **kwargs) ax.add_artist(tag) fincoords=model.layers[2].get_weights() ccode={} for obj in graph['services']['items']: ccode[obj['id']]=('\#'+obj['attributes']['color'])[1:] xn = fincoords[0][:,0] yn = fincoords[0][:,1] zn = fincoords[0][:,2] l=[labels[idi] for idi in myIDs] colors=[ccode[lines[idi]] for idi in myIDs] xyzn = zip(xn, yn, zn) fig = plt.figure() ax = fig.gca(projection='3d') ax.scatter(xn,yn,zn, c=colors, marker='o') for j, xyz_ in enumerate(xyzn): annotate3D(ax, s=labels[myIDs[j]], xyz=xyz_, fontsize=9, xytext=(-3,3), textcoords='offset points', ha='right',va='bottom') plt.show()
Puisqu'il y avait des difficultés avec la conversion au format 3D interactif pour le navigateur, je poste les gifs:
la version sans texte est plus belle et reconnaissable:
xn = fincoords[0][:,0] yn = fincoords[0][:,1] zn = fincoords[0][:,2] l=[labels[idi] for idi in myIDs] colors=[ccode[lines[idi]] for idi in myIDs] xyzn = zip(xn, yn, zn) fig = plt.figure() ax = fig.gca(projection='3d') ax.scatter(xn,yn,zn, c=colors, marker='o') plt.show()
UPD: Ajoutez des lignes de métro de la couleur souhaitée et créez un gif. Lignes noires - transitions entre stations:
myedges=[(myIDs.index(edge[0]),myIDs.index(edge[1]))for edge in G.edges] xn = fincoords[0][:,0] yn = fincoords[0][:,1] zn = fincoords[0][:,2] l=[labels[idi] for idi in myIDs] c=[ccode[lines[idi]] for idi in myIDs] fig = plt.figure() ax = fig.gca(projection='3d') ax.scatter(x,y,z, c=c, marker='o',s=25) for edge in myedges: col='black' if c[edge[0]]==c[edge[1]]: col=c[edge[0]] ax.plot3D([x[edge[0]], x[edge[1]]], [y[edge[0]], y[edge[1]]], [z[edge[0]], z[edge[1]]], col) ims = [] def rotate(angle): ax.view_init(azim=angle) rot_animation = animation.FuncAnimation(fig, rotate, frames=np.arange(0, 362, 3), interval=70) rot_animation.save('rotation2.gif', dpi=80, writer=matplotlib.animation.PillowWriter(80))
Ce schéma permet de tirer des conclusions intéressantes qui ne sont pas aussi évidentes à partir d'autres schémas. Pour certaines branches, par exemple vertes, bleues ou violettes, le MCC (anneau rose) est presque inutile en raison de transplantations inconfortables, visibles à distance de l'anneau de ces branches. Les itinéraires les plus longs - d'un appartement commun à une autoroute claquante ou du vendredi (chevaux rouges et roses / bleus), les itinéraires longs sont également le conte d'Alma-Ata et Bunin Alley-Nekrasovka. À en juger par le plan, dans le nord de Moscou, il y a une duplication partielle des branches grises et vert clair - elles sont proches dans le diagramme. Il serait intéressant de voir comment les nouvelles lignes (WDC, BKL) et qui les utiliseront plus souvent. En tout cas, j'espère que de tels programmes peuvent être des outils intéressants pour l'analyse, l'inspiration et la planification des voyages.
La PS 3D n'est pas nécessaire, pour la version 2D il suffit de corriger légèrement le code. Mais dans le cas du schéma 2d, il est impossible d'obtenir une telle précision des distances.
