company_banner

Как статистика помогает делать Яндекс.Пробки лучше

    Как устроены Яндекс.Пробки? Откуда берутся исходные данные о дорожном движении? Как они превращаются в карту пробок? Всегда ли информация о пробках достоверна? Как это проверить? А главное, как сделать данные о пробках более точными? Для всего этого в Пробках используется статистика: наука одновременно сильная и коварная. В этой лекции аналитик Яндекс.Пробок Леонид Медников рассказывает студентам, как отличать достоверные результаты от случайных, и как статистика применяется в разных практических задачах.





    Принцип работы Яндекс.Пробок достаточно прост. Чтобы описать его не требуется отдельная лекция. Приложения Яндекс.Карты и Яндекс.Навигатор при помощи GPS определяют местоположение устройства, на котором они запущены, и передают эти сведения на сервер. А он в свою очередь на основе этих данных создает картину пробок.

    image

    Но как именно это происходит? Вот это уже совсем нетривиальный процесс, требующий применения специальных алгоритмов и учета статистики. Как отличить медленно продвигающегося автомобилиста от пешехода или велосипедиста? Как убедиться в достоверности передаваемой информации? А главное, как сделать данные о пробках наиболее точными?

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

    image

    Алгоритму нужно принять решение, что это же это было. Для уточнения данных алгоритм попытается найти наиболее вероятный и разрешенный правилами маршрут. Далее нужно определить, какой перед нами объект? Ведь в пробке машины могут ехать со скоростью пешехода, а точность GPS не позволяет с уверенностью сказать, движется объект по проезжей части или по обочине. Тут можно учитывать несколько факторов: во-первых если количество объектов движущихся с небольшой скоростью достаточно велико, то мы можем предположить, что на этой дороге действительно есть пробка и автомобили едут медленно. Также мы можем учитывать историю скорости передвижения объекта за последние несколько часов. Допустим, если объект за последние четыре часа не развивал скорость больше 10-15 километров в час, то это, скорее всего, пешеход.

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

    Алгоритмы


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

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

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

    image

    В 54 случаях новый алгоритм сработал лучше старого, а в 13 – хуже. По процентному соотношению верных ответов и ошибок новый алгоритм явно лучше. А теперь представим, что к сравнению мы добавляем еще один алгоритм. Но прогонялся он на меньшем количестве отрезков – на шести.

    image

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

    Статистика


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

    image

    Теперь рассмотрим пример, в котором мы бросаем монетку N раз. Количество объектов мы примем за k, а количество комбинаций – за С.

    image

    Среднее и наблюдаемое среднее


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

    Почему мы вообще говорим о случайностях? Ведь ошибки в алгоритмах построения карты пробок чаще всего возникают по неким объективным причинам. Но не все эти причины нам известны. Если бы мы знали все причины, можно было бы составить идеальный алгоритм, и больше никогда его не улучшать. Но пока этого не произошло, мы вынуждены принимать некоторые ошибки алгоритмов за случайные величины. Поэтому мы проверяем, насколько лучше стал работать алгоритм при помощи примерно того же аппарата, что и гипотезу с ровной монетой. Только в данном случае в качестве базовой гипотезы мы принимаем то, что алгоритм вообще не изменился. А затем при помощи прогона данных через алгоритм определяем, есть ли перекосы в ту или иную сторону. И так же, как и в случае с монетой важно, чтобы таких прогонов было как можно больше, иначе у вероятность ошибиться будет слишком высока.

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

    image
    Яндекс
    472.36
    Как мы делаем Яндекс
    Share post

    Comments 31

      +4
      Пешеход с 15 кмч это конечно круто :-)
        +1
        Пешебег
          0
          Просто общественный транспорт редко быстрее едет. Кроме метро, но там нет GPS.
          +1
          Помню, как года два назад ехал на велосипеде с включенными яндекс-картами, так они в 2 часа ночи на абсолютно пустой улице нарисовали пробку. Но, видимо, с тех пор много поменялось.
            0
            Ничего не изменилось на примере Самары. Пробки ночью, когда дороги пустые. Это то же часть алгоритма, что нафига что-то «считать», если «там» всегда пробка или затруднения, значит надо всегда это и показывать.

            В Самаре качество Я.пробок плохое. Пользуюсь только глядя на то, есть ли ДТП впереди, значит пробка действительно есть, значит объехать, либо, если нельзя объехать смотрю в каком ряду, чтобы держаться нужного.
            +2
            И ни слова про фильтр Калмана (или его у вас там нет О_о) !;)
            Что-то у меня видео в HQ глючить начинает, если его перематывать начать.

            Скажите, а насколько адекватно сейчас считается время которое сервис говорит будет затрачено на добирательство из пункта A в B? Просто у меня складывается ощущение, что там разброс реальности от прогноза чудовищный, если пробок много.
              0
              Аналогичная ситуация с HD.
                0
                И ни слова про фильтр Калмана (или его у вас там нет О_о) !;)

                Фильтр Калмана встроен во все gps'ки. Они выдают уже сглаженный результат. Если вы посмотрите на GPS треки, то точки в них не будут хаотично прыгать. Кроме того, сами погрешности GPS носят не совсем случайный характер: они зависят от того, какие спутники принимает устройство и от состояния ионосферы на пути сигнала. Эти параметры не меняются мгновенно.

                Так что нет, фильтр Калмана не используется. Его пробовали добавлять, но качество результата не возрасло.
                  +2
                  В GPS при прогнозе используется линейная модель движения. Вы же можете использовать реальную модель дороги, что значительно поднимет точность использования Калмана. Приведу пример: однажды я делал систему, которая должна была кушать GPS-датчик низкоорбитального спутника и выдавать отфильтрованное положение. Судя по оценке сигма, которую давал GPS равнялась где-то 20 метрам. Если в таком алгоритме использовать линейную модель движения, то меньше пол метра-метр сигма не схлопывалась. Но если использовать априорную информацию по траектории и прогнозировать её даже неточным алгоритмом (который даёт ошибки в 500 метров за виток), то достаточно быстро ошибка уходила на уровень 1-2 сантиметров.
                  Может есть какая-то более глубокая специфика, почему он не работает. Но «Фильтр Калмана встроен во все gps'ки. Они выдают уже сглаженный результат.» не должно влиять на результат, если вы используете более точный прогноз движения.

                  «Эти параметры не меняются мгновенно.» — если параметры не меняются мгновенно, то по моему опыту фильтр Калмана должен работать. Вот если они быстро меняются — это хуже.
                    +1
                    Спасибо за замечание, оно очень интересное. Пробовали и линейный фильтр Калмана и с моделью дороги: скармливали в фильтр вектор ошибки привязки на очередном шаге.
                    Я думаю, что качество не увеличилось потому, что используемый алгоритм привязки точек к дорожному графу и так справлялся с ошибками, которые мог скорректировать фильтр. Этот алгоритм значительно более изощренный, чем привязка к ближайшему ребру с нужным направлением.
                +2
                У Хокинга в книге по физике одна формула, у вас пост о статистике и ни одной. Соревнуетесь с мэтром? Намеренно упрощаете?
                Малый шад, 9-11 класс, уже должны осилить и формулы, и алгоритмы.
                  0
                  Последнее время навигатор при наличии двух маршрутов предлагает ехать по более длительному и более длинному, к тому же это платная дорога, начинаю подозревать в аффилированности кое кого. Причем при выборе короткого маршрута, навигатор норовит его перестроить обратно на платку. К сожалению уже потер скриншот, но можно и снова снять в ближайшее время.
                    0
                    А стоит ждать когда-нибудь разделения пробок по полосам? Точнее, по направлениям — например, те, кому сворачивать — стоят в пробке длиной квартала в три, а те, кому прямо — пролетают мимо «со свистом». При этом Я.Пробки считают, похоже, просто среднюю скорость, и навигатор строит маршрут с поворотом ровно по этому месту.
                    Пример: СПб, Синопская набережная в направлении к Смольной — регулярно полоса-две стоят на поворот на Большеохтинский мост.
                    Раз уж вы всё равно анализируете точки ДО и ПОСЛЕ и строите варианты маршрута — можно было бы и разделять проезжающих в разных направлениях.

                    Ещё вопрос: у меня подозрение, что при построении маршрутов есть некая прибавка «на светофоры», и если ехать по маршруту со светофорами, то время проезда примерно верное, а если ехать по главной дороге без светофоров, то приезжаешь стабильно раньше прогноза. Я прав, есть такая поправка?
                      –1
                      Пользуйтесь Ситигайдом. Там пробки по полосам уже несколько лет как реализовано. Называется эта технология «векторные пробки». Можно пройтись поиском по их форуму probki.net
                        0
                        Действительно, Яндекс.Пробки и маршрутизатор используют среднюю скорость для всех полос.

                        С поворачивающими есть ряд проблем:
                        1) Время на съезде может быть очень нестабильным из-за «хитрых» водителей, поворачивающих не с той полосы. В итоге входные данные очень шумные.
                        2) В общем случае не очевидно, в каком месте начинается разделение потоков. Если на съезде действительно собралась длинная очередь, то может начаться за сотни метров до поворота.
                        3) Считая отдельно поворачивающих и едущих прямо мы уменьшаем себе объём данных по каждому направлению, как итог получаем более шумное значение скорости и медленную реакцию на изменение дорожной ситуации.

                        Таким образом видно, что в лоб, просто расчётом разных скоростей по разным направлениям съезда, задача качественно не решается: более того при таком подходе качество может даже ухудшится (см. пункт 3). В общем, совсем непростая эта задача, но может когда-нибудь и она будет решена Яндексом.
                          0
                          Есть еще один момент. Мы не просто анализируем точки ДО и ПОСЛЕ, но еще и делаем это в мягком реальном времени. Ждать несколько минут, пока машина проедет поворот, чтобы определить, свернула ли она, нельзя. Теоретически задача решаема: заметив два кластера скоростей на одном ребре графа можно поискать приоритетные направления, куда поворачивают машины с такой скоростью, после чего соотносить новые сигналы с тем или иным маршрутом в зависимости от их скорости. А практически, это сложный алгоритм, да еще и с положительной обратной связью. Он будет давать нестабильные результаты.
                            0
                            1) А на скорость «на прямой» эти хитрые водители, шпарящие по автобусным полосам, конечно, не влияют?
                            2) Ну в навигаторе же есть текущий маршрут. Можно же пользоваться этой инфой? Мне кажется, чаще всего водитель поворачивает именно по маршруту…
                            3) Ну да, это понятно, но неужели поделить на 2-3 так уж фатально? И потом, можно же не разделять потоки полностью, а просто дополнить граф информацией о времени проезда не только ребер, но и вершин между ними?

                            А вообще, конечно, все это (и коммент kibergus тоже) сильно смахивает на отговорки.
                            Да, понятно, что задача трудная, тяжело вписывающаяся в существующую концепцию, но от того не менее важная.
                            Я тоже надеюсь, что Яндекс сделает в этом направлении хоть что-то. Это будет точно лучше, чем просто оставить все как есть под благовидным предлогом.
                          +1
                          А когда вы начнёте пользоваться акселерометром и гироскопом в смартфонах? Сможете повысить точность определения координат.
                            0
                            Сами по себе акселерометр и гироскоп не позволяют повысить точность позиционирования, скорее отсечь выбросы. Так или иначе текущий алгоритм уже достаточно качественно справляется с привязкой.
                              0
                              Как раз позволяют. Данные с гпс и с инерциалки загоняются в фильтр Калмана и ещё можно написать мат.модель движения авто.
                            0
                            Яндекс, дорогой, ну как тебе не стыдно писать статьи на Хабре про учет статистики в пробках, если ты банально не можешь просчитать маршрут и пункта А в пункт Б на определенный день в определенное время. Я вот прямо сейчас не могу просчитать маршрут в Шереметьево на завтра в 7 утра — брать мне Аэроэкспресс или такси, панимаишь?
                              0
                              А что вам мешает просчитать маршрут на завтра в 7 утра? В пробках есть режим статистики — выбираете там «понедельник, 7 утра», и считаете.
                                0
                                Вообще-то статья немного про другое ;-)
                                Но маршрут с учётом пробок на определённый действительно построить нельзя. Но посмотреть типичную ситуацию и её развитие вполне можно: maps.yandex.ru/-/CVfiYSLz (Пробки — Прогноз — Выбираете день недели и время).
                                В Шереметьево в 7 утра по Москве проедите отлично, а до поворота на Международное шоссе чуть-чуть постоите, а если будете проезжать МКАД уже после 7:30, то постоите побольше.
                                0
                                Вот на чего, а на статистику эта чтука не смотрит.
                                Не считает среднее время работы светофора, не считает нормальное время совершения поворота(или другого маневра), не смотрит на данные других машин, что ехали этим маршрутом ранее…
                                  0
                                  Если едет выделенная полоса, то это не значит, что остальные полосы едут. Когда уже это простое правило будет выполняться в вашем приложении?

                                  Если куча придурков прется по тратуару\выделенной полосе на проспекте Андропова, то не нужно остальных направлять в тоже русло.

                                  Давно уже себе взял за правило, что если Яндекс направляет на Андропова, то нужно срочно разворачиваться и ехать оттуда подальше.
                                    0
                                    Выделенные полосы невозможно определить по GPS. Получается под них нужно писать отдельный алгоритм, который бы пробовал понять, что здесь данные нетипично оптимистичные. При этом данные вида «кто-то едет быстро, кто-то медленно», очевидно, будут похожи на много других ситуаций, например, просто хвост пробки или светофор.
                                    Итого, да, проблеме ставим +1, но быстрого решения обещать не можем.
                                    0
                                    Почему пешеходов нельзя отличать через акселерометр? По тому же методу как работает куча приложений шагомеров и беговых трекеров.
                                      0
                                      Можно. Но исторически применяемый нами алгоритм появился раньше массового внедрения акселерометров в смартфоны. И в целом он довольно удачно справляется с задачей. Впрочем, возможно мы добавим и ещё одну степень фильтрации пешеходов, уже на основе акселерометра.
                                        0
                                        А все проблемы от того, что у Яндекса нет пешеходной навигации — иначе бы автомобилисты от пешеходов отличались просто по типа запущенного интерфейса.
                                        0
                                        В 5s так вообще motion сопроцессор как раз для этих целей: сам подскажет, идет человек или едет.
                                        0
                                        Жаль не увидел раньше, но надеюсь прочтете) Товарищи яндексоиды, сделайте пожалуйста «пробки в интернете» — насколько я понимаю, по вечерам 3g интернет плохо ловит из-за скоплений людей читающих фейсбуки в пробках, а не лажовости приема отдельных моделей телефонов. а эти скопления можно отследить и тогда можно будет заранее знать, смогу ли я зачекиниться\уточнить маршрут там где хочется или надо это заранее сделать)

                                        Only users with full accounts can post comments. Log in, please.