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

Московский Государственный Университет имени М.В. Ломоносова Факультет Вычислительной Математики и Кибернетики

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

Коваленко Дмитрий Сергеевич

МЕТОДЫ И ПРОГРАММНЫЕ СРЕДСТВА ОБУЧЕНИЯ АЛГОРИТМОВ РАСПОЗНАВАНИЯ УЧАСТКОВ ФАЗОВЫХ ТРАЕКТОРИЙ

Специальность 05.13.11 — математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва

2011 2 /, ^

4856162

Работа выполнена на кафедре Автоматизации Систем Вычислительных Комплексов факультета Вычислительной Математики и Кибернетики Московского Государственного Университета имени М.В. Ломоносова.

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

старший научный сотрудник Костснко Валерий Алексеевич

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

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

кандидат физико-математических паук, старший научный сотрудник Литинский Леонид Борисович

Ведущая организация: ОАО «НИИ ВК им. М.А. Карцева»

Защита состоится «4» марта 2011 г. в 11:00 на заседании диссертационного совета Д 501.001.44 при Московском Государственном Университете имени М.В. Ломоносова по адресу: 119991, ГСП-1, Москва, Ленинские горы, МГУ, 2-ой учебный корпус, факультет Вычислительной Математики и Кибернетики, аудитория 085.

С диссертацией можно ознакомиться в библиотеке факультета ВМиК МГУ имени

М.В. Ломоносова, с текстом автореферата..... на официальном сайте ВМиК МГУ имени

М.В. Ломоносова: http://uww.cs.msu.su в разделе «Наука» — «Работа диссертационных советов» - «Д 501.001.44».

Автореферат разослан «2» февраля 2011 г.

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

диссертационного совета Д 501.001.44

профессор Н.П. Трифонов

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

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

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

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

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

1 Последовательности действий или событий, происходящих в рассматриваемой системе и приводящих ее в состояние, а котором она не выполняет своих функций.

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

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

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

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

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

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

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

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

Основные результаты работы. Результаты диссертационной работы заключаются в следующем:

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

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

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

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

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

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

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

состояния.

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

Апробация работы. Результаты, представленные в работе, докладывались па научном семинаре Лаборатории Вычислительных Комплексов кафедры АСВК факультета ВМиК МГУ имени М.В. Ломоносова под руководством профессора Р.Л. Смелянского; на семинаре кафедры АСВК под руководством заведующего кафедрой члеи-корр. РАН Л.Н. Королева; а также па следующих конференциях:

• II Всероссийская научная конференция «Методы и средства обработки информации», Москва, 2005;

• VII Международная конференция «Дискретные модели в теории управляющих систем», Москва, 2006;

• VI Международная конференция «Интеллектуализация обработки информации», Алушта, Украина, 2006;

• V Международная конференция по исследованию операций «ORM», Москва, 2007;

• VII Международная конференция «Интеллектуализация обработки информации», Алушта, Украина, 2008;

• XI Всероссийская конференция «Нейроинформатика», Москва, 2009;

• III Всероссийская научная конференция «Методы и средства обработки информации», Москва, 2009;

• V Международная конференция «IEEE BIC-ТА», Чанша, Китай, 2010.

Публикации. По теме диссертации опубликовано 8 печатных работ, в

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

Структура и объем диссертации. Диссертация состоит из введения, шести глав, заключения, списка литературы и трех приложений. Объём работы — 146 страниц, объём приложений составляет 22 страницы. Список литературы содержит 62 наименования.

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

Во введении обоснована актуальность диссертационной работы и сформулирована цель исследований.

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

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

1. Штатное состояние, при котором система стабильно выполняет заложенные в нее функции.

2. Нештатное состояние, при котором система в скором времени гарантированно перестанет выполнять заложенные в нее функции.

3. Аварийное состояние, при котором система не выполняет заложенных в нее функций.

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

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

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

• Набор классов нештатного поведения системы, для каждого из которых задана эталонная траектория Х1Апот.

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

• Ограничения на полноту и точность распознавания:

ех < сх и е2 < с2 (1)

где: е\, е2 — число ошибок распознавания I и II рода соответственно; с\, с2 — заданные числовые ограничения.

• Ограничение на время работы алгоритма распознавания:

Ъацх) < сз (2)

где: Ьщх) - время работы алгоритма распознавания А1 над траекторией X; сз - заданное ограничение, которое определяется в зависимости от скорости развития процессов в наблюдаемой системе. Требуется провести распознавание нештатного поведения в работе наблюдаемой системы с учетом ограничений на время работы, полноту и точность распознавания.

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

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

Пусть определена целевая функция </?(еь ег), где е\ и е^ — число ошибок распознавания I и II рода, которая отвечает следующим требованиям:

• Функция 1р(в1,е2) определена для любых неотрицательных целых значений аргументов е\ и е?.

