Оценка и прогнозирование параметров транспортных потоков с использованием композиции методов машинного обучения и моделей прогнозирования временных рядов

ОЦЕНКА И ПРОГНОЗИРОВАНИЕ ПАРАМЕТРОВ ТРАНСПОРТНЫХ ПОТОКОВ С ИСПОЛЬЗОВАНИЕМ КОМПОЗИЦИИ МЕТОДОВ МАШИННОГО ОБУЧЕНИЯ И МОДЕЛЕЙ ПРОГНОЗИРОВАНИЯ ВРЕМЕННЫХ РЯДОВ

Агафонов А.А., Мясников В.В.

Институт систем обработки изображений РАН, Самарский государственный аэрокосмический университет имени академика С. П. Королёва

Аннотация

Работа посвящена решению задачи анализа и прогнозирования транспортных потоков в сети крупного города. В качестве исходных данных для решения указанной задачи используются данные ОРБ/ГЛОНАСС о местоположении отдельных транспортных средств. Проецируя полученную информацию на граф транспортной сети города, а также используя дополнительную фильтрацию, можно получить оценку отдельных параметров транспортных потоков. Эти параметры используются для краткосрочного (в пределах часа) прогнозирования изменения ситуации в транспортной сети города. Предлагаемый оригинальный метод прогнозирования использует несколько этапов для построения прогноза. На первом этапе предлагается декомпозировать транспортный граф на некоторое число подграфов по территориальному признаку. На втором для описания пространственно-временного состояния распределения транспортных потоков в получаемых подграфах используется метод снижения размерности, основанный на методе главных компонент. На третьем этапе для каждого из подграфов формируется несколько элементарных прогнозов с использованием метода опорных векторов и метода потенциальных функций. На четвёртом этапе формируется дополнительный элементарный прогноз, рассчитываемый с использованием известных скалярной и векторной моделей Бокса-Дженкинса. На пятом этапе производится построение прогноза для каждого из подграфов с использованием адаптивной линейной композиции полученных элементарных прогнозов. На шестом, заключительном этапе производится расчёт прогнозных параметров транспортных потоков во всей транспортной сети города как линейной комбинации данных для подграфов. Проводится экспериментальное исследование эффективности предложенного метода прогнозирования на примере решения соответствующей задачи для транспортной сети города Самары, даётся сравнение результатов прогнозирования с другими способами построения прогнозов.

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

Введение

Развитие и повсеместное активное использование современных систем электронных коммуникаций, глобальных навигационных систем, систем компьютерного зрения, активных и пассивных датчиков различного типа и назначения [1] привело к появлению возможности решения чрезвычайно сложных проблем, сама постановка которых два десятилетия назад казалась невозможной. К числу таких проблем, несомненно, относятся проблемы создания «умных городов» (Smart Cities) [2] и интеллектуальных транспортных систем (ITS - Intelligent Transportation Systems) [3, 4]. Рассматриваемая в рамках настоящей работы задача построения краткосрочного (в пределах часа) прогноза параметров транспортных потоков (ТП) в крупных городах является одной из многих задач, которые приходится решать на пути полного и эффективного разрешения указанных проблем. В настоящем времени решение указанной задачи оказывается также полезно, что наглядно демонстрируют известные компании Microsoft, Яндекс и др., предоставляющие различные интернет-сервисы и/или мобильные приложения, которые позволяют участникам дорожного движения визуально анализировать развитие транспортной си-

туации в своём городе и планировать свои перемещения. При этом информация о прогнозных параметрах ТП может использоваться не только для просмотра, но и для решения сопутствующих технических задач. Примером такой задачи с формулировкой, привычной для участника дорожного движения, является задача навигации или задача построения оптимального маршрута, которая с математической точки зрения формулируется как задача поиска кратчайшего пути в динамическом графе [5, 6]. Естественно, использование прогнозных параметров ТП не исчерпывается только указанной задачей навигации [4, 7, 8].

Собственно задаче краткосрочного прогнозирования ТП посвящено в мировой печати огромное число работ. Подробные обзоры и детальные классификации можно найти в обзорных публикациях [9 - 11]. На основании этих работ можно выделить следующие основные подходы к решению задачи:

- регрессионные модели [12, 13];

- модели временных рядов [14 - 17];

- модели нейронных сетей [18 - 20];

- метод опорных векторов [21, 22].

Несмотря на огромное количество работ в исследуемой области, предлагаемые решения в настоящее

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

1) Основная часть существующих работ посвящена вопросам прогнозирования параметров ТП на отдельном сегменте улично-дорожной сети (УДС) по данным небольшой окрестности, как правило, перекрёстка. Совершенно очевидно, что такой подход серьёзным образом игнорирует информацию о состоянии УДС в целом, что не является хорошим решением. Также, «посегментный» подход создаёт проблемы при попытке его использования в крупных городах/мегаполисах по причине вычислительной и технологической сложности итогового решения.

2) Использование в качестве источников информации датчиков трафика (Traffic Detectors) [1], принцип работы которых заключается в прямом наблюдении за конкретном сегментом УДС. Недостаток такого решения очевиден - огромные финансовые затраты на создание требуемой для получения необходимой информации инфраструктуры систем наблюдения. Здесь следует отметить, что один из альтернативных подходов к получению информации был предложен российской компанией Yandex [23]. Его суть заключается в получении информации не от датчиков трафика, а напрямую от участников движения - транспортных средств (ТС) - посредством измерения их положения GPS/ГЛОНАСС - источниками и передачи указанной информации по беспроводным сетям (в Yandex - через соответствующие сервисы интернет-приложений). Настоящая работа использует аналогичный подход. Заметим также, что, учитывая существенную неполноту сведений, которые поступают в результате таких измерений (далеко не все ТС оборудованы соответствующими датчиками и/или передают необходимую информацию), этот подход не позволяет автоматически перенести существующие решения, которые были разработаны для датчиков трафика.

3) Недостаточный учёт в предлагаемых моделях и алгоритмах пространственно-временной избыточности данных. Прямое подтверждение пространственной избыточности дано в работе [24], где отмечено, что объём основной информации о пространственном распределении ТП составляет не более 10 % от объёма данных в сети. Косвенным подтверждением того же тезиса о наличии значительной избыточности в данных является использование вычислительных процедур распределения транспортных потоков в статических и динамических сетях на основании матрицы корреспонденции существенно меньшего (чем количество сегментов в УДС) размера [4, 7, 25 - 27]. Пространственная избыточность данных явно и косвенно была использована в ряде работ по краткосрочному прогнозированию ТП [19, 21 - 23]. Однако использование факта временной избыточности в известных авторам работах не встречалось.

Настоящая работа посвящена вопросу разработки метода (математической модели и соответствующего алгоритма её настройки) краткосрочного прогнозирования параметров ТП для УДС крупного населённого пункта по данным ОРБ/ГЛОНАСС - наблюдений от отдельных ТС. Метод разрабатывается таким образом, чтобы устранить указанные выше недостатки и иметь возможность использования различных алгоритмов прогнозирования в своём составе.

Основные обозначения и постановка задачи

Примем в качестве математической модели УДС ориентированный граф, дуги иеW которого соответствуют реальным участкам (сегментам) УДС, а вершины представляют собой разделяющие участки дорог узлы. Направление дуги определяет направление движения ТС на соответствующем участке сети, а параметр ТП на конкретном участке сети определим как функцию у WXT  Я, которая в конкретный момент времени ¿еТ для конкретной дуги WEW определяет его значение у(ш, ¿). В качестве параметров ТП на дуге могут выступать следующие величины [8, 25 - 28]:

- скорость потока;

- среднее время прохождения ТС сегмента сети

(величина, обратная к скорости потока);

- плотность потока;

- поток (собственно величина потока).

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

Геометрическое расположение сегмента wеW транспортной сети определим в виде двузначной функции вида х;(т) (те[0,1]) такой, что координаты (х, (0), х;(0)) и (х0;(1), х;(1)) определяют физическое расположение точек начала и конца соответствующего сегмента УДС, а геометрическое местоположение остальных точек можно получить, положив параметр в интервале ¿е (0, 1).

В дополнении к УДС будут рассмотрены маршруты - упорядоченная последовательность сегментов УДС (узлов и рёбер в графе), по которым производится движение общественных транспортных средств (ОТС). Обозначив И множество условных номеров маршрутов, величиной Шт в дальнейшем будем обозначать конкретный маршрут с номером те О в графе, то есть следующую последовательность из Zm рёбер:

№т ° <, <,-, -1.

Исходными данными для оценок параметров ТП выступают данные ОРБ/ГЛОНАСС-измерений, которые поступают с различных ТС как актуальная информация, то есть информация, поступающая в режиме реального времени. Формально эти данные могут быть представлены как последовательность пар физических координат следующего вида:

где Зс N - определяет множество условных номеров ТС, которые поставляют ОРБ/ГЛОНАСС - данные о своём местоположении; ' - задаёт порядковый номер поступившего ОРБ/ГЛОНАСС-сигнала. Дополнительно для маршрутных ОТС считаются известными один или два номера соответствующих маршрутов, обозначаемых далее т0(1), т1 (/). На практике альтернативные маршруты обычно различаются только направлением движения. В тех случаях, когда движение ОТС производится только в одном направлении, для него считаем известным единственный номер маршрута т(/). Для немаршрутных ТС номер маршрута считается неопределённым или незаданным.

Существенным моментом в данных (1) является то, что поступающие ОРБ/ГЛОНАСС-данные о координатах являются неточными, что вызвано погрешностями навигационных систем. То есть координаты в (1) можно интерпретировать в виде:

Р0

где пара (р('), р(')) определяет истинное расположение ТС, а (50,51) - вектор искажений. В связи с этим практически для всех поступающих данных (то есть пар 1, ]) следующее утверждение оказывается неверным:

3 щ х:

Более того, в тех редких случаях, когда соотношение (3) всё же оказывается верным, реальное расположение ТС может не совпадать с полученным. То есть следующая импликация может быть неверной:

(р0 (о х р; ({у) ) =

= ( хЩ(х), хЩ(х))д( Ро ('), р*)) =

= (хщ(х),хЩ(х)) ^ щ = Щлх = х.

Указанные недостатки данных ОРБ/ГЛОНАСС-сигналов приводят к необходимости дополнительной обработки данных для получения более точных оценок реального местоположения ТС.

Учитывая введённые обозначения, формальная постановка задачи получения краткосрочного прогноза для заданного параметра ТП УДС может быть сделана следующим образом:

имея заданный граф УДС со множеством рёбер W и множеством маршрутов {Ит}теа и актуальные (и исторические) данные о положении ТС в виде (1), рассчитать оценку (спрогнозировать) параметров ТП V(щ, *) для всех ще W и *= * + лА (п = 1, Л) .

В приведённой формулировке N - число формируемых прогнозов, расположенных регулярно с временным интервалом А, величина * - текущий момент времени. Прогнозный горизонт в этом случае опреде-

ляется величиной ЛА, которая для интересующего нас краткосрочного прогноза имеет порядок одного часа.

В свою очередь, построение метода краткосрочного прогнозирования параметров транспортных ТП для УДС заключается:

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

- в определении способа (алгоритма) настройки (идентификации) параметров указанной выше математической модели по данным реальных ОРБ/ГЛОНАСС-наблюдений (1). Предварительным, но необходимым этапом предлагаемого метода является преобразование исходных данных к виду, удобному для обработки. Суть такого преобразования - переход от набора данных (1), косвенно характеризующих параметры ТП в сети в конкретные моменты времени (прошлого), к собственно значениям параметров ТП в эти моменты:

v

Предлагаемый способ получения (4) на основании данных (1) представлен в следующем разделе.

Оценка параметров транспортных потоков по данным ОРБ/ГЛОНАСС-наблюдений

Предлагаемый способ построения актуальных оценок параметров транспортных потоков (4) по данным ОРБ/ГЛОНАСС-наблюдений (1) состоит из двух этапов:

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

- расчёт величин (4) по полученным оценкам местоположений.

Ниже рассмотрены оба этапа подробнее. Оценка местоположения ТС в конкретные моменты времени

Суть решения заключается в проецировании данных (1) на граф УДС с учётом ограничений, налагаемых поступательным и/или маршрутным движением ТС.

Как было указано ранее, для каждого маршрутного ОТС с условным номером 1 считается известным либо единственный маршрут движения И^), либо два альтернативных маршрута движения Ищ() и Ищ(1у Для краткости изложения ниже представлен один из трёх предложенных алгоритмов, соответствующий простейшей ситуации с наличием одного маршрута.

Алгоритм для случая единственного маршрута Wm

1. При поступлении очередной '-й координаты для 1-го маршрутного ОТС (р0 *), р1 (')) определя-

ется ближайший по расположению сегмент маршрута и относительное положение на нём как решение следующей задачи:

(w,t) = arg mrn[( p0 (j)-<(t))2 + (P (ty)-< (t))2).

xe[0,l]

Если расстояние

P = J( P (tj)-xw (t))2 + (p (tj)-XW (t))2

превышает некоторое пороговое значение рс, то считается, что ОТС находится не на маршруте и его точное местоположение не определено с текущего момента. В приводимых далее экспериментах используется рс=10 м.

2. Вычисляется расстояние г по маршруту следования от его начала - узла графа с координатами

Xw (0) - до найденного положения на сегменте

xw(t) .

3. Если (j = 1) или (j> 1 и г > г,ч), то считаем сегмент и относительное положение на нём определённым верно, то есть за оценку очередного положения ОТС принимаем следующую величину:

(P (tj), P (tj )) = (xW(t), xW(t)).

4. Если ] > 1 и г < г,ч, то

- если для трёх подряд полученных координат ОТС не выполняется условие г > /}ч, считаем, что ОТС находится не на маршруте («сошло» с маршрута) и его точное местоположение не определено;

- в противном случае за оценку местоположения принимается оценка предыдущей координаты

(р (0), р (^)) = (р (^ -1), р (^)).

Оценка параметров транспортных потоков по актуальным данным

Динамическая (привязанная ко времени) оценка параметров транспортного потока может быть получена по информации о положении отдельных транспортных средств (р (^), р ))1еЗ . Для удобства

jе N

дальнейшего изложения определим величины ш(4Д х (1,j), значения которых определим из условия выполнения следующих равенств:

X*Л(х(1, j)) = р (tj), Л(х(;, j )) = р (^).

Способ получения оценки уЩ[те(0 времени прохождения дуги/сегмента ш по величинам ш(1, j), х (1, j) описан в нашей предшествующей работе [8]. Эта величина позволяет также получить оценку скорости потока на соответствующем сегменте по очевидной формуле:

speed

(t ) = -

,(t)"

Оценка двух оставшихся параметров может быть задана следующими выражениями:

- плотность потока (Ь - число полос движения):

density

(t ) = k

\i еЗ : $j e N |

[ j < t)A(tj > t)A( w(i, j)= w)j

L\W

- поток (число ТС в единицу времени, Т- интервал наблюдения):

УЩ,ош ^) =

1 еЗ : (ш (1, j) ф ш) л (ш (1, j + У) = ш) л

л(0 < t)л(^+j е t + Т])л]е N

= к - '

Т

В приведённых выражениях величина к > 1 - эмпирически подобранный коэффициент пропорциональности, определяющий отношение общего числа ТС к числу ТС с датчиками ОРБ/ГДОНАСС.

Общая схема предлагаемого метода

Общее описание предлагаемого метода, представляющее его основные компоненты и идеи, но не детализирующее его до математической модели и алгоритмов, представлено ниже. Мы также предполагаем, что предварительная обработка, описанная в предыдущем разделе и заключающаяся в оценке актуальных параметров транспортных потоков по данным ОРБ/ГДОНАСС-наблюдений, выполнена, а входная актуальная и исторически доступная (архивная) информация для метода представлена в виде наборов значений параметра ТП для всех сегментов сети (4):

у( ш, ^, ше I = £ - пД(п = 0,1,...),

здесь t - текущий момент времени. Выходной информацией метода являются краткосрочные прогнозные значения параметра ТП для всех сегментов сети:

у(ш, (), ше ' , I = t* + пД (п = 1, Щ .

Предлагаемый метод состоит из следующих этапов:

- разбиение графа УДС на пересекающиеся подграфы по территориальному признаку и формирование вектора признаков (вектора значений параметров потоков) по каждому из них;

- вычисление размерности вектора признаков для каждого подграфа путём устранения пространственно-временной зависимости значений параметров потоков;

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

сформирован по причине финитности выбранных ядер. Эта ситуация используется на следующем этапе предлагаемого метода как дополнительная (управляющая) информация. Во втором варианте используется элементарный прогноз, основанный на методе опорных векторов - SVM (support vector machine). В третьем варианте используются элементарные прогнозы, основанные на классических скалярных и векторных моделях временных рядов Бокса-Дженкинса. Результатом работы каждого элементарного прогноза является прогнозный вектор параметров потоков сети или (для первого варианта) указание на невозможность построения прогноза;

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

- расчёт окончательных значений прогнозных параметров транспортных потоков всей УДС в виде линейной комбинации прогнозов для всех подграфов УДС. В данном случае изменениям (усреднениям) подвергаются только те параметры, которые соответствуют сегментам УДС (рёбрам графа), попавшим одновременно в несколько подграфов.

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

Представление графа сети с использованием подграфов. Вектор признаков подграфа

Выбираемый способ разбиения графа УДС на подграфы должен удовлетворять ряду плохо формализуемых требований, которые условно могут быть сформулированы следующим образом:

- способ должен быть регулярным;

- подграфы УДС должны быть связными;

- подграфы УДС должны быть примерно одинакового размера (по количеству рёбер и по размеру занимаемой площади);

- набор сегментов УДС, попадающих в подграфы, должен быть «компактно» расположен (то есть территориально близко);

- число рёбер в подграфах не должно быть малым -для реальных графов УДС оно должно составлять от нескольких десятков до нескольких сотен;

- простота введения меры территориальной близости между двумя подграфами УДС (используется в последующих разделах).

Учитывая приведённые выше требования, предлагается следующий способ представления графа УДС с использованием подграфов.

Выбирается число формируемых подграфов в количестве К0, К, и в подграф с номером к = к0К1 + к1 (к0 = О, К0 -1; к1 = О, К1 -1), обозначаемый ниже Wk, относятся те дуги из множества W, координаты одной из вершин которых попадают в соответствующую прямоугольную область П^^ :

^^ко к е W: ^ (0)е П ^ V х' (1)еП ко,,} ,

где Пк0,к1 °

хг1п+к

K

mm + ( ™х _ и™ ) , X™ + АН ( x™ - xT* ) 1 KV 1 1,1 Kl 1 1 1

xmiin = min

s C=o:

n xw(z), xm-=ma^ xw(z), s=0,1.

Число подграфов по вертикали и горизонтали К0, К1 выбирается эмпирически, но так, чтобы удовлетворять требованию по числу рёбер.

Каждый получаемый подграф Wk УДС для дальнейшей обработки представляется в виде своего описания - вектора признаков, характеризующего потоки подграфа в конкретный момент времени. Формирование указанного вектора признаков производится следующим образом.

Пусть {'-1 - набор рёбер конкретного выбранного подграфа Wk в количестве Бк штук, упорядоченный определённым образом (способ упорядочивания значения не имеет). Тогда вектор признаков, используемый в качестве описателя этого подграфа, имеет вид:

M (t ) =

(v («О, t),

, v (w0, t _ MA),..., v (

W^ -1,t _

Ma))7

здесь М> 1 - число используемых в векторе признаков архивных значений параметров ТП для каждого сегмента сети. Для удобства дальнейшего изложения процесс получения описания для конкретного подграфа запишем в виде операции проекции:

'(')= Vm (t)|W

k = 0, K _ 1.

Снижение размерности описания подграфа УДС с учётом пространственной и временной избыточности данных о потоках

Представление состояния подграфа сети в виде вектора признаков (5) обладает существенной информационной избыточностью. Прямое подтвержде-

х

и

vk

ние информационной избыточности по отношению к пространственному распределению ТП (то есть избыточности представления подграфа в виде вектора текущих значений параметров ТП v0k (t)) дано в работе [24], где отмечено, что объём основной информации о распределении ТП составляет не более 10 % от объёма данных в сети. Другим, но косвенным подтверждением того же тезиса о наличии значительной избыточности в данных является использование вычислительных процедур распределения транспортных потоков в статических и динамических сетях на основании матрицы корреспонденции существенно меньшего (чем количество сегментов в УДС) размера [4, 7, 25 - 27]. Как уже было замечено ранее, избыточность данных (в отношении пространственного распределения ТП) явно и косвенно была использована в ряде работ [19, 21 - 23]. Ниже мы предлагаем решение, которое для снижения размерности вектора описания ситуации использует как информационную избыточность, связанную с информацией о пространственном распределении ТП, так и избыточность, связанную с информацией о временном распределении ТП. В известных авторам работах такой подход не рассматривался.

Предлагаемый способ снижения размерности заключается в переходе от исходного представления (5) к сокращённому представлению с использованием небольшого числа компонент, получаемых с использованием метода главных компонент (PCA - Principal Component Analysis) [29].

В контексте данной работы метод PCA состоит из следующих шагов (выполняется для каждого подграфа Wk УДС отдельно):

1. Вычисляется оценка ковариационной матрицы векторов признаков vM(t) (реализации вектора

соответствуют N временным моментам в прошлом):

1 N-1 T

C = i X

N n=0

1 N-1

где средний вектор vk = — X vM (t -An).

N n=0

2. Вычисляются собственные значения А^ , ...,А k и

собственные векторы ковариационной матрицы Производится их упорядочивание так, что

Ak >А2 >... ^Ksk > 0.

3. Вычисляется квадрат относительной ошибки представления вектора (5) заданным числом главных компонент как отношение остаточной дисперсии к выборочной дисперсии:

X А

d2 = l=r +1

k,r MSk

X A

По относительной ошибке 5кг выбирается число Я главных компонент, обеспечивающих требуемую точность представления 82Лге1ЬоИ.

4. Формируется матрица главных компонент Мк размера МБк * Я из собственных векторов ковариационной матрицы Ск, соответствующих первым Я собственным числам.

5. Вычисляется новый вектор признаков со сниженной размерностью как проекция исходного вектора признаков на главные компоненты:

JM (t ) = ( Mk )T vM (t).

Результатом работы метода снижения размерности оказывается вектор JM (0, состоящий из Я (Я<MSk) компонент, которые совокупно характеризуют текущее состояние (с предысторией на M отсчётов по времени) подграфа Wk УДС в конкретный момент времени t.

Полученный вектор описания JM (t) вместе с исходным vM (t) описанием подграфа УДС используются для построения набора элементарных прогнозов.

Алгоритмы прогнозирования транспортных потоков с использованием временных рядов

Решение задачи прогнозирования транспортных потоков с использованием временных рядов обычно производится с использованием одной из следующих моделей:

- интегрированная модель авторегрессии скользящего среднего (ARIMA) и её модификация с учётом сезонных компонент - сезонная модель ARIMA [15];

- векторная модель VARMA [16];

- пространственно-временная модель STARMA [17]. В настоящей работе для построения отдельных

элементарных прогнозов и исследования их эффективности были использованы сезонная модель ARIMA и векторная модель VARMA.

Результат прогнозирования, получаемый при применении одного из представленных выше методов прогнозирования временных рядов для всех сегментов в конкретном k-м подграфе сети, будем в дальнейшем обозначать следующим образом:

v0k (t + лА) = TS(k,M, t, лА).

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

Среди методов машинного обучения для решения задачи кратковременного прогнозирования транспортных потоков обычно используются следующие методы и алгоритмы:

- алгоритм линейной регрессии [12];

- регрессия методом опорных векторов (Support Vector Regression - SVR) [21, 22];

- метод потенциальных функций [12, 30];

i=1

- метод ближайших соседей [13];

- нейронные сети [18 - 20].

В настоящей работе для построения отдельных элементарных прогнозов и исследования их эффективности были использованы метод опорных векторов и метод потенциальных функций.

Результат прогнозирования, получаемый в результате применения метода БУК для всех сегментов в конкретном 1-м подграфе сети, будем в дальнейшем обозначать следующим образом:

VI (С + лД) = SVR(к,M, 4 лД).

Метод потенциальных функций Метод потенциальных функций позволяет прогнозировать значения параметров ТП с учётом близости векторов описания $М (0 в разные моменты времени. Общее соотношение, характеризующее вычислительную процедуру получения прогнозного значения, для нашей задачи имеет вид (значение «0» в приводимой ниже формуле соответствует факту, что результат прогноза не определён/отсутствует):

уЦ (с + лД) = РРа (1, М, С, лД) °

N1-1 _ _

X VI

N —1 ___

X

0,

где R0 ($М (0, $М((- тД)) - ядро формируемой оценки, монотонно убывающее по мере увеличения расхождения между векторами $М (0, (С- тД). В работе предлагается использовать следующую функцию, которая учитывает близость векторов описания не только в том же подграфе, в котором строится прогноз, но и в «соседних» к 1-му Н подграфах:

R0(JM ('), < (' - тД)) =

1

а72я

0,

ехр

¿2 ) '

Р > 4а,

где

Р = II^М (0-#М (тД)| +

+ Н XX ^М (' )-5М (' - тД) .

н ь=0

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

В выбранном варианте использования - с финитным ядром (10) - (11) - метод потенциальных функций имеет специфику: при малых значениях параметра а может быть формально получен результат со значением, обозначенным символом «0», то есть результат отсутствует. Такая ситуация возникает, если для текущего состояния сети в исторических данных не окажется ни одного близкого прототипа. В предлагаемом решении эта ситуация используется для построения адаптивной вычислительной процедуры агрегации элементарных прогнозов, описание которой приведено ниже.

N-1 ___

X Rа(Jkм (С), < (С - тД)) > 0,

т=0

N-1 _ _

X Rа(Jkм (С), < (С - тД)) = 0,

Алгоритм адаптивной линейной композиции элементарных прогнозов

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

Пусть {ад }(=0 (ад е Я+) - монотонно убывающая

последовательность чисел: ад >ад+1 (д = 0, (- 2). Учитывая вид соотношений (10) - (11), очевидны следующие утверждения:

Rаq (£М (О,(С- тД)) = 0 ^ ^ Rа^+1 (< (О,< ('- тД)) = 0,

(1, м, С, лД)=0 ^ рр (1, М, С, лД)=0.

Тогда при ( выбранных для метода потенциальных функций ядер с различными {ад }(=0, удовлетворяющими указанному выше ограничению, возможны всего ((+ 1) различных ситуаций, когда отдельные прогнозы дают определённые/неопределённые значения.

Идея метода адаптивной линейной композиции элементарных прогнозов заключается в построении независимых линейных комбинаций элементарных прогнозов (линейной регрессии элементарных прогнозов) для каждой из ((( +1) возможных ситуаций.

Предлагаемый вариант адаптивной композиции может быть формально представлен в следующем виде:

т=0

т=0

т=0

Ук {(+м) =

а0 TS (к, M, г, пД ) + а0 SVR (к, M, г, пА) ,

PF0o ( к, M, г, пД) = 0, аДО (к, M, г, пД) + afSVR (к, M, г, пД) +

+ Xа0+2PFO0 (к,М, г,пД),

0=0

0 = 1 + ате тах (Р/;, (к,М,г,пД)^0).

о=о, о-Л °° !

В представленной адаптивной линейной комбинации настройка требуется для следующего набора вещественных коэффициентов {а0 }^=оо

0=0,9+1

Вычислительная процедура расчёта прогнозных параметров транспортных потоков

Заключительным этапом предлагаемого метода является расчёт прогнозных параметров транспортных потоков для графа всей УДС как линейной комбинации прогнозных данных (12) для подграфов. Данная операция оказывается необходимой, поскольку для некоторых из сегментов, попавших одновременно в несколько подграфов, существует несколько прогнозных значений. Искомое прогнозное значение ш, г) параметра ТП для сегмента ш в момент времени г предлагается вычислять по следующей формуле:

X V/ (г )|, У (ш, г ) = £-

где у0 (г) - значение параметра ТП на конкретном

0 I ш

сегменте ш, полученное для к-го подграфа:

у (И, г),

УК (г ),=

ш = шг е Wk;

0,

иначе.

Значение, как видно из формулы, полагается нулевым, если сегмент не входит в конкретный подграф.

Значение У0к (г) играет роль индикатора вхождения сегмента в конкретный подграф и определяется по формуле:

У0К

1,

ш = шг е Wk;

0, иначе.

Настройка модели адаптивной линейной композиции элементарных прогнозов

Математическая модель краткосрочного прогнозирования параметров ТП, представленная в предыдущем разделе, определена с точностью до набора параметров. Параметры можно условно разбить на две группы: параметры, определяемые пользователем или постановкой задачи, и параметры модели и входящих в её состав алгоритмов/методов, которые не-

обходимо идентифицировать по историческим данным состояний УДС. Описание метода выбора порядка и настройки параметров модели временных рядов представлено в монографии [14] и для краткости изложения здесь не приводится. По той же причине мы опускаем описание идентификации коэффициентов для метода опорных векторов. Наконец, способ получения коэффициентов адаптивной линейной комбинации сводится к независимому решению задач идентификации коэффициентов для обычной линейной регрессии, выполняемой методом наименьших квадратов (МНК), в количестве (О + 1) штук. Каждая из указанных МНК-задач сводится в конечном итоге к решению системы нормальных уравнений, явный вид которой известен из теории оценивания и здесь для краткости изложения также не приводится.

Экспериментальные исследования

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

Эксперимент 1. Оценка эффективности предлагаемой адаптивной композиции и сравнение её с качеством отдельных алгоритмов.

Эксперимент 2. Определение зависимости времени работы предлагаемой адаптивной композиции от числа главных компонент, используемых в методе РСА, для описания вектора пространственно-временного распределения потоков.

Экспериментальные исследования разработанного метода проводились для УДС г. Самары. Дорожная сеть состоит из 3387 сегментов. Количество ОТС, подключённых к системе мониторинга, - более 1500, новые координаты положения ОТС поступают с усреднённой периодичностью в 30 секунд. Подробнее система мониторинга движения описана в работе [8].

Для экспериментальных исследований производилось разбиение графа дорожной сети на подграфы по территории размером 1 км2. Каждый подграф содержал в среднем 50 дуг. Число используемых в векторе признаков архивных значений параметров ТП для каждого сегмента сети М= 6, значение временного интервала А = 10 минут, т.е. вектор признаков содержит архивные данные за последний час. Пересчёт новых значений параметров ТП проводился раз в 10 минут.

Ниже представлены результаты экспериментов.

Эксперимент 1. Оценка эффективности

В рамках этого направления исследовалась зависимость величины средней абсолютной и средней относительной ошибок прогнозных значений параметров ТП для предлагаемого метода адаптивной композиции и отдельных алгоритмов прогнозирования, входящих в состав его модели, от горизонта прогноза. Для простоты анализа результата далее представлены результаты анализа для одного подграфа УДС. В качестве элементарных прогнозов использовались прогнозы методом опорных векторов (на графиках - БУК), моделью временных рядов УАКМА (на графиках - ТБ), методом потенциальных функций с наибольшим значением

к=0

о(РГ(0)), дающим результат прогноза для всех участков УДС, и МПФ с наименьшим значением о(РГ(4)), дающим результат прогноза примерно в 20 % случаев.

Исследование качества прогнозов проводилось на выборке, состоящей из значений параметров ТП на дорожных сегментах за 12 будних дней. Исследование проводилось методом перекрёстной проверки, размер одной части контрольной выборки составлял один день. График зависимости средней абсолютной ошибки от горизонта прогноза на контрольной выборке показан на рис. 1, средней относительной ошибки на контрольной выборке - на рис. 2.

Средняя абсолютная ошибка, с

140 120

100 80 60* 40 20 0

Hi--SVR "О...... TS

-A—PF

-Композиция

10

20

30 40 50 60 Горизонт прогноза, мин

Рис. 1. Зависимость средней абсолютной ошибки

от горизонта прогноза на контрольной выборке

Средняя относительная ошибка

0,05

0

--SVR О...... TS

-А— PF

-Композиция

10

20

30 40 50 60 Горизонт прогноза, мин

Рис. 2. Зависимость средней относительной ошибки от горизонта прогноза на контрольной выборке

Из представленных результатов видно, что модель адаптивной композиции даёт более качественный результат практически на всём горизонте прогноза.

Более детальный анализ результатов показал, что наибольший вклад в величины ошибок вносят те моменты состояния УДС, которые соответствуют заторам на сегменте. Данный факт делает актуальным разработку как способов предварительной фильтрации данных для обучения и оценки эффективности методов, что используется в некоторых существующих работах [9, 12], так и собственно методов «обнаружения» подобных ситуаций с последующим изменением метода прогнозирования.

Эксперимент 2. Определение зависимости времени расчёта прогноза от числа главных компонент В этом эксперименте исследовалась зависимость времени работы предлагаемой адаптивной композиции алгоритмов от числа используемых главных ком-

понент, обеспечивающих необходимую точность представления исходных данных. График зависимости времени работы от относительного числа оставленных в представлении вектора признаков параметров ТП показан на рис. 3. В эксперименте прогнозировалось значение параметров ТП в одном подграфе для 438 дорожных сегментов при горизонте прогноза 1 час. Характеристики используемой ПЭВМ: процессор Intel Core i5-3740 3.20 GHz, оперативная память -8 ГБ, жёсткий диск - 1 ТБ, ОС - Windows 8.1.

Время работы, с

300 250 200 150 100 50

Г

0 50 100 150 200 250 300

Число компонент

Рис. 3. Зависимость времени работы от числа оставленных компонент

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

Выводы

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

В исследованиях, проведённых по данным движения городского пассажирского транспорта в г. Самаре, предложенный алгоритм прогнозирования показал лучший результат по сравнению с отдельными алгоритмами, используемыми для краткосрочного прогнозирования транспортных потоков: моделями ARIMA и VARMA, методом SVR, методом потенциальных функций.

Учитывая, что предложенный алгоритм адаптивной композиции обладает свойствами, которые совместно не присущи ни одному из представленных в литературе, а именно:

- позволяет формировать прогноз одновременно для всей УДС города;

- использует в качестве источников данных информацию от отдельных ТС (данные GPS/ГЛОНАСС), а не информацию от датчиков трафика;

- учитывает пространственно-временную избыточность данных о ТП на анализируемой УДС;

- обладает адаптивностью по отношению к анализируемой ситуации на графе УДС;

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

Дальнейшие направления работ включают в себя:

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

- исследования, связанные с разработкой методов «обнаружения заторов» с последующим изменением алгоритма(ов) прогнозирования;

- исследования, связанные с анализом эффективности отдельных алгоритмов прогнозирования, не рассмотренных в настоящей работе.

Благодарности

Работа выполнена при поддержке:

- Министерства образования и науки РФ в рамках реализации мероприятий Программы повышения конкурентоспособности СГАУ среди ведущих мировых научно-образовательных центров на 20132020 годы;

- грантов РФФИ, проекты № 13-07-12103-офи-м, 13-01-12080-офи-м, 12-07-00021 -а;

- программы фундаментальных исследований Президиума РАН «Фундаментальные проблемы информатики и информационных технологий», проект 2.12;

- Министерства образования и науки Российской Федерации (в рамках постановления Правительства Российской Федерации от 09.04.2010 г. № 218: договор № 02.Г36.31.0001 от 12.02.2013).

Литература

1. Klein, L.A. Traffic Detector Handbook / L.A. Klein, D.R. Gibson, M.K. Mills // Federal Highway Administration, Turner-Fairbank Highway Research Center. - 2006. - 687p.

2. Batty, M. Smart cities of the future / M. Batty, K.W. Axhausen,

F. Giannotti, A. Pozdnoukhov, A. Bazzani, M. Wachowicz,

G. Ouzounis, Y. Portugali // The European Physical Journal Special Topics. - 2012. - Vol. 214, Issue 1. - P. 481-518.

3. Directive 2010/40/EU of the European Parliament and of the Council of 7 July 2010 on the framework for the deployment of Intelligent Transport Systems in the field of road transport and for interfaces with other modes of transport / Legislative acts // Official Journal of the European Union. - 2010. - P. 1-13.

4. Hall, R. Handbook of transportation science / R.W. Hall. -Dordrecht: Kluwer Academic Publishers, 2003. - 737 p.

5. Liu, X. Dynamic Graph Shortest Path Algorithm / X. Liu,

H. Wang // Web-Age Information Management: Lecture Notes in Computer Science. - 2012. - Vol. 7418. - P. 296-307.

6. Polychronopolulos, G. Stochastic shortest path problems with recourse / G. Polychronopolulos, J. Tsitsiklis // Networks. - 1996. - Vol. 27, Issue 2. - P. 133-143.

7. Hoogendoorn, S.P. State-of-the-art of vehicular traffic flow modeling / S.P. Hoogendoorn, P.H.L. Bovy / Proceedings of the Institution of Mechanical Engineers. Part I: Journal of Systems and Control Engineering. - 2001. - Vol. 215(4). -P. 283-303.

8. Агафонов, А.А. Алгоритм оценки времени прибытия общественного транспорта с использованием адаптив-

ной композиции элементарных прогнозов / А.А. Агафонов, В.В. Мясников // Компьютерная оптика. -2014. - Т. 38, № 2. - С. 356-369.

9. Vlahogianni, E.I. Short-term traffic forecasting: Where we are and where we're going / E.I. Vlahogianni, M.G. Kar-laftis, J.C. Golias // Transportation Research Part C: Emerging Technologies. - 2014. - Vol. 43, Part 1. - P. 3-19.

10. Bolshinsky, E. Traffic Flow Forecast Survey / E. Bolshin-sky, R. Freidman // Technion - Israel Institute of Technology. - 2012. - Technical Report. - 15 p.

11. Faouzi, N.E. Data fusion in intelligent transportation systems: Progress and challenges / N.E. Faouzi, H. Leung, A. Kurian // A survey, Information Fusion. - 2011. -Vol. 12, Issue 1. - P. 4-10.

12. Sun, H. Short term traffic forecasting using the local linear regression model / H. Sun, H. Liu, H. Xiao, R. He, B. Ran // Journal of Transportation Research Board. - 2003. -Vol. 1836. - P. 143-150.

13. Oswald, R. Traffic flow forecasting using approximate nearest neighbor nonparametric regression / R. Oswald, T. Scherer, B.L. Smith // The National ITS Implementation Research Center U.S. DOT University Transportation Center. - 2001. - Research Report. - 115 p.

14. Box, G.E. Time Series Analysis: Forecasting and Control / G.E. Box, G.M. Jenkins, G.C. Reinsel. - 4th edition. - Wiley, 2008. - 784 p.

15. Mai, T. Short-term traffic flow forecasting using dynamic linear models / T. Mai, B. Ghosh, S. Wilson // Irish Transport Research Network. - 2011.

16. Stathopoulos, A. A multivariate state space approach for urban traffic flow modeling and prediction / A. Stathopou-los, M.G. Karlaftis // Transportation Research Part C: Emerging Technologies. - 2003. - Vol. 11, Issue 2. -P. 121-135.

17. Lin, S.-H. The application of space-time ARIMA model on traffic flow forecasting / S.-H. Lin, H.-Q. Huang, D.-Q. Zhu, T.-Z. Wang // Machine Learning and Cybernetics, 2009 International Conference on. - 2009. - Vol. 6. - P. 3408-3412.

18. Min, W. Real-time road traffic prediction with spatiotemporal correlations / W. Min, L. Wynter // Transportation Research Part C: Emerging Technologies. - 2011. -Vol. 19, Issue 4. - P. 606-616.

19. Zheng, W. Short-term freeway traffic flow prediction: bayesian combined neural network approach / W. Zheng, D.-H. Lee, Q. Shi // Journal of Transportation Engineering. - 2006. - Vol. 132, N 2. - P. 114-121.

20. Zhang, X. Forecasting Approach for Short-term Traffic Flow based on Principal Component Analysis and Combined Neural Network / X. Zhang, G. He // Systems Engineering: Theory & Practice. - 2007. - Vol. 27(8). - P. 167-171.

21. Guorong, G. Traffic Flow Forecasting based on PCA and Wavelet Neural Network / G. Guorong, L. Yanping // Information Science and Management Engineering (ISME). -2010. - Vol. 1. - P. 158-161.

22. Jin, X. Simultaneously Prediction of Network Traffic Flow Based on PCA-SVR / X. Jin, Y. Zhang, D. Yao // Lecture Notes in Computer Science. - 2007. - Vol. 4492. - P. 1022-1031.

23. Как устроен краткосрочный прогноз на Яндекс.Пробки. -http://habrahabr.ru/company/yandex/blog/153631/ (How does the short-term forecast Yandex.Traffic. - http://habra-habr.ru/company/yandex/blog/153631/ - (In Russian)).

24. Lakhina, A. Structural analysis of network traffic flows / A. Lakhina, K. Papagiannaki, M. Crovella, C. Diot, E.D. Ko-laczyk, N. Taft // ACM SIGMETRICS Performance Evaluation Review. - 2004. - Vol. 32, Issue 1. - P. 61-72.

25. Введение в математическое моделирование транспортных потоков / А.В. Гасников, С.Л. Кленов, Е.А. Нур-

минский, Я.А. Холодов, Н.Б. Шамрай; под ред. А.В. Гасникова. - М.: МФТИ, 2010. - 362 с.

26. Швецов, В.И. Математическое моделирование транспортных потоков / В.И. Швецов // Автоматика и телемеханика. - 2003. - № 11. - P. 3-46.

27. Cascetta, E. Transportation Systems Analysis: Models and Applications / E. Cascetta. - New York: Springer, 2009. -752 p.

28. Копенков, В.Н. Оценка параметров транспортного потока на основе анализа данных видеорегистрации / В.Н. Копенков, В.В. Мясников // Компьютерная оптика. - 2014. -Т. 38, № 1. - С. 81-86. (Kopenkov, V.N. The estimation of the traffic flow parameters based on the videoregistration data analysis // V.N. Kopenkov, V.V. Myasnikov // Computer Optics. - 2014. - Vol. 38(1). - P. 81-86).

29. Jolliffe, IT. Principal Component Analysis / I.T. Jolliffe. -2nd edition. - New York: Springer, 2002. - 487 p.

30. Айзерман, М.А. Метод потенциальных функций в теории обучения машин / М.А. Айзерман, Э.М. Браверман, Л.И. Ро-зоноэр. - М.: Наука, 1970. - 384 с.

AN ALGORITHM FOR TRAFFIC FLOW PARAMETERS ESTIMATION AND PREDICTION USING COMPOSITION OF MACHINE LEARNING METHODS AND TIME SERIES MODELS

A.A. Agafonov, V. V. Myasnikov Image Processing Systems Institute, Russian Academy of Sciences, Samara State Aerospace University

Abstract

A problem of traffic flow analysis and prediction in city transport network is considered in this paper. The proposed algorithm uses GPS / GLONASS data of public transport location as input. Projecting this information on a transport network graph, as well as using additional filtering, we estimate traffic flow parameters. These parameters are used for short-term (up to 1 hour) prediction of road conditions in the city transport network. There is proposed a new method which consists of several steps to construct prediction. First, the transport graph is divided into a number of subgraphs by a territorial basis. Second, we use a dimension reduction method based on principal components analysis to describe the spatio-temporal distribution of traffic flow condition in the subgraphs. Third, an elementary prediction for each of the subgraphs is formed using the potential functions method with the measure of the subgraphs descriptions closeness introduced by analogy with bilateral filtering and support vector machine. Fourth, the additional elementary prediction is calculated using the known scalar and vector Box-Jenkins time series prediction models. Fifth, we construct the result prediction for each of the subgraphs using an adaptive linear composition of elementary predictions. At last, the traffic flow parameters are calculated as a linear combination of predictions for subgraphs of the city transport network. We have also made experimental investigations of transport network in Samara to evaluate the prediction accuracy of the proposed algorithm. The advantages of the proposed solution in comparison with existing ones are provided.

Key words: transport network, traffic flow, traffic flow estimation, traffic flow prediction, algorithms composition, potential functions method, Box-Jenkins model, SVR.

Сведения об авторах Агафонов Антон Александрович, 1988 года рождения. В 2011 году окончил Самарский государственный аэрокосмический университет (СГАУ). В настоящее время работает стажёром-исследователем в Федеральном государственном бюджетном учреждении науки Институт систем обработки изображений РАН и по совместительству инженером-математиком в ОАО «Самара-Информспутник». Круг научных интересов включает геоинформационные технологии, веб-технологии. Имеет 5 публикации, из них 2 статьи. E-mail: ant.agafonov@gmail.com .

Anton Aleksandrovich Agafonov (1988 b.), graduated from Samara State Aerospace University (SSAU) at 2011. At present he is intern-researcher at the Image Processing Systems Institute of the Russian Academy of Sciences, holding a part-time positions of engineer-mathematician at JSC "Samara-Informsputnik". The area of interests includes geoinformatics and web-technologies. He's list of publications contains 5 publications, including 2 scientific papers.

Сведения об авторе Мясников Владислав Валерьевич - см. стр. 493 этого номера.

Поступила в редакцию 17 июня 2014 г.