Сравнение временных рядов при авторегрессионном прогнозе (пример)

Материал из MachineLearning.

(Различия между версиями)

Текущая версия

Содержание

1 Аннотация
2 Постановка задачи
3 Алгоритм
4 Вычислительный эксперимент
- 4.1 Пример на реальных данных
- 4.2 Пример на сгенерированных данных
5 Исходный код
6 Литература

Аннотация

Данная работа посвящена исследованию зависимости между пространственными характеристиками (форма, период) временного ряда^[1] и распределением параметров регрессионных моделей, которые описывают эти временные ряды. Один из подходов исследовать данную зависимость - посмотреть, как распределены параметры моделей для похожих в некотором смысле временных рядов, и насколько эти распределения различаются для непохожих (различных в некотором смысле) временных рядов.

Постановка задачи

Временным рядом называется последовательность упорядоченных по времени значений некоторой вещественной переменной $\mathbf{x}=\{x_{t}\}_{t=1}^T\in\mathbb{R}^T$ . Элемент последовательности называется отсчетом временного ряда.

Задача авторегрессионного прогноза заключается в нахождении модели $f(\mathbf{x}, \mathbf{w})$ , где $\mathbf{w}\in\mathbb{R}^M$ вектор параметров модели, которая наилучшим образом приближает следущее значение временного ряда $x_{T+1}:\widehat{x}_{T+1}=f(\mathbf{x}, \mathbf{w})$ .

Пусть задан временной ряд $\mathbf{x}=\{x_{t}\}_{t=1}^T\in\mathbb{R}^T$ . Предполагается, что отсчеты $t=1,\dots, T$ были сделаны через равные промежутки времени, и период временного ряда равен $p$ , при этом ${T}+1=p\cdot{n}$ , где $n\in\mathbb{N}$ . Задана модель $\mathbf{x}=f(\mathbf{x}, w)+\epsilon$ ,где случайная величина $\mathbf{\varepsilon}$ имеет нормальное распределение $\mathbf{\varepsilon} \in N(0, \sigma^2)$ . Вектор параметров модели $\mathbf{w}$ рассматривается как многомерная случайная величина. Пусть плотность распределения параметров имеет вид многомерного нормального распределения $N(\mathbf{0}, A)$ с матрицей ковариации $A$ . Модель некоторым образом учитывает период временного ряда. Предполагается, модель временного ряда может меняться с течением времени, т.е. для разных подпоследовательностей длины $p$ оптимальные параметры модели $\mathbf{x}=f(\mathbf{x}, w)+\epsilon$ будут отличаться.

Расстояние между временными рядами

Расстояние между различными подпоследовательностями $x_{n_1\cdot{p}+1},\dots,x_{(n_1+1)\cdot{p}}$ и $x_{n_2\cdot{p}+1},\dots,x_{(n_2+1)\cdot{p}}$ можно вычислить как сумму квадратов отклонений:

$SSE=\sum_{i=1}^p{(x_{n_2{p}+i}-x_{n_1{p}+i})^2}.$

Однако этот метод учитывает только расстояния между парами отсчетов временного ряда. Метод поиска пути минимальной стоимости (warping path)^[1] учитывает не только расстояние между отсчетами рядов, но и форму самих временных рядов.

Предположим, мы имеем две последовательности $\mathbf{x}= \{x_{1},\dots,x_{n}\}\in\mathbb{R}^n$ и $\mathbf{y}= \{y_{1},\dots,y_{m}\}\in\mathbb{R}^m$ . Тогда построим матрицу $n\times m$ попарных расстояний:

$\Omega=\|\omega_{i,j}\|_{i=1,j=1}^{n, m}=\|(x_i-x_j)^2\|_{i=1,j=1}^{n, m}.$

Далее из элементов матрицы $\Omega$ строим путь:

$\{s_1, \dots, s_C\}=\{\omega_{i_1,j_1}, \dots, \omega_{i_{n_C}, j_{m_C}}\}.$

Построенный путь удовлетворяет следующим условиям:

'1 граничные условия:' $s_1 = \omega_{1,1},~ s_C = \omega_{n,m}$ ; '2) непрерывность:' если~ $s_k = \omega_{i,j},~ s_{k-1} = \omega_{i',j'}$ , тогда $i-i'\leq 1,~ j-j'\leq 1$ ; '3) монотонность:' если~ $s_k = \omega_{i,j},~ s_{k-1} = \omega_{i',j'}$ , тогда $i-i'\geq 0,~j-j'\geq 0$ .

Стоимостью пути $\{s_1, \dots, s_C\}$ будет

$<tex>D\left(\{s_1, \dots, s_C\}\right)=\frac{\sqrt{\sum_{c=1}^C{s_c}}}{C}.$

Среди всех путей есть по крайней мере один с минимальной стоимостью. Его стоимость и будем считать расстоянием между последовательностями:

$DTW(\mathbf{x},\mathbf{y}) = \min\limits_{\{s_1, \dots, s_C\}}D\left(\{s_1, \dots, s_C\}\right).$

Алгоритм поиска пути минимальной стоимости рекурсивно находит длину пути наименьшей стоимости $\gamma_{i,j}$ до каждого элемента матрицы $\Omeg$ :

$\gamma_{i,j} = \omega_{i,j}+\min(\gamma_{i,j-1}, \gamma_{i-1,j}, \gamma{i-1, j-1}).$

Расстояние между параметрами модели

Расстояние между параметрами модели $\mathbf{x}=f(\mathbf{x}, \mathbb{w})+\epsilon$ , настроенной на разных подпоследовательностях, можно измерить как расстояние Кульбака-Лейблера между функциями распределения 2-ух случайных величин ${p(w)},{q(w)}$ :

$D_{KL}(p, q) = \sum\limits_{w\in \mathcal{W}} p(w) \ln \frac{p(w)}{q(w)}.$

Постановка задачи

Требуется исследовать зависимость расстояния между параметрами модели $\mathbf{x}=f(\mathbf{x}, w)+\epsilon$ от расстояния между подпоследовательностями, на которых эти параметры были настроены.

Алгоритм

Для настройки параметров модели $f(\mathbf{x}, \mathbf{w})+\epsilon$ используется связный байесовский вывод

$\ln p(D|\beta, A)=-\frac{1}{2}\ln|A|-\frac{N}{2}\ln2\pi+\frac{N}{2}\ln\beta-S(\mathbf{w_0})-\frac{1}{2}\ln|H|,$

где $S(\mathbf{w})=\frac{1}{2}\mathbf{w}^TA\mathbf{w}+\beta E_D$ — функция ошибки,

$H=-\nabla\nabla S(\mathbf{w})|_{\mathbf{w}=\mathbf{w_0}}$ — матрица Гессе функции ошибок,

$E_D=\frac{1}{2}\sum^n_{i=1}(\widehat{x_i}-x_i)^2$ — функция ошибки в пространстве данных.

Настройка параметрической регрессионной модели происходит в 2 этапа ^[1], сначала настраиваются параметры $\mathbf{w}$ при фиксированных гиперпараметрах $\beta, A$ , затем при вычисленных значениях параметров функция правдоподобия $\ln p(D|\beta, A)$ оптимизируется по гиперпараметрам. Процедура повторяется, пока настраиваемые параметры не стабилизируется.

Для простоты вычислений, считаем, что $A$ имеет диагональный вид:

$A=\left( \begin{array}{cccc} \alpha_{1} & 0 & \dots & 0\\ 0 & \alpha_2 & \dots & 0 \\ \vdots & \vdots & \ddots & 0\\ 0 & \dots & 0 & \alpha_M\\ \end{array} \right).$ .

Вычислительный эксперимент

Пример на реальных данных

Вычислительный эксперимент проводился на реальных данных. Использовались временные ряды потребления электроэнергии в некотором регионе с отсчетами 1 час, период ряда равен $p=24$ . Эксперимент состоит из этапов:

1) из множества порождающих моделей:

$f_1(x) = x; f_2(x) = \sin(x); f_3(x) = \cos(x); f_4(x) = \exp(x); f_5(x) = \ln(x); f_6(x) = \tan(x);$

была построена их суперпозиция, описывающая потребление электроэнергии за сутки:

$\widehat{x}_{pn+t}=w_1\cdot{\sqrt{t}}+w_2\cdot{\exp(-t)}+w_3\cdot{\exp(-24\cdot{t})}+w_4\cdot \exp\left(w_5\cdot{\sin(t^4)} \right)+w_6\cdot \exp \left( w_7\cdot cos(24\cdot t^{2,5})\right)+$ $+w_{10}\cdot cos(t)+w_{12}\cdot t\cdot cos(t^3).$

2) модель настраивается на подпоследовательности

$\mathbf{x}(n)=\{x_{pn+1},\dots,x_{pn+24}\}$ ,

где $n$ - номер суток. В результате получаем набор оптимальных параметров и гиперпараметров модели, оптимальных для данной подпоследовательности:

$\mathbf{w}(n), A(n), \beta(n)$ .

3) строится зависимость расстояния между последовательностями в пространстве параметров:

$D_{KL} \left( \mathbf{x}(n), \mathbf{x}(m) \right)= D_{KL}\left(p(w), q(w) \right) = \sum\limits_{w\in \mathcal{W}} p(w) \ln \frac{p(w)}{q(w)}$ , где $p(w),q(w)$ - плотности распределений случайных величины из $N(\mathbf{w}(n),A(n))$ и $N(\mathbf{w}(m),A(m))$ соотвественно, и расстояний в пространстве значений:

$Dintance \left( \mathbf{x}(n), \mathbf{x}(m) \right)=\sum_{t=1}^{24}\left( x_t(n)-x_t(m) \right)^2$

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

Пример на сгенерированных данных

Проведен для для 6 моделей распределения данных: 1) $f(\mathbf{x},\mathbf{w}) = a_1 + b_1\cdot{t}+\epsilon$ , где $\epsilon\in N(0, 1)$ ;

2) $f(\mathbf{x},\mathbf{w}) = a_1 + b_1\cdot{t}+\epsilon$ , где $\epsilon\in N(0, 5)$ ;

3) $f(\mathbf{x},\mathbf{w}) = a_1-10*\sigma_{\epsilon} + b_1\cdot{t}+\epsilon$ , где $\epsilon\in N(0, 1)$ , $\sigma_{\epsilon}$ - дисперсия случайной величины;

4) $f(\mathbf{x},\mathbf{w}) = a_1 + 1,5\cdot b_1\cdot{t}-t^2+\epsilon$ , где $\epsilon\in N(0, 5)$ ;

5) $f(\mathbf{x},\mathbf{w}) = a_1 + 1,5\cdot b_1\cdot{t}-t^2+\epsilon$ , где $\epsilon\in N(0, 10)$ ;

6) $f(\mathbf{x},\mathbf{w}) = a_1 -10*\sigma_{\epsilon} + 1,5\cdot b_1\cdot{t}-t^2+\epsilon$ , где $\epsilon\in N(0, 5)$ .

Первые три модели относится в первому типу (line), три последних модели относятся ко второму типу (parabola). Прогнозирующая модель была линейной: $\widehat{x}_{t}=w_1+w_2\cdot{t}$ .

На тестовом примере видно, что чем больше расстояние между рядами в пространстве значений, тем скорее больше будет разница между распределениями настроенных параметров. На картинках можно явно разделить увидеть, что расстояние Кульбака-Лейблера между распределениями настроенных параметров для похожих моделей (line - line или parabola - parabola) значительно меньше расстояния между параметрами непохожих моделей (line-parabola или parabola-line). Таким образом можно настроить такой порог, по которому можно было бы определить, относится ли временной ряд к заранее фиксированному типу моделей.

Исходный код

Romanenko2010Compare

Литература

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

Студент: Участник:Алексей Романенко

Преподаватель: В.В.Стрижов

Срок: 24 декабря 2010

В настоящее время задание завершено и проверено. Данная страница может свободно правиться другими участниками проекта MachineLearning.ru.

См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%A1%D1%80%D0%B0%D0%B2%D0%BD%D0%B5%D0%BD%D0%B8%D0%B5_%D0%B2%D1%80%D0%B5%D0%BC%D0%B5%D0%BD%D0%BD%D1%8B%D1%85_%D1%80%D1%8F%D0%B4%D0%BE%D0%B2_%D0%BF%D1%80%D0%B8_%D0%B0%D0%B2%D1%82%D0%BE%D1%80%D0%B5%D0%B3%D1%80%D0%B5%D1%81%D1%81%D0%B8%D0%BE%D0%BD%D0%BD%D0%BE%D0%BC_%D0%BF%D1%80%D0%BE%D0%B3%D0%BD%D0%BE%D0%B7%D0%B5_%28%D0%BF%D1%80%D0%B8%D0%BC%D0%B5%D1%80%29»

Категория: Практика и вычислительные эксперименты

@@ Строка 1: / Строка 1: @@
 == Аннотация ==
-Данная работа посвящена исследованию зависимости между пространственными характеристиками (форма, период)  временного ряда и распределением параметров регрессионных моделей, которые описывают эти временные ряды. Один из подходов исследовать данную зависимость - посмотреть, как распределены параметры моделей для похожих в некотором смысле временных рядов, и насколько эти распределения различаются для непохожих (различных в некотором смысле) временных рядов.
+Данная работа посвящена исследованию зависимости между пространственными характеристиками (форма, период) временного ряда<ref>Стрижов В.В, Пташко Г.О. Построение инвариантов на множестве временных рядов путем динамической свертки свободной переменной. — ВЦ РАН, 2009.</ref> и распределением параметров регрессионных моделей, которые описывают эти временные ряды. Один из подходов исследовать данную зависимость - посмотреть, как распределены параметры моделей для похожих в некотором смысле временных рядов, и насколько эти распределения различаются для непохожих (различных в некотором смысле) временных рядов.
 == Постановка задачи ==
@@ Строка 6: / Строка 6: @@
 Задача авторегрессионного прогноза заключается в нахождении модели <tex>$f(\mathbf{x}, \mathbf{w})$</tex>, где <tex>$\mathbf{w}\in\mathbb{R}^M$</tex> вектор параметров модели, которая наилучшим образом приближает следущее значение временного ряда <tex>$x_{T+1}:\widehat{x}_{T+1}=f(\mathbf{x}, \mathbf{w})$</tex>.
-Свертка временного ряда возникает в случае существования на множестве подпоследовательностей временного ряда некоторого инварианта. Примером инварианта является период временного ряда, который физически может означать сезонность в данных. При этом построенная модель должна учитывать наличие инварианта и сохранять данное свойство для ряда прогнозов: <tex>$\{\widehat{x}_{t}\}_{t=1}^T\in\mathbb{R}^T$</tex>.
 Пусть задан временной ряд <tex>$\mathbf{x}=\{x_{t}\}_{t=1}^T\in\mathbb{R}^T$</tex>. Предполагается, что отсчеты <tex>t=1,\dots, T</tex> были сделаны через равные промежутки времени, и период временного ряда равен <tex>$p$</tex>, при этом <tex>$ {T}+1=p\cdot{n}$</tex>, где <tex>n\in\mathbb{N}</tex>.
@@ Строка 15: / Строка 14: @@
 Расстояние между различными подпоследовательностями <tex> x_{n_1\cdot{p}+1},\dots,x_{(n_1+1)\cdot{p}}</tex> и <tex> x_{n_2\cdot{p}+1},\dots,x_{(n_2+1)\cdot{p}}</tex> можно вычислить как сумму квадратов отклонений:
-<center><tex>SSE=\sum_{i=1}^p{(x_{n_2{p}+i}-x_{n_1{p}+i})^2}</tex></center>.
+<center><tex>SSE=\sum_{i=1}^p{(x_{n_2{p}+i}-x_{n_1{p}+i})^2}.</tex></center>
-Однако этот метод учитывает только расстояния между парами отсчетов временного ряда. Метод поиска пути минимальной стоимости (warping path) учитывает не только расстояние между отсчетами рядов, но и форму самих временных рядов.
+Однако этот метод учитывает только расстояния между парами отсчетов временного ряда. Метод поиска пути минимальной стоимости (warping path)<ref>Keogh E. J., Pazzani M. J. Derivative Dynamic Time Warping International Conference on Data Mining (SDM’2001) 2001</ref> учитывает не только расстояние между отсчетами рядов, но и форму самих временных рядов.
 Предположим, мы имеем две последовательности <tex>\mathbf{x}= \{x_{1},\dots,x_{n}\}\in\mathbb{R}^n</tex> и <tex>\mathbf{y}= \{y_{1},\dots,y_{m}\}\in\mathbb{R}^m</tex>. Тогда построим матрицу <tex>n\times m</tex> попарных расстояний:
-<center><tex>\Omega=\|\omega_{i,j}\|_{i=1,j=1}^{n, m}=\|(x_i-x_j)^2\|_{i=1,j=1}^{n, m}</tex></center>.
+<center><tex>\Omega=\|\omega_{i,j}\|_{i=1,j=1}^{n, m}=\|(x_i-x_j)^2\|_{i=1,j=1}^{n, m}.</tex></center>
 Далее из элементов матрицы <tex>\Omega</tex> строим путь:
-<center><tex>\{s_1, \dots, s_C\}=\{\omega_{i_1,j_1}, \dots, \omega_{i_{n_C}, j_{m_C}}\}</tex></center>.
+<center><tex>\{s_1, \dots, s_C\}=\{\omega_{i_1,j_1}, \dots, \omega_{i_{n_C}, j_{m_C}}\}.</tex></center>
 Построенный путь удовлетворяет следующим условиям:
@@ Строка 37: / Строка 36: @@
 Стоимостью пути <tex>\{s_1, \dots, s_C\}</tex> будет
-<center><tex><tex>D\left(\{s_1, \dots, s_C\}\right)=\frac{\sqrt{\sum_{c=1}^C{s_c}}}{C}</tex>.</center>
+<center><tex><tex>D\left(\{s_1, \dots, s_C\}\right)=\frac{\sqrt{\sum_{c=1}^C{s_c}}}{C}.</tex></center>
 Среди всех путей есть по крайней мере один с минимальной стоимостью. Его стоимость и будем считать расстоянием между последовательностями:
-<center><tex>DTW(\mathbf{x},\mathbf{y}) = \min\limits_{\{s_1, \dots, s_C\}}D\left(\{s_1, \dots, s_C\}\right)</tex></center>.
+<center><tex>DTW(\mathbf{x},\mathbf{y}) = \min\limits_{\{s_1, \dots, s_C\}}D\left(\{s_1, \dots, s_C\}\right).</tex></center>
+Алгоритм поиска пути минимальной стоимости рекурсивно находит длину пути наименьшей стоимости <tex>\gamma_{i,j}</tex> до каждого элемента матрицы <tex>\Omeg</tex>:
+<center><tex>\gamma_{i,j} = \omega_{i,j}+\min(\gamma_{i,j-1}, \gamma_{i-1,j}, \gamma{i-1, j-1}).</tex></center>
 === Расстояние между параметрами модели ===
-Расстояние между параметрами модели <tex>$\mathbf{x}=f(\mathbf{x}, \mathbb{w})+\epsilon$</tex>, настроенной на разных подпоследовательностях, можно измерить как расстояние Кульбака-Лейблера между функциями распределения 2-ух случайных величин <tex>{p(x)},{q(x)}</tex>:
+Расстояние между параметрами модели <tex>$\mathbf{x}=f(\mathbf{x}, \mathbb{w})+\epsilon$</tex>, настроенной на разных подпоследовательностях, можно измерить как расстояние Кульбака-Лейблера между функциями распределения 2-ух случайных величин <tex>{p(w)},{q(w)}</tex>:
-<center><tex>D_{KL}(p, q) = \sum\limits_{x\in \mathcal{X}} p(x) \ln \frac{p(x)}{q(x)}.</tex></center>
+<center><tex>D_{KL}(p, q) = \sum\limits_{w\in \mathcal{W}} p(w) \ln \frac{p(w)}{q(w)}.</tex></center>
 === Постановка задачи ===
 Требуется исследовать зависимость расстояния между параметрами модели <tex>$\mathbf{x}=f(\mathbf{x}, w)+\epsilon$</tex> от расстояния между подпоследовательностями, на которых эти параметры были настроены.
@@ Строка 61: / Строка 64: @@
 <tex>E_D=\frac{1}{2}\sum^n_{i=1}(\widehat{x_i}-x_i)^2</tex> — функция ошибки в пространстве данных.
-Настройка параметрической регрессионной модели происходит в 2 этапа, сначала настраиваются параметры <tex>\mathbf{w}</tex> при фиксированных гиперпараметрах <tex>\beta, A</tex>, затем при вычисленных значениях параметров функция правдоподобия <tex>\ln p(D|\beta, A)</tex> оптимизируется по гиперпараметрам. Процедура повторяется, пока настраиваемые параметры не стабилизируется.
+Настройка параметрической регрессионной модели происходит в 2 этапа <ref>Стрижов В.В Методы выбора регрессионных моделей. — ВЦ РАН, 2010</ref>, сначала настраиваются параметры <tex>\mathbf{w}</tex> при фиксированных гиперпараметрах <tex>\beta, A</tex>, затем при вычисленных значениях параметров функция правдоподобия <tex>\ln p(D|\beta, A)</tex> оптимизируется по гиперпараметрам. Процедура повторяется, пока настраиваемые параметры не стабилизируется.
 Для простоты вычислений, считаем, что<tex> A </tex> имеет диагональный вид:
@@ Строка 76: / Строка 79: @@
 == Вычислительный эксперимент ==
-=== Пример на реальных дынных ===
+=== Пример на реальных данных ===
 [[Изображение:EnergyConsumptoin.png|thumb|left]]
 [[Изображение:DayPeriod.png|thumb|right]]
@@ Строка 144: / Строка 147: @@
 == Исходный код ==
+[https://mlalgorithms.svn.sourceforge.net/svnroot/mlalgorithms/Group874/Romanenko2010Compare/  Romanenko2010Compare]
 == Литература ==
-# {{книга
+{{список примечаний}}
-|автор        = Стрижов В.В, Пташко Г.О.
-|заглавие     =  Построение инвариантов на множестве временных рядов путем динамической свертки свободной переменной
+{{ЗаданиеВыполнено|Алексей Романенко|В.В.Стрижов|24 декабря 2010||Strijov}}
-|издательство = ВЦ РАН
+[[Категория:Практика и вычислительные эксперименты]]
-|год          = 2009
-}}
-# {{книга
-|автор        = Стрижов В.В
-|заглавие     =  Методы выбора регрессионных моделей
-|издательство = ВЦ РАН
-|год          = 2010
-}}
-# {{книга
-|автор        = Keogh E. J., Pazzani M. J.
-|заглавие     = Derivative Dynamic Time Warping
-|издательство = International Conference on Data Mining (SDM’2001)
-|год          = 2001
-}}

Сравнение временных рядов при авторегрессионном прогнозе (пример)

Материал из MachineLearning.

Текущая версия

Содержание

Аннотация

Постановка задачи

Расстояние между временными рядами

Расстояние между параметрами модели

Постановка задачи

Алгоритм

Вычислительный эксперимент

Пример на реальных данных

Пример на сгенерированных данных

Исходный код

Литература

Просмотры

Личные инструменты

Навигация

Поиск

Инструменты