• Функция (р(ег,е2) монотонно не убывает по каждому из аргументов. Задача обучения алгоритмов распознавания формулируется в виде

задачи обучения по прецедентам. Дано:

• Обучающая выборка ТБ и контрольная выборка ТБ,

• Целевая функция </?(е1, ег).

Требуется построить алгоритм распознавания А1, который будет

удовлетворять следующему набору ограничений:

8

1. Алгоритм А1 должен выдавать ограниченное число ошибок на обучающей выборке ТБ\

е1(А1, Т5) < Р1„ е2(А1, ТБ) < Р^ (3)

где: Ротона 11 Ригопд ~ заданные числовые ограничения.

2. Алгоритм А1 должен минимизировать значение целевой функции <р(е 1,ег) на контрольной выборке Г5:

А1 = агд тт(<р(е\(А1,ТЗ), Г5))) (4)

А1

3. Вычислительная сложность работы алгоритма распознавания 0д;(т) над любой фазовой траекторией, длины не больше ш, должна быть ограничена наперед заданной функцией 9(тп), которая определяется характеристиками используемого вычислителя и скоростью развития процессов в анализируемой системе:

вА,(т) < в(т) (5)

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

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

• Алгоритмы на основе искусственных нейронных сетей.

• Алгоритмы, основанные на преобразованиях Фурье и вейвлетах.

• Алгоритм "Гусеница," - Singular Spectrum Analysis (SSА).

• Алгоритмы на основе Dynamic Time Warping (DTW).

• Алгоритмы распознавания на основе идей алгебраического подхода. Целью исследования методов является сравнение качества их работы в условиях, когда участки наблюдаемой траектории, соответствующие нештатному поведению, искажены относительно эталонных траекторий. Для сравнения методов выбраны следующие критерии: а) Количество ошибок распознавания I рода, b) Количество ошибок распознавания II рода, с) Вычислительная сложность работы алгоритма распознавания.

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

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

Ключевым элементом алгоритмов распознавания, основанных на идеях алгебраического подхода, является разметка фазовой траектории условиями. Эти условия называются аксиомами2. Точка траектории размечается аксиомой, если для данной точки условия аксиомы выполняются. Аксиома

2 Простейшими примерами аксиом являются: условие локального max (или min) значения разыечамои точки фазоггой траектории, условия возрастания и убывания.

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

Существующие алгоритмы обучения распознавателей на основе данного подхода обладают рядом недостатков: а) высокая вычислительная сложность алгоритмов обучения; Ъ) необходимость участия эксперта при построении системы аксиом; с) невысокая устойчивость алгоритмов распознавания к наложению шумов; d) необходимость повышения точности работы получаемых в результате обучения алгоритмов распознавания в ряде случаев; е) отсутствие алгоритмов обучения в случае, когда для траекторий выборки TS указаны точки аварий.

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

В третьей главе описано разработанное параметрическое семейство алгоритмов распознавания и условия его обучаемости. Определение 1. Элементарное условие ее — ec{x*t,t,P) — это функция, определенная на отчете t и некоторой его окрестности х\ на траектории X, зависящая от набора параметров Р, которая принимает значения из множества {true, false}.

Определение 2. Аксиома а = a{x\,t) — это булева функция, заданная в виде формулы от элементарных условий, определенных на отсчете t и некоторой его окрестности x*t на траектории X:

а(х;,1) = У/\ есуф.^У«

а |

(6)

г 3

где:

ес{х1^,Р), при ¡5=1

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

т.е. для любой точки произвольной фазовой траектории X найдется и притом только одна аксиома а^ из множества ав, условия которой выполняются в данной точке.

Далее будем считать, что аксиомы в системе аксиом ав пронумерованы последовательными натуральными числами: ав = {а^ а2,..., ад/}-

Любое множество аксиом возможно представить в виде системы аксиом выполнив следующее:

1. Введение порядка на множестве аксиом. Будем считать что, если аксиома с индексом г выполняется в некоторой точке произвольной фазовой траектории, то никакая аксиома с индексом 3 : у > г не выполняется в данной точке траектории.

2. Добавление тождественной аксиомы а«, с наименьшим приоритетом:

Тождественная аксиома аж — это аксиома, которая выполняется в любой точке любой фазовой траектории.

Определение 4. Разметкой траектории X = (х\,х2, ..,хп) относительно системы аксиом ав будем называть последовательность 3 = (]\,32т-^п), где ^ - индекс аксиомы в системе аксиом ав, условия которой выполняются на отсчете í траектории X.

МХ 4x1 6 X 3! а* € ав : аДх^, ¿) = Ьгие

ав = {а1,а2, • • • , ам,^}

Алгоритм, который сопоставляет траектории X ее разметку относительно заданной системы аксиом, будем называть алгоритмом разметки и обозначать: Л.

Параметрическое семейство алгоритмов распознавания 51 — это множество таких алгоритмов А1, каждый из которых включает: а) алгоритм предобработки траекторий к(Х, Р/,), где: Р/, — параметры алгоритма Л; Ь) алгоритм разметки Л и система аксиом ав; с) алгоритм поиска разметок эталонных траекторий {Злпот} в разметке J наблюдаемой фазовой траектории <?(</, {./¿пот}* Рд)> гДе: Рд ~ параметры алгоритма д.

Под алгоритмом предобработки /г(Х, Рд) будем понимать алгоритм, который реализует функцию преобразования траекторий, ставящую произвольной фазовой траектории в однозначное соответствие некоторую траекторию: И(Х, Р/,,) : X —> X , где: X — исходная фазовая траектория; X — траектория, полученная из X в результате преобразования. Примерами алгоритмов предобработки являются: алгоритм сглаживания траекторий, алгоритм сжатия или растяжения траектории на заданный коэффициент.

Каждый алгоритм распознавания А1 £ 5 работает следующим образом. При помощи алгоритма к(Х, Рд) происходит предобработка эталонных траекторий {Хапош} и анализируемой фазовой траектории X. Затем, при помощи алгоритма Л формируются разметки эталонных траекторий {«/¿„от} и разметка анализируемой траектории 3 относительно системы аксиом аэ. После этого, происходит поиск разметок {7лпот} в разметке 3, на основании результатов которого производится вывод о том, к какому классу относится поведение анализируемой системы на каждом отсчете траектории X.

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

В разделе 3.2 приведены условия обучаемости параметрического семейства алгоритмов распознавания S.

Определение 5. Пусть даны две траектории X и Y, len(X) < len(Y), и множество элементарных условий {ее}. Будем говорить, что траектории X uY различимы в элементарных условиях из множества {ее}, если: Vr е [1, len{Y) - len(X) + 1] 31 е [1,1еп{Х)), 3eck е {ее} , 3РеСк : eck{Yr+t, r + t, РесJ ф eck(Xu t, PecJ

fee}

Различимость траекторий X uY будем обозначать: X Y.

Необходимое условие обучаемости семейства S для заданной выборки TS сформулировано в виде следующей теоремы.

Теорема 1. Для того, чтобы в параметрическом семействе алгоритмов распознавания S существовал алгоритм Al € S, решающий с наперед заданной точностью3 основную задачу распознавания нештатного поведения для произвольной наблюдаемой траектории X необходимо, чтобы любые два участка нештатного поведения из выборки TS, соответствующие различным классам нештатного поведения, были различимы в элементарных условиях из множества {ее}:

V Y\nmn, Y{nmn € TS, w* ф wi : У|потп yjnom (8)

где: {ее} — множество всех используемых в S элементарных условий; w' — класс нештатного поведения участка Y\nmn из выборки TS.

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

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

3 Под томностью понимаются ограничения на число ошибок распознавания I и II рода.

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

В разделе 4-1 описана общая схема разработанного алгоритма обучения:

1. Разбиение всего параметрического семейства алгоритмов распознавания 5 на подсемейства: 5 = {5ь ¿г,..., 5лг}- При этом, в каждом подсемействе определен только один тип алгоритма предобработки и тип алгоритма поиска разметок.

2. Для каждого подсемейства Бк строится алгоритм распознавания:

а. Построение системы аксиом ав.

б. Определение значений Рд для алгоритма поиска разметок д.

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

г. Проверка критерия останова и переход на шаг 3, в случае его выполнения, иначе переход на шаг 2а.

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

Рассмотрим шаги данного алгоритма. Для описания способа разбиения семейства алгоритмов 5 на подсемейства на шаге 1 введем определение. Определение 6. Под шаблоном алгоритма распознавания из параметрического семейства 5 будем понимать следующую тройку элементов (Н^р''\{ес}, д^):

• заданный алгоритм предобработки Н и диапазон допустимых изменений значений его параметров {Рн};

• фиксированное множество элементарных условий {ее} и диапазон допустимых изменений значений параметров каждого из них;

• заданный алгоритм поиска разметок д и диапазон допустимых изменений значений его параметров {Рэ}.

Шаблон {ес},д{Рд^) определяет подсемейство алгоритмов

распознавания в семействе 5. Выделение подсемейств происходит путем разделения 5 на шаблоны. Для каждой пары: тип алгоритма предобработки

^ и тип алгоритма поиска разметок д^ - создается шаблон Б к — (Ы, {ее}, д Множество элементарных условий {ее} в каждом шаблоне совпадает с множеством всех элементарных условий {ее}, определенных в Б. Диапазоны изменения значений параметров условий не ограничиваются. Если число шаблонов необходимо увеличить, то создается заданное число шаблонов с одинаковыми типами алгоритмов предобработки и поиска разметок, при этом разграничивается область изменения их параметров.

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

На шаге 2а алгоритма обучения происходит построение системы аксиом. Для случая задания выборки ТБ с указанием участков нештатного поведения был разработан генетический алгоритм, который описан в разделе 1^.2. Для случая задания выборки ТБ с указанием точек аварий был разработан алгоритм, основанный на схеме ограниченного перебора. Его описание приведено в разделе 4-3.

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

Критериями останова итерационного алгоритма поиска решения в рамках шаблона на шаге 2г алгоритма обучения являются: а) выполнены условия задачи обучения алгоритма распознавания; Ь) общее число итераций алгоритма превысило заданный параметр; с) число итераций без улучшения значения целевой функции <р(е\,е2) превысило заданный параметр.

