Дипломная работа студента 974 группы ѕПрогнозирование времени прибытия автомобильных рейсов



Скачать 188.21 Kb.

Дата31.01.2017
Размер188.21 Kb.
Просмотров90
Скачиваний0
ТипДиплом

Московский физико-технический институт
(Государственный университет)
Факультет управления и прикладной математики
Кафедра ѕИнтеллектуальные системыї
ДИПЛОМНАЯ РАБОТА СТУДЕНТА 974 ГРУППЫ
ѕПрогнозирование времени прибытия автомобильных рейсов,
совершающих междугородние перевозкиї
Выполнил:
студент 4 курса 974 группы
Шульга Александр Вадимович
Научный руководитель:
к. ф-м. н., н. с. ВЦ РАН
Чехович Юрий Викторович
Москва, 2013

Содержание
1 Введение
3 2 Постановка задачи, исходные гипотезы, входные данные
9 2.1 Основные обозначения и исходные гипотезы . . . . . . . . . . . . . . . .
9 2.2 Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.3 Задача минимизации . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.4 Структура данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.5 Предобработка данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3 Описание предложенных алгоритмов
12 4 Вычислительный эксперимент
15 4.1 Построение историй проездов H
i
. . . . . . . . . . . . . . . . . . . . . . . 15 4.2 Алгоритм сложения средних времен проездов отрезков BaseAlg . . . . . 17 4.3 Алгоритм сложения гистограмм HistAlg . . . . . . . . . . . . . . . . . . 18 4.4 Алгоритм построения эмпирической функции распределения методом сэмплирования DistrAlg . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 5 Заключение
23 1

Аннотация
Рассмотрена задача прогнозирования времени прибытия автомобилей, со- вершающих междугородние перевозки. Были предложены алгоритмы, основан- ные на истории проездов автомобилей, которые решают данную задачу на вы- деленном участке дороги Тосно-Химки. Был сделан сравнительный анализ и предложены критерии качества каждого из алгоритмов. Итоговая версия про- гноза основана на построении эмпирической функции распределения по вре- менам проездов по всей дороге, используя метод сэмплирования для функций распределения отдельных участков дороги. Исследованы устойчивость итогово- го алгоритма к многократным запускам и к прореживанию исходных данных.
Так же была исследована его обобщающая способность. Все алгоритмы тести- ровались на реальных данных.
Ключевые слова: метод сэмплирования, travel-time prediction, функция рас- пределения случайной величины.
2

1 Введение
Актуальность темы. На сегодняшний день задача прогнозирования времени при- бытия автомобилей является весьма существенной для различных прикладных об- ластей. Давно известно, что пробки на дорогах в больших городах, а так же на основных магистралях и дорогах, переросли в проблему едва ли не первой степе- ни важности. Предсказание времени прибытия автомобилей может быть полезным для многих компаний, связанных с транспортом. Дальнейшие исследования в этой сфере могут значительно упростить и улучшить как транспортные перевозки, так и пассажирские.
Цель работы. Построить несколько вариантов алгоритмов, основанных на исто- рических данных проездов, которые будут решать поставленную задачу прогнози- рования времени прибытия автомобилей. Построить критерии для оценки качества прогнозирования алгоритмов.
Методы исследований. При построении алгоритмов использовались методы пре- добработки данных  медианная фильтрация, фильтрация выбросов и неинформа- тивных треков, методы восстановления плотности распределения, методы построе- ния эмпирических функций распределения случайных величин и суммы случайных величин. При оценке качества алгоритмов использовались методы сравнения эмпи- рических функций распределения и методы оценивания абсолютных ошибок алго- ритмов. Для программной реализации разработанных алгоритмов использовались среды MATLAB, MySQL.
Научная новизна.

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

Разработан алгоритм на основе модели, который выдает не единичное значение прогноза времени, а распределение вероятности по времени прибытия.

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

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

Делает предобработку входных данных;

Разбивает заданный маршрут на отрезки;

Привязывает к каждому отрезку историю проездов по нему;

Строит алгоритм на основе историй проездов по каждому из отрезков;

Визуализирует результаты.
Положения, выносимые на защиту:

Алгоритм прогнозирования времени прибытия автомобилей, основанный на по- строении функции распределения суммы случайных величин  времен проез- дов по отрезкам дороги, с помощью метода сэмплирования.
Апробация. Результаты квалификационной работы бакалавра были использова- ны для решения задачи прогнозирования времени прибытия автомобилей для ком- пании Cargo  РНТ.
Обзор литературы. [1]. Short Term Trac Prediction Models
Обзорная статья по трем основным типам моделей для предсказания трафика  на- ивные, параметрические и непараметрические. Приводятся их основные разновид- ности, вкратце рассказывается про ключевые недостатки и преимущества. В конце статьи дана сравнительная таблица, а так же огромный список литературы.
[2].Inter - Urban Short Term Trac Congestion Prediction
В статье представлено достаточно много теоретического материала по тематике транспорта. Дан обзор различным алгоритмам, так же есть история DTM [3]. Но практической ценности статья не представляет, так как нет никаких исследований и проектов.
[4].Прогнозирование загруженности автомобильных дорог
4

Рис. 1: Сравнительная статистика алгоритмов по метрике Яндекса
Рассматриваются различные подходы к предсказанию трафика, и делается срав- нительная статистика работы различных методов. Основные рассмотренные мето- ды  средневзвешенное, сингулярное разложение, нейронные сети, метод ближайших соседей, а так же их модификации (кластеризация, глобальные эффекты и комби- нирование различных методов).Вкратце изложены основные идеи и формулы алго- ритмов.
Результаты работы представлены на Рис. 1, где:
Baseline  это ѕпростая скептическая оценкаї: средняя скорость для участка по всем дням месяца в одно и тоже время. Если данных не было, то скорость полагали рав- ной 0;
Basic I, II, III  базовые модели I, II и III соответственно;
SVD  алгоритм, на основе метода сингулярного разложения;
NN  алгоритм, на основе нейронных сетей;
LAD I  комбинирование результатов вышеупомянутых алгоритмов, за исключени- ем базовой модели III;
LAD II  комбинирование результатов базовой модели III и LAD I;
Final  финальный результат, построенный на основе базовой модели III с исполь- зованием кластеризации.
Используя данные Яндекса, делается вывод, что простые алгоритмы, основан- ные на вычислении средних скоростей, работают лучше алгоритмов, построенных на основе сложных моделей. Минусом статьи является отсутствие сравнения работы алгоритмов на других данных, а так же не проводится сравнение с алгоритмами, у которых больше параметров. Данная статья может быть полезна при использовании в прогнозировании фактора загруженности дорог.
5

[5].Real-time travel path prediction using GPS-enabled mobile Phones
Работа посвящена предсказанию маршрута в реальном времени с помощью GPS
на телефоне. Предложен алгоритм (с графической схемой), который использует исто- рические данные и положение в реальном времени. Алгоритм состоит из двух частей.
Первая - строит путь по данным от GPS. Вторая часть алгоритма делает прогноз времени, основываясь на сходстве шаблонов.
Результаты : Алгоритм тестировался на сети Sprint - Nextel CDMA и было по- казано, что он выдает правильные результаты. Таким образом, данная концепция алгоритма работает. Минусы алгоритма в том, что он нуждается в доработке, по- тому что в нем задействовано мало параметров. Никаких конкретных численных данных нет. Так же нет готовых продуктов.
[6].Travel-Time Prediction using Gaussian Process Regression: A Trajectory-Based
Approach
Статья про алгоритм, использующий регрессию для гауссовского процесса
(Gaussian Process Regression). Новизной является способность предсказывать вре- мя для любого пути (в том числе и не использовавшегося ранее), если схожесть между участками путей определена с помощью ядра (kernel function [7]). При этом не нужно использовать большие массивы данных. Для ускорения вычислений GPR
используется факторизация Холецкого [8].
Результаты - Эксперимент проводился на реальных данных центра г.Киото, Япо- ния и дал весьма точные предсказания времени. В минусы можно записать большое время вычислений. Так же было рассмотрено мало видов ядер.
[9].Travel Time Prediction System (TIPS)
Статья про оценивание эффективности внедренной системе прогнозирования
TIPS, которая использует свои детекторы. В статье представлено достаточно много
6
таблиц и графиков, но теоретических расчетов не много. В результате было уста- новлено, что при прогнозировании с использованием временных рядов с лагом в 30
секунд, предсказанные значения должны отображаться на Changeable Message Sign
(CMS) для водителей с 4х минутными интервалами, и информация на CMS не долж- на меняться в течении 3х минут.
[10].Trac Modelling and Prediction using ARIMA/GARCH Model
Статья о комбинации двух моделей  ARIMA и GARCH [11]. Весьма подробно описана сама модель и методы оценивания ее параметров. В сравнении ставилась модель FARIMA [12]. Тестировались они на реальных данных LBL-TCP-3.
Основные результаты - нелинейные временные ряды могут делать прогнозы луч- ше, чем классические линейные, даже если линейные временные ряды могут вести себя автомодельно (selfsimilarity). Новизна работы в том, что модель позволяет ра- ботать с нестационарными временными рядами. В то же время есть и проблемы - неустойчивость и сложность вычислений.
[13].Evaluation of DynaMIT - A Prototype Trac Estimation and Prediction System
Еще один готовый продукт  DynaMIT . Статья о внедрении системы DynaMIT в
Hampton Roads network. Параметрами модели являются матрицы корреспонденций.
Статья большая, с многочисленными выкладками и графиками.
Основные результаты  DynaMIT показала хорошую производительность с
RMSN ошибками в пределах 0.15 ? 0.25 для оценивания trac sensor, когда эти предсказанные trac sensor counts были в пределах 0.25 ? 0.4. Проблемы DynaMIT:
подсчет трафика  не очень чувствительный параметр в оценивании эффективно- сти и прогнозировании системы. К тому же дополнительные параметры могут быть неоптимальными для всех сегментов.
[14].An Adaptive Travel Time Prediction Model Based On Pattern Matching
7

В данной статье предложена модель предсказания трафика, основанная на сход- стве шаблонов. ѕПохожестьї находят с помощью генетического алгоритма (который весьма подробно описан). Данные проверялись на inbound section of route no. 3 of the
Tokyo Metropolitan Expressway, i.e. from Yoga to Tanimachi. Результаты  адаптивные параметры улучшают оценки модели и соответствуют интуиции (лучше, чем stepwise параметры). Средние абсолютные ошибки и средние абсолютные процентные ошибки и выше находятся в пределах  ±5%, ±10% и ±5 минут. Большим плюсом является то, что адаптивные параметры увеличивают эффективность модели, и она может быть внедрена для любой дороги с любыми условиями без модификаций.
[15].Short-Term Trac Forecasting Using The Local Linear Regression Model
Небольшая статья про краткосрочное прогнозирование трафика с использова- нием модели локальной линейной регрессии. Достаточно подробно описан алгоритм.
Тестировался он на Houston US-290 Northwest freeway eastbound .
Результаты  данный алгоритм более эффективен, чем kNN, локальные кон- стантные методы и ядерное сглаживание. Так же, в отличие от этих методов, LLR
использует как исторические, так и текущие данные. Проблемы данного метода 
сильное различие при одно- и многошаговом предсказании.
[16].Как работают Яндекс.Пробки
Небольшая статья собственно о том, как работают Яндекс.Пробки. Описан толь- ко поэтапный план, никаких теоретических выкладок нет. Данные собираются с раз- личных источников, отсеиваются ненужные, и потом определяется загруженность транспортной сети. Далее составляется карта пробок города. А время маршрута определяется в сравнении с эталонным временем проезда по данному участку. Плюсы данного проекта  простота реализации. Минусы  большая неточность прогноза,
и результаты предоставлены только в пределах одного города.
[17].Расчет оптимального маршрута 2.0 8

Короткая обзорная статья о том, как при расчете оптимального маршрута ис- пользуется Google.Maps API. Никакого теоретического материала или даже алгорит- ма нет. Так как при определении времени маршрута нужен сам трек, то все недостат- ки этого сервиса у Google наследуются от недостатков Google.Maps API. Плюсами проекта является то, что он хорошо прокладывает маршрут в рамках одного города и около 8 ? 10 промежуточных пунктов. Минусы  мало промежуточных пунктов.
Так же проект не умеет строить маршруты между городами.
2 Постановка задачи, исходные гипотезы, входные данные
2.1 Основные обозначения и исходные гипотезы
Задано:

Точка  положение машины в определенное время;

Трек T  последовательность точек данного автомобиля;

Маршрут M  трек от стартовой точки A до конечной B;

Отрезок i  ребро графа дорог G;

История проездов H  таблица со всеми данными;
Введено:
• H
i
 таблица времен проездов всех автомобилей по данному отрезку дороги;
• Ї
x = Ї
x(t) = (x, Ї
?(t))
 объект, где x  описание автомобиля, Ї?(t) параметры автомобиля в каждый момент времени.
• T
i
 время въезда на i -й отрезок;
• t i
 время проезда i -го отрезка;
• T
 общее время в пути.
Таблица треков H задает признаковое описание объектов, т.е. объект  авто- мобиль, совершающий маршрут из точки A в заданное известное время в точку B.
9

Описание объекта  последовательность точек трека данного автомобиля.
Пусть Їx = Їx(t)  объект. Его можно представить в виде Їx = (x, T
0
, Ї
?(t))
, где x 
описание автомобиля, Ї?(t) параметры автомобиля в каждый момент времени (его местоположение).
Основное предположение  истории проездов H достаточно для построения про- гноза.
Требования, предъявляемые к модели.

Адекватное соответствие реальному времени проезда по выбранному маршру- ту:
|t real
? t f orecast
| ? ?

Устойчивость прогноза к разреженности начальных данных, а так же к много- кратному запуску алгоритма;

Отсутствие переобучения (желательно). Алгоритм должен при тех же парамет- рах работать для других участков дороги.
2.2 Постановка задачи
Дано:

множество отрезков заданного маршрута M : {i}, i = 1, n;

история проездов каждого из отрезка H
i
;

Объект Їx;

Контрольная выборка X
k
= {Ї
x
1
, . . . , Ї
x k
}
с ответами в виде времен проездов всего маршрута Y
k
= {T
1
, . . . , T
k
}
При вычислении времени въезда на отрезок предполагается преобразование типов данных.
Требуется построить функцию f:
t i
= f (Ї
x j
(T
i
), T
i
, H
i
, ?),
10
где ?  параметры функции f.
Тогда прогноз для всего маршрута будет:
T = F (Ї
x j
, T
0
, H
1
. . . H
n
, ?),
где
F (Ї
x j
, T
0
, H
1
. . . H
n
, ?) =
i=n i=1
f (Ї
x j
(T
i
), T
i
, H
i
, ?),
T
i+1
= T
i
+ f (Ї
x j
(T
i
), T
i
, H
i
, ?).
Вводится функция потерь L(T
i
, F (Ї
x j
, T
0
, H
1
. . . H
n
, ?))
и функционал качества алго- ритма
Q(f, X
k
) =
j=k j=1
L(T
i
, F (Ї
x j
, T
0
, H
1
. . . H
n
, ?)).
2.3 Задача минимизации f = arg min
?
Q(F (Ї
x j
, T
0
, H
1
. . . H
n
, ?), X
k
).
Таким образом исходная проблема сводится к двум следующим подзадачам:
1. Выбор алгоритма f  задать модель на данных H и H
i
2. Оптимизировать параметры функции ?.
В данной работе будет предложено несколько вариантов решения этих двух подзадач.
2.4 Структура данных
История проездов автомобилей представлена в виде таблицы треков H, полученных по данным GPS:
• vehicle
_id  id автомобиля;
• id
 id точки;
• date
 время с точностью до 2х секунд;
• latitude
 широта;
• longitude
 долгота;
История проездов по каждому из отрезков представлена в виде таблицы H
i
:
11

• vehicle
_id  id автомобиля;
• id
_tr  id маршрута данного автомобиля;
• date
 время въезда на данный отрезок точностью до 2х секунд;
• t
 время проезда по данному отрезку;
Граф дорог был выделен из карт OSM [18] и представляет собой набор точек с ко- ординатами а так же участки дорог в виде последовательностей точек. Направление участка дороги задается параметрами в тэгах а так же последовательностью точек.
Участки дорог не всегда являются ребрами графа, поэтому отдельной задачей явля- ется выделение ребер из G.
2.5 Предобработка данных
История проездов не содержит разбиения на маршруты, поэтому пришлось разби- вать на маршруты по критерию задержки сигнала. Если следующая точка в треке в
H
по времени была позже более чем на 3 часа  это начало нового маршрута.
Так же в H присутствовали как повторяющиеся записи, так и выбросы, связанные с неточностью GPS, поэтому проводилась фильтрация данных.
Выбранный участок дороги от Тосно до Химок разбивался на отрезки i. Для каж- дого отрезка выделялись все автомобили, которые проезжали эти отрезки, и вычис- лялись времена проездов. Таким образом были сформированы истории проездов H
i
При привязке истории проездов H
i к i -му отрезку делалась фильтрация остановок и быстрых времен проездов (связанные с ошибками в данных) с помощью медианной фильтрации с порогами в 10 %. Так же для каждой точки в таблице H вычислялось расстояние до дороги и фильтровались точки, которые лежат дальше, чем значение порога h.
3 Описание предложенных алгоритмов

Алгоритм сложения средних времен проездов отрезков(далее BaseAlg):
Для каждого отрезка i = 1, n вычисляется среднее значение времени проезда t
i по подмножеству H
Ї
?,i
? H
i в зависимости от входных параметров Ї? объекта
Ї
x
. Итоговый прогноз  T (Їx) =
i=n i=1
t i
12

Вход: входные параметры ?
0
= Ї
?(T
0
),
число отрезков n
Выход: прогноз времени T
1. Для всех i = 1, . . . , n
2. Вычислить среднее время проезда для отрезка i  t i
по подвыборке
?
H
i
= H
i
(?
i
) = H
Ї
?,i
;
3. Пересчитать входные параметры для следующего отрезка ?
i+1
= Ї
?(T
i+1
)
и время въезда на следующий отрезок T
i+1
;
4. T := T + t i
;

Алгоритм сложения гистограмм (далее HistAlg):
Задается параметр h  шаг гистограммы, одинаковый для всех отрезков. Для каждого отрезка i = 1, n вычисляется нормированная гистограмма G
i рас- пределения времен проездов в соответствии с величиной h по подмножеству
H
Ї
?,i
? H
i
. G
i представляет собой таблицу с двумя столбцами t и p, где t  вре- менной интервал ширины h (интервал можно отождествить, например, с его серединой), а p  доля значений времен проездов, попавших в интервал t;
Предполагается, что отрезки независимы. Тогда формула для сложения гисто- грамм имеет вид:
G
1+2
= {(t min
, p(t min
)) . . . (t max
, p(t max
))}
;
t min
= min(t
1
) + min(t
2
), t
1
? G
1
, t
2
? G
2
;
t max
= max(t
1
) + max(t
2
), t
1
? G
1
, t
2
? G
2
;
p
1+2
(t) =
t
1
+t
2
=t p
1
(t
1
) · p
2
(t
2
), ?t ? G
1+2
;
Вход: входные параметры ?
0
= Ї
?(T
0
),
число отрезков n, ширина окна h
Выход: прогноз времени T
1. Для всех i = 1, . . . , n
2. Построить нормированную гистограмму G
i
= {t, p i
(t)}
времени проезда по подвыборке ?
H
i
= H
i
(?
i
) = H
Ї
?,i
;
13

3. Выход из цикла
4. Применить алгоритм сложения гистограмм соседних отрезков для всех от- резков с получением итоговой гистограммы G
T
5. Построить прогноз по G
T
Итоговый прогноз представляет собой гистограмму  распределение вероятно- сти по временным интервалам.
Так как параметр h может быть очень малым, итоговую гистограмму можно пересчитать для новых интервалов ширины €h > h по формуле:
p(€
t) = p[€
t, €
t + €
h] =
t?[€
t,€
t+€
h]
p(t)

Алгоритм построения эмпирической функции распределения методом сэмплирования (далее DistrAlg):
Для каждого отрезка i = 1, n вычисляется эмпирическая функция распределе- ния F
i
(t)
, где t время проезда, по подмножеству H
Ї
?,i
? H
i
. Затем вычисляются коэффициенты корреляции c i
для каждых соседних пар отрезков [i ? 1, i].
Известно, что если t ? F, r ? U(0, 1) ? F
?1
t
(r) ? F
Суть метода сэмплирования заключается в том, что N раз для каждого отрезка выбираются числа r i
, вычисляются значения t i
= F
?1
i
(r i
)
, а затем суммируют- ся T
j
=
i=n i=1
t i
, j = 1, N
. По найденным T
j строится итоговая эмпирическая функция распределения F
T
Задача состоит в выборе модели подбора случайных величин r i
= g(i, r i?1
, c i
)
Вводится порог p c
, для которого если c i
< p c
, g(i, r i?1
, c i
) = rand(0, 1)
Если c i
? p c
, то функция g вводится по следующим соображениям:
Так как коэффициент корреляции для соседних двух отрезков больше порога,
значит должны коррелировать и времена проездов t i
, t i?1
, и, следовательно,
r i
и r i?1
. Значение r i
должны выбираться случайным образом из интервала,
который содержит r i?1
: r i
? [r i?1
? a, r i?1
+ b]
, причем возможно, что a = b.
Величины a, b должны зависеть от коэффициента корреляции:
Соответственно, если c i
= 1
 линейная связь, то интервал ѕсхлопываетсяї в точку r i?1
, a = b = 0
. Если же c i
< p c
, то интервал вырождается в [0, 1].
14

Вход: входные параметры ?
0
,
число отрезков n, порог коэффициента корреляции p c
, w
1
, w
2
Выход: прогноз времени T
1. Для всех i = 1, . . . , n
2. Для отрезка i построить эмпирическую функцию распределения F
i
(t)
вре- мени проезда по ?
H
i
= H
i
(?
i
)
;
3. Для отрезка i вычислить коэффициент корреляции c i
с отрезком i ? 1;
4. Для всех j = 1, . . . , N = 1000 . . . 30000 5. инициализировать T
j
:= 0 6. r
1
= rand(0, 1), T
j
:= F
?1 1
(r
1
)
7. Для всех i = 2, . . . , n
8. r i
= rand(r i?1
? a, r i?1
+ b)
Если c i
< p c
,
Тогда a = 0, b = 1
Иначе a = ?
1
(r i?1
, c i
, w
1
), b = ?
2
(r i?1
, c i
, w
2
)
9. t i
= F
?1
i
(r i
), T
j
:= T
j
+ t i
10. Выход из цикла по i
11. Выход из цикла по j
12. Построить эмпирическую функцию распределения F
T
по T
j
13. Построить прогноз по F
T
Прогноз по функции F
T
(t)
можно построить либо вычислив функцию плот- ности f
T
(t)
, либо построив график распределения вероятности по интервалам времени, для которого вероятность попасть в интервал [t, t + k]:
P [t, t + k] = F
T
(t + k) ? F
T
(t)
4 Вычислительный эксперимент
4.1 Построение историй проездов H
i
Первым делом выделялась дорога M из Тосно в Химки из карт OSM. Нужно бы- ло упорядочить точки маршрута в порядке их следования. Для этого использовался поиск в глубину (предполагалось, что карты не содержат ошибок и тогда алгоритм
15

Рис. 2: Доля точек внутри полосы ширины h, в зависимости от h.
правильно находит последовательность). Всего точек в M около 2600.
Начальная таблица с треками H содержит около 80 млн записей. Данных о точных разбиениях на маршруты не было, поэтому пришлось разбивать ѕвручнуюї
по задержке сигналов от GPS. Если следующая точка трека была на 3 часа позже текущей  это новый маршрут. Далее отбрасывались все данные, которые не попа- дали в условный прямоугольник, образованный самыми крайними точками марш- рута M. После фильтрации повторяющихся записей в итоге получилась первично- обработанная история проездов €
H
, которая содержит порядка 12 млн записей.
Для каждой точки A вычислялось расстояние до двух ближайших точек марш- рута M, а так же расстояние между этими точками. По формуле Герона находилось расстояние h от A до дороги.
График зависимости доли точек из истории, лежащих внутри полосы ширины h во- круг дороги от h приведен на Рис. 2.
Видно, что 90 % данных лежит в 200м полосе. Излом графика объясняется тем, что
16
при больших h в долю данных попадали точки и с других дорог, которые примыкают к M. Остальные точки были отфильтрованы, как выбросы, связанные с неточностью
GPS.
Далее, нужно было разбить исходную дорогу на отрезки. Выделялись все доро- ги, которые имели общие точки с M. Тогда точки пересечения и являлись концами отрезков. По сути отрезок  это участок дороги, с которого нельзя съехать и на который нельзя въехать, кроме как на концах. Таким образом было получено 506
отрезков i = 1, 506.
Потом для каждой точки определялся отрезок, которому она принадлежит. Фор- мально, точка принадлежит отрезку, если ее проекция на дорогу лежит внутри этого отрезка.
Вычисление историй проездов H
i производились следующим образом:
Если две соседние точки (x
1
, T
1
), (x
2
, T
2
)
трека (для данного маршрута данного ав- томобиля) лежат соответственно на i и k отрезке (i < k), то вычислялась скорость v =
dist(x
1
,x
2
)
T
2
?T
1
, а затем время въезда на каждый из отрезков {T
j
| j : j > i, j ? k}
и время проезда каждого из отрезков {t j
| j : j > i, j < k}
К этим таблицам проездов применялась медианная фильтрация с 10 % порогом и в итоге получались H
i
4.2 Алгоритм сложения средних времен проездов отрезков
BaseAlg
Задавался только один входной параметр  час недели t = n h
+ 24n d
, где n h
 час дня, когда стартовала машина, а n d
= 0, 6
 номер дня.
На Рис. 3, 4 приведен график зависимости времени проезда от часа недели, а так же относительная ошибка в сравнении с контрольной выборкой. Ошибка вычисляется по формуле:
Err =
|f (t)?x(t)|
x(t)
17

Рис. 3: Прогноз алгоритма BaseAlg в за- висимости от часа недели.
Рис. 4: Ошибка алгоритма BaseAlg в сравнении с контрольной выборкой в за- висимости от часа недели.
Видно, что прогноз дает не достаточно качественные результаты и что ошибка дан- ного алгоритма не превышает 30 %, но при этом значения сильно разбросаны.
4.3 Алгоритм сложения гистограмм HistAlg
В зависимости от входных параметров Ї? (час или день недели, тип автомобиля,
и т. д.), делается выборка истории H
Ї
?,i
? H
i для каждого из отрезков. По ней строит- ся гистограмма доли выборки, попавшей во временной интервал t заданной ширины h
. Предполагается, что соседние отрезки независимы.
Пример работы алгоритма для двух произвольных соседних отрезков представлен на Рис. 5, 6, 7, 8.
Контрольная выборка так же формировалась из автомобилей, проехавших весь маршрут. Но остановки на отрезках j заменялись на наиболее вероятные значения времен проездов в соответствии с гистограммой для j. На Рис. 9, 10 представлены итоговые гистограммы с величиной шага h = 5 с и h = 10 с в сравнении с кон- трольной выборкой. Пересчитывались данные гистограммы на интервалы шириной в 50 с.
В связи с тем, что вычисление итоговой гистограммы  весьма трудоемкая про- цедура, а сама итоговая гистограмма лишь приближает вид распределения вероят- ности по интервалам, алгоритм HistAlg так же является не эффективным: оптими-
18
зация параметра h будет занимать много времени, а решение будет неустойчивым.
Идея же настройки параметров h i
для каждого из отрезков может привести как к еще большему увеличению трудоемкости, так и к возможному переобучению.
Рис. 5: Гистограмма первого отрезка.
Рис. 6: Гистограмма второго отрезка.
Рис. 7: Гистограмма объединения отрез- ков.
Рис. 8: Алгоритм сложения гистограмм.
4.4 Алгоритм построения эмпирической функции распределе- ния методом сэмплирования DistrAlg
Чтобы еще раз показать, что Алгоритм сложения гистограмм не эффективен, пред- лагается сравнение функций распределений контрольной выборки, и прогноза, по- строенного в предположении о независимости соседних отрезков на Рис. 11.
19

Рис. 9: HistAlg (красный) в сравнении с контрольной выборкой, h = 5c.
Рис. 10: HistAlg (красный) в сравнении с контрольной выборкой, h = 10c.
Зависимость вида функции распределения от порога p c
представлена на Рис. 12, 13, 14
и 15.
В результате подбора параметров эмпирическим методом, был установлен вид функ- ции g:
If c i
< p c
, then a = 0, b = 1
;
Else
If r i?1
> 0.5, then a := max{r i?1
? (1 ? r i?1
)(1 ? c i
)/0.815, 0}
;
b := min{(1 ? r i?1
) + (1 ? r i?1
)(1 ? c i
)/4, 1}
;
Else a := max{r i?1
? (r i?1
)(1 ? c i
)/0.815, 0}
;
b := min{r i?1
+ (r i?1
)(1 ? c i
)/4), 1}
;
g(i, r i?1
, c i
) = rand(r i?1
? a, r i?1
+ b)
Сравнение графиков функций распределения итоговой модели и контрольной выборки представлено на Рис. 16.
Так же для анализа можно использовать методы статистики. В данной работе приме- нялся критерий Колмогорова-Смирнова [19]. При текущих параметрах для N = 3000
(число сэмплирований) значение статистики Колмогорова-Смирнова (далее ?
?
) со- ставляет в среднем около 0.96.
20

Рис. 11: Сравнение функции распределения прогноза (красным) с контрольной вы- боркой при гипотезе о независимости отрезков.
Это весьма хороший результат согласно таблице критических значений статистики
Колмогорова-Смирнова:
Таблица 1: Критические значения статистики Колмогорова-Смирнова
?
0.20 0.10 0.05 0.02 0.01 0.001
?
?
1.073 1.224 1.358 1.520 1.627 1.950
Полученную модель так же нужно было проверить на устойчивость. Первый способ  повторить построение N сэмплирований T раз и вычислить значения ?
?
Второй способ  истории проездов H
Ї
?,i
= €
H
i разбить независимо на две произволь- ные подвыборки различной длины €
H
i,less и €
H
i,bigg
. По ним построить прогноз и вычис- лить значения статистики ?
?
. Результаты экспериментов на устойчивость приведены в таблице 2 и 3.
Таблица 2: Устойчивость модели при многократном запуске сэмплирований
ќ эксперимента
1 2
3 4
5 6
7 8
9 10
?
?
0.805 0.985 0.805 1.202 0.598 0.989 0.859 1.206 1.081 1.079 21

Таблица 3: Устойчивость модели при переразбиении истории проездов H
i less
1.857 1.954 0.867 1.064 1.458 0.827 1.914
bigg
0.863 0.819 0.817 0.67 0.813 1.082 0.805
Так же модель нужно было проверить модель на переобучение.
Первый способ  построить прогноз для какого-то участка исходной дороги. Резуль- таты приведены на Рис. 17 и 18.
Второй предложенный способ  построить прогноз для обратной дороги Химки 
Тосно. Результат показан на Рис. 19.
Видно, что данный метод склонен к переобучению на новых участках дорог, поэто- му в дальнейших работах предлагается разработать методы настройки параметров данного алгоритма.
Прогноз алгоритма DistrAlg представлен на Рис. 20. По оси Y отложена веро- ятность попадания в интервал ширины h = 600c и h = 300c, а по оси X  середина каждого интервала.
Рис. 12: Сравнение вероятности попада- ния значения в заданный интервал для прогноза (красным) и контрольной вы- борки для интервалов шириной 300с.
Рис. 13: Сравнение вероятности попада- ния значения в заданный интервал для прогноза (красным) и контрольной вы- борки для интервалов шириной 600с.
22

Рис. 14: Сравнение функции распреде- ления контрольной выборки и прогноза
(красным) при p c
=0.6
Рис. 15: Сравнение функции распреде- ления контрольной выборки и прогноза
(красным) при p c
=0.7 5 Заключение
Построено несколько алгоритмов, строящих прогноз времени прибытия:

Алгоритм сложения средних времен проездов отрезков BaseAlg,

Алгоритм сложения гистограмм HistAlg,

Алгоритм построения эмпирической функции распределения методом сэмпли- рования DistrAlg.
Был сделан анализ качества каждого из них. Показано, что алгоритмы, основанные на сложении гистограмм и вычисления среднего времени проезда дают не очень точ- ные результаты. В отличии от них, алгоритм DistrAlg показал хорошее качество прогноза, а так же обладает устойчивостью к многократным запускам и прорежива- нию историй проездов. Дальнейшие исследования будут направлены на улучшение обобщающих способностей алгоритма и разработку методов подбора параметров.
Список литературы
[1] F.M. Sanders C.P.IJ. van Hinsbergen, J.W.C. van Lint. Short term trac prediction models. ITS World Congress, Beijing, China, October 2007.
23

Рис. 16: Сравнение функции распреде- ления контрольной выборки и прогноза
(красным) при p c
=0.8
Рис. 17: Сравнение функции распреде- ления контрольной выборки и прогноза
(красным) при p c
=0.9
Рис. 18: Сравнение функций распределения прогноза (красным) и контрольной вы- борки.
[2] http://doc.utwente.nl/57639/1/thesis_Huisken.pdf.
[3] http://www.esafety-effects-database.org/applications_11.html.
[4] http://elar.urfu.ru/bitstream/10995/3060/1/russir-2010-06.pdf.
[5] http://www.csee.usf.edu/REU/publications/Persad%20Maharaj%20-%
20PathPrediction%20-%20july%2031.pdf.
[6] http://www.siam.org/proceedings/datamining/2009/dm09_108_idet.pdf.
24

Рис. 19: Сравнение функций распределе- ния прогноза (красным) и контрольной выборки для участка дороги между 150м и 400м отрезком.
Рис. 20: Сравнение функций распределе- ния прогноза (красным) и контрольной выборки для участка дороги между 0м и 300м отрезком.
Рис. 21: Сравнение функций распределения прогноза (красным) и контрольной вы- борки для обратной дороги.
[7] http://en.wikipedia.org/wiki/Kernel_(statistics).
[8] http://ru.wikipedia.org/wiki/Разложение_Холецкого. Факторизация Холец- кого.
[9] http://ssom.transportation.org/Documents/MwSWZDI-2001-Drakopoulos-TIPS.
pdf.
25

[10] http://www.cost285.itu.edu.tr/tempodoc/TD05_12.pdf.
[11] R. (1980). Granger, C. W. J.; Joyeux. "an introduction to long-memory time series models and fractional dierencing". Journal of Time Series Analysis, 1: 1530.
[12] http://en.wikipedia.org/wiki/Autoregressive_fractionally_integrated_
moving_average.
[13] http://cts.virginia.edu/docs/UVACTS-15-11-71.pdf.
[14] http://www.transport.iis.u-tokyo.ac.jp/publications/2004-017.pdf.
[15] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.202.
3791&rep=rep1&type=pdf.
[16] http://company.yandex.ru/technologies/yaprobki/.
[17] http://www.integprog.ru/route2/.
[18] http://www.openstreetmap.org/.
[19] http://ru.wikipedia.org/wiki/Критерий_согласия_Колмогорова.
26


Поделитесь с Вашими друзьями:


База данных защищена авторским правом ©nethash.ru 2017
обратиться к администрации

войти | регистрация
    Главная страница


загрузить материал