Как работает Яндекс.
Трафик? Откуда берутся необработанные данные о трафике? Как они превращаются в карту дорожного движения? Всегда ли достоверна информация о дорожном движении? Как я могу это проверить? И самое главное: как мы можем сделать данные о трафике более точными? При всем этом «Пробки» использует статистику: науку одновременно мощную и коварную.
В эта лекция Аналитик Яндекс.
Трафика Леонид Медников рассказывает студентам, как отличить достоверные результаты от случайных и как статистика используется в различных практических задачах.
Принцип работы Яндекс.
Трафика довольно прост. Для его описания не требуется отдельная лекция.
Приложения Яндекс.
Карты и Яндекс.
Навигатор используют GPS для определения местоположения устройства, на котором они работают, и передают эту информацию на сервер.
А он, в свою очередь, на основе этих данных создает картину пробок.
Но как именно это происходит? Это совершенно нетривиальный процесс, требующий использования специальных алгоритмов и статистики.
Как отличить медленно движущегося автомобилиста от пешехода или велосипедиста? Как обеспечить точность передаваемой информации? И самое главное, как сделать данные о трафике более точными? Самая первая проблема, с которой вы сталкиваетесь при картировании трафика, заключается в том, что технология GPS далека от идеала и не всегда точно определяет местоположение.
Отслеживая перемещения одного объекта, можно получить довольно странные данные: мгновенные перемещения на довольно большие расстояния, смещение на обочину и т. д. В результате мы можем получить следующую картину: 
Алгоритму необходимо решить, что это оно.
Для уточнения данных алгоритм попытается найти наиболее вероятный маршрут, разрешенный правилами.
Далее нам нужно определить, что за предмет находится перед нами? Ведь в пробке автомобили могут двигаться со скоростью пешехода, а точность GPS не позволяет с уверенностью сказать, движется ли объект по проезжей части или по обочине.
Здесь можно учесть несколько факторов: во-первых, если количество объектов, движущихся с небольшой скоростью, достаточно велико, то можно предположить, что на этой дороге действительно пробка и машины движутся медленно.
Также мы можем учесть историю скорости движения объекта за последние несколько часов.
Допустим, если объект за последние четыре часа не развил скорость более 10-15 километров в час, то, скорее всего, это пешеход. Итак, мы определили скорость движения автомобилей в определенном направлении за определенный период, обработали ее специальными алгоритмами, усреднили и в итоге получили примерную суммарную скорость потока.
Все это происходит в реальном времени и в потоке, состоящем из сотен тысяч машин.
Алгоритмы
Как мы говорили выше, алгоритмы занимаются определением типа объекта, скорости его движения и усреднением скорости потока.Но как оценить качество их работы и понять, в каком направлении нам нужно двигаться, чтобы их улучшить? Первая проблема решается запуском тестовых автомобилей в город. Как и обычные пользователи, они присылают данные о своих перемещениях, но при этом мы точно знаем, каковы были реальные условия.
После этого на основе метрики можно сравнить реальную карту пробок в определенном районе с рассчитанной алгоритмами и определить, насколько хорошо система справляется со своей задачей.
Сравнивая реальную ситуацию с результатами сразу нескольких алгоритмов, мы можем оценить, какой из них лучше.
Допустим, мы тестируем новый алгоритм и сравниваем его со старым.
Мы запускаем его на 67 сегментах и получаем следующие результаты: 
В 54 случаях новый алгоритм работал лучше старого, а в 13 — хуже.
По проценту правильных ответов и ошибок новый алгоритм явно лучше.
Теперь представьте, что мы добавляем к сравнению еще один алгоритм.
Но его прогоняли на меньшем количестве сегментов – шесть.
Его процент попаданий и ошибок даже выше, чем у первого.
Но стоит ли доверять тесту на таком небольшом количестве сегментов? Чтобы четко ответить на этот вопрос, обратимся к статистике.
Статистика
Во-первых, давайте посмотрим на случайные значения.Допустим, мы подбрасываем монетку три раза.
Орел принимаем за ноль, а решку за единицу.
Всего мы можем получить восемь комбинаций.
Если подсчитать суммы выпавших значений для каждой из комбинаций, то мы увидим, что крайние значения выпадают реже всего, а по мере приближения к центру вероятность возрастает. 
Теперь рассмотрим пример, в котором мы подбрасываем монету N раз.
Примем количество предметов за k, а количество комбинаций за C. 
Среднее и наблюдаемое среднее
Теперь поставим другую задачу.Представим, что у нас есть монета, и мы хотим понять, четная ли она, т. е.
выпадает ли она с одинаковой вероятностью на каждую сторону.
Мы проверим эту гипотезу, бросив монетку.
Если монета четная, то чем больше раз мы ее подбросим, тем ближе к среднему должно быть наибольшее количество результатов.
В то же время при малом количестве бросков вероятность сделать неправильный вывод значительно выше.
Почему мы вообще говорим о случайности? Ведь ошибки в алгоритмах построения карты пробок чаще всего возникают по каким-то объективным причинам.
Но не все эти причины нам известны.
Если бы мы знали все причины, мы могли бы создать идеальный алгоритм и никогда больше его не улучшать.
Но пока этого не произошло, мы вынуждены принимать некоторые ошибки алгоритма как случайные величины.
Поэтому мы проверяем, насколько лучше стал алгоритм, используя примерно тот же аппарат, что и гипотеза четной монеты.
Только в этом случае в качестве базовой гипотезы принимаем, что алгоритм вообще не изменился.
А затем, пропуская данные через алгоритм, мы определяем, есть ли смещения в ту или иную сторону.
И так же, как и в случае с монетой, важно, чтобы таких пробегов было как можно больше, иначе вероятность ошибки будет слишком велика.
Если вернуться к нашему примеру с двумя алгоритмами, то мы все равно можем с уверенностью сказать, что первый новый алгоритм лучше старого.
А вот второй вызывает больше сомнений, несмотря на то, что у него больший процент правильных ответов и ошибок.
Возможно, это действительно работает лучше, но, чтобы быть уверенным, необходимо провести больше испытаний.
Теги: #статистика #геоинформационные сервисы #Яндекс.
трафик
-
Как Получить Эффективную Ит-Поддержку
19 Oct, 24