Выбор лучшего из построенных алгоритмов распознавания на последнем шаге алгоритма происходит по значению целевой функции (^(е^ег) па контрольной выборке Т5.

В разделе 4-2 рассматривается алгоритм построения системы аксиом ав по выборке ТБ с указанием участков нештатного поведения. Для построения системы аксиом был разработан алгоритм, основанный на схеме генетического алгоритма. Особыо в популяции является система аксиом.

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

Для учета этой особенности были разработаны функции значимости (для систем аксиом, аксиом и элементарных условий) и разработаны методы автоматического определения на каждой итерации генетического алгоритма значений параметров операций мутации и скрещивания в зависимости от значений этих функций. Функции значимости определяются в зависимости от значений целевой функции (/?(е1,е2) для системы аксиом и от частоты срабатывания элементарных условий и аксиом на траекториях обучающей выборки Т5. Автоматическое определение параметров операций мутации и скрещивания позволило улучшить точность и скорость сходимости генетического алгоритма по сравнению со случаем, когда параметры операций задаются вручную перед началом выполнения алгоритма.

В разделе 4-3 рассматривается алгоритм построения системы аксиом ав по выборке ТБ с указанием точек аварии. Перед применением алгоритма вся выборка ТБ преобразуется. Каждая траектория X € ТБ, содержащую точку аварии, разделяется на части: траектория нормального поведения X' и траектория X" длиной г отсчетов, содержащая участок нештатного поведения (г - параметр преобразования). Траектория X" представляет собой участок траектории X с отсчета (тах(1,1х — г-)) п0 отсчет (1х), где Iх — это точка аварии на траектории X. После преобразований выборка ТБ представляет собой набор траекторий: ТБ = {X'} и {X"}. Часть из них является траекториями нормального поведения {X'}, другая часть {X") - это набор таких траекторий, каждая из которых содержит участок нештатного поведения, однако не известно на каких именно отсчетах.

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

Алгоритм построения системы аксиом состоит в следующем: 1. Для каждого класса I е [1,Ь] нештатного поведения системы производится построение элементарных условий и аксиом, которые выполняются на участках нештатного поведения именно этого класса:

а. Из множества всех входящих в шаблон Бк элементарных условий {ее} путем перебора типов условий и значений их параметров выбираются те, которые чаще выполняются на траекториях, содержащих участки нештатного поведения класса I, и реже на траекториях нормального поведения из обучающей выборки ТБ.

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

выборки ТБ, поступают на вход следующему этапу алгоритма.

2. Формирование множества систем аксиом из построенных аксиом. Для каждой системы формируются разметки эталонных траекторий. Эти разметки получаются из выборки Т5 путем выделения наибольшей общей подпоследовательности разметок траекторий, содержащих участки нештатного поведения одного класса, относительно данной системы аксиом. Выбор лучшей системы ав осуществляется по значению целевой функции ф(е 1,62) на контрольной выборке Т£>.

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

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

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

2. Распараллеливание алгоритма обучения в рамках одного шаблона. Наиболее вычислительно-ёмкими операциями алгоритмов обучения в рамках одного шаблона являются операции вычисления целевых функций (для особей популяции в генетическом алгоритме; для элементарных условий, аксиом и систем аксиом в алгоритме построения системы аксиом по выборке с указанием точек аварии). Их выполнение выделяется в отдельные нити процессов, что позволяет задействовать все вычислительные ядра каждого из узлов.

В разделе 5.2 описаны составляющие созданной программной библиотеки АхютЫЬ. Для работы с библиотекой АхютЫЪ был создан графический пользовательский интерфейс (ГПИ), который так же описан в разделе 5.2. Все разработанные средства являются кросс-платформенными.

Раздел 5.3 посвящен исследованию эффективности предложенного алгоритма распараллеливания разработанных методов обучения. Для исследования эффективности предложенного алгоритма был проведен набор экспериментов на кластере, состоящем из шести 8МР-узлов, каждый узел которого содержал два 4-х ядерных процессора. В работе приведены подробные характеристики используемого вычислителя и описаны используемые наборы данных. В среднем ускорение времени работы алгоритма обучения на б узлах кластера по сравнению со временем работы на одном узле составило 5.64 раза. Загрузка вычислительных ядер системы при этом составляла 95% — 99%.

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

В разделе 6.1 приводится описание используемых наборов данных. В разделах 6.2-6.3 описаны полученные результаты исследований и проведено сравнение разработанных алгоритмов с существующими.

Результаты сравнения алгоритма распознавания, построенного при

помощи разработанного метода по обучающей выборке с указанием участков нештатного поведения, с другими алгоритмами, рассмотренными в главе 2, представлены в таблице 1. Результаты показаны для следующих характеристик искажений участков нештатного поведения относительно эталонных траекторий: искажения по времени до 40%, но амплитуде до 2.5%, амплитуда шума до 25% от амплитуды сигнала.

Таблица 1. Результаты работы алгоритмов распознавания на модельных данных.

Тип алгоритма распознавания Число ошибок I рода Процент ошибок II рода Сложность алгоритма распознавания

Нечеткое сопоставление строк 501 33%

Dynamic Time Warping (DTW) 175 31%

Нейросетевой подход 1453 20% 0(с? ■ М) где: с1 — число нейронов

Преобразования Фурье 323 35% О&ЛИс^-М)

Вейвлет-преобразоваиия 1136 32% -\ogNi - М)

"Гусеница'-SSA 741 21% 0(Еш •м)

Алгоритм на основе идей алгебраического подхода 146 6% +Кес(а5)) ■ М) где: Кес(аз) — число элем, условий в ав

Разработанный метод 76 2% Оцх) + Кес{аз) ■ М+ где: Оцх) — сложность алгоритма предобработки

Обозначения в таблице 1: М — длина анализируемой траектории X; М — длина траектории X, полученной из X в результате предобработки; Л^ — длина ХгАпот\ Ь — число классов нештатного поведения.

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

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

Для проведения исследований на реальных данных была рассмотрена задача прогнозирования периодов микросна водителя по показаниям датчиков электроэнцефалограммы (ЭЭГ). Данные представляют собой набор 4-мерных траекторий, отражающих показания датчиков ЭЭГ. Частота дискретизации — 100 Гц. Выделение участков нештатного поведения производилось экспертом на основе поведения испытуемых, движения их глаз, состояние зрачков и т.п. Для каждого испытуемого были получены траектории длиной 2 • 106 -2,5-106 отсчетов (что соответствует 6 — 7 часам наблюдения), число периодов микросна составляло от 12 до 26. Результаты применения разработанного метода: в среднем, процент ошибок II рода составил 5%, а число ложных срабатываний в среднем составило около 15.

В разделе 6.3 приведено исследование метода обучения алгоритмов распознавания по выборке с указанием только точек аварии. Исследования показали, что предложенный метод позволяет получать алгоритмы распознавания, устойчивые к искажениям участков нештатного поведения по амплитуде и времени относительно эталонных траекторий. При искажениях по времени до 20% и амплитуде до 20% и при амплитуде шума в 5% от амплитуды сигнала были получены следующие результаты: число I первого рода — 51, процент ошибок II рода — 8.5%. При искажениях по времени до 20% и амплитуде до 2.5% и при амплитуде шума в 15% от амплитуды сигнала получены следующие значения ошибок распознавания: 30 ошибок I рода (при длине анализируемой траектории в 30000 отсчетов) и 6% ошибок II рода.

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

как на модельных, так и на реальных данных. Была рассмотрена задача распознавания рукописных букв по показаниям трех датчиков: движение пера вдоль оси X, оси У и сила нажатия на перо (ось Z). Частота работы датчиков — 200 Гц. Использованный набор данных содержит 2858 трехмерных траекторий для символов латинского алфавита. Длина каждой траектории составляет от 109 до 205 отсчетов. Результаты применения разработанного метода оказались следующими: число корректно распознанных букв составило 95%, число ложных срабатываний - 58.

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Коваленко Д. С., Костенко В. А., Васин Е. А. Исследование применимости алгебраического подхода к анализу временных рядов. // Труды Второй Всероссийской научной конференции «Методы и средства обработки информации». Издательство факультета ВМиК МГУ, 2005. С. 553-559.

2. Коваленко Д. С., Костенко В. А., Васин Е. А. Генетический алгоритм построения системы аксиом для разметки временных рядов. // Труды VII Международной конференции «Дискретные модели в теории управляющих систем». М.: Макс Пресс, 2006. С. 46-54.

3. Коваленко Д. С., Костенко В. А., Васин Е. А. Автоматическое построение алгоритмов, основанных на алгебраическом подходе, для распознавания предаварийных ситуаций динамических систем. // Искусственный интеллект, № 2. Изд.: Крымский научный центр НАН Украины, Симферополь, 2006. С.130-133.

4. Коваленко Д. С. Методы нечеткого сравнения и голосования для построения распознавателей нештатного поведения динамических систем. // Труды V Московской международной конференции по исследованию операций «ORM-2007». Изд: МАКС Пресс, 2007. С.123-125.

5. Коваленко Д. С., Костенко В. А. Метод построения алгоритмов распознавания, основанных на идеях аксиоматического подхода. // Сборник научных трудов XI Всероссийской научно-технической конференции «Нейроинформатика-2009». Изд: МИФИ, 2009. С. 141-149.

6. Коваленко Д. С. Метод автоматического построения алгоритмов распознавания участков фазовых траекторий. // Моделирование и анализ информационных систем, Т. 16, №4, 2009. Изд.: ЯрГУ. С. 6-21.

7. Коваленко Д. С., Костенко В. А, Барыбии А. К., ТумакинД. А., Чельдиев М. И. Параллельный алгоритм обучения распознавателей нештатного поведения динамических систем. // Труды Третьей Всероссийской научной конференции «Методы и средства обработки информации». Изд.: МАКС Пресс, 2009. С. 362-373.

8. Kovalenko D., Kostenko V. A Genetic Algorithm for Construction of Recognizers of Anomalies in Behaviour of Dynamical Systems. // Proceedings of the IEEE Fifth International Conference on Bio-Inspired Computing: Theories and Applications, IEEE Press, China, 2010. P. 258-263.

Заказ № 89-а/01 /2011 Подписано в печать 24.01.2011 Тираж 100 экз. Усл. п.л. 1,2

ООО "Цифровичок", тел. (495) 649-83-30 I нпууу. с/г. ги ; е-таИ: щ[о(а)с/г. ги

Введение.

1. Цели и задачи работы.

2. Методы исследования

3. Актуальность работы.

4. Структура работы

Глава 1. Задача распознавания поведения системы.

1.1. Исследуемая система.

1.2. Задача распознавания поведения системы.

1.3. Ограничения на исходные данные

1.4. Задача обучения алгоритма распознавания.

1.5. Выводы.

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

2.1. Критерии сравнения алгоритмов и методика численного исследования

2.2. Алгоритм распознавания на основе нечеткого сопоставления строк

2.3. Алгоритм на основе

2.4. Алгоритм на основе искусственных нейронных сетей

2.5. Алгоритм на основе преобразований Фурье.

2.6. Алгоритм на основе вейвлет-преобразований.

2.7. Алгоритм на основе метода Тусеница'-ЗБА.

2.8. Алгоритм на основе идей алгебраического подхода.

2.9. Выводы.

Глава 3. Параметрическое семейство алгоритмов распознавания и условия его обучаемости.

3.1. Параметрическое семейство алгоритмов распознавания.

3.2. Условие обучаемости параметрического семейства решений.

Глава 4. Метод обучения алгоритмов распознавания нештатного поведения систем.

4.1. Общая схема метода обучения.

4.2. Генетический алгоритм построения системы аксиом по обучающей выборке с маркировкой участков нештатного поведения.

4.3. Алгоритм построения системы аксиом по обучающей выборке с маркировкой точек аварии.

Глава 5. Инструментальная система.

5.1. Требования к системе построения алгоритмов распознавания

5.2. Архитектура разработанного средства.

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

5.4. Выводы.

Глава 6. Исследование эффективности предложенных алгоритмов

6.1. Исходные данные.

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

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

6.4. Выводы.

В; данной; работе рассматривается задача разработки методов и программных средств-, обучения алгоритмов, распознавания нештатного поведения систем; информация, о которых доступна в- виде фазовых траекторий! Рассмотрим систему, информация* о состоянии которой получается с некоторого фиксированного набора датчиков. Время рассматривается дискретное, то есть датчики опрашиваются: с некоторой; фиксированной частотой.- Состояние системы характеризуется точкой в многомерном пространстве показаний, датчиков. Пусть, определены три класса состояний: штатное состояние, нештатное и аварийное состояние. Под; штатным (или нормальным) состоянием будем понимать такой режим работы системы,, при котором она выполняет свои: функции. Под нештатными состоянием будем понимать такой режим работы системы, при- котором; она гарантированно через; некоторое время, прекратит выполнять возложенные на нее функции. Под аварийным состоянием будем понимать. такой режим работы системы, при котором она* не выполняет возложенных на нее функций.

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

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

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

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

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

Рассмотрим пример: одним из нештатных состояний движущегося автомобиля можно считать такое, когда человек за рулем уснул или находится в состоянии микросна. При этом на водителе могут быть установлены датчики; которые измеряют его электроэнцефалограмму (ЭЭГ). Показания датчиков ЭЭГ водителя могут существенно отличаться в зависимости от времени суток, от состояния его здоровья, от эмоционального состояния и др. Для данной системы возникает задача распознавания, решение которой может предотвратить аварию. Задача заключается в определении того, когда человек из нормального состояния переходит к состоянию микросна.

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

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

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

Для решения задачи обучения по заданной выборке существует множество методов. Наиболее известные и широко применяемые из них исследованы в главе 2 данной работы, среди них: алгоритмы распознавания на основе искусственных нейронных сетей [18, 21], алгоритмы на основе Dynamic Time Warping (DTW) [40, 41], алгоритм "Гусеница" - Singular Spectrum Analysis (SSA) [10, 11] и др. Проведенное исследование показало, что большинство методов, применяемых для задач выявления нештатного поведения сложных систем, слабо справляются либо с нелинейными искажениями фазовой траектории по времени, либо с искажениями по амплитуде или наложением шума. Наилучшие результаты показали алгоритмы распознавания на основе идей алгебраического подхода [22].

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

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

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

• выдавать минимальное число ошибок распознавания на обучающей выборке;

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

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

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

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

1. Цели и задачи работы

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

Для достижения указанной цели необходимо решить следующие задачи:

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

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

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

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

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

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

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

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

Заключение

1. Айвазян С. А., Енюков И. С., Мешалкин JT. Д. Прикладная статистика. М.: Финансы и статистика. 1989.

2. Бахвалов Н. С., ЖидковЕ. П., Кобельков Г. М. Численные методы. 4-е издание. СПб.: ФизМатЛит, Невский диалект, 2003.

3. Березин И. С., Жидков Н. П. Методы вычислений. М.: ФизМатЛит, 1962.

4. Блейхут Р. Теория и практика кодов, контролирующих ошибки. М.: Мир, 1986.

5. Васильев А. П., Кудрявцев В. М., Кузнецов В. А. Основы теории и расчета жидкостных ракетных двигателей. М.: Высшая школа, 1983.

6. Воробьев В. И., Грибунин В. Г. Теория и практика вейвлет-преобразования. СПб.: Типография ВУС, 1999.

7. Воронцов К. В. Комбинаторный подход к оценке качества обучаемых алгоритмов. // Математические вопросы кибернетики. №13, 2004. С.5-36.

8. Глебов Н. И., Кочетов Ю. А., Плясунов А. В. Методы оптимизации. Изд.: НГУ, 2000.

9. Голяидина Н. Э., Некруткин В. В., Степанов Д. В. Варианты метода «Гусеницах-SSA для анализа многомерных временных рядов. // Труды II Международной конференции "Идентификация систем и задачи управления" SICPRO'03. Москва, 2003, С. 2139-2168.

10. Данилов Д. Л., Жиглявский А. А. Главные компоненты временных рядов: метод «Гусеница». СПб.: Санкт-Петербургский университет, 1997.

11. Васин Е. А. Операции мутации и скрещивания для генетического алгоритма построения систем аксиом. // Вестник Московского университета: Вычислительная математика и кибернетика, номер 2, 2007. Изд.: МГУ. С. 29-35.

12. Коваленко Д. С., Костенко В. А., Васин Е. А. Исследование применимости алгебраического подхода к анализу временных рядов. // Труды II Всероссийской научной конференции «Методы и средства обработки информации». Изд.: ВМиК МГУ, 2005. С. 553-559.

13. Коваленко Д. С., Костенко В. А. Метод построения алгоритмов распознавания, основанных на идеях аксиоматического подхода. // Труды XI Всероссийской конференции «Нейроинформатика-2009». Изд: МИФИ, 2009. С. 141-149.

14. Коваленко Д. С. Методы нечеткого сравнения и голосования- для построения распознавателей нештатного поведения динамических систем. // Труды V Международной конференции «ORM-2007». Изд: МАКС Пресс, 2007. С.123-125.

15. Коваленко Д. С. Метод автоматического построения алгоритмов распознавания участков фазовых траекторий. // «Моделирование и анализ информационных систем», Т. 16, JVM, 2009. Изд.: ЯрГУ. С. 6-21.

16. Козлов П.В:, Чен Б.Б. Вейвлет-преобразование и анализ временных рядов. // Вестник КРСУ, №2, 2002.

17. Крыжановский Б.В., Микаэлян A.JI. О распознающей способности нейросети на нейронах с параметрическим преобразованием частот. // Доклады АН, сер. мат. физика, т. 383, №3, с.318-321, 2002.

18. Ладыгин И. И., Филатов А. В., ЯньковС. Г. Кластеры на многоядерных процессорах. // М.: Издательский дом МЭИ, 2008.

19. Рудаков К. В., ЧеховичЮ.В. О проблеме синтеза обучающих алгоритмов выделения трендов (алгебраический подход). // Прикладная математика и информатика N 8, М.: Издательство факультета ВМиК МГУ, 2001. С. 97-114.

20. Уоссермен Ф. Нейрокомпыотерная техника. Теория и практика. М.: Мир, 1992.

21. Энслейн К., Рэлстон Э., Уилф Г. Статистические методы для ЭВМ. М: Наука, 1986.

22. Berg В. A., Stamatescu I. О. Neural networks and confidence limit estimates. // Lecture Notes in Physics, volume 508/1998. Springer Berlin / Heidelberg, 1998. P. 173-191.

23. Berndt D. J., Clifford J. Using dynamic time warping to find patterns in time series. // Workshop on Knowledge Discovery in Databases. USA : AAAI Press, 1994. P. 229-248.

24. Bouchner P. Driver's Micro-sleeps Detection Using Virtual Simulation. // Neural Network World, vol. 14, No. 1, 2004, Czech Republic. P. 3-15.

25. Buschmann F., Meunier R., Rohnert H., Sommerlad P., Stal M. A System of Patterns: Pattern-Oriented Software Architecture. ISBN:0-471-95869-7. John Wiley and Sons, West Sussex, England. 1996.

26. Das G., Gunopulos D., Mannila H. Finding Similar Time Series. // Proceedings of the Fourth International Conference on Knowledge Discovery and Data Mining. USA : AAAI' Press, 1996. P. 88-100.

27. Goldberg D. E. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1989.

28. Graham A. S. String searching algorithms. // World Scientific Publishing Company, UK, 1994.

29. Graves A., Bunke H., Fernandez S., Liwicki M., Schmidhuber J. Unconstrained online handwriting recognition with recurrent neural networks. // Advances in Neural Information Processing Systems 20, MIT Press, 2007.

30. Hamming R. Coding and information theory. Prentice Hall, USA, 1982.

31. Heitmann A., GuttkuhnR., AguirreA., Trutschel U., Moore-Ede M. Technologies for the monitoring and prevention of driver fatigue. // Proceedings of the First International

32. Driving Symposium on Human Factors in Driving, Assessment, Training and Vehicle Design, 2001. P. 81-86.

33. KeoghE. J., Michael J. Pazzani Derivative Dynamic Time Warping. // First SIAM International Conference on Data Mining (SDM'2001), Chicago, USA. 2001.

34. Keogh E. J., Smyth P. A probabilistic approach to fast pattern matching in time series databases. // Proceedings of the 3rd Conference on Knowledge Discovery in Database and Data Mining, 1997. P. 52-57.

35. Keogh E. J. Exact indexing of dynamic time warping. // Proceedings of Very Large Data Bases Conference, 2002. P. 406-417.

36. Keogh E. J., Pazzani M. J. Scaling up dynamic time warping to massive datasets. // 3rd European Conference on Principles and Practice of Knowledge Discovery in Databases, Springer, 1999. P. 1-11.

37. Kohavi R. A study of cross-validation and bootstrap for accuracy estimation and model selection. // IJCAI, 1995. P. 1137-1145.

38. Lauer F., Suen C. Y., Bloch G. A trainable feature extractor for handwritten digit recognition. // Pattern Recognition Journal, Elsevier, vol. 40, num. 6, 2007. P. 1816-1824.

39. Meuer H. W. The TOP500 Project: Looking Back over 15 Years of Supercomputing Experience. // University of Mannheim and Prometeus GmbH, Germany, 2008. PDF] http : //www.topbOO oi g/files/TO P500LookingbackHWM.pdf

40. Marr D. T. Hyper-Threading Technology Architecture and Microarchitecture. // Intel Technology Journal, Vol. 6, Issue 01, February, USA. 2002. P. 4-15.

41. Moore-Ede M.C., Trutschel U.E., Guttkuhn R., Heitmann A.M. Method of and apparatus for evaluation and mitigation of microsleep events. // Patent: 6070098, issued January 28, 2003.

42. Mitchell Tom M. Machine Learning. ISBN 0070428077. McGraw-Hill, USA. 1997.

43. Miiller M. Information Retrieval for Music and Motion. ISBN 3540740473. Springer-Verlag New York, Inc., USA. 2007.

44. Official OpenMP API specification for parallel programming. // PDF] http : //www.openmp.org/mp-documents/spec30.pdf

45. QuinnM.J. Parallel Programming in C with MPI and OpenMP. ISBN 0072822562. Oregon State University, 2003.

46. Plamondon R., Srihari S. N. Online and off-line handwriting recognition: a comprehensive survey. // Pattern Analysis and Machine Intelligence Journal, Vol. 22, Issue 1, Ecole Polytech., Montreal, Canada, 2000. P. 63 84.

47. Peters R. D., Kloeppel E., Alicandri E., Fox J. E., Thomas M. L., Thorne D. R., Sing H. C., Balwinski S. M. Effects of Partial and Total Sleep Deprivation On Driving Performance. // Public Roads, Vol. 62 Issue 4, 1999.

48. Schiffmann W., Joost M., Werner R. Optimization of the backpropagation algorithm for training multilayer perceptrons. // Tech. Rep. 15, University of Koblenz, Institute of Physics, Germany, 1994.

49. Svoboda P. Alternative Methods of EEG Signal Analysis. // Neural Network World, Vol.12, No.3, 2002, Czech Republic. P. 255-260.

50. The Message Passing Interface (MPI) standard. // HTML] http : /¡www-unix.mcs.anl.gov/mpi/index.htm

51. Vapnik V. Statistical Learning Theory. ISBN: 0471030031. Wiley-Interscience, USA, 1998.

52. Xinyu Guo, Xun Liang, Xiang Li A Stock Pattern Recognition Algorithm Based on Neural Networks. // Third International Conference on Natural Computation (ICNC 2007), vol. 2, 2007. P. 518-522.

53. Yi B., Jagadish H., Faloustos C. Efficient retrieval of similar time sequences under time warping. // Proceedings of International Conference on Data Engineering, 1998. P. 23-27.