Выделение периодической компоненты временного ряда (пример)

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

(Различия между версиями)
Перейти к: навигация, поиск
(→Постановка задачи)
Строка 28: Строка 28:
<center><tex>Q = \sum\limits_{t=1}^{l}|\hat{X_t}-X_t|,</tex></center>
<center><tex>Q = \sum\limits_{t=1}^{l}|\hat{X_t}-X_t|,</tex></center>
где <tex>\hat{X_t}</tex> - прогнозируемое значение в <tex>t</tex>-ый момент времени, <tex>X_t</tex> - фактическое значение.
где <tex>\hat{X_t}</tex> - прогнозируемое значение в <tex>t</tex>-ый момент времени, <tex>X_t</tex> - фактическое значение.
 +
 +
==Пути решения задачи==
 +
 +
Опишем используемые в работе алгоритмы.
 +
 +
<b><big>Автокорреляционная функция.</big></b>
 +
 +
<i>Автокорреляционная функция</i> - это характеристика временного ряда, которая помогает находить его повторяющиеся участки, скрытые из-за наложений шума или других помех.
 +
 +
Для дискретного временного ряда <tex>X_1, X_2, ..., X_n</tex> с известными матожиданием <tex>\mu</tex> и дисперсией <tex>\sigma</tex> автокорреляционную функцию можно рассчитать по следующей формуле:
 +
<center><tex>R(w)=\frac{1}{(n-w)\sigma ^2}\sum_{t=1}^{n-w} [X_t-\mu][X_{t+w}-\mu],</tex></center>
 +
где <tex>n</tex> - длина временного ряда, <tex>w</tex> - текущая задержка во времени. Таким образом получим функцию <tex>R(w)</tex>, зависящую от лагов (задержек во времени). Исследуя ее на экстремальные значения, получим искомые значения периодов <tex>T=\{\tau_1,..\tau_p\}</tex>.
 +
 +
Оценка периода осложняется тем, что в некоторой окрестности оцениваемого периода, наблюдаются локальные максимумы коэффициентов корреляции. Следовательно, необходимо усреднение коэффициентов корреляции, а также удаление <<близких>> и кратных периодов (<<близкими>> в работе считаются периоды, отличающиеся друг от друга менее, чем на величину <tex>\delta</tex>).
 +
 +
<b><big>Ряд Фурье.</big></b>
 +
 +
Сделаем предположение о наличии периодичности в предлагаемом ряде и обратимся к теореме.
 +
 +
<b>Теорема 1.</b>
 +
Если некоторая периодическая функция с периодом <tex>2j</tex> на интервале <tex>[-j, j]</tex> удовлетворяет условиям Дирихле (имеет конечное число экстремумов и точек разрыва I рода), то она может быть представлена в виде суммы ряда Фурье (разложена в ряд Фурье).
 +
 +
Таким образом, рассматриваемые в данной работе временные ряды могут быть представлены в виде бесконечного ряда Фурье. Построим регрессионную модель следующего вида.
 +
 +
Можно заметить, что разложение временной последовательности в ряд Фурье позволяет отыскать скрытые периодичности. Одним из возможных способов определения автокорреляционной зависимости является разложение временного ряда в функции синусов и косинусов и нахождение линейной множественной регрессии.
 +
 +
<center><tex>X_t=\frac{a_0}{2}+\sum_{k=1}^{n} {a_k}\cos({\lambda_k}t) + {b_k}\sin({\lambda_k}t),</tex></center>
 +
где <tex>\lambda_k=2\pi\eta_k</tex>, <tex>\eta_k=\frac{k}{n}</tex>, <tex>k=1,2,.., n</tex>.
 +
 +
Коэффициенты <tex>a_k</tex> и <tex>b_k</tex> определяются следующими рядами:
 +
 +
<center><tex>a_k=\frac{2}{n} \sum_{i=1}^n {X_i}\cos(\lambda_k t), k=0,1,2.., n;</tex></center>
 +
<center><tex>b_k=\frac{2}{n} \sum_{i=1}^n {X_i}\sin(\lambda_k t), k=1,2.., n.</tex></center>
 +
 +
Коэффициенты при косинусах и синусах - это коэффициенты регрессии. Они показывают степень, с которой соответствующие функции коррелируют с данными. Необходимо заметить, что сами синусы и косинусы на различных частотах ортогональны. Будем рассматривать не более чем <tex>n</tex> различных синусов и косинусов.В итоге определяется корреляция функций синусов и косинусов различной частоты с наблюдаемыми данными. Если найденная корреляция (коэффициент при определенном синусе или косинусе) велика, то можно заключить, что существует строгая периодичность на соответствующей частоте в данных.
 +
 +
Данный метод даёт точный результат только тогда, когда длина временного ряда (то есть параметр <tex>n</tex>) кратен искомому периоду. В противном случае мы получим некую суперпозицию синусов и косинусов, которую достаточно сложно интерпретировать. Поэтому воспользуемся методом тригонометрической интерполяции с помощью метода наименьших квадратов.
 +
 +
<b><big>Тригонометрическая интерполяция методом наименьших квадратов.</big></b>
 +
 +
Требуется построить кривую, которая воспроизводила бы график исходной экспериментальной закономерности, то есть была бы максимально близка к экспериментальным точкам, но в то же время была бы нечувствительна к случайным отклонениям измеряемой величины.
 +
 +
Введем непрерывную функцию <tex>\varphi(x)</tex> для аппроксимации дискретной зависимости <tex>g(x_i)</tex>, <tex>i =1,...,n</tex>. Будем считать, что <tex>\varphi(x)</tex> построена при условии наилучшего квадратичного приближения, если:
 +
 +
(1)<center><tex>M=\sum_{i=1}^n (\varphi(x_i)-g(x_i))^2=\min.</tex></center>
 +
 +
Рассмотрим случай линейной аппроксимации:
 +
<center><tex>\varphi(x)=c_{0}\varphi_{0}(x)+c_{1}\varphi_{1}(x)+...+c_{m}\varphi_{m}(x),</tex></center>
 +
где <tex>\varphi_{0},...,\varphi_{m}</tex> - произвольные базисные функции, <tex>c_0,...,c_m</tex> - неизвестные коэффициенты. Количество базисных функций должно быть меньше количества заданных точек для того, чтобы их суперпозиция определялась единственным образом.
 +
 +
Для решения задачи линейной аппроксимации в общем случае следует найти условия минимума суммы квадратов отклонений. Это можно свести к задаче поиска корня системы уравнений <tex>\frac{\partial M}{\partial c_k}=0</tex>, <tex>k=1,...,m</tex>. Вычисление данных производных, при учёте равенства (1) приведёт к следующей системе алгебраических уравнений:
 +
<tex>
 +
\left\{
 +
\begin{array}{lcl}
 +
\sum_{i=1}^n (c_{0}\varphi_{0}(x)+c_{1}\varphi_{1})(x)+\ldots+c_{m}\varphi_{m}(x)-g_i)\varphi_{0}(x)=0;\\
 +
&&\\
 +
\sum_{i=1}^n (c_{0}\varphi_{0}(x)+c_{1}\varphi_{1})(x)+\ldots+c_{m}\varphi_{m}(x)-g_i)\varphi_{1}(x)=0;
 +
&&\\
 +
\ldots
 +
\\
 +
&&\\
 +
\sum_{i=1}^n (c_{0}\varphi_{0}(x)+c_{1}\varphi_{1})(x)+\ldots+c_{m}\varphi_{m}(x)-g_i)\varphi_{m}(x)=0.\\
 +
\end{array}
 +
\right.
 +
</tex>
 +
 +
Далее следует решить полученную СЛАУ относительно коэффициентов <tex>c_0,...,c_m</tex>. Для решения СЛАУ обычно составляется расширенная матрица коэффициентов, которую называют матрицей Грамма, элементами которой являются скалярные произведения базисных функций и столбец свободных коэффициентов:
 +
<center><tex>
 +
\begin{Vmatrix}
 +
(\varphi_0,\varphi_0)&(\varphi_0,\varphi_1)&\ldots&(\varphi_0,\varphi_m)&(\varphi_0,g)\\
 +
(\varphi_1,\varphi_0)&(\varphi_1,\varphi_1)&\ldots&(\varphi_1,\varphi_m)&(\varphi_1,g)\\
 +
\ldots&\ldots&\ddots&\ldots&\ldots\\
 +
(\varphi_m,\varphi_0)&(\varphi_m,\varphi_1)&\ldots&(\varphi_m,\varphi_m)&(\varphi_m,g)\\
 +
\end{Vmatrix}
 +
</tex></center>
 +
 +
<center><tex>(\varphi_j,\varphi_k)=\sum_{i=1}^n \varphi_{j}(x_i)\varphi_{k}(x_i)(\varphi_{j}g)=\sum_{i=1}^n \varphi_{j}(x_i)g(x_i),</tex></center>
 +
где <tex>j=0,...,m</tex>, <tex>k=0,...,m</tex>.
 +
 +
После того как с помощью, например, метода Гаусса найдены коэффициенты <tex>c_0,...,c_m</tex>, можно построить аппроксимирующую кривую или вычислить координаты заданной точки. Таким образом, задача аппроксимации решена.
 +
 +
Для того чтобы сформировать ортонормированный базис, коэффициенты нормировки будут следующими:
 +
для <tex>a_0</tex> - <tex>(4/n)^{0.5};</tex>
 +
для <tex>a_k</tex> и <tex>b_k</tex> - <tex>(2/n)^{0.5},</tex> где <tex>a_k</tex> - коэффициенты нормировки для косинусов, <tex>k=0,...,m</tex>; <tex>b_k</tex> - коэффициенты нормировки для синусов, <tex>k=1,...,m</tex>; <tex>n</tex> - количество отсчетов. В качестве функции <tex>g(x)</tex> рассмотрим дискретный ряд <tex>X_t</tex>.
 +
 +
 +
При работе с временными рядами необходимо учесть возможное наличие тренда или присутствие постоянного слагаемого. Обе эти составляющие исключим из данных, поскольку они могут привести к большим погрешностям при подсчёте функционала <tex>Q = \sum\limits_{t=1}^{l}|\hat{X_t}-X_t|</tex>. Пользуясь методом наименьших квадратов мы учтём и тренд и наличие постоянного слагаемого. Необходимо заметить, что тригонометрическая интерполяция основана на разложении в ряд Фурье, поэтому она также не годится для выявления периодической компоненты ряда. В данной работе она используется для нахождения тренда, содержащего периодическую компоненту. Оставшиеся точки исследуются при помощи автокорреляционной функцией.

Версия 17:16, 21 мая 2011

Введение

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

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

Метод наименьших квадратов(МНК) оценивает параметры для тригонометрической аппроксимации данного ряда. Так как любая последовательность, обладающая периодичностью может быть разложена в ряд Фурье, необходимо принять коэффициенты перед синусами и косинусами за коэффициенты регрессии и оценить их величину. Если найденная корреляция (коэффициент при определенном синусе или косинусе) велика, то можно заключить, что существует строгая периодичность на соответствующей частоте в данных.

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

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

Дан временной ряд X_t, где n - длина временного ряда, t\in\{1,...,n\} - номер отсчета. Предполагаем, что в рассматриваемом временном ряде нет пропущенных значений, и он имеет периодические составляющие с периодом T=\{\tau_1,..\tau_p\}. Работа состоит из трех следующих ступеней.

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

       1. при увеличении шума;
       2. при уменьшении числа отсчётов на период;
       3. при сокращении длины временного ряда.

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

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

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

Q = \sum\limits_{t=1}^{l}|\hat{X_t}-X_t|,

где \hat{X_t} - прогнозируемое значение в t-ый момент времени, X_t - фактическое значение.

Пути решения задачи

Опишем используемые в работе алгоритмы.

Автокорреляционная функция.

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

Для дискретного временного ряда X_1, X_2, ..., X_n с известными матожиданием \mu и дисперсией \sigma автокорреляционную функцию можно рассчитать по следующей формуле:

R(w)=\frac{1}{(n-w)\sigma ^2}\sum_{t=1}^{n-w} [X_t-\mu][X_{t+w}-\mu],

где n - длина временного ряда, w - текущая задержка во времени. Таким образом получим функцию R(w), зависящую от лагов (задержек во времени). Исследуя ее на экстремальные значения, получим искомые значения периодов T=\{\tau_1,..\tau_p\}.

Оценка периода осложняется тем, что в некоторой окрестности оцениваемого периода, наблюдаются локальные максимумы коэффициентов корреляции. Следовательно, необходимо усреднение коэффициентов корреляции, а также удаление <<близких>> и кратных периодов (<<близкими>> в работе считаются периоды, отличающиеся друг от друга менее, чем на величину \delta).

Ряд Фурье.

Сделаем предположение о наличии периодичности в предлагаемом ряде и обратимся к теореме.

Теорема 1. Если некоторая периодическая функция с периодом 2j на интервале [-j, j] удовлетворяет условиям Дирихле (имеет конечное число экстремумов и точек разрыва I рода), то она может быть представлена в виде суммы ряда Фурье (разложена в ряд Фурье).

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

Можно заметить, что разложение временной последовательности в ряд Фурье позволяет отыскать скрытые периодичности. Одним из возможных способов определения автокорреляционной зависимости является разложение временного ряда в функции синусов и косинусов и нахождение линейной множественной регрессии.

X_t=\frac{a_0}{2}+\sum_{k=1}^{n} {a_k}\cos({\lambda_k}t) + {b_k}\sin({\lambda_k}t),

где \lambda_k=2\pi\eta_k, \eta_k=\frac{k}{n}, k=1,2,.., n.

Коэффициенты a_k и b_k определяются следующими рядами:

a_k=\frac{2}{n} \sum_{i=1}^n {X_i}\cos(\lambda_k t), k=0,1,2.., n;
b_k=\frac{2}{n} \sum_{i=1}^n {X_i}\sin(\lambda_k t), k=1,2.., n.

Коэффициенты при косинусах и синусах - это коэффициенты регрессии. Они показывают степень, с которой соответствующие функции коррелируют с данными. Необходимо заметить, что сами синусы и косинусы на различных частотах ортогональны. Будем рассматривать не более чем n различных синусов и косинусов.В итоге определяется корреляция функций синусов и косинусов различной частоты с наблюдаемыми данными. Если найденная корреляция (коэффициент при определенном синусе или косинусе) велика, то можно заключить, что существует строгая периодичность на соответствующей частоте в данных.

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

Тригонометрическая интерполяция методом наименьших квадратов.

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

Введем непрерывную функцию \varphi(x) для аппроксимации дискретной зависимости g(x_i), i =1,...,n. Будем считать, что \varphi(x) построена при условии наилучшего квадратичного приближения, если:

(1)
M=\sum_{i=1}^n (\varphi(x_i)-g(x_i))^2=\min.

Рассмотрим случай линейной аппроксимации:

\varphi(x)=c_{0}\varphi_{0}(x)+c_{1}\varphi_{1}(x)+...+c_{m}\varphi_{m}(x),

где \varphi_{0},...,\varphi_{m} - произвольные базисные функции, c_0,...,c_m - неизвестные коэффициенты. Количество базисных функций должно быть меньше количества заданных точек для того, чтобы их суперпозиция определялась единственным образом.

Для решения задачи линейной аппроксимации в общем случае следует найти условия минимума суммы квадратов отклонений. Это можно свести к задаче поиска корня системы уравнений \frac{\partial M}{\partial c_k}=0, k=1,...,m. Вычисление данных производных, при учёте равенства (1) приведёт к следующей системе алгебраических уравнений: \left\{ \begin{array}{lcl} \sum_{i=1}^n (c_{0}\varphi_{0}(x)+c_{1}\varphi_{1})(x)+\ldots+c_{m}\varphi_{m}(x)-g_i)\varphi_{0}(x)=0;\\ &&\\ \sum_{i=1}^n (c_{0}\varphi_{0}(x)+c_{1}\varphi_{1})(x)+\ldots+c_{m}\varphi_{m}(x)-g_i)\varphi_{1}(x)=0; &&\\ \ldots \\ &&\\ \sum_{i=1}^n (c_{0}\varphi_{0}(x)+c_{1}\varphi_{1})(x)+\ldots+c_{m}\varphi_{m}(x)-g_i)\varphi_{m}(x)=0.\\ \end{array} \right.

Далее следует решить полученную СЛАУ относительно коэффициентов c_0,...,c_m. Для решения СЛАУ обычно составляется расширенная матрица коэффициентов, которую называют матрицей Грамма, элементами которой являются скалярные произведения базисных функций и столбец свободных коэффициентов:

\begin{Vmatrix} (\varphi_0,\varphi_0)&(\varphi_0,\varphi_1)&\ldots&(\varphi_0,\varphi_m)&(\varphi_0,g)\\ (\varphi_1,\varphi_0)&(\varphi_1,\varphi_1)&\ldots&(\varphi_1,\varphi_m)&(\varphi_1,g)\\ \ldots&\ldots&\ddots&\ldots&\ldots\\ (\varphi_m,\varphi_0)&(\varphi_m,\varphi_1)&\ldots&(\varphi_m,\varphi_m)&(\varphi_m,g)\\ \end{Vmatrix} </p>
(\varphi_j,\varphi_k)=\sum_{i=1}^n \varphi_{j}(x_i)\varphi_{k}(x_i)(\varphi_{j}g)=\sum_{i=1}^n \varphi_{j}(x_i)g(x_i),

где j=0,...,m, k=0,...,m.

После того как с помощью, например, метода Гаусса найдены коэффициенты c_0,...,c_m, можно построить аппроксимирующую кривую или вычислить координаты заданной точки. Таким образом, задача аппроксимации решена.

Для того чтобы сформировать ортонормированный базис, коэффициенты нормировки будут следующими: для a_0 - (4/n)^{0.5}; для a_k и b_k - (2/n)^{0.5}, где a_k - коэффициенты нормировки для косинусов, k=0,...,m; b_k - коэффициенты нормировки для синусов, k=1,...,m; n - количество отсчетов. В качестве функции g(x) рассмотрим дискретный ряд X_t.


При работе с временными рядами необходимо учесть возможное наличие тренда или присутствие постоянного слагаемого. Обе эти составляющие исключим из данных, поскольку они могут привести к большим погрешностям при подсчёте функционала Q = \sum\limits_{t=1}^{l}|\hat{X_t}-X_t|. Пользуясь методом наименьших квадратов мы учтём и тренд и наличие постоянного слагаемого. Необходимо заметить, что тригонометрическая интерполяция основана на разложении в ряд Фурье, поэтому она также не годится для выявления периодической компоненты ряда. В данной работе она используется для нахождения тренда, содержащего периодическую компоненту. Оставшиеся точки исследуются при помощи автокорреляционной функцией.

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%92%D1%8B%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BF%D0%B5%D1%80%D0%B8%D0%BE%D0%B4%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B9_%D0%BA%D0%BE%D0%BC%D0%BF%D0%BE%D0%BD%D0%B5%D0%BD%D1%82%D1%8B_%D0%B2%D1%80%D0%B5%D0%BC%D0%B5%D0%BD%D0%BD%D0%BE%D0%B3%D0%BE_%D1%80%D1%8F%D0%B4%D0%B0_%28%D0%BF%D1%80%D0%B8%D0%BC%D0%B5%D1%80%29»