Что дальше с картографическими приложениями? Планирование путешествия по маршруту.

Что дальше с картографическими приложениями? Планирование путешествия по маршруту.

Представьте себе это; вы в пути - вы получили сообщение, что место встречи изменилось. Но вы уже в поезде - вам нужно найти маршрут к новому месту. Но тут возникает проблема: приложение не понимает, что вы уже в поезде! Предлагаемый шаг 1 - вернитесь на станцию, с которой вы только что пришли…

Несколько заметок об этом блоге

Цель этого блога - дать обзор проблемы и рассмотреть подход к ее решению с позиций науки о данных.

Для улучшения доступности большая часть этого блога будет написана для случайного читателя; в разделах, обозначенных «Повышение уровня» и выделенных курсивом, будут описаны более технические детали - так что, если это не для вас, пожалуйста, пропустите остальные, что все равно будет иметь смысл! Нет никаких предпосылок для понимания остальной части блога!

Давайте начнем!

Краткое описание проблемы; если вы измените пункт назначения сейчас, начальное местоположение будет принято в качестве вашего текущего местоположения, которое, поскольку вы находитесь в поезде, должно быть на железнодорожной линии (надеюсь), что является довольно странным местом для начала путешествия, если вы еще не на поезд. Ваше полезное картографическое приложение предоставит вам маршрут от ближайшей пешеходной точки, но не принимает во внимание то, что вы можете ехать на поезде, и первым шагом, скорее всего, будет прогулка / сесть на транспорт до ближайшей станции - несмотря на то, что вы в настоящее время находитесь в поезде на линии, которую он предлагает.

В качестве примера мы будем использовать маршрут от Актон-Тауна до обновленного пункта назначения Кингс-Кросс.

Теперь ваше картографическое приложение сообщает вам, что вам нужно пройти 11 минут назад до Актон-Таун, чтобы сесть на поезд, идущий именно по той линии, на которой вы сейчас находитесь! (не то чтобы вы все равно могли сойти с поезда, чтобы сделать это).

Так вы думаете; ах, я установлю свое местоположение до моей следующей станции (Хаммерсмит) и буду следовать инструкциям оттуда - главное предложение: сверните по круговой линии до Кингс-Кросс. Идеально… или не совсем.

Приложение абсолютно правильное, если оно стояло в Хаммерсмите, а не в поезде, а следующий поезд отправляется по Кольцевой линии, тогда, возможно, самый быстрый способ - это. Однако это не относится к вам.

Есть два прямых пути от Хаммерсмит до Кингс-Кросс, линии Пикадилли и кольцевой линии - оба занимают 26 минут.

Здесь важен контекст; Если указать ваше местоположение на Хаммерсмит, приложение не знает, что вы на самом деле уже находитесь на поезде линии Пикадилли, направляющемся на Кингс-Кросс. Поскольку станция Хаммерсмит состоит из двух частей, 4–5 минут ходьбы между двумя платформами, и вам, возможно, придется подождать до 5 минут, чтобы поезд кольцевой линии был, по крайней мере, на 5 минут дольше и, возможно, до 10 минут дольше, чтобы сесть на кольцевую линию, чем оставаться в поезде линии Пикадилли - что примерно на 40% дольше!

Что можно сделать?

Похоже, это отличный вопрос для науки о данных; нам нужно использовать доступные данные, чтобы дать понимание конечному пользователю!

Здесь представлено возможное объяснение того, как можно было бы решить проблему; Есть много проблем - этот блог ни в коем случае не говорит о том, что решение проблемы является легким!

Чтобы структурировать мыслительный процесс, мы будем следовать структуре науки о данных OSEMN (Obtain, Scrub, Explore, Model, iNterpret).

Получать

Здесь требуются два основных потока информации:

1. Расположение пользователей
2. Возможный вид транспорта (железнодорожная линия, автобусный маршрут, трамвайная линия и т. Д.), По которому пользователь может в настоящее время ездить

Ключ к проблеме - возможность сопоставить пользователя с конкретным экземпляром (поезд, автобус или трамвай) этого вида транспорта.

Начнем с того, какая информация доступна по каждому из них:

Пользователи:

• Информация GPS (которая даст местоположение и время)

Транспортный экземпляр:

• Маршрут
• Расписание / расписание
• Фактическое время прибытия / отправления - станции / остановки

Что мы пытаемся сопоставить:

• Место расположения
• Направление
• Время

Для этого обсуждения мы возьмем простой (для сравнения) пример: мы будем использовать участок наземной линии Richmond / Stratford Overground от Южного Эктона до Эктон-Сентрал.

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

