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

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

Алгебраические методы синтеза алгоритмов классификации элементов временных рядов

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

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

О з [>;др 2011

Москва-2010 ^Цч.

4856519

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

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

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

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

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

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

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

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

Защита состоится «■/"/» ММЖ^СС 2011 г. в<<, часов на заседании диссертационного совета Д 212.154.32 при Московском педагогическом государственном университете по адресу: 107140, г. Москва, ул. Краснопрудная, д. 14, математический факультет МПГУ, ауд. 301.

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

Автореферат разослан « 7 » фЩСШЗ 20 $ г.

Ученый секретарь

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

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

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

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

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

В основу алгебраического подхода легла идея выбирать некоторые алгоритмы из эвристических семейств и, используя подходящие корректирующие операции над ними, получать оптимальные алгоритмы для решаемых задач. Необходимо подчеркнуть, что вышеупомянутая идея активно использовалась и используется различными группами исследователей (Н.Г. Белецкий, B.C. Казанцев, В.Д. Мазуров, JI.A. Растригин, Р.Х. Эренштейн и др.). В основополагающих работах Ю.И. Журавлёва по алгебраическому подходу к распознаванию образов помимо использования и развития этой идеи были введены такие важные понятия алгебраического подхода, как регулярность и полнота.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Методы исследования. В настоящей работе использовались методы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В соответствии с теорией члена-корреспондента РАН К.В. Рудакова, опишем задачу классификации в виде задачи синтеза алгоритма преобразования информации. Будем рассматривать некоторое множество & = {5}, элементы которого называются объектами. Описания объектов £>(5) образуют пространство начальных информации 3; = {£>(5)| 5 е 6}, элементы которого обозначаются /,-, так что 3,- = {/,•}.

В первой главе рассматривается задача синтеза алгоритмов А, реализующих отображения из пространства начальных информации 3,- в пространство финальных информаций Зу = {/у}. Далее мы не будем

различать алгоритмы и реализуемые ими отображения. Решение синтезируется в рамках модели алгоритмов Ш, где Ш с {А\ А г иг- —17у}.

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

Конструкции алгебраического подхода к проблеме синтеза корректных алгоритмов основаны на использовании «промежуточного» по отношению к 3,- и 3у пространства оценок Зе ={1е). При этом корректные алгоритмы

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

специальные суперпозиции алгоритмических операторов (отображений из 3,в Зе) и решающих правил (отображений из в Зу, р - арность решающего правила).

Модели Ш определяются моделями алгоритмических операторов ЙЯ°, где 9Л° с9Я* = {2?| В:3,- Зе}, и решающих правил ЯЛ1, где

со

с и(С| С Зу} следующим образом:

Р=О

Ш1 = ЯЯ1оШ1° = {Со(В1х...хВр)д| Се®11,В1)...,Вре9Л0}. Для синтеза корректных алгоритмов используются также множества корректирующих операций, определённых над множеством отображений Ш*. Корректирующие операции F, рассматриваемые в настоящей работе,

индуцируются операциями Р над пространством оценок Зе:

ад.....вр){ц)=ада,).....(/,)),

где Ц пробегает пространство начальных информаций 3,-, алгоритмические операторы В\,...,Вр - произвольные отображения из 3,- в Зе, и Р -операция над Зе.

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

аяН Тал1

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

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

пар вида ((/■,7^),...,(/?,сопровождаемые требованием = при

/се{1,...,д}, являются характерной частью структурной информации в рассматриваемых задачах. Кроме того, структурная информация может содержать и дополнительные ограничения на вид отображений, реализуемых корректными алгоритмами. Член-корреспондент РАН К.В. Рудаков предложил рассматривать прецедентные и дополнительные ограничения как абсолютно равноправные части структурной информации. Прецедентные и дополнительные к ним ограничения имеют принципиально важное отличие: рассматривая алгоритм как «чёрный ящик» можно легко проверить, удовлетворяет ли он прецедентным ограничениям, однако осуществить такую проверку для дополнительных ограничений обычно невозможно.

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

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

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

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

Задача 2 из множества 3 называется полной относительно семейства 9Я отображений из 3,- в Зf, если в Ш содержатся допустимые

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

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

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

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

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

В соответствии с теорией, изложенной в работах Ю.В. Чеховича,

2

рассмотрим конечные наборы точек на плоскости . Конечной

плоской конфигурацией (КПК) назовём вектор

^ = .....= где 1. При этом

значения /',1 = 1.....таковы, что г1 </г+1, либо <гг+1, и если г' = гг+1, то

V* < у1+1 р случае строгого неравенства будем называть конфигурацию однозначной, во втором случае - неоднозначной. Множество всех

00 d

однозначных конфигураций определим как К = U К , а множество

1 d = 1 1

00 d

неоднозначных как К= U К ■ Очевидно, что К с К. Мощностью

d = 1 1 конфигурации будем называть количество её точек.

Словарём разметки или множеством меток называется конечное множество М = ,..., мг }> г ^ 1.

Расширенным множеством меток или расширенным словарём разметки называется множество М^ = Ми{А},АеМ, где Д - специальная метка,

означающая «не размечено».

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

Размеченным объектом называется пара {S,/i), где /ieM.

_j j _* j

Размеченной конфигурацией называется пара (S , Д ), где S еК для неоднозначной и Sd eKd для однозначной конфигураций, а fid eMd.

fid называется разметкой или полной разметкой конфигурации Sd. Если

1 1 _ J л

~fi еЛ/д, то пара (S ,fi ) называется частично размеченной

конфигурацией, разметка fid при этом называется частичной разметкой

конфигурации Sd.

Алгоришом разметки называется всякий алгоритм А, реализующий

отображение А:С->М такое, что для любого d > 1 верно A(Sd ) = fid, где

Sd zKd,fid eMd.

Аксиомами или правилами разметки называется набор П =

00 d d

эффективно вычислимых предикатов: ж.: (J (л х М") -»{0,1}.

1 d=1

Пусть фиксирована система аксиом разметки П = {я }. Разметка

х К

fid называется подходящей для Sd, если = Частичная

разметка fid е М^ называется подходящей для Sd тогда и только тогда,

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

Система аксиом разметки П = является непротиворечивой

тогда и только тогда, когда выполнено следующее условие:

3 d 3 Sd 3 Jid :U(Sd ,Jid) = l, то есть когда существует по меньшей Kd М

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

Система аксиом разметки П = является независимой тогда и

только тогда, когда выполнено условие:

V w 3 d 3 Sd 3 pd :(Ilw(Sd,Jid) = I)A(n(Sd,JId) = <)), где w = l...k d> 1 Kd M

Ilw ={/г.....я ,...,я\}, то есть, в том случае, когда при изъятии из

1 W — 1 W -f* 1 к

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

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

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

Система аксиом разметки П = {гг ,...,7Г,} называется покрывающей

1 к

тогда и только тогда, когда выполнено следующее условие:

VSd Э Jld :U{Sd,Jid) = \, то есть когда для любой конфигурации К Md

существует хотя бы одна подходящая разметка.

Произвольное конечное множество пар вида _d. d. _d. d. d. d. # = {(S\ 1 y/u.^-.S.1 eK l;fi. 1 eM^ ;i= l,...,q} называется набором

прецедентов.

Задача Z выделения трендов заключается в синтезе подходящего

-d.

алгоритма А, такого, что при всех i = l,...,q полная разметка ACS.1)

J.

является продолжением разметки ц 1, или, иначе говоря, такого, что выполнено условие:

У/ (я/ е V) => ((А/ * А) => (/// = г!У), (1)

О.....d.) 11 1

d. _d. где у.1 = A{S. 1).

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

II ll

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

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

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

модель содержит в себе два параметрических семейства алгоритмов А^ и

Aw.

Для проведения одной из серий экспериментов, которая будет описана ниже, был зафиксирован словарь разметки M - {min, шах, non} и система П из четырёх аксиом:

А1: Vf :(v <v.)a(v. >v.)=>^. *"min"A^. *"max" {2,...,d-l} 1-1 « i + l » « 1

A2: Vf :(v. , >v.)a(v. , <v.)=> u. *"min"AU. ¡¡¿"max" {2,...,d-l} 1 1 + 1 1 1 1

A3: Vf :(v. , >v.)a(v. >v.)=>//. *"max" {2,...,d-\} » « + 1 » »

A4: V/ :(v. . <v.)a(v. < v.)=>//. *"min" {2,...,d-l} '-1 1 ,+1 ' г

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

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

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

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

прямой / ;

4) если все d^<S, то к увеличивается на единицу и осуществляется

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

5) если хотя бы одно d ^>8, то новой стартовой точкой становится точка с

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

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

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

(v . >v )a(v. , > v ), to точка с индексом i размечается как «min», /-1 i г+l i

если (v . <v )a(v , <v ), то точка с индексом г размечается как 1-1 1 v i + 1 г

«шах», всем остальным точкам присваивается метка «поп».

Второе параметрическое семейство Aw имеет несколько параметров: co,a,Vy...,v ,r> 1, в рассматриваемом ниже случае г = 3 (по количеству

меток в словаре разметки). Данное семейство устроено следующим образом:

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

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

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

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

4) для найденных минимума и максимума в соответствующие векторы т

добавляются метки «min» и «max», для остальных точек в векторы т.

добавляются метки «поп»;

5) происходит смещение «окна» выделенных точек на а точек вправо, если в конфигурации ещё остались нерассмотренные точки, таким образом, фиксируются очередные со точек, осуществляется переход к пункту 3;

6) после того, как все точки конфигурации рассмотрены, и векторы т.

заполнены значениями меток, производится вычисление значений координат векторов w. размерности 3 (по количеству меток в словаре

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

меток «min» в соответствующем по индексу векторе т., вторая -

произведение v^ и количества меток «max» и так далее.

7) в каждом векторе w. производится поиск максимального значения

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

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

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

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

Вводится набор П = {щ.....л/,} предикатов щ :3,- х 3у -»{0,1} для

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

Пусть /,• - произвольный элемент пространства 3;. Положим П(/;-) = {//| /уеЗу, V j:Лj(Ij,If) = \} - множество всех допустимых

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

РШС = {((//,...,/?),(/}.....I})) |

| д е N.(//,...,/?) е 3?,// * /три ] * к,(/},...,/}) е 3},

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

У/г:9Л(/г) = {Л(/,-)| ЛеШ1}сП(/г); (2)

V ((1},...,1?),(Л,...,Л))ЗА: V ;:А{1/) = 1}. (3)

РЯЕС 3 ] ОТ {1,...,?} 7

Определение 2.3.3. Семейство решающих правил Ш11 называется П -полным,

если существуют модель алгоритмических операторов и семейство корректирующих операций 5 такие, что модель

Ш= у о$я(т0я 0>) является П-полной.

ЯбХое^Я)

Определение 2.3.4. При фиксированном П-полном семействе решающих правил 9Я1 семейство корректирующих операций # называется ОТ1 -П-полным, если существует модель алгоритмических операторов ЯЛ0 такая, что модель ОН = и и^Л1 о а) является П -полной.

Определение 2.3.5. При фиксированных П-полном семействе решающих

правил Ш11 и 9Я1 - П -полном семействе корректирующих операций #

модель алгоритмических операторов называется $ - 9Л1 - П -полной,

если модель ЙЯ= у УЗЯ1 щ) является П-полной.

ЛеЬшеЖ(Я)

1 00 1

Рассмотрим непустое семейство решающих правил ЯЛ = []Шр,

р=0

где при любом р из М0 выполнено соотношение 9Л^с{С| ->3у}.

При этом для любого X с:Зе оказывается, естественно, выполненным условие

®t1(X)= и и 1КОО-

р=О р=ОСе£Ш1р хеЛГ'

Определение 2.3.6. Пусть peNg. Для произвольного из 3/ множеством

afpiEDt1,/,-) называется пересечение в р -ой декартовой степени пространства оценок Зе всех полных прообразов множества П(/,) относительно решающих правил арности /?:

apm\li) = ПС_1(П(/;)) = {/е| Iee3§, V С:С(/е)еП(/,)}. (4) СеОТ1, ^

Определение 2.3.7. Пусть ре No- Для семейства 9Л1 и элемента /,■ пространства 3; подмножество Х(/г-) пространства оценок Зе называется допустимой р -проекцией, если выполнены условия (5) и (6):

Х{Ц)Р&ар{Ж\цу, (5)

-3ZСЗе :(*(/,-)сZ)Л(Z* сар(Ж\Ц)). (6)

Множество всех допустимых р -проекций для семейства ЯЯ1 и элемента /,- обозначим ^(ЯЛ1,//).

Для произвольного /,• из 3,- введем множество Ф(Ш11,/1) функций выбора допустимых проекций:

ФСШ11 ) = {ср\ <р:Щ~*В(Зе)Ур:((9Jtp = 0) =>^(Р) = Зе)л

N0

л «ал1, (?(/>) e ^(ая1, /,»)},

где В(Зе) - множество всех подмножеств множества Зе.

Для каждой функции выбора допустимых проекций ср из ФСЗЛ1,/,)

00

положим X(Ij,<p)= Р| <р(р). Отметим, что

Р=О

Ж\Х{1ь<р)) = (J [J С(([)<р(р)У).

r=OCe$OT' р=О Пусть Ф(®г1,/,) = {9?| <pe<b(m{,Ii),X(Ii,<p)*0}. На приведённых выше определениях К.В. Рудакова и Ю.В. Чеховича базируются две предложенные ими следующие теоремы. Теорема 2.3.1. При всех /,■ из 3,- выполнено соотношение (7):

и^те.рйеЩ/,). (7)

реФСЗП1,/,)

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

Для П -полноты семейства решающих правил ЯЯ1 необходимо и достаточно, чтобы при любом // из 3(- было выполнено условие (8):

II ЯК1 (*(//,?)) = П(/,). (8)

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

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

Определение 2.4.1. Назовём алгоритм разметки А§ фильтрующим с параметром 8, если результатом его работы является новая КПК 5' и множество индексов /ий?^ .

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

а1(аЯ1,//) = С-1(П(/,)).

Теорема 2.4.1. Для А§ верно, что С(С_1(П(/,))) = П(/г).

Определение 2.4.2. Назовём алгоритм А§^ фильтрующим с переменным

параметром, если этот алгоритм является фильтрующим по определению 2.4.1 и использует новый параметр на каждой итерации. Теорема 2.4.2. Семейство алгоритмов {Ду(/)} полно.

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

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

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

Первая КПК:

8 =0,03289; 0=5; ст = 1; V =0,2; У2=0,1; у3 =0,5.

Первый базовый алгоритм верно разметил 84 из 96 точек КПК, функционал качества второго алгоритма, рассмотренный в пункте 5 описания

параметрического семейства А™, равен 18,8, результат работы третьего результирующего алгоритма 89 из 96 верно размеченных точек, а =0,05.

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

8 =0,06927; со = 3; сг = 1; V =0,2; у2 =0,1; ^ =0,1.

Первый базовый алгоритм верно разметил 270 из 285 точек КПК, функционал качества второго алгоритма, рассмотренный в пункте 5 описания

параметрического семейства А™, равен 26,5, результат работы третьего результирующего алгоритма 273 из 285 верно размеченных точек, а=0,55. Улучшение качества работы алгебраической композиции алгоритмов относительно первого базового здесь составляет 1,05%. Третья КПК:

8 = 0,34436; со =7; <х = 1; v1=0,3; ^ =0,3; ^ =0,2.

Первый базовый алгоритм верно разметил 78 из 87 точек КПК, функционал качества второго алгоритма, рассмотренный в пункте 5 описания

параметрического семейства А™, равен 14,6, результат работы третьего результирующего алгоритма 83 из 87 верно размеченных точек, а =0,05. Улучшение качества работы алгебраической композиции алгоритмов относительно первого базового здесь составляет 5,74%.

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

8 =0,23571; со =6; <7 = 1; ^=0,3; 1^=0,2; =0,2.

Первый базовый алгоритм верно разметил 159 из 183 точек набора, функционал качества второго алгоритма, рассмотренный в пункте 5 описания

параметрического семейства Л™, равен 30,5, результат работы третьего результирующего алгоритма 175 из 183 верно размеченных точек, а =0,35. Улучшение качества работы алгебраической композиции алгоритмов относительно первого базового здесь составляет 8,74%. Второй набор:

8 = 0,09224; о =8; сг = 1; >^=0,5; v1 =0,3; Уъ =0,4.

Первый базовый алгоритм верно разметил 652 из 719 точек набора, функционал качества второго алгоритма, рассмотренный в пункте 5 описания

параметрического семейства А4', равен 89,8, результат работы третьего результирующего алгоритма 702 из 719 верно размеченных точек, а =0,15. Улучшение качества работы алгебраической композиции алгоритмов относительно первого базового здесь составляет 6,95%.

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

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

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

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

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

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

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

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

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

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

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

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

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, с/о МАИК «Наука / Interperiodica», 2010. Vol. 20. №2. P. 145-151.-0,75 пл.

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

Изд-во Политехнического университета, 2010. Т. 3. С. 124 - 125. - 0,25 п.л.

3. Сарапас В.В. О классификации элементов временных радов. // Математика, информатика, физика и их преподавание. М.: МПГУ, 2009. С. 163-164.-0,2 п.л.

4. Сарапас В.В. Алгебраический подход к задаче выделения трендов временных рядов. // Молодежь и наука XXI века. Материалы XI Всероссийской научно-практической конференции студентов, аспирантов и молодых учёных с международным участием. Красноярск: Изд-во КГПУ, 2010. Т. 1. С. 229 - 233. - 0,5 п.л.

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

Подп. к печ. 20.12.2010 Объем 1 п.л. Заказ № 148 Тир 100 экз.

Типография МПГУ

Введение.

Глава

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

1.1. О задачах распознавания и классификации.

1.2. Постановка задачи классификации в рамках алгебраического подхода.

1.3. Элементы теории универсальных и локальных ограничений.

1.4. О понятиях регулярности и полноты.

Глава

Постановка и формализация класса задач выделения трендов, описание методов решения задач этого класса, проблемы полноты

2.1. Постановка и формализация класса задач выделения трендов.

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

2.3. Проблемы полноты. Общие результаты.

2.4. Теоремы о полноте.

Глава

Экспериментальное исследование методов синтеза алгоритмов выделения трендов

3.1. Описание проведённых экспериментов.

3.2. О работе экспериментальной программы.

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

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

Для первого периода характерна разработка и реализация отдельных алгоритмов распознавания для конкретных прикладных задач. Стало ясно, что вместо адекватной математической модели, описывающей ту или иную ситуацию или предметную область, возможно использование пар вида «входная информация - выходная информация», то есть массивов прецедентов. В это время накапливались примеры корректно решённых прикладных задач и соответствующих алгоритмов, которые принято называть эвристическими, так как они построены на основе не имевших теоретического обоснования содержательных гипотез. Такие исследователи, как М.М. Бонгард, М.Н. Вайнцвайг, Н.Г. Загоруйко, Д.В. Кочетков, Г.С. Лбов, Г.С. Себастьян и другие, в своих работах описали общие принципы построения решений, базирующиеся на идее разделения точечных множеств гиперповерхностями, выделении частичных описаний объектов, использовании метрических характеристик, применении информационных весовых коэффициентов и других приёмах. Также в этот период появились первые труды по разработке специального общего математического аппарата для исследования задач и алгоритмов, в которых были отчасти теоретически обоснованы некоторые эвристические процедуры и конструкции (Л.А. Асланян, Ю.И. Журавлёв, C.B. Яблонский и другие).

Второй период характеризуется переходом от принципа «прикладная задача - алгоритм» к принципу «семейство алгоритмов -прикладная задача». Таким образом, были выделены параметрические семейства алгоритмов, которые имели универсальный характер и большое прикладное значение. Эти семейства принято называть моделями, или моделями алгоритмов распознавания, или эвристическими информационными моделями. Решение практических задач свелось к решению проблемы выбора значений параметров, выделяющих из семейства оптимальный для конкретной задачи алгоритм. Наибольшую известность среди моделей алгоритмов распознавания, возникших в этот период, имеют алгоритмы вычисления оценок (А.Р. Ашуров, И.Б. Гуревич, Ю.И. Журавлёв, B.JI. Матросов, К.В. Рудаков, В.В. Рязанов), алгоритмы метода потенциальных функций (М.А. Айзерман, Э.М. Браверман, Л.И. Розоноэр, К.В. Рудаков), алгоритмы, основанные на принципе комитетных решений (Н.Г. Белецкий, B.C. Казанцев, В.Д. Мазуров), статистические (В.Н. Вапник, В.И. Васильев, A.JI. Горелик, Н.Г. Загоруйко, Г.С. Лбов, А .Я. Червоненкис) и структурные (А.Б. Глаз, У. Гренандер) семейства. Следует подчеркнуть, что модели вычисления оценок (школа Ю.И. Журавлёва) включают в себя большинство используемых эвристических принципов и поэтому можно сказать, что они являются в некотором смысле универсальным языком для описания алгоритмов распознавания.

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

Академик РАН Ю.И. Журавлёв в 70-х годах XX века заложил основы алгебраического подхода к синтезу корректных алгоритмов распознавания образов [34]. Алгебраический подход к проблеме распознавания образов позволил по-новому и эффективно решать многие задачи классификации, прогнозирования и, вообще говоря, задачи преобразования информации. В основу алгебраического подхода легла идея о том, что помимо использования эвристических семейств алгоритмов в качестве фиксированных областей, где производится поиск решения, есть альтернативный путь: из данных семейств можно определенным образом выбирать некоторые алгоритмы и, используя подходящие корректирующие операции над ними, целенаправленно строить оптимальные алгоритмы для конкретных задач. Необходимо подчеркнуть, что идея совместного использования наборов алгоритмов при решении отдельных задач широко распространена и активно применяется различными группами исследователей (Н.Г. Белецкий, B.C. Казанцев, В.Д. Мазуров, JI.A. Растригин, Р.Х. Эренштейн и др.). Эта идея была использована в основополагающих работах Ю.И. Журавлева

33, 34] по алгебраическому подходу к распознаванию образов. Необходимо отметить, что Ю.И. Журавлёвым были также предложены так называемые «прямые методы» построения точных на прецедентах алгоритмов классификации путём применения специальных алгебраических операций к эвристическим распознающим операторам. Им были введены такие основополагающие понятия алгебраического подхода, как регулярность и полнота.

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

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

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

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

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

В рамках этого подхода Ю.В. Чехович разработал теорию [80-86], для решения задачи синтеза алгоритмов, описывающих отображения из пространства начальных информаций (конечных множеств точек на плоскости) во множество финальных информаций (множество конечных наборов «меток» - слов в конечном алфавите), то есть теорию синтеза алгоритмов выделения трендов временных рядов. В качестве основного объекта исследований Ю.В. Чехович рассматривает конечные множества точек на плоскости, которым могут соответствовать временные ряды различного вида и происхождения. Это могут быть данные информационных потоков в сетях связи, поведения атмосферных и океанических течений, колебаний земной коры, динамики биологических популяций, наблюдений излучения, приходящего из космоса, медицинских и биологических сигналов, колебательных и волновых процессов в радиофизических устройствах, показателей финансового рынка и другие. Для обозначения таких множеств Ю.В. Чеховичем было введено понятие конечных плоских конфигураций (КПК). Обычно при решении прикладных задач возникает необходимость выделения внутри временного ряда так называемых трендов. Как правило, трендом называют интервал временного ряда, не содержащий точек экстремума. В работах Ю.В. Чеховича под выделением трендов подразумевается решение задачи классификации, в которой каждой точке конфигурации сопоставляется номер класса из заранее определенного множества классов или, говоря иначе, метка из фиксированного словаря разметки.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

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

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

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

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

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

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

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

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

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

1. Авдеенко Т.В. Компьютерные методы анализа временных рядов и прогнозирования. Новосибирск: НГТУ, 2008. 270 с.

2. Айзерман М.А., Браверман Э.М., Розоноэр Л.И. Метод потенциальных функций в теории обучения машин. М.: Наука, 1970. 320 с.

3. Алексанян A.A., Журавлев Ю.И. Об одном подходе к построению эффективных алгоритмов распознавания // ЖВМ и МФ. 1985. Т. 25, №2, с. 283-291.

4. Алимов Ю.И. Альтернатива методу математической статистики. Знание, 1980.

5. Асарин Е.А. О некоторых свойствах случайных в алгоритмическом смысле конечных объектов // ДАН СССР. 1987. Т. 295, № 4. С. 782785.

6. Асланян Л.А. Алгоритмы распознавания с логическими отделителями // Сб. работ по матем. кибернетике. Вып. 1. М.: ВЦ АН СССР, 1976, с. 116-131.

7. Ашуров А.Р., Рудаков K.B. О задачах распознавания образов с континуальной начальной информацией. М.: ВЦ АН СССР, 1983. 21 с.

8. Ашуров А.Р., Рудаков К.В. Алгоритмы вычисления оценок для задач с континуальной начальной информацией // ЖВМ и МФ. 1984. Т. 24, № 12, с. 1871-1880.

9. Белецкий Н.Г. Задача коррекции параметров объекта в распознавании образов // ЖВМ и МФ. 1987. Т. 27, № 4, с. 610-616.

10. Ю.Бонгард М.М. Проблема узнавания. М.: Наука, 1967. 320 с.

11. П.Борисова И.А., Дюбанов В.В., Загоруйко Н.Г., Кутненко O.A. Сходство и компактность // Всеросс. конф. Математические методы распознавания образов-14. М.: МАКС Пресс, 2009. С. 89-92.

12. Бурбаки Н. Теория множеств, М. Мир, 1965. 456 с.

13. Ботов П.В. Точные оценки вероятности переобучения для монотонных и унимодальных семейств алгоритмов // Всеросс. конф. Математические методы распознавания образов-14. М.: МАКС Пресс, 2009. С. 7-10.

14. Вапник В.Н. Восстановление зависимостей по эмпирическим данным. М.: Наука, 1979. 448 с.

15. Вапник В.Н., Червоненкис А .Я. Теория распознавания образов. М.: Наука, 1974.

16. Васильев В.И. Распознающие системы. Киев: Наукова думка, 1983. 466 с.

17. Венжега A.B., Ументаев С.А., Орлов A.A., Воронцов К.В. Проблема переобучения при отборе признаков в линейной регрессии с фиксированными коэффициентами // Математические методы распознавания образов-13. М.: МАКС Пресс, 2007. С. 90-93.

18. Воронцов К.В. О проблемно-ориентированной оптимизации базисов задач распознавания // ЖВМ и МФ. 1998 Т. 38, № 5, с. 870-880.

19. Воронцов К.В. Оптимизационные методы линейной и монотонной коррекции в алгебраическом подходе к проблеме распознавания // ЖВМ и МФ. 2000. Т. 40, №1, с. 166-176.

20. Воронцов К.В., Рудаков К.В., Чехович Ю.В. Информационные методы анализа сложных систем // Тезисы докладов научной конференции "Математические модели сложных систем и междисциплинарные исследования", ВЦ РАН им. A.A. Дородницына, 2002 г., Москва, с. 9.

21. Воронцов К.В. Обзор современных исследований по проблеме качества обучения алгоритмов // Таврический вестник информатики и математики. 2004. № 1. С. 5-24.

22. Воронцов К.В. Слабая вероятностная аксиоматика и надёжность эмпирических предсказаний // Математические методы распознавания образов-13. М.: МАКС Пресс, 2007. С. 21-25.

23. Воронцов К.В. Комбинаторный подход к проблеме переобучения // Всеросс. конф. Математические методы распознавания образов-14. М.: МАКС Пресс, 2009.С. 18-21.

24. Гаек Я., Шидак 3. Теория ранговых критериев. М.: Наука, 1971.

25. Гуз И.С. Нелинейные монотонные композиции классификаторов // Математические методы распознавания образов-13. М.: МАКС Пресс, 2007. С. 111-114.

26. Дуда Р., Харт П. Распознавание образов и анализ сцен. М.: Мир, 1976.

27. Дюкова Е.В. Дискретные (логические) процедуры распознавания: принципы конструирования, сложность реализации и основные модели. М.: Прометей, 2003. 29 с.

28. Дюкова Е.В. О числе тупиковых покрытий целочисленной матрицы // ЖВМ и МФ. 2005. Vol. 45, по. 5. Pp. 935-940.

29. ДюковаЕ.В., ИнякинА.С. О процедурах классификации, основанных на построении покрытий классов // ЖВМ и МФ. 2003. Т. 43, № 12. С. 1910-1921.

30. Журавлев Ю.И. Локальные алгоритмы вычисления информации I, II //Кибернетика 1965 г. № 1, с. 12-19, 1966 г. №2, с. 1-11.

31. Журавлев Ю.И. Об одном классе алгоритмов над конечными множествами, ДАН СССР, т 151, 5, М. 1963, с. 1025-1028.

32. Журавлев Ю.И., Лосев Г.Ф. Окрестности в задачах дискретной математики // Кибернетика и системный анализ, 1995 г., №2, с. 3241.

33. Журавлев Ю.И. Корректные алгебры над множествами некорректных (эвристических) алгоритмов. I-III // Кибернетика. 1977. № 4, с. 5-17, 1977, № 6, с. 21-27, 1978, № 2, с. 35-43.

34. Журавлев Ю.И. Об алгебраическом подходе к решению задач распознавания и классификации // Проблемы кибернетики. Вып. 33 М.: Наука, 1978, с. 5-68.

35. Журавлев Ю.И. Рудаков К.В. Об алгебраической коррекции процедур обработки (преобразования) информации // Проблемы прикладной математики и информатики. М. Наука, 1987, с. 187-198.

36. Ивахненко A.A., Воронцов K.B. Верхние оценки переобученности и профили разнообразия логических закономерностей // Математические методы распознавания образов-13. М.: МАКС Пресс, 2007. С. 33-37.

37. Кац Дж. О., МакКормик Д. JI. Энциклопедия торговых стратегий //Пер. с англ. — Москва, Альпина Паблишер, 2002. 400 с.

38. Колби Р.В., Мейерс Т.А., Энциклопедия технических индикаторов рынка //Пер. с англ. Москва, Альпина, 1998. 581 с.

39. Колмогоров А.Н. Теория информации и теория алгоритмов / Под ред. Ю.В. Прохорова. М.: Наука, 1987. 304 с.

40. Кочедыков Д.А. Структуры сходства в семействах алгоритмов классификации и оценки обобщающей способности // Всеросс. конф. Математические методы распознавания образов-14. М.: МАКС Пресс, 2009. С. 45-48.

41. Лбов Г.С. Методы обработки разнотипных экспериментальных данных. Новосибирск: Наука, 1981.

42. Леонтьев В.К., Сметанин Ю.Г. О восстановлении вектора по набору его фрагментов. // ДАН СССР. 1988. - Т. 302, № 6, с. 1319 - 1322.

43. Мазуров В.Д. Метод комитетов в задачах оптимизации и классификации. М. Наука. 1990. 248 с.

44. Матросов В.Л. Нижние оценки емкости многомерных алгебр алгоритмов вычисления оценок // ЖВМ и МФ. 1984, Т. 24, № 12, с. 1881-1892.

45. Матросов В.Л. Емкость алгебраических расширений модели алгоритмов вычисления оценок // ЖВМ и МФ. 1984, Т. 11, № 5, с. 1719-1730.

46. Матросов В.Л. Емкость полиномиальных расширений множества алгоритмов вычисления оценок // ЖВМ и МФ. 1985, Т. 25, № 1, с. 122-133.

47. Матросов В.Л. Корректные алгебры ограниченной емкости над множествами некорректных алгоритмов // ДАН СССР. 1980, Т. 253, № 1, с. 25-30.

48. Матросов В.Л. Корректные алгебры ограниченной емкости над множествами некорректных алгоритмов // ЖВМ и МФ. 1981, Т. 21, №5, с. 1276-1291.

49. Матросов В.Л. О критериях полноты модели алгоритмов вычисления оценок и ее алгебраических замыканий // ДАН СССР. 1981, Т. 258, № 4, с. 791-796.

50. Матросов В.Л. Оптимальные алгебры в алгебраических замыканиях операторов вычисления оценок // ДАН СССР. 1982, Т. 262, № 4, с. 818-822.

51. Матросов В.JI. Синтез оптимальных алгоритмов в алгебраических замыканиях моделей алгоритмов распознавания // Распознавание, классификация, прогноз. М.: Наука, 1989, с. 149-176.

52. Минский М., Пайперт С. Персептроны. М.: Мир, 1971.

53. Норушис А. Построение логических (древообразных) классификаторов методами нисходящего поиска (обзор) // Статистические проблемы управления. Вып. 93 / Под ред. Ш. Раудис. Вильнюс, 1990. С. 131-158.

54. Райгородский A.M. Экстремальные задачи теории графов и анализ данных. М.: НИЦ «Регулярная и хаотическая динамика», Институт компьютерных исследований, 2008. 118 с.

55. Растригин Л.А., Эренштейн Р.Х. Коллективные правила распознавания. М.: Энергия, 1981. 244 с.

56. Рудаков К.В. Алгебраическая теория универсальных и локальных ограничений для алгоритмов распознавания. Дис. . докт. физ.-мат. наук. Москва, 1991. 146 с.

57. Рудаков К.В. О некоторых универсальных ограничениях для алгоритмов классификации // ЖВМ и МФ. 1988, Т.26, № 11, с. 1719 1729.

58. Рудаков К.В. О применении универсальных ограничений при исследовании алгоритмов классификации // Кибернетика. 1988, № 1, с. 1-5.

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

60. Рудаков К.В. Построение проблемно-ориентированных теорий на основе алгебраического подхода к задачам распознавания образов // Доклады 10-й Всероссийской конференции "Математические методы распознавания образов", Москва, АЛЕВ-В, 2001, с. 113-115.

61. Рудаков К.В. Симметрические и функциональные ограничения для алгоритмов классификации // Кибернетика. 1987, № 4, с. 73-77.

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

63. Рудаков К.В., Чехович Ю.В. О проблеме синтеза обучаемых алгоритмов выделения трендов (алгебраический подход) // Прикладная математика и информатика, 2001, № 8, с. 97-113.

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

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

66. Рудаков К.В., Чехович Ю.В. Критерии полноты моделей алгоритмов и семейств решающих правил для задач классификации с теоретико-множественными ограничениями // ДАН. 2004, Т. 394, № 4, с. 1-3.

67. Рязанов В.В. Комитетный синтез алгоритмов распознавания и классификации//ЖВМ и МФ. 1981, Т. 21, № 6, с. 1533-1543.

68. Рязанов В.В. О построении оптимальных алгоритмов распознавания и таксономии (классификации) при решении прикладных задач // Распознавания, классификация, прогноз. Выпуск 1. М.: Наука. 1989, с. 229-279.

69. Рязанов В. В., Сенько О. В. О некоторых моделях голосования и методах их оптимизации // Распознавание, классификация, прогноз. 1990. Т. 3. С. 106-145.

70. Сметанин Ю.Г. Распознавание при представлении исходных данных в виде длинных последовательностей. // Распознавание,классификация и прогноз. Математические методы и их применения. Вып. 2. М.: Наука. 1988, с. 38 41.

71. Хайкин С. Нейронные сети: полный курс, 2-е издание. М.: Издательский дом «Вильяме», 2006.

72. Черепнин A.A. О радиусах разрешимости и регулярности задач распознавания // Доклады 11-й Всероссийской конференции "Математические методы распознавания образов", 2003, Пущино, с. 210-211.

73. Черепнин A.A. Об оценках регулярности задач распознавания и классификации // Журнал вычислительной математики и математической физики. 1993, №1, с. 155-159

74. Чехович Ю.В. Об обучаемых алгоритмах выделения трендов // Интеллектуализация обработки информации: тезисы докладов Международной научной конференции, Симферополь, 2002, с. 153154.

75. Чехович Ю.В. Мощности окрестностей в задачах выделения трендов // Доклады 11-й Всероссийской конференции "Математические методы распознавания образов". Пущино, 2003, с. 215-216.

76. Чехович Ю.В. Элементы алгебраической теории синтеза обучаемых алгоритмов выделения трендов. Дис. . канд. физ.-мат. наук. Москва, 2003. 70 с.

77. Abu-Mostafa Y. S. Hints // Neural Computation. 1995. Vol. 7, no. 4. Pp. 639-671.

78. Anderson A.P. Algorythm synthesis: A comparative study // D.M. Steier, A.P. Anderson. New York etc.: Springer, Cop. 1989. VIII. 118 p.

79. Anthony M. Uniform glivenko-cantelli theorems and concentration of measure in the mathematical modelling of learning: Tech. Rep. LSE-CDAM-2002-07: 2002.

80. Anthony M., Bartlett P.L. Neural Network Learning: Theoretical Foundations. Cambridge University Press, Cambridge, 1999.

81. Bontempi G., Birattari M. A bound on the cross-validation estimate for algorithm assessment // Eleventh Belgium/Netherlands Conference on Arti.cial Intelligence (BNAIC). 1999. Pp. 115-122.

82. Bousquet O., Elissee. A. Algorithmic stability and generalization performance // Advances in Neural Information Processing Systems 13. 2001. Pp. 196-202.

83. Cohen W. W., Singer Y. A simple, fast and e.ective rule learner // Proc. of the 16 National Conference on Arti.cial Intelligence. 1999. Pp. 335342.

84. Elissee. A., Evgeniou T., Pontil M. Stability of randomized learning algorithms // Journal of Machine Learning Research. 2005. no. 6. Pp. 5579.

85. Kearns M., Valiant L.G. Cryptographic limitations on learning Boolean formulae and finite automata // Proc. of the 21st Annual ACM Symposium on Theory of Computing. 1989. Pp. 433-444.

86. Kittler I. Feature set search algoritms // Pattern Recogn. and Signal Process. 1978. P. 41-60.

87. Leont'ev V.K., Smetanin Yu.G. Problems of Information on the Set of Words. // Journal of Mathematical Sciences. Kluwer Academic/Consultants Bureau, New York, 2000, p. 49-70.

88. Leont'ev V.K., Smetanin Yu.G. Recognition Model with Representation of Information in the Form of Long Sequences. // Pattern Recognition and Image Analysis: Advances in Mathematical Theory and Applications. 2002, Vol. 12, No. 3, p. 250-287.

89. Mann H. B., Whitney D. R. On a test of whether one of two random variables is stochastically larger than the other // The Annals of Mathematical Statistics. 1947. Vol. 18, no. 1. Pp. 50-60.

90. Pavel M. Algebraic, topological and cathegorial aspects of pattern recognition: a survey // Pattern Recogn. 1981, V. 14, № 1-6, p. 117-120.

91. Quinlan J. Induction of decision trees // Machine Learning. 1986. Vol. 1, no. l.Pp. 81-106.

92. Rivest R. L. Learning decision lists // Machine Learning. 1987. Vol. 2, no. 3. Pp. 229-246.