Испытание алгоритма метода "гусеница-SSA" для восстановления временного ряда

Одной из важнейших задач в анализе временных рядов является отделение тренда и периода от шума. Данная статья посвящена исследованию мощного и быстро-развивающегося метода анализа временных рядов «Гу-сеница-SSA» [1].

Рассмотрим временной ряд F :

f 0 , f l , ..., f N - 1 , (1) где N – его длина. В дальнейшем будем предполагать, что ряд F – ненулевой.

Алгоритм метода «Гусеница-SSA» состоит из четырех последовательно выполняемых шагов: вложения, сингулярного разложения, группировки и диагонального усреднения.

На первом шаге процедура вложения переводит исходный временной ряд F в последовательность многомерных векторов, которая называется траекторной матрицей .

Для анализа временного ряда выбирается целочисленный параметр L , именуемый длиной окна , такой что 1 <  L <  N . При этом образуется K = N – L – 1 векторов вложения:

X. = ( f - 1 , f ,..., f + L - 2 ) T , 1 ^ i ^ K .

Эти векторы образуют траекторную матрицу ряда F , столбцами которой являются скользящие отрезки ряда длины L : с первой точки по L -ю, со второй по ( L + 1)-ю и т. д.:

^f 0     ^f ,    ...   ^f K - 1

X = [ X1: X 2:...: Xk ] = f ... f

2 K

I f_L - 1

f_L  ...   f N - 1 )

Существует взаимно однозначное соответствие между матрицами размерности L x K вида (2) и рядами (1) длины N = L + K – 1 [1].

Результатом второго шага является сингулярное разложение траекторной матрицы (2) в сумму элементарных матриц.

Пусть S = X ■ X T . Обозначим через X 1 , X ₂, ^, X _L собственные числа матрицы S , взятые в неубывающем порядке, а через U ₁, U ₂, …, U_L ортонормированную систему собственных векторов матрицы S , соответствующих упорядоченным собственным числам. Тогда сингулярное разложение траекторной матрицы X может быть записано следующим образом:

^X = Х V -, (3) где V = U_; ■ U T ■ X , I = 1, ^ , L . Учитывая, что каждая из матриц V_i имеет ранг 1, назовем их элементарными матрицами [1].

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

На третьем шаге на основе разложения (3) множество индексов {1, 2, …, L } делится на m непересекающих-ся подмножеств I ₁, I ₂, …, I_m . Тем самым разложение (3) может быть записано в виде

m

X = £ Y ; , (4)

Е ^; = 1

V_k – результирующие матрицы для каждого k € I;

подмножества I_i , I = 1, …, m .

Фактически именно на этом шаге происходит разделение исходного ряда (1) на шумы, тренд и периодики. Основным критерием группировки является значимость каждой элементарной матрицы Vk, прямо соответствующая ее собственному числу Xк.

На четвертом шаге алгоритма каждая матрица сгруппированного разложения (4) переводится в ряд длины N .

Положим L * = min( L , K), K = max( L , K). Пусть также y* j = Y j , если L <  K , и y * j = Y , если L >  K . Диагональное усреднение переводит каждую результирующую матрицу Y ( ¹ ) , 5 = 1, 2, ..., m , в ряд f ^{( 5} ) по следующей формуле:

f k =]

к + 1

• к”-. Е У" , к - п + 2 , ⁰ ^ ^к <  L ^{- 1}

• ¹    п = 1

L *

• ¹    V *          *           *

"Г Е У п , к - п +2 , L ^{- 1} ^ ^к <  ^K , ^L n = 1

N - к

N - K * + 1 Z*       *

У п , к - п + 2 , ^K ^ ^к <  N .

п = к - K * + 2

Эта формула соответствует усреднению элементов вдоль диагоналей I +j = к + 2.

Итак, применяя диагональное усреднение (5) к результирующим матрицам Y(5), получаем ряды ~    ~  ~~

F(5) = (f)(5), f,(5),..., fN-1). Исходный же ряд Fрасклады- вается в сумму m рядов: mm

F = Е F'’■ Л =Е f’ п =1

п = 0,1, ..., N- 1,5 = 1,2, ..., m.(6)

Таким образом, результатом работы алгоритма является разложение временного ряда на интерпретируемые аддитивные составляющие. При этом он не требует стационарности ряда, знания модели тренда, а также сведений о наличии в ряде периодических составляющих и их периодах. При таких слабых предположениях метод «Гу-сеница-SSA» может решать различные задачи, такие как выделение тренда, обнаружение периодик, сглаживание ряда, построение полного разложения ряда в сумму тренда, периодик и шума [2].

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

Для исследования преимуществ и недостатков алгоритма метода «Гусеница-SSA» рассмотрим его работу на трех различных примерах. В каждом из примеров дан временной ряд, который состоит из суммы сгенерированных помех R , и заданной искомой функции х :

f = x + R -

Введем также критерий эффективности, задаваемый отношением                 ₂

W = Е ⁽ A^-xi ) . 100 %           (7)

Е ( R , )²

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

Пример 1. Простой временной ряд, слабые помехи; х , = I + 10, I = 0, 1, ..., 49, N = 50, L = 25; R. - равномерно распределенная случайная величина из промежутка [-2; 2]. Матрица S имеет размеры 25 х 25 и 25 собственных чисел X , (табл. 1).

В качестве индексов группировки выбираются числа 24 и 25 как соответствующие наиболее значимым составляющим. С ними соотносятся элементарные матрицы V , ₄ и V ,5 . Производя усреднение для результирующей матрицы Y = V 2 ₄+ V ₂₅, получаем восстановленный ряд (рис. 1).

Рис. 1. Графики рядов (для примера 1): чистого, с шумом и восстановленного

Гашение шума составило W = 11,4 % от исходного шума.

Пример 2. Ряд с сезонными составляющими, средние помехи;

х = I ⁽ I ⁶⁰⁾ + 5sin( i ), I = 0, 1, _, 59, N = 60, .     100

L = 30; R , - равномерно распределенная случайная величина из промежутка [-3; 3]. Матрица S имеет размеры 30 х 30 и 30 собственных чисел X , (табл. 2).

В качестве индексов группировки выбираются числа с 27 по 30 как соответствующие наиболее значимым составляющим (стоит отметить, что они не обязаны быть последними, хотя такое довольно часто происходит). Им соответствуют элементарные матрицы V ₂₇, V 28 , V ₂₉ и V ₃₀. Производя усреднение для результирующей матрицы Y = V ₂₇ + V 28 + V ₂₉ + V ₃₀, получаем восстановленный ряд (рис. 2).

Гашение шума составило W = 25,6 % от исходного шума.

Пример 3. Ряд с несколькими сезонными составляющими, сильные помехи; х , = 0,03 i + 1,6 sin(0,3 i + 0,17) + 1,3 sin(2 i + 0,57), I = 0, 1, ^, 49, N = 50, L = 15; R , - нормально распределенная случайная величина, с = 3. Матрица S имеет размеры 15 х 15 и 15 собственных чисел X , (табл. 3).

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

Рис. 2. Графики рядов (для примера 2): чистого, с шумом и восстановленного

Гашение шума при взятии трех наиболее значимых компонент составляет W = 21,8 %, для четырех - W = 29,2 % и для пяти - W = 34,6 % .

Результаты для трех выделенных компонент приведены ниже (рис. 3).

Рис. 3. Графики рядов (для примера 3): чистого, с шумом и восстановленного

По результатам проведенных испытаний можно сделать вывод, что базовый алгоритм метода «Гусеница-SSA» справляется с поставленной для него задачей: для временного ряда отделяет тренд и периодики от помех, снижая уровень шумов в 2–3 раза; при этом изначально неизвестно, какой тип будут иметь значимые компоненты: линейный, периодический, логарифмический или иной. Это является достоинством данного метода, что в перспективе позволит создать мощный механизм непараметрического анализа временных рядов, в том числе и в виде программ для ЭВМ.

Недостатками же базового алгоритма метода «Гусе-ница-SSA» являются необходимость вмешательства человека для анализа разделенных компонент и проблема выбора длины окна, от которой зависит качество разделения аддитивных составляющих. Дальнейшие исследования будут направлены на автоматизацию процесса анализа и использование других методов, улучшающих качество результатов работы алгоритма и уменьшающих вмешательство человека в этот процесс.