Выделение периодической компоненты временного ряда (пример)
Материал из 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
Введение
Временной ряд - последовательно измеренные через некоторые (зачастую равные) промежутки времени данные. При прогнозировании некоторых временных рядов, например временных рядов продаж, потребления энергии или электрокардиограммы, мы сталкиваемся с тем, что данные ряды обладают периодической компонентой. Существует несколько методов выявления периода. В данной работе сравниваются алгоритмы автокорреляционной функции и метода наименьших квадратов.
Автокорреляционная функция исследует временной ряд на наличие периодической компоненты, сдвигая ряд на несколько временных отсчетов и сравнивая с самим собой.
Метод наименьших квадратов(МНК) оценивает параметры для тригонометрической аппроксимации данного ряда. Так как любая последовательность, обладающая периодичностью может быть разложена в ряд Фурье, необходимо принять коэффициенты перед синусами и косинусами за коэффициенты регрессии и оценить их величину. Если найденная корреляция (коэффициент при определенном синусе или косинусе) велика, то можно заключить, что существует строгая периодичность на соответствующей частоте в данных.
Далее будет рассмотрена работа алгоритмов на модельных данных, а также на реальном временном ряде электрокардиограммы. Будет исследована зависимость коэффициента корреляции от различных характеристик временного ряда, а также рассмотрена возможность применения метода наименьших квадратов для прогнозирования данных.
Постановка задачи
Дан временной ряд , где
- длина временного ряда,
- номер отсчета. Предполагаем, что в рассматриваемом временном ряде нет пропущенных значений, и он имеет периодические составляющие с периодом
. Работа состоит из трех следующих ступеней.
Во-первых, тестирование на модельной задаче. Дан зашумлённый синус с известным периодом. Необходимо исследовать изменение коэффициента корреляции в следующих ситуациях:
1. при увеличении шума; 2. при уменьшении числа отсчётов на период; 3. при сокращении длины временного ряда.
Во-вторых, тестирование на реальном временном ряде. Дан временной ряд электрокардиограммы, включающий периодическую компоненту со сложным строением. Необходимо исследовать его на наличие временных периодичностей, используя алгоритмы автокорреляционной функции и МНК.
В-третьих, необходимо выяснить пригодность метода наименьших квадратов для прогнозирования временных рядов.
Для контроля качества алгоритма прогноза будем выделять во временном ряде последовательных значений (контрольную выборку), которые алгоритм будет прогнозировать по предыдущим значениям. В качестве критерия качества прогноза будем минимизировать следующий функционал:
где - прогнозируемое значение в
-ый момент времени,
- фактическое значение.
Пути решения задачи
Опишем используемые в работе алгоритмы.
Автокорреляционная функция.
Автокорреляционная функция - это характеристика временного ряда, которая помогает находить его повторяющиеся участки, скрытые из-за наложений шума или других помех.
Для дискретного временного ряда с известными матожиданием
и дисперсией
автокорреляционную функцию можно рассчитать по следующей формуле:
где - длина временного ряда,
- текущая задержка во времени. Таким образом получим функцию
, зависящую от лагов (задержек во времени). Исследуя ее на экстремальные значения, получим искомые значения периодов
.
Оценка периода осложняется тем, что в некоторой окрестности оцениваемого периода, наблюдаются локальные максимумы коэффициентов корреляции. Следовательно, необходимо усреднение коэффициентов корреляции, а также удаление <<близких>> и кратных периодов (<<близкими>> в работе считаются периоды, отличающиеся друг от друга менее, чем на величину ).
Ряд Фурье.
Сделаем предположение о наличии периодичности в предлагаемом ряде и обратимся к теореме.
Теорема 1.
Если некоторая периодическая функция с периодом на интервале
удовлетворяет условиям Дирихле (имеет конечное число экстремумов и точек разрыва I рода), то она может быть представлена в виде суммы ряда Фурье (разложена в ряд Фурье).
Таким образом, рассматриваемые в данной работе временные ряды могут быть представлены в виде бесконечного ряда Фурье. Построим регрессионную модель следующего вида.
Можно заметить, что разложение временной последовательности в ряд Фурье позволяет отыскать скрытые периодичности. Одним из возможных способов определения автокорреляционной зависимости является разложение временного ряда в функции синусов и косинусов и нахождение линейной множественной регрессии.
где ,
,
.
Коэффициенты и
определяются следующими рядами:
Коэффициенты при косинусах и синусах - это коэффициенты регрессии. Они показывают степень, с которой соответствующие функции коррелируют с данными. Необходимо заметить, что сами синусы и косинусы на различных частотах ортогональны. Будем рассматривать не более чем различных синусов и косинусов.В итоге определяется корреляция функций синусов и косинусов различной частоты с наблюдаемыми данными. Если найденная корреляция (коэффициент при определенном синусе или косинусе) велика, то можно заключить, что существует строгая периодичность на соответствующей частоте в данных.
Данный метод даёт точный результат только тогда, когда длина временного ряда (то есть параметр ) кратен искомому периоду. В противном случае мы получим некую суперпозицию синусов и косинусов, которую достаточно сложно интерпретировать. Поэтому воспользуемся методом тригонометрической интерполяции с помощью метода наименьших квадратов.
Тригонометрическая интерполяция методом наименьших квадратов.
Требуется построить кривую, которая воспроизводила бы график исходной экспериментальной закономерности, то есть была бы максимально близка к экспериментальным точкам, но в то же время была бы нечувствительна к случайным отклонениям измеряемой величины.
Введем непрерывную функцию для аппроксимации дискретной зависимости
,
. Будем считать, что
построена при условии наилучшего квадратичного приближения, если:
Рассмотрим случай линейной аппроксимации:
где - произвольные базисные функции,
- неизвестные коэффициенты. Количество базисных функций должно быть меньше количества заданных точек для того, чтобы их суперпозиция определялась единственным образом.
Для решения задачи линейной аппроксимации в общем случае следует найти условия минимума суммы квадратов отклонений. Это можно свести к задаче поиска корня системы уравнений ,
. Вычисление данных производных, при учёте равенства (1) приведёт к следующей системе алгебраических уравнений:
Далее следует решить полученную СЛАУ относительно коэффициентов . Для решения СЛАУ обычно составляется расширенная матрица коэффициентов, которую называют матрицей Грамма, элементами которой являются скалярные произведения базисных функций и столбец свободных коэффициентов:
где ,
.
После того как с помощью, например, метода Гаусса найдены коэффициенты , можно построить аппроксимирующую кривую или вычислить координаты заданной точки. Таким образом, задача аппроксимации решена.
Для того чтобы сформировать ортонормированный базис, коэффициенты нормировки будут следующими:
для -
для
и
-
где
- коэффициенты нормировки для косинусов,
;
- коэффициенты нормировки для синусов,
;
- количество отсчетов. В качестве функции
рассмотрим дискретный ряд
.
При работе с временными рядами необходимо учесть возможное наличие тренда или присутствие постоянного слагаемого. Обе эти составляющие исключим из данных, поскольку они могут привести к большим погрешностям при подсчёте функционала . Пользуясь методом наименьших квадратов мы учтём и тренд и наличие постоянного слагаемого. Необходимо заметить, что тригонометрическая интерполяция основана на разложении в ряд Фурье, поэтому она также не годится для выявления периодической компоненты ряда. В данной работе она используется для нахождения тренда, содержащего периодическую компоненту. Оставшиеся точки исследуются при помощи автокорреляционной функцией.