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

САРАПАС Владимир Викторович

Алгебраические методы синтеза алгоритмов

классификации элементов временных рядов

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

информатики

Автореферат

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

кандидата физико-математических наук

Москва – 2010

Работа выполнена на кафедре теоретической информатики и дискретной математики математического факультета Московского педагогического государственного университета

Научный руководитель:

член-корреспондент РАН, доктор физико-математических наук, профессор РУДАКОВ Константин Владимирович

Официальные оппоненты:

доктор физико-математических наук СМЕТАНИН Юрий Геннадьевич кандидат физико-математических наук, доцент ГУРОВ Сергей Исаевич

Ведущая организация:

Московский физико-технический институт (государственный университет)

Защита состоится 11 марта 2011 г. в 16 часов на заседании диссертационного совета Д 212.154.32 при Московском педагогическом государственном университете по адресу: 107140, г. Москва, ул.

Краснопрудная, д. 14, математический факультет МПГУ, ауд. 301.

С диссертацией можно ознакомиться в библиотеке Московского педагогического государственного университета: 119992, Москва, ул. Малая Пироговская, д. 1.

Автореферат разослан « » 20_ г.

Ученый секретарь диссертационного совета МУРАВЬЁВА О.В.

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

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

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

Академик РАН Ю.И. Журавлёв в 70-х годах XX века заложил основы алгебраического подхода к синтезу корректных алгоритмов распознавания образов. Алгебраический подход к проблеме распознавания образов позволил по-новому и эффективно решать многие задачи классификации, прогнозирования и, вообще говоря, задачи преобразования информации.

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

Растригин, Р.Х. Эренштейн и др.). В основополагающих работах Ю.И.

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

При дальнейших исследованиях были получены важные результаты для многих семейств алгоритмов и корректирующих операций над ними (А.Р. Ашуров, Ю.И. Журавлёв, И.В. Исаев, В.В. Краснопрошин, К.В.

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

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

Журавлёвым и его учениками, а исследования второго типа, для которых был создан специальный тонкий математический аппарат, были проведены академиком РАН В.Л. Матросовым. Им были устранены некоторые внешние противоречия между статистической теорией и алгебраическим подходом.

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

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

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

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

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

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

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

Объектом исследования являются методы алгебраического подхода к решению задач синтеза обучаемых алгоритмов выделения трендов временных рядов.

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

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

1) конкретизировать основные принципы и методы алгебраического подхода для задач выделения трендов;

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

3) исследовать построенные параметрические модели алгоритмов классификации элементов временных рядов;

4) разработать соответствующее программное обеспечение;

5) провести серию экспериментов и сделать необходимые выводы.

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

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

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

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

Основные положения, выносимые на защиту:

1) семейства фильтрующих алгоритмов выделения трендов временных рядов полны при системе локальных аксиом;

2) семейство фильтрующих алгоритмов с переменным параметром выделения трендов временных рядов полно при расширенной системе 3) алгебраическая коррекция результатов работы семейств алгоритмов в сплит-модели позволяет добиться улучшения результатов классификации;

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

Апробация работы. Результаты диссертационного исследования и его отдельные положения были представлены в докладах и выступлениях на кафедре теоретической информатики и дискретной математики Московского педагогического государственного университета, в отделе «Интеллектуальные системы» Вычислительного центра имени А.А.

Дородницына РАН, обсуждались на научно-практической конференции преподавателей, аспирантов и сотрудников математического факультета МПГУ (Москва, 2007, 2008), заседаниях круглого стола молодых ученых по приоритетным направлениям развития науки (Москва, 2007, 2008), Девятой международной научно-практической конференции «Высокие технологии, исследования, промышленность» (Санкт-Петербург, 2010), XI Всероссийской научно-практической конференции студентов, аспирантов и молодых учёных с международным участием «Молодежь и наука XXI века» (Красноярск, 2010), II Международной научно-практической конференции «Наука и современность – 2010» (Новосибирск, 2010). По теме диссертации опубликовано пять работ, в том числе одна в журнале, включённом в список ВАК.

Структура диссертации соответствует логике научного исследования, определяется его целью и основными задачами: работа (общим объёмом страниц) состоит из введения, трёх глав, заключения, списка литературы и приложения. Библиография включает 103 наименования научной литературы.

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

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

характеризуется общая методологическая база работы.

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

О постановке задачи распознавания имеет смысл говорить тогда, когда применение классических математических методов и построение формальных теорий чем-либо осложнено или вовсе невозможно. Располагая информацией о классах, благодаря параметризации моделей алгоритмов распознавания, можно синтезировать корректные алгоритмы для некоторых узких подклассов задач, при отсутствии точной модели изучаемых объектов и явлений. Важно отметить, что использование достаточно «богатых»

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

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

В соответствии с теорией члена-корреспондента РАН К.В. Рудакова, опишем задачу классификации в виде задачи синтеза алгоритма преобразования информации. Будем рассматривать некоторое множество S = {S }, элементы которого называются объектами. Описания объектов D(S ) образуют пространство начальных информаций Ii = {D( S ) S S}, элементы которого обозначаются I i, так что Ii = {I i }.

В первой главе рассматривается задача синтеза алгоритмов A, реализующих отображения из пространства начальных информаций Ii в пространство финальных информаций I f = {I f }. Далее мы не будем различать алгоритмы и реализуемые ими отображения. Решение синтезируется в рамках модели алгоритмов M, где M { A A : Ii I f }.

Задачи определяются структурными информациями I s, выделяющими из M подмножества допустимых отображений, обозначаемые M[ I s ]. Любой алгоритм A, реализующий произвольное допустимое отображение, называется корректным для задачи, определяемой структурной информацией I s, и является ее решением.

Конструкции алгебраического подхода к проблеме синтеза корректных алгоритмов основаны на использовании «промежуточного» по отношению к Ii и I f пространства оценок I e = {I e }. При этом корректные алгоритмы синтезируются на базе эвристических информационных моделей, т.е.

параметрических семейств отображений из Ii в I f, представляющих собой специальные суперпозиции алгоритмических операторов (отображений из Ii в I e ) и решающих правил (отображений из I e в I f, p – арность решающего правила).

Модели M определяются моделями алгоритмических операторов M 0, Для синтеза корректных алгоритмов используются также множества F корректирующих операций, определённых над множеством отображений M *. Корректирующие операции F, рассматриваемые в настоящей работе, индуцируются операциями F над пространством оценок I e :

где I i пробегает пространство начальных информаций Ii, алгоритмические операторы B1,..., B p – произвольные отображения из Ii в I e, и F – операция над I e.

Схема построения модели алгоритмов M представлена на следующей коммутативной диаграмме:

При зафиксированном пространстве возможных начальных информаций Ii и пространстве финальных информаций I f любую из задач определяет соответствующая структурная информация I s, являющаяся системой ограничений, которые выделяют из M * подмножество допустимых для задачи отображений M[ I s ]. Прецедентные ограничения, то есть наборы пар вида (( I i, I 1 ),..., ( I iq, I q )), сопровождаемые требованием A( I ik ) = I k при k {1,..., q}, являются характерной частью структурной информации в рассматриваемых задачах. Кроме того, структурная информация может содержать и дополнительные ограничения на вид отображений, реализуемых корректными алгоритмами. Член-корреспондент РАН К.В. Рудаков предложил рассматривать прецедентные и дополнительные ограничения как абсолютно равноправные части структурной информации. Прецедентные и дополнительные к ним ограничения имеют принципиально важное отличие:

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

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

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

Пусть имеется разбиение множества Z изучаемых задач с общей системой универсальных ограничений на классы эквивалентности по некоторому отношению « »: Z1 Z 2 если задачи Z1 и Z 2 неразличимы в момент выбора и анализа модели алгоритмов.

Задача Z из множества Z называется регулярной, если она разрешима и разрешимы все задачи из класса эквивалентности по отношению « », в который она входит.

Задача Z из множества Z называется полной относительно семейства M отображений из Ii в I f, если в M содержатся допустимые отображения для всех задач из класса эквивалентности, содержащего Z ;

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

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

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

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

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

В соответствии с теорией, изложенной в работах Ю.В. Чеховича, рассмотрим конечные наборы точек на плоскости S (v,t )R. Конечной S d = ( S 1,..., S d ) = ((t1, v1),..., (t d, v d )), где t R, v R, d 1. При этом значения t i, i = 1,..., d таковы, что t i < t i +1, либо t i t i +1, и если t i = t i +1, то v i < v i +1. В случае строгого неравенства будем называть конфигурацию однозначной, во втором случае – неоднозначной. Множество всех однозначных конфигураций определим как K = K d, а множество неоднозначных как K = K d. Очевидно, что K K. Мощностью конфигурации будем называть количество её точек.

Словарём разметки или множеством меток называется конечное множество M = {µ,..., µ r }, r 1.

Расширенным множеством меток или расширенным словарём разметки называется множество M = M {}, M, где - специальная метка, означающая «не размечено».

Например, разметка может быть такой: M = {min, max, down, up, plt}, где «min» - метка для обозначения точки минимума, «max» - точки максимума, «down» - точки убывания, «up» - точки возрастания, «plt» - точки плато.

Размеченным объектом называется пара ( S, µ ), где µ M.

Размеченной конфигурацией называется пара ( S d, µ d ), где S d K d для неоднозначной и S d K d для однозначной конфигураций, а µ d M d.

µ d называется разметкой или полной разметкой конфигурации S d. Если разметка µ d при этом называется частичной разметкой конфигурацией, конфигурации S d.

Алгоритмом разметки называется всякий алгоритм A, реализующий отображение A : C M такое, что для любого d 1 верно A( S d ) = µ d, где Аксиомами или правилами разметки называется набор = {,..., } эффективно вычислимых предикатов: : ( K d M d ) {0,1}.

Пусть фиксирована система аксиом разметки = {,..., }. Разметка µ d называется подходящей для S d, если ( S d, µ d ) = 1. Частичная разметка µ d M d называется подходящей для S d тогда и только тогда, когда существует полная подходящая разметка µ d, являющаяся продолжением µ d.

Система аксиом разметки = {,..., } является непротиворечивой тогда и только тогда, когда выполнено следующее условие:

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

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

Система аксиом разметки = {,..., } называется покрывающей тогда и только тогда, когда выполнено следующее условие:

S d µ d : ( S d, µ d ) = 1, то есть когда для любой конфигурации существует хотя бы одна подходящая разметка.

H = {( S i, µ i ) : S i K i ; µ i M i ; i = 1,..., q} называется набором прецедентов.

Задача Z выделения трендов заключается в синтезе подходящего алгоритма A, такого, что при всех i = 1,..., q полная разметка A( S i ) является продолжением разметки µ i, или, иначе говоря, такого, что выполнено условие:

Из того, что алгоритм A подходящий следует, что для всех i = A( S i ) выполнено условие: ( S i, i ) = 1.

Алгоритм A, удовлетворяющий условию (1) будем называть корректным для задачи Z.

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

В данной главе рассматривается задача синтеза корректного алгоритма для разметки произвольных конфигураций. Для неё разработана сплитмодель, позволяющая практически решать задачу выделения трендов. Данная модель содержит в себе два параметрических семейства алгоритмов Al и Для проведения одной из серий экспериментов, которая будет описана ниже, был зафиксирован словарь разметки M = {min, max, non} и система из четырёх аксиом:

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

1) фиксируется стартовая точка с индексом i = 1, она же отмечается как первая вершина ломаной;

2) задаётся k (начальное значение равно 2), через точки конфигурации с индексами i и i + k проводится прямая l ;

3) вычисляются расстояния d, где i < j < i + k, от точек с индексами j до прямой l ;

4) если все d, то k увеличивается на единицу и осуществляется переход к пункту 2, если в конфигурации остались нерассмотренные точки;

5) если хотя бы одно d >, то новой стартовой точкой становится точка с индексом i + k 1, она теперь рассматривается как точка с индексом i , она же отмечается как очередная вершина ломаной, k присваивается его начальное значение и осуществляется переход к пункту 2, если в конфигурации остались нерассмотренные точки;

6) последняя точка конфигурации отмечается как очередная вершина ломаной;

7) точки конфигурации, которые являются вершинами ломаной, размечаются в соответствии с их взаимным расположением, то есть, если «max», всем остальным точкам присваивается метка «non».

Второе параметрическое семейство A w имеет несколько параметров:

,,,...,, r 1, в рассматриваемом ниже случае r = 3 (по количеству меток в словаре разметки). Данное семейство устроено следующим образом:

1) для каждой точки конфигурации формируется вектор mi размерности, который будет заполняться значениями в процессе работы алгоритма;

фиксируется первых идущих подряд точек конфигурации;

среди зафиксированных точек проводится поиск минимума и максимума;

для найденных минимума и максимума в соответствующие векторы m добавляются метки «min» и «max», для остальных точек в векторы m добавляются метки «non»;

происходит смещение «окна» выделенных точек на точек вправо, если в конфигурации ещё остались нерассмотренные точки, таким образом, фиксируются очередные точек, осуществляется переход после того, как все точки конфигурации рассмотрены, и векторы m заполнены значениями меток, производится вычисление значений координат векторов w размерности 3 (по количеству меток в словаре разметки), которые сформированы для каждой точки конфигурации, по следующей схеме: первая координата – это произведение и количества меток «min» в соответствующем по индексу векторе mi, вторая – произведение и количества меток «max» и так далее.

7) в каждом векторе wi производится поиск максимального значения координаты и в соответствии с этим каждой точке конфигурации присваивается метка, т.е. если наибольшее значение имеет первая координата вектора w, то соответствующая точка размечается как «min», если наибольшее значение имеет вторая координата, то соответствующая точка размечается как «max» и так далее.

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

В соответствии с теорией, разработанной К.В. Рудаковым и Ю.В.

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

формализации понятия теоретико-множественных ограничений.

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

Определение 2.3.1. Множество Определение 2.3.2. Модель M называется -полной, если выполнены условия (2) и (3):

Определение 2.3.3. Семейство решающих правил M1 называется -полным, если существуют модель алгоритмических операторов M 0 и семейство Определение 2.3.4. При фиксированном -полном семействе решающих правил M1 семейство корректирующих операций F называется M1 полным, если существует модель алгоритмических операторов M 0 такая, Определение 2.3.5. При фиксированных -полном семействе решающих правил M1 и M1 -полном семействе корректирующих операций F модель алгоритмических операторов M 0 называется F M1 -полной, где при любом p из N 0 выполнено соотношение M1 {C C : I e I f }.

При этом для любого X I e оказывается, естественно, выполненным условие Определение 2.3.6. Пусть p N 0. Для произвольного I i из Ii множеством p (M1, I i ) называется пересечение в p -ой декартовой степени пространства решающих правил арности p :

Определение 2.3.7. Пусть p N 0. Для семейства M1 и элемента I i пространства Ii подмножество X ( I i ) пространства оценок I e называется допустимой p -проекцией, если выполнены условия (5) и (6):

Множество всех допустимых элемента I i обозначим p (M1, I i ).

Для произвольного I i из Ii введем множество (M1, I i ) функций выбора допустимых проекций:

где B(I e ) – множество всех подмножеств множества I e.

Для каждой функции выбора допустимых проекций из (M1, I i ) На приведённых выше определениях К.В. Рудакова и Ю.В. Чеховича базируются две предложенные ими следующие теоремы.

Теорема 2.3.1. При всех I i из Ii выполнено соотношение (7):

Теорема 2.3.2. (Критерий -полноты для семейств решающих правил).

Для -полноты семейства решающих правил M1 необходимо и достаточно, чтобы при любом I i из Ii было выполнено условие (8):

Далее во второй главе диссертации приведены определения и теоремы, сформулированные и доказанные автором данного исследования.

Рассмотрены так называемые фильтрующие алгоритмы выделения трендов временных рядов. Далее подразумевается использование словаря разметки {min, max, non}.

Определение 2.4.1. Назовём алгоритм разметки A фильтрующим с параметром, если результатом его работы является новая КПК S l и множество индексов Ind d.

Для фильтрующего алгоритма A имеем следующее (определение 2.3.6):

Теорема 2.4.1. Для A верно, что C (C 1 ( ( I i ))) = ( I i ).

Определение 2.4.2. Назовём алгоритм A (t ) фильтрующим с переменным параметром, если этот алгоритм является фильтрующим по определению 2.4.1 и использует новый параметр на каждой итерации.

Теорема 2.4.2. Семейство алгоритмов { A (t ) } полно.

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

В этой главе рассматриваются результаты работы нашей программы на пяти различных КПК. Данные для конфигураций – курсы валют, опубликованные Центробанком РФ.

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

Первая КПК:

Первый базовый алгоритм верно разметил 84 из 96 точек КПК, функционал качества второго алгоритма, рассмотренный в пункте 5 описания параметрического семейства A w, равен 18,8, результат работы третьего результирующего алгоритма 89 из 96 верно размеченных точек, = 0,05.

Улучшение качества работы алгебраической композиции алгоритмов относительно первого базового здесь составляет 5,21%.

Вторая КПК:

Первый базовый алгоритм верно разметил 270 из 285 точек КПК, функционал качества второго алгоритма, рассмотренный в пункте 5 описания параметрического семейства A w, равен 26,5, результат работы третьего результирующего алгоритма 273 из 285 верно размеченных точек, = 0,55.

Улучшение качества работы алгебраической композиции алгоритмов относительно первого базового здесь составляет 1,05%.

Третья КПК:

Первый базовый алгоритм верно разметил 78 из 87 точек КПК, функционал качества второго алгоритма, рассмотренный в пункте 5 описания параметрического семейства A w, равен 14,6, результат работы третьего результирующего алгоритма 83 из 87 верно размеченных точек, = 0,05.

Улучшение качества работы алгебраической композиции алгоритмов относительно первого базового здесь составляет 5,74%.

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

Первый набор:

Первый базовый алгоритм верно разметил 159 из 183 точек набора, функционал качества второго алгоритма, рассмотренный в пункте 5 описания параметрического семейства A w, равен 30,5, результат работы третьего результирующего алгоритма 175 из 183 верно размеченных точек, = 0,35.

Улучшение качества работы алгебраической композиции алгоритмов относительно первого базового здесь составляет 8,74%.

Второй набор:

Первый базовый алгоритм верно разметил 652 из 719 точек набора, функционал качества второго алгоритма, рассмотренный в пункте 5 описания параметрического семейства A w, равен 89,8, результат работы третьего результирующего алгоритма 702 из 719 верно размеченных точек, = 0,15.

Улучшение качества работы алгебраической композиции алгоритмов относительно первого базового здесь составляет 6,95%.

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

Далее в этой главе рассматривается работа экспериментальной программы в схемах и графиках.

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

Разработана сплит-модель, позволяющая практически решать задачу выделения трендов.

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

Описаны серии проведённых экспериментов с использованием разработанной программы, на схемах подробно представлены принципы её работы. Сделаны выводы о результатах экспериментов.

Основное содержание диссертации отражено в работах:

1. Sarapas V.V. Experimental Study of Synthesis Methods of Algorithms of Trends Allocation. // Pattern Recognition and Image Analysis. A Journal of Russian Academy of Sciences. City of Dover: Pleiades Publishing, c/o МАИК «Наука / Interperiodica», 2010. Vol. 20. №2. P.

2. Сарапас В.В. Параметрические семейства алгоритмических операторов для решения задач выделения трендов. // Высокие технологии, международной научно-практической конференции. Санкт-Петербург:

Изд-во Политехнического университета, 2010. Т. 3. С. 124 – 125. – 0, 3. Сарапас В.В. О классификации элементов временных рядов. // Математика, информатика, физика и их преподавание. М.: МПГУ, 2009. С. 163 – 164. – 0,2 п.л.

4. Сарапас В.В. Алгебраический подход к задаче выделения трендов временных рядов. // Молодежь и наука XXI века. Материалы XI Всероссийской научно-практической конференции студентов, аспирантов и молодых учёных с международным участием.

Красноярск: Изд-во КГПУ, 2010. Т. 1. С. 229 – 233. – 0,5 п.л.

5. Сарапас В.В. Об алгебраических методах синтеза алгоритмов выделения трендов временных рядов. // Наука и современность – 2010.

Сборник материалов II Международной научно-практической конференции. Новосибирск: Изд-во «СИБПРИНТ», 2010. Ч. 3. С. 77 – 82. – 0,5 п.л.