автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Разработка программного комплекса автоматического выделения и прогноза аддитивных компонент временных рядов в рамках подхода "Гусеница"-SSA

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи

Александров Фёдор Игоревич

РАЗРАБОТКА ПРОГРАММНОГО КОМПЛЕКСА АВТОМАТИЧЕСКОГО ВЫДЕЛЕНИЯ И ПРОГНОЗА АДДИТИВНЫХ КОМПОНЕНТ

ВРЕМЕННЫХ РЯДОВ В РАМКАХ ПОДХОДА <ТУСЕНИЦА"-ЗЗА

05.13.18 — Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

диссертации на соискание ученой степени

Работа выполнена на кафедре статистического моделирования математико-механического факультета Санкт-Петербургского государственного университета

Научный руководитель: доктор физико-математических наук,

профессор Ермаков Сергей Михайлович

Официальные оппоненты: доктор физико-математических наук,

профессор Егоров Владимир Алексеевич

доктор физико-математических наук, доцент Тайбин Борис Залманович

Ведущая организация: Санкт-Петербургский государственный

политехнический университет

Защита состоится

2006 г. в /•/ часов

на заседании диссертационного совета Д 2Й.232.51 по защите диссертаций на соискание ученой степени доктора наук при СПбГУ по адресу: 198504, Санкт-Петербург, Старый Петергоф, Университетский пр., 28.

С диссертацией можно ознакомиться в научной библиотеке им. М. Горького СПБГУ по адресу: 199034, Санкт-Петербург, Университетская наб., 7/9.

Автореферат разослан _ __

2006 г.

Ученый секретарь диссертационного совета, доктор фиэ.-мат. наук, профессор 'ТИ1Ч|, Мартыненко Б. К.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Работа посвящена:

• разработке математических методов автоматической идентификации для задач выделения и прогноза аддитивных составляющих одномерных временных рядов в рамках общего подхода "Гусеница1-БЭЛ;

• созданию на их базе алгоритмов, позволяющих решать задачи выделения аддитивных составляющих ряда как интерактивно, так и при пакетной обработке данных, и реализация их в виде программного комплекса;

• исследованию качества данных алгоритмов при решении поставленных задач;

• исследованию метода оценки коэффициентов линейной рекуррентной формулы, управляющей сигналом временного ряда для случая, когда ряд соответствует модели "сигнал плюс шум".

Актуальность темы следует из:

• практической значимости задач выделения и прогноза аддитивных составляющих одномерных временных и пространственных рядов в различных областях прикладной науки;

• необходимости автоматизации решения этих задач как при работе с одним рядом, так и для пакетной обработки;

• отсутствия на данный момент методов и алгоритмов, позволяющих решать данные задачи в рамках подхода "Гусеница'-ЗЭ А.

Целью работы является: 1) разработка новых теоретически обоснованных методов для выделения и прогноза таких аддитивных составляющих временных рядов, как тренд и периодические составляющие; 2) разработка алгоритмов для автоматической обработки временных рядов на основе предложенных методов и реализация этих алгоритмов на ЭВМ; 3) статистическое исследование данных алгоритмов; 4) исследование методов оценки параметров сигнала ряда.

Методика исследования включает в себя применение подхода "Гусеница'-ЗЗА, теорию сингулярного разложения матриц, использование свойств их собственных значений и собственных векторов, основы

обработки цифровых сигналов, методы разложения Фурье, регрессионные методы. Численные оценки получались с помощью методов статистического моделирования. Для реализация алгоритмов использовались средства программирования Microsoft Visual С++ и Matlab.

.Научная новизна. В работе получены следующие результаты:

• разработаны математические методы автоматического выделения и прогноза тренда и периодической составляющей ряда, управляемые заданием параметров и пороговых значений;

• описаны рекомендации по выбору параметров методов исходя из специфики поставленной задачи и предложены способы выбора пороговых значений для рассматриваемого ряда;

• на модельных примерах с помощью статистического моделирования исследовано качество предоставляемой автоматизации в рамках подхода "Гусеница'-SS А и качество получаемой аппроксимации;

• представлено решение задачи выделения тренда для множества рядов, исследованы вопросы проверки работоспособности методов в данном случае;

• проведено статистическое сравнение метода оценки коэффициентов линейной рекуррентной формулы, основанного на подходе Тусеница'-SSA с регрессионным методом, основанным на оценке метода наименьших квадратов.

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

Апробация работы. Основные результаты обсуждались на:

• семинарах кафедры статистического моделирования математико-механического факультета Санкт-Петербургского государственного университета;

• семинаре Time Series group в Astronomical Institute of Tübingen

(Тюбинген, Германия, март 2005); .

• семинарах в Zentrum für Tecbnomatematik, Bremen University (Бремен, Германия, март 2005, март 2006);

и докладывались на

• международной конференции System Identification and Control Probiems'05, (Москва, январь 2005);

• международном семинаре 5th Workshop on Simulation (Санкт-Петербург, июнь 2005);

• международном семинаре Workshop on nonlinear and nonstationary time series in Kaiserslautern (Кайэерслаутерн, Германия, сентябрь 2005);

• международном симпозиуме 26th International Symposium on Forecasting (Сантавдер, Испания, июнь 2006).

Работа над диссертацией была частично поддержана стипендией Правительства РФ для аспирантов за 2005-2006 гг. и грантами CRDF № RUB 1-1556-ST-05, № RUB1-1643-ST-06.

