Содержание к диссертации
Введение
1 Постоянные закономерности 15
1.1 Основные определения 15
1.2 Алгоритм поиска постоянных закономерностей 17
1.2.1 Построение закономерности по маске 17
1.2.2 Оценка необходимой длины пучка временных рядов 21
1.2.3 Полнота системы закономерностей 23
1.2.4 Алгоритм поиска постоянных закономерностей . 26
2 Плавно меняющиеся закономерности 28
2.1 Меры сходства 29
2.1.1 Метрика на масках одинаковой мощности 29
2.1.2 Мера сходства на масках произвольной мощности . 32
2.1.3 Метрика на частично определенных функциях . 34
2.1.4 Мера сходства на закономерностях 37
2.2 Разбиения 39
2.3 Плавно меняющиеся закономерности 40
2.4 Показатели качества плавно меняющихся закономерностей 43
2.5 Поиск периодических закономерностей 45
2.6 Сложность алгоритмов 47
3 Результаты экспериментов 48
3.1 Примеры решения модельных задач 48
3.2 Примеры решения реальных задач 64
Заключение 72
Список литературы 75
- Алгоритм поиска постоянных закономерностей
- Алгоритм поиска постоянных закономерностей
- Метрика на частично определенных функциях
- Показатели качества плавно меняющихся закономерностей
Введение к работе
Актуальность темы. Анализ и прогнозирование процессов, протекающих во времени, всегда были крайне актуальными задачами. Важность задач прогнозирования обусловила как накопление статистической информации о значениях показателей процессов в различные моменты времени, так и стимулировала развитие методов анализа этих данных.
Еще большую значимость приобрел анализ пучков временных рядов или многомерных временных рядов, который предполагает исследование временных рядов в их взаимосвязи и взаимовлиянии. Пучки временных рядов позволяют описать процесс или систему процессов наиболее полно.
Задачи прогнозирования и поиска закономерностей в пучках временных рядов возникают в различных сферах деятельности человека: медицине, экономике, физике, химии, метеорологии, кибернетике. Пучки временных рядов могут, например, описывать процессы жизнедеятельности человека, стоимость акций на бирже, курсы валют, сигналы, погодные условия и т. д.
Для решения задач анализа временных рядов было предложено большое число методов. В том числе различные методы сглаживания и фильтрации (Р.Г.Браун, А. Лич, Д. Тригг, Ч. Хольт), авторегрессии и скользящего среднего (Дж. Бокс, Г. Дженкинс), модели, учитывающие гетероскедастичность (Р. Энгл). Прорабатывались алгоритмы основанные на спектральных характеристиках (Д. Ватте, Ф.Ф. Дедус, Г. Дженкинс, Л. Заде, Дж. Рагаззини), статистические модели (С.А.Айвазян, Т.Андерсон, В. М. Бухштабер, М. Кендэл, Г. Крамер, А. Стюарт, Э. Хеннан). Были разработаны различные модели, представляющие закономерности в виде правил: ассоциативных (Р. Агравал, Р. Шрикант), эпизодических (X. Маннила), иерархических (Ф. Морхен). Для поиска правил также создавались методы дискретизации временных рядов (Г. Дас). Алгебраический подход, предложенный академиком РАН Ю. И. Журавлевым, был применен к задачам анализа
временных рядов и выделения трендов (К. В. Рудаков, Ю. В. Чехович).
Цель работы состоит в разработке алгоритма поиска закономерностей в пучках временных рядов, базирующегося на предположении о плавном изменении закономерностей с течением времени.
В настоящей работе рассматривается задача поиска закономерностей в пучках дискретных нестационарных временных рядов с конечным алфавитом значений. Для ее решения предлагается подход, который позволяет выявлять закономерности, подвергающиеся «плавным» структурным изменениям с течением времени. Для определения подобного рода изменений предлагается мера сходства закономерностей и описывается ее применение как веса на графе закономерностей.
Методика исследований. В диссертации использован экспериментально-теоретический подход к задаче поиска закономерностей как задаче интеллектуального анализа данных. Также использованы методы теории оптимизации и теории графов, комбинаторика. Проведены эксперименты на модельных и реальных пучках временных рядов.
Научная новизна. Все результаты, полученные в диссертации, являются новыми. В работе предложены модель закономерности и подход, который позволяет учитывать «плавное» изменение закономерностей с течением времени. Для определения плавного изменения вводится понятие меры сходства закономерностей, указывающей на близкие закономерности. При этом задача поиска закономерностей рассматривается как задача интеллектуального анализа данных, что позволяет в явном виде описывать найденные закономерности.
Апробация работы. Результаты, изложенные в диссертации, докладывались на XIII Международной научной конференции «Ломоносов» (Москва, 2006 г.); 49-й и 50-й конференциях МФТИ (Долгопрудный,
2006 г. и 2007 г.); Международной конференции «Pattern Recognition and Information Processing»-2007 (Минск, Республика Беларусь, 2007 г.) Всероссийских конференциях «Математические методы распознавания образов» XIII и XIV (Москва, 2007 г. и 2009 г.); Международной конференции «Интеллектуализация обработки информации»-2008 (Алушта, Украина, 2008 г.); Международной конференции «IADIS European Conference on Data Mining»-2008 (Амстердам, Нидерланды, 2008 г.); а также на научных семинарах ВЦ РАН.
Основные результаты диссертации
Введены и исследованы понятия маски, функции и закономерности в пучках конечнозначных временных рядов.
Построен алгоритм поиска постоянных закономерностей в пучках временных рядов.
Получены оценки необходимой длины пучка временных рядов для поиска закономерностей, определенных на всех наборах значений
аргументов.
Предложены меры сходства масок, функций и закономерностей. Получены условия, при которых указанные меры сходства являются метриками.
Введено и исследовано понятие графа закономерностей. Предложен подход к поиску плавно меняющихся закономерностей как кратчайших путей на графе закономерностей.
Рассмотрены модификации алгоритма поиска плавно меняющихся закономерностей для выявления периодических закономерностей.
Реализован программный стенд, позволяющий импортировать и генерировать временные ряды, осуществлять поиск стационарных
и плавно меняющихся закономерностей, а также производить прогнозирование пучков временных рядов.
Проведена серия экспериментов на модельных пучках временных рядов. На рассмотренных примерах показана высокая эффективность метода. Выработаны практические рекомендации по установке параметров алгоритма.
Проведены практические эксперименты для сравнения эффективности с другими методами на реальных временных рядах. Показано превосходство предложенного метода. С использованием предложенного алгоритма проведено выявление скрытых закономерностей, определяющих поведение пучка временных рядов, и дана их содержательная интерпретация.
Практическая и теоретическая ценность. Предложенный подход позволяет выявлять плавно меняющиеся закономерности в пучках временных рядов.
Алгоритмы, предложенные в работе, могут быть использованы для прогнозирования временных рядов. Вместе с тем, алгоритмы позволяют решать задачу интеллектуального анализа данных.
Таким образом, подход позволяет выявлять скрытые закономерности в данных и в явном виде выписывать их. Найденные закономерности в дальнейшем могут быть использованы экспертами для детального анализа явления, а также для моделирования процесса, описываемого пучком временных рядов.
Вместе с тем в работе приводятся теоретические результаты, касающиеся предложенных алгоритмов. В том числе, оценивается необходимая длина пучка временных рядов для поиска наиболее универсальных закономерностей. Также рассматриваются условия, при которых предложенные в работе меры сходства являются метриками.
Публикации. По теме диссертации автором опубликованы 10 работ, в том числе 1 работа в ЖВМиМФ без соавторов.
Структура и объем работы. Работа состоит из введения, трех глав и списка литературы из 69 наименований. Общий объем работы — 82 страницы, включая 5 рисунков и 14 таблиц.
Алгоритм поиска постоянных закономерностей
Анализ и прогнозирование процессов, протекающих во времени, всегда были крайне актуальными задачами, стоявшими перед человечеством. Важность задач прогнозирования обусловила как накопление статистической информации о значениях показателей процессов в различные моменты времени, так и стимулировала развитие методов анализа этих данных.
Последовательность чисел, представляющих собой значения некоторого процесса в дискретные моменты времени, принято называть одномерным временным рядом. Как правило, последовательность чисел представляет значения процесса, измеренные через равные промежутки времени.
Во многих прикладных задачах возникает необходимость исследования сразу нескольких процессов или показателей одного процесса. Тогда говорят о многомерном временном ряде, который определяется как последовательность векторов, содержащих значения нескольких показателей в один момент времени. Многомерный временной ряд может быть также представлен как совокупность одномерных временных рядов.
Часто многомерный временной ряд описывает систему, которая предполагает наличие взаимосвязей между одномерными рядами. В этом случае говорят о пучке временных рядов, который анализируют в рамках гипотезы о существовании взаимосвязей и взаимовлияний между рядами.
В настоящее время задачи анализа и прогнозирования значений пучков временных рядов возникают в различных сферах деятельности человека: медицине, экономике, физике, химии, метеорологии, кибернетике. Пучки временных рядов могут, например, описывать процессы жизнедеятельности человека, стоимость акций на бирже, курсы валют, сигналы, погодные условия и т. д. Пучок временных рядов, учитывая множество характеристик явления, позволяет описать процесс или систему процессов наиболее полно, что, в свою очередь, позволяет сделать более точный прогноз. Возможность системного анализа процессов, их более точного описания определила высокий интерес исследователей к изучению пучков временных рядов.
Происхождение пучков временных рядов может быть совершенно разнообразным. Порой пучки порождаются принципиально различными системами или совокупностями систем, но вместе с тем пучки временных рядов могут исследоваться в рамках единого подхода, предполагающего обработку экспериментальных данных алгоритмами анализа временных рядов.
Пучок временных рядов отражает характеристики явления во времени, по само явление может меняться с течением времени. Нестационарными в общем смысле называются временные ряды, свойства которых не постоянны во времени. Такие ряды составляют большинство, таккак почти все явления под воздействием различных факторов претерпевают изменения. Для анализа нестационарных временных рядов был предложен целый ряд адаптивных методов, обзор которых приводится в работе [20].
Значительные ресурсы, привлеченные в середине XX-го века к решению задач радиоэлектроники, спровоцировали бурное развитие методов анализа временных рядов, которые впоследствии трансформировались в теорию цифровой обработки сигналов. В рамках этой теории было разработано большое число методов анализа временных рядов, основанных на использовании спектральных характеристик рядов [12], [13]. Спектральные характеристики позволяют выявлять изменения в структуре рядов такие как острый пик или ступенчатое изменение.
Существенное развитие данная область получила в работах школы Ф. Ф. Дедуса [9], [10], [11]. В этих работах предложен и развивается обобщенный спектрально-аналитический метод для задач анализа изображений и распознавания образов, который основан на применении систем алгебраических ортогональных полиномов и аналитических преобразованиях описаний сигналов как отрезков ортогональных рядов.
В настоящее время наряду со спектральным анализом временных рядов распространен вейвлетный анализ, который также исследует частотные характеристики рядов [5].
Развитие методов математической статистики также оказало существенное влияние на подходы к анализу временных рядов [1], [2], [3], [1G], [17]. [18], [38]. Сформировалась отдельная областьзнаний — теория случайных процессов [8].
Дальнейшее развитие вычислительной техники привело к расширению как сфер применения методов анализа временных рядов, так и к увеличению разнообразия самих методов. Существенный импульс к совершенствованию алгоритмов анализа временных рядов дало развитие финансовых рынков и накопление эконометрических данных. Задачи прогнозирования цен на товары, акции, финансовые инструменты требовали новых моделей, описывающих временные ряды и позволяющих осуществлять прогноз.
Алгоритм поиска постоянных закономерностей
Алгоритм поиска постоянных закономерностей на пучке временных рядов & состоит в последовательном переборе масок, максимизирующем достоверность Conf(R, 3vaiid) построенных закономерностей. Здесь & valid отрезок пучка временных рядов @, используемый для валидации закономерностей. В качестве методов оптимизации предлагается использовать методы селекции признаков, применяемые в распознавании образов. Это обусловлено сходством задачи выбора оптимального подмножества признаков и задачи выбора единичных элементов маски.
В настоящей работе применяется алгоритм плавающего поиска, рассматриваемый в [59]. Алгоритм поиска постоянных закономерностей с целевым рядом р на пучке временных рядов может быть представлен в виде следующей схемы действий." Шаг 1. Инициализация. С = О (С — значение полноты системы закономерностей, найденных на данный момент). Выбор первой маски о;. Шаг 2. Построение по маске со функции /. Получение новой закономерности R= (p,co,f). Шаг 3. Вычисление текущего значения полноты С системы закономерностей. Шаг 4. Если С = 1, то конец выполнения алгоритма. Шаг 5. Выбор очередной маски в соответствии с алгоритмом плавающего поиска, максимизирующим достоверность Conf(R, ). Шаг 6. Переход к шагу 2. Закономерность, определяющая поведение целевого ряда, может меняться с течением времени. Описанный выше алгоритм не способен адекватно реагировать на подобного рода изменения. Наиболее часто встречающейся в литературе идеей при поиске нестационарных закономерностей является использование «старых» наборов с меньшим весом по отношению к «более новым» наборам.
Но данная методика не позволяет выделить закономерности, подвергающиеся структурным изменениям, т.е. изменениям маски или функции. Предлагаемый ниже подход призван исправить этот недостаток. Он учитывает возможные структурные изменения и ориентирован не только на прогнозирование значений ряда, но и на поиск закономерностей, которые затем могут быть использованы при анализе и моделировании процесса, описываемого пучком временных рядов. Идея подхода состоит в разбиении исходного пучка временных рядов на отрезки, на каждом из которых применяется алгоритм поиска постоянных закономерностей. Наиболее близкие в смысле некоторой меры сходства закономерности, полученные на различных отрезках, считаются этапами эволюции одной закономерности. Ключевую роль в алгоритме Ниже будет рассмотрена мера сходства на закономерностях, полученных в результате анализа fc-значных временных рядов.
Предполагается, что закономерности в процессе структурной деформации не могут менять номер целевого ряда. Поэтому мера сходства вводится па закономерностях с одинаковым параметром р. Пусть «то — симметрическая группа перестановок, действующих на множестве Q = {(1,1),..., (N, А)}. Пусть также Я — произвольное множество, UJ — произвольная матрица размера NxA над множеством Я и s — перестановка из группы GQ. Определим действие перестановки s на матрице ш равенством Введем расстояние между масками одинаковой мощности следующим образом: Здесь функция W(UJI,S) с параметрами h и v (h,v Є Ш:Н 0,v 0) задает стоимость преобразования одной маски в другую: или, что то же самое, Доказательство. Так как параметры h и v положительны, то ртп отображает любую пару масок одинаковой мощности в неотрицатель ное число. Если pm{uJi,LJ2) — 0. то перестановка s в определении отображения такова, что г = is и j = jS) где (iSljs) = s(i,j), т.е. маски совпадают. Справедливо и обратное утверждение: если маски совпали, то pm(uji,uj2) = 0. Симметричность следует из существования в группе сто обратной перестановки для любой из перестановок. Докажем выполнение неравенства треугольника: pm(x: z) рт(х, у) + рт{у z) Для всех масок ж, у и z.
Метрика на частично определенных функциях
Теперь определим метрику на функциях, которые зависят от одинакового числа переменных. Для этого надо фактически ввести метрику на векторах фиксированной длины, координатами которых могут быть элементы множества {0,1,...,к — 1,А}, где Л обозначает отсутствие значения функции на данном наборе. Заметим, что здесь неявно предполагается, что фиксирован некоторый порядок переменных: где г «пробегает» по всем наборам значений переменных, /г- и gi — это, соответственно, значения функций / и д на г-м наборе или символ Л, a CJ —количество переменных.
Так как количество наборов равно /с"ш и р(х, у) к, то для произвольных функций /ид выполнено неравенство
Знаменатель меры сходства функций позволяет нормировать данную функцию, что представляется более удобным для практического использования и одновременно делает меру инвариантной относительно добавления фиктивных переменных. Так как в определении отображения р/ используется сумма координат, то справедлива
Теорема 2.4. Минимальное w\, при котором pj является метрикой, равно (k—1)/2. При 0 w\ (к —1)/2 выполнены все аксиомы метрики, за исключением неравенства треугольника.
Наконец, можно ввести метрику на произвольных частично определенных функциях из Р. Определим ее так же, как и для функций, которые зависят от одинакового числа переменных. Для этого добавим фиктивные переменные к функции, у которой их меньше. Но добавление фиктивных переменных определено неоднозначно, так как не задан порядок на переменных. Порядок задается с использованием введенной метрики на масках. Этот процесс описан ниже в определении меры сходства на закономерностях.
Основываясь на содержательных соображениях, можно сформулировать два требования к мере сходства на закономерностях. Во-первых, она должна отражать близость масок, а во-вторых - близость функций.
Пусть R\ — (P,UJL, /), / = (р,0 2,50—закономерности, порожденные fc-значными временными рядами, т.е. функции /ид принадлежат Р. Определим отображение р на закономерностях, используя понятия метрики на масках и метрики на частично определенных функциях, введенные ранее (формулы (2.2) и (2.4) соответственно):
Здесь кт и х/ — веса мер сходства, удовлетворяющие следующим условиям: 0 Так как справедливы неравенства (2.3) и (2.5), то верно аналогичное неравенство для меры сходства закономерностей:
Как уже упоминалось выше, метрика на функциях не задана однозначно, пока не определен порядок переменных. Сначала зададим порядок на множестве Г2 = {(1,1),..., (7V, А)}: (а, Ь) (с, (і), если а с или если Ъ d при а = с. Далее для упрощения выкладок предположим, что to i 2І- Пусть (ii,ji), (i2:j2):..., (ЇЦШІІІІІші) - единичные элементы маски ш\, расположенные в соответствии с введенным на Г2 порядком. Пусть известна перестановка s Є &о : s(L0i)f\LU2 = s(uji). Тогда порядок переменных функции / задается так: (iuji) (i2,J2) iKlhilKll), а далее следуют c4;2-a;i фиктивных переменных. Порядок переменных функцииg задается так: s{ kji) s(i2J2) ... s(2Wl, ІШі), а далее следуют оставшиеся единичные элементы маски ш\ в соответствии с введенным наП порядком. В случае если а;2І і? порядок задается аналогично. Теперь введенное нами отображение на частично-определенных функциях определено однозначно для всех функций. Следовательно. p(R[. R2) определено для всех закономерностей, порожденных /с-значными временными рядами. Нетрудно видеть, что для p(R\, -) выполнены все аксиомы метрики, за исключением неравенства треугольника. Выполнение аксиом очевидно. А неравенство треугольника не выполнено, так как в качестве примера можно привести закономерности с одинаковыми функциями и масками
Выше было показано, что для них неравенство треугольника не выполнено. Отрезком &1 на пучке временных рядов (5 с началом tb Є {0,1,..., Т} и концом te Є {0,1,..., Т} (tb te) назовем матрицу размерности N х (9, где в = te — tb +1, составленную из последовательных столбцов матрицы (3, первым из которых является столбец с номером tb, а последним — столбец с номером te. Величина в называется длиной отрезка О1. Множество отрезков (Е51,..., 5т на пучке временных рядов (5 с началами ,..., и концами ,..., соответственно называется последовательностью отрезков, если \/г,_; Є {1,2,...,772,} справедливо {(і j) = (( t3b)&(tl tJe))}.
Показатели качества плавно меняющихся закономерностей
Во второй серии экспериментов исследовалось влияние меры сходства закономерностей на качество распознавания. С этой целью проводился поиск изменяющихся закономерностей для разных комбинаций весов функционала качества Qstep шага изменяющейся закономерности. При этом исследование влияния меры сходства закономерностей проводилось для нескольких значений уровня шума.
Эксперименты проводились следующим образом. Был задан набор значений уровня шума є: 0,2, 0,3 и 0,5. Для каждого значения уровня шума генерировался пучок временных рядов способом, аналогичным примененному в первой серии экспериментов. Значения параметров генерации представлены в табл. 3.3.
В сгенерированном пучке временных рядов происходил поиск изменяющихся закономерностей при различных весах функционала качества Qstep шага изменяющейся закономерности. Вес поддержки wsupp полагался равным нулю, что исключило влияние уровня поддержки на выбор оптимальной изменяющейся закономерности. Вес меры сходства закономерностей wsimiiarity увеличивался от 0 до 1 с шагом 0,05. Вес достоверности wconf соответственно уменьшался от 1 до 0 с шагом 0,05.
Для каждого значения уровня шума было сгенерировано 100 пучков временных рядов. В каждом пучке временных рядов происходил поиск плавно меняющихся закономерностей при 21-ой различной комбинации весов функционала качества QstKP- Значения параметров алгоритмов поиска закономерностей представлены в табл. 3.3 и 3.4.
Для каждого значения уровня шума и для каждой комбинации весов была рассчитана доля успешных экспериментов. Успешный эксперимент определялся аналогично первой серии экспериментов. Доля определялась по отношению к общему количеству экспериментов для данного значения уровня шума и комбинации весов. Результаты второй серии экспериментов представлены в табл. 3.6 и на рис. 3.3.
Результаты второй серии экспериментов указывают на необходимость использования как меры сходства закономерностей, так и достоверности в функционале качества шага изменяющейся закономерности. При граничных значениях весов доля успешных экспериментов снижается, и, наоборот, она достигает максимального уровня при значениях веса меры сходства закономерностей wsimilarity в интервале от 0,65 до 0,75 (соответственно значениях веса достоверности wconf от 0,35 до 0,25).
Комбинация значений весов wconf = 1и similarity — 0 соответствует алгоритму, при котором на каждом отрезке выбирается закономерность, обладающая максимальной достоверностью. Объединенные вместе данные закономерности составляют изменяющуюся закономерность. Мера сходства закономерностей в этом случае не используется.
При указанных значениях весов и высоком уровне шума алгоритм поиска изменяющихся закономерностей склонен к «переобучению». Так как мера сходства закономерностей не используется в функционале качества, в изменяющуюся закономерность объединяются «локальные оптимумы» каждого из отрезков. В итоге, при любом уровне шума поиск плавно меняющихся закономерностей без использования меры сходства закономерностей приводит к низкому качеству распознавания: не удается правильно определить плавно меняющуюся закономерность.
Теперь рассмотрим случай, когда веса принимают другое пограничное значение: wconf = 0 и т8гтцагцу = 1. Тогда единственным критерием для выбора закономерностей является их близость. Если нет ограничения на количество закономерностей, записываемых в базу знаний алгоритмом поиска стационарных закономерностей, то такой выбор весов исключает возможность изменения закономерности. То есть при данном выборе весов оптимальной является любая изменяющаяся закономерность составленная из одинаковых стационарных закономерностей (то есть фактически стационарная закономерность).
При комбинации весов wconf — 0 и ги3гтцагцу = 1 бывает удобно упорядочить закономерности по убыванию достоверности и поставить ограничение на количество закономерностей, записываемых в базу знаний алгоритмом поиска стационарных закономерностей. Например, в базу знаний на каждом из отрезков могут записываться только 50 закономерностей, обладающих наилучшей достоверностью. Тогда достоверность будет неявно учитываться при выборе плавно меняющейся закономерности.
В проведенной серии экспериментов наилучшее качество распознавания достигается при значениях веса меры сходства закономерностей wЗітііаггіу в диапазоне от 0,G5 до 0,75 при всех рассмотренных уровнях шума.