Для пользователя основной информацией будет GPS-канал; ниже представлен типичный набор данных для пользователя, включая время, широту и долготу.

Для надземных поездов основным потоком данных будет API TfL, предоставляющий оперативную информацию о поездах. Как минимум, на линии, вероятно, будет следующее: поезда будут ходить в обоих направлениях. Для повышения осведомленности необходимо рассмотреть большую часть строки:

В режиме реального времени не вся «актуальная» информация будет доступна, независимо от того, заполняется ли информация слева направо или справа налево, указывает направление поезда.

Скраб

Ошибки могут возникать в обоих наборах данных, мы кратко рассмотрим, как их можно идентифицировать.

Пользователь

Для данных, предоставленных пользователем, ошибки, скорее всего, связаны с местоположением GPS (а не временем), с использованием стандартных методов анализа выбросов, например, анализа распределения точек.

Уровень повышен

Можно с уверенностью предположить, что ошибки в определении местоположения GPS будут иметь нормальное распределение. Важно отметить, что поскольку эти два компонента генерируются с помощью одного и того же механизма (чип GPS в телефоне), существует высокая вероятность корреляции ошибок; то есть ошибка в долготе с большей вероятностью приведет к ошибке и в широте. В результате это следует рассматривать как многомерное обнаружение выбросов, Z-Score будет подходящим выбором для этой проблемы.

TfL - API

Для пользователя информация, получаемая приложением, поступает с телефона, на котором оно установлено (т. Е. Непосредственно с GPS-чипа), поэтому источник информации, вероятно, будет очень стабильным (если не переменным). Одной из ключевых проблем с данными TfL является получение данных и обеспечение того, чтобы полученные данные были именно такими, какими должны были быть.

Вот простые методы для этого примера:

• Проверить тип данных; это строка или целое число, где оно должно быть
• Проверить хронологию; следуют ли все точки данных в соответствующем порядке
• Проверить регулярность; время между станциями в одной поездке значительно меньше, чем во всех остальных

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

Картографические данные

Помимо того, что мы знаем, когда поезд будет в определенных точках, нам нужно знать, где эти точки, то же самое для пользователя; это момент, когда нам, возможно, потребуется сопоставить разные источники данных, что может быть проблемой. Мы рассмотрим это более подробно на этапе изучения. XX - возможно обновить

Проводить исследования

На этом этапе важно помнить, что мы следим за этим процессом, чтобы позволить нам построить модель; это не обязательно тот процесс, которому фактически следовали бы в процессе моделирования. В результате мы можем собирать дополнительные данные, которые могут помочь нам понять, что происходит, - которые обычно были бы слишком сложными / трудоемкими или просто недоступными при реализации модели.

Итак, во-первых, чтобы лучше понять, мы нанесем пользовательские данные GPS на карту.

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

Во-первых, краткое изложение того, что мы пытаемся идентифицировать:

• Место расположения
• Направление
• Время

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

В этом разделе мы рассмотрим, как мы можем добраться до обоих из них для пользователя и поезда.

Пользователь

Местоположение - нам повезло, что большая часть предварительной обработки происходит внутри чипа / телефона, чтобы обеспечить уже относительно точное измерение точки (мы вряд ли сможем улучшить точность определения местоположения).

Уровень повышен

Почему мы используем местоположение, а не маршрут, ведь это было бы более точным? Просто да - позже мы рассмотрим преимущества аппроксимации маршрута.

Направление - это посложнее; однако, к счастью, для этого примера нам не нужен высокий уровень точности определения направления, проще говоря, нам нужно знать, движется ли пользователь на север или на юг. Скользящее среднее, вероятно, будет иметь дело с любыми естественными вариациями в наборе данных и предоставит достаточно точное изменение значения долготы / широты, которое может быть взято из результирующего вектора (выделено красным ниже), являющегося направлением.

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

Время - просто это предоставляется телефоном.

Тренироваться

Местоположение - у поезда очень точный маршрут, но его местоположение по временным данным мало (то есть местоположение по времени известно только на станциях).

В определенных точках маршрута (например, на станциях) местонахождение поездов известно с высокой степенью достоверности. Простой способ приблизительно определить местоположение поезда по времени - это предположить линейную зависимость между временем и расстоянием.

Уровень повышен

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

Модель

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

Давайте быстро рассмотрим два набора данных и их атрибуты:

Поезд

• Высокоточные данные о маршруте и местоположении станции
• Редкие, но относительно точные данные о времени

Пользователь

• Частые данные о местоположении с переменной точностью и данные о времени с высокой точностью

Цель модели - определить, к какому классу принадлежит точка данных, это можно увидеть на рисунке ниже. Также включен еще один возможный вид транспорта, который модель должна будет определить между собой.

В этом простом примере легко увидеть, как простое сравнение пользовательских серий точек данных с видами транспорта в аналогичном месте позволяет легко идентифицировать различные режимы / маршруты. Точки данных в синем поле можно легко пометить, однако точки в красном поле сложнее - здесь настройка модели становится действительно важной, особенно при использовании небольших наборов данных.

Повышение уровня - выбор модели

Простая, но эффективная модель, которую можно использовать в этом простом случае, - это модель классификации k-ближайших соседей, в которой точка данных сравнивается с ближайшими к ней точками данных и помечается как класс, у которого имеется большее число (дополнительная информация Здесь)

Повышение уровня - более высокое измерение

Это чрезмерное упрощение, потому что для получения возможности получить экземпляр (т.е. конкретный поезд), а не только режим (маршрут), двухмерный график, показанный над реальной моделью, будет иметь как минимум 5 измерений (долгота, широта, Change Long, Change Lat, Time), которые позволяют модели учитывать три прогнозные характеристики, которые мы используем в настоящее время; место, направление и время.

Модель может быть настроена либо в классификаторе пользователя - ›экземпляр транспорта, либо в экземпляре транспорта -› пользователь; в этом случае транспортный экземпляр - это помеченный набор данных, поэтому пользователи должны быть сопоставлены с транспортным экземпляром.

Ниже приведен пример набора данных, который, вероятно, будет входить в эту простую модель.

Повышение уровня - проверка модели

Одной из проблем при улучшении модели является отсутствие помеченных пользовательских данных - приложение не обязательно получает какое-либо подтверждение того, что предсказание, в каком поезде находился пользователь, на самом деле было поездом, в котором находился пользователь; другими словами, набор данных не «маркируется». Чем дольше модель работает для отдельного пользователя, тем выше уровень вероятности, что модель может определить, был ли ее прогноз точным - например, если пользователь проехал 10 остановок, а трек пользователя совпадает с поездом для каждой, гораздо более вероятно, что пользователь находится в этом поезде. Эту повышенную вероятность можно использовать для присвоения предполагаемого ярлыка.

Интерпретировать

Итак, мы успешно определили, в каком транспортном режиме находится пользователь (в данном случае просто, в каком поезде находится пользователь) - как это использовать?

Пользователь, скорее всего, не будет заинтересован в том, что он находится в поезде, а не в автобусе (надеюсь, они уже знают об этом), но что мы можем сделать, так это начать решать выделенную проблему; создание плана маршрута для пользователя, который уже находится в движении. Используя данные, которые мы собрали, исследовали и смоделировали, мы можем указать, что пользователь уже находится на линии Пикадилли, и вместо «Сесть на следующий поезд Кольцевой линии в Хаммерсмите» гораздо более полезной строчкой «Остаться на борту» линия Пикадилли в Хаммерсмите »; предотвращение рекомендации, которая занимает на 40% больше времени, чем оптимальная!

Ключевые возможности для улучшения

Возможность 1

Чрезмерно простая модель для прогнозирования местоположения поезда между станциями по времени. В действительности вряд ли будет линейной, поскольку скорость поезда, вероятно, будет варьироваться между станциями.

Одним из механизмов преодоления этого является улучшение модели местоположения по времени между станциями; это может быть выполнено с помощью пользовательских данных (конечно, с разрешения) для предоставления дополнительных данных. Также существует возможность получить дополнительные данные от TfL, то есть по участкам линий, а не только по станциям.

Повышение уровня - возможность 2

Улучшенная модель; в то время как k-Nearest Neighbours является хорошей моделью для простых случаев с низкой размерностью, подобных этому, для более продвинутых моделей с высокой размерностью (и для повышения точности, вероятно, потребуется, по крайней мере, сначала увеличить объем информации и, следовательно, размерность). Логистическая регрессия - хороший ход, однако полагается на возможность линейного разделения классов меток - что не невозможно, но, поскольку размеры увеличиваются, вероятно, означает использование анализа главных компонентов (PCA) или другого метода уменьшения размерности для уменьшения количества измерений без потери информации содержится внутри - мы все-таки увеличили количество измерений по уважительным причинам.

Использование дерева решений (либо как метод ансамбля, либо как метод повышения градиента) имеет явные преимущества в том, что оно может справиться с нелинейно разделяемыми классами, а также с категориальными переменными-предикторами; подходит для работы с большими наборами входных данных и высокой размерностью. Однако реализация может оказаться гораздо более сложной, если потребуется оптимизировать ряд гиперпараметров.