Публикации. Основные результаты диссертации опубликованы в работах [1-5J. В совместных работах диссертанту принадлежит выбор методов решения, доказательства теорем и численное моделирование, а соавтору Голяндиной Н.Э. — постановки задач [1,4], а также идея метода низких частот идентификации трендовых составляющих [1] и описание схемы расчёта оптимальных пороговых значений для временных рядов фиксированной модели [2]. - -

Структура и объем работы. Диссертация объёмом 152 страницы состоит из введения и четырёх глав, разбитых на разделы и параграфы. Содержит 145 рисунков, 36 таблиц и список цитируемой литературы из 69 наименований. -

СОДЕРЖАНИЕ РАБОТЫ

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

Основным объектом исследования является одномерный временной ряд — последовательность вещественных чисел Р = (/о, /ь — 1 /N-1) длины N. Обычно это наблюдения в равноотстоящие моменты времени, но, несмотря на название, эта последовательность может иметь другую природу. Примеры пространственных рддов приводятся в диссертация. Предполагаем, что ряд состоит из суммы аддитивных составляющих, из которых наиболее интересны тренд и периодическая состав-

ляющая с некоторым периодом

р = р(т) + + > /п = дт) + ДР) + /(н>)

где в качестве обозначаем остаток, являющийся реализацией некоторой случайной последовательности. соответствует шуму, который имеет случайную природу и часто присутствует в наблюдениях. Трендом будем называть медленно меняющуюся составляющую ряда (для определённости полагаем, что она не является периодической). Периодическую составляющую с периодом Т (Т ^ 2) определим следующим образом:

[Т/2]

' = X) ™к/Т + фк), ак,Ак еЕ.^е [0,2тг). (1)

к=1

Основной задачей является выделение из известного ряда Р неизвестных составляющих п Целью диссертации является разработка методов для решения этой задачи, которые можно использовать для автоматизированной обработки рядов. Для этого используется общий подход исследования временных радов 'Тусеница"-83А.

Первая глава содержит информацию о подходе нГусеница"-&5А, которая потребуется для решения поставленных задач. В рамках этого подхода описываются уже существующие интерактивные способы решения задач выделения тренда и периодических составляющих временных рядов, а также рассматриваются условия, при которых возможно решение этих задач.

Для того чтобы выделить аддитивную составляющую ряда Р длины И, Р — ^(Ч в подходе "Гусеница"-38А по ряду Р строится тпраек-

тпорная матрица X заданного размера ЬхК, 1 < Ь < N, К = N (Ь называется длиной окна), вычисляются собственные числа

собственны« и факторные вектора матрицы ХХГ, фор-

мируя сингулярное разложение X = Х^, X* = Набор

(У'Хь У к) будем называть к-ой собственной тройкой.

Затем выделяется группа собственных троек с номерами из некоторого X и определяется матрица Х'1^ = Х^, по которой восстанавливается требуемая составляющая с помощью диагонального усреднения (ганкелизации).

Эта схема имеет параметр - длину окна Ь и управляется выбором группы компонент 2", процесс этого выбора будем называть идентификацией. Нашей основной задачей будет автоматизация идентификации при решении поставленных задач.

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

В разделе 2.1 приводятся данные, необходимые для определения тренда на языке разложения Фурье. Дня элементов ряда Р вводится периодограмма Пр, определённая на дискретном множестве частот:

п£М = £

лг-1

п=0

軈

Так как по определению тренд — это последовательность, элементы которой медленно меняются, то его периодограмма в некоторой низкочастотной области будет иметь большие значения по сравнению с её значениями на остальной части частотного интервала [0,0.5], причём периодограммы собственных векторов, соответствующих тренду, обладают этим же свойством.

Введём шо - границу интервала низких частот и в разделе 2.2 построим метод низких частот идентификации трендовых собственных троек, который для каждого собственного вектора будет проверять, достаточно ли велик вклад значений его периодограммы на интервале [0,шо]- Критерий идентификации собственного вектора ?7 € К.1, выглядит так:

где Со - пороговое значение метода. На основе этого метода построен . алгоритм Trend для выделения тренда ряда, параметрами которого являются wq и пороговое значение Cq.

В разделе 2.3 изучается проблема выбора ljq и предлагаются варианты её решения в зависимости от специфики поставленной задачи и имеющейся информации о ряде. Основной способ состоит в исследовании периодограммы исходного рада F, так как в утверждении 2.1 доказано, что в случае, если F = G + Hi

|П£+„<*/Л0 - nif(fcyW)| < 2^n%(k/N)il%(k/N). (2)

Так как, в отличие or периодограмм других составляющих, периодограмма тренда имеет большие значения в низкочастотном интервале, то из (2) следует, что, при наличие в ряде тренда, значения в низкочастотном интервале также будут большими,

В разделе 2.4 проводится статистическое исследование алгоритма Trend для решения задачи выделепня экспоненциального тренда в присутствии белого нормального шума с изменяющейся дисперсией. Для такого ряда можно имитировать процедуру визуального выделения тренда, так как известно, что тренду в этом случае соответствует первая собственная тройка (X = {1}). Показано, что при наилучшем в среднем пороговом значении Со, во-первых, результаты алгоритма Trend близки к результатам имитированной визуальной (интерактивной) процедуры идентификации, и, во-вторых, качество предоставляемой им аппроксимации достаточно высоко. Качество оценивается с помощью как среднеквадратичной ошибки — Р(т'(Со)1!з (где ^т'(Со) — тренд,

выделенный с помощью Trend с Со), так и вероятности ошибки идентификации первого рода - когда Х(Со) ^ X (где Х(Со) — группа идентифицированных с помощью Trend с Со компонент).

Таким образом, установлено, что при некотором Со процедура Trend действительно может быть использована для автоматического выделения тренда, и встаёт проблема выбора Cq. .

Далее исследуется вопрос оценки качества результата алгоритма Trend и в разделе 2.6 предлагается некоторая мера качества 7£(Со), которая рассчитывается только по результату, F^ (Со), и для которой показано, что в рассмотренных модельных случаях она согласована с

||jr(T) —FÍTi(Co)||2 таким образом, что используя меру TL{C^), можно выбрать такое пороговое значение Со, что при нём идентифицируются все компоненты тренда. Предлагается алгоритм TrRmeas, использующий процедуру Trend с Cq, выбранным с помощью TC(Cq) .

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

В разделе 2.8 приводятся примеры выделения тренда с помощью алгоритма TrRmeas для реальных радов: ежемесячный уровень безработицы в различных штатах США н уровень экспрессии некоторых генов плодовой мушки Drosophila. Два примера изображены на рис. 1.

Рис. 1: Уровень безработицы во Флориде (слева) и пространственное распределение уровня экспрессии гена ЬипсЬЬ в эмбрионе плодовой мушки ОгозорЫ1а (справа), тренды выделены с помощью ТйКмёаЗ

Для того чтобы применять алгоритм ТиНмеаз к ряду, необходимо, чтобы выполнялись некоторые требования, обусловленные свойствами как подхода"Гусёница'-ЗЗА, так и метода'низких частот и способа выбора Со- Не имея информации о модели ряда, проверить эта требования невозможно, и применение алгоритма ТяЯмБАв, строго говоря, необоснованно. В разделе 2.9 исследуется эха проблема и рассматривается случай, для которого возможно проверить обоснованность .применения ТяКмбаз - обработка множества рядов. Описывается математическая

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

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

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

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

Известно, что при выполнении определённых условий экспоненциально-модулированная (э-м) гармоническая составляющая с частотой и (или просто э-Л4 гармоника), п-ый элемент которой задаётся так:

Аеап со8(2тгт> + а,АеЖ, ф 6 [0,27т],

порождает две собственных тройки (одну, если ш = 0.5), элементы собственных векторов Щ — (и^.и^,...которых также задаются э-м гармонической функцией с теми же «на, причём одному соответствует э-м синус, а другому — э-м косинус. При более слабых условиях это будет выполняться приближённо!

Пользуясь этим фактом, построим в разделе 3.2 метод Фурье дня идентификации собственных векторов э-м гармоники, основанный на

исследовании периодограмм последовательностей их элементов Пу^. Метод Фурье состоит из двух частей, в первой для пар векторе® вида Ui, ¡7i+i проверяется, что максимумы их периодограмм совпадают или достаточно близки:

вз = (3)

где so е Z+ — пороговое значение. Во второй — для найденных пар векторов проверяется, что значение максимума превышает уровень, необходимый для того, чтобы они соответствовали э-м гармонике:

отах/2{П&( (к/Ь) + П&(+1 (к/Ь) } > 2ро, (4)

где ро е [0,1] - пороговое значение. На основе этого метода идентификации предлагается алгоритм Per выделения э-м гармонической составляющей ряда, параметрами которого являются L, so и ро- В разделе также численно и аналитически изучается поведение критериев (3), (4) для э-м гармоник с разными параметрами w, а, и показано, что в большинстве случаев можно брать so = 1.

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

■ В следующих разделах описаны способы выбора ро при решении задачи выделения э-м гармонической компоненты с помощью алгоритма Per. Предлагается аналитический метод, позволяющий выбрать ро для выделения э-м гармоники с известным а при условии, что Iaj eN. Этот метод заключается в использовании для э-м гармонической последовательности с частотой cj оценки значения суммы периодограмм её собственных векторов в точке и>, которая была получена в разделе 3.2.2:

П£» а где 7 = La.

Однако то, что а зачастую неизвестно, а также накладываемое ограничение Llj ейи другие причины делают этот метод полезным только

в частных случаях. Поэтому далее предлагается эмпирический метод выбора /сто- На его основе предлагается алгоритм РееЕмр автоматического выделения гармоники, параметрами которого являются: Ь и А — ограничение снизу на амплитуду искомой гармоники. При выделении э-м гармоники алгоритм можно сделать более точным, задав ограничение снизу на а и приблизительное значение частоты искомой э-м гармоники ь/, если они известны. .

т&м же приведено статистическое исследование алгоритма Рей,Емр, которое подтверждает хорошее качество данного алгоритма как: для модели + где - шум, так и в присутствии некоторого

тренда: Г<т> + +

' Так как периодическая составляющая с периодом Т состоит из суммы э-м гармонических компонент с частотами вида кш, из = 1/Т (см. (1)), то для её выделения необходимо уметь оценивать частоту найденной э-м гармонической компоненты. В разделе 3.6 рассмотрен метод оценки частоты, который использует линейное рекуррентное представление э-м гармоники /п — Аеап соз(27гып 4- ф) = аг/п—г + йг/п—2:

ш(а1,аз) = (2тт)-1 агссоз(а1.(2^^2)-1)- (5)

В разделе 3.7 приводится пример применения алгоритма РеиЕмр к ряду, содержащему данные, о ежемесячном уровне потребления электроэнергии в США. Приводится решение задачи разложения [»яда- на тренд, сезонную составляющую (периодическую составляющую с периодом Т и 12) и остаток, см. рис. 2.

В разделе 3.8 представлен алгоритм автоматического прогноза, периодической составляющей и, как и в главе 2, с помоптью статистического моделирования показано, что данный алгоритм при наилучшем в среднем ро близок к имитированному визуальному (интерактивному) прогнозу и что это пороговое значение близко к наилучшему с среднем ро Для аппроксимации. Это позволяет использовать при прогнозе уже сформулированные ранее для аппроксимации методы выбора ро~

Четвертая глава посвящена задаче оценки коэффициентов линейной рекуррентной формулы (ЛРФ) сигнала ряда, где ряд .Р* = (/о,..., /лг—1) соответствует модели "сигнал плюс шум". Исследу-

»тшштШШШШ

-5 [-Беазопа! соторопепд

1972 1977 1982 1987 1992 1997 2002

Рис. 2: Ежемесячный уровень потребления электроэнергии в США, тренд выделен с помощью ТиПМЕАв, сезонная составляющая - с помощью РеиЕмр с параметрами Ь — 198, А = 1

ется случай, когда сигнал представляет собой гармонику:

и = + е„, = А а!п(2х(длг + ф),

которой в рекуррентной записи соответствует ЛРФ порядка 2 (то есть = + йа^п-а). а остаток (е0,^N-1) - реализация белого

нормального шума, каждый элемент которого распределён по N(0, ет2). Ставится задача оценки коэффициентов <ц, «а и через них частоты ы по (5).

В разделе 4.1 описаны два метода оценки а\, а^. Первый, БэлЬяр, основан на подходе 'Тусеница"-83А, с помощью которого находится ЛРФ порядка 2 для сигнала. Второй метод, Нес Я, использует регрессионную запись для и оценивает коэффициенты <11, а? по методу наименьших квадратов.

Методы сравнивались с помощью статистического моделирования рядов Р, для которых оценивались и и и для каждого метода и параметра рассчитывались: абсолютное отклонение выборочного среднего от настоящего значения и выборочная дисперсия. Исследования проводились при различных значениях Ы, а, причём при фиксирован-

ном значении одного из них другой изменялся с заданным шагом.

Метод БэлЬкр в достаточно большой области параметров показал результаты лучшие, чем метод Ябоя (при не слишком больших о или при достаточно большом ЛГ), что видно на рис. 3, на котором изображены результаты при N = 60, о» = 1/6, А = 1, ф = 0, оцененные на 104 реализациях.

Рис. 3: Зависимость от стандарта шума <т характеристик оценок из алгоритмами ЗвлЬяр и Кесзд

Основные положения диссертации, выносимые па защиту.

• Разработаны математические методы автоматической идентификации собственных троек, соответствующих тренду или периодическим составляющим в рамках подхода <1Гусеница"-53А;

• Созданы и реализованы в виде программного комплекса алгоритмы выделения тренда и периодических составляющих, использующие предложенные методы;

• Рассмотрены способы выбора параметров и пороговых значений алгоритмов;

• Проведено статистическое исследование качества работы алгоритмов при наилучших в среднем пороговых значениях;

• Построена математическая модель применения алгоритма выделения тренда к множеству рядов;

• Представлены результаты обработки временных и пространственных рядов с помощью предложенных алгоритмов;

• Выполнено статистическое сравнение подхода Тусеница''-SSA и регрессионного метода при оцеики коэффициентов ЛРФ порядка 2 для периодического сигнала.

СПИСОК ОПУБЛИКОВАННЫХ РАБОТ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Александров, Ф. И. Оценка коэффициентов линейной рекуррентной формулы порядка 2, управляющей сигналом / Ф. И. Александров // Мат. модели. Теория и приложения. — 2004. — вып. 5. — С. 50-61. — ISBN 5-9651-0082-5.

2. Александров, Ф. И. Выделение аддитнвпых компонент временного ряда при пакетной обработке методом 'Тусеиица'-SSA / Ф. И, Александров // Вестник СПбГУ, Сер. 1. Математика. Механика. Астрономия. — 2006. — № 2. — С. 71-74. — ISSN 1025-3106.

3. Александров, Ф. И. Автоматизация выделения трендовых и периодических составляющих временного ряда в рамках метода 'Тусеница''-SSA / Ф. И. Александров, Н. Э. Голяндина // Exponenta Pro. Математика в приложениях. — 2004. — вып. 3-4. — С. 54-61.

4. Александров, Ф. И. Выбор параметров при автоматическом выделении трендовых и периодических составляющих временного ряда в рамках подхода 'Тусеница''-SSA / Ф, И. Александров, Н. Э. Голяцдина, IV Международная конференция "Идентификация систем и задачи управления" SICPRO'05, Москва, январь 2005 // Труды IV Международной конференции "Идентификация систем и задачи управления". - М.: 2005. — С. 1849-1864. — ISBN 5-201-14975-8.

5. Alexandrov, F. Automatic extraction and forecast of tiine series cyclic components within the framework of SSA / F. Alexandrov, N. Golyandina, 5th St.Petersburg Workshop on Simulation, St.-Petersburg, June 2005 // Proc. of the 5th St.Petersburg Workshop on Simulation. - SPb.: 2005. — p. 45-50. — ISBN 5-9651-0102-3.

Подписано в печать 09.11.2006. Формат 60x84/16. Бумага офсетная. Печать офсетная. Усл. печ. л. 0,93, Тираж 100 экз. Заказ № 70.

Типография Издательства СПбГУ. ' 199061, С.-Петербург, Средний пр.. 41.

Введение

Глава 1. Подход "Гусеница''-SSA для анализа и прогноза временных рядов

1.1 Базовый алгоритм.

1.1.1 Разложение.

1.1.2 Восстановление.

1.1.3 Комментарии к алгоритму

1.1.4 Выбор параметра L — длины окна.

1.2 Разделимость рядов.

1.2.1 Приближённая и асимптотическая разделимость.

1.3 Ряды конечного ранга.

1.3.1 Примеры рядов конечного ранга.

1.4 Прогноз аддитивной составляющей

1.4.1 Вычисление коэффициентов ЛРФ порядка L — 1.

1.4.2 Минимизация линейной рекуррентной формулы.

Глава 2. Автоматический метод выделения тренда

2.1 Вводные данные.

2.2 Описание метода низких частот для идентификации трендовых компонент.

2.3 Выбор параметра loq.

2.4 Проверка метода для модели с известной трендовой составляющей

2.4.1 Расчёт ошибки АИ при наилучшем в среднем Со с помощью моделирования.

2.4.2 Поведение автоматической процедуры с Cq^ при изменении параметров а, а.

2.4.3 Зависимость ошибки от Со.

2.4.4 Общие соображения по выбору Со

2.5 Оценка качества выделения тренда

2.5.1 Требования к мере качества выделения тренда.

2.5.2 7^-мера качества выделения тренда

2.6 Выбор порогового значения Cq на основе меры 7Z.

2.6.1 Стах — пороговое значение, при котором идентифицируются все трендовые собственные тройки.

2.6.2 Вычисление Стах с помощью меры Л.

2.6.3 Примеры поиска Стах с помощью меры 7Z.

2.6.4- Сравнение Стах и CqPL для экспоненциального тренда 52 2.6.5 Описание процедуры TrR,MEAS автоматического выделения тренда ряда.

2.7 Случай известной модели шума

2.8 Примеры выделения трендов реальных рядов.

2.8.1 Исследование уровня экспрессии гена.

2.8.2 Выделение тренда различной детализации из данных по уровню безработицы.

2.8.3 Сравнение процедуры TR.RMEAS с другими методами выделения тренда.

2.9 Применение процедуры автоматического выделения тренда для обработки множества рядов.

2.9.1 Проблема проверки качества процедуры TrRmeas

2.9.2 Математическая постановка задачи, оценка ошибки автоматической процедуры и её свойства.

2.9.3 Схема применения TrR,MEAS к множеству рядов

2.10 Пример применения процедуры TrRmeas к множеству рядов

2.11 Прогноз тренда.

2.11.1 Схема прогноза тренда ряда

2.11.2 Проблема выбора порогового значения при прогнозе

2.11.3 Моделирование прогноза экспоненциального тренда

Глава 3. Автоматический метод выделения периодической составляющей

3.1 Отличие задачи выделения тренда от задачи выделения периодической составляющей

3.2 Описание метода Фурье для идентификации э-м гармонических компонент.

3.2.1 Первая часть метода Фурье.

3.2.2 Вторая часть метода Фурье.

3.3 Проверка процедуры PER для модели с известной периодической составляющей.

3.3.1 Расчёт ошибки АН при наилучшем в среднем ро с помощью моделирования.

3.4 Подходы к выбору порогового значения ро

3.4.1 Аналитическое вычисление р$ для известного а и при

Ьше N.

3.5 Эмпирический подход к выбору

3.5.1 Результаты численного исследования

3.5.2 Выделение гармоники в присутствии тренда.

3.6 Оценка частоты выделенной э-м гармоники.

3.7 Пример выделения периодической составляющей реального ряда

3.8 Прогноз периодических компонент.

3.8.1 Моделирование прогноза э-м гармоники.

Глава 4. Оценка коэффициентов линейной рекуррентной формулы порядка

4.1 Методы оценки коэффициентов ЛРФ.

4.1.1 Метод, основанный на подходе "Гусеница'-SSA.

4.1.2 Регрессионный метод.

4.2 Сравнение методов с помощью моделирования.

4.2.1 Значения параметров

4.2.2 Результаты.

Одномерным вещественнозначным временным рядом F длины N (N > 2) будем называть упорядоченную последовательность вещественных чисел F = (/о,. - -, /лг-i)) /п Е Временной ряд чаще всего является результатом последовательных замеров некоторого показателя в равноотстоящие моменты времени, поэтому естественной является следующая интерпретация его элементов: fn = /(АО, где f(t) — некоторая функция, a tn соответствует времени регистрации измерений, хотя это может быть и функция от другого физического параметра, например пространственной координаты [7, 9, 16, 41].

Будем говорить, что ряд F состоит из суммы аддитивных составляющих

Fи обозначать это как F = F^ + F^2\ если ь = й1]+й2\ о^п^м-1.

Проблема выделения некоторой аддитивной составляющей ряда одна из самых общих и часто встречающихся проблем анализа временных рядов.

Среди задач, связанных с выделением аддитивной составляющей, можно назвать: определение глобального поведения ряда (выделение тренда), выделение периодической составляющей или её удаление из ряда (например, так называемое seasonal adjustment [36, 48]), сглаживание ряда (выделение низкочастотной составляющей), отделение детерминированной составляющей ряда от шума (выделение сигнала).

Будем называть периодической составляющей с периодом Т (Т ^ 2) ряд, n-ый элемент которого за,даётся следующим выражением:

Т/2J fP = Y, A^akn cos(27rnfc/T + фк), (0.1) к=1 где Ак, ак Е М, Ак > 0, а фк Е [0,2тг).

Существуют много подходов к определению тренда [56]. Иногда под трендом понимают некоторую параметрическую составляющую ряда, на которую накладываются определённые ограничения, например гладкость или, для полиномиального тренда — его порядок [7, глава 3]. При стохастическом подходе к исследованию временных рядов тренд понимается как нестационарная медленно меняющаяся аддитивная составляющая [52]. В монографии [32] трендом называется медленное изменение среднего уровня1.

1В оригинале — long terra change in the mean level

Будем считать трендом медленно меняющуюся составляющую, описывающую глобальное поведение ряда. Для определённости будем полагать, что она не является периодической. При таком подходе тренд определяется неоднозначно, в главе 2 приводятся примеры выделения трендов одного ряда, которые отличаются детализацией, или, как говорят, разрешением.

Будем предполагать, что ряд содержит следующие аддитивные составляющие: тренд периодическую составляющую F^ и шум случайной природы

Тогда в общем случае рассматриваемая модель временного ряда имеет вид:

F = F<T) + ^P) + FW, т. е. /„ = 4т> + /Р> + где (fu\ ., ftfLi) ~ реализация последовательности случайных величин.

Основная задача данной работы — это выделение из известного ряда F неизвестных составляющих F^ и Будем использовать для этого общий подход к исследованию временных рядов Тусепица''-SSA (см. главу 1). В рамках этого подхода уже существуют методы для решения данных задал, однако они могут быть применены только в интерактивном режиме, так как строятся на визуальном исследовании информации, предоставляемой о ряде.

Целью работы будет разработка и исследование методов выделения и прогноза тренда и периодических составляющих ряда на базе подхода "Гусеница'-SSA, которые позволяют решать поставленные задачи не только интерактивно, по и при пакетной обработке данных. Для решения этой задачи выясним, как построены интерактивные методы выделения аддитивных составляющих [5, 10, 41], и попробуем автоматизировать процедуру визуального исследования.

Кроме того, исследуем свойства метода "Гусеница'-SSA при оценке коэффициентов линейной рекуррентной формулы, управляющей сигналом ряда.

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

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

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

Четвертая глава посвящена задаче оценки коэффициентов линейной рекуррентной формулы сигнала ряда F для случая . В ней рассматривается задача оценки коэффициентов ЛРФ порядка два для периодического сигнала. Предлагаются два метода её решения: один — регрессионный, другой — в рамках подхода "Гусепица'-SSA. Выполнено статистическое исследование по сравнению их качества.

Автор приносит искреннюю благодарность своему научному руководителю С.М. Ермакову, а также пользуется случаем выразить признательность Н.Э. Го-ляндиной за бесценную помощь, оказанную при работе над диссертацией и в процессе написания совместных работ.

Выводы При не слишком большом уровне шума метод SsaLrf, основанный на подходе Тусеиица'-SSA, продемонстрировал лучшее качество, чем метод regr, использующий оценку МНК. Этот результат был зарегистрирован в достаточно большой области параметров, задающих отношение сигнал/шум. Это хорошо характеризует метод SsaLrf и подход "Гусеница''-SSA вообще, ведь он не настроен на работу е рядами одной модели. Единственная информация о ряде, которая использовалась в методе SsaLrf —это его ранг, в то время как метод Regr представляет собой оценку параметров заданной модели.

Этой особенностью метода "Гусеница'-SSA объясняется и тот факт, что при достижении некоторого порога отношения сигнал/шум наблюдается резкое ухудшение качества метода SsaLrf. При слишком большом уровне шума метод SsaLrf выделяет сигнал, всё более непохожий на гармонику. Зависимость качества метода SsaLrf от изменения длины ряда, описанная выше, также объясняется свойствами метода "Гусеница''-SSA.

144

Заключение

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

Исследование продемонстрировало, что качество предложенных алгоритмов во многих случаях близко к качеству существующих в рамках подхода "Гусеница''-SSA визуальных способов интерактивной обработки рядов.

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

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

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

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

Все алгоритмы реализованы в виде комплекса программ. Представлены результаты обработки с их помощью временных и пространственных рядов.

Кратко сформулируем выводы проделанной работы:

Разработаны математические методы автоматической идентификации собственных троек, соответствующих тренду или периодическим составляющим в рамках подхода "Гусеница''-SSA;

Созданы и реализованы в виде программного комплекса алгоритмы выделения тренда и периодических составляющих на основе предложенных методов;

Рассмотрены способы выбора параметров и пороговых значений алгоритмов;

Проведено статистическое исследование качества работы алгоритмов при наилучших в среднем пороговых значениях;

Построена математическая модель применения алгоритма выделения тренда к множеству рядов;

Представлены результаты обработки временных и пространственных рядов с помощью предложенных алгоритмов;

Выполнено статистическое сравнение подхода "Гусеница''-SSA и регрессионного метода при оценки коэффициентов ЛРФ порядка два для периодического сигнала.

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

1. Айвазян, С. Ф. Прикладная статистика. Классификация и снижение размерности / С. Ф. Айвазян, В. М. Бухштабер, И. С. Енюков, Л. Д. Мешал-кин. — М.: Финансы и статистика, 1989. — 607 С.

2. Александров, Ф. И. Выделение аддитивных компонент временного ряда на основе метода "Гусеница": дипломная работа / Александров Фёдор Игоревич, СПбГУ, 2003. 37 С.

3. Александров, Ф. И. Оценка коэффициентов линейной рекуррентной формулы порядка 2, управляющей сигналом / Ф. И. Александров // Мат. модели. Теория и приложения. — 2004. — вып. 5. — С. 50-61. — ISBN 59651-0082-5.

4. Александров, Ф. И. Выделение аддитивных компонент временного ряда при пакетной обработке методом "Гусеница'-SSA / Ф. И. Александров // Вестник СПбГУ, Сер. 1. Математика. Механика. Астрономия. -. 2006.

5. С. 71-74. - ISSN 1025-3106.

6. Александров, Ф. И. Автоматизация выделения трендовых и периодических составляющих временного ряда в рамках метода "Гусеница'-SSA / Ф. И. Александров, Н. Э. Голяндина // Exponenta Pro. Математика в приложениях. 2004. - вып. 3-4. - С. 54-61.

7. Андерсон, Т. Статистический анализ временных рядов / Т. Андерсон. — М.: Мир, 1976. 755 С.

8. Белонин, М. Д. Факторный анализ в нефтяной геологии / М. Д. Белонин, И. В. Татаринов, О. М. Калинин, В. К. Шиманский, О. В. Бескровная, В. В. Гранский, Т. Е. Похитонова М.: ВИЭМС, 1971.

9. Бриллинджер, Д. Временные ряды. Обработка данных и теория / Д. Бриллинджер. М.: Мир, 1980. - 536 С.

10. Голяндина, Н. Э. Метод "Гусеница''-SSA: анализ временных рядов: учеб. пособие / Н. Э. Голяндина. СПб.: ВВМ, 2004. 76 С. ISBN 5-96510019-1.

11. Голяндина, Н. Э. Метод "Гусеница''-SSA: прогноз временных рядов: учеб. пособие / Н. Э. Голяндина. СПб.: ВВМ, 2004. - 52 С. - ISBN 5-96510020-5.

12. Голяндина, Н. Э. Метод "Гусеница''-SSA для анализа временных рядов с пропусками / Н. Э Голяндина, Е. В. Осипов // Мат. модели. Теория и приложения — 2005 — вып. 6. — С. 50-61.

13. Градштейн, И. С. Таблицы интегралов, сумм, рядов и произведений / И. С. Градштейн, И. М. Рыжик, изд-е 4-ое, переработанное при участии Ю. В. Геронимуса и М. Ю. Цейтлина. — М.: Физматгиз, 1963. — 1100 С.

14. Данилов, Д. Л. Главные компоненты временных рядов: метод "Гусеница" / Д. Л. Данилов, А. А. Жиглявский (ред.). — СПбГУ, изд-во Пресском, 1997. 308 С.

15. Дженкинс, Г. Спектральный анализ и его приложения / Г. Дженкинс, Д. Ватте. М.: Мир, 1971. - 287 С.

16. Ивченко, Г. И. Математическая статистика: учеб. пособие для втузов / Г. И. Ивченко, Ю. И. Медведев. М.: Высш. шк., 1984. - 248 С.

17. Кислицин, М. М. Многомерная статистика временных рядов наблюдений в авиационной эргономике / М. М. Кислицин // Вопросы кибернетики. Биотехнические системы в авиационной эргономике. — 1978. — вып. 51. — С. 117-126.

18. Колмогоров, А. Н. Об оценке параметров стационарного гауссовского марковского процесса / А. Н. Колмогоров, М. Арато, Я. Г. Синай. — ДАН СССР, 1962, т. 146 С. 747-750.

19. Некруткин, В. В. Разложения временных рядов / В. В. Некруткин // Главные компоненты временных рядов: метод "Гусеница": сб. науч. тр. / ред. Д. Л. Данилов, А. А. Жиглявский. СПбГУ, 1997. - С. 194-227.

20. Allen, M. R. Interactions between the atmosphere and oceans on time scales of weeks to years: Ph.D. thesis, Univ. Of Oxford, / M. R. Allen — Oxford, England, 1992. 202 P.

21. Allen, M. R. Monte Carlo SSA: detecting irregular oscillations in the presence of colored noise / M. R. Allen, L. A. Smith // J. Clim. 1996. - vol. 9. -P. 3373-3404.

22. Baratta, D. Application of an Ensemble Technique based on Singular Spectrum Analysis to Daily Rainfall Forecasting / D. Baratta, G. Cicioni, F. Masulli, L. Studer // Neural Networks. 2003. - vol. 16, № 3-4. -- P. 375387.

23. Bertero, M. Resolution in diffraction-limited imaging, a singular value analysis I. The case of coherent illumination / M. Bertero, E. R. Pike // Optica Acta. 1982. - vol. 29. - P. 727-746.

24. Broomhead, D. S. Extracting qualitative dynamics from experimental data / D. S. Broomhead, G. P. King // Physica D. 1986 - vol. 20. - P. 217-236.

25. Buchstaber, V. M. Time Series Analysis and Grassmannians / V. M. Buchstaber // Amer. Math. SoC. Transl. 1994. vol. 2, № 162.1. P. 1-17.

26. Cadzow, J. A. Signal Enhancement A Composite Property Mapping Algorithm / J. A. Cadzow // IEEE Transactions on Acoustics, Speech and Signal Processing. - 1988. - v. 36. - P. 49-62.

27. Chatfield, C. The Analysis of Time Series: An Introduction / Christopher Chatfield. 2nd eel. - Chapman&Hall, London, 1980 - 268 P.

28. Colebrook, J. M. Continuous plankton records zooplankton and evironment, northeast Atlantic and North Sea, 194-8-1975 / J. M. Colebrook // Oceanol. Acta. 1978. - vol. 1. - P. 9-23.

29. Economagic.com: Economic Time Series Page Электронный ресурс]. — Режим доступа: http://www.economagic.com/.

30. Eisner, J. В. Singular Spectrum Analysis: A New Tool in Time Series Analysis / J. B. Eisner, A. A. Tsonis Plenum, 1996. - 164- P.

31. Findley, D. F. Some Recent Developments and Directions in Seasonal Adjustment / D. F. Findley // Journal of Official Statistics. — 2005. — vol. 21, № 2. P. 343-365.

32. Fisher, R. A. Tests of significance in Harmonic Analysis / R. A. Fisher // Proc. of the Royal Society, Ser. A. 1929. - vol. 125. - P. 54-59.

33. Fraedrich, K. Estimating dimensions of Weather and Climate Attractors / K. Fraedrich // J. Atmos. Sci. 1986. - vol. 43. - P. 419-432.

34. Ghil, M. Advanced spectral methods for climatic time series / M. Ghil, R. M. Allen, M. D. Dettinger, K. Ide, D. Kondrashov, M. E. Mann, A. Robertson, A. Saunders, Y. Tian, F. Varadi, P. Yiou // Rev. Geophys. 2002. - vol. 40, № 1. - P. 1-41.

35. Golyandina, N.E. Analysis of Time Series Structure: SSA and Related Techniques / N. E. Golya,ndina, V. V. Nekrutkin, A. A. Zhigljavsky — Chapman&Hall, 2001 305 P. - ISBN 1-58488-194-1.

36. Golyandina, N. E. The "Caterpillar"-SSA method for analysis of time series with missing values / N. E. Golyandina, E. V. Osipov // Submitted to Journal of Statistical Planning and Inference, 2006.

37. Hodrick, R. J. Postwar U.S. Business Cycles: An Empirical Investigation / Robert J. Hodrick, Edward C. Prescott // Journal of Money, Credit and Banking. 1997. - vol. 29(1) - P. 1-16.

38. Hsieh, W. W. Nonlinear multichannel singular spectrum analysis of the tropical Pacific climate variability using a neural network approach / W. W. Hsieh, A. Wu // J. Geophys. Res. 2002. - vol. 107, № C7. - P. 3076.

39. Kaiser, R., Combining filter design with model-based filtering (with an application to business-cycle estimation) / R. Kaiser, A. Maravall // International Journal of Forecasting. — 2005. vol. 21, № 4. — P. 691-710.

40. Kondrashov, D. Spatio-temporal filling of missing points in geophysical data sets / D. Kondrashov, M. Ghil // Nonl. Proc. Geophys. 2006. - vol. 13. -P. 151-159.

41. Kuiper, J. A survey and comparative analysis of various methods of seasonal adjustment / J. Kuiper // Proc. of the NBER/Bureau of the Census Conference on Seasonal Analysis of Economic Time Series / Ed. A. Zellner. Washington, D.C., 1976. - P. 59-76.

42. Kumaresan, R. Data-adaptive principal component signal processing / R. Kumaresan, D. W. Tufts // Proc. of IEEE Conference On Decision and Control. Albuquerque, 1980. - P. 949-954.

43. Makridakis, S. Forecasting: Methods and Applications / S. Makridakis, S. Wheelwright, R. Hyndman, 3rd ed. — John Wiley & Sons, New York, 1998. — 656 P.

44. Marple, S. L. Digital spectral analysis: with applications / S. L. Marple. — Prentice-Hall, Inc., 1987. 492 P.

45. McElroy, T. An iterated parametric approach to nonstationary signal extraction / T. McElroy, A. Sutcliffe // Computational Statistics к Data Analysis. 2006. - vol. 50. - P. 2206-2231.

46. Muratani, К. Watermarking 3D Polygonal Meshes Using the Singular Spectrum Analysis / K. Muratani, K. Sugihara // Proe. of IMA Conference on the Mathematics of Surfaces — 2003 — P. 85-98.

47. Packard, N. H. Geometry from a time series / N. H. Packard, J. P. Crutchfielcl, J. D. Farmer, R. S. Shaw // Phys. Rev. Lett. 1980. - vol. 45. - P. 712-716.

48. Pike, E. R. Generalized information theory for inverse problems in signal processing / E. R. Pike, J. G. McWhirter, M. Bertero, C. de Mol // IEE Proc. -1984. vol. 131. - P. 660-667.

49. Planas, C. The Analysis of Seasonality in Economic Statistics: A Survey of Recent Developments / C. Planas, EUROSTAT working group document. — 1997.

50. Schoellhamer, D. H. Singular spectrum analysis for time series with missing data / D. H. Schoellhamer // Geophys. Res. Lett. 2001. - vol. 28, № 16. -P. 3187-3190.

51. Schuster, Sir A. On the Investigation of Hidden Periodicities with Application to a Supposed Twenty-Six Day Period of Meteorological Phenomena / Sir A. Schuster // Terrestrial Magnetism. 1898. - vol. 3. - P. 13-41.

52. SSA-MTM Toolkit Электронный ресурс]. — Режим доступа: http: / / www. atmos. ucla. edu/tcd/ssa/.

53. Takens, F. Detecting strange attractors in turbulence F. Takens // Lecture Notes in Mathematics, eds. D. A. Rand, L.-S. Young — 1981. — vol. 206. — P. 366-381.

54. Time series analysis and forecasting, Caterpillax-SSA method Электронный ресурс] / Caterpillar. Time series analysis and forecasting,

55. N. E. Golyandina, V. V. Nekrutkin, К. A. Braulov. — Режим доступа: http: //www.gistatgroup.com/.

56. Varadi, F. Searching for signal in noise by Random-lag Singular Spectrum Analysis F. Varadi, J. M. Pap, R. K. Ulrich, L. Bertello, C. J. Henny // The Astrophysical Journal. 1999. - vol. 526. - P. 1052-1061.

57. Varadi, F. Random-lag Singular Cross-Spectrum Analysis / F. Varadi, R. К Ulrich., L. Bertello, C. J. Henney // The Astrophysical Journal. — 2000. — vol. 528. P. 53-56.

58. Vautard, M. Singular spectrum analysis in nonlinear dynamics, with applications to paleoclimatic time series / M. Vautard, M. Ghil // Physica D. — 1989. vol. 35. - P. 395-424.

59. Vautard, R. Singular-Spectrum Analysis: A toolkit for short, noisy chaotic signals R. Vautard, P. Yiou, M. Ghil // Physica D. 1992. - vol. 58. -P. 95-126.

60. Whitney, H. Differentiable Manifolds / H. Whitney // Ann. Math. 1936. -vol. 37. P. 645-680.