Я составил персональную карту Лондона, на которой показано, как далеко я могу проехать на общественном транспорте за 10, 20, 30 (и т. Д.) Минут. Вот как это выглядит:

А еще лучше то, что код можно использовать в любой точке мира, а также можно ходить пешком. Вот персональные карты еще трех великих городов, в которых мне посчастливилось жить:

Процесс

Одним ленивым воскресным утром я наткнулся на серию красивых исторических карт. Эти карты назывались изохронными картами и представляли собой оценки картографа того, как далеко вы можете путешествовать в разные периоды времени. Мне больше всего нравится карта изохронных расстояний от Лондона по всему миру, составленная Варфоломеем.

Хотя это интересно, их следует принимать с большой долей скепсиса. Я сомневаюсь, что г-н Варфоломей хорошо изучил расписание поездов в Польше [2]. Но в наши дни у нас действительно есть очень точные прогнозы времени в пути. Итак, как бы выглядела настоящая изохронная карта моего любимого города в мире?

Что мне особенно интересно в Лондоне, так это то, что из того места, где я живу в Западном Лондоне, я могу быстро добраться до основных музеев и попасть в лондонский Сити (площадь в одну квадратную милю внутри Лондона). Но путешествие на юго-восток Лондона - это кошмар (~ 1,5 часа), дольше, чем путешествие из Эдинбурга в Глазго.

На код…

Код

Чтобы создать персонализированную карту, нам нужно было выбрать набор точек для анализа, получить время в пути для этих точек, сгруппировать эти точки в границы, нарисовав корпуса, и нанести их на карту.

При создании решетки точек я сосредоточился на использовании NumPy повсюду, чтобы использовать его векторизацию и гораздо более эффективные вычисления по сравнению со списками Python. Я создал два варианта:

  1. Локальная решетка с центром вокруг начала координат с определенным разделением точек и номером точки.
  2. Глобальная решетка, определяющая минимальную и максимальную широту и долготу для области поиска, а также количество раз для разделения решетки.

Затем мне нужно было рассчитать фактическое время, затраченное на поездку. Для этого есть много вариантов, но я остановился на использовании Google Distance Matrix API. Это возвращает расстояния и время от и до пунктов назначения. Другие варианты, которые я рассмотрел, включают Google Directions API (который также возвращает маршруты, которые не нужны для этого приложения) и MapQuest Direction API.

Вы можете получить доступ к набору из более чем двух десятков API Google через консоль разработчика Google. Я нашел настройку API действительно интуитивно понятной, и, хотя этот API является платным, вы получаете 300 долларов бесплатных кредитов в течение 12-месячного пробного периода, чего я нашел более чем достаточно для своего проекта. Убедитесь, что вы собрали результаты, чтобы вам не приходилось вызывать API для одной и той же области более одного раза!

# Storing my latitudes, longitudes, and travel times from the API
pickle.dump([lats, lngs, travel_times], open(pickle_path, 'wb'))

При использовании этого API я обнаружил следующие интересные особенности:

  1. Ваша строка запроса, которую вы отправляете в API, может быть слишком длинной, и в этом случае вам необходимо закодировать ее с помощью полилинейного кодирования.
  2. Вы можете отправлять только 100 элементов на запрос (1 источник, 100 пунктов назначения), поэтому я разбил свои массивы NumPy, используя chunked_latitudes = np.split(latitudes, len(latitudes)//chunk_size).
  3. Время ожидания неожиданно истекает, поэтому я приостанавливаю свой код каждые 5000 запросов.

Затем с набором точек данных мне пришлось выяснить, как объединить их в области в зависимости от времени в пути. Это менее тривиальная задача, чем кажется на первый взгляд. Моей первой мыслью было просто соединить внешние точки, это известно как выпуклая оболочка. Однако я не этого хотел. Я хочу влезть в укромные уголки и трещины, найти фьорды в данных. Эта реализация называется вогнутой оболочкой.

Вогнутая оболочка не уникальна, и вы решаете, сколько обтекания вы хотите, чтобы ваш вогнутый корпус имел вокруг точек, выбирая количество ближайших соседей. Я использовал отличную реализацию, написанную Дж. П. Фигейрой, найденную здесь.

Реализация вогнутого корпуса не справилась с островками точек. Это самые интересные части карты. В частности, доступны районы вокруг метро и автобуса, тогда как географически более близкие районы - нет. Вот что мне действительно любопытно: какие районы Лондона относительно близки мне, но спрятаны?

Меня интересует машинное обучение, поэтому я начал с попытки реализовать два метода машинного обучения без учителя: кластеризацию K-средних и методы смеси Гаусса (GMM). Однако у обоих были проблемы.

K-средство кластеризации рисует постоянный радиус вокруг центра кластера, который не учитывает то, как точки более распространены в продольном направлении.

GMM решает эту проблему, рисуя произвольно выровненный эллипс, чтобы сгруппировать остров кластера. Однако я обнаружил, что эти эллипсы все еще имеют неправильную форму. Это неудивительно, поскольку GMM - это, прежде всего, метод оценки плотности. Фактически, я искал метод кластеризации без центра кластеризации, который просто группировал точки на основе попарных расстояний.

После некоторых поисков (и попытки написать алгоритм сам) я понял, что мне нужен DBSCAN. Sci-kit learn имеет простую в использовании реализацию, однако есть дискуссии о том, является ли эта реализация эффективной.

Среди всего этого я нашла J. Книга Вандерпласа очень полезна для понимания этих методов и того, почему они не подходят для моей задачи. Это был хороший урок для поиска того, что есть на свете, прежде чем пытаться изобрести велосипед, а также для размышлений о простых, а не сложных методах.

Последним шагом к этой проблеме было нанесение данных на карту. Доступно довольно много библиотек карт, в том числе библиотеки, которые позволяют размещать данные непосредственно на карте Google. Однако то, что я искал, - это возможность рисовать многоугольники, и оказалось, что библиотека Folium может делать именно это для OpenStreetMap.

Folium - это интуитивно понятная библиотека, поскольку она следует стилю кодирования, аналогичному Matplotlib, в котором вы создаете объект карты и добавляете к нему дочерние элементы в виде слоев точек или многоугольников. Кроме того, они созданы в виде интерактивных HTML-страниц, которые можно увеличивать и уменьшать, а также выбирать и отменять выбор слоев.

Для каких еще интересных приложений мы могли бы использовать это?

В оживленных районах Лондона есть знаки, показывающие, куда можно добраться за 5 или 15 минут, но это довольно неточные круги. А как насчет точно точной версии?

Идеи, которые я не изучал:

  • Узнать, в каких районах Лондона хуже транспортное сообщение, особенно с «культурными центрами», и изучить корреляцию между индексами доступности и депривации.
  • Как такая персонализированная карта развивается за 24 часа, особенно с момента появления ночной трубки.

Вскоре после этого я обнаружил в сети две компании, которые сделали именно это. К сожалению, один позволяет выполнить только два поиска, прежде чем попросить вас заплатить [4], а другой имеет ограничения по странам [5]. Поскольку формы, которые они рисуют, и острова, которые они находят, разные, я обращусь к обоим, чтобы узнать, как их методы сравниваются.

Где еще вы могли бы использовать этот код? Вы можете использовать его, чтобы найти подходящее место для жизни недалеко от работы, спортзала или чего-то еще.

Не стесняйтесь использовать мой код GitHub (соответственно) или обращаться ко мне с любыми вопросами или идеями.

использованная литература

[1] Дж. Г. Бартоломью, I Sochronic Distance Chart (1904), доступ через Собрание карт Дэвида Рамси.

[2] С 1795 по 1918 год Польши даже не существовало.

[3] Э. Розен, Э. Янссон и М. Брундин, Реализация быстрого и эффективного алгоритма вогнутой оболочки (2014).

[4] Оалли, https://www.oalley.net/

[5] Карты времени в пути, https://app.traveltimeplatform.com/