Сравнение временных рядов при авторегрессионном прогнозе (пример)
Материал из MachineLearning.
(→Пример на реальных дынных) |
(→Исходный код) |
||
(9 промежуточных версий не показаны.) | |||
Строка 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>$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>$\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>. | Пусть задан временной ряд <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> можно вычислить как сумму квадратов отклонений: | Расстояние между различными подпоследовательностями <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> попарных расстояний: | Предположим, мы имеем две последовательности <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> строим путь: | Далее из элементов матрицы <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> будет | Стоимостью пути <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><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( | + | Расстояние между параметрами модели <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_{ | + | <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> от расстояния между подпоследовательностями, на которых эти параметры были настроены. | Требуется исследовать зависимость расстояния между параметрами модели <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> — функция ошибки в пространстве данных. | <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> имеет диагональный вид: | Для простоты вычислений, считаем, что<tex> A </tex> имеет диагональный вид: | ||
Строка 76: | Строка 79: | ||
== Вычислительный эксперимент == | == Вычислительный эксперимент == | ||
- | === Пример на реальных | + | === Пример на реальных данных === |
[[Изображение:EnergyConsumptoin.png|thumb|left]] | [[Изображение:EnergyConsumptoin.png|thumb|left]] | ||
[[Изображение:DayPeriod.png|thumb|right]] | [[Изображение:DayPeriod.png|thumb|right]] | ||
Строка 144: | Строка 147: | ||
== Исходный код == | == Исходный код == | ||
+ | [https://mlalgorithms.svn.sourceforge.net/svnroot/mlalgorithms/Group874/Romanenko2010Compare/ Romanenko2010Compare] | ||
== Литература == | == Литература == | ||
- | + | {{список примечаний}} | |
- | + | ||
- | + | {{ЗаданиеВыполнено|Алексей Романенко|В.В.Стрижов|24 декабря 2010||Strijov}} | |
- | + | [[Категория:Практика и вычислительные эксперименты]] | |
- | + | ||
- | }} | + | |
- | + | ||
- | | | + | |
- | | | + | |
- | | | + | |
- | | | + | |
- | }} | + | |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + |
Текущая версия
Содержание |
Аннотация
Данная работа посвящена исследованию зависимости между пространственными характеристиками (форма, период) временного ряда[1] и распределением параметров регрессионных моделей, которые описывают эти временные ряды. Один из подходов исследовать данную зависимость - посмотреть, как распределены параметры моделей для похожих в некотором смысле временных рядов, и насколько эти распределения различаются для непохожих (различных в некотором смысле) временных рядов.
Постановка задачи
Временным рядом называется последовательность упорядоченных по времени значений некоторой вещественной переменной . Элемент последовательности называется отсчетом временного ряда.
Задача авторегрессионного прогноза заключается в нахождении модели , где вектор параметров модели, которая наилучшим образом приближает следущее значение временного ряда .
Пусть задан временной ряд . Предполагается, что отсчеты были сделаны через равные промежутки времени, и период временного ряда равен , при этом , где . Задана модель ,где случайная величина имеет нормальное распределение . Вектор параметров модели рассматривается как многомерная случайная величина. Пусть плотность распределения параметров имеет вид многомерного нормального распределения с матрицей ковариации . Модель некоторым образом учитывает период временного ряда. Предполагается, модель временного ряда может меняться с течением времени, т.е. для разных подпоследовательностей длины оптимальные параметры модели будут отличаться.
Расстояние между временными рядами
Расстояние между различными подпоследовательностями и можно вычислить как сумму квадратов отклонений:
Однако этот метод учитывает только расстояния между парами отсчетов временного ряда. Метод поиска пути минимальной стоимости (warping path)[1] учитывает не только расстояние между отсчетами рядов, но и форму самих временных рядов.
Предположим, мы имеем две последовательности и . Тогда построим матрицу попарных расстояний:
Далее из элементов матрицы строим путь:
Построенный путь удовлетворяет следующим условиям:
'1 граничные условия:'Стоимостью пути будет
Среди всех путей есть по крайней мере один с минимальной стоимостью. Его стоимость и будем считать расстоянием между последовательностями:
Алгоритм поиска пути минимальной стоимости рекурсивно находит длину пути наименьшей стоимости до каждого элемента матрицы :
Расстояние между параметрами модели
Расстояние между параметрами модели , настроенной на разных подпоследовательностях, можно измерить как расстояние Кульбака-Лейблера между функциями распределения 2-ух случайных величин :
Постановка задачи
Требуется исследовать зависимость расстояния между параметрами модели от расстояния между подпоследовательностями, на которых эти параметры были настроены.
Алгоритм
Для настройки параметров модели используется связный байесовский вывод
где — функция ошибки,
— матрица Гессе функции ошибок,
— функция ошибки в пространстве данных.
Настройка параметрической регрессионной модели происходит в 2 этапа [1], сначала настраиваются параметры при фиксированных гиперпараметрах , затем при вычисленных значениях параметров функция правдоподобия оптимизируется по гиперпараметрам. Процедура повторяется, пока настраиваемые параметры не стабилизируется.
Для простоты вычислений, считаем, что имеет диагональный вид:
.
Вычислительный эксперимент
Пример на реальных данных
Вычислительный эксперимент проводился на реальных данных. Использовались временные ряды потребления электроэнергии в некотором регионе с отсчетами 1 час, период ряда равен . Эксперимент состоит из этапов:
1) из множества порождающих моделей:
была построена их суперпозиция, описывающая потребление электроэнергии за сутки:
2) модель настраивается на подпоследовательности
,
где - номер суток. В результате получаем набор оптимальных параметров и гиперпараметров модели, оптимальных для данной подпоследовательности:
3) строится зависимость расстояния между последовательностями в пространстве параметров:
Результаты экспериментов на реальных данных показывают, что можно выделить среди множества пар временных рядов похожие и непохожие. Используя расстояние Кульбака-Лейблера между распределениями параметров моделей можно установить порог, который поможет определить похожие на заранее выделенный тип временных рядов. Для пояснения вышесказанного приведем пример на модельных данных, в которых участвуют временные ряды двух типов.
Пример на сгенерированных данных
Проведен для для 6 моделей распределения данных: 1) , где ;
2) , где ;
3) , где , - дисперсия случайной величины;
4) , где ;
5) , где ;
6) , где .
Первые три модели относится в первому типу (line), три последних модели относятся ко второму типу (parabola). Прогнозирующая модель была линейной: .
На тестовом примере видно, что чем больше расстояние между рядами в пространстве значений, тем скорее больше будет разница между распределениями настроенных параметров. На картинках можно явно разделить увидеть, что расстояние Кульбака-Лейблера между распределениями настроенных параметров для похожих моделей (line - line или parabola - parabola) значительно меньше расстояния между параметрами непохожих моделей (line-parabola или parabola-line). Таким образом можно настроить такой порог, по которому можно было бы определить, относится ли временной ряд к заранее фиксированному типу моделей.
Исходный код
Литература
Данная статья была создана в рамках учебного задания.
См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |