Информация о пробках появилась на Яндексе в 2006 году. Начинали мы с необходимого — научились строить схему загруженности городских улиц и учитывать текущую ситуацию при прокладывании маршрутов. Автомобилисты, ориентируясь перед выездом на эту информацию, уже могли сэкономить время в пути:
Затем, чтобы помогать водителям непосредственно во время движения, мы добавили в мобильные Яндекс.Карты (и, как следствие, в Яндекс.Навигатор) автоматическое перестроение маршрута. Приложения научились адаптировать маршрут при каждом заметном изменении ситуации в городе.
Собрав на десктопе и в мобильном информацию про «сейчас», мы перешли к решению вопроса «а как будет потом?»:
Первым шагом стала статистическая карта пробок — на ней можно посмотреть, как в среднем стоит и едет город в конкретный час конкретного дня недели. Мы предполагали, что у карты «обычных» пробок может быть полезный побочный эффект — возможность по ним спрогнозировать заторы на ближайшее время. Но практика показала, что усреднённая картина помогает примерно спланировать только, например, завтрашнюю поездку в аэропорт — но не помогает выезжающим сейчас избежать новых пробок. По нашим измерениям, даже в конце часового маршрута картина пробок на момент выезда обычно ближе к фактической, чем усреднение:
Неделю назад на Яндекс.Картах появилась возможность посмотреть изменения пробок в ближайший час — следующий наш шаг в решении вопроса про будущее. Для тех, кто в этом году не смог приехать на Yet another Conference, мы сегодня расскажем, что у нашего прогноза внутри, и как оно там оказалось.
Собственно, задача
Мы прогнозируем изменения средней скорости движения на разных участках дорог. Технически карта дорог — это граф. Каждый перекрёсток — вершина этого графа, а участки дороги между двумя перекрёстками — рёбра. У последних есть атрибут «длина» и атрибут «скорость». Длина, понятно, известна заранее, а скорость рассчитывается в реальном времени — в зависимости от неё участок дороги и раскрашивается в зелёный, жёлтый и красный. Собственно, второй атрибут мы и взялись предсказывать.
Конечно, эту задачу придумали не мы, ею занимаются разные специалисты по всему миру. В России над моделированием и прогнозированием движения работают, например, авторы учебного пособия по одному из основных направлений в этой сфере — «Введение в математическое моделирование транспортных потоков». И хоть тема известна достаточно давно, российскому пользователю пока недоступна автомобильная навигация, в которой используются прогнозы по свежим данным. Лишь в редких случаях при построении маршрута учитывается усреднённая статистика пробок.
В мире прогнозы загруженности используются для автоматического управления дорожным движением в некоторых городах. Первые прототипы, в которых были применены прогнозы, появились появились в 1998 году в США. А первое пилотное использование системы, «заглядывающей в будущее», началось в 2006 году в Сингапуре.
Мы впервые затронули прогнозирование в конкурсе Интернет-математика в 2010 году. Тот опыт помог нам понять, как должна ставиться задача и какие данные нужны для достижения хорошего результата.
Источник данных
Во многих странах используются стационарные датчики потока, которые измеряют скорость и плотность движения на ключевых автомагистралях. Это хороший источник чистых данных о загруженности дорог, но покрытие ими даже одной Москвы потребовало бы гигантских вложений. Мы же вполне обошлись обезличенными GPS-треками, которые поступают от пользователей мобильных Карт и Навигатора. Каждый трек — это цепочка сигналов о местоположении (широта и долгота) автомобиля в конкретное время. Мы привязываем GPS-треки к дорожному графу, то есть определяем, по каким улицам они проходили. Затем усредняем скорость всех треков, проходящих по одним и тем же рёбрам.
У этих данных есть ряд особенностей, которые осложняют получение качественного прогноза. Потребительские GPS-устройства определяют координаты с погрешностью, поэтому треки очень «шумные». Это усложняет не только расчёт средних скоростей, но и привязку треков к графу, например когда дороги проходят близко друг к другу:
К тому же иногда на некоторых улицах мало автомобилей, передающих данные. Да и сама ситуация на дорогах не всегда устойчива. Например, полосы магистралей движутся с разными скоростями, поэтому на одном и том же участке треки могут одновременно показывать существенно разную скорость.
Выбор метода
В этой области используется большое разнообразие методов. Среди них:
Параметрическая регрессионная модель. В ней заранее предполагается конкретный вид функции в зависимости Vбудущая=F(Vпрошлая, Vтекущая), и подбираются параметры в F. Особенность модели в том, что выбор функции накладывает ограничения на результат. С одной стороны, это ограждает от серьёзных ошибок, которые неизбежны при использовании шумных данных, — параметрическая функция позволяет уменьшить разброс предсказываемых значений. С другой стороны, при неверном выборе функции модель может давать систематически неправильные ответы.
Непараметрическая модель («k ближайших соседей»). Она просто ищет в прошлом ситуацию, похожую на текущую, и в качестве прогноза выдаёт, как события развивались дальше. Такая модель гибче — используя её, можно сказать: «Если 10 раз после затишья возникала буря, то и после нового затишья тоже будет буря». Если же, например, взять линейную функцию в параметрической модели, мы не сможем предсказать такое, так как ограничены гипотезой, что будущее может быть только линейной комбинацией прошлого. Однако на «шумных» данных линейная модель обеспечивает большую точность, чем непараметрическая.
Другая классификация регрессионных методов — на скалярные и векторные. В первых предполагается, что ситуация на выбранном участке не зависит от происходящего на соседних, во вторых, наоборот, зависимости учитываются. Отсюда и разница в объёме вычислений. Если в городе 10 тысяч участков дорог, то для построения скалярной модели достаточно подобрать 10 тысяч параметров. А для векторной модели может понадобиться до 100 миллионов параметров. В нашем случае очевидно, что ситуации на разных участках влияют друг на друга. И ключевым становится вопрос, как ограничить круг соседей, чтобы расчёт уложился в разумное время.
Методы моделирования потоков учитывают природу процесса, а не просто оперируют абстрактными числами. Используется уравнение текущей жидкости с переменной вязкостью: больше плотность — меньше скорость. Методы широко применяются для планирования дорог и перспективны для прогнозов, но слишком требовательны к точности и полноте данных. Они дают хорошее качество на потоковых датчиках, но почти не работают на «шумных» GPS-треках.
Поэкспериментировав с разными методами и оценив их точность и вычислительную сложность, мы остановились на линейной векторной авторегрессии. Она предполагает, что будущая скорость — это линейная комбинация нынешней и нескольких прошлых скоростей на нескольких участках: непосредственно на рассматриваемом, а также соседних с ним.
Что и как рассчитывается
Раз в сутки наша модель обучается. На основе развития событий за какой-то временной промежуток в прошлом она строит прогноз. Этот прогноз сравнивается с последующим развитием событий. В модели подбираются коэффициенты, чтобы минимизировать расхождение между прогнозом и тем, как на самом деле всё оказывалось. Для каждого времени суток система рассчитывает свои коэффициенты, поскольку характер движения в течение дня немного меняется. Каждые несколько минут по готовой модели и свежим трекам расчитывается прогноз на ближайший час.
При обучении модели используется огромный объём данных. Граф дорог занимает около 100 гигабайт: это информация о топологии — какое ребро с каким связано, а также геометрии — GPS-координаты начала, конца и точек изгиба каждого сегмента дороги. История треков, которую мы храним, занимает десятки терабайт. На таких объёмах подбор коэффициентов на сутки растянулся бы на одном сервере на 2 недели. Чтобы уложиться в приемлемые несколько часов, мы используем кластер из 30 серверов. Но в нашей задаче нельзя просто разделить входные данные поровну между серверами, предоставить каждому серверу полный цикл расчёта по своей части, и собрать уже конечные результаты. Помогает наша платформа распределённых вычислений. Она берёт на себя сбор и перераспределение промежуточных результатов, она же автоматически передаёт задачи от вышедших из строя серверов работающим и сильно упрощает масштабирование при росте объёмов вычислений.
Но даже при распараллеливании такие объёмы, конечно, не поместятся в оперативную память. Поэтому мы используем собственную библиотеку Memory Mapped Storage, которая позволяет приложению работать с данными на диске, как если бы они хранились в оперативной памяти.
Обычно мы дублируем любую обработку данных между несколькими дата-центрами (ДЦ), чтобы сбой в любом из них не привёл к недоступности сервиса для пользователя. Но при подготовке модели мы сознательно не стали этого делать. Качество прогноза практически не пострадает, если несколько часов использовать вчерашнюю модель. А вот сам прогноз должен всегда быть свежим — ситуация на дороге постоянно меняется. Поэтому он готовится с тройным дублированием вычислений в разных ДЦ, полностью автономно друг от друга. Даже если произойдёт сбой одновременно в двух ДЦ, пользователь этого не заметит. Результаты расчёта разных реплик не синхронизируются между собой, на каждый запрос просто берётся самый свежий из трёх прогнозов.
Новый прогноз рассчитывается каждые 10 минут. Сначала обрабатываются свежие треки от пользователей: происходит их привязка к графу, усреднение скорости проехавших по одному сегменту автомобилей, вычисляется прогноз по построенной на текущие сутки модели. На это уходит 1–2 минуты. Затем эти данные подготавливаются к отрисовке на карте пробок. Сглаживаются резкие перепады скорости; выбирается цвет для каждой скорости с учётом категории дорог и масштаба просмотра карты. Это занимает ещё 2 минуты.
Оценка качества
Достоверное измерение качества прогноза — само по себе интересная задача. Изучив несколько методик, мы выбрали следующую.
Метрика качества должна отражать, насколько прогноз помогает людям. В отсутствие прогноза, пытаясь предугадать скорость движения по какой-то дороге через час, мы вынуждены пользоваться текущей информацией о пробках. Ясно, что за час пробки поменяются и наша оценка окажется неверной. Оценка, полученная с помощью прогноза тоже не идеальна, но она должна быть ближе к реальности. Насколько ближе — это мы и постараемся измерить.
Отметим, что можно брать разные приближения фактической ситуации. Самое простое — опираться на пользовательские треки. Так мы получили оценку 15%.
Однако у самих этих данных могут существовать систематические отклонения. Тогда наша метрика качества будет отдавать предпочтение прогнозу, прилежно воспроизводящему эти отклонения. Чтобы этого избежать, мы воспользовались замерами асессоров — специальных людей, помогающих измерять качество сервиса. Они выезжали на автомобилях с высокоточными GPS-устройствами на наиболее показательные магистрали, и привозили треки. Сопоставив прогноз с треками асессоров, мы получили другую оценку качества — 12%.
Рекомендуемая литература
Всем серьёзно интересующимся темой анализа данных можно порекомендовать классический учебник The Elements of Statistical Learning (Hastie, T., Tibshirani, R., Friedman, J. — Springer. В нем можно найти более подробную информацию о всех применявшихся в нашем исследовании методах машинного обучения.
Большое количество материалов на русском языке есть на сайте MachineLearning.ru.
Хорошим введением в проблематику транспортного моделирования будет учебное пособие под редакцией А.В. Гасникова «Введение в математическое моделирование транспортных потоков».
Специалистам будут интересны результаты зарубежных научных коллективов, занимающихся тематикой прогнозирования дорожной ситуации. Из множества доступных публикаций нам бы хотелось выделить несколько:
- Wanli Min, Laura Wynter, Yasuo Amemiya — Road Traffic Prediction with Spatio-Temporal Correlations. Эта статья исследовательского отдела IBM, описывающая успешный опыт применения авторегрессии, помогла нам поверить в решаемость задачи прогнозирования пробок.
- R.J. Gibbens, Y. Saacti — Road traffic analysis using MIDAS data: journey time prediction. Отчёт исследовательского коллектива Кембриджского университета содержит экспериментальное сравнение линейно-регрессионного метода и метода k ближайших соседей.
- Weizhong Zheng, Der-Horng Lee and Qixin Shi — Short-Term Freeway Traffic Flow Prediction: Bayesian Combined Neural Network Approach. Помимо методов, описанных нами, существует множество других подходов к задаче прогнозирования дорожной ситуации. К примеру, эта статья описывает успешный опыт применения нейросетей.
- Yang Zhang, Yuncai Liu — Comparison of Parametric and Nonparametric Techniques for Non-peak Traffic Forecasting. Здесь сравниваются ещё несколько параметрических и непараметрических методов прогнозирования.
Автор: yurkennis
