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

004600163

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

Филипенков Николай Владимирович

Об алгоритмах прогнозирования процессов с плавно меняющимися закономерностями

Специальность 05.13.17— теоретические основы информатики

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Москва 2010

1 АПР 20Ю

004600163

Работа выполнена в Учреждении Российской академии наук Вычислительный центр им. A.A. Дородницына РАН.

Научный руководитель: доктор физико-математических яаук, профессор, член-корреспондент РАН Рудаков Константин Владимирович.

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

Дедус Флоренц Федорович,

кандидат физико-математических наук Гуревкч Игорь Борисович.

Ведущая организация: Московский Педагогический Государственный Университет.

Защита диссертации состоится л

часов на заседании диссертационного совета Д 002.017.02 в Учреждении Российской академии наук Вычислительный центр им. А. А. Дородницына РАН по адресу: 119333, Москва, ул. Вавилова, 40.

С диссертацией можно ознакомиться в библиотеке Учреждения Российской академии наук Вычислительный центр им. А. А. Дородницына РАН.

Автореферат разослан < » чМ^рТА 2010

Ученый секретарь диссертационного совета Д 002.017.02, д.ф.-м.н,, профессор (В. В. Рязанов

Общая характеристика работы

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

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

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

Для решения задач анализа временных рядов было предложено большое число методов. В том числе различные методы сглаживания и фильтрации (Р. Г. Браун, А. Лич, Д. Тригг, Ч. Хольт), авторегрессии и скользящего среднего (Дж. Бокс, Г. Дженкинс), модели, учитывающие гетероскедастичность (Р. Энгл). Прорабатывались алгоритмы основанные на спектральных характеристиках (Д. Ватте, Ф. Ф. Дедус, Г. Дженкинс, Л. Заде, Дж. Рагаззини), статистические модели (С.А.Айвазян, Т.Андерсон, В. М. Бухштабер, М. Кендэл, Г. Крамер, А. Стюарт, Э. Хеннан). Были разработаны различные модели, представляющие закономерности в виде правил: ассоциативных (Р. Агравал, Р. Шрикант), эпизодических (X. Маннила), иерархических (Ф. Морхен). Для поиска правил также создавались методы дискретизации временных рядов (Г. Дас). Алгебраический подход, предложенный академиком РАН Ю. И. Журавлевым, был применен к задачам анализа

временных рядов и выделения трендов (К. В. Рудаков, Ю. В. Чехович).

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

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

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

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

Апробация работы. Результаты, изложенные в диссертации, докладывались на XIII Международной научной конференции «Ломоносов» (Москва, 2006 г.); 49-й и 50-й конференциях МФТИ (Долгопрудный,

2006 г. и 2007 г.); Международной конференции «Pattern Récognition and Information Processing»-2007 (Минск, Республика Беларусь, 2007 г.) Всероссийских конференциях «Математические методы распознавания образов» XIII и XIV (Москва, 2007 г. и 2009 г.); Международной конференции «Интеллектуализация обработки информации»-2008 (Алушта, Украина, 2008 г.); Международной конференции «IADIS European Conference on Data Mining»-2008 (Амстердам, Нидерланды, 2008 г.); а также на научных семинарах ВЦ РАН.

Основные результаты диссертации

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

2) Построен алгоритм поиска постоянных закономерностей в пучках временных рядов.

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

4) Предложены меры сходства масок, функций и закономерностей. Получены условия, при которых указанные меры сходства являются метриками.

5) Введено и исследовано понятие графа закономерностей. Предложен подход к поиску плавно меняющихся закономерностей как кратчайших путей на графе закономерностей.

6) Рассмотрены модификации алгоритма поиска плавпо меняющихся закономерностей для выявления периодических закономерностей.

7) Реализован программный стенд, позволяющий импортировать и генерировать временные ряды, осуществлять поиск стационарных

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

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

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

дана их содержательная интерпретация.

[

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

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

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

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

Публикации. По теме диссертации автором опубликованы 10 работ, в том числе 1 работа в ЖВМиМФ без соавторов.

Структура и объем работы. Работа состоит из введения, трех глав и списка литературы из 69 наименований. Общий объем работы — 82 страницы, включая 5 рисунков и 14 таблиц.

Содержание диссертационной работы

Во введении дается краткий обзор методов анализа временных рядов. Описывается общая структура диссертации и приводится краткое изложение содержания работы.

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

Пучком временных рядов б называется совокупность взаимосвязанных временных рядов <5"и i 6 {1,2..., Щ. Каждый ряд Бг представляет собой последовательность чисел конечнозначной логики Еъ = {0,1,..., /с;}. Каждому элементу ряда соответствует некоторый момент времени, и эти моменты времени для всех рядов одинаковы. Поэтому одинакова и длина всех рядов, которая обозначается через Т. Таким образом, пучок временных рядов © есть матрица размера N х Г, где элемент г-й строки принадлежит множеству Е^. Значения ряда 5,,г е {1,2...,ЛГ} в момент времени Ь 6 {1,2...,Г} обозначим через а(г,£) или а^.

Маской и) на прямоугольнике N х А называется булева матрица размера N х Д (здесь параметр Д определяет максимальный отступ

по времени). Число единиц в маске и> называется мощностью маски и обозначается ||о;||. Элемент маски, находящийся в г-й строке и ¿-м столбце, обозначается ш(г, у) или ш^. Закономерностью Я называется набор (р,^,/) с такими особенностями:

1) число р € {1,2,..., ЛГ} указывает на целевой ряд (ряд, значения которого определяются закономерностью Д);

2) маска ш указывает на значения рядов, являющиеся аргументами функции /;

3) частично определенная функция / задает зависимость значений целевого ряда от переменных, на которые указывает маска ш.

Л},

где ■ ■ ■,—единичные элементы матрицы и,

р — номер целевого ряда, символ А обозначает, что / не определена на соответствующем наборе значений переменных.

Если значения всех рядов представляют собой числа &-зкачной логики (Ек1 = ... = Екр, — Ек), то функция / принадлежит множеству всех частично определенных функций к-значной логики.

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

Рассматривается один из подходов к поиску закономерностей в пучках временных рядов, который предполагает отсутствие изменений в закономерностях с течением времени. Для простоты выкладок предполагается, что к{ — к, { = 1,2..., N. т.е. рассматриваются N А;-значных временных рядов длины Т.

Пусть заданы пучок временных рядов 6 5 целевой

ряд р 6 {1,2,..., И} и маска ш € с единичными элемента-

ми .. ,^(гц„||,7||ы||), упорядоченными лексикографически. Тогда

при фиксированном целевом ряде р на основании б и w строится множество пар (a¡, t>¡), t G {1,2,..., T - Д}, где

at = {а(гь t + ji - 1),..., а(гИ|, í + jN| - 1)} € E^,

vt = a(p, t + A) 6 Ek.

Пусть a — произвольный набор из E^ и v g Ek- Частотой i/(a, v, p, u, 6) называется число раз, которое пара (a, v) встречается среди пар (at,vt), t е {1,2,... ,Т - Д}. Достоверностью Confsct(a.v,p,u!,<5) значения v на наборе а при маске ш на пучке 6 называется частота появления значения v па наборе а:

Confset(a}V,p.UJ, 6) = - fcJr —;-—.

¿2i=o 6)

Поддержкой Suppsot(a,p,u>,6) набора а при маске и на пучке & называется частота появления набора а в исследуемой выборке:

Suj}pset(a,p,u,&) = Т_А-.

Достоверностью Conf(R, ©) закономерности R = (р, и>, /) на пучке временных рядов © называется доля правильных прогнозов закономерности R на пучке временных рядов &:

Conf(R, G) = Conf(p, и, f, &) = -^Гд-=

= Conf(a,f(a),p,u>,&)Supp(a,p,uj,&).

<*e4MI

Поиск постоянных закономерностей на пучке временных рядов 6, определяющих поведение целевого ряда р = 1,2состоит в последовательном переборе масок. Для каждой маски и> определяется закономерность R = (р,и>, /), которая наиболее точно описывает исследуемый пучок временных рядов 6, т.е. которая максимизирует достоверность закономерности Д. При фиксированном целевом ряде р и маске ш оптимальная закономерность на пучке временных рядов 6 строится путем выбора функции /.

Теорема 1.1. При фиксированном целевом ряде р и маске и> максимальную достоверность С'опЦК, 6) на пучке временных рядов 6 имеет закономерность До — (р, с*-1, /о), где значения /о(а) выбираются следующим образом:

/о(а) = а1^тах{/(а, &).

уеЕк

Малая длина Т пучка временных рядов 6 приводит к появлению неопределенных значений А на большом числе наборов функции /. Это способно сделать найденную закономерность Я = (р, и>, /) не пригодной для применения на практике. Ниже приводится оценка необходимой длины пучка временных рядов Т при фиксированных к и ||о;||, которая основана на следующих заключениях. Если набор а € Е^ не появился в множестве {а(} Ь € {1,2,...,Т — Д}, то значение функции / на нем равно Л. Поэтому информативной оценкой достаточности длины пучка временных рядов является вероятность того, что в множестве {«г} присутствуют все наборы из Е^. В работе рассмотрена оценка этой вероятности при равновероятном появлении всех наборов в пучке временных рядов и доказана следующая теорема. Теорема 1.2. Пусть все наборы из Ё^ появляются в множестве с равной вероятностью. Обозначим через М — А:""'' число всех наборов из через Ь — Т — Д — число элементов в множестве {а(} (М < Ь). Вероятность того, что в множестве {а(} присутствуют все наборы из обозначим через Р. Тогда Р = М\8(Ь,М)/М1, где Э(Ь, М) -число Стирлинга II рода.

В работе приводятся примеры необходимой длины пучка временных рядов для различных значений параметров Р и Д.

Алгоритм поиска постоянных закономерностей на пучке временных рядов 6 состоит в последовательном переборе масок, максимизирующем достоверность Соп/(Н, &тц<д построенных закономерностей. Здесь ©шШ — отрезок пучка временных рядов 6, используемый для валидации закономерностей.

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

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

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

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

играет мера сходства на закономерностях.

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

Построение меры сходства масок происходит в несколько шагов. На первом этапе определяется мера сходства рт(^1,^2) Для масок и>2 одинаковой мощности. Указанная мера сходства отражает минимальную стоимость деформации одной маски в другую. Доказывается теорема о том, что

Теорема 2.1. Описанное отображение рт является метрикой.

Мера сходства рт обобщается на случай масок произвольной мощности. Идея состоит в том, чтобы переставить элементы меньшей маски, получив подмножество элементов большей маски. Определяется мера сходства р'т для масок произвольной мощности.

Теорема 2.2. Для меры сходства р'т выполнены все аксиомы метрики, за исключением неравенства треугольпика.

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

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

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

Вначале определяется вспомогательная мера р. Мера сходства р с

параметром ш^е! вводится на множестве {0,1,..., к — 1, Л}. Для этого доопределяется модуль разности, действующий на множестве {0,1,..., к - 1}, следующими правилами:

1) р(Х, х) = р(х, А) = адд > О \/х € {0,1,... — 1},

2) р(А, А) = 0.

Теорема 2.3. Описанное отображение р является метрикой тогда и только тогда, когда к < 2шд + 1.

Следствие 1. Минимальное шд, при котором р является метрикой, равно (к — 1)/2.

На основе меры р определяется метрика р/ на функциях, которые зависят от одинакового числа переменных. Она вводится как метрика на векторах фиксированной длины, координатами которых могут быть элементы множества {0,1,...,А; — 1,А}, где А обозначает отсутствие значения функции на данном наборе. Предполагается, что фиксирован некоторый порядок переменных. Справедлива следующая теорема. Теорема 2.4. Минимальное год, при котором р/ является метрикой, равно (к— 1)/2. При 0 < гид < (к—1)/2 выполнены все аксиомы метрики, за исключением неравенства треугольника.

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

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

Пусть = (р,о>1,/), Дг = — закономерности, порожденные

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

метрики на масках и метрики на частично определенных функциях, введенные ранее:

р(Я ь Я2) = Ь ^з) + д).

Здесь ят и х/ — веса мер сходства, удовлетворяющие следующим условиям: 0 < ит ^ 1, 0 ^ х/ ^ 1, хт + х/ = 1.

Затем в работе вводится понятие последовательности отрезков. Отрезком б1 на пучке временных рядов в с началом 1ь € {0,1,..., Т} и концом 1е е {0,1,... ,Т} (¿¡, < ¿е) назовем матрицу размерности N х О, где в = — ¿ь + 1, составленную из последовательных столбцов матрицы 6, первым из которых является столбец с номером ¿¡,, а последним — столбец с номером Величина 9 называется длиной отрезка б1. Множество отрезков <31,. - ■, бт на пучке временных рядов & с началами и концами ... соответственно называется

последовательностью отрезков, если Уг,./ 6 {1,2,...,т} справедливо {(1<1)^№<4№1<т.

На основе понятия последовательности отрезков и стационарной закономерности вводится понятие плавно меняющейся закономерности.

Пусть б1,..., <Зт - последовательность отрезков на пучке временных рядов б. Введем понятия изменяющейся закономерности и ее длины.

Изменяющейся закономерностью К для последовательности отрезков б1,...,бт на пучке временных рядов 6 называется система закономерностей Я1,..., ВТ1, где каждая закономерность взаимно однозначно соответствует некоторому отрезку &, г — 1,2,... ,т. Будем называть стационарные закономерности Я.1,..., Я!*1 шагами, которые составляют изменяющуюся закономерность Д.

Длиной 1(Н.) изменяющейся закономерности Л называется сумма мер сходства «соседних» шагов —закономерностей, составляющих меняющуюся закономерность.

Пусть каждый из отрезков & , ] = 1,2,... ,т, разбит на две части: обучение б£.01-„ и валидацию Тогда алгоритм поиска постоянных

закономерностей, примененный к каждому из отрезков, порождает наборы закономерностей: Я[,..., - на отрезке в1, ..., Л™,..., й™ - на отрезке 6т. Для каждой закономерности г = 1,2,..., = 1,2,..., т определены значения показателей качества: достоверность на обучении Соп/(Щ,&1Ып), достоверность на валидации Соп/(Щ, &тШ), поддержка на обучении Бирр(Щ, &1Та1п) и т.п. Найденные закономерности можно представить в виде следующего графа закономерностей.

Рисунок 1. Граф закономерностей

Вершинами графа являются стационарные закономерности, найденные на каждом из отрезков, а также две дополнительные вершины: beg и end. С каждой вершиной ассоциированы показатели качества закономерности. Дугами на графе связаны закономерности соседних отрезков, что отражает факт возможного «превращения» одной закономерности в другую. С каждой дугой ассоциирован вес —мера сходства соответствующих закономерностей. Веса дуг, соединяющие закономерности крайних отрезков с вершинами beg и end, полагаются равными нулю.

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

Эта задача сводится к стандартной задаче поиска кратчайшего пути на графе, если использовать в качестве веса вершины величину (1 — где я¡Ьер — функционал качества шага изменяющейся закономерности Ё, который также определяется в работе.

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

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

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

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

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

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

Вторая серия экспериментов показала, что добавление меры сход-

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

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

В заключении подводится краткий итог диссертации.

Список публикаций по теме диссертации

1. Филипенков Н. В. Поиск плавно меняющихся закономерностей в пучках временных рядов // XIII Международная научная конференция «Ломоносов»: Тез. докл. — М.: Изд-во МГУ, 2006. — С. 56-57.

2. Филипенков Н. В. О задачах анализа пучков временных рядов с изменяющимися закономерностями // Искусственный интеллект,— 2006.2. -С. 125-129.

3. Филипенков Н. В. Об одном методе выявления плавно меняющихся закономерностей в к-значных временных рядах // 49-я научная конференция МФТИ: Тез. докл. - М.: МФТИ, 2006. - С. 270-271.

4. Филипенков Н. В. Об оптимальном выборе закономерностей, составляющих плавно меняющуюся закономерность // Математические методы распознавания образов XIII: Тез. докл. — М.: МАКС Пресс, 2007.-С. 223-225.

5. Филипепков Н. В. Поиск плавно меняющихся ассоциативных правил // 50-я научная конференция МФТИ: Тез. докл. — Часть VII. Управление и прикладная математика. Том 2. — М.: МФТИ, 2007. — С. 117-119.

6. Филипенков Н. В. Об эволюционирующих алгоритмах классификации и прогнозирования // Интеллектуализация обработки информации: Тез. докл. —Симферополь. Крымский НЦ НАН Украины, 2008.-С. 228-230.

7. Филипенков Я. В. О некоторых аспектах интеллектуального анализа пучков временных рядов // Математические методы распознавания образов XIV: Тез. докл.-М.: МАКС Пресс, 2009.-С. 204-207.

8. Филипенков Н. В. Об одном методе поиска плавно меняющихся закономерностей в пучках временных рядов // Ж. вычисл. матем. и матем. физ. — 2009. — Т. 49, № 11. — С. 2020-2040.

9. Filipenkov N. V. On the mining of slightly changing patterns in multidimensional time series // Proc. 9th Internat. Conf on Pattern Recognition and Information Processing. — Minsk, 2007. —Vol. 1 — pp. 123-127.

10. Filipenkov N. V. Data mining in non-stationary multidimensional time series using a rule similarity measure // Proc. IADIS European Conf. on Data Mining. — Amsterdam, 2008.— pp. 92-96.

Подписано в печать:

11.03.2010

Заказ № 3376 Тираж -100 экз. Печать трафаретная. Объем: 1 усл. п.л. Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш., 36 (499) 788-78-56 www.autoreferat.ru

Введение

1 Постоянные закономерности

1.1 Основные определения.

1.2 Алгоритм поиска постоянных закономерностей.

1.2.1 Построение закономерности по маске

1.2.2 Оценка необходимой длины пучка временных рядов

1.2.3 Полнота системы закономерностей.

1.2.4 Алгоритм поиска постоянных закономерностей

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

2.1 Меры сходства.

2.1.1 Метрика на масках одинаковой мощности.

2.1.2 Мера сходства на масках произвольной мощности

2.1.3 Метрика на частично определенных функциях

2.1.4 Мера сходства на закономерностях.

2.2 Разбиения.

2.3 Плавно меняющиеся закономерности.

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

2.5 Поиск периодических закономерностей

2.6 Сложность алгоритмов

3 Результаты экспериментов

3.1 Примеры решения модельных задач.

3.2 Примеры решения реальных задач.

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

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

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

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

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

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

Пучок временных рядов отражает характеристики явления во времени, но само явление может меняться с течением времени. Нестационарными в общем смысле называются временные ряды, свойства которых не постоянны во времени. Такие ряды составляют большинство, так как почти все явления под воздействием различных факторов претерпевают изменения. Для анализа нестационарных временных рядов был предложен целый ряд адаптивных методов, обзор которых приводится в работе [20].

Значительные ресурсы, привлеченные в середине XX-го века к решению задач радиоэлектроники, спровоцировали бурное развитие методов анализа временных рядов, которые впоследствии трансформировались в теорию цифровой обработки сигналов. В рамках этой теории было разработано большое число методов анализа временных рядов, основанных на использовании спектральных характеристик рядов [12], [13]. Спектральные характеристики позволяют выявлять изменения в структуре рядов такие как острый пик или ступенчатое изменение.

Существенное развитие данная область получила в работах школы Ф. Ф. Дедуса [9], [10], [11]. В этих работах предложен и развивается обобщенный спектрально-аналитический метод для задач анализа изображений и распознавания образов, который основан на применении систем алгебраических ортогональных полиномов и аналитических преобразованиях описаний сигналов как отрезков ортогональных рядов.

В настоящее время наряду со спектральным анализом временных рядов распространен вейвлетный анализ, который также исследует частотные характеристики рядов [5].

Развитие методов математической статистики также оказало существенное влияние на подходы к анализу временных рядов [1], [2], [3], [16], [17]. [18], [38]. Сформировалась отдельная область знаний — теория случайных процессов [8].

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

В экономике и физике большое распространение получили методы сглаживания (в т. ч. экспоненциального) [42], [64], а также методы, основанные на авторегрессии скользящего среднего [7|, [45], [46].

Одним из наиболее распространенных адаптивных методов прогнозирования временных рядов является метод экспоненциального сглаживания, предложенный в 50-х гг. XX в. Р. Г. Брауном [42] и Ч. Хольтом. Общая идея метода состоит в том, что более старые наблюдения учитываются с меньшим весом. Вес убывает экспоненциально в зависимости от возраста наблюдения. Модель задается параметром а, 0 < а < 1 по рекуррентной формуле, где более новому наблюдению присваивается вес о:, а экспоненциальной средней — вес (1 — а). Параметр а выбирается в зависимости от особенностей решаемой задачи. Увеличение параметра а приводит к увеличению веса свежих наблюдений, и соответственно к быстрому отражению изменений, что эффективно при краткосрочном прогнозировании. С другой стороны уменьшение параметра а позволяет сгладить случайные отклонения. Таким образом, поиск наилучшего параметра а составляет задачу оптимизации модели. Например, Р. Браун рекомендует брать а в пределах от 0,1 до 0, 3.

Д. Тригг и А. Лич предложили метод оптимизации параметра экспоненциального сглаживания, автоматически реагирующий на различие прогнозов модели и фактических данных [62]. Идея состоит в регулировании параметра а. Параметр сначала увеличивается, чтобы повысить «обучаемость» модели. После обучения системы параметр уменьшается с целью фильтрации шума.

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

Для учета линейного тренда используют модель Хольта [51], мультипликативного экспоненциального тренда и сезонности — модель Хольта-Уинтерса [65], аддитивного линейного тренда и сезонности — модель Тейла-Вейджа [61].

Развитие области анализа временных рядов происходило и путем объединения различных методов. Например, метод, предложенный в работе [64], совмещает экспоненциальное сглаживание и спектральные методы анализа временных рядов. Основная идея метода заключается в использовании изменения в спектре для управления величиной а в процедуре подсчета экспоненциальной средней. Спектр оценивается для окна, движущегося по оси времени. Ширина окна должна быть, с одной стороны, не очень велика, чтобы не было сглажено фундаментальное изменение ряда. " С другой стороны, ширина окна должна позволять получать устойчивые оценки частей спектра.

Существенный вклад в развитие методов анализа временных рядов внесли труды Дж. Бокса и Г. Дженкинса [7]. Предложенная ими модель авторегрессионного интегрированного скользящего среднего (ARIMA, autoregressive integrated moving average) обобщает три широких класса моделей временных рядов: авторегрессионые модели, интегральные модели и модели скользящего среднего.

Модель ARIMA задается тремя параметрами р, d и q — целыми неотрицательными числами, которые характеризуют порядок для частей модели (соответственно авторегрессионной, интегрированной и скользящего среднего). После выбора параметров модели настройка весов может осуществляться с помощью метода наименьших квадратов, минимизирующего погрешность. Часто настройка состоит в нахождении наименьших порядков модели, при которых достигается необходимая точность.

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

Существуют также и обобщения данной модели. Например, модель авторегрессионного дробиоиитегрировапного скользящего среднего autoregressive fractionally integrated moving average, ARFIMA) допускает дробные значения порядка разностей [49]. Предложены также расширения модели ARIMA для временных рядов с учетом сезонности (SARIMA) и аппарата нечеткой логики (FSARIMA) [63]. Модель Дж. Бокса и Г. Дженкинса была обобщена и на случай многомерных временных рядов (vector ARIMA) [7].

Среди авторегрессиониых моделей наряду с семейством моделей ARIMA большое распространение получило семейство моделей ARCH, предложенное Р. Энглом [46]. Особенно широкое применение семейство моделей ARCH нашло в финансовых временных рядах.

Основной особенностью этого семейства моделей является то, что оно учитывает неопределенность взаимосвязей переменных, которая отражается в дисперсии остаточного члена регрессии. Если дисперсия изменяется со временем, то говорят о гетероскедастичности временного ряда. Модель Р. Энгла предполагает, что условная дисперсия изменяется во времени. Отсюда возникает и название простейшей модели семейства: модель с авторегрессионной условной гетероскедастичностыо (AutoRegressive Conditional Iieteroscedasticity — ARCH).

На основе модели Энгла были разработаны различные модификации в виде моделей GARCH (обобщенная), GARCH-M (обобщенная в среднем значении), AG ARCH (абсолютная), AGARCH-M (абсолютная в среднем значении), EGARCH (экспоненциальная), EGARCH-M (экспоненциальная в среднем значении) [20], NGARCH (нелинейная), NAG ARCH (нелинейная ассиметричная), IGARCH (интегрированная), QGARCH (квадратичная), СЛЯ-ОАКСН (учитывает асимметрию), ТСАЯСН (пороговая), РЮАШИН (дробноиитегрировапная), Р1Е0АГ1СН (дробноинтегрирован-ная экспоненциальная) и т. д.

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

Новый виток в развитии вычислительной техники, а также совершенствовании области искусственного интеллекта и машинного обучения [4] расширили понимание задачи анализа временных рядов. Анализ временных рядов стал рассматриваться как одна из задач интеллектуального анализа данных [27], [43], [44], [50], [57], [58]. Таким образом, был осуществлен переход от оценки параметров ряда и прогнозирования к задаче, предполагающей поиск временно проявляющихся скрытых закономерностей во временных рядах. Найденные закономерности позволяют не только прогнозировать поведение временного ряда, но и более детально описывать явление, что может быть в дальнейшем использовано экспертами. Закономерности также позволяют более точно моделировать временной ряд.

Закономерности, обнаруженные при анализе временных рядов как задаче интеллектуального анализа данных, в зависимости от метода могут быть представлены как ассоциативные правила [40], [41], эпизодические правила [54], иерархические [55] или прочие виды [44], [60] правил. Рассмотрение анализа временных рядов как задачи интеллектуального анализа позволили применить алгебраический подход к задаче выделения трендов во временных рядах [27].

В классической постановке задачи анализа временных рядов значениями ряда являются действительные числа. Но при анализе временных рядов в рамках задачи машинного обучения (то есть при поиске скрытых закономерностей во временных рядах) более эффективное решение практических задач достигается за счет рассмотрения конечнозначных временных рядов [44], [60].

Однако методы, разработанные для поиска закономерностей в конечнозначных временных рядах, могут применяться не только для рядов со значениями из некоторого конечного алфавита. Такие методы могут быть распространены на «классические» ряды со значениями — элементами действительной оси. Для этой цели используются методы дискретизации или символьного представления временных рядов [44], [56]. Идея методов дискретизации действительных временных рядов в общем случае состоит в том, что действительный временной ряд разбивается на короткие сегменты. Каждый из сегментов относится к одному из классов, которому ставится в соответствие некоторый символ. Таким образом, действительный временной ряд преобразуется в конечнозначный временной ряд.

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

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

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

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

Благодарности

Автор выражает глубокую признательность своему Учителю члену-корреспонденту РАН Константину Владимировичу Рудакову за постановку задачи и постоянную поддержку в ходе исследований. Автор хотел бы выразить благодарность к. ф.-м. н. Константину Вячеславовичу Воронцову, к. ф.-м. н. Юрию Викторовичу Чеховичу и к. ф.-м. н. Вадиму Викторовичу Стрижову за внимание к работе, помощь в поиске литературы и подборе данных для экспериментов. Также автор хотел бы поблагодарить всех своих коллег по учебе в аспирантуре Вычислительного центра РАН, принимавших участие в обсуждении работы и всегда морально поддерживавших автора исследования.

Заключение

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

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

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

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

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

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

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

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

1. Айвазян С. А., Бухштабер В. М. Анализ данных, прикладная статистика и построение общей теории автоматической классификации.— М.: Финансы и статистика, 1985.

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

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

4. Барсегян А. А., Куприянов М. С., Степаненко В. В., Холод И. И. Методы и модели анализа данных: OLAP и Data Mining — СПб.: БХВ-Петербург, 2004.

5. Блаттер К. Вейвлет-анализ. Основы теории — М.: Техносфера, 2006.

6. Богнер Р., Констлнтинидес А. Введение в цифровую фильтрацию—М.: Мир, 1976.

7. БоксДж., Дженкинс Г. Анализ временных рядов, прогноз и управление — М.: Мир, 1974.

8. Булинский А. В.; Ширяев А. H. Теория случайных процессов — М.: Физматлит, 2005.

9. ДедусФ.Ф., Махортых С. А., УстининМ.Н., Деду с А. Ф. Обобщенный спектрально-аналитический метод обработки информационных массивов. Задачи анализа изображений и распознавания образов. — М.: Машиностроение, 1999.

10. Дедуе Ф. Ф. Достижения и перспективы развития обобщенного спектрально-аналитического метода в решении сложных информационных задач // Математические методы распознавания образов XII: Тез. докл. — М.: МАКС Пресс, 2005.-С. 84-86.

11. Деду с Ф. Ф. Обобщенный спектрально-аналитический метод и его приложения // Математические методы распознавания образов XIII: Тез. докл. — М.: МАКС Пресс, 2007.-С. 680-682.

12. Дженкинс Г., Ватте Д. Спектральный анализ и его приложения. Выпуск 1. — М.: Мир, 1971.

13. Дженкинс Г., Ватте Д. Спектральный анализ и его приложения. Выпуск 2, —М.: Мир, 1972.

14. Журавлёв Ю. И. Об алгебраическом подходе к решению задач распознавания или классификации // Пробл. кибернетики. — 1978. — №33.-С. 5-68.

15. Журавлев Ю. И. Избранные научные труды — М.: Магистр, 1998.

16. Кендэл М. Временные ряды — М.: Финансы и статистика, 1981.

17. Кендэл М., Стюарт А. Многомерный статистический анализ и временные ряды — М.: Наука, 1976.

18. Крамер Г. Математические методы статистики. — М.: Мир, 1975.

19. Кристофидес Н. Теория графов. Алгоритмический подход. — М.: Мир, 1978.

20. Лукашин Ю. П. Адаптивные методы краткосрочного прогнозирования временных рядов —М.: Финансы и статистика, 2003.

21. Ope О. Теория графов, — М.: Наука, 1980.

22. Рудаков К. В. О некоторых универсальных ограничениях для алгоритмов классификации // Ж. вычисл. матем. и матем. физ.— 1986.-Т. 26, №11-С. 1719-1726.

23. Рудаков К. В. Универсальные и локальные ограничения в проблеме коррекции эвристических алгоритмов // Кибернетика—1987.— №2-С. 30-35.

24. Рудаков К. В. Полнота и универсальные ограничения в проблеме коррекции эвристических алгоритмов классификации // Кибернетика — 1987. — № 3 — С. 106-109.

25. Рудаков К. В. Алгебраическая теория универсальных и локальных ограничений для алгоритмов распознавания.—Дис. .докт. физ.-матем. наук, М.: ВЦ РАН, 1992.

26. Рудаков К. В., Воронцов К. В. О методах оптимизации и монотонной коррекции в алгебраическом подходе к проблеме распознавания // Докл. РАН-1999.-Т. 367 — №3 — С. 314-317.

27. Рудаков К. В., Чехович Ю. В. Алгебраический подход к проблеме синтеза обучаемых алгоритмов выделения трендов // Докл. РАН — 2003. Т. 388 - № 1 - С. 33-36.

28. Tamm У. Теория графов, —М.: Мир, 1988.

29. Уилсон Р. Введение в теорию графов. — М.: Мир, 1977.

30. Филипенков Н. В. Поиск плавно меняющихся закономерностей в пучках временных рядов // XIII Международная научная конференция «Ломоносов»: Тез. докл. — М.: Изд-во МГУ, 2006. — С. 56-57.

31. Филипенков Н. В. О задачах анализа пучков временных рядов с изменяющимися закономерностями // Искусственный интеллект. — 2006. 2. — С. 125-129.

32. Филипенков Н. В. Об одном методе выявления плавно меняющихся закономерностей в k-значных временных рядах // 49-я научная конференция МФТИ: Тез. докл.-М.: МФТИ, 2006.-С. 270-271.

33. Филипенков Н. В. Об оптимальном выборе закономерностей, составляющих плавно меняющуюся закономерность // Математические методы распознавания образов XIII: Тез. докл. —М.: МАКС1. Пресс, 2007. С. 223-225.

34. Филипенков Н. В. Поиск плавно меняющихся ассоциативных правил // 50-я научная конференция МФТИ: Тез. докл. —Часть VII. Управление и прикладная математика. Том 2. — М.: МФТИ, 2007. — С. 117-119.

35. Филипенков Н. В. Об эволюционирующих алгоритмах классификации и прогнозирования // Интеллектуализация обработки информации: Тез. докл. — Симферополь. Крымский НЦ HAH Украины, 2008.— С. 228-230.

36. Филипенков Н. В. О некоторых аспектах интеллектуального анализа пучков временных рядов // Математические методы распознавания образов XIV: Тез. докл. — М.: МАКС Пресс, 2009. С. 204-207.

37. Филипенков Н. В. Об одном методе поиска плавно меняющихся закономерностей в пучках временных рядов // Ж. вычисл. матем. и матем. физ. 2009. - Т. 49, №11.-С. 2020-2040.

38. Хеннан Э. Многомерные временные ряды. — М.: Мир, 1974.

39. Харари Ф. Теория графов. — М.: Мир, 1973.

40. AgrawalR., Imielinski Т., Swamiet A. Mining association rules between sets of items in large databases // Proc. Conf. Management of Data. 1993. - pp. 207-216.

41. AgrawalR., Srikant R. Mining sequential patterns // Proc. 11th Internat. Conf. on Data Eng-ng. — 1995. — pp. 3-14.

42. Brown R. G. Smoothing forecasting and prediction of discrete time series —N.Y.: Prentice-Hall, 1963.

43. Caraca-valente J. P, Lopez-Chavarrias I. Discovering similar patterns in time series // KDD-2000. — Boston, 2000.-pp. 497-505.

44. Das G., Lin K., Mannila H. et al. Rule discovery from time series // Proc. 4th Internat. Conf. on Knowledge Discovery and Data Mining. — 1998.-pp. 16-22.

45. EngleR.F., Kroner K. F. Multivariate Simultaneous Generalized ARCH // Econometric Theory. 1993. - Vol. 11.-pp. 122-150.

46. EngleR.F. ARCH: Selected readings — Oxford: Oxford Univ. Press, 1995.

47. Filipenkov N. V. On the mining of slightly changing patterns in multidimensional time series // Proc. 9th Internat. Conf on Pattern Recognition and Information Processing. — Minsk, 2007. — Vol. 1 —pp. 123-127.

48. Filipenkov N. V. Data mining in non-stationary multidimensional time series using a rule similarity measure // Proc. IADIS European Conf. on Data Mining. — Amsterdam, 2008.— pp. 92-96.

49. Granger C. W. J., Joyeux R. An introduction to long-memory time series and fractional differencing — Journal of Time Series Analysis. — 1980. — Vol. 1, № 1. — pp. 15-29.

50. Han J. Efficient mining of partial periodic patterns in time series database —Proc. Internat. Conf. on Data Engineering — 1999. — pp. 106-115.

51. Holt C. C. Forecasting trends and seasonals by exponentially weighted moving averages // ONR Research Memorandum — Carnegie Institute of Technology 1957 - Vol. 52.

52. Keogh E., Lin J. Clustering of Time Series Subsequences is Meaningless // Proc. 3rd IEEE Internat. Conf. on Data Mining.— 2003.-pp. 115-122.

53. Lin J., Keogh E., Lonardi S., Chiu B. A symbolic representation of time series, with implications for streaming algorithms // Proc. 8th ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery. — 2003. — pp. 2-11.

54. Mannila H., Toivonen H., Verkavio A. I. Discovery of frequent episodesin event sequences // Data Mining and Knowledge Discovery. — 1997. — Vol. 1, №3. —pp. 259-289.

55. Morchen F., Ultsch A. Mining hierarchical temporal patterns in multivariate time series // Proc. 27th Ann. German Conf. Artificial Intelligence. — 2004. — pp. 127-140.

56. Morchen F., Ultsch A. Optimizing time series discretization for knowledge discovery // Proc. 11th Internat. Conf. on Knowledge Discovery and Data Mining.-—2005.—pp. 660-665.

57. Morchen F., Ultsch A. Efficient mining of understandable patterns from multivariate interval time series // Data Mining and Knowledge Discovery. 2007. - Vol. 15, № 2. - pp. 181-215.

58. Povinelli R. J., Feng X. Data Mining of Multiple Nonstationary Time Series // Proc. Artificial Neural Networks in Engineering. — 1999. — pp. 511-516.

59. Pudil P., FerriF.J., Novovicova J. et al. Floating search methods for feature selection // Pattern Recognition Letters. — 1994.—Vol. 15, №10.-pp. 1119-1125.

60. Sayal M. Detecting time correlations in time-series data streams — Palo Alto: HP Labs, 2004.

61. Theil H., Wage S. Some observations on adaptive forecasting // Management Sc. — 1964. Vol. 10, №2.-pp. 198-206.

62. Trigg D.W., Leach A. G. Exponential smoothing with an adaptive response rate // Operat. Res. Quart. — 1967. Vol. 18, №1. — pp. 5359.

63. Tseng F. M., Tzeng G. H. A fuzzy seasonal ARIMA model for forecasting // Fuzzy Sets and Systems. — 2002.—Vol. 126, №3. —pp. 367-376.

64. Rao A. G., Shapiro A. Adaptive smoothing using evolutionary spectra // Management Sc. — 1970. — Vol. 17, №3, —pp. 208-218.

65. Winters P. R. Forecasting sales by exponentially weighted moving averages // Management Sc. — 1960. — Vol. 6, №3. — pp. 324-342.

66. Xuan X., Murphy K. Modeling changing dependency structure in multivariate time scries // ICML-2007. — Corvallis, 2007. — pp. 10551062.

67. Vlachos M., Hadjieleftheriou M., Gunopulos D., Keogh E. Indexing multi-dimensional time-series with support for multiple distance measures // Proc. 9th ACM SIGKDD Internat. Conf. on Knowledge discovery and data mining . — 2003. —pp. 216-225.

68. Zadeh L. A., Ragazzini J. R. An extension of Wiener's theory of prediction // J. Appl. Phys. 1950.-Vol. 21.-pp. 645-655.

69. Zadeh L. A., Ragazzini J. R. The analysis of sampled-data systems // Applic. and Industry (AIEE). 1952.-pp. 225-234.