Содержание к диссертации
Введение
Глава 1 Описание основных конструкций алгебраического подхода к задачам распознавания и классификации
1.1. О задачах распознавания и классификации 15
1.2. Постановка задачи классификации в рамках алгебраического подхода .. 19
1.3. Элементы теории универсальных и локальных ограничений 23
1.4. О понятиях регулярности и полноты 26
Глава 2 Постановка и формализация класса задач выделения трендов, описание методов решения задач этого класса, проблемы полноты
2.1. Постановка и формализация класса задач выделения трендов 30
2.2. Описание параметрических семейств алгоритмических операторов для решения задач выделения трендов 38
2.3. Проблемы полноты. Общие результаты 44
2.4. Теоремы о полноте 53
Глава 3 Экспериментальное исследование методов синтеза алгоритмов выделения трендов
3.1. Описание проведённых экспериментов 55
3.2. О работе экспериментальной программы 63
Заключение 67
Список литературы 70
Приложение 84
- Постановка задачи классификации в рамках алгебраического подхода
- Элементы теории универсальных и локальных ограничений
- Описание параметрических семейств алгоритмических операторов для решения задач выделения трендов
- О работе экспериментальной программы
Введение к работе
Актуальность темы исследования. Создание и исследование систем распознавания образов является трудоёмкой теоретической и технической задачей, необходимость её решения возникает в различных областях. Одним из направлений теории распознавания образов является алгебраический подход, включающий в себя методы построения проблемно-ориентированных теорий синтеза корректных алгоритмов распознавания образов на базе параметрических семейств операторов.
Алгебраический подход возник в результате исследований, в которых соответствующие решаемым задачам алгоритмы преобразования информации строились в контексте отсутствия подходящих математических моделей конкретных ситуаций.
Академик РАН Ю.И. Журавлёв в 70-х годах XX века заложил основы алгебраического подхода к синтезу корректных алгоритмов распознавания образов. Алгебраический подход к проблеме распознавания образов позволил по-новому и эффективно решать многие задачи классификации, прогнозирования и, вообще говоря, задачи преобразования информации.
В основу алгебраического подхода легла идея выбирать некоторые алгоритмы из эвристических семейств и, используя подходящие корректирующие операции над ними, получать оптимальные алгоритмы для решаемых задач. Необходимо подчеркнуть, что вышеупомянутая идея активно использовалась и используется различными группами исследователей (Н.Г. Белецкий, B.C. Казанцев, В.Д. Мазуров, Л.А. Растригин, Р.Х. Эренштейн и др.). В основополагающих работах Ю.И. Журавлёва по алгебраическому подходу к распознаванию образов помимо использования и развития этой идеи были введены такие важные понятия алгебраического подхода, как регулярность и полнота.
При дальнейших исследованиях были получены важные результаты для многих семейств алгоритмов и корректирующих операций над ними (А.Р. Ашуров, Ю.И. Журавлёв, И.В. Исаев, В.В. Краснопрошин, К.В. Рудаков, В.В. Рязанов и др.). В итоге всех вышеперечисленных исследований алгебраический подход стал общетеоретической базой для решения задач распознавания и используемых при этом математических конструкций и методов.
Отметим, что применение алгебраических конструкций было обосновано на базе принятия некоторых дополнительных метрических и статистических гипотез. Исследования первого типа проводились Ю.И. Журавлёвым и его учениками, а исследования второго типа, для которых был создан специальный тонкий математический аппарат, были проведены академиком РАН В.Л. Матросовым. Им были устранены некоторые внешние противоречия между статистической теорией и алгебраическим подходом.
Основополагающие идеи академика РАН Ю.И. Журавлёва развил в своих трудах член-корреспондент РАН К.В. Рудаков. Он разработал алгебраическую теорию универсальных и локальных ограничений для алгоритмов распознавания, чем расширил границы применимости идей
алгебраического подхода. Им была исследована проблема разрешимости и регулярности задач классификации и получен общий необходимый и достаточный критерий регулярности, который для отдельных конкретных систем универсальных ограничений сводится к легко проверяемым на практике условиям. Также К.В. Рудаковым были получены критерии полноты для моделей алгоритмов как на общем уровне, так и для конкретных систем универсальных ограничений; выявлены критерии полноты для моделей алгоритмических операторов и семейств корректирующих операций и сформулировано понятие корректности семейств решающих правил.
При решении многих прикладных задач часто возникает необходимость выделения внутри временного ряда так называемых трендов. Как правило, трендом называют интервал временного ряда, не содержащий точек экстремума. Задачи выделения трендов временных рядов находятся в центре многих отраслей науки и прикладных сфер.
В реферируемой диссертации под выделением трендов подразумевается решение задачи классификации, в которой каждой точке ряда сопоставляется номер класса из заранее определенного множества классов или, говоря иначе, метка из фиксированного словаря разметки. Анализ распределенных во времени элементов требует применения комплексных решений, что и обеспечивают алгебраические методы синтеза алгоритмов классификации. Алгебраический подход как способ построения проблемно-ориентированных теорий синтеза корректных алгоритмов распознавания образов на базе параметрических семейств операторов, позволяет построить такую теорию над предметной областью, объектами изучения которой будут являться обучаемые алгоритмы выделения трендов, семейства алгоритмов и операции над ними.
В рамках алгебраического подхода К.В. Рудаков и Ю.В. Чехович разработали общую теорию задач с теоретико-множественными ограничениями. Также была разработана специализация этой теории для решения задач синтеза алгоритмов, описывающих отображения из пространства начальных информации - конечных множеств точек на плоскости - во множество финальных информации - множество конечных наборов «меток» - слов в конечном алфавите., то есть алгоритмов выделения трендов временных рядов.
При этом не были построены конкретные примеры моделей, удовлетворяющие разработанной теории. Поэтому построение, теоретическое и экспериментальное исследование таких семейств оставалось нерешённой актуальной задачей. В реферируемой диссертации такие модели предложены, а также проведено их теоретическое и экспериментальное исследование.
Объектом исследования являются методы алгебраического подхода к решению задач синтеза обучаемых алгоритмов выделения трендов временных рядов.
Предмет исследования составили параметрические семейства алгоритмов, семейства корректирующих операций и решающих правил для задач синтеза обучаемых алгоритмов выделения трендов временных рядов.
Целью данной работы является синтез и исследование параметрических семейств алгоритмов классификации элементов временных рядов, допускающих минимум ошибок на прецедентах и удовлетворяющих наборам дополнительных ограничений. Для достижения указанной цели в работе поставлены и решены следующие задачи:
конкретизировать основные принципы и методы алгебраического подхода для задач выделения трендов;
построить параметрические модели алгоритмов классификации элементов временных рядов, задать семейства корректирующих операций над этими алгоритмами и семейства решающих правил;
исследовать построенные параметрические модели алгоритмов классификации элементов временных рядов;
разработать соответствующее программное обеспечение;
5) провести серию экспериментов и сделать необходимые выводы.
Методы исследования. В настоящей работе использовались методы
алгебраического подхода к распознаванию образов, теории задач с теоретико-множественными ограничениями, теории оптимизации, системного анализа, для проведения экспериментов использовались специально разработанные программные средства.
Научная новизна исследования обусловлена тем, что в его рамках созданы новые модели алгоритмов, проведён их анализ с помощью аппарата теории задач с теоретико-множественными ограничениями и тем, что впервые разработана программа для синтеза обучающихся алгоритмов выделения трендов временных рядов.
Теоретическая значимость обусловлена, прежде всего, тем, что впервые для анализа моделей алгоритмов используется теория задач с теоретико-множественными ограничениями. Данное исследование развивает и дополняет алгебраическую теорию синтеза обучаемых алгоритмов выделения трендов временных рядов.
Практическая значимость заключается в том, что результаты работы могут быть использованы в дальнейших научных исследованиях, посвященных проблеме выделения трендов временных рядов, а также в возможности использования результатов исследования в таких практических сферах, как экономика, астрономия, медицинская диагностика, геологический анализ.
Основные положения, выносимые на защиту:
семейства фильтрующих алгоритмов выделения трендов временных рядов полны при системе локальных аксиом;
семейство фильтрующих алгоритмов с переменным параметром выделения трендов временных рядов полно при расширенной системе аксиом;
алгебраическая коррекция результатов работы семейств алгоритмов в сплит-модели позволяет добиться улучшения результатов классификации;
результаты экспериментального исследования демонстрируют практическую применимость разработанных конструкций.
Апробация работы. Результаты диссертационного исследования и его
отдельные положения были представлены в докладах и выступлениях на
кафедре теоретической информатики и дискретной математики Московского
педагогического государственного университета, в отделе
«Интеллектуальные системы» Вычислительного центра имени А.А. Дородницына РАН, обсуждались на научно-практической конференции преподавателей, аспирантов и сотрудников математического факультета МПГУ (Москва, 2007, 2008), заседаниях круглого стола молодых ученых по приоритетным направлениям развития науки (Москва, 2007, 2008), Девятой международной научно-практической конференции «Высокие технологии, исследования, промышленность» (Санкт-Петербург, 2010), XI Всероссийской научно-практической конференции студентов, аспирантов и молодых учёных с международным участием «Молодежь и наука XXI века» (Красноярск, 2010), II Международной научно-практической конференции «Наука и современность - 2010» (Новосибирск, 2010). По теме диссертации опубликовано пять работ, в том числе одна в журнале, включённом в список ВАК.
Структура диссертации соответствует логике научного исследования, определяется его целью и основными задачами: работа (общим объёмом 102 страниц) состоит из введения, трёх глав, заключения, списка литературы и приложения. Библиография включает 103 наименования научной литературы.
Постановка задачи классификации в рамках алгебраического подхода
В контексте алгебраического подхода к синтезу корректных алгоритмов распознавания образов, классификации и прогнозирования [33, 34] рассматривается класс задач, характеризующийся наличием явным образом заданных теоретико-множественных ограничений на множество допустимых ответов алгоритма.
В соответствии с теорией члена-корреспондента РАН К.В. Рудакова [62, 63, 64], опишем задачу классификации в виде задачи синтеза алгоритма преобразования информации. Будем рассматривать некоторое множество & = {S}, элементы которого называются объектами. Описания объектов D(S) образуют пространство начальных информации Jj - {D(S)\ S є }, элементы которого обозначаются Ij, так что 3j ={//}.
Рассматривается задача синтеза алгоритмов А, реализующих отображения из пространства начальных информации 3f в пространство финальных информации Зг={1Л. Далее мы не будем различать алгоритмы и реализуемые ими отображения. Решение синтезируется в рамках модели алгоритмов 971, где 9ЯС{У4 A:3J —»3у}. Задачи определяются структурными информациями Is, выделяющими из ЇЇЯ подмножества допустимых отображений, обозначаемые 9Я7у]. Любой алгоритм А, реализующий произвольное допустимое отображение, называется корректным для задачи, определяемой структурной информацией Is, и является ее решением.
Для рассматриваемых нами задач с теоретико-множественными ограничениями модели алгоритмов ЯЯ строятся на базе параметрических семейств моделей алгоритмических операторов и корректирующих операций. Кроме того, структурная информация может содержать и дополнительные ограничения на вид отображений, реализуемых корректными алгоритмами. Член-корреспондент РАН К.В. Рудаков предложил [62, 63, 64] рассматривать прецедентные и дополнительные ограничения как абсолютно равноправные части структурной информации. Прецедентные и дополнительные к ним ограничения имеют принципиально важное отличие: рассматривая алгоритм как «чёрный ящик» можно легко проверить, удовлетворяет ли он прецедентным ограничениям, однако осуществить такую проверку для дополнительных ограничений обычно невозможно.
Дополнительные к прецедентным ограничения обязательно должны вводиться так, чтобы синтезируемые алгоритмы удовлетворяли им «по построению». Эти ограничения должны представлять собой систему требований, применимых как к отображениям из 3f в 3 j-, так и к отображениям из 3; в Зе, из 3е в себя и из Зе в 3 f, причём не только к унарным, но и к р -арным при р 1. Таким образом, эти ограничения должны иметь смысл для моделей алгоритмических операторов, семейств корректирующих операций и решающих правил. Дополнительные ограничения должны строиться так, чтобы синтезированные в виде (1.3.1) из удовлетворяющих этим ограничениям алгоритмических операторов, корректирующих операций и решающих правил алгоритмы сами удовлетворяли данным ограничениям.
Системы ограничений Is распадаются на пары (/",/5) подсистем, которые называются [62, 63, 64] системами универсальных и локальных ограничений соответственно. Локальные ограничения (далее будут рассматриваться только прецедентные ограничения) - условия, относящиеся к отображениям из 3; в 3 f, которые можно проверить за конечное число шагов. Универсальные ограничения должны относиться ко всем отображениям, используемым при синтезе алгоритмов методами алгебраического подхода и сохраняться при образовании суперпозиций вида (1.3.1).
Необходимо отметить, что универсальные ограничения всегда трактуются как формальные описания реальной информации о предметной области. При этом возможно, что универсальные ограничения будут противоречить прецедентным, то есть будет выполнено равенство 9tt[/" ] П %KUS ] = 0, тогда можно утверждать о внутренней противоречивости предложенной информации.
При решении задач в рамках алгебраического подхода встаёт вопрос о выборе пространства возможных оценок, когда заданы универсальные ограничения, это пространство должно иметь структуру, которая позволяет сохранять информацию, выраженную этими ограничениями.
В данном параграфе будут рассмотрены понятия регулярности и полноты задач преобразования информации в соответствии с теорией члена-корреспондента РАН К.В. Рудакова [62, 63, 64].
Проблема разрешимости является важнейшим теоретическим вопросом для задач синтеза корректных алгоритмов классификации, удовлетворяющих одновременно системам универсальных и локальных ограничений.
Пусть имеется разбиение множества 3 изучаемых задач с общей системой универсальных ограничений на классы эквивалентности по некоторому отношению «»»: Z\ «Z2 если задачи Z\ и Z неразличимы в момент выбора и анализа модели алгоритмов. Задача Z из множества 3 называется регулярной, если она разрешима и разрешимы все задачи из класса эквивалентности по отношению ««», в который она входит. Задача Z из множества 3 называется полной относительно семейства Ш отображений из 3t в Зу, если в 9Л содержатся допустимые отображения для всех задач из класса эквивалентности, содержащего Z; задача Z называется регулярной, если для нее существует семейство отображений ЯЯ, относительно которого она полна. Основной объект исследования при алгебраическом подходе — регулярные задачи и методы их решения. Пусть зафиксирован класс задач 3 и эквивалентность, определяющая регулярность, выделенный из 3 подкласс регулярных задач, будет обозначаться специальным символом Зш Наличие такого подкласса позволяет определить понятие полной модели алгоритмов: модель алгоритмов, удовлетворяющих универсальным ограничениям класса задач 3, называется полной, если в ней для каждой регулярной задачи из Згя] содержится корректный алгоритм. Поскольку классы задач, структурные ограничения и эквивалентности, определяющие понятия регулярности, отражают фактическую информацию, можно сказать, что понятие полноты определяет естественное экстремальное свойство моделей алгоритмов, поэтому один из центральных вопросов алгебраического подхода — изучение условий, обеспечивающих полноту. Так как подклассы регулярных задач обычно меньше классов разрешимых задач, то требование полноты является более мягким, чем требование разрешимости для всех в принципе разрешимых задач, поэтому синтез полных моделей алгоритмов - как правило, более реальная на практике задача, нежели построение моделей для решения всех разрешимых задач.
Для задач классификации, постановка которых включает в себя матрицу информации / и информационную матрицу /, эквивалентность, определяющая понятия регулярности и полноты, задается обычно следующим образом [63]. Рассматривается класс задач одной размерности с общими для всех задач пространствами допустимых начальных и финальных информации и с фиксированной системой универсальных ограничений. Задачи Z\ и Z2 из такого класса считаются эквивалентными, если совпадают их матрицы информации. Таким образом класс эквивалентности, содержащий задачу Z, возникает при произвольном варьировании информационной матрицы этой задачи. Таким образом, соотношение систем универсальных ограничений и матриц информации полностью определяет свойство регулярности задач классификации. При этом понятие полноты, производное от регулярности, связанно со своеобразной сюръективностью: образ матрицы информации при отображении всеми алгоритмами из полной модели должен совпадать со всем пространством информационных матриц.
Элементы теории универсальных и локальных ограничений
Нами рассматривается задача синтеза корректного алгоритма для разметки произвольных конфигураций. Для неё разработана сплит модель, позволяющая практически решать задачу выделения трендов.
Первое параметрическое семейство алгоритмов А является однопараметрическим с параметром S, в результате его работы формируется новая конфигурация, полученная «вычёркиванием» некоторых точек исходной, это можно представить в виде ломаной с вершиной в некоторых точках конфигурации. Семейство устроено следующим образом: 1) фиксируется стартовая точка с индексом i = l, она же отмечается как первая вершина ломаной; 2) задаётся к (начальное значение равно 2), через точки конфигурации с индексами і и і + к проводится прямая /; 3) вычисляются расстояния d., где i j i + k, от точек с индексами j до прямой /; 4) если все d . 8, то к увеличивается на единицу и осуществляется переход к пункту 2, если в конфигурации остались нерассмотренные точки; 5) если хотя бы одно d . 8, то новой стартовой точкой становится точка с индексом і + к -1, она теперь рассматривается как точка с индексом і, она же отмечается как очередная вершина ломаной, к присваивается его начальное значение и осуществляется переход к пункту 2, если в конфигурации остались нерассмотренные точки; 6) последняя точка конфигурации отмечается как очередная вершина ломаной; 7) точки конфигурации, которые являются вершинами ломаной, размечаются в соответствии с их взаимным расположением, то есть, если (v , V.)A(V. , v.), то точка с индексом размечается как «min», если (v. V.)A(V. V.), TO точка с индексом і размечается как «max», всем остальным точкам присваивается метка «поп».
Второе параметрическое семейство Aw имеет несколько параметров: й),сг,v ,...,v ,г 1, в рассматриваемом ниже случае г = 3 (по количеству меток в словаре разметки). Данное семейство устроено следующим образом: 1) для каждой точки конфигурации формируется вектор гп. размерности со, который будет заполняться значениями в процессе работы алгоритма; 2) фиксируется со первых идущих подряд точек конфигурации; 3) среди зафиксированных точек проводится поиск минимума и максимума; 4) для найденных минимума и максимума в соответствующие векторы m. добавляются метки «min» и «max», для остальных точек в векторы m. добавляются метки «поп»; 5) происходит смещение «окна» выделенных точек на а точек вправо, если в конфигурации ещё остались нерассмотренные точки, таким образом, фиксируются очередные со точек, осуществляется переход к пункту 3; 6) после того, как все точки конфигурации рассмотрены, и векторы Тії. заполнены значениями меток, производится вычисление значений координат векторов w. размерности 3 (по количеству меток в словаре разметки), которые сформированы для каждой точки конфигурации, по следующей схеме: первая координата — это произведение v и количества меток «min» в соответствующем по индексу векторе т., вторая — произведение v и количества меток «max» и так далее. 7) в каждом векторе w. производится поиск максимального значения координаты и в соответствии с этим каждой точке конфигурации присваивается метка, т.е. если наибольшее значение имеет первая координата вектора w., то соответствующая точка размечается как «min», если наибольшее значение имеет вторая координата, то соответствующая точка размечается как «max» и так далее.
На основании вышеизложенного материала разработана компьютерная программа. В качестве входных данных используются наборы прецедентов, то есть КПК и разметки этих конфигураций экспертом, выходными данными является разметка алгоритма и некоторая статистическая информация. Схему работы этой программы можно описать так: 1) проверка соответствия разметки эксперта системе аксиом разметки П, в случае соответствия переход к пункту 2, иначе полученные данные нельзя считать корректными; 2) построение первого базового алгоритма посредством оптимизационной настройки параметрического семейства А1; 3) построение вектора, содержащего ошибки первого базового алгоритма, то есть отражающего несоответствия разметки алгоритма разметке эксперта; 4) вычисление функционала качества первого базового алгоритма; 5) построение второго базового алгоритма посредством оптимизационной настройки параметрического семейства
А при этом учитываются ошибки, которые допустил первый базовый алгоритм: если алгоритм из семейства Aw размечает точку так же, как первый базовый алгоритм, и это соответствует разметке эксперта, то значение функционала качества увеличивается на 0,1, если второй базовый алгоритм размечает точку так же как эксперт, а первый алгоритм на этой точке ошибся, то значение функционала качества увеличивается на единицу; 6) построение третьего результирующего алгоритма посредством применения алгебраической коррекции к первым двум базовым алгоритмам: W = a-W +(\-d)-W , где а -параметр, изменяющийся от нуля до единицы (начальное значение равно 0,05, шаг изменения параметра составляет 0,05), W - матрицы, содержащие по столбцам векторы w. для первого и второго базовых алгоритмов, причём матрица W формируется аналогично матрице W той разницей, что соответствующие по номерам меток координаты содержат не произведение параметра на количество меток, а значение 0,3 (экспериментально определённая константа); 7) вычисление номера максимальной координаты по каждому столбцу матрицы W (столбцы матрицы соответствуют точкам конфигурации), в соответствии с найденными значениями принимается решение о разметке каждой точки конфигурации аналогично пункту 7 описания параметрического семейства А .
Задачи синтеза обучаемых алгоритмов выделения трендов являются частным случаем задач с теоретико-множественными ограничениями, в роли которых выступают аксиомы разметки. Опираясь на теорию, разработанную К.В. Рудаковым и Ю.В. Чеховичем [71], приведём требования к семействам алгоритмов, выполнение которых обеспечивало бы полноту этих семейств.
Описание параметрических семейств алгоритмических операторов для решения задач выделения трендов
Алгебраический подход к распознаванию образов представляет собой математическую технологию построения проблемно-ориентированных теорий синтеза корректных алгоритмов распознавания образов на базе параметрических семейств операторов.
В русле этого подхода в настоящее время эффективно решаются задачи и классы задач преобразования информации. Проведённое нами исследование задач синтеза обучаемых алгоритмов выделения трендов позволило построить эффективные в рамках рассматриваемого класса задач семейства алгоритмических операторов, решающих правил и корректирующих операций и разработать соответствующее программное обеспечение.
В первой главе описаны основные конструкции алгебраического подхода к задачам распознавания и классификации. В контексте алгебраического подхода к синтезу корректных алгоритмов преобразования информации рассмотрен класс задач, , характеризующийся наличием теоретико-множественных ограничений на множество допустимых ответов алгоритма, изложены элементы теории универсальных и локальных ограничений для алгоритмов распознавания и классификации.
Проблема разрешимости является важнейшим теоретическим вопросом для задач синтеза корректных алгоритмов классификации, удовлетворяющих одновременно системам универсальных и локальных ограничений, в связи с этим в первой главе также рассмотрены понятия регулярности и полноты задач преобразования информации в соответствии с теорией члена-корреспондента РАН К.В. Рудакова.
Постановка и формализация класса задач выделения трендов, а также описание практических методов решения задач этого класса представлено во второй главе настоящего исследования.
Построены параметрические семейства алгоритмических операторов для решения задач выделения трендов, разработана сплит-модель, позволяющая практически решать задачу выделения трендов.
Разработана программа для синтеза обучаемых алгоритмов выделения трендов временных рядов на основе предложенной модели, описан принцип её работы. Изложены требования к семействам алгоритмов, выполнение которых обеспечивает их полноту.
В третьей главе описаны серии проведённых экспериментов с использованием разработанной программы, на схемах подробно представлены принципы её работы. Сделаны выводы о результатах экспериментов. Таким образом, впервые для анализа моделей алгоритмов была использована теория задач с теоретико-множественными ограничениями.
Данное исследование развивает и дополняет алгебраическую теорию синтеза обучаемых алгоритмов вьвделения трендов временных рядов.
Результаты работы могут быть использованы в дальнейших научных исследованиях, посвященных проблеме выделения трендов временных рядов, а также в таких практических сферах, как экономика, астрономия, медицинская диагностика, геологический анализ. На Рис. 2 изображена разметка того же участка алгоритмом из семейства А , параметр S настроен так, что все точки участка размечены как неэкстремальные, хотя это отражает общую тенденцию разметки эксперта, но не учитывает тот факт, что эксперт всё же выделил два минимума и два максимума, таким образом, этот алгоритм ошибся на четырёх точках. Рис. 3. На Рис. 3 показана разметка рассматриваемого участка пятой КПК алгоритмом из семейства Aw. Как видно, такая разметка ближе к разметке эксперта, чем на Рис. 2, в смысле вьщеления минимумов и максимумов, но в ней присутствуют три минимума (во второй части КПК), которые эксперт не выделял. Рис. 4. На Рис. 4 изображена разметка, получившаяся в результате применения алгебраической коррекции к двум алгоритмам из A AW параметрических семейств Аил, параметр а настроен так, что в этой разметке сохранились первые два минимума и первые два максимума, выделенные вторым алгоритмом, а последние три минимума получили разметку в соответствии с первым алгоритмом, что полностью совпадает с разметкой эксперта с точностью до неразмеченных им точек ЮЖ. Полученные результаты показывают возможность построения эффективной системы параметрических семейств алгоритмов и их алгебраической коррекции, которая повышает качество работы этих семейств. Заключение
О работе экспериментальной программы
Перейдём к непосредственному описанию серии проведённых экспериментов. Рассмотрим результаты работы нашей программы на пяти различных ЮЖ. Данные для конфигураций - курсы валют, опубликованные Центробанком РФ. Далее во всех случаях под верной разметкой точки конфигурации алгоритмом подразумевается, что алгоритм разметил точку так же, как эксперт. В том случае, если эксперт не разметил точку конфигурации, то любая её разметка алгоритмом считается верной, если она удовлетворяет аксиомам разметки. Первая КПК: =0,03289; со =5; а = 1; v = 0,2; v2=0,l; v3 =0,5. Первый базовый алгоритм верно разметил 84 из 96 точек КПК, функционал качества второго алгоритма, рассмотренный в пункте 5 описания параметрического семейства Aw, равен 18,8, результат работы третьего результирующего алгоритма 89 из 96 верно размеченных точек, а =0,05. Улучшение качества работы алгебраической композиции алгоритмов относительно первого базового здесь составляет 5,21%. Вторая КПК: =0,06927; а=3; а = 1; у = 0,2; v =0,1; v =0,1. Первый базовый алгоритм верно разметил 270 из 285 точек КПК, функционал качества второго алгоритма, рассмотренный в пункте 5 описания параметрического семейства Aw, равен 26,5, результат работы третьего результирующего алгоритма 273 из 285 верно размеченных точек, а =0,55. Улучшение качества работы алгебраической композиции алгоритмов относительно первого базового здесь составляет 1,05%. Третья КПК: д = 0,34436; со=1\ (7 = 1; v =0,3; 2=0,3; v =0,2. Первый базовый алгоритм верно разметил 78 из 87 точек КПК, функционал качества второго алгоритма, рассмотренный в пункте 5 описания параметрического семейства Aw, равен 14,6, результат работы третьего результирующего алгоритма 83 из 87 верно размеченных точек, я: =0,05. Улучшение качества работы алгебраической композиции алгоритмов относительно первого базового здесь составляет 5,74%. Четвёртая КПК: = 0,21435; (0=1; т = 1; v = 0,2; v =0,1; v3 =0,9. Первый базовый алгоритм верно разметил 91 из 98 точек КПК, функционал качества второго алгоритма, рассмотренный в пункте 5 описания параметрического семейства Aw, равен 14,9, результат работы третьего результирующего алгоритма 95 из 98 верно размеченных точек, а =0,05. Улучшение качества работы алгебраической композиции алгоритмов относительно первого базового здесь составляет 4,08%. Пятая КПК: 8 = 0,62178; со =9; сг = 1; v = 0,7; v =0,2; v =0,3. Первый базовый алгоритм верно разметил 406 из 434 точек КПК, функционал качества второго алгоритма, рассмотренный в пункте 5 описания параметрического семейства Aw, равен 51, результат работы третьего результирующего алгоритма 415 из 434 верно размеченных точек, or =0,85. Улучшение качества работы алгебраической композиции алгоритмов относительно первого базового здесь составляет 2,07%. Далее рассмотрим результаты экспериментов, полученные на наборах прецедентов, каждый из которых состоит из двух КПК. Первый набор: 6 =0,23571; со = 6; сг = 1; v =0,3; v2 =0,2; v3 =0,2. Первый базовый алгоритм верно разметил 159 из 183 точек набора, функционал качества второго алгоритма, рассмотренный в пункте 5 описания параметрического семейства Aw, равен 30,5, результат работы третьего результирующего алгоритма 175 из 183 верно размеченных точек, а =0,35. Улучшение качества работы алгебраической композиции алгоритмов относительно первого базового здесь составляет 8,74%.
Второй набор: 8 =0,09224; w=S; cr = l; v = 0,5; v2 =0,3; v3 =0,4. Первый базовый алгоритм верно разметил 652 из 719 точек набора, функционал качества второго алгоритма, рассмотренный в пункте 5 описания параметрического семейства Aw, равен 89,8, результат работы третьего результирующего алгоритма 702 из 719 верно размеченных точек, а =0,15. Улучшение качества работы алгебраической композиции алгоритмов относительно первого базового здесь составляет 6,95%. Третий набор: =0,37102; со =5; т = 1; у =0,3; v2 =0,1; v3 =0,2. Первый базовый алгоритм верно разметил 168 из 185 точек набора, функционал качества второго алгоритма, рассмотренный в пункте 5 описания параметрического семейства Aw, равен 30,8, результат работы третьего результирующего алгоритма 179 из 185 верно размеченных точек, «=0,05. Улучшение качества работы алгебраической композиции алгоритмов относительно первого базового здесь составляет 5,95%. Четвёртый набор: =0,135; а=1; сг = 1; v = 0,5; v2 =0,2; v3 =0,1. Первый базовый алгоритм верно разметил 359 из 381 точек набора, функционал качества второго алгоритма, рассмотренный в пункте 5 описания параметрического семейства Aw, равен 54,4, результат работы третьего результирующего алгоритма 373 из 381 верно размеченных точек, а =0,55. Улучшение качества работы алгебраической композиции алгоритмов относительно первого базового здесь составляет 3,67%. Пятый набор: = 0,5189; й =8; у = 1; v =0,3; v2 =0,1; v3 =0,3. Первый базовый алгоритм верно разметил 489 из 521 точек набора, функционал качества второго алгоритма, рассмотренный в пункте 5 описания параметрического семейства Aw, равен 65,1, результат работы третьего результирующего алгоритма 513 из 521 верно размеченных точек, «=0,05. Улучшение качества работы алгебраической композиции алгоритмов относительно первого базового здесь составляет 4,61%. Далее рассмотрим результаты экспериментов, полученные на наборах прецедентов, каждый из которых состоит из трёх КПК. Первый набор: 8 =0,32412; у=8; т = 1; v = 0,2; v2 =0,5; v3 =0,7. Первый базовый алгоритм верно разметил 579 из 628 точек набора, функционал качества второго алгоритма, рассмотренный в пункте 5 описания параметрического семейства Aw, равен 78,5, результат работы третьего результирующего алгоритма 611 из 628 верно размеченных точек, а =0,05. Улучшение качества работы алгебраической композиции алгоритмов относительно первого базового здесь составляет 5,1%. Второй набор: 5 =0,15863; 0=8; сг = 1; v =0,3; v2=0,2; v3 =0,1. Первый базовый алгоритм верно разметил 441 из 479 точек набора, функционал качества второго алгоритма, рассмотренный в пункте 5 описания параметрического семейства Aw, равен 59,9, результат работы третьего результирующего алгоритма 463 из 479 верно размеченных точек, а =0,05. Улучшение качества работы алгебраической композиции алгоритмов относительно первого базового здесь составляет 4,6%. Третий набор: = 0,55742; со =9; 7 = 1; v = 0,2; v2 =0,4; v3 =0,5. Первый базовый алгоритм верно разметил 753 из 806 точек набора, функционал качества второго алгоритма, рассмотренный в пункте 5 описания параметрического семейства Aw, равен 74,6, результат работы третьего результирующего алгоритма 798 из 806 верно размеченных точек, а =0,75. Улучшение качества работы алгебраической композиции алгоритмов относительно первого базового здесь составляет 5,58%. Четвёртый набор: = 0,61271; а=%; сг = 1; v =0,1; v2 =0,3; v3 =0,2. Первый базовый алгоритм верно разметил 574 из 619 точек набора, функционал качества второго алгоритма, рассмотренный в пункте 5 описания параметрического семейства Aw, равен 68,7, результат работы третьего результирующего алгоритма 603 из 619 верно размеченных точек, а =0,05. Улучшение качества работы алгебраической композиции алгоритмов относительно первого базового здесь составляет 4,68%. Пятый набор: = 0,38701; а =9; сг = 1; у = 0,4; v2 =0,2; v3 = 3. Первый базовый алгоритм верно разметил 763 из 817 точек набора, функционал качества второго алгоритма, рассмотренный в пункте 5 описания параметрического семейства Aw, равен 90,7, результат работы третьего результирующего алгоритма 796 из 817 верно размеченных точек, а =0,25. Улучшение качества работы алгебраической композиции алгоритмов относительно первого базового здесь составляет 4,04%. Проведённые эксперименты показывают, что улучшение качества работы алгебраической композиции относительно первого базового алгоритма (отметим, что аналогичное улучшение наблюдается и относительно второго базового алгоритма) не зависит от размера КПК или их набора, а также от характера действий эксперта при их разметке (при условии, что разметка корректна с точки зрения используемых аксиом). Это позволяет говорить о получении стабильных результатов в контексте задачи синтеза обучаемых алгоритмов выделения трендов временных рядов.
