к библиотеке к оглавлению к дискретной математике технологии программирования

Метод SSA (Singular Spectrum Analysis)

(Метод SSA - "Гусеница": базовый алгоритм)

Описание базового алгоритма
Развертка одномерного ряда в многомерный
Анализ главных компонент
Отбор главных компонент
Восстановление одномерного ряда
Выбор параметров при применении метода "Гусеница"
Выбор длины гусеницы
Отбор главных компонент

Описывается базовый алгоритм анализа одномерных временных рядов, реализуемый методом "Гусеница" (Singular Spectrum Analysis), проанализированы его этапы. Обсуждается выбор параметров ппри применении метода: выбор длины гусеницы, отбор главных компонент. Даются полезные рекомендации относительно этого метода.

Описание базового алгоритма

Рассмотрим временной ряд {x_i}^N_i₌₁, образованный последовательностью N равноотстоящих значений некоторой (возможно, случайной) функции f(t):

x_i = f((i-1)Dt), где i=1,2,…,N.

Отметим, что существует несколько вариантов базового алгоритма, здесь мы опишем лишь минимальный.

Базовый алгоритм метода "Гусеница" можно разбить на четыре этапа.

Этап 1. ( Развертка одномерного ряда в многомерный )

Выберем некоторое число M<N , называемое длиной гусеницы, и представим первые M значений последовательности f в качестве первой строки матрицы X . В качестве второй строки матрицы берем значения последовательности с x₂ по x_M₊₁. Последней строкой с номером k = N – M + 1 будут последние M элементов последовательности. Эту матрицу, элементы которой равны x_ij = x_i+j-₁, можно рассматривать как M – мерную выборку объема k или M – мерный временной ряд, которому соответствует M – мерная траектория (ломаная в M – мерном пространстве из k-1 звена. Отметим, что матрица X (будем называть ее матрицей ряда) представлена в традиционном для прикладной статистики виде "строка – индивид, столбец – признак". При изложении теоретических аспектов естественным является сопоставление индивиду столбца.

Далее по обычной схеме (за исключением стандартизации признаков) проводится анализ главных компонент (АГК).

Этап 2. ( Анализ главных компонент: сингулярное разложение выборочной ковариационной матрицы )

Сначала вычисляется матрица V = (1/k)X^TX. Несмотря на то, что ее элементы не центрированы, мы будем называть ее ковариационной матрицей, иногда добавляя слово "нецентральная".

Следующий шаг, как обычно в АГК, состоит в вычислении собственных чисел и собственных векторов матрицы V , т.е. разложение ее V = PLP^T, где L – диагональная матрица, на диагонали которой стоят упорядоченные по убыванию собственные числа, а P – ортогональная матрица собственных векторов матрицы V.

Матрицы L и P совместно имеют множество интерпретаций, основанных на АГК. В частности, матрицу P можно рассматривать как матрицу перехода к главным компонентам XP = Y = (y₁,y₂,...,y_M).

Если изучается выборка из случайной совокупности, то собственные числа матрицы V являются выборочными дисперсиями соответствующих главных компонент, а квадратные корни из них – выборочными стандартами. Графическое представление собственных чисел и некоторых функций от них в АГК традиционно используется для выявления структуры исследуемой совокупности и отбора и интерпретации главных компонент.

Заметим также, что при выборе длины гусеницы, равной N-M+1 , собственные вектора и главные компоненты (с точностью до нормировки) просто меняются местами.

Этап 3. ( Отбор главных компонент )

В силу свойств матрицы P мы можем представить матрицу ряда X как X = Y P^T. Таким образом, мы получаем разложение матрицы ряда по ортогональным составляющим (главным компонентам).

В то же время преобразование y_j = X p_j является линейным преобразованием исходного процесса с помощью дискретного оператора свертки, т.е.

y_j[l] = S^M_q₌₁x_lqp_jq=S^M_q₌₁x_l+q-₁ p_jq.

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

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

В частности, среди главных компонент можно выделить

относящиеся к тренду (медленно меняющиеся),
периодические,
шумовые.

Для нахождения периодических составляющих чрезвычайно большую визуальную информацию дает изучение двумерных графиков, аналогичных фигурам Лиссажу, когда по осям x и y откладываются различные пары собственных векторов или главных компонент. Известно, что, если по осям откладывать значения синусоиды одной и той же той же частоты, но с разными фазами, то на плоскости получается эллипс. Из ортогональности собственных векторов и главных компонент следует, что сдвиг фаз между такими парами обязательно будет равен ±p/2 и эллипс переходит в окружность.

Этап 4 . ( Восстановление одномерного ряда )

Следующим ключевым элементом метода "Гусеница" является процедура восстановления. Эта процедура основана на разложении X = Y P^T. Будем говорить, что восстановление проводится по данному набору главным компонентам, если при применении формулы восстановления X = Y^* P^T матрица Y^* получена из матрицы Y обнулением всех не входящих в набор главных компонент. Таким образом, мы можем получить интересующее нас приближение матрицы ряда или интерпретируемую часть этой матрицы.

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

Отметим сразу одну очень важную особенность описанного метода – его интерактивность, то есть использование диалога исследователя и ЭВМ в процессе применения метода. Причем эта интерактивность не должна рассматриваться как следствие общей тенденции развития современного программного обеспечения персональных ЭВМ. Скорее, наоборот, эффективная реализация алгоритма стала возможной только благодаря возможностям современных ПК. Его интерактивность связана с типично статистическим свойством алгоритма – необходимостью интерпретации промежуточных результатов и управлением работой алгоритма в процессе многоэтапной процедуры обработки. Опыт многолетнего использования различных реализаций алгоритма на ЭВМ разных поколений показал, что чем больше промежуточных результатов удается "увидеть", тем более полным оказывается решение поставленной задачи.

Заметим, что при программной реализации этапы приведенного выше алгоритма не воспроизводятся непосредственно. Например, этап построения матрицы X отсутствует, а формулы преобразованы к виду удобному для проведения ускоренных вычислений.

Выбор параметров при применении метода "Гусеница"

Выбор длины гусеницы.

Как видно из описания метода, основным управляющим параметром метода является M – длина гусеницы.

При геометрической интерпретации этот параметр является размерностью пространства, в котором исследуется траектория многомерной ломаной линии, в которую переводится исходный временной ряд процедурой гусеница. Естественным условием является M<N/2 , так как размерность множества k точек (вершин ломаной) в M -мерном пространстве не превосходит min(M,k-1). Этот подход тесно связан с аналитической интерпретацией метода гусеница как аппроксимацией решения уравнения в конечных разностях с l коэффициентами. Можно сказать, что l – это число степеней свободы функции f(t), а следовательно, и соответствующего ей временного ряда. В процедуре "Гусеница" это выразится в том, что при M>l у ковариационной матрицы окажется только l ненулевых собственных чисел (учитывая ограниченную точность вычислений, остальные M-l будут почти нулевые). Однако, в реальных исследованиях эта ситуация достаточно редкая.

В общем случае выбор длины гусеницы существенно зависит от задачи, решаемой этим методом. Рассмотрим три наиболее типичных и исследованных разработчиками случая.

Если решается задача анализа исходного временного ряда, например, с целью отыскания скрытых периодичностей с неизвестными периодами, то можно посоветовать брать длину гусеницы, равную половине длины ряда (или, если ряд длинный, то такую, которую позволяет использовать компьютерные ресурсы).
Если решается более узкая задача, например, сглаживание исходного ряда или выделение периодичности с известным периодом, то работает другой механизм, связанный с "Гусеницей" – механизм фильтрации. Как уже отмечалось в разделе 1, выделение некоторой главной компоненты в M -мерном представлении исходного временного ряда эквивалентно пропусканию ряда через фильтр, переходная функция которого совпадает с собственным вектором этой компоненты. Спектральная функция фильтра равна преобразованию Фурье этого собственного вектора. Ширина полосы пропускания зависит от формы переходной функции фильтра и определяется как видом собственного вектора, так и длиной интервала усреднения, т.е. длиной гусеницы M . Чем больше M , тем уже может быть сделана полоса фильтра. Выбор нескольких главных компонент эквивалентен параллельному соединению соответствующих фильтров, что позволяет управлять формой спектральной характеристики.
Еще один случай выбора M – при необходимости наилучшего выделения (или исключения) периодического, не обязательно гармонического, колебания с известной частотой и, следовательно, периодом. В этом случае бывает необходимо для лучшего решения задачи изменить длину временного ряда N (естественно, в сторону уменьшения). Из теории метода следует, что периодические колебания наилучшим образом выделяются, если M и N кратны длине периода выделяемого колебания.

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

Отбор главных компонент

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

Для этих двух представлений имеется 4 набора интерпретируемых объектов:

Собственные числа ковариационной матрицы M – мерного представления исходного одномерного ряда. Их интерпретация во многом сходна с АГК.
Набор собственных векторов ковариационной матрицы. Поскольку их элементы упорядочены оператором формирования матрицы ряда (гусеницей), их можно изучать как функции времени (точнее, временные ряды длины M).
Набор главных компонент M – мерного представления. Они, как и соответствующие им собственные векторы, образуют ортогональную систему и так же представимы как функции от номера элемента.
Всевозможные восстановленные по разным множествам главных компонент временные ряды, получаемые в результате последовательного применения двух обратных операторов (оператора перехода от главных компонент к исходному M – мерному представлению и оператора перехода от M – мерного (матрицы ряда) к одномерному (собственно ряду) представлению временного ряда).

Еще раз отметим два крайних случая, где логика отбора несколько отличается:

При M<<N более естественным кажется интерпретация собственных векторов как переходных функций линейных фильтров, а соответствующих главных компонент как результатов действия этих фильтров. Здесь применима терминология, связанная с линейной фильтрацией такая, как "ширина полосы пропускания", фильтры "высоких и низких частот" и тому подобные термины спектрального подхода.
При M близком к N/2 метод гусеница можно интерпретировать как метод аппроксимации исходного временного ряда рядами конечного ранга. Здесь более уместен геометрический подход к интерпретации отдельных шагов и результатов применения метода. Наиболее простым является поиск гармонических компонент исследуемого процесса. Как уже отмечалось при изложении основ теории метода, каждому синусоидальному слагаемому ряда соответствуют две главные компоненты, имеющие вид отрезков синуса и косинуса одной и той же частоты. Их легко обнаруживать по двумерным графикам для пар собственных векторов ковариационной матрицы или пар соответствующих главных компонент. Кроме того, для таких пар собственные числа обычно оказываются достаточно близкими, поэтому оказывается возможным угадывать эти пары по графику собственных чисел или квадратных корней или логарифмов из них.

Источник: http://www.gistatgroup.com/gus/index.html
http://www.gistatgroup.com/gus/book1/index.html

к библиотеке к оглавлению визуальные среды - 4GL технологии программирования

Знаете ли Вы, что только в 1990-х доплеровские измерения радиотелескопами показали скорость Маринова для CMB (космического микроволнового излучения), которую он открыл в 1974. Естественно, о Маринове никто не хотел вспоминать. Подробнее читайте в FAQ по эфирной физике.

НОВОСТИ ФОРУМА

Рыцари теории эфира