UPD: По просьбам в комментах добавляю ссылку на вращабельную схему на Javascript
К сожалению, код javascript вставить в тело поста не удалось
Добрый день! Недавно я читал блог одного урбаниста, который рассуждал о том, какая должна быть идеальная схема метро.Схему метро можно рисовать исходя из двух принципов:
Очевидно, что эти принципы взаимоисключающие и первый принцип требует существенного искажения географической реальности.
Достаточно вспомнить, как выглядит схема Московского метро с красивыми кольцами и прямыми линиями:
и сравнить с географически точным планом:
На плане видно что кольца вовсе не являются идеально ровными и концентрическими, линии изгибаются гораздо сильнее, чем в схеме, а плотность станций в центре города настолько велика, что в плане практически невозможно разобраться.
И хотя второе изображение гораздо точнее отображает реальность, видно, что пользоваться для планирования маршрута в метро удобнее первой схемой.
И тут мне в голову пришла следующая мысль: «Как выглядело бы метро, если бы критерием для построения схемы являлось время, требуемое для перемещения от одной станции к другой?». То есть если от одной станции до другой добраться быстро, то пространственно они на схеме располагались бы недалеко.
Очевидно, что в двумерном пространстве невозможно нарисовать такую схему, в которой расстояние между двумя станциями равнялось бы времени путешествия от одной к другой из-за сложной топологии графа метро.
Также есть догадка, что такое точно возможно при построении схемы в пространстве с высокой размерностью (верхняя оценка n-1, где n- число станций). Для пространства с небольшим количеством измерений такую схему можно построить лишь приближенно.
Задача построения карты метро по времени путешествия выглядит типичной задачей оптимизации.
Пусть у нас есть начальный набор координат всех станций (X,Y,Z) и целевая матрица попарных времен (расстояний). Можно сконструировать метрику «неправильность» данного набора координат и далее минимизировать ее методом градиентного спуска по каждой из координат каждой станции. В качестве метрики можно взять простую функцию среднеквадратичного отклонения расстояний.
Что же, осталось дело за малым — нужно получить данные о том, сколько времени следует затратить на путешествие от любой станции московского метро к любой другой.
Первой мыслью было проверить api яндекс метро и вытащить оттуда эти данные. К сожалению, описания api и найти не удалось. Смотреть времена вручную в приложении долго (в метро 268 станций и размер матрицы времен 268*268=71824). Поэтому я решил разобраться в исходных данных Яндекс Метро. Так как доступа к серверу нет, был скачан apk файл с приложением и обнаружены необходимые данные. Вся информация о метро замечательно структурирована и хранится в формате JSON в папке assets/metrokit/ apk-архива приложения. Все данные хранятся в self-explanotary структурах. Meta.json содержит информацию о городах, схемы которых присутствуют в приложении, а также id данных схем.
По id схемы находим папку с JSON, относящиеся и к Москве.
Файл data.json содержит основную информацию о графе метро, включая названия узлов графа, id узлов, географические координаты узлов, информацию о переходах с одной станции на другую (id, время перехода, тип перехода — перегон или пешком, по улицу или нет, время интересующее нас в секундах) а также много дополнительной информации о входах и выходах со станции. С этим достаточно легко разобраться. Начнем писать код для построения нашей схемы.
Импортируем необходимые библиотеки:
Структура словарей и списков python полностью соответствует структуре формата json, поэтому читаем иннформацию о метро и создаем объекты, соответствующие json объектам.
Создаем словарь, ставящий в соответствие узлы графа и станции (это необходима для так как к именам привязаны именно станции, а не узлы графа)
Также на всякий случай сохраним координаты узлов для возможности построения географической карты (нормированы на диапазон 0-1)
Создадим граф метро со связями. Зададим веса каждой связи. Вес соответствует времени в пути. Удалим узлы, не являющиеся станциями (по-моему это выходы из метро а связи к ним нужны для яндекс карт при расчете времени, но точно не разбирался) создадим словарь id узла- реальное название на русском языке
Определим к какой ветке (к какому id ветки) относится каждый узел (это понадобится позже для раскрашивания линий метро на схеме)
библиотека networkx позволяет найти длину кратчайшего пути от одного узла к другому при помощи функции nx.shortest_path_length(G, id1, id2, weight='length'), поэтому можно считать что с подготовкой данных закончили. Следующее, что необходимо сделать — подготовить модель, которая будет оптимизировать координаты станций.
Для этого разберемяся, что будет даваться на вход, на выход и как будем оптимизировать матрицу координат станций.
Предположим, у нас есть матрица всех координат (3x268). Умножение one-hot вектора (вектора, где везде 0, кроме одной единичной координаты на месте n) размерности 268 на данную матрицу координат даст 3 координаты, соответствующие станции n. Если мы возьмем пару one-hot векторов и умножим их на необходимую матрицу, то получим две тройки координат. Из пары координат можно расчитать евклидово расстояние между станциями. Таким образом, можно определить архитектуру нашей модели:
на вход мы подаем пару станций, на выходе получаем расстояние между ними.
После того, как мы определились с форматом данных для обучения модели, подготовим данные с использованием поиска расстояний на графе:
Оптимизируем методом градиентного спуска матрицу координат станций.
Если мы будем использовать фреймворк keras для машинного обучения, то получим следующее:
заметим, что в качестве начальных координат в слое layer1 мы используем реальные географические координаты -это необходимо для того, чтобы не попасть в локальный минимум функции СКО. Третью координату инициализируем ненулевой для получения ненулевого градиента (если в начале карта будет абсолютно плоской, смещение любой станции вверх или вниз будет равнозначно, следовательно градиент равен 0 и оптимизации z не произойдет). Последний элемент нашей модели (Dense(1)) влияет на масштабирование схемы для соответствия временной шкале.
Расстояние будем измерять в часах, а не секундах, так как порядки расстояний — около 1 часа, а для более эффективного обучении модели важно, чтобы все величины (входные данные, веса, targetы) были примерно одного порядка по величине. Если эти значения близки к 1, то можно использовать стандартные значения шага при оптимизации (0.001-0.01).
Строка model.layers[2].trainable=False замораживает координаты станций и на первом этапе варьируется один параметр — масштаб. После подбора масштаба нашей схемы размораживаем координаты и оптимизируем уже их:
видим, что на вход подаем сразу все пары станций, на выходе — все расстояния и наша оптимизация- full batch gradient descent (один шаг на всех данных). Функция loss в данном случае — среднеквадратичное отклонение и можно видеть, что оно составило 0.015 в конце обучения, что значит среднеквадратичное отклонение менее чем в 1 минуты для любой пары станций. Иными словами, полученная схема позволяет точно узнать расстояние, которое требуется, чтобы добраться от одной станции к другой по расстоянию по прямой между станциями сточностью +-1 минута!
Но давайте посмотрим, как выглядит наша схема!
получим координаты станций, возьмем цветовую кодировку линий и построим 3d изображение с подписями (код для красивого отображения подписей взят отсюда):
Так как возникли трудности с конвертацией в интерактивный 3d формат для браузера, выкладываю гифки:
более красиво и узнаваемо выглядит версия без текста:
UPD: Добавим линии метро нужного цвета и создадим гифку. Черные линии — переходы между станциями:
Из данной схемы можно сделать некоторые интересные выводы, которые не столь очевидны из других схем. Для некоторых веток, например зеленой, синей или фиолетовой МЦК (розовое кольцо) практически бесполезно из-за неудобных пересадок, что видно в удалении кольца от этих веток. Самые длинные по времени маршруты — от коммунарки до щелкого или пятницкого шоссе (коней красной и розовая/синяя линии) длинные маршруты так же алмаатинская-рассказовка и бунинская аллея-некрасовка. На севере Москвы, судя по плану, происходит частичное дублирование серой и салатовой ветками — они находятся рядом на схеме. Было бы итересно посмотреть на то, как новые линии (МЦД, БКЛ) и кто чаще будет пользоваться ими. В любом случае, надеюсь, подобные схемы могут быть интересным инструментам анализа, вдохновения и планирования поездок.
P.S. 3D не обязательно, для 2D варианта достаточно чуть-чуть исправить код. Но в случае 2d схемы добиться подобной точности расстояний невозможно.
К сожалению, код javascript вставить в тело поста не удалось
Добрый день! Недавно я читал блог одного урбаниста, который рассуждал о том, какая должна быть идеальная схема метро.Схему метро можно рисовать исходя из двух принципов:
- Схема должна быть удобной и простой для запоминания и ориентирования
- Схема должна соответствовать географии города
Очевидно, что эти принципы взаимоисключающие и первый принцип требует существенного искажения географической реальности.
Достаточно вспомнить, как выглядит схема Московского метро с красивыми кольцами и прямыми линиями:
и сравнить с географически точным планом:
На плане видно что кольца вовсе не являются идеально ровными и концентрическими, линии изгибаются гораздо сильнее, чем в схеме, а плотность станций в центре города настолько велика, что в плане практически невозможно разобраться.
И хотя второе изображение гораздо точнее отображает реальность, видно, что пользоваться для планирования маршрута в метро удобнее первой схемой.
И тут мне в голову пришла следующая мысль: «Как выглядело бы метро, если бы критерием для построения схемы являлось время, требуемое для перемещения от одной станции к другой?». То есть если от одной станции до другой добраться быстро, то пространственно они на схеме располагались бы недалеко.
Очевидно, что в двумерном пространстве невозможно нарисовать такую схему, в которой расстояние между двумя станциями равнялось бы времени путешествия от одной к другой из-за сложной топологии графа метро.
Также есть догадка, что такое точно возможно при построении схемы в пространстве с высокой размерностью (верхняя оценка n-1, где n- число станций). Для пространства с небольшим количеством измерений такую схему можно построить лишь приближенно.
Задача построения карты метро по времени путешествия выглядит типичной задачей оптимизации.
Пусть у нас есть начальный набор координат всех станций (X,Y,Z) и целевая матрица попарных времен (расстояний). Можно сконструировать метрику «неправильность» данного набора координат и далее минимизировать ее методом градиентного спуска по каждой из координат каждой станции. В качестве метрики можно взять простую функцию среднеквадратичного отклонения расстояний.
Что же, осталось дело за малым — нужно получить данные о том, сколько времени следует затратить на путешествие от любой станции московского метро к любой другой.
Первой мыслью было проверить api яндекс метро и вытащить оттуда эти данные. К сожалению, описания api и найти не удалось. Смотреть времена вручную в приложении долго (в метро 268 станций и размер матрицы времен 268*268=71824). Поэтому я решил разобраться в исходных данных Яндекс Метро. Так как доступа к серверу нет, был скачан apk файл с приложением и обнаружены необходимые данные. Вся информация о метро замечательно структурирована и хранится в формате JSON в папке assets/metrokit/ apk-архива приложения. Все данные хранятся в self-explanotary структурах. Meta.json содержит информацию о городах, схемы которых присутствуют в приложении, а также id данных схем.
{ "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" }
По id схемы находим папку с JSON, относящиеся и к Москве.
Файл data.json содержит основную информацию о графе метро, включая названия узлов графа, id узлов, географические координаты узлов, информацию о переходах с одной станции на другую (id, время перехода, тип перехода — перегон или пешком, по улицу или нет, время интересующее нас в секундах) а также много дополнительной информации о входах и выходах со станции. С этим достаточно легко разобраться. Начнем писать код для построения нашей схемы.
Импортируем необходимые библиотеки:
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
Структура словарей и списков python полностью соответствует структуре формата json, поэтому читаем иннформацию о метро и создаем объекты, соответствующие 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() )
Создаем словарь, ставящий в соответствие узлы графа и станции (это необходима для так как к именам привязаны именно станции, а не узлы графа)
Также на всякий случай сохраним координаты узлов для возможности построения географической карты (нормированы на диапазон 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)))
Создадим граф метро со связями. Зададим веса каждой связи. Вес соответствует времени в пути. Удалим узлы, не являющиеся станциями (по-моему это выходы из метро а связи к ним нужны для яндекс карт при расчете времени, но точно не разбирался) создадим словарь id узла- реальное название на русском языке
G=nx.Graph() for node in graph['nodes']['items']: G.add_node(node['id']) #graph['links'] for link in graph['links']['items']: #G.add_edges_from([(link['fromNodeId'],link['toNodeId'])]) G.add_edge(link['fromNodeId'], link['toNodeId'], length=link['attributes']['time']) nodestoremove=[] for node in G.nodes(): if len(G.edges(node))<2: nodestoremove.append(node) for node in nodestoremove: G.remove_node(node) labels={} for node in G.nodes(): try: labels[node]=names['keysets']['generated'][nodeStdict[node]+'-name']['ru'] except: labels[node]='error'
Определим к какой ветке (к какому id ветки) относится каждый узел (это понадобится позже для раскрашивания линий метро на схеме)
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)
библиотека networkx позволяет найти длину кратчайшего пути от одного узла к другому при помощи функции nx.shortest_path_length(G, id1, id2, weight='length'), поэтому можно считать что с подготовкой данных закончили. Следующее, что необходимо сделать — подготовить модель, которая будет оптимизировать координаты станций.
Для этого разберемяся, что будет даваться на вход, на выход и как будем оптимизировать матрицу координат станций.
Предположим, у нас есть матрица всех координат (3x268). Умножение one-hot вектора (вектора, где везде 0, кроме одной единичной координаты на месте n) размерности 268 на данную матрицу координат даст 3 координаты, соответствующие станции n. Если мы возьмем пару one-hot векторов и умножим их на необходимую матрицу, то получим две тройки координат. Из пары координат можно расчитать евклидово расстояние между станциями. Таким образом, можно определить архитектуру нашей модели:
на вход мы подаем пару станций, на выходе получаем расстояние между ними.
После того, как мы определились с форматом данных для обучения модели, подготовим данные с использованием поиска расстояний на графе:
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) #listofinputs.append([vec1,vec2]) listofoutputs.append(nx.shortest_path_length(G, pair[0], pair[1], weight='length')/3600) #myDistMatrix[myIDs.index(pair[0]),myIDs.index(pair[1])]=nx.shortest_path_length(G, pair[0], pair[1], weight='length')
Оптимизируем методом градиентного спуска матрицу координат станций.
Если мы будем использовать фреймворк keras для машинного обучения, то получим следующее:
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')
заметим, что в качестве начальных координат в слое layer1 мы используем реальные географические координаты -это необходимо для того, чтобы не попасть в локальный минимум функции СКО. Третью координату инициализируем ненулевой для получения ненулевого градиента (если в начале карта будет абсолютно плоской, смещение любой станции вверх или вниз будет равнозначно, следовательно градиент равен 0 и оптимизации z не произойдет). Последний элемент нашей модели (Dense(1)) влияет на масштабирование схемы для соответствия временной шкале.
Расстояние будем измерять в часах, а не секундах, так как порядки расстояний — около 1 часа, а для более эффективного обучении модели важно, чтобы все величины (входные данные, веса, targetы) были примерно одного порядка по величине. Если эти значения близки к 1, то можно использовать стандартные значения шага при оптимизации (0.001-0.01).
Строка model.layers[2].trainable=False замораживает координаты станций и на первом этапе варьируется один параметр — масштаб. После подбора масштаба нашей схемы размораживаем координаты и оптимизируем уже их:
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)
видим, что на вход подаем сразу все пары станций, на выходе — все расстояния и наша оптимизация- full batch gradient descent (один шаг на всех данных). Функция loss в данном случае — среднеквадратичное отклонение и можно видеть, что оно составило 0.015 в конце обучения, что значит среднеквадратичное отклонение менее чем в 1 минуты для любой пары станций. Иными словами, полученная схема позволяет точно узнать расстояние, которое требуется, чтобы добраться от одной станции к другой по расстоянию по прямой между станциями сточностью +-1 минута!
Но давайте посмотрим, как выглядит наша схема!
получим координаты станций, возьмем цветовую кодировку линий и построим 3d изображение с подписями (код для красивого отображения подписей взят отсюда):
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()
Так как возникли трудности с конвертацией в интерактивный 3d формат для браузера, выкладываю гифки:
более красиво и узнаваемо выглядит версия без текста:
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: Добавим линии метро нужного цвета и создадим гифку. Черные линии — переходы между станциями:
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))
Из данной схемы можно сделать некоторые интересные выводы, которые не столь очевидны из других схем. Для некоторых веток, например зеленой, синей или фиолетовой МЦК (розовое кольцо) практически бесполезно из-за неудобных пересадок, что видно в удалении кольца от этих веток. Самые длинные по времени маршруты — от коммунарки до щелкого или пятницкого шоссе (коней красной и розовая/синяя линии) длинные маршруты так же алмаатинская-рассказовка и бунинская аллея-некрасовка. На севере Москвы, судя по плану, происходит частичное дублирование серой и салатовой ветками — они находятся рядом на схеме. Было бы итересно посмотреть на то, как новые линии (МЦД, БКЛ) и кто чаще будет пользоваться ими. В любом случае, надеюсь, подобные схемы могут быть интересным инструментам анализа, вдохновения и планирования поездок.
P.S. 3D не обязательно, для 2D варианта достаточно чуть-чуть исправить код. Но в случае 2d схемы добиться подобной точности расстояний невозможно